2611 - Raza

Cerinţa

Avem la dispoziție un chenar dreptunghiular format din oglinzi. O rază de lumină pornește din colțul stânga jos al dreptunghiului sub un unghi de 45 de grade față de latura de jos a dreptunghiului și lovește latura de sus sau latura din dreapta. Aici se reflectă (pornește spre o altă latură tot sub un unghi de 45 de grade față de latura de care s-a lovit). Își continuă drumul până când ajunge într-un colț al dreptunghiului.

Date de intrare

Programul citește de la tastatură dimensiunile chenarului a și b.

Date de ieşire

Programul va afișa pe ecran numărul de atingeri ale marginilor chenarului. Punctul de pornire și cel final nu se numără.

Restricții și precizări

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

Exemplu1

Intrare

3 8

Ieșire

Datele de intrare corespund restricțiilor impuse.

9

Exemplu2

Intrare

8 4

Ieșire

Datele de intrare corespund restricțiilor impuse.

1

Rezolvare

<syntaxhighlight lang="python" line> def validare_date(dim1, dim2):

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

def raza(dim1, dim2):

   n, m = dim1, dim2
   while dim2:
       r = dim1 % dim2
       dim1 = dim2
       dim2 = r
   numar_atingeri = n // dim1 + m // dim1 - 2
   print(numar_atingeri)

if __name__ == '__main__':

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

</syntaxhighlight>

Explicație

Programul primește două dimensiuni ca date de intrare și verifică dacă acestea sunt între 1 și 2 miliarde. Dacă valorile introduse sunt corecte, programul calculează numărul de puncte de pe circumferința cea mai mare posibilă, astfel încât aceste puncte să atingă două linii ce reprezintă dimensiunile introduse. Programul folosește algoritmul lui Euclid pentru a determina cel mai mare divizor comun (CMMD) între cele două dimensiuni și apoi calculează numărul de puncte de pe circumferința cea mai mare posibilă, astfel încât acestea să atingă liniile.