VanceaGabriel: Pagină nouă: = Cerința = Fie un număr natural nenul `n`, cunoscut. RAU-Gigel alege un număr oarecare din intervalul închis `[1,n]`, fie acesta `x`. Apoi calculează “suma XOR” `S = 1 ^ 2 ^ ... ^ (x-2) ^ (x-1) ^ (x+1) ^ (x+2) ^ ... ^ n` pe care v-o comunică. Puteți să-l ghiciți pe `x` ? RAU-Gigel nu prea are răbdare, el vrea repede un răspuns de la voi. Am notat cu `^` operația `XOR` (operatorul d...

2024-01-13T19:39:00Z

Pagină nouă: = Cerința = Fie un număr natural nenul <code>n</code>, cunoscut. RAU-Gigel alege un număr oarecare din intervalul închis <code>[1,n]</code>, fie acesta <code>x</code>. Apoi calculează “suma XOR” <code>S = 1 ^ 2 ^ ... ^ (x-2) ^ (x-1) ^ (x+1) ^ (x+2) ^ ... ^ n</code> pe care v-o comunică. Puteți să-l ghiciți pe <code>x</code> ? RAU-Gigel nu prea are răbdare, el vrea repede un răspuns de la voi. Am notat cu <code>^</code> operația <code>XOR</code> (operatorul d...

New page

= Cerința =
Fie un număr natural nenul <code>n</code>, cunoscut. RAU-Gigel alege un număr oarecare din intervalul închis <code>[1,n]</code>, fie acesta <code>x</code>. Apoi calculează “suma XOR” <code>S = 1 ^ 2 ^ ... ^ (x-2) ^ (x-1) ^ (x+1) ^ (x+2) ^ ... ^ n</code> pe care v-o comunică. Puteți să-l ghiciți pe <code>x</code> ? RAU-Gigel nu prea are răbdare, el vrea repede un răspuns de la voi.

Am notat cu <code>^</code> operația <code>XOR</code> (operatorul de disjuncție exclusivă).

Ca să fie sigur că nu nimeriți din întâmplare răspunsul, RAU-Gigel vă testează de mai multe ori.

= Date de intrare =
Fișierul de intrare <code>ghicitoare.in</code> conține pe prima linie un număr natural <code>T</code> reprezentând numărul de teste / ghicitori pe care RAU-Gigel vi le propune, apoi <code>T</code> linii care conțin perechi de forma <code>n S</code>, separate printr-un spațiu, cu semnificația de mai sus.

= Date de ieșire =
Fișierul de ieșire <code>ghicitoare.out</code> va conține <code>T</code> rânduri, cu răspunsurile <code>x</code>, în ordinea solicitării, câte unul pe linie, la ghicitorile lui RAU-Gigel.

= Restricții și precizări =

* <code>1 ≤ T ≤ 10</code>, <code>1 ≤ n ≤ 1.000.000.000</code>, <code>0 ≤ S ≤ 1.000.000.000</code>, <code>1 ≤ x ≤ n</code>
* Pentru teste în valoare de <code>10</code> de puncte: <code>T = 2</code>, <code>n ≤ 100</code>
* Pentru teste în valoare de alte <code>30</code> de puncte: <code>n ≤ 1.000.000</code>

= Exemplu: =
<code>ghicitoare.in</code>
2
5 2
10 14
<code>ghicitoare.out</code>
3
5

=== Explicație ===
RAU-Gigel vă propune <code>2</code> ghicitori.

La prima ghicitoare avem: <code>n = 5, S = 2</code>. Numărul căutat este <code>3</code>. Intr-adevăr,

<code>S = 1 ^ 2 ^ 4 ^ 5 = |001| ^ |010| ^ |100| ^ |101| = |010| = 2</code> (am notat cu <code>|a|</code> reprezentarea binară a lui <code>a</code>)

La a doua ghicitoare avem: <code>n = 10, S = 14</code>. Numărul căutat este <code>5</code>. Intr-adevăr,

<code>S = 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10</code> are valoarea <code>14</code>.<syntaxhighlight lang="python3">
def main():
# Deschide fisierul de intrare si iesire
fin = open("ghicitoare.in", "r")
fout = open("ghicitoare.out", "w")

# Citim numarul de teste 'numar_t' din prima linie a fisierului de intrare.
numar_t = int(fin.readline())

# Parcurge fiecare test.
for i in range(numar_t):
# Citim linia de input și extragem cele două valori 'numar_n' și 'numar_s'.
line = fin.readline().split()
numar_n, numar_s = int(line[0]), int(line[1])

# Calculam xorrange pentru numar_n și adaugă rezultatul la numar_s.
# Scriem rezultatul în fisierul de iesire.
fout.write(str(xorrange(numar_n) ^ numar_s) + "\n")

# Inchidem fisierele de intrare si iesire.
fin.close()
fout.close()

def xorrange(numar_n):
# Folosim // pentru impartire la intreg in Python.
if (numar_n + 1) // 2 % 2 == 0:
rezultat = 0
else:
rezultat = 1

# Initializam i la 4 pentru a evita bucla infinita.
i = 4

# Parcurgem elementele în șir până la numar_n.
while (i >> 1) <= numar_n:
rest_impartire = numar_n % i

# Verificam daca restul impartirii este mai mic decat i / 2 si aplicam operatii.
if rest_impartire < (i >> 1):
pass
elif rest_impartire == 1 or rest_impartire % 2 == 0:
rezultat |= (i >> 1)

# Dublam valoarea lui i pentru a continua iteratia.
i <<= 1

return rezultat

if __name__ == "__main__":
main()
</syntaxhighlight>

4143 - Ghicitoare - Revision history