PROBLEM 1: Cow Relays [Brian Dean, 2001] Farmer John has formed a relay team for a race by choosing K (2 <= K <= 40) of his cows. The race is run on FJ's farm which has N (4 <= N < 800) fields numbered 1..N and M (1 <= M <= 4000) unique bidirectional pathways that connect pairs of different fields. You will be given the time it takes a cow to traverse each pathway. The first cow begins the race in field #1 and runs to the finish line in field #N. As soon as the first cow finishes, the next cow then starts from field #1 and runs to field #N and so on. For this race, no two cows can follow precisely the same route (a route is a sequence of fields). Write a program which computes the minimum possible time required for FJ's relay team. It is guaranteed that some minimum possible time exists. Any cows can revisit a path in her trip to the other barn if that turns out to be required for a "best" solution. As soon as a cow enters field #N, her relay leg is finished. PROBLEM NAME: relay INPUT FORMAT: * Line 1: One line with three integers: K, N, and M * Lines 2..M+1: Each line contains three integers describing a path: the starting field, the ending field, and the integer time to traverse the path (in the range 1..9500). SAMPLE INPUT (file relay.in): 4 5 8 1 2 1 1 3 2 1 4 2 2 3 2 2 5 3 3 4 3 3 5 4 4 5 6 OUTPUT FORMAT: One line with a single integer that is the minimum possible time to run a relay. SAMPLE OUTPUT (file relay.out): 23 [Namely: Cow 1: 1->2->5 4 Cow 2: 1->3->5 6 Cow 3: 1->2->1->2->5 6 Cow 4: 1->2->3->5 7] ---------------------------------------------------------------------- PROBLEM 2: Earthquake [Chandrasekaran, 1977; Tvarozek, 2001] An earthquake has destroyed Farmer John's entire farm. Being a resolute fellow, he decides to rebuild it. After rebuilding all N fields (1 <= N <= 400), he realizes he must also connect the fields with roads. When complete, there must be some way to traverse from any field to any other field. After studying the terrain, FJ has concluded that M (1 <= M <= 10,000) two-way roads can possibly be built. Since he is low on money, he would like to complete the project in the cheapest way possible. As luck would have it, the cows have formed an engineering consulting firm that specializes in rebuilding farm roads destroyed in earthquakes. The cows also have a keen business sense and have no interest in taking on jobs for which they do not make a handsome profit. The cows are concerned about the profit potential. They have negotiated a fee F (1 <= F <= 2,000,000,000) which they are paid to rebuild the roads. They are given a table of possible roads, the time (in hours) to build each road (1 <= t <= 2,000,000,000), and the cost to build the road (1 <= c <= 2,000,000,000). The table might contain more than one road connecting the same pair of fields. It will always be possible to connect all the fields given the input data though it might not be profitable. Determine the highest profit rate the cows can make in rebuilding the farm's roads. PROBLEM NAME: quake INPUT FORMAT: * Line 1: Three integers, N, M, and F * Lines 2...M+1: Each line contains four space-separated integers: i, j, c, and t respectively denoting two fields the road connects, the cost, and the time requirements to build the road. SAMPLE INPUT (file quake.in): 5 5 100 1 2 20 5 1 3 20 5 1 4 20 5 1 5 20 5 2 3 23 1 OUTPUT FORMAT: A single line containing one number -- printed to four decimal places -- which is the maximum profit per hour the cows can achieve. If the profit is not positive, print 0.0000 . SAMPLE OUTPUT (file quake.out): 1.0625 [The cows choose to construct the last four roads, with a total cost of 83 and a time of 16. Their fee is 100, so they make a profit of 100-83 over a period of 16 time units: 17/16 = 1.0625.] ---------------------------------------------------------------------- PROBLEM 3: Cow Sorting [Kolstad & Burch, 2001] Farmer John has C (2 <= C <= 400) cows and the same number of stalls. These cows are notoriously fickle about their stall arrangement. While they enter the stalls in an order that appears to be random, they must be rearranged to be in a "proper" order or their milk output will decrease. To find the "proper" order, each cow examines its brand (which is a positive integer smaller than 2,000,000) to ensure that the cow to her right has a brand at least as large and the cow to her left has a brand at least as small. Interestingly, the cow with the smallest brand knows that she might also have on her left the cow with the largest brand (and, likewise, the cow with the largest brand knows she might have on her right the cow with the smallest brand). If these ordering rules are met, the cows are in "proper" order. Note that these ordering rules are intended to describe a cycle of a sorted list and not something exotic. By way of example, if the cow's brands were 2, 2, 4, 5, 7, the set of proper orderings for the cows in the stalls is: 2 2 4 5 7 7 2 2 4 5 5 7 2 2 4 4 5 7 2 2 2 4 5 7 2 If you have any experience with cows, you know that moving them is difficult. In order to rearrange the cows, Farmer John can lead cows out of stalls, traverse the stalls, and lead the cows into other stalls. Having only two hands, FJ can lead at most two cows at a time (before having to deposit at least one cow back into some stall). Farmer John exerts 10 joules of energy to remove a cow from a stall and 10 joules to put a cow into a stall. He exerts 1 joule for each cow he is leading for every stall-length he walks while leading those cows. If he's not leading a cow, he exerts no energy walking by himself between stalls. Thus, if he goes from the 3rd stall to the 7th stall leading 2 cows, he will expend (7-3)*2 = 8 joules of energy doing so. Walking back to stall 1 while leading no cows requires 0 joules. Determine the minimum amount of energy Farmer John must exert to put the cows into a "proper" order. PROBLEM NAME: sort INPUT FORMAT: * Line 1: One integer: C * Lines 2..C+1: Each line contains a cow brand. The input lines are ordered such that the first brand given is in stall 1, the second in stall 2, and so on. SAMPLE INPUT (file sort.in): 5 5 2 7 4 2 OUTPUT FORMAT: A single line with the integer that represents the minimum amount of energy Farmer John must exert. SAMPLE OUTPUT (file sort.out): 66 [Arrived at like this: Action Cost Stalls FJ Cow out of stall 1 10 * 2 7 4 2 5 Walk to stall 2 1 * 2 7 4 2 5 Cow out of stall 2 10 * * 7 4 2 5 2 Cow #5 into stall 2 10 * 5 7 4 2 2 Walk to stall 4 2 * 5 7 4 2 2 Cow out of stall 4 10 * 5 7 * 2 2 4 Cow #2 into stall 4 10 * 5 7 2 2 4 Walk to stall 1 3 * 5 7 2 2 4 Cow #4 into stall 1 10 4 5 7 2 2 - Final configuration: 4 5 7 2 2; final cost: 66] ---------------------------------------------------------------------- PROBLEM 4: Cow Signs [Galperin, 2001] Farmer John decided to make the most out of his highwayside farm and sell advertising. He found a client and hiked to his fence which runs along the highway and painted the message on the sides of the cows grazing along the fence. He painted exactly K letters (2 <= K <= 4) on each of C (2 <= C <= 20) cows and ignored spaces. Although cows are fairly lazy creatures, they are not immobile. After milking the next morning, FJ noticed that the message he was being paid to display was now in pieces in his barn. Worse still, FJ also forgot the original message. Help FJ reconstruct the original message. Given K, the cows' letter groupings (which all happen to be unique), and a dictionary that contains all the possible words, figure out all the possible messages (note that the message ABCD EF is different from AB CDEF). Each dictionary word is unique and can be used more than once in any given message. All C cows are used exactly once. Being advertising, it is important to ignore grammar and any possible meaning of the message. It is guaranteed that the number of possible original messages will not exceed 2,000,000,000. Furthermore, all data in this problem is supplied in upper-case. PROBLEM NAME: sign INPUT FORMAT: * Line 1: Three integers, K, C, and D (1 <= D <= 150, the number of words in the dictionary) * Lines 2..C+1: Each line contains K letters of the scrambled message * Lines C+2..C+D+1: Each line contains a single word from a dictionary; no word is longer than ten characters SAMPLE INPUT (file sign.in): 3 5 7 TEN ATT NAT BAR ACK AT ATTACK BARN CHICKENS CHOPPERS COWS TEN OUTPUT FORMAT: * Line 1: The first (in alphabetical order) possible message. Note that "A B" preces "AB" alphabetically. * Line 2: A single integer which is the number of possible messages If no solutions exist, print a single line containing the word "NOSOLUTIONS". SAMPLE OUTPUT (file sign.out): ATTACK BARN AT TEN 6 [in case you were wondering, here are the six: TEN ATTACK BARN AT, TEN BARN AT ATTACK, ATTACK TEN BARN AT, ATTACK BARN AT TEN, BARN AT TEN ATTACK, and BARN AT ATTACK TEN] ----------------------------------------------------------------------