ECOO '19 R1 P4 - Bus Route

View as PDF
Submit solution
Points: 12
Time limit: 13.0s
Memory limit: 512M
Problem types

Every morning, Lisa drives a public bus from one terminal stop to the other. Through months of careful observation, she has noticed that the order in which buses complete the route isn't necessarily the order in which they started. It is possible for the first bus to arrive at the first stop to not be the first bus to leave the last stop due to delays along the route. To leave work as early as possible, Lisa would like to figure out which bus will finish the route first on a given morning.

The route has N bus stops (labelled 1 to N) and M daily passengers. Each passenger gets on a bus at some stop and gets off at a later stop. Each morning, the buses (labelled 1, 2, 3, \dots) start at the first stop in 10-minute intervals, i.e., the k+1st bus starts 10 minutes after the kth bus.

A bus takes one minute to travel from one stop to the next. Each bus can carry 40 people. Passengers at a bus stop board the buses in the order that they arrive at the stop. A bus will only stop at a bus stop if it is not full and there is a passenger waiting at the stop, or if someone on the bus wants to get off at the stop. If a bus stops, it first lets off any passengers that want to get off the bus, then picks up as many passengers that it can. Stopping delays a bus by one minute, regardless of how many people it picks up or drops off. If multiple buses arrive at a stop at the same time, they would stop in increasing order of their indices (i.e., the bus with the lowest index stops first).

Can you help Lisa by figuring out which bus she should drive to complete the route first?

Input Specification

The input will contain 10 datasets. Each dataset begins with two integers N, M (1 \le N, M \le 500\,000). The next M lines each contain two integers S, F (1 \le S < F \le N), which represent a passenger who wants to travel between stop S and stop F. If multiple people start at the same stop, buses pick them up in the order that they are listed.

For the first 4 datasets, N, M \le 1\,000.

Output Specification

For each dataset, output Bus #X, where X is the index of the bus that will be the first to reach the last stop. If two buses tie for first, output the one with the lower index.

Sample Input (Two Datasets Shown)

5 3
1 2
2 3
4 5
13 6
1 7
2 8
3 9
4 10
5 11
6 12

Sample Output

Bus #1
Bus #2

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

Comments


  • 6
    Kirito  commented on April 3, 2019, 9:37 p.m.

    To discourage hardcoding, the testcases are now shuffled between runs.


    • -2
      Kevy3030  commented on April 27, 2020, 9:58 p.m.

      When your team got 4/10 by guessing during the actual ECOO


    • -2
      Joon7891  commented on June 23, 2019, 4:12 a.m. ← edit 3

      :)