3641 - Xorstanta

Cerința

Totuși, combatanții au și ei regretele lor, regrete pe care vor să le depășească

În anul 2018, Olimpiada Națională de Informatică s-a ținut în Constanța, iar concurenții au fost triști că nicio problemă nu s-a numit Xorstanța.

Se dă un număr n. De asemenea, ai două variabile a și b, inițial egale cu 0. Apoi, pentru fiecare număr i de la 1 la n, trebuie să alegem între a = a ^ i și b = b ^ i, unde cu ^ notăm operația XOR.

Calculați suma maximă ce se poate obține între a și b.

Date de intrare

Programul citește de la tastatură numărul t, reprezentând numărul de teste ce trebuie rezolvate.

Pe fiecare dintre următoarele t linii se va afla numărul n.

Date de ieșire

Programul va afișa pe fiecare dintre cele t linii răspunsul pentru inputul de pe linia i+1.

Restricții și precizări

• 1 ≤ t ≤ 100000
• 1 ≤ n ≤ 1.000.000.000
• Pentru 10 puncte, 1 ≤ n ≤ 20 și t = 1
• Pentru 30 de puncte, 1 ≤ n ≤ 100000 și t = 1

Exemplu:

Intrare

4
6
30
15
18

Ieșire

7
31
30
43

<syntaxhighlight lang="python3"> def calculeaza_suma_maxima_xor(n):

   # Setăm suma_max la 29, valoare constantă folosită în bucla for.
   suma_max = 29
   numar_a, numar_b = 0, 0

   # Calculăm valoarea lui a în funcție de restul împărțirii lui n la 4.
   if n % 4 == 1:
       numar_a = 1
   elif n % 4 == 2:
       numar_a = n + 1
   elif n % 4 == 3:
       numar_a = 0
   else:
       numar_a = n

   # Calculăm valoarea numarului b în funcție de puterile lui 2 până la 2^29 care sunt mai mici sau egale cu n.
   for j in range(suma_max, -1, -1):
       if (1 << j) <= n:
           numar_b += (1 << j)

   # Efectuăm operația XOR între a și b și returnăm suma rezultată.
   numar_a = numar_a ^ numar_b
   return numar_a + numar_b

def main():

   # Citim numărul de teste.
   numarul_t = int(input("T: "))

   # Parcurgem fiecare test.
   for _ in range(numarul_t):
       # Citim valoarea n pentru testul curent.
       numarul_n = int(input("n: "))

       # Calculăm și afișăm suma maximă XOR pentru valoarea n dată.
       suma_maxima_xor = calculeaza_suma_maxima_xor(numarul_n)
       print(suma_maxima_xor)

if __name__ == "__main__":

   main()

</syntaxhighlight>