1683 - xor1
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
.
Cerința
Se cere să se răspundă la q
întrebări de forma “Pentru i
și j
date, să se determine numărul situat pe linia i
coloana j
a matricei”. Pentru a genera cele q
întrebări vor fi cunoscute următoarele valori: .
reprezintă valorile pentru prima întrebare. Următoarele întrebări vor fi generate una din alta folosind următoarea regulă:
Date de intrare
Fișierul de intrare xor1IN.txt
conține pe prima linie numerele naturale separate prin câte un spaţiu.
Date de ieșire
Fișierul de ieșire xor1OUT.txt
va conține q
linii. Pe linia k
se va afișa elementul situat pe linia coloana a matricei. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Restricții și precizări
- Pentru 10% dintre teste
1 ≤ q ≤ 100
,1 ≤ m ≤ 100
- Pentru alte 10% dintre teste
1 ≤ q ≤ 100000
,1 ≤ m ≤ 1000
- Pentru alte 30% dintre teste
1 ≤ q ≤ 50
,1 ≤ m ≤ 30000
- Pentru alte 50% dintre teste
1 ≤ q ≤ 100000
,1 ≤ m ≤ 108
1 ≤ a,b ≤ 9
Exemplul 1:
xor1IN.txt
4 2 3 1 1 5
xor1OUT.txt
2 7 0 1
Explicație
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
.
Exemplul 2:
xor1IN.txt
4 2 3 1 11 5
xor1OUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def check_restrictions(q, a, b, m):
if not (1 <= a <= 9 and 1 <= b <= 9 and 1 <= q <= 100000 and 1 <= m <= 10**8):
with open("xor1OUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return False
return True
def main():
with open("xor1IN.txt", "r") as f:
q, i, j, a, b, m = map(int, f.readline().strip().split())
if not check_restrictions(q, a, b, m):
return
results = []
for _ in range(q):
s = 0
P = 1
p = 0
while P <= j:
if ((i + P) & (j - P)) == 0:
s |= (1 << p)
p += 1
P <<= 1
results.append(s)
i = (a * i + b) % m
j = (a * j + b) % m
with open("xor1OUT.txt", "w") as g:
for result in results:
g.write(f"{result}\n")
if __name__ == "__main__":
main()