0254 - Puteri: Difference between revisions

Revision as of 16:19, 26 April 2023

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

<syntaxhighlight lang="python" line> def validare(n, a, b):

   for i in range(n):
       if not (1 <= n <= 10_000):
           return False
       if not (0 <= a[i] < 1_000_000_000 and 0 <= b[i] < 1_000_000_000):
           return False
   return True

def puteri(n, a, b):

   for i in range(n):
       p = 1
       while p * 2 <= max(b[i], a[i]):
           p = p * 2
       if p >= min(a[i], b[i]):
           print(p)
       else:
           print(0)

if __name__ == '__main__':

   n = int(input())
   a, b = [], []
   for i in range(n):
       ai, bi = map(int, input().split())
       a.append(ai)
       b.append(bi)

   if validare(n, a, b):
       print("Date de intrare valide")
       puteri(n, a, b)
   else:
       print("Date de intrare invalide")

</syntaxhighlight>

@@ Line 27: / Line 27: @@
 ==Rezolvare==
 <syntaxhighlight lang="python" line>
-def validate_input(n, pairs):
+def validare(n, a, b):
-     """
+     for i in range(n):
-    Verifică dacă datele de intrare sunt valide conform cerinței.
+         if not (1 <= n <= 10_000):
-    """
+            return False
-    # n trebuie să fie un număr întreg pozitiv
+        if not (0 <= a[i] < 1_000_000_000 and 0 <= b[i] < 1_000_000_000):
-    if not isinstance(n, int) or n <= 0:
+            return False
-         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():
+def puteri(n, a, b):
-    """
-    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())
+         p = 1
-         pairs.append((a, b))
+        while p * 2 <= max(b[i], a[i]):
+            p = p * 2
-    # verificăm validitatea datelor de intrare
+         if p >= min(a[i], b[i]):
-    if not validate_input(n, pairs):
+            print(p)
-         return None
+         else:
+            print(0)
-    return pairs
+if __name__ == '__main__':
+    n = int(input())
+    a, b = [], []
+    for i in range(n):
+        ai, bi = map(int, input().split())
+        a.append(ai)
+        b.append(bi)
-def largest_power_of_2(a, b):
+    if validare(n, a, b):
-    """
+        print("Date de intrare valide")
-    Determină cea mai mare putere a lui 2 din intervalul închis determinat de a și b.
+         puteri(n, a, 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
+         print("Date de intrare invalide")
-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()
 </syntaxhighlight>
-==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.