USACO 2013 March Contest, Gold
Problem 1. The Cow Run
Contest has ended.
Log in to allow submissions in analysis mode
Problem 1: The Cow Run [Chris Tzamos, 2006]
Farmer John has forgotten to repair a hole in the fence on his farm, and
his N cows (1 <= N <= 1,000) have escaped and gone on a rampage! Each
minute a cow is outside the fence, she causes one dollar worth of damage.
FJ must visit each cow to install a halter that will calm the cow and stop
the damage.
Fortunately, the cows are positioned at distinct locations along a straight
line on a road outside the farm. FJ knows the location P_i of each cow i
(-500,000 <= P_i <= 500,000, P_i != 0) relative to the gate (position 0)
where FJ starts.
FJ moves at one unit of distance per minute and can install a halter
instantly. Please determine the order that FJ should visit the cows so he
can minimize the total cost of the damage; you should compute the minimum
total damage cost in this case.
PROBLEM NAME: cowrun
INPUT FORMAT:
* Line 1: The number of cows, N.
* Lines 2..N+1: Line i+1 contains the integer P_i.
SAMPLE INPUT (file cowrun.in):
4
-2
-12
3
7
INPUT DETAILS:
Four cows placed in positions: -2, -12, 3, and 7.
OUTPUT FORMAT:
* Line 1: The minimum total cost of the damage.
SAMPLE OUTPUT (file cowrun.out):
50
OUTPUT DETAILS:
The optimal visit order is -2, 3, 7, -12. FJ arrives at position -2 in 2
minutes for a total of 2 dollars in damage for that cow.
He then travels to position 3 (distance: 5) where the cumulative damage is
2 + 5 = 7 dollars for that cow.
He spends 4 more minutes to get to 7 at a cost of 7 + 4 = 11 dollars for
that cow.
Finally, he spends 19 minutes to go to -12 with a cost of 11 + 19 = 30 dollars.
The total damage is 2 + 7 + 11 + 30 = 50 dollars.
Contest has ended. No further submissions allowed.