USACO 2013 March Contest, Bronze
Problem 1. Cow Race
Contest has ended.
Log in to allow submissions in analysis mode
Problem 1: Cow Race [Brian Dean, 2013]
In order to finally settle their long-running dispute over who is the
faster cow, Bessie and her friend Elsie decide to hold a race across the farm.
The two cows start at the same location and begin running in the same
direction at the same time. The progress of each cow is described by a
series of "segments", during each of which the cow runs at a constant
speed. For example, Bessie might run at a speed of 5 for 3 units of time,
then at a speed of 10 for 6 units of time. Bessie and Elsie both run for
the same total amount of time.
The cows would like your help in counting the number of leadership changes
during their race. A leadership change happens at a point in time when cow
A pulls into the lead of cow B, whereas the last time one cow was in the
lead, it was cow B. For example, if B is in the lead and then A pulls
ahead, then this is a leadership change. If B is in the lead, and then A
becomes even with B for some time and then finally pulls ahead, then this
also counts as a leadership change.
PROBLEM NAME: cowrace
INPUT FORMAT:
* Line 1: Two space-separated integers, N and M. (1 <= N, M <= 1000)
* Lines 2..1+N: Each line contains one of the N segments of Bessie's
run, described by two integers: Bessie's speed and the amount
of time she runs at that speed (both integers are in the range
1..1000).
* Lines 2+N..1+N+M: Each line contains one of the M segments of
Elsie's run, described by two integers: Elsie's speed and the
amount of time she runs at that speed (both integers are in
the range 1..1000).
SAMPLE INPUT (file cowrace.in):
4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9
INPUT DETAILS:
Bessie runs at a speed of 1 for 2 units of time, then at a speed of 4 for 1
unit of time, then at a speed of 1 for 1 unit of time, and finally at a
speed of 2 for 10 units of time. Elsie runs at a speed of 2 for 3 units of
time, then at a speed of 1 for 2 units of time, then finally at a speed of
3 for 9 units of time. Note that both cows run for a total of 14 units of
time.
OUTPUT FORMAT:
* Line 1: The number of leadership changes during the race.
SAMPLE OUTPUT (file cowrace.out):
2
OUTPUT DETAILS:
Elsie is ahead until time t=3, when both cows meet after both have traveled
6 units of total distance and travel together for 1 unit of time. Bessie
then pulls ahead briefly (the first leadership change), only to be
overtaken shortly thereafter by Elsie (the second leadership change).
Elsie ends the race in the lead.
Contest has ended. No further submissions allowed.