Fişierul intrare/ieşire:xor3.in, xor3.outSursăONI 2016, clasele 11-12
AutorAdrian PanaeteAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Xor3

Se consideră o matrice cu un număr infinit de linii şi coloane indexate începând cu 0. Pe prima linie matricea conţine şirul numerelor naturale (0, 1, 2, 3 ...). Pe fiecare linie începând cu linia a doua pe poziţia j matricea conţine suma xor a elementelor situate pe linia anterioara de la poziţia 0 până la poziţia j.

Cerinta

Se cere să se răspundă la Q întrebări de forma “Pentru i si j date, să se determine numărul situat pe linia i si coloana j a matricei”. Pentru a genera cele întrebări vor fi cunoscute următoarele valori: i1, j1, a, b, m. Dintre acestea, i1 si j1 reprezintă valorile pentru prima întrebare. Următoarele întrebări vor fi generate una din alta folosind următoarea regulă:

  • ik = (a*ik-1 + b) mod m
  • jk = (a*jk-1 + b) mod m

Date de intrare

Fişierul de intrare xor3.in conţine pe prima linie numerele naturale Q, i1, j1, a, b, m separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire xor3.out va conţine Q linii. Pe linia k se va afişa elementul situat pe linia ik coloana jk a matricei.

Restricţii

  • Pentru 10% din teste, 1 ≤ Q ≤ 100 si 1 ≤ m ≤ 100.
  • Pentru alte 10% din teste, 1 ≤ Q ≤ 100.000 si 1 ≤ m ≤ 1000.
  • Pentru alte 30% din teste, 1 ≤ Q ≤ 50 si 1 ≤ m ≤ 30.000.
  • Pentru restul de 50% din teste, 1 ≤ Q ≤ 100.000 si 1 ≤ m ≤ 108.
  • 0 ≤ i1, j1 < m.
  • 1 ≤ a, b ≤ 9.

Exemplu

xor3.inxor3.outExplicatie
4 2 3 1 1 5
2
7
0
1
Avem q = 4 întrebări.
Pentru i1 = 2, j1 = 3, a = 1, b = 1, m = 5 se obţin întrebările: (2, 3), (3, 4), (4, 0), (0, 1).
Matricea este:
0 1 2 3 4 5 6 ...
0 1 3 0 4 1 7 ...
0 1 2 2 6 7 0 ...
0 1 3 1 7 0 0 ...
0 1 2 3 4 4 4 ...
.................
Se observă că pe poziţiile corespunzătoare
întrebărilor avem valorile 2, 7, 0 şi 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?