1683 - xor1: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: 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...)
 
Fără descriere a modificării
 
Linia 1: Linia 1:
Se consideră o matrice cu un număr infinit de linii și coloane indexate începând cu 0.
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 (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.
Pe prima linie matricea conține șirul numerelor naturale (<code>0, 1, 2, 3 …</code>).
== 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: i1,j1,a,b,m.
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>.
i1,j1 reprezintă valorile pentru prima întrebare. Următoarele întrebări ik, jk vor fi generate una din alta folosind următoarea regulă:
 
ik=(a∗ik−1+b) mod m
= Cerința =
jk=(a∗jk−1+b) mod m
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: .
== Date de intrare ==
 
Fișierul de intrare xor1in.txt conține pe prima linie numerele naturale q,i1,j1,a,b,m separate prin câte un spaţiu.
reprezintă valorile pentru prima întrebare. Următoarele întrebări  vor fi generate una din alta folosind următoarea regulă:
== 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 ik coloana jk a matricei.
= Date de intrare =
== Restricții și precizări ==
Fișierul de intrare <code>xor1IN.txt</code> conține pe prima linie numerele naturale  separate prin câte un spaţiu.
*Pentru 10% dintre teste '''1 ≤ q ≤ 100, 1 ≤ m ≤ 100'''
 
*Pentru alte 10% dintre teste '''1 ≤ q ≤ 100000, 1 ≤ m ≤ 1000'''
= Date de ieșire =
*Pentru alte 30% dintre teste '''1 ≤ q ≤ 50, 1 ≤ m ≤ 30000'''
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".
*Pentru alte 50% dintre teste '''1 ≤ q ≤ 100000, 1 ≤ m ≤ 108'''
 
*'''0≤i1,j1<m'''
= Restricții și precizări =
*'''1 ≤ a,b ≤ 9'''
 
== Exemplul 1 ==
* Pentru 10% dintre teste <code>1 ≤ q ≤ 100</code>, <code>1 ≤ m ≤ 100</code>
; xor1in.txt
* Pentru alte 10% dintre teste <code>1 ≤ q ≤ 100000</code>, <code>1 ≤ m ≤ 1000</code>
: 4 2 3 1 1 5
* Pentru alte 30% dintre teste <code>1 ≤ q ≤ 50</code>, <code>1 ≤ m ≤ 30000</code>
; xor1out.txt
* Pentru alte 50% dintre teste <code>1 ≤ q ≤ 100000</code>, <code>1 ≤ m ≤ 108</code>
:2
*
:7
* <code>1 ≤ a,b ≤ 9</code>
:0
:1
<br>
== Exemplul 2 ==
; xor1in.txt
: 5 2 3 1 1 5
; xor1.out.txt
:1
:1
:1
:1
:1
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1683 - xor1
def generate_matrix_element(i, j, a, b, m):
    row = [(a * k + b) % m for k in range(j + 1)]
    return row


def main():
= Exemplul 1: =
    # Deschideți fișierul xor1in.txt pentru citire
<code>xor1IN.txt</code>
    with open("xor1in.txt", "r") as file:
4 2 3 1 1 5
        # Citiți valorile q, i1, j1, a, b, m din fișier
<code>xor1OUT.txt</code>
        q, i1, j1, a, b, m = map(int, file.readline().split())
2
7
0
1


    for _ in range(q):
=== Explicație ===
        current_row = generate_matrix_element(i1, j1, a, b, m)
Avem <code>q=4</code> întrebări.
        result = current_row[j1]
        # Utilizați result într-un mod necunoscut sau salvați-l într-un loc
        print(result)
        i1 = (a * i1 + b) % m
        j1 = (a * j1 + b) % m


if __name__ == "__main__":
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>
    main()
</syntaxhighlight>


== Explicatie ==
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:
Matricea este:
0 1 2 3 4 5 6 …
0 1 2 3 4 5 6 …
0 1 3 0 4 1 7 …
0 1 3 0 4 1 7 …
0 1 2 2 6 7 0 …
0 1 2 2 6 7 0 …
0 1 3 1 7 0 0 …
0 1 3 1 7 0 0 …
0 1 2 3 4 4 4 …
0 1 2 3 4 4 4 …
…
…
Se observă că pe pozițiile corespunzătoare întrebărilor avem valorile 2, 7, 0 și 1.
 
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>

Versiunea curentă din 18 mai 2024 16:48

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()
Adus de la „http://wiki.universitas.ro/index.php?title=1683_-_xor1&oldid=9813”