Editing 3641 - Xorstanta

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

În anul <code>2018</code>, 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 <code>n</code>. De asemenea, ai două variabile <code>a</code> și <code>b</code>, inițial egale cu <code>0</code>. Apoi, pentru fiecare număr <code>i</code> de la <code>1</code> la <code>n</code>, trebuie să alegem între <code>a = a ^ i</code> și <code>b = b ^ i</code>, unde cu <code>^</code> notăm operația <code>XOR</code>.

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

= Date de intrare =
Programul citește de la tastatură numărul <code>t</code>, reprezentând numărul de teste ce trebuie rezolvate.

Pe fiecare dintre următoarele <code>t</code> linii se va afla numărul <code>n</code>.

= Date de ieșire =
Programul va afișa pe fiecare dintre cele <code>t</code> linii răspunsul pentru inputul de pe linia <code>i+1</code>.

= Restricții și precizări =

* <code>1 ≤ t ≤ 100000</code>
* <code>1 ≤ n ≤ 1.000.000.000</code>
* Pentru <code>10</code> puncte, <code>1 ≤ n ≤ 20</code> și <code>t = 1</code>
* Pentru <code>30</code> de puncte, <code>1 ≤ n ≤ 100000</code> și <code>t = 1</code>

= Exemplu: =
Intrare
 4
 6
 30
 15
 18
Ieșire
 7
 31
 30
 43
<syntaxhighlight lang="python3">
def main():
    suma_max = 29
    numar_t = int(input("T: "))
    while numar_t > 0:
        n = int(input(""))
        numar_a, numar_b = 0, 0

        # Calculează 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

        # Calculează 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, 0, -1):4
            if (1 << j) <= n:
                numar_b += (1 << j)

        # Efectuam operația XOR între a și b și afișam rezultatul.
        numar_a = numar_a ^ numar_b
        print(str(numar_a + numar_b) + "\n")
        numar_t -= 1

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