Bus StopsIf you take the TTC, you'll know that often buses can only carry a certain number of people (call this C).
Sometimes, you get left stranded at the bus stop when the bus is full.
If you're lazy, you'll just wait for the next bus. But sometimes, it might just be better to walk to another stop beforehand.
In our scenario, there is only one bus, and so some people might be required to walk.
Let's suppose you know in advance all N of the passengers and where they want to get on and off.
Now, you want to create a plan so that each passenger spends the least amount of time in transit to reach his/her destination.
All passengers are treated equally - we just want to minimize the total time for all passengers.
The bus starts at bus stop #1 and goes "rightward", going to bus stop 2, then 3, etc.
The bus stops, numbered 1,2,3 ... B, are located along a perfectly straight street.
It takes 5 minutes to walk from one bus stop to the next, and 1 minute to do the same by bus.
InputThree integers, passengers (N) ≤ 1,000,000, stops (B) ≤ 1,000,000, capacity (C) ≤ N
N pairs of integers, representing the start and end stops of a passenger.
Passengers get to their starting stops instantly.
Assume that they get to their required bus stop right on time: they won't have to wait for the bus.
All numbers will be positive integers.
OutputThe total time taken for all the passengers to get to work, assuming an optimal schedule.
3 5 2 1 5 2 5 3 4
The bus only holds 2 people, so the third guy has to walk. (No passenger is favored over another)
Passenger 1: takes the bus (4 minutes)
Passenger 2: takes the bus (3 minutes)
Passenger 3: walks from 3-4 (5 minutes)
5 8 1 1 3 2 4 2 5 6 7 7 8
In this case, the bus is more like a taxi.
Passenger 1: Just takes the bus (2 minutes)
Passenger 2: walks to stop 3 first (5 minutes) and then takes the bus to 4 (1 minute)
Passenger 3: walks to stop 4 first (10 minutes) and then takes the bus to 5 (1 minute)
Passengers 4/5: just take the bus (1+1 minutes)
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 02, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Our current policy is basically to ignore the fact that Java exists at all, mostly because it's a lot harder to grade Java programs accurately than it is to grade C/C++/Pascal ones. This may change if they ever start allowing Java at the IOI, but according to kolstad it's not likely to happen soon, as it gets proposed (and subsequently rejected) every year.
(NB: kolstad also implied that the only reason why Java is allowed in USACO is that it's unreasonably popular among Americans. He's probably also one of very few people in the world with enough technical expertise to grade it properly.)
Or was it just too hard? (It's not too bad, the solution is very simple)