Morning Problem: Ferrying Vehicles

CMPUT 275 - Tangible Computing
Morning Problem: Ferrying Vehicles
Description
There is a cute little single-vehicle ferry that transports vehicles across a river. It begins
each day on the West bank of the river. Vehicles arrive at various times throughout the day
on either side of the river. But it can only hold one vehicle at a time.
The ferry operates as follows. If there are no vehicles waiting, it idles on the side it is
currently resting on.
At any time it is not currently transporting a vehicle, if some vehicle is waiting to be
transported then it serves the vehicle that has been waiting the longest. It does this by first
traveling to the side of the river the vehicle is waiting on (if the ferry is not there already),
loading the vehicle, transporting it to the other side, and then unloading it.
The ferry operator is very single-minded. If he unloads a vehicle and if there are vehicles waiting on both sides of the river but the next vehicle to be served (i.e. the one that
has waited the longest) is on the other side, he will travel to the other side without bringing
over a vehicle from the current side. See examples 2 and 3 for clarification.
Loading and unloading takes 0 time. The ferry takes 100 units of time to cross the river.
Again, recall the ferry starts on the West bank. What time is the last vehicle dropped off?
Input
The input consists of three lines. The first line consists of two integers 1 ≤ n, m ≤ 100, 000,
where n and m represent the number of arrivals on the West and East banks (respectively).
This is followed by two lines of space-separated integers: w1, w2, · · · , wn indicating the times
the vehicles arrive on the West bank, and then e1, e2, · · · , em indicating the times the vehicles
arrive at the East bank. Both lists will already be in sorted order.
Each time will be a positive integer at most 1, 000, 000, 000. No two vehicles arrive at
the bank at the same time.
Output
The output should be a single integer indicating the time the ferry drops the last vehicle off.
Sample Input 1
3 1
10 220 330
75
Sample Output 1
530
Explanation: At time 10, the ferry starts moving the first vehicle on the West bank and
drops it off on the East bank at time 110. Immediately it picks up the vehicle that has been
waiting from time 75 and drops it off on the West bank at time 210.
The ferry idles on the West bank until the next vehicle arrives at time 220. It transports
this vehicle and drops it off at time 320. As no vehicles are currently at either bank, the
ferry idles until the last vehicle arrives at 330. Once the ferry sees this vehicle at time 330,
it first travels to the West bank to pick it up at time 430 and then drops it off on the East
bank at time 530.
Sample Input 2
2 1
10 20
50
Sample Output 2
410
Explanation: The ferry picks up the first vehicle on the West bank at time 10 and drops
it off on the East bank at time 110. While both sides of the river now have waiting vehicles,
the one that arrived earliest is on the West bank.
So the ferry travels from the East bank to the West bank without transporting the vehicle that has not been waiting as long (the one that arrived at time 50). The ferry arrives
at the West bank at time 210, picks up the vehicle, and delivers it at time 310. Finally it
picks up the only vehicle on the East bank at time 310 and delivers it at time 410.
Sample Input 3
5 1
1 2 3 4 5
6
Sample Output 3
1001
Explanation: The vehicles on the West bank are all served before the only vehicle on
the East bank because they arrived first. They are dropped off on the East bank at times
101, 301, 501, 701, 901, respectively. Finally, at time 901 the ferry finally picks up the only
vehicle on the right bank and delivers it at time 1001.