0254 - Puteri
Cerinţa
Se dau n perechi de numere naturale a, b. Să se determine pentru fiecare pereche, dacă există, cea mai mare putere a lui 2 din intervalul închis determinat de a şi b.
Date de intrare
Programul citeşte de la tastatură numărul n, apoi n perechi de numere a, b.
Date de ieşire
Programul va afişa pe câte o linie ecranului, pentru fiecare interval dat, cea mai mare putere a lui 2 din interval, sau 0, dacă intervalul nu conţine nici o putere al lui 2.
Restricţii şi precizări
1 ≤ n ≤ 10000 fiecare dintre numerele a şi b au cel mult 9 cifre. intervalele sunt închise
Exemplu:
Date de intrare 3 2 69 20 10 19 25
Date de ieşire 64 16 0
Rezolvare
def validate_input(n, pairs):
"""
Verifică dacă datele de intrare sunt valide conform cerinței.
"""
# n trebuie să fie un număr întreg pozitiv
if not isinstance(n, int) or n <= 0:
return False
# perechile de numere trebuie să fie listă de tupluri de 2 elemente
if not isinstance(pairs, list) or not all(isinstance(p, tuple) and len(p) == 2 for p in pairs):
return False
# fiecare număr din fiecare pereche trebuie să fie un număr întreg pozitiv
if not all(isinstance(p[0], int) and isinstance(p[1], int) and p[0] > 0 and p[1] > 0 for p in pairs):
return False
return True
def read_input():
"""
Primește datele de intrare de la tastatură și le validează.
În cazul în care datele de intrare nu sunt valide, se va returna None.
"""
n = int(input()) # citim numărul de perechi
pairs = []
for i in range(n):
a, b = map(int, input().split())
pairs.append((a, b))
# verificăm validitatea datelor de intrare
if not validate_input(n, pairs):
return None
return pairs
def largest_power_of_2(a, b):
"""
Determină cea mai mare putere a lui 2 din intervalul închis determinat de a și b.
"""
# găsim cea mai mare putere a lui 2 mai mică sau egală cu a și b
power = 0
while (1 << power) <= a or (1 << power) <= b:
power += 1
# dacă puterea găsită este mai mare decât 0 și este mai mică sau egală cu a și b,
# atunci returnăm valoarea acestei puteri; altfel, returnăm 0
if power > 0 and (1 << (power - 1)) <= a and (1 << (power - 1)) <= b:
return 1 << (power - 1)
else:
return 0
def main():
pairs = read_input() # citim și validăm datele de intrare
# pentru fiecare pereche, calculăm cea mai mare putere a lui 2 din intervalul închis determinat de a și b
for a, b in pairs:
print(largest_power_of_2(a, b))
if __name__ == '__main__':
main()
Explicatie
Acest cod definește trei funcții care sunt folosite pentru a rezolva problema dată:
Funcția validate_input(n, pairs) verifică dacă datele de intrare sunt valide conform cerinței. Verificările includ:
n trebuie să fie un număr întreg pozitiv pairs trebuie să fie o listă de tupluri de 2 elemente fiecare element din fiecare tuplu trebuie să fie un număr întreg pozitiv Funcția returnează True dacă datele de intrare sunt valide și False altfel.
Funcția read_input() primește datele de intrare de la tastatură și le validează folosind funcția validate_input(n, pairs). În cazul în care datele de intrare nu sunt valide, se va returna None. Altfel, funcția returnează perechile de numere.
Funcția largest_power_of_2(a, b) primește două numere întregi a și b și determină cea mai mare putere a lui 2 din intervalul închis determinat de a și b. Pentru a face acest lucru, se găsește cea mai mare putere a lui 2 mai mică sau egală cu a și b. Dacă puterea găsită este mai mare decât 0 și este mai mică sau egală cu a și b, atunci se returnează valoarea acestei puteri; altfel, se returnează 0.
Funcția main() apelează funcția read_input() pentru a citi și valida datele de intrare, apoi apelează funcția largest_power_of_2(a, b) pentru fiecare pereche de numere și afișează rezultatele obținute.