| Fişierul intrare/ieşire: | xor3.in, xor3.out | Sursă | ONI 2016, clasele 11-12 |
| Autor | Adrian Panaete | Adăugată de |  Vlad Dumitru-Popescu •depevlad |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | xor3.out | Explicatie |
|---|---|---|
| 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 |
