| Cutting Up |
Quilters often have to cut fabric into squares. To do this, they have a special tool (called a rotary cutter) that can cut through many layers of fabric at a time. The exact number of layers depends on the type of fabric being cut. In using a rotary cutter, the problem is not how long the cut needs to be (it is just as easy to make a cut one centimeter long as it is to make a cut 20 centimeters long), but how many cuts need to be made.
For example, to cut a 2 by 3 piece of fabric into 1 by 1 squares takes five cuts if only one layer of fabric may be cut at a time:
If two layers may be cut at a time, it will only take three cuts (the two pieces of fabric can be placed on top of each other after the first cut, so when the second and third cuts are made, they will also make the fourth and fifth cuts).
In cutting fabric, pieces may be placed on top of each other. Pieces do not need to be of identical shapes to be put on top of each other. For example, if the fabric above had first been cut vertically, a 1 by 2 piece could have been put on top of the 2 by 2 piece. Fabric may be rearranged between cuts. Fabric can not be folded. For example, to cut a 1 by 3 piece of fabric into squares will take 2 cuts, not 1 (if the fabric were folded in half before cutting). Quilters are thrifty people so they never have any waste: if a piece of fabric is m by n, they will get mn pieces from it.
Write a program to determine the fewest cuts necessary to cut a piece of fabric into squares.
The input will consist of a number of lines. Each line will have 3 integers describing the fabric to be cut. The first is the maximum number of layers that can be cut at a time (between 1 and 200) and the last two are the dimensions (between 1 and 20 in each dimension).
A line consisting of the values 0 0 0 will mark the end of input. This line should not be processed.
For each line, echo the dimensions and give the smallest number of cuts that are necessary to cut it entirely into 1 by 1 squares. Use the format given in the Sample Output below.
Leave a blank line after each line of output.
1 3 2 1 5 5 2 3 2 3 2 3 10 5 5 1 2 1 0 0 0
3 by 2 takes 5 cuts 5 by 5 takes 24 cuts 3 by 2 takes 3 cuts 2 by 3 takes 3 cuts 5 by 5 takes 6 cuts 2 by 1 takes 1 cuts