0378 - Pavare

Cerinţa

Curtea bunicului este de formă dreptunghiulară cu dimensiunile cunoscute. Bunicul dorește pavarea curții cu plăci de piatră. Firma furnizoare produce plăci de piatră de formă pătrată, de orice dimensiune, iar bunicul dorește să folosească plăci de o singură dimensiune, astfel încât să folosească cât mai puține plăci. NU este posibilă tăierea plăcilor de piatră, iar curtea trebuie pavată în întregime.

Cunoscând dimensiunile curții, determinați numărul minim de plăci cu care poate fi pavată curtea și dimensiunea acestora.

Date de intrare

Programul citește de la tastatură două numere naturale dim1 dim2, reprezentând dimensiunile curții.

Date de ieşire

Programul afișează pe ecran numerele numar_placi și dim_max, separate prin exact un spațiu, reprezentând numărul minim de plăci cu care poate fi pavată curtea și dimensiunea acestora.

Restricții și precizări

• dim1, dim2 ∈ Ν
• 1 ⩽ dim1, dim2⩽ 1.000.000.000

Exemplu1

Intrare

12 16

Ieșire

Datele de intrare corespund restricțiilor impuse.

12 4

Explicație

Dimensiunea maximă plăcilor cu care se poate pava curtea este 4. Se vor folosi 12 plăci.

Exemplu2

Intrare

26 8

Ieșire

Datele de intrare corespund restricțiilor impuse.

52 2

Explicație

Dimensiunea maximă plăcilor cu care se poate pava curtea este 2. Se vor folosi 52 plăci.

Rezolvare

<syntaxhighlight lang="python" line> import math

def validare_date(dim1, dim2):

   flag = False
   if 0 <= int(dim1) < 1_000_000_000 and 0 <= int(dim2) < 1_000_000_000:
       flag = True
   return flag

def pavare_curte(dim1, dim2):

   if dim1 < dim2:
       dim1, dim2 = dim2, dim1
   cmmdc = math.gcd(dim1, dim2)
   dim_max = cmmdc
   numar_placi = dim1 * dim2 // (dim_max ** 2)
   print(numar_placi, dim_max)

if __name__ == '__main__':

   dim1, dim2 = map(int, input().split())
   if validare_date(dim1, dim2):
       print("\nDatele de intrare corespund restrictiilor impuse.\n")
       pavare_curte(dim1, dim2)
   else:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>