Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 1213
Lumber Cutting

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Carpenters are often required to cut a set of pieces of given lengths, but can only obtain lumber at a fixed length. They must therefore determine how to use the length available most economically to make the parts. Lumber companies will not refund a partially cut two-by-four, and so using one foot of a twelve-foot two-by-four is no better of a solution than using all of it, since whatever remains will be discarded.

Each line of the input will constitute a "job", represented in the form

<board_length> <saw_width> <part1_length> <part2_length> ...

where

<board_length> is the length of the original lumber

<saw_width> is the width of the cutting tool, the amount of wood that will become sawdust with each cut

the remaining entries on the line constitute the list of the lengths of the desired parts, in non-decreasing order.

Here is an example of an input:

1000 100 250 250 500 650 1000
1000 50 200 250 250 500 650 970

All numbers in the input will be positive integers (thousandths of inches or centimeters if you like).

The board length will not exceed 30000, the saw width will not exceed 1000, and each part length will not exceed 9999.

The saw width will be less than the smallest part length.

Each part length will be less than or equal to the board length.

The number of part lengths on each line will not exceed 12.

Each line of input will provide valid input for one job, i.e., it will give rise to some output as described below.

For each job (each line of input), the output will consist of

one blank line

one line that displays the board length

one line that displays the saw width

one line that displays the number of boards needed for the job

the number of boards used for each job will be as small as possible

In the first job (with saw width = 100 units)

when two parts (lengths = 250 and 650 units) are cut from a 1000 unit long board, one cut will turn 100 units of lumber into sawdust and there is no discarded lumber.

when one 1000 unit long part is required, it is obtained as the entire board, without requiring any cuts

when two parts (lengths = 250 and 500 units) are cut from a 1000 unit long board, two cuts are required, 200 units of lumber will turn into sawdust, leaving a 50 unit piece of discarded lumber.

In the second job (with saw width = 50 units)

when two parts (lengths = 250 and 650 units) are cut from a 1000 unit long board, two cuts are required, turning 100 units of lumber into sawdust and leaving no discarded lumber.

when one 970 unit long part is required, one cut is required, turning 30 units of lumber into sawdust and leaving no discarded lumber.

Problem 7 by team x

Board length            =  1000
Saw width               =   100
Number of boards needed =     3

Board length            =  1000
Saw width               =    50
Number of boards needed =     4
End of problem 7 by team x

Observe every detail of the output, such as the exact wording of statements, upper/lower case variations, blank lines and blank spaces.

The board length, the saw width, and the number of boards are right-justified in a field of width 6 starting immediately after the equal sign.

A few lines of the above output will be reproduced here with a formatting template:

1         2         3         4         5         6
123456789012345678901234567890123456789012345678901234567890123456789
Number of boards needed =     4

Source: Rocky Mountain 1999
Submit    Status