1595 - Bomboane 1

Cerinţa

Lui Cristian, ca oricărui alt copil, îi plac bomboanele. A primit cadou de la prietenii lui cutii cu bomboane. Fiind multe cutii le-a numerotat: 1, 2, 3, … Desfăcând câteva, a văzut că există o legătură între numărul de pe etichetă și numărul de bomboane din cutie. Astfel în fiecare cutie sunt atâtea bomboane câți divizori pari are numărul de pe cutie. De exemplu cutia cu numărul 10 conține 2 bomboane, cutia cu numărul 8 conține 3 bomboane ș.a.m.d.

Cristian a ales la întâmplare două etichete x și y dorind să desfacă toate cutiile cu etichete cuprinse între x și y. Ajutați-l să determine prima cutie, etichetată cu a, și utima cutie, etichetată cu b, cu număr maxim de bomboane (x≤a≤b≤y), câte cutii n sunt cu acest număr de bomboane și care este acest număr d de bomboane.

Date de intrare

Fișierul de intrare bomboane1.in conține pe prima linie numerele naturale nenule x și y separate prin câte un spațiu.

Date de ieşire

Fișierul de ieșire bomboane1.out va conține o singură linie pe care vor fi scrise cele patru valori determinate, în ordinea din cerință (a b n d), separate prin câte un spațiu.

Restricții și precizări

• 1 ⩽ x ⩽ a ⩽ b ⩽ y⩽ 1.000.000.000
• y - x ⩽ 1000

Exemplul 1

bomboane1.in

10 20

bomboane1.out

Datele introduse corespund restricțiilor impuse.

12 20 3 4

Explicație

Dacă parcurgem toate numerele de la 10 la 20 constatăm că numărul maxim de divizori pari este 4 obținut la numerele 12, 16 şi 20 (3 numere).

Rezolvare

<syntaxhighlight lang="python" line> def validare_date(x, a, b, y):

   if not (1 <= x <= a <= b <= y <= 1_000_000_000 and y - x <= 1000):
       return False
   return True

def nr_bomboane(n):

   cnt = 0
   for i in range(2, int(n**0.5) + 1):
       if n % i == 0:
           if i % 2 == 0:
               cnt += 1
           if (n/i) % 2 == 0 and i != n // i:
               cnt += 1
       if i*i == n and i % 2 == 0:
           cnt -= 1
   if n % 2 == 0:
       cnt += 1
   return cnt

if __name__ == '__main__':

   with open("bomboane1.in", "r") as f_in:
       x, y = map(int, f_in.readline().split())

   a = x
   while a % 2 != 0:
       a += 1
   if a % 4 != 0:
       a += 2
   b = y
   while b % 2 != 0:
       b -= 1
   if b % 4 != 0:
       b -= 2

   max_numar_divizori = 0
   for i in range(a, b+1, 4):
       numar_divizori = nr_bomboane(i)
       if numar_divizori > max_numar_divizori:
           max_numar_divizori = numar_divizori

   cnt = 0
   for i in range(a, b+1, 4):
       numar_divizori = nr_bomboane(i)
       if numar_divizori == max_numar_divizori:
           cnt += 1
           if cnt == 1:
               min_div_box = i
           max_div_box = i

   with open("bomboane1.out", "w") as f_out:

       if validare_date(x, a, b, y):
           f_out.write("Datele sunt introduse corect.\n")
       else:
           f_out.write("Datele nu corespund restricțiilor impuse.")

       f_out.write(f"{min_div_box} {max_div_box} {cnt} {max_numar_divizori}\n")

</syntaxhighlight>

Explicație rezolvare

Funcția validare_date(x, a, b, y) verifică dacă datele de intrare respectă restricțiile și returnează True dacă sunt, altfel False.
Funcția nr_bomboane(n) calculează numărul de divizori pari ai unui număr n.
În funcția if __name__ == '__main__': se deschide fișierul de intrare și se citesc valorile x și y. Se calculează apoi valorile a și b ca fiind cele mai apropiate numere pare de x și y, respectiv. Se parcurge apoi intervalul de la a la b, cu pași de 4, și se calculează numărul de divizori pari ai fiecărui număr, iar din aceștia se găsește maximul. În a doua parcurgere a intervalului, se numără câte cutii au numărul maxim de divizori pari și se găsesc primele și ultimele cutii care îndeplinesc această condiție. Rezultatul final este afișat în fișierul de ieșire în formatul cerut de problemă.