4143 - Ghicitoare

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

Date de ieșire

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

Restricții și precizări

• 1 ≤ T ≤ 10, 1 ≤ n ≤ 1.000.000.000, 0 ≤ S ≤ 1.000.000.000, 1 ≤ x ≤ n
• Pentru teste în valoare de 10 de puncte: T = 2, n ≤ 100
• Pentru teste în valoare de alte 30 de puncte: n ≤ 1.000.000

Exemplu:

ghicitoare.in

2
5 2
10 14

ghicitoare.out

3
5

Explicație

RAU-Gigel vă propune 2 ghicitori.

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

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

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

S = 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 are valoarea 14.<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>