2771 - Covorul
Cerinţa
Mama vrea să acopere cu covoare o cameră cu lungimea de dimensiunea_x metri și lățimea de dimensiunea_y metri. Ea are la dispoziție oricâte covoare în formă de pătrat, de orice dimensiune, număr natural și respectă următoarele reguli:
fiecare covor plasat are laturile paralele cu laturile camerei; covoarele așezate nu se suprapun; de fiecare dată se folosește cel mai mare covor care poate fi ales în acel moment; de fiecare dată covorul ales se plasează în așa fel încât zona neacoperită încă să fie un dreptunghi. Știind dimensiunile camerei să se determine care este dimensiunea maximă a unui covor folosit și numărul total de covoare folosite.
Date de intrare
Programul citește de la tastatură numerele dimensiunea_x și dimensiunea_y, reprezentând dimensiunile camerei.
Date de ieşire
Programul va afișa pe ecran numerele dim_max și numar_total reprezentând în ordine dimensiunea maximă a unui covor folosit și numărul total de covoare folosite.
Restricții și precizări
- dimensiunea_x, dimensiunea_y ∈ Ν
- 1 ⩽ dimensiunea_x, dimensiunea_y ⩽ 1.000.000.000
- dimensiunile covoarelor sunt numere naturale nenule
Exemplu1
- Intrare
- 10 3
- Ieșire
- Datele de intrare corespund restricțiilor impuse.
- 3 6
Explicație
Se folosesc 3 covoare de latură 3 și 3 covoare de latură 1. Dimensiunea maximă este 3.
Exemplu2
- Intrare
- 1 100
- Ieșire
- Datele de intrare corespund restricțiilor impuse.
- 1 100
Explicație
Se folosesc 100 covoare de latură 1. Dimensiunea maximă este 1.
Rezolvare
<syntaxhighlight lang="python" line> def validare_date(dimensiunea_x, dimensiunea_y):
if 0 <= int(dimensiunea_x) <= 1_000_000_000 and 0 <= int(dimensiunea_y) <= 1_000_000_000:
return True
return False
def calculeaza_numarul_covoarelor(dimensiunea_x, dimensiunea_y):
dim_max = min(dimensiunea_x, dimensiunea_y)
print(dim_max, end=' ')
numar_total = 0
while dimensiunea_x != 0 and dimensiunea_y != 0:
if dimensiunea_x > dimensiunea_y:
x = dimensiunea_x // dimensiunea_y
dimensiunea_x -= x * dimensiunea_y
numar_total += x
else:
x = dimensiunea_y // dimensiunea_x
dimensiunea_y -= x * dimensiunea_x
numar_total += x
print(numar_total)
if __name__ == '__main__':
dimensiunea_x, dimensiunea_y = map(int, input().split())
if validare_date(dimensiunea_x, dimensiunea_y):
print("\nDatele de intrare corespund restrictiilor impuse.\n")
calculeaza_numarul_covoarelor(dimensiunea_x, dimensiunea_y)
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
</syntaxhighlight>
Explicație
Programul citește de la tastatură dimensiunile unei camere si calculează numărul minim de covoare necesare pentru a acoperi podeaua întregii camere, folosind algoritmul lui Euclid pentru determinarea CMMDC-ului. Mai întâi se valideaza dimensiunile, apoi se calculeaza CMMDC-ul dintre cele două dimensiuni, pentru a obține dimensiunea maxima a unui covor. Apoi, se calculeaza numărul total de covoare necesare prin împărțirea produsului celor două dimensiuni la pătratul dimensiunii maxime si se afișează dimensiunea maximă a covorului și numărul total de covoare necesare.