Problems - 1999 National Championship - Back to the Farm PROBLEM 1: Bessie Come Home [Kolstad & Burch] The cows are out in their separate pastures. It's dinner time. Farmer John rings the bell and they all start walking to the barn. Your job is to figure out which one cow gets to the barn first. The supplied test data will always have exactly one fastest cow. Between milkings, each cow is located in her own pasture. Some pastures have no cows in them. Each pasture is connected by a path to one or more other pastures. One or more of the pastures has a path to the barn. Thus, all cows have a path to the barn and they always know the shortest path. Of course, cows can go either direction on a path and they all walk at the same speed. The pastures are labeled `a'..`z' and `A'..`Y'. One cow is in each pasture labeled with a capital letter. No cow is in a pasture labeled with a lower case letter. The barn's label is `Z'; no cows are in the barn, though. INPUT FORMAT: Line 1: integer P, 1 <= P <= 10000, the number of paths that interconnect the pastures (and the barn) Lines 2..P+1: two letters and an integer: the names of the interconnected pastures (barn) and the distance between them Column 1: the name of the first pasture (or the barn) Column 2: a space Column 3: the name of the second pasture (or the barn) Column 4: a space Column 5..: integer, 1 <= x <= 1000, the distance between the two named entities SAMPLE INPUT (file INPUT.TXT): 5 A d 6 B d 3 C e 9 d Z 8 e Z 3 OUTPUT FORMAT: The output is a single line of output that contains two items: the capital letter name of the pasture with the cow that arrives first back at the barn, followed by the length of the path traveled by that cow SAMPLE OUTPUT (file OUTPUT.TXT): B 11 [Problem|Data|Solutions] PROBLEM 2: Milk Measuring [Burch] Farmer John must measure Q quarts of his finest milk and deliver it in one big bottle to a customer. He fills that bottle with exactly the number of quarts that the customer orders. Farmer John has always been frugal. He is at the cow hardware store where he must purchase a set of pails with which to measure out Q quarts of milk from his giant milk tank. Since the pails each cost the same amount, your task is to figure out a minimal set of pails Farmer John can purchase in order to fill a bottle with exactly Q quarts of milk. To measure out milk, F.J. may completely fill a pail from the tank and pour it into the bottle. He can never remove milk from the bottle or pour milk anywhere except into the bottle. With a one-quart pail, FJ would need only one pail to create any number of quarts in a bottle. Other pail combinations are not so convenient. Determine the optimally small number of pails to purchase, given the guarantee that at least one solution is possible for all contest input data. INPUT FORMAT: Line 1: integer Q (1 <= Q <= 20000): number of quarts to be measured out Line 2: integer P (1 <= P <= 100): number of pails in the store Lines 3..P+2: integer pail_value (1 <= pail_value <= 10000), the number of quarts a pail holds SAMPLE INPUT (file INPUT.TXT): 11 3 3 5 7 OUTPUT FORMAT: The output is a single line that contains: the minimum number of pails required to measure out the desired number of quarts, followed by: a SORTED list (from smallest to largest) of the capacity of each of the required pails SAMPLE OUTPUT (file OUTPUT.TXT): 2 3 5 [Problem|Data|Solutions] PROBLEM 3: Healthy Holsteins [Burch & Kolstad] Farmer John prides himself on having the healthiest dairy cows in the world. He knows the vitamin content for one scoop of each feed type and the minimum daily vitamin requirement for the cows. Your goal is to help Farmer John feed his cows so they stay healthy while minimizing the number of scoops that a cow is fed. Given the daily requirements of each kind of vitamin that a cow needs, identify the smallest combination of scoops of feed a cow can be fed in order to meet at least the minimum vitamin requirements. Vitamins are measured in integer units. Cows can be fed at most one scoop of any feed type. It is guaranteed that a solution exists for all contest input data. INPUT FORMAT: Line 1: integer V (1 <= V <= 25), the number of types of vitamins Line 2: V integers (1 <= each one <= 1000), the minimum requirement for each of the V vitamins that a cow requires each day Line 3: integer G (1 <= G <= 15), the number of types of feeds available Lines 4..G+3: V integers (0 <= each one <= 1000), the amount of each vitamin that one scoop of this feed contains. The first line of these G lines describes feed #1; the second line describes feed #2; and so on. SAMPLE INPUT (file INPUT.TXT): 4 100 200 300 400 3 50 50 50 50 200 300 200 300 900 150 389 399 OUTPUT FORMAT: The output is a single line of output that contains: the minimum number of scoops a cow must eat, followed by: a SORTED list (from smallest to largest) of the feed types the cow is given SAMPLE OUTPUT (file OUTPUT.TXT): 2 1 3 [Other answers might be possible; any one correct answer is fine] [Problem|Data|Solutions] PROBLEM 4: Big Barn [USACO FALL '97] Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis. EXAMPLE Consider the following grid of Farmer John's land where `.' represents a parcel with no trees and `#' represents a parcel with trees: 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # . . . # . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 . . # . . . . . 7 . . . . . . . . 8 . . . . . . . . The largest barn is 5 x 5 and can be placed in either of two locations in the lower right part of the grid. INPUT FORMAT Line 1: two integers: N (1 <= N <= 200), the number of parcels on a side, and T (1 <= T <= 500) the number of parcels with trees Line 2..T+1: two integers (1 <= each integer <= N), the row and column of a tree parcel SAMPLE INPUT (file INPUT.TXT): 8 3 2 2 2 6 6 3 OUTPUT FORMAT The output file should consist of exactly one line, the maximum side length of John's barn. SAMPLE OUTPUT (file OUTPUT.TXT): 5 [Problem|Data|Solutions] PROBLEM 5: Cow Tours [Burch] Farmer John has a number of pastures on his farm. Cow paths connect a pasture with certain other pastures. But, at the present time, you can find at least two pastures that cannot be connected by a sequence of cow paths. Farmer John would like create cow paths between one extra pair of pastures so that more pastures are connected by a sequence of cow paths. In a set of connected pastures, the `diameter' is defined to be the largest distance of all the shortest walks between any pair of pastures. Consider the five pastures below with the cow paths marked by a line: 15,15 20,15 D E *-------* | _/| | _/ | | _/ | |/ | *--------*-------* A B C 10,10 15,10 20,10 The `diameter' of this set of farm pastures is approximately 12.07106, since the longest of the set of shortest paths between pairs of pastures is the path from A to E (which includes the point set {A,B,E}). No other pair of pastures is farther apart when connected by an optimal sequence of cow paths. Suppose another set of pastures on the same plane is connected by cow paths as follows: *F 30,15 / _/ _/ / *------ G H 25,10 30,10 In the scenario of just two pastures on his farm, Farmer John would add a cow path between a point in each of these two pastures (namely point sets {A,B,C,D,E} and {F,G,H}) so that the joined set of pastures {A,B,C,D,E,F,G,H} has the smallest possible diameter. Note that cow paths do not intersect or connect by crossing each other; they only connect at listed points. The input contains the pastures, their locations, and a symmetric "adjacency" matrix that tells whether pastures are connected by cow paths. Pastures are not considered to be connected to themselves. Here's one annotated adjacency list for the pasture {A,B,C,D,E,F,G,H} as shown above: A B C D E F G H A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 Other adjacency lists might permute the rows and columns by using some other order than alphabetical to show the point connections. The input data contains no names for the points. The input will contain a least two pastures that are not connected by any sequence of cow paths. Find a way to connect exactly two pastures in the input with a cow path so that the new combined pasture has the smallest possible diameter of any possible pair of connected pastures. Output that smallest possible diameter. INPUT FORMAT: Line 1: integer, N (1 <= N <= 150) the number of pastures Lines 2..N+1: two integers, X, Y, (0 <= X <= 100000, 0 <= Y <= 100000), that denote that X,Y grid location of the pastures; all input pastures are unique Lines N+2..2*N+1: N lines, each containing N space-separated integers (each integer 0 1) that represent the adjacency matrix as described above. SAMPLE INPUT (file INPUT.TXT): 8 10 10 15 10 20 10 15 15 20 15 30 15 25 10 30 10 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 OUTPUT FORMAT: The output consists of a single line with the diameter of the newly joined pastures. Print the answer to exactly six decimal places. Do not perform any special rounding on your output. SAMPLE OUTPUT (file OUTPUT.TXT): 22.071068 [The precise answer is closer to 22.071067811865475244 and might print as 22.071067 with your compiler/output libraries.] [Problem|Data|Solutions]