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

<syntaxhighlight lang="python" line="1"> 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()

</syntaxhighlight>