ShortTaps
TCO05 Finals · 2005-08-16 · by Yarin
Problem Statement
You want to send some messages of various lengths (specified in the number of minutes it takes to send them), and don't want more than three of them to be completely intercepted. A message is considered to be intercepted if some malevolent person taps your connection the whole time the message is being sent (a partially tapped message won't do this person any good). Assuming that the connection is being tapped during interceptTime consecutive minutes, what's the shortest time you need to send all the messages so at most three of the messages can be completely intercepted?
Each message is sent in one continuous transmission, though any number of messages can be sent in parallel. You can only start sending a message at the beginning of a minute. The messages can be sent in any order.
Create a class ShortTaps containing the method leastTime which takes an
Constraints
- interceptTime will be between 1 and 100, inclusive.
- messageTimes will contain between 1 and 50 elements, inclusive.
- Each element in messageTimes will be between 1 and 100, inclusive.
10
{2, 3, 4, 5, 6, 7, 8}
Returns: 14
The optimal solution can be achieved by sending the messages according to this scheme: Time Message length --------------------- 0 2 min, 3 min, 6 min 3 8 min 6 5 min 7 4 min, 7 min
20
{14, 2, 9, 14, 17, 1, 3, 10, 5, 9, 25, 8, 11, 7}
Returns: 43
40
{30, 40, 50, 60, 70, 80, 90, 100}
Returns: 100
Only the two shortest messages have any chance of being intercepted, so all eight messages can be sent at time 0.
100
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 1601
100
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 1601
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ShortTaps with a public method int leastTime(int interceptTime, vector<int> messageTimes) · 74 test cases · 2 s / 256 MB per case