1995 USACO Final Round
Day 1, June 1, 1995
Problem 1: Cows on Parade
Farmer John was marching 19 of his finest black Angus and white Jersey
cows to market the other day when his wife, Farmeress Joanne, noticed
that all 16 possible combinations of four successive black and white
cows (e.g., bbbb, bbbw, bbwb, bbww, ..., wwww) were present (as
contiguous cow-subsequences) as the parade passed by. Of course, some
of the combinations overlapped others.
Part 1: Print any ordering of 19 marching black and white cows that
contains all the possible four-color combinations.
Part 2: Accept as console input the number of cows and the length of
the subsequence and print any ordering of the cows that contains all
the possible color combinations. Typical lengths and subsequences
are: 2,5; 3,10; 4,19; 5,36 and more. The number of cows will not
exceed 32,782 and the length of the subsequence will not exceed 15. It
is guaranteed that a solution will exist. Your program must run in
less than 30 seconds.
[Charley Ashbacher; JRM 25:4 p299 '93]
Problem 2: Udder Travel
The Udder Travel cow transport company is based at farm A and owns one cow
truck which it uses to pick-up and deliver cows between seven farms A, B, C,
D, E, F, and G. The (commutative) distances between farms are given by the
following array:
B C D E F G
A 56 43 71 35 41 36
B . 54 58 36 79 31
C . . 30 20 31 58
D . . . 38 59 75
E . . . . 44 67
F . . . . . 72
Every morning, Udder Travel has to decide the order in which to pick up and
deliver cows to minimize the total distance traveled. Here are the rules:
1. The truck always starts from the headquarters at farm A and must return
there when the day's deliveries are done.
2. The truck can only carry one cow at time.
3. The orders are given as pairs of letters denoting where a cow is to be
picked up followed by where the cow is to be delivered.
Your job is to write a program that, given any set of orders, determines the
shortest route that takes care of all the deliveries, while starting and
ending at farm A.
Input data: The orders are stored in the DELVR.TXT file. The file starts
with the number of orders n (1<=n<=12). Next, each order is given
by a pair of letters separated by a space. The first letter is the
pick-up farm and the second is the delivery farm. Your program must
complete in less than 60 seconds.
Sample input data:
5
F C
G B
B D
A E
G A
Output: Write to the screen the minimum route distance followed by Udder
Travel, showing the farms in order in which the truck visits them.
Sample output:
368
A E F C G B D G A
[Don Piele, 1995]
Problem 3: Attack of the Killer Cows
Eight of Farmer John's cows have taken up paintball on his north 40. You
may recall that the north 40 is divided into 64 cow-size squares -- an 8 x
8 grid. Each of the eight cows occupies a single square and can attack any
cows (or other beasts!) from some other team that might appear on a square.
Curiously enough, the nonaggressive Holsteins play paintball in a cowardly
way. Their new F18 Hornet paintball games spray paint in eight directions
-- vertically and horizontally along the squares aligned with the occupied
square and along the obvious 45 degree diagonals.
Arrange eight Holsteins so that, in aggregate, they attack a minimum number
of squares. Omit squares upon which each cow sits from the count of attacked
squares.
[W.W.R. Ball; Mathematical Recreations & Essays, p119, 1905]
1995 USACO Final Round
Day 2 , June 4, 1995
Problem 1: Perfect Cows & Perfect Cow Cousins
Like most cow farmers, Farmer John keeps meticulous records of the fine
breeding of his cows, each of which has a serial number. For the Cownty
Fair, FJ wishes to find the best bred cows: The Perfect Cows.
The serial numbers of the perfect cows are distinguished by the fact that
the sum of the proper divisors of the serial number is the serial number
itself (e.g., 28=1+2+4+7+14). A number's proper divisors are those integers
less than a number which divide it evenly.
Perfect Cow Cousins are also interesting because the proper divisors of the
serial number of one cow sum to the serial number of the other cow, while
the proper divisors of the serial number of the other cow sum to the original
cow's serial number (e.g., the cows numbered 220 and 284).
The rare group of five Cow Cousins forms a chain of serial numbers in which
the first cow's serial number's divisors sum to the second cow's serial
number; the second cow's serial number's divisors sum to the third cow's
serial number, etc.; the fifth cow's serial number's divisors sum to the
first cow's serial number.
Print the serial numbers of the Perfect Cows and Perfect Cow Cousins, including
the chain(s) of five Cow Cousins serial numbers. Of course, you shouldn't print any duplicate serial numbers.
Sample Output:
6
28
220 284
[fewer than 20 lines follow]
[Traditional; adapted by Kolstad/Burch, 1995]
Problem 2: Cowcycles
Having made a fortune on Playbov, Hugh Heiffer has moved from his original
field in the country to a fashionable yard in the suburbs. To visit
fond pastoral memories, he wishes to cowmmute back to his old stomping grounds.
Being environmentally minded, Hugh wishes to transport himself using his own
power on a Cowcycle (specially fitted for his neatly manicured hooves).
Hugh weighs over a ton; as such, getting smoothly up to speed on traditional
cowcycle
gearsets is a bit challenging. Changing among some of the widely spaced gear
ratios causes exertion that's hard on Hugh's heart.
Help Hugh outfit his Cowcycle with two larger gears in the front and five
smaller gears in the rear subject to the following:
1. Each of the two front gears cowntains from 39 through 62 teeth (inclusive)
2. Each of the five rear gears cowntains from 12 through 28 teeth (inclusive)
3. At any given setting, the \fIgear ratio is the quotient of the
number of teeth on the front gear and the number of teeth on the
rear gear.
4. The range of the gear ratios must span at least a factor of 3\(mu.
5. The variance of the differences between successive gear ratios
should be minimized.
Calculate the variance of a set of numbers by the following formulae:
_ 1 n
mean = x = --- SUM x
n i=1 i
1 n _ 2
variance = --- SUM (x - x)
n i=1 i
Print and label the number of teeth of the optimal front and rear gear sets.
[Don Gillies; Adapted by Galperin, Burch, Kolstad, 1995]
Problem 3: Cow Scans
Farmer John has just invested in a shiny new Locowter-2000 for tracking his
grazing cows. The Locowter-2000's best feature is that it does not need to
get input from anywhere except the perimeter of the verdant pastures in which
the cows are grazing.
Farmer John has conveniently partitioned his field into a grid of 10 rows
and 15 columns of cow-sized grazing-cells, each of which can host either 0
or 1 dining bovines.
The Locowter-2000 sports a battery of scanners located on fence posts around
the pasture. Each of the 73 scanners counts the number of cows in its direct
line of sight. Farmer John has arranged the scanners to observe the number
of cows in each row, in each column, and in each diagonal (both directions!).
The numbers are fed back to the L2000's cowputer, which cowculates
the locowtions of Farmer John's feeding friends and displays a graphical map
of those locowtions using ASCII graphics.
Regrettably, the L2000's cowputer has been decowmissioned for maintenance
and Farmer John needs you to cowculate his cow locowtions.
The scanners' output is given as a set of integers representing the numbers
of cows observed on the various rows, columns, and diagonals. The first
10 numbers represent the rows; note the order of letters in the diagram
below:
a->.##########....
b->.##########....
c->....######.....
d->......####.....
e->.......####..##
f->.......########
g->#####..########
h->###############
i->..#########..##
j->....######.....
The second 24 numbers are diagonals; see the letters below for the ordering:
.##########....
/.##########....
a/....######.....
b/......####.....
c/.......####..##
d/.......########
e/#####..########
f/###############
g/..#########..##
h/....######.....
i///////////////
jklmnopqrstuvwx
The third 15 numbers are the columns; see the letters below for the ordering:
.##########....
.##########....
....######.....
......####.....
.......####..##
.......########
#####..########
###############
..#########..##
....######.....
|||||||||||||||
abcdefghijklmno
The final 24 numbers are the other diagonals; see the letters below for the
ordering:
.##########....
.##########....\
....######.....\x
......####.....\w
.......####..##\v
.......########\u
#####..########\t
###############\s
..#########..##\r
....######.....\q
\\\\\\\\\\\\\\\p
abcdefghijklmno
The sample input datafile for this particular example looks just
like this:
10 10 6 4 6 8 13 15 11 6
0 1 2 2 2 2 4 5 5 6 7 6 5 6 6 5 5 6 6 3 2 2 1 0
2 4 5 5 7 6 7 10 10 10 7 3 3 5 5
0 0 1 3 4 4 4 4 3 4 5 7 8 8 9 9 6 4 4 2 0 0 0 0
Your program should prompt for a file name, then use the data in that file to
reconstruct a diagram of the cow's grazing locations. Note that there do
exist datasets in the universe that can not be precisely decoded given this
kind of input data. Farmer John's Courteous Cows never arrange themselves
in any of these positions. You will be able to determine the value of every
grazing-cell without resorting to any guesswork.
[ACM Programming Contest, 1992; adapted by Galperin, Burch, Kolstad, Simeonov]