cartoane
C.C, elev
într-a 10-a, viseaza sa termine odata scoala si sa se angajeze la firma
tatalui sau, firma de papetarie, publicitate si reclame luminoase. Pentru început
i s-a promis postul de muncitor la departamentul "Cartoane" si aici
îl asteapta cartoane dreptunghiulare de diferite dimensiuni din care trebuie
sa obtina alte cartoane dreptunghiulare, mai mici, prin taierea cartoanelor
mari cu ajutorul unui dispozitiv mecanic numit ghilotina.
Pentru a fi promovat în functia de sef al departamentului "Cartoane",
el are de rezolvat o problema de proiectare a procesului de taiere: pentru un
carton dreptunghiular de dimensiuni L si H date, se cere sa se gaseasca o modalitate
de taiere cu ajutorul ghilotinei pentru a obtine un numar maxim de cartonase
dreptunghiulare de dimensiuni A si B date. Se stie ca singura operatie admisa
este asezarea ghilotinei cu lama paralela cu una dintre laturile unui carton
dreptunghiular si taierea acestuia, de la o margine pâna la cealalta,
în doua bucati dreptunghiulare mai mici.
Cerinta
Pentru dimensiunile
L si H ale cartonului initial si dimensiunile A si B ale cartonaselor comandate
de client, sa se determine numarul maxim da cartonase care se pot obtine din
cartonul initial.
Date de
intrare
Fisierul de intrare cartoane.in
contine pe prima linie numerele natural L
H, separate printr-un spatiu, reprezentand dimensiunile cartonului initial.
Pe cea de a doua linie se afla numere naturale A
si B separate printr-un spatiu,
care reprezinta dimensiunile fiecaruia dintre cartoanele comandate.
Date de
iesire
Fisierul de iesire cartoane.out
va contine o singura linie pe care se scrie un singur numar reprezentând
numarul maxim de cartoane care se pot obtine.
Restrictii
si precizari
- 1 <= L, H <= 150
- 1 <= A, B <= 50
- Toate datele de intrare
sunt numere naturale.
Exemplu
|
cartoane.in |
cartoane.out
|
Explicatie |
12
21
5 8
|
5
|
O modalitate de taiere
posibila care conduce la numarul maxim de cartonase este descrisa mai
jos:
 |
Taietura verticala
la 16 cm. formeaza dreptunghiurile I (cel din stanga) si II (cel
din dreapta)
Dreptunghiul
II se taie orizontal la 8 cm obtinându-se un cartonas si un
rest (deseu).
Dreptunghiul
I se taie orizontal la 5 cm si apoi dreptunghiul mai mare obtinut
se taie din nou orizontal la 5 cm. Se obtin trei fâsii de
5, 5 si respectiv 2 cm. Fâsia de 2 cm poate fi aruncata.
Fiecare dintre
cele 2 fâsii se taie vertical la 8 cm obtinându-se 4
cartonase.
S-au obtinut
în total 5 cartonase.
|
|
Timp maxim de executie/test:
0.1 secunde
prof. Rodica
Pintea
Liceul "Grigore
Moisil" Bucuresti
Contact:ro_dica@yahoo.com