Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2385

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2385

Multiplicação de Matrizes

 

Por OBI - Olimpíada Brasileira de Informática, 2010 BR Brazil

Timelimit: 1

O conglomerado indiano Tutu é um conjunto de empresas que atua nos mais diversos ramos da indústria, produzindo desde sapatos até aviões e foguetes. Por ser tão diversificada, precisa de grandes e rápidos sistemas para cálculos de contabilidade.

Um dos módulos mais importantes desse sistema é o de fornecimento de produtos, onde fica a base de dados de produtos e fornecedores. Um mesmo produto pode ser fornecido por vários fornecedores diferentes.

O sistema possui duas grandes matrizes: a matriz A, onde cada linha representa um produto e cada coluna representa um fornecedor. O valor da matriz na linha m e coluna n representa o preço do produto m se for comprado do fornecedor n.

A outra grande matriz é a B, onde cada linha representa um dia do mês e cada coluna é um produto. O valor da matriz na linha m e coluna n representa a quantidade do produto n a ser adquirido no dia m. Tal empresa tem uma política de fidelidade com seus fornecedores, e uma das práticas efetuadas pela empresa é, em um determinado dia, comprar todos os produtos necessários de um único fornecedor. Isto é, em um dia todos os produtos adquiridos serão comprados do fornecedor x, no outro dia do fornecedor y, e assim por diante.

Para auxiliar a escolha de qual fornecedor será o escolhido no dia, foi gerada outra matriz C, que é o resultado da multiplicação das matrizes A × B. Essa matriz diz o quanto será gasto pela empresa se adquirir todos os produtos de um determinado fornecedor em um determinado dia.

As matrizes A e B são quadradas (o número de linhas é igual ao número de colunas) e têm valores definidos pelas fórmulas:

Aij = (P × i + Q × j) (mod X)
Bij = (R × i + S × j) (mod Y)

onde i é o índice da linha da matriz e j é o índice da coluna da matriz (todos os índices vão de 1 até N). Os inteiros P, Q, R, S, X e Y são parâmetros constantes, que definem as duas matrizes A e B.

Escreva um programa que, dados os parâmetros das matrizes A e B, e a posição de uma das entradas as matriz C, calcula o valor daquela entrada.

 

Entrada

 

A primeira linha da entrada contém um inteiro N, indicando as dimensões das matrizes A, B e C (2 ≤ N ≤ 105). A linha seguinte contém seis inteiros P, Q, R, S, X e Y, indicando os parâmetros das matrizes A e B (2 ≤ X, Y ≤ 104; 0 ≤ P, Q < X; 0 ≤ R, S < Y).

Finalmente, a última linha da entrada contém dois inteiros I e J, indicando a linha e a coluna da matriz C a serem consultados (1 ≤ I, JN).

 

Saída

 

Seu programa deve imprimir uma única linha contendo o valor da matriz C na linha e coluna especificadas.

 

 

 

Exemplos de Entrada Exemplos de Saída

3

4 3 2 3 5 6

2 2

18

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
typedef long long ll;
ll resposta;
int main() {
    int ordem, p, q, r, s, x, y, a, b;
    scanf("%d %d %d %d %d %d %d %d %d", &ordem, &p, &q, &r, &s, &x, &y, &a, &b);
    for (int i = 1; i  < = ordem; i++) {
        ll elemento1 = (p * a + q * i) % x;
        ll elemento2 = (i * r + s * b) % y;
        resposta += elemento1 * elemento2;
    }
    printf("%lld\n", resposta);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
4 3 2 3 5 6
2 2

Output

x
+
cmd
18
Advertisements

Demonstration


Previous
#2384 Beecrowd Online Judge Solution 2384 Tradutor Alienígena Solution in C, C++, Java, Js and Python
Next
#2386 Beecrowd Online Judge Solution 2386 Telescópio Solution in C, C++, Java, Js and Python