Hi people,
I have here a sample exam I got from a friend. This will test your logic skills. I have tried to answer it and create my own program but my logic has many loopholes in it. :( You can help me and try to solve this by yourself as well. Please post your code to this thread. Thanks!
Problem 1: CD Dubbing Optimization
A feature now becoming available on some compact disc players allows the
user to optimize the copying of a compact disc to cassette. The user
specifies the size of the cassette; the player selects the tracks that will
best fill the first side of the cassette and plays them, then plays the
remaining tracks to be copied on the second side. You have been hired by a
CD player manufacturer to implement this feature for their model line.
The number of tracks and time of each track is supplied on every CD.
Your program will be given this information, and is to determine which
tracks will best fill the first side of a cassette, given the size of the
cassette in minutes. Cassettes come in sizes of 45, 60, and 90 minutes; the
size represents the total usable playing time of the cassette on both sides.
The tracks which best fill the first side of the cassette are the ones
with a total playing time closest to but not greater than half the cassette
size (Take note - It is best fit NOT first fit).
Input to your program will be the side of the cassette in minutes and the
number of tracks on the CD to be played (up to 17), followed by the time of
each track on the CD in order, starting with track 1. The size and number
of tracks will appear on one line, separated from each other by spaces. The
track times will appear in order, one per line starting in the first column,
with the minutes and seconds separated from each other by a colon. This
information will be repeated for each cassette/CD combination, and will be
terminated by end-of-file.
The output for each combination should consist of five lines. The first
line is to contain the total number of tracks and the size of the cassette,
appropriately labeled. The second line is to contain the label "Side 1: "
followed by the numbers of the tracks to be placed on the first side of the
cassette, in ascending order separated from each other by single spaces.
The third line is to contain the total time for the side (labeled, in mm:ss
format, with a leading zero if needed for the seconds field). The fourth
and fifth lines are to contain the same information for side 2. One blank
line should appear between the output for each combination.
You may assume that the cassette will be large enough to hold all the
tracks on the compact disc. If there is more than one set of tracks that
will yield the best possible result, any such set will be acceptable.
<Sample Input>
45 6
7:45
11:30
0:59
3:45
9:25
2:10
60 4
15:00
15:00
15:00
15:00
<Sample Output>
6 tracks on a C-45 cassette
Side 1: 1 2 3 6
Side 1 Elapsed Time 22:24
Side 2: 4 5
Side 2 Elapsed Time 13:10
4 tracks on a C-60 cassette
Side 1: 1 3
Side 1 Elapsed Time 30:00
Side 2: 2 4
Side 2 Elapsed time 30:00