Editing 1683 - xor1

Se consideră o matrice cu un număr infinit de linii și coloane indexate începând cu <code>0</code>.

Pe prima linie matricea conține șirul numerelor naturale (<code>0, 1, 2, 3 …</code>).

Pe fiecare linie începând cu linia a doua pe poziția <code>j</code> matricea conține suma xor a elementelor situate pe linia anterioara de la poziția <code>0</code> până la poziția <code>j</code>.

= Cerința =
Se cere să se răspundă la <code>q</code> întrebări de forma “Pentru <code>i</code> și <code>j</code> date, să se determine numărul situat pe linia <code>i</code> coloana <code>j</code> a matricei”. Pentru a genera cele <code>q</code> î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 <code>xor1IN.txt</code> conține pe prima linie numerele naturale  separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>xor1OUT.txt</code> va conține <code>q</code> linii. Pe linia <code>k</code> 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 <code>1 ≤ q ≤ 100</code>, <code>1 ≤ m ≤ 100</code>
* Pentru alte 10% dintre teste <code>1 ≤ q ≤ 100000</code>, <code>1 ≤ m ≤ 1000</code>
* Pentru alte 30% dintre teste <code>1 ≤ q ≤ 50</code>, <code>1 ≤ m ≤ 30000</code>
* Pentru alte 50% dintre teste <code>1 ≤ q ≤ 100000</code>, <code>1 ≤ m ≤ 108</code>
*
* <code>1 ≤ a,b ≤ 9</code>

= Exemplul 1: =
<code>xor1IN.txt</code>
 4 2 3 1 1 5
<code>xor1OUT.txt</code>
 2
 7
 0
 1

=== Explicație ===
Avem <code>q=4</code> întrebări.

Pentru <code>i1=2</code>, <code>j1=3</code>, <code>a=1</code>, <code>b=1</code>, <code>m=5</code> se obțin întrebările: <code>(2,3)</code>, <code>(3,4)</code>, <code>(4,0)</code>, <code>(0,1)</code>

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 <code>2</code>, <code>7</code>, <code>0</code> și <code>1</code>.

== Exemplul 2: ==
<code>xor1IN.txt</code>
 4 2 3 1 11 5
<code>xor1OUT.txt</code>
 '''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>