Cassette
SRM 125 · 2002-12-16 · by Yarin
Problem Statement
Old cassette tapes have two sides where you can record music. The length of both sides are the same, and the start of the first side (side A) is the end of the second side (side B). For instance, if the tape length (one side) is 45 minutes, and you're currently at position 13 minutes on side A, switching sides would result in being at position 32 minutes on side B. When you've reached the end of one side, the tape automatically switches sides.
In this problem, the time unit will be one second. This means that all songs will start and end at exact seconds, and you can only start listening, switch sides and stop listening at exact seconds.
Given a tape and the location of several songs on the tape, as well as how good you think each song is (a positive integer), you want to know where on the tape you should start listening in order to maximize your listening enjoyment during a given amount of time. You're allowed to switch sides anytime, but you're only allowed to listen to the same second (on the same side) once. You may assume a side switch takes 0 seconds.
The location of the songs on the tape will be given as a list of elements where each element describes a song. The format of each element is (quotes are for clarity only)
"<side> <start> <duration> <value>"
where <side> is the side of the tape (uppercase 'A' or 'B'), <start> is where on the side the song begins, <duration> is the length of the song, and <value> is a positive integer describing how good you think the song is (the "enjoyment value"). Both <start> and <duration> will be in the format mm:ss which describes the amount of minutes (two digits, leading zero if necessary) and seconds (two digits, leading zero if necessary) where seconds is between 00 and 59 inclusive. There will be exactly one space between each of the four values above, and each element will contain no other extra characters.
The method should return an integer, the maximum total enjoyment value. For each second you listen, the total enjoyment value is increased with the enjoyment value of the song at that position.
Create a class Cassette containing the method bestListen which takes an
Notes
- A song will always end on the same side as it begins (although it may end at the very end of that side).
- A song may start immediately after another song ends.
- All songs will have a duration of at least 1 second.
- Empty parts of the tape are considered as having enjoyment values 0.
- You're not allowed to fast forward, rewind or play the tape backwards.
Constraints
- songs will contain between 0 and 30 elements, inclusive.
- Each element in songs will be in the format specified above.
- The enjoyment value for each song will be between 1 and 100, inclusive, and contain no leading zeros.
- tapelength will be between 1 and 5400, inclusive.
- listeningtime will be between 1 and 2*tapelength, inclusive.
- No two songs will overlap each other on the same side.
- No song will start or end outside the tape.
36
{"A 00:05 00:05 4",
"B 00:19 00:10 7",
"A 00:14 00:04 6",
"A 00:22 00:12 1",
"B 00:03 00:09 3",
"B 00:16 00:01 5",
"A 00:00 00:05 2"}
20
Returns: 110
The songs on this tape are plotted below, each character represents one second: Side A: 2222244444----6666----111111111111-- Side B: -------7777777777--5----333333333--- On this tape, you get the best total listening value by starting to listen 14 seconds into side A, after four seconds switch to side B, after another 12 seconds switch back to side A and then listen the last four seconds. The X below marks the part of the tape that has been listened to. Side A: 222224XXXX----XXXX------------------ Side B: ------XXXXXXXXXXXX-5----333333333--- This will yield the answer 110.
46
{"A 00:05 00:03 8",
"A 00:04 00:01 2",
"B 00:02 00:06 1",
"B 00:22 00:04 4",
"B 00:28 00:09 8",
"B 00:16 00:01 8",
"A 00:26 00:02 7",
"A 00:10 00:07 5"}
30
Returns: 143
The best result can be achieved by starting to listen 23 seconds into side B, then listening for 18 seconds, switching to side A and then listening 12 seconds. This will yield 4*3 + 8*9 + 8*3 + 5*7 = 143.
1320
{"B 00:02 02:41 38","A 13:10 02:12 35",
"B 02:58 03:10 32","B 12:48 03:55 71",
"A 06:51 00:20 45","A 17:39 01:41 13",
"B 17:23 02:45 26","A 09:43 03:20 6",
"A 19:25 01:26 24","B 02:47 00:09 53",
"A 01:52 01:07 44","B 11:55 00:46 48",
"A 15:25 00:50 34","B 20:13 00:10 75",
"B 10:39 01:12 74","A 00:01 01:50 21",
"B 06:15 03:14 52","A 03:01 03:41 47",
"A 16:24 01:06 62","A 08:13 01:23 49",
"B 16:48 00:35 59","B 09:35 01:00 20",
"A 20:51 01:03 36","B 20:32 01:11 63",
"A 07:13 00:51 48"}
1765
Returns: 80314
15
{"B 00:00 00:10 20","A 00:00 00:10 22"}
11
Returns: 240
5216
{"B 00:00 11:14 60","A 00:01 18:16 23",
"B 11:14 06:43 26","B 17:59 01:07 33",
"A 18:18 07:01 19","B 19:07 17:27 54",
"A 25:24 11:13 97","A 36:38 09:19 90",
"B 36:41 18:18 33","A 46:00 04:22 51",
"A 50:28 19:32 41","B 55:06 16:18 62",
"A 70:02 01:36 3", "B 71:31 12:29 32",
"A 71:43 15:12 77"}
5216
Returns: 330607
Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Cassette with a public method int bestListen(int tapelength, vector<string> songs, int listeningtime) · 61 test cases · 2 s / 256 MB per case