cartoane
C.C, a 10th grade student, dreams of finishing school and working for his father's company, a paper, advertising and billboard ads company. For start he was promised a position in the "Cardboards" department and he has rectangular pieces of cardboard of different sizes waiting for him there, from which he has to make smaller rectangular pieces of cardboard, by cutting the big ones with a mechanical device called a guillotine.
In order to be promoted head of the "Cardboards" department he has
to solve a cutting process design problem: for a rectangular piece of cardboard
of sizes L and H
which are given the task is to find a cutting method using a guillotine so as
to obtain the maximum number of rectangular pieces of cardboard of sizes A
and B which are also given. What
is known is that the only acceptable operation is placing the guillotine with
the blade parallel to one of the sides of the rectangular piece of cardboard
and cutting it, from one part to the other, into two smaller rectangular pieces.
Task
Determine
the maximum number of cardboard pieces that can be obtained from the initial
piece of cardboard while knowing sizes L
and H of the initial piece of
cardboard and sizes A and B
of the pieces of cardboard ordered by the client.
Input Data
Input file cartoane.in
contains on the first line two positive integers L
H, separated by a space, representing the sizes of the initial piece
of cardboard. The second line contains two positive integers A
and B separated by a space, representing
the sizes of each of the ordered pieces of cardboard.
Output Data
Output file cartoane.out will contain one line with a single number representing the maximum number of pieces of cardboard that can be obtained.
Constraints and Statements
- 1 <= L, H <= 150
- 1 <= A, B <= 50
- All input data is made up of positive integers.
Example
| cartoane.in |
cartoane.out
|
Explanation |
12 21
5 8
|
5
|
One possible cutting method that can lead to finding the maximum number of pieces of cardboard is outlined below:
 |
The vertical
cut at 16 cm. forms rectangles I (the left one) and II (the right
one).
Rectangle II is cut horizontally at 8 cm obtaining a piece of cardboard and some waste.
Rectangle I is cut horizontally at 5 cm and then the larger rectangle obtained is again cut horizontally at 5 cm. Three strips of 5, 5 and namely 2 cm. are obtained The 2 cm strip can be thrown away.
Each of the
two strips is cut vertically at 8 cm obtaining 4 pieces of cardboard.
A total of 5 pieces of cardboard are obtained.
|
|
Time limit: 0.1 seconds/test
prof. Rodica Pintea
Bucharest "Grigore Moisil" High-School
Contact:ro_dica@yahoo.com