3641 - Xorstanta: Diferență între versiuni
De la Universitas MediaWiki
(Pagină nouă: = 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 <...) |
(sc) |
||
Linia 36: | Linia 36: | ||
43 | 43 | ||
<syntaxhighlight lang="python3"> | <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(): | 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__": | if __name__ == "__main__": | ||
main() | main() | ||
</syntaxhighlight> | </syntaxhighlight> |
Versiunea curentă din 15 ianuarie 2024 10:19
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
șit = 1
- Pentru
30
de puncte,1 ≤ n ≤ 100000
șit = 1
Exemplu:
Intrare
4 6 30 15 18
Ieșire
7 31 30 43
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()