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

Further facts about the input:

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