CCC '02 S4 - Bridge Crossing

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2002 Stage 1, Senior #4

A rope bridge traverses a deep gorge. People may cross the bridge in groups, but there is a limit (M) to the size of the group. The time taken for a group to cross is determined by the slowest member. You are responsible for safety on the bridge and part of your job is to control the groups crossing. People are waiting in a queue (line), when the previous group has crossed you tell the next few people they can now cross. Groups can be of different sizes; no group can contain more than M people, and the goal is to get everyone over in the shortest time, all the time maintaining the order of the people in the queue.

Input Specification

The first line of the input contains an integer M (1 \le M \le 20). The second line contains Q (1 \le Q \le 100), the length of the queue waiting to cross. For each person in the queue, a pair of input lines follows. The first of these is the name of the person, and the second is that person's individual time to cross the bridge. Recall that a group crossing time will be the maximum crossing time for time for any individual in the group.

Output Specification

The first line of the output is to give the total crossing time for the entire queue of people. Then, output the names of the people in each group, one group per line, which will obtain the minimum overall crossing time. If several groupings yield the same overall crossing time, any such grouping may be listed.

Sample Input

2
5
alice
1
bob
5
charlie
5
dobson
3
eric
3

Sample Output

Total Time: 9
alice
bob charlie
dobson eric

Comments


  • 10
    Evang  commented on June 29, 2020, 5:22 p.m. ← edited

    What are the constraints on how long a person takes to cross the bridge?

    Edit: the constraint is the range [1, 102]


  • -13
    pblpbl  commented on April 23, 2020, 7:06 p.m. ← edit 3

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 14
      chika  commented on April 24, 2020, 5:58 a.m.

      This is incorrect.

      You must output groups in the order that they appear in the queue (a group cannot skip a group ahead of it in the queue), but within a given group you are permitted to print the people in the group in any order. The custom checker for this problem checks that each group has the correct people in it but does not check for a specific ordering.


  • 14
    Plasmatic  commented on Oct. 29, 2018, 1:56 a.m. ← edit 2

    If anyone is having trouble with WA, I recommend the following test case

    3
8
a
3
b
3
c
3
d
1
e
1
f
3
g
3
h
3

    Total time should be 7


    • 2
      Lemonsity  commented on Oct. 29, 2018, 4:21 p.m.

      This is my result:

      Total Time: 7

      d e

      a b c

      f g h

      is it correct?


      • 4
        dechen4198  commented on March 6, 2022, 2:03 a.m.

        Order in the queue matters (a b c should come before d e) so for those reading the comments and wondering, it's not correct.


  • 5
    Lemonsity  commented on Oct. 28, 2018, 12:01 a.m. ← edited

    does the order matter? For example, given the same input as the example, will the judge count it wrong if I output:

    eric dobson

    charlie bob

    alice


    • 3
      Blazebot99  commented on Feb. 18, 2019, 10:27 p.m.

      Order most certainly matters as the question explicitly states that you have to keep the order of the queue when making groups.


    • -16
      Arihan10  commented on Jan. 21, 2019, 9:08 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • 1
      Plasmatic  commented on Oct. 29, 2018, 1:57 a.m.

      I recommend just pushing the output to an arraylist/vector first and then reversing it before printing it back out again