USACO 2013 February Contest, Gold
Problem 2. Taxi
Contest has ended.
Log in to allow submissions in analysis mode
Problem 2: Taxi [Mark Gordon, Richard Peng, 2013]
Bessie is running a taxi service for the other cows on the farm. The
cows have been gathering at different locations along a fence of
length M (1 <= M <= 1,000,000,000). Unfortunately, they have grown
bored with their current locations and each wish to go somewhere else
along the fence. Bessie must pick up each of her friends at their
starting positions and drive them to their destinations. Bessie's car
is small so she can only transport one cow in her car at a time. Cows
can enter and exit the car instantaneously.
To save gas, Bessie would like to minimize the amount she has to
drive. Given the starting and ending positions of each of the N cows
(1 <= N <= 100,000), determine the least amount of driving Bessie
has to do. Bessie realizes that to save the most gas she may need to
occasionally drop a cow off at a position other than her destination.
Bessie starts at the leftmost point of the fence, position 0, and must
finish her journey at the rightmost point on the fence, position M.
PROBLEM NAME: taxi
INPUT FORMAT:
* Line 1: N and M separated by a space.
* Lines 2..1+N: The (i+1)th line contains two space separated
integers, s_i and t_i (0 <= s_i, t_i <= M), indicating the
starting position and destination position of the ith cow.
SAMPLE INPUT (file taxi.in):
2 10
0 9
6 5
INPUT DETAILS:
There are two cows waiting to be transported along a fence of length 10.
The first cow wants to go from position 0 (where Bessie starts) to position
9. The second cow wishes to go from position 6 to position 5.
OUTPUT FORMAT:
* Line 1: A single integer indicating the total amount of driving
Bessie must do. Note that the result may not fit into a 32 bit
integer.
SAMPLE OUTPUT (file taxi.out):
12
OUTPUT DETAILS:
Bessie picks up the first cow at position 0 and drives to position 6.
There she drops off the first cow, delivers the second cow to her
destination and returns to pick up the first cow. She drops off the first
cow and then drives the remainder of the way to the right side of the fence.
Contest has ended. No further submissions allowed.