1) Firetruck The Center City fire department collaborates with the transportation department to maintain maps of the city which reflects the current status of the city streets. On any given day, several streets are closed for repairs or construction. Firefighters need to be able to select routes from the firestations to fires that do not use closed streets. Central City is divided into non-overlapping fire districts, each containing a single firestation. When a fire is reported, a central dispatcher alerts the firestation of the district where the fire is located and gives a list of possible routes from the firestation to the fire. You must write a program that the central dispatcher can use to generate routes from the district firestations to the fires. Input and Output The city has a separate map for each fire district. Streetcorners of each map are identified by positive integers less than 21, with the firestation always on corner #1. The input file contains several test cases representing different fires in different districts. The first line of a test case consists of a single integer which is the number of the streetcorner closest to the fire. The next several lines consist of pairs of positive integers separated by blanks which are the adjacent streetcorners of open streets. (For example, if the pair 4 7 is on a line in the file, then the street between streetcorners 4 and 7 is open. There are no other streetcorners between 4 and 7 on that section of the street.) The final line of each test case consists of a pair of 0's. For each test case, your output must identify the case by number (case #1, case #2, etc). It must list each route on a separate line, with the streetcorners written in the order in which they appear on the route. And it must give the total number routes from firestation to the fire. Include only routes which do not pass through any streetcorner more than once. (For obvious reasons, the fire department doesn't want its trucks driving around in circles.) Output from separate cases must appear on separate lines. The following sample input and corresponding correct output represents two test cases. Sample Input Sample Output 6 CASE 1: 1 2 1 2 3 4 6 1 3 1 2 3 5 6 3 4 1 2 4 3 5 6 3 5 1 2 4 6 4 6 1 3 2 4 6 5 6 1 3 4 6 2 3 1 3 5 6 2 4 There are 7 routes from the firestation to streetcorner 6. 0 0 CASE 2: 4 1 3 2 5 7 8 9 6 4 2 3 1 3 4 3 4 1 5 2 3 4 5 1 1 5 7 8 9 6 4 1 6 1 6 4 7 8 1 6 9 8 7 5 2 3 4 8 9 1 8 7 5 2 3 4 2 5 1 8 9 6 4 5 7 There are 8 routes from the firestation to streetcorner 4. 3 1 1 8 4 6 6 9 0 0 2) Getting in Line Computer networking requires that the computers in the network be linked. This problem considers a ÒlinearÓ network in which the computers are chained together so that each is connected to exactly two others except for the two computers on the ends of the chain which are connected to only one other computer. A picture is shown below. Here the computers are the black dots and their locations in the network are identified by planar coordinates (relative to a coordinate system not shown in the picture). Distances between linked computers in the network are shown in feet. For various reasons it is desirable to minimize the length of cable used. Your problem is to determine how the computers should be connected into such a chain to minimize the total amount of cable needed. In the installation being constructed, the cabling will run beneath the floor, so the amount of cable used to join 2 adjacent computers on the network will be equal to the distance between the computers plus 16 additional feet of cable to connect from the floor to the computers and provide some slack for ease of installation. The picture below shows the optimal way of connecting the computers shown above, and the total length of cable required for this configuration is (4+16)+ (5+16) + (5.83+16) + (11.18+16) = 90.01 feet. Input The input file will consist of a series of data sets. Each data set will begin with a line consisting of a single number indicating the number of computers in a network. Each network has at least 2 and at most 8 computers. A value of 0 for the number of computers indicates the end of input. After the initial line in a data set specifying the number of computers in a network, each additional line in the data set will give the coordinates of a computer in the network. These coordinates will be integers in the range 0 to 150. No two computers are at identical locations and each computer will be listed once. Output The output for each network should include a line which tells the number of the network (as determined by its position in the input data), and one line for each length of cable to be cut to connect each adjacent pair of computers in the network. The final line should be a sentence indicating the total amount of cable used. In listing the lengths of cable to be cut, traverse the network from one end to the other. (It makes no difference at which end you start.) Use a format similar to the one shown in the sample output, with a line of asterisks separating output for different networks and with distances in feet printed to 2 decimal places. 3) Department of Redundancy Department When designing tables for a relational database, a functional dependency (FD) is used to express the relationship between the different fields. A functional dependency is concerned with the relationship of values of one set of fields to those of another set of fields. The notation X->Y is used to denote that when supplied values to the field(s) in set X, the assigned value for each field in set Y can be determined. For example, if a database table is to contain fields for the social security number (S), name (N), address (A), and phone (P) and each person has been assigned a unique value for S, the S field functionally determines the N, A and P fields. This is written as S->NAP. Develop a program that will identify each redundant FD in each input group of FDs. An FD is redundant if it can be derived using other FDs in the group. For example, if the group contains the FDs A->B, B->C, and A->C, then the third FD is redundant since the field set C can be derived using the first two. (The A fields determine values for the B fields, which in turn determine values for the fields in C.) In the group A->B, B->C, C->A, A->C, C->B, and B->A, all the FDs are redundant. Input The input file contains an arbitrary number of groups of FDs. Each group is preceded by a line containing an integer no larger than 100 specifying the number of FDs in that group. A group with zero FDs indicates the end of the input. Each FD in the group appears on a separate line containing two non- empty lists of field names separated by the characters - and >. The lists of field names contain only uppercase alphabetic characters. Functional dependency lines contain no blanks or tabs. There are no trivially redundant FDs (for example, A->A). For identification purposes, groups are numbered sequentially, starting with 1; the FDs are also numbered sequentially, starting with 1 in each group. Output For each group, in order, your program must identify the group, each redundant FD in the group, and a sequence of the other FDs in the group which were used to determine the indicated FD is redundant. If more than one sequence of FDs can be used to show another FD is redundant, any such sequence is acceptable, even if it is not the shortest proof sequence. Each FD in an acceptable proof sequence must, however, be necessary. If a group of FDs contains no redundancy, display No redundant FDs. 4) Budget Travel An American travel agency is sometimes asked to estimate the minimum cost of traveling from one city to another by automobile. The travel agency maintains lists of many of the gasoline stations along the popular routes. The list contains the location and the current price per gallon of gasoline for each station on the list. In order to simplify the process of estimating this cost, the agency uses the following rules of thumb about the behavior of automobile drivers. - A driver never stops at a gasoline station when the gasoline tank contains more than half of its capacity unless the car cannot get to the following station (if there is one) or the destination with the amount of gasoline in the tank. - A driver always fills the gasoline tank completely at every gasoline station stop. - When stopped at a gasoline station, a driver will spend $2.00 on snacks and goodies for the trip. - A driver needs no more gasoline than necessary to reach a gasoline station or the city limits of the destination. There is no need for a Òsafety margin.Ó - A driver always begins with a full tank of gasoline. - The amount paid at each stop is rounded to the nearest cent (where 100 cents make a dollar). You must write a program that estimates the minimum amount of money that a driver will pay for gasoline and snacks to make the trip. Input Program input will consist of several data sets corresponding to different trips. Each data set consists of several lines of information. The first 2 lines give information about the origin and destination. The remaining lines of the data set represent the gasoline stations along the route, with one line per gasoline station. The following shows the exact format and meaning of the input data for a single data set. Line 1: One real number Ñ the distance from the origin to the destination Line 2: Three real numbers followed by an integer ¼ The first real number is the gallon capacity of the automobile's fuel tank. ¼ The second is the miles per gallon that the automobile can travel. ¼ The third is the cost in dollars of filling the automobile's tank in the origination city. ¼ The integer (less than 51) is the number of gasoline stations along the route. Each remaining line: Two real numbers ¼ The first is the distance in miles from the origination city to the gasoline station. ¼ The second is the price (in cents) per gallon of gasoline sold at that station. All data for a single data set are positive. Gasoline stations along a route are arranged in nondescending order of distance from the origin. No gasoline station along the route is further from the origin than the distance from the origin to the destination There are always enough stations appropriately placed along the each route for any car to be able to get from the origin to the destination. The end of data is indicated by a line containing a single negative number. Output For each input data set, your program must print the data set number and a message indicating the minimum total cost of the gasoline and snacks rounded to the nearest cent. That total cost must include the initial cost of filling the tank at the origin. Sample input data for 2 separate data sets and the corresponding correct output follows. Sample Input Output for the Sample Input 475.6 Data Set #1 11.9 27.4 14.98 6 minimum cost = $27.31 102.0 99.9 Data Set #2 220.0 132.9 minimum cost = $38.09 256.3 147.9 275.0 102.9 277.6 112.9 381.8 100.9 516.3 15.7 22.1 20.87 3 125.4 125.9 297.9 112.9 345.2 99.9 -1 5) Kissin' Cousins The Oxford English Dictionary defines cousin as follows: cous'in (kO(u,ù)zn), n. (Also first cousin) child of one's uncle or aunt; my second (third) cousin, my parent's first (second) cousin's child; my first cousin once (twice) removed, my first cousin's child (grandchild), also my parent's (grandparent's) first cousin. Put more precisely, any two persons whose closest common ancestor is (m+1) generations away from one person and (m+1)+n generations away from the other are mth cousins nce removed. Normally, m ³ 1 and n ³ 0, but being used to computers counting from 0, in this problem we require m ³ 0 and n ³ 0. This extends the normal definition so that siblings are zeroth cousins. We write such a relationship as cousin-m-n. If one of the persons is an ancestor of the other, p generations away where p ³ 1, they have a relationship descendant-p. A relationship cousin-m1-n1 is closer than a relationship cousin-m2-n2 if m1 < m2 or (m1 = m2 and n1 < n2). A relationship descendant-p1 is closer than a relationship descendant-p2 if p1 < p2. A descendant-p relationship is always closer than a cousin-m-n relationship. Write a program that accepts definitions of simple relationships between individuals and displays the closest cousin or descendant relationship, if any, which exists between arbitrary pairs of individuals. Input Each line in the input begins with one of the characters '#', 'R', 'F' or 'E'. '#' lines are comments. Ignore them. 'R' lines direct your program to record a relationship between two different individuals. The first 5 characters following the 'R' constitute the name of the first person; the next 5 characters constitute the name of the second. Case is significant. Following the names, possibly separated from them by blanks, is a non-negative integer, k, defining the relationship. If k is 0, then the named individuals are siblings. If k is 1, then the first named person is a child of the second. If k is 2, then the first named person is a grandchild of the second, and so forth. Ignore anything on the line following the integer. 'F' lines are queries; your program is to find the closest relationship, if any, which exists between the two different persons whose 5 character names follow the 'F'. Ignore anything on the line following the second name. A query should be answered only with regard to 'R' lines which precede the query in the input. There will be one 'E' line to mark the end of the input data. Ignore anything on or after the 'E' line. Output For each 'F' line, your program is to report the closest relationship that exists between the two persons named aaaaa and bbbbb in one of the following formats: aaaaa and bbbbb are descendant-p. aaaaa and bbbbb are cousin-m-n. with m, n and p replaced by integers calculated as defined above. If no relationship exists between the pair, your program is to output the following: aaaaa and bbbbb are not related. Assumption: A person is not an ancestor of himself/herself. Sample Input # A Comment! RFred Joe 1 Fred is Joe's son RFran Fred 2 RJake Fred 1 RBill Joe 1 RBill Sue 1 RJean Sue 1 RJean Don 1 RPhil Jean 3 RStan Jean 1 RJohn Jean 1 RMary Don 1 RSusanMary 4 RPeg Mary 2 FFred Joe FJean Jake FPhil Bill FPhil Susan FJake Bill FDon Sue FStan John FPeg John FJean Susan FFran Peg FJohn Avram RAvramStan 99 FJohn Avram FAvramPhil E Output for the Sample Input Fred and Joe are descendant-1. Jean and Jake are not related. Phil and Bill are cousin-0-3. Phil and Susan are cousin-3-1. Jake and Bill are cousin-0-1. Don and Sue are not related. Stan and John are cousin-0-0. Peg and John are cousin-1-1. Jean and Susan are cousin-0-4. Fran and Peg are not related. John and Avram are not related. John and Avram are cousin-0-99. Avram and Phil are cousin-2-97. Diagram of the Sample Input 6) VTAS - Vessel Traffic Advisory Service In order to promote safety and efficient use of port facilities, the Association of Coastal Merchants (ACM) has developed a concept for a Vessel Traffic Advisory Service (VTAS) that will provide traffic advisories for vessels transiting participating ports. The concept is built on a computer program that maintains information about the traffic patterns and reported movements of vessels within the port over multiple days. For each port, the traffic lanes are defined between waypoints. The traffic lanes have been designated as directional to provide traffic separation and flow controls. Each port is represented by a square matrix containing the distances (in nautical miles) along each valid traffic lane. The distances are defined from each row waypoint to each column waypoint. A distance of 0 indicates that no valid traffic lane exists between the two waypoints. Vessel traffic enters the port at a waypoint and transits the traffic lanes. A vessel may begin its transit at any of the waypoints and must follow a valid connected route via the valid traffic lanes. A vessel may end its transit at any valid waypoint. The service provided by the VTAS to transiting vessels includes: ¼ Projection of arrival times at waypoints ¼ Notification of invalid routes ¼ Projected encounters with other vessels on each leg of the transit. An ÒencounterÓ occurs when two vessels are between common waypoints (either traffic lane) at a common time ¼ Warning of close passing with another vessel in the vicinity of a waypoint (within 3 minutes of projected waypoint arrival) Reported times will be rounded to the nearest whole minute. Time is maintained based on a 24 hour clock (i.e. 9 am is 0900, 9 PM is 2100, midnight is 0000). Speed is measured in knots which is equal to 1 nautical mile per hour. Input The input file for the computer program include a Port Specification to provide the description of the traffic patterns within the port and a Traffic List which contains the sequence of vessels entering the port and their intended tracks. The end of the input is indicated by a Vessel Name beginning with an "*" Port Specification : Number of Waypoints in Port (an integer N) Waypoint ID List (N single-character designators) Waypoint Connection Matrix (N rows of N real values specifying the distances between waypoints in nautical miles) Traffic List: Vessel Name (alphabetic characters) Time at first waypoint (on 24-hour clock) & Planned Transit Speed (in knots) Planned Route (ordered list of waypoints) Output The output shall provide for each vessel as it enters the port a listing indicating the arrival of the vessel and its planned speed followed by a table containing the waypoints in its route and projected arrival at each waypoint. Following this table will be appropriate messages indicating: ¼ Notification of Invalid Routes ¼ Projected Encounters on each leg ¼ Warning of close passing at waypoints All times are to be printed as four-digit integers with leading zeros when necessary. Assumptions & Limitations 1. Vessel names are at most 20 characters long. 2. There are at most 20 waypoints in a port and at most 20 waypoints in any route. 3. There will be at most 20 vessels in port at any time. 4. A vessel will complete its transit in at most 12 hours. 5. No more than 24 hours will elapse between vessel entries. Sample Input 6 ABCDEF 0 3 0 0 0 0 3 0 0 2 0 0 0 3 0 0 0 0 0 0 0 0 3 0 0 0 2 0 0 4 0 0 0 0 4 0 Tug 2330 12 ABDEF WhiteSailboat 2345 6 ECBDE TugWBarge 2355 5 DECBA PowerCruiser 0 15 FECBA LiberianFreighter 7 18 ABDXF ChineseJunk 45 8 ACEF *****  Output for the Sample Input Tug entering system at 2330 with a planned speed of 12.0 knots Waypoint: A B D E F Arrival: 2330 2345 2355 0010 0030 WhiteSailboat entering system at 2345 with a planned speed of 6.0 knots Waypoint: E C B D E Arrival: 2345 0005 0035 0055 0125 TugWBarge entering system at 2355 with a planned speed of 5.0 knots Waypoint: D E C B A Arrival: 2355 0031 0055 0131 0207 Projected encounter with Tug on leg between Waypoints D & E ** Warning ** Close passing with Tug at Waypoint D PowerCruiser entering system at 0000 with a planned speed of 15.0 knots Waypoint: F E C B A Arrival: 0000 0016 0024 0036 0048 Projected encounter with Tug on leg between Waypoints F & E Projected encounter with WhiteSailboat on leg between Waypoints C & B ** Warning ** Close passing with WhiteSailboat at Waypoint B LiberianFreighter entering system at 0007 with a planned speed of 18.0 knots **> Invalid Route Plan for Vessel: LiberianFreighter ChineseJunk entering system at 0045 with a planned speed of 8.0 knots **> Invalid Route Plan for Vessel: ChineseJunk 7) Jill's Bike Jill Bates hates climbing hills. Jill rides a bicycle everywhere she goes, but she always wants to go the easiest and shortest way possible. The good news is that she lives in Greenhills, which has all its roads laid out in a strictly rectangular gridÑeast-west roads are streets; north-south roads are avenues and the distance between any two adjacent grid points is the same. The bad news is that Greenhills is very hilly and has many one-way roads. In choosing a route between where she starts and where she ends, Jill has three rules: 1. Avoid any climb of more than 10 meters between adjacent grid points. 2. Never go the wrong way on a one-way road. 3. Always travel the shortest possible route. Your program should help Jill find an acceptable route. Input The input file contains data in the following form: * The first line contains two integers, separated by one or more spaces. The first integer n represents the number of streets, and the second integer m represents the number of avenues, 1² n ²20, 1² m ²20. * The next n lines contain the altitudes of grid points. Each line represents a street and contains a sequence of m integers separated by one or more spaces. These integers represent the altitude in meters of the grid points along that street. Even if a particular street and avenue have no intersection, the altitude is still given for that grid point. * One or more lines follow that define the one-way roads. Each road is represented by two pairs of integers, separated by one or more spaces, in the form: street avenue street avenue The first street and avenue define the starting point of the road and the second pair define the ending point. Since Greenhills is a strict grid, if the two points are not adjacent in the grid, the road passes through all the intervening grid points. For example, 5 7 5 10 represents roads 5-7 to 5-8, 5-8 to 5-9, and 5-9 to 5-10. Road definitions are terminated by a line containing four zeroes in the above format. * Finally, one or more lines will follow that contain pairs of grid points between which Jill wants to find an optimal path, in the form: street avenue street avenue As before, the integer pairs are separated by one or more spaces. The end of the input set is defined by a line containing four zeroes, formatted as before. You may assume that all street and avenue numbers are within the bounds defined by the first line of input, and that all road definitions are strictly north-south or east-west. Output For each path query in the input file, output a sequence of grid points, from the starting grid point to the ending grid point, which meets Jill's three rules. Output grid points as 'street-avenue' separated by the word 'to'. If there is more than one path that meets Jill's criteria, any such path will be acceptable. If no route satisfies all the criteria, or if the starting and ending grid points are the same, output an appropriate message to that effect. Output a blank line between each output set. Sample Input 3 4 10 15 20 25 19 30 35 30 10 19 26 20 1 1 1 4 2 1 2 4 3 4 3 3 3 3 1 3 1 4 3 4 2 4 2 1 1 1 2 1 0 0 0 0 1 1 2 2 2 3 2 3 2 2 1 1 0 0 0 0 Output for the Sample Input 1-1 to 1-2 to 1-3 to 1-4 to 2-4 to 2-3 to 2-2 To get from 2-3 to 2-3, stay put! There is no acceptable route from 2-2 to 1-1. 8) Variable Radix Huffman Encoding Huffman encoding is a method of developing an optimal encoding of the symbols in a source alphabet using symbols from a target alphabet when the frequencies of each of the symbols in the source alphabet are known. Optimal means the average length of an encoded message will be minimized. In this problem you are to determine an encoding of the first N uppercase letters (the source alphabet, S1 through SN, with frequencies f1 through fN) into the first R decimal digits (the target alphabet, T1 through TR). Consider determining the encoding when R=2. Encoding proceeds in several passes. In each pass the two source symbols with the lowest frequencies, say S1 and S2, are grouped to form a new "combination letter" whose frequency is the sum of f1 and f2. If there is a tie for the lowest or second lowest frequency, the letter occurring earlier in the alphabet is selected. After some number of passes only two letters remain to be combined. The letters combined in each pass are assigned one of the symbols from the target alphabet. The letter with the lower frequency is assigned the code 0, and the other letter is assigned the code 1. (If each letter in a combined group has the same frequency, then 0 is assigned to the one earliest in the alphabet. For the purpose of comparisons, the value of a "combination letter" is the value of the earliest letter in the combination.) The final code sequence for a source symbol is formed by concatenating the target alphabet symbols assigned as each combination letter using the source symbol is formed. The target symbols are concatenated in the reverse order that they are assigned so that the first symbol in the final code sequence is the last target symbol assigned to a combination letter. The two illustrations below demonstrate the process for R=2. Symbol Frequency Symbol Frequency A 5 A 7 B 7 B 7 C 8 C 7 D 1 D 75 Pass 1: A and B grouped Pass 1: A and B grouped Pass 2: {A,B} and C grouped Pass 2: C and D grouped Pass 3: {A,B,C} and D grouped Pass 3: {A,B} and {C,D} grouped Resulting codes: A=110, B=111, Resulting codes: A=00, B=01, C=10, D=0 C=10, D=11 Avg len=(3*5+3*7+2*8+1*15)/35=1.91 Avg len=(2*7+2*7+2*7+2*7)/28=2.00 When R is larger than 2, R symbols are grouped in each pass. Since each pass effectively replaces R letters or combination letters by 1 combination letter, and the last pass must combine R letters or combination letters, the source alphabet must contain k*(RÐ1)+R letters, for some integer k. Since N may not be this large, an appropriate number of fictitious letters with zero frequencies must be included. These fictitious letters are not to be included in the output. In making comparisons, the fictitious letters are later than any of the letters in the alphabet. Now the basic process of determining the Huffman encoding is the same as for the R=2 case. In each pass, the R letters with the lowest frequencies are grouped, forming a new combination letter with a frequency equal to the sum of the letters included in the group. The letters that were grouped are assigned the target alphabet symbols 0 through RÐ1. 0 is assigned to the letter in the combination with the lowest frequency, 1 to the next lowest frequency, and so forth. If several of the letters in the group have the same frequency, the one earliest in the alphabet is assigned the smaller target symbol, and so forth. The illustration below demonstrates the process for R=3. Symbol Frequency A 5 B 7 C 8 D 15 Pass 1: ? (fictitious symbol), A and B are grouped Pass 2: {?,A,B}, C and D are grouped Resulting codes: A=11, B=12, C=0, D=2 Avg len=(2*5+2*7+1*8+1*15)/35=1.34 Input The input will contain one or more data sets, one per line. Each data set consists of an integer value for R (between 2 and 10), an integer value for N (between 2 and 26), and the integer frequencies f1 through fN, each of which is between 1 and 999. The end of data for the entire input is the number 0 for R; it is not considered to be a separate data set. Output For each data set, display its number (numbering is sequential starting with 1) and the average target symbol length (rounded to two decimal places) on one line. Then display the N letters of the source alphabet and the corresponding Huffman codes, one letter and code per line. The examples below illustrate the required output format. Sample Input 2 5 5 10 20 25 40 2 5 4 2 2 1 1 3 7 20 5 8 5 12 6 9 4 6 10 23 18 25 9 12 0 Output for the Sample Input Set 1; average length 2.10 A: 1100 B: 1101 C: 111 D: 10 E: 0 Set 2; average length 2.20 A: 11 B: 00 C: 01 D: 100 E: 101 Set 3; average length 1.69 A: 1 B: 00 C: 20 D: 01 E: 22 F: 02 G: 21 Set 4; average length 1.32 A: 32 B: 1 C: 0 D: 2 E: 31 F: 33 9) Sail Race The Atlantic Coastal Mariners (ACM) sailing club is building a race planning tool to estimate durations of sailboat races with various race courses, wind directions, and types of sailboats. You must write a program to help with that task. A race course is defined by marks with up to 10 marks per race course. A sailboat must sail to all marks in the specified order. The marks are identified as x- and y-coordinates on a hypothetical grid with a single unit equal to one nautical mile (nm). The positive y-axis is oriented due north and the positive x-axis is oriented due east. The race course is in open waters without any navigational limitations. For purposes of this planning tool, the only driving force controlling a sailboat is the wind. The wind determines the sailboat's speed of advance and limits its direction of travel. The wind is constant for the duration of each race and is specified in terms of the direction from which the wind is blowing and its speed in nautical miles per hour (kts). Wind direction is specified as a compass bearing in degrees measured clockwise from 000.0¥ as north. Sailboats cannot steer any closer to the wind than a given "point angle" off the wind direction. In order to make progress closer to the wind direction, the sailboat must tack back and forth across the wind, steering no closer to the wind than its point angle. Each time the sailboat tacks or passes a mark it incurs a tack penalty. For this simulation, each sailboat will travel each leg of a race (the portion of a race between successive marks) with the minimum number of tacks and the minimum possible distance. Courses and directions are specified as compass bearings in degrees measured clockwise from 000.0¥ as north. The speed of a sailboat is determined by the sailboat design, wind speed, and direction steered relative to the wind. In the figure, the wind direction is 45¥ and the point angle is 40¥. This means then that this sailboat cannot steer between 5¥ and 85¥ because it cannot point that closely into the wind. For this problem, the ratio of sailboat speed to wind speed is one of three ratios, selected as shown in the table below according to the angle off the wind : Angle off wind Applicable ratio >= point angle and < reach angle point speed ratio >= reach angle and < downwind angle reach speed ratio >= downwind angle downwind speed ratio For instance, if the boat is steering at an angle off the wind which is between the reach angle and downwind angle then boat speed = reach speed ratio * wind speed Input Your solution must accept multiple input data sets. Each data set represents a different race course to be evaluated for a single sailboat. The data set begins with a line with 4 numbers: wind direction (real), wind speed (real), tack penalty (real), and number of marks n (integer). The next line contains six real numbers: point angle, point speed ratio, reach angle, reach speed ratio, downwind angle, downwind speed ratio. The subsequent n lines of the data set represent the n race marks in the order in which they must be reached. Each line begins with a 2-character mark id followed by the x-coordinate then y-coordinate of the mark. The end of input is denoted by a line of four 0's. Output The output for your program consists of various data calculated for each input data set. Values should be presented with the following precisions and units. Courses, tacks, directions 0.1 degree Distance 0.01 nm Speed 0.1 kts Time 0.01 hours Output for each race begins with a header containing the number of the data set (1 for the first, 2 for the second, etc.) and the number of legs. The next line is the total length of the race course, measured as the sum of distances between successive marks. For each leg of the course, the leg number, beginning and ending mark id's, course from the beginning to end marks of the leg, and the leg distance is presented. This is followed by a listing of the tacks necessary to complete the leg. The tacks for each race are numbered sequentially, with tack numbers beginning with 1 for each race. For each tack, the tack number, the projected sailboat speed, the course steered, and the length of that tack are presented. The summary output for each data set includes the total number of tacks, the total distance traveled for the race, the estimated race duration, and the total tack penalty time incurred by the sailboat after leaving the first mark. The exact format of the output is not specified, but all output should be organized so that it is in the specified order, appropriately labeled and follows given numeric specifications. Sample Input 45 10 .1 6 45 0.5 90 0.75 135 0.67 M1 15 10 M2 25 20 M3 22 30 M4 5 25 M5 10 15 M6 10 10 0 0 0 0 Output for the Sample Input ======================== Race 1 has 5 legs The race layout is 58.48 nm long ----------------------------- Leg 1 from Mark M1 to M2 == > Direction: 45.0 Distance: 14.14 nm Tack 1 ==> Speed: 5.0 Direction: 90.0 Distance: 10.00 nm Tack 2 ==> Speed: 5.0 Direction: 0.0 Distance: 10.00 nm Leg 2 from Mark M2 to M3 == > Direction: 343.3 Distance: 10.44 nm Tack 3 ==> Speed: 5.0 Direction: 343.3 Distance: 10.44 nm Leg 3 from Mark M3 to M4 == > Direction: 253.6 Distance: 17.72 nm Tack 4 ==> Speed: 6.7 Direction: 253.6 Distance: 17.72 nm Leg 4 from Mark M4 to M5 == > Direction: 153.4 Distance: 11.18 nm Tack 5 ==> Speed: 7.5 Direction: 153.4 Distance: 11.18 nm Leg 5 from Mark M5 to M6 == > Direction: 180.0 Distance: 5.00 nm Tack 6 ==> Speed: 6.7 Direction: 180.0 Distance: 5.00 nm -------------------------------- Race 1 was 64.34 nm long with 6 tack legs Estimated Race Duration is 11.47 hours with 0.50 hours of Tack Penalty 10) Theseus and the Minotaur Those of you with a classical education may remember the legend of Theseus and the Minotaur. This is an unlikely tale involving a bull-headed monster, lovelorn damsels, balls of silk and an underground maze full of twisty little passages all alike. In line with the educational nature of this contest, we will now reveal the true story. The maze was a series of caverns connected by passages. Theseus managed to smuggle into the labyrinth with him a supply of candles and a small tube of phosphorescent paint with which he could mark his way, or, more specifically, the exits he used. He knew that he would be lowered into a passage between two caverns, and that if he could find and kill the Minotaur he would be set free. His intended strategy was to move cautiously along a passage until he came to a cavern and then turn right (he was left-handed and wished to keep his sword away from the wall) and feel his way around the edge of the cavern until he came to an exit. If this was unmarked, he would mark it and enter it; if it was marked he would ignore it and continue around the cavern. If he heard the Minotaur in a cavern with him, he would light a candle and kill the Minotaur, since the Minotaur would be blinded by the light. If, however, he met the Minotaur in a passage he would be in trouble, since the size of the passage would restrict his movements and he would be unable to either light a candle or fight adequately. When he entered a cavern that had been previously entered by the Minotaur he would light a candle and leave it there and then turn right (as usual) but take the Minotaur's exit. In the meantime, the Minotaur was also searching for Theseus. He was bigger and slower-moving but he knew the caverns well and hence, unlikely as it may seem, every time he emerged from a passage into a cavern, so did Theseus, albeit usually in a different one. The Minotaur turned left when he entered a cavern and traveled clockwise around it until he came to an unmarked (by him) exit, at which point he would mark it and take it. If he sensed that the cavern he was about to enter had a candle burning in it, he would turn and flee back up the passage he had just used, arriving back at the previous cavern to complete his 'turn.' Consider the following labyrinth as an example Assume that Theseus starts off between A and C going toward C, and that the Minotaur starts off between F and H going toward H. After entering C, Theseus will move to D, whereas the Minotaur, after entering H will move to G. Theseus will then move towards G while the Minotaur will head for D and Theseus will be killed in the corridor between D and G. If, however, Theseus starts off as before and the Minotaur starts off between D and G then, while Theseus moves from C to D to G, the Minotaur moves from G to E to F. When Theseus enters G he detects that the Minotaur has been there before him and heads for E, and not for H, reaching it as the Minotaur reaches H. The Minotaur is thwarted in his attempt to get to G and turns back, arriving in H just as Theseus, still 'following' the Minotaur arrives in F. The Minotaur tries E and is again thwarted and arrives back at H just as Theseus arrives in hot pursuit. Thus the Minotaur is slain in H. Write a program that will simulate Theseus' pursuit of the Minotaur. Input Input will consist of a series of labyrinths. Each labyrinth will contain a series of cavern descriptors, one per line. Each line will contain a cavern identifier (a single upper case character) followed by a colon (:) and a list of caverns reachable from it (in counterclockwise order). No cavern will be connected to itself. The cavern descriptors will not be ordered in any way. The description of a labyrinth will be terminated by a line starting with a @ character, followed by two pairs of cavern identifiers. The first pair indicates the passage in which Theseus starts, and the second in which the Minotaur starts. The travel in a starting passage is toward the cavern whose identifier is the second character in the pair. The file will be terminated by a line consisting of a single #. A final encounter is possible for each input data set. Output Output will consist of one line for each labyrinth. Each line will specify who gets killed and where. Note that if the final encounter takes place in a passage it should be specified from Theseus' point of view. Follow the format shown in the example below exactly, which describes the situations referred to above. Sample Input A:BCD D:BACG F:HE G:HED B:AD E:FGH H:FEG C:AD @ACFH A:BCD D:BACG F:HE G:HED B:AD E:FGH H:FEG C:AD @ACDG # Output for the Sample Input Theseus is killed between D and G The Minotaur is slain in H 11) 1 Problem: Tree Summing Background LISP was one of the earliest high-level programming languages and, with FORTRAN, is one of the oldest languages currently being used. Lists, which are the fundamental data structures in LISP, can easily be adapted to represent other important data structures such as trees. This problem deals with determining whether binary trees represented as LISP S-expressions possess a certain property. The Problem Given a binary tree of integers, you are to write a program that determines whether there exists a root-to-leaf path whose nodes sum to a specified integer. For example, in the tree shown below there are exactly four root-to-leaf paths. The sums of the paths are 27, 22, 26, and 18. +---+ | 5 | +---+ / \ / \ +---+ +---+ | 4 | | 8 | +---+ +---+ / / \ / / \ +---+ +---+ +---+ |11 | |13 | | 4 | +---+ +---+ +---+ / \ \ / \ \ +---+ +---+ +---+ | 7 | | 2 | | 1 | +---+ +---+ +---+ Binary trees are represented in the input file as LISP S-expressions having the following form. empty tree ::= () tree ::= empty tree | (integer tree tree) The tree diagrammed above is represented by the expression (5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) ) Note that with this formulation all leaves of a tree are of the form (integer () () ) Since an empty tree has no root-to-leaf paths, any query as to whether a path exists whose sum is a specified integer in an empty tree must be answered negatively. The Input The input consists of a sequence of test cases in the form of integer/tree pairs. Each test case consists of an integer followed by one or more spaces followed by a binary tree formatted as an S-expression as described above. All binary tree S-expressions will be valid, but expressions may be spread over several lines and may contain spaces. There will be one or more test cases in an input file, and input is terminated by end-of-file. The Output There should be one line of output for each test case (integer/tree pair) in the input file. For each pair I,T (I represents the integer, T represents the tree) the output is the string yes if there is a root-to-leaf path in T whose sum is I and no if there is no path in T whose sum is I. Sample Input 22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) 20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()())))) 10 (3 (2 (4 () () ) (8 () () ) ) (1 (6 () () ) (4 () () ) ) ) 5 () Sample Output yes no yes no 12) Climbing Trees Background Expression trees, B and B* trees, red-black trees, quad trees, PQ trees; trees play a significant role in many domains of computer science. Sometimes the name of a problem may indicate that trees are used when they are not, as in the Artificial Intelligence planning problem traditionally called the Monkey and Bananas problem. Sometimes trees may be used in a problem whose name gives no indication that trees are involved, as in the Huffman code. This problem involves determining how pairs of people who may be part of a ``family tree'' are related. The Problem Given a sequence of child-parent pairs, where a pair consists of the child's name followed by the (single) parent's name, and a list of query pairs also expressed as two names, you are to write a program to determine whether the query pairs are related. If the names comprising a query pair are related the program should determine what the relationship is. Consider academic advisees and advisors as exemplars of such a single parent genealogy (we assume a single advisor, i.e., no co-advisors). In this problem the child-parent pair pq denotes that p is the child of q. In determining relationships between names we use the following definitions: * p is a 0-descendent of q (respectively 0-ancestor) if and only if the child-parent pair p q (respectively q p) appears in the input sequence of child-parent pairs. * p is a k-descendent of q (respectively k-ancestor) if and only if the child-parent pair p r (respectively q r) appears in the input sequence and r is a (k-1)-descendent of q (respectively p is a (k-1)-ancestor of r). For the purposes of this problem the relationship between a person p and a person q is expressed as exactly one of the following four relations: 1. child --- grand child, great grand child, great great grand child, etc. By definition p is the ``child'' of q if and only if the pair p q appears in the input sequence of child-parent pairs (i.e., p is a 0-descendent of q); p is the ``grand child'' of q if and only if p is a 1-descendent of q; and p is the ``great great ... great grand child'' of q |---------v---------| n times if and only if p is an (n+1)-descendent of q. 2. parent --- grand parent, great grand parent, great great grand parent, etc. By definition p is the ``parent'' of q if and only if the pair q p appears in the input sequence of child-parent pairs (i.e., p is a 0-ancestor of q); p is the ``grand parent'' of q if and only if p is a 1-ancestor of q; and p is the `` great great ...great grand parent'' of q |---------v--------| n times if and only if p is an (n+1)-ancestor of q. th st nd 3. cousin --- 0 cousin, 1 cousin, 2 cousin, etc.; cousins may be once removed, twice removed, three times removed, etc. By definition p and q are ``cousins'' if and only if they are related (i.e., there is a path from p to q in the implicit undirected parent-child tree). Let r represent the least common ancestor of p and q (i.e., no descendent of r is an ancestor of both p and q), where p is an m-descendent of r and q is an n-descendent of r. th Then, by definition, cousins p and q are ``k cousins'' if and only if k= min(n,m), and, also by definition, p and q are ``cousins removed j times'' if and only if j =|n-m|. th 4. sibling --- 0 cousins removed 0 times are ``siblings'' (they have the same parent). The Input The input consists of parent-child pairs of names, one pair per line. Each name in a pair consists of lower-case alphabetic characters or periods (used to separate first and last names, for example). Child names are separated from parent names by one or more spaces. Parent-child pairs are terminated by a pair whose first component is the string ``no.child''. Such a pair is NOT to be considered as a parent-child pair, but only as a delimiter to separate the parent-child pairs from the query pairs. There will be no circular relationships, i.e., no name p can be both an ancestor and a descendent of the same name q. The parent-child pairs are followed by a sequence of query pairs in the same format as the parent-child pairs, i.e., each name in a query pair is a sequence of lower-case alphabetic characters and periods, and names are separated by one or more spaces. Query pairs are terminated by end-of-file. There will be a maximum of 300 different names overall (parent-child and query pairs). All names will be fewer than 31 characters in length. There will be no more than 100 query pairs. The Output For each query-pair pq of names the output should indicate the relationship p is-the-relative-of q by the appropriate string of the form * child, grand child, great grand child, great great ... great grand child * parent, grand parent, great grand parent, great great ... great grand parent * sibling * n cousin removed m * no relation If an m-cousin is removed 0 times then only m cousin should be printed, i.e., removed 0 should NOT be printed. Do not print st, nd, rd, th after the numbers. Sample Input alonzo.church oswald.veblen stephen.kleene alonzo.church dana.scott alonzo.church martin.davis alonzo.church pat.fischer hartley.rogers mike.paterson david.park dennis.ritchie pat.fischer hartley.rogers alonzo.church les.valiant mike.paterson bob.constable stephen.kleene david.park hartley.rogers no.child no.parent stephen.kleene bob.constable hartley.rogers stephen.kleene les.valiant alonzo.church les.valiant dennis.ritchie dennis.ritchie les.valiant pat.fischer michael.rabin Sample Output parent sibling great great grand child 1 cousin removed 1 1 cousin removed 1 no relation 13) Unidirectional TSP Background Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) --- finding whether all the cities in a salesperson's route can be visited exactly once with a specified limit on travel time --- is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check. This problem deals with finding a minimal path through a grid of points while traveling only from left to right. The Problem Given an mxn matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix ``wraps'' so that it represents a horizontal cylinder. Legal steps are illustrated below. +---+ | | | | +---+---+ | / | | | --| | | \ | | +---+---+ | | | | +---+ The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited. For example, two slightly different 5x6 matrices are shown below (the only difference is the numbers in the bottom row). / +---+---+---+---+---+---+ +---+---+---+---+---+---+ | | | | | | | | | | /| | | | -|-3 | 4 | 1 | 2 | 8 | 6 | -|-3 | 4 | 1 | 2 | 8 | 6 | | \| | | | | | | \| |/ | | | | +---+---+---+---+---+---+ +---+---+---+---+---+---+ | |\ | | | | | | |\ /| | | | | | 6 | 1 | 8 | 2 | 7 | 4 | | 6 | 1 | 8 | 2 | 7 | 4 | | | \| | | | | | | | | | | | +---+---+---+---+---+---+ +---+---+---+---+---+---+ | | |\ | | | | | | | | | | | | 5 | 9 | 3 | 9 | 9 | 5 | | 5 | 9 | 3 | 9 | 9 | 5 | | | | \| | | | | | | | | | | +---+---+---+---+---+---+ +---+---+---+---+---+---+ | | | |\ | | | | | | | | | | | 8 | 4 | 1 | 3-|-2 | 6 | | 8 | 4 | 1 | 3 | 2 | 6 | | | | | | \| | | | | | |/ \| | +---+---+---+---+---+---+ +---+---+---+---+---+---+ | | | | | |\ | | | | | /| |\ | | 3 | 7 | 2 | 8 | 6 | 4-|-> | 3 | 7 | 2 | 1 | 2 | 3-|-> | | | | | | | | | | |/ | | | +---+---+---+---+---+---+ +---+---+---+---+---+---+ / The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows. The Input The input consists of a sequence of matrix specifications. Each matrix specification consists of the row and column dimensions in that order on a line followed by mn integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in an input file. Input is terminated by end-of-file. For each specification the number of rows will be between 1 and 9 inclusive; the number of columns will be between 1 and 100 inclusive. No path's weight will exceed integer values representable using 30 bits. The Output Two lines should be output for each matrix specification in the input file, the first line represents a minimal-weight path, and the second line is the cost of a minimal path. The path consists of a sequence of n integers (separated by one or more spaces) representing the rows that constitute the minimal path. If there is more than one path of minimal weight the path that is lexicographically smallest should be output. Sample Input 5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 8 6 4 5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 1 2 3 2 2 9 10 9 10 Sample Output 1 2 3 4 4 5 16 1 2 1 5 4 5 11 1 1 19 14) The Postal Worker Rings Once Background Graph algorithms form a very important part of computer science and have a lineage that goes back at least to Euler and the famous Seven Bridges of Koenigsberg problem. Many optimization problems involve determining efficient methods for reasoning about graphs. This problem involves determining a route for a postal worker so that all mail is delivered while the postal worker walks a minimal distance, so as to rest weary legs. The Problem Given a sequence of streets (connecting given intersections) you are to write a program that determines the minimal cost tour that traverses every street at least once. The tour must begin and end at the same intersection. The ``real-life'' analogy concerns a postal worker who parks a truck at an intersection and then walks all streets on the postal delivery route (delivering mail) and returns to the truck to continue with the next route. The cost of traversing a street is a function of the length of the street (there is a cost associated with delivering mail to houses and with walking even if no delivery occurs). In this problem the number of streets that meet at a given intersection is called the degree of the intersection. There will be at most two intersections with odd degree. All other intersections will have even degree, i.e., an even number of streets meeting at that intersection. The Input The input consists of a sequence of one or more postal routes. A route is composed of a sequence of street names (strings), one per line, and is terminated by the string ``deadend'' which is NOT part of the route. The first and last letters of each street name specify the two intersections for that street, the length of the street name indicates the cost of traversing the street. All street names will consist of lowercase alphabetic characters. For example, the name foo indicates a street with intersections f and o of length 3, and the name computer indicates a street with intersections c and r of length 8. No street name will have the same first and last letter and there will be at most one street directly connecting any two intersections. As specified, the number of intersections with odd degree in a postal route will be at most two. In each postal route there will be a path between all intersections, i.e., the intersections are connected. The Output For each postal route the output should consist of the cost of the minimal tour that visits all streets at least once. The minimal tour costs should be output in the order corresponding to the input postal routes. Sample Input one two three deadend mit dartmouth linkoping tasmania york emory cornell duke kaunas hildesheim concord arkansas williams glasgow deadend Sample Output 11 114 15) Trees on the level Background Trees are fundamental in many branches of computer science. Current state-of-the art parallel computers such as Thinking Machines' CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics. This problem involves building and traversing binary trees. The Problem Given a sequence of binary trees, you are to write a program that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes. In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k+1. For example, a level order traversal of the tree +---+ | 5 | +---+ / \ / \ +---+ +---+ | 4 | | 8 | +---+ +---+ / / \ / / \ +---+ +---+ +---+ |11 | |13 | | 4 | +---+ +---+ +---+ / \ \ / \ \ +---+ +---+ +---+ | 7 | | 2 | | 1 | +---+ +---+ +---+ is: 5, 4, 8, 11, 13, 4, 7, 2, 1. In this problem a binary tree is specified by a sequence of pairs (n,s) where n is the value at the node whose path from the root is given by the string s. A path is given be a sequence of L's and R's where L indicates a left branch and R indicates a right branch. In the tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node paths in the tree is given a value exactly once. The Input The input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs (n,s) as described above separated by whitespace. The last entry in each tree is (). No whitespace appears between left and right parentheses. All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes. Input is terminated by end-of-file. The Output For each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ``not complete'' should be printed. Sample Input (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) () (3,L) (4,R) () Sample Output 5 4 8 11 13 4 7 2 1 not complete 16) Following Orders (experts only) Background Order is an important concept in mathematics and in computer science. For example, Zorn's Lemma states: ``a partially ordered set in which every chain has an upper bound contains a maximal element.'' Order is also important in reasoning about the fix-point semantics of programs. This problem involves neither Zorn's Lemma nor fix-point semantics, but does involve order. The Problem Given a list of variable constraints of the form x < y, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the constraints x < y and x < z there are two orderings of the variables x, y, and z that are consistent with these constraints: x y z and x z y. The Input The input consists of a sequence of constraint specifications. A specification consists of two lines: a list of variables on one line followed by a list of contraints on the next line. A constraint is given by a pair of variables, where x y indicates that x < y. All variables are single character, lower-case letters. There will be at least two variables, and no more than 20 variables in a specification. There will be at least one constraint, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the contraints in a specification. Input is terminated by end-of-file. The Output For each constraint specification, all orderings consistent with the constraints should be printed. Orderings are printed in lexicographical (alphabetical) order, one per line. Characters on a line are separated by whitespace. Output for different constraint specifications is separated by a blank line. Sample Input a b f g a b b f v w x y z v y x v z v w v Sample Output abfg abgf agbf gabf wxzvy wzxvy xwzvy xzwvy zwxvy zxwvy 17) Numbering Paths (experts only) Background Problems that process input and generate a simple ``yes'' or ``no'' answer are called decision problems. One class of decision problems, the NP-complete problems, are not amenable to general efficient solutions. Other problems may be simple as decision problems, but enumerating all possible ``yes'' answers may be very difficult (or at least time-consuming). This problem involves determining the number of routes available to an emergency vehicle operating in a city of one-way streets. The Problem Given the intersections connected by one-way streets in a city, you are to write a program that determines the number of different routes between each intersection. A route is a sequence of one-way streets connecting two intersections. Intersections are identified by non-negative integers. A one-way street is specified by a pair of intersections. For example, j k indicates that there is a one-way street from intersection j to intersection k. Note that two-way streets can be modeled by specifying two one-way streets: j k and kj. Consider a city of four intersections connected by the following one-way streets: 0 1 0 2 1 2 2 3 There is one route from intersection 0 to 1, two routes from 0 to 2 (the routes are 0->1->2 and 0->2), one route from 2 to 3, and no other routes. It is possible for an infinite number of different routes to exist. For example if the intersections above are augmented by the street 3 2, there is still only one route from 0 to 1, but there are infinitely many different routes from 0 to 2. This is because the street from 2 to 3 and back to 2 can be repeated yielding a different sequence of streets and hence a different route. Thus the route 0->2->3->2-> 3->2 is a different route than 0->2->3->2. The Input The input is a sequence of city specifications. Each specification begins with the number of one-way streets in the city followed by that many one-way streets given as pairs of intersections. Each pair j k represents a one-way street from intersection j to intersection k. In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection. All integers in the input are separated by whitespace. The input is terminated by end-of-file. There will never be a one-way street from an intersection to itself. No city will have more than 30 intersections. The Output For each city specification, a square matrix of the number of different routes from intersection j to intersection k is printed. If the matrix is denoted M, then M[j][k] is the number of different routes from intersection j to intersection k. The matrix M should be printed in row-major order, one row per line. Each matrix should be preceded by the string ``matrix for city k'' (with k appropriately instantiated, beginning with 0). If there are an infinite number of different paths between two intersections a -1 should be printed. DO NOT worry about justifying and aligning the output of each matrix. All entries in a row should be separated by whitespace. Sample Input 7 0 1 0 2 0 4 2 4 2 3 3 1 4 3 5 0 2 0 1 1 5 2 5 2 1 9 0 1 0 2 0 3 0 4 1 4 2 1 2 0 3 0 3 1 Sample Output matrix for city 0 0 4 1 3 2 0 0 0 0 0 0 2 0 2 1 0 1 0 0 0 0 1 0 1 0 matrix for city 1 0 2 1 0 0 3 0 0 0 0 0 1 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 matrix for city 2 -1 -1 -1 -1 -1 0 0 0 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 18) Happy Traveller You have won a contest sponsored by an airline. The prize is a ticket to travel around Canada, beginning in the most western point served by this airline, then traveling only from west to east until you reach the most eastern point served, and then coming back only from east to west until you reach the starting city. No city may be visited more than once, except for the starting city, which must be visited exactly twice (at the beginning and the end of the trip). You are not allowed to use any other airline or any other means of transportation. Given a list of cities served by the airline, and a list of direct flights between pairs of cities, find an itinerary which visits as many cities as possible and satisfies the above conditions beginning with the first city and visiting the last city on the list and returning to the first city. Different data sets are written in an ASCII input file. Each data set consists of: o in the first line: the number N of cities served by the airline and the number V of direct flights that will be listed. N will be a positive integer not larger than 100. V is any positive integer. o in each of the next N lines: a name of a city served by the airline. The names are ordered from west to east in the input file. That is, the i-th city is west of the j-th city if and only if i < j (There are no two cities in the same meridian). The name of each city is a string of, at most, 15 digits and/or characters of the Latin alphabet, for example: AGR34 or BEL4. (There are no spaces in the name of a city.) o in each of the next V lines: two names of cities, taken from the list of cities, separated by a blank space. If the pair city1 city2 appears in a line, it indicates that there exists a direct flight from city1 to city2 and also a direct flight from city2 to city1. Different data sets will be separated by an empty record (that is, a line containing only the end of line character). There will be no empty record after the last data set. The following example is stored in file ITIN.DAT. 8 9 5 5 Vancouver C1 Yellowknife C2 Edmonton C3 Calgary C4 Winnipeg C5 Toronto C5 C4 Montreal C2 C3 Halifax C3 C1 Vancouver Edmonton C4 C1 Vancouver Calgary C5 C2 Calgary Winnipeg Winnipeg Toronto Toronto Halifax Montreal Halifax Edmonton Montreal Edmonton Yellowknife Edmonton Calgary The input may be assumed correct. No checking is necessary. The solution found for each data set must be written to an ASCII output file, ITIN.SOL: in the first line, the total number of cities in the input data set; in the next line, the number M of different cities visited in the itinerary, and in the next M+1 lines the names of the cities, one per line, in the order in which they are visited. Note the first city visited must be the same as the last. Only one solution is required. If no solution is found for a data set, only two records for this data set must be written in ITIN.SOL, the first one giving the total number of cities, and the second one saying: "NO SOLUTION." A possible solution for the above example: 8 5 7 NO SOLUTION Vancouver Edmonton Montreal Halifax Toronto Winnipeg Calgary Vancouver 19) ARITHMETIC PROGRESSIONS An arithmetic progression is of the form a, a+b, a+2b....., a+nb where n=0,1,2,3...Assume a and b are non-negative integers (0,1,2,3,....). Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p^2 + q^2 (where p and q are non-negative integers). As input, your program should accept the length of progressions N to search for and an upper bound M to limit the search to the bisquares in the range from 0 to M. Each line of the input file ARITH.DAT contains N M. Assume M <=10,000. Sample Run ARITH.DAT 8 200 10 100 ARITH.SOL Arithmetic progressions of length 8 taken from bisquares within the range from 0 to 200: Difference of 12: 1 13 25 37 49 61 73 85 13 25 37 49 61 73 85 97 25 37 49 61 73 85 97 109 37 49 61 73 85 97 109 121 Difference of 24: 1 25 49 73 97 121 145 169 2 26 50 74 98 122 146 170 25 49 73 97 121 145 169 193 26 50 74 98 122 146 170 194 20) MOTHER'S MILK Farmer John has three milking buckets of capacity A, B, and C quarts. Each of the numbers A, B, and C is an integer from 1 through 15, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out. Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty. Sample Runs: Enter A B C: 8 9 10 Answer: 1 2 8 9 10 Enter A B C: 2 5 10 Answer: 5 6 7 8 9 10 21) HOME ON THE RANGE Farmer John grazes his cows on a large, square field N miles on a side (because, for some reason, his cows will only graze on precisely square land segments). Regrettably, the cows have ravaged some of the land (always in 1 mile square increments). FJ needs to map the remaining squares on which his cows can graze (in these larger squares, no 1x1 mile segments are ravaged). Your first job is to find any 4 x 4 mile grazing area in the supplied data. Your program must execute in less than 30 seconds. Your second job is to count up all the various remaining square grazing areas within the supplied dataset and report the number of square grazing areas (of all existing sizes) remaining. Of course, grazing areas may overlap for purposes of this report. Your program must run in under one minute for datasets up to 20 miles on a side. Be sure to read and understand the example below. Your third job is to create the same report as the second job -- but for datasets up to 250 miles on a side. Your program must run in under two minutes. The input data is found in files PROB3A.DAT, PROB3B.dat, ..., etc. Repeatedly ask for name of the input dataset so your program is easily tested. The first line is the number of miles on one side of the square. Subsequent lines give the map of the fields (0 means 'ravaged'; 1 means 'ready to eat'), one row at a time (no extra blanks in the input, just 1's and 0's and line separators). See 6x6 example below. Name your programs PROB3A.xxx, PROB3B.xxx, and PROB3C.xxx (where xxx is the appropriate filename extensioin). Input Dataset PROB3A.DAT: 6 101111 001111 111111 001111 101101 111001 Program Executions: Part 1: Input Dataset: PROB3A.DAT 4x4 is located at row 1 column 3 Part 2: Input Dataset: PROB3A.DAT Squares: 2:10 3:4 4:1 Part 3: Input Dataset: PROB3A.DAT Squares: 2:10 3:4 4:1 [executes very quickly] There are 8 progressions. Arithmetic progressions of length 10 taken from bisquares within the range from 0 to 1000: Difference of 12: 1 13 25 37 49 61 73 85 97 109 13 25 37 49 61 73 85 97 109 121 Difference of 24: 2 26 50 74 98 122 146 170 194 218 26 50 74 98 122 146 170 194 218 242 101 125 149 173 197 221 245 269 293 317 761 785 809 833 857 881 905 929 953 977 Difference of 36: 421 457 493 529 565 601 637 673 709 745 Difference of 48: 4 52 100 148 196 244 292 340 388 436 52 100 148 196 244 292 340 388 436 484 202 250 298 346 394 442 490 538 586 634 Difference of 60: 5 65 125 185 245 305 365 425 485 545 65 125 185 245 305 365 425 485 545 605 Difference of 72: 29 101 173 245 317 389 461 533 605 677 Difference of 84: 29 113 197 281 365 449 533 617 701 785 37 121 205 289 373 457 541 625 709 793 73 157 241 325 409 493 577 661 745 829 121 205 289 373 457 541 625 709 793 877 205 289 373 457 541 625 709 793 877 961 Difference of 96: 8 104 200 296 392 488 584 680 776 872 104 200 296 392 488 584 680 776 872 968 Difference of 108: 9 117 225 333 441 549 657 765 873 981 There are 21 progressions 22) 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 23) TELECOWMUNICATION Farmer John's cows like to keep in touch via email so they have created a network of cowputers so that they can intercowmunicate. These machines route email so that if there exists a sequence of cowputers a1, a2, ..., a(n) such that a1 is connected to a2, a2 is connected to a3, and so on then a1 and a(n) can send email to one another. Unfortunately, a cow will occasionally step on a cowputer or Farmer John will drive over it, and the machine will stop working. This means that the cowputer can no longer route email, so connections to and from that cowputer are no longer usable. Two of the most cowmunicative cows are pondering the minimum number of these accidents that can occur before they can no longer use their two favorite cowputers to send email to each other. Write a program to calculate this minimal value for them, and to calculate a set of machines that corresponds to this minimum. For example the network: 1* / 3 - 2* shows 3 cowputers connected with 2 lines and we want to send messages between 1 with 2. Direct lines connect 1 3 and 2 3. If cowputer 3 is down, them there is no way to get a message from 1 to 2. INPUT The first line of a network will consist of four integers: n m a b. The first number, n, is the number of cowputers that are on the network. The second number, m, is the number of connections between pairs of cowputers. The last two numbers, a and b, are the id numbers (1..n) of the cowputers that the questioning cows are using. The subsequent m lines will be pairs of cowputers that have connections between them. The ID numbers are in the range 1..n. The network shown above is represented as: Input 3 2 1 2 1 3 2 3 There will be no more than 40 cowputers. Each connection is unique and two-way (if c1 is connected to c2, then c2 is connected to c1). There can be at most one wire between any two given cowputers. For this problem, terminals a and b will NOT have a direct connection between them. The input file is named INPUT.C3. The input file may consist of several networks. The end of the file will be shown by a line reading: 0 0 0 0 OUTPUT For each network, three lines of output will be generated. The first line will read "Network #n", where n is the data set number. The second line is the minimum number of connections that can be down before terminals a & b are no longer connected. The third line is a list of cowputers of minimal length that will cause a & b to no longer be connected, separated by spaces. Note that a & b cannot go down. Name the output file OUT.C3. SAMPLE INPUT 3 2 1 2 1 3 2 3 8 14 1 2 1 3 1 6 1 7 1 8 2 3 2 4 2 5 2 6 2 7 3 6 4 5 4 7 4 8 7 8 0 0 0 0 SAMPLE OUTPUT Network #1 1 3 Network #2 4 3 4 6 7 (also correct is 3 6 7 8) Test run the following cases: Test Case C3.1 3 2 1 2 1 3 2 3 8 14 1 2 1 3 1 6 1 7 1 8 2 3 2 4 2 5 2 6 2 7 3 6 4 5 4 7 4 8 7 8 0 0 0 0 Test Case C3.2 20 26 1 2 1 9 1 17 1 19 2 6 2 9 2 14 3 15 3 16 3 18 4 8 5 6 5 7 5 12 5 17 6 7 6 19 7 13 7 14 7 15 9 12 9 14 10 14 11 12 12 17 13 15 15 17 10 12 1 2 1 3 1 5 1 7 1 9 2 4 2 6 2 8 2 10 3 4 5 6 7 8 9 10 0 0 0 0 Test Case C3.3 40 76 1 2 1 6 1 11 1 12 1 19 1 31 1 33 1 35 2 3 2 4 2 17 2 20 2 33 3 4 3 11 3 36 4 37 5 9 6 8 6 9 6 21 6 22 6 27 6 32 6 35 6 36 7 19 7 24 8 10 8 11 8 20 8 25 8 28 9 10 10 12 11 14 11 20 12 14 12 15 12 28 12 39 13 21 13 36 14 15 14 18 14 36 14 39 15 30 15 33 16 17 16 21 16 37 17 18 17 26 17 28 17 36 19 26 21 28 21 37 22 24 22 29 22 31 23 24 24 30 27 29 27 31 27 40 29 31 30 32 30 40 32 34 32 37 34 39 35 40 36 37 36 40 38 39 0 0 0 0 Results: Test run the following cases: Test Case 1 3 2 1 2 1 3 2 3 8 14 1 2 1 3 1 6 1 7 1 8 2 3 2 4 2 5 2 6 2 7 3 6 4 5 4 7 4 8 7 8 0 0 0 0 answer 1 Network 1 1 3 Network 2 2 1 2 Test Case 2 20 26 1 2 1 9 1 17 1 19 2 6 2 9 2 14 3 15 3 16 3 18 4 8 5 6 5 7 5 12 5 17 6 7 6 19 7 13 7 14 7 15 9 12 9 14 10 14 11 12 12 17 13 15 15 17 10 12 1 2 1 3 1 5 1 7 1 9 2 4 2 6 2 8 2 10 3 4 5 6 7 8 9 10 0 0 0 0 answer 2: Network 1 3 6 7 9, 6 9 14, 6 9 17, or 9 17 19 Network 2 4 (3/4) (5/6) (7/8) (9/10) (one from each) Test Case 3 40 76 1 2 1 6 1 11 1 12 1 19 1 31 1 33 1 35 2 3 2 4 2 17 2 20 2 33 3 4 3 11 3 36 4 37 5 9 6 8 6 9 6 21 6 22 6 27 6 32 6 35 6 36 7 19 7 24 8 10 8 11 8 20 8 25 8 28 9 10 10 12 11 14 11 20 12 14 12 15 12 28 12 39 13 21 13 36 14 15 14 18 14 36 14 39 15 30 15 33 16 17 16 21 16 37 17 18 17 26 17 28 17 36 19 26 21 28 21 37 22 24 22 29 22 31 23 24 24 30 27 29 27 31 27 40 29 31 30 32 30 40 32 34 32 37 34 39 35 40 36 37 36 40 38 39 0 0 0 0 answer 3 5 3 4 17 20 33 or 3 17 20 33 37 test case 4: 9 12 1 2 1 3 1 4 1 5 2 6 2 7 2 8 3 9 4 9 5 9 6 9 7 9 8 9 0 0 0 0 Answer 4: 1 9 test case 5: 20 120 1 2 1 3 1 6 1 8 1 9 1 10 1 12 1 15 1 17 1 19 2 3 2 4 2 5 2 6 2 7 2 8 2 11 2 14 2 15 2 16 2 17 2 19 2 20 3 5 3 6 3 7 3 8 3 14 3 16 3 17 3 18 3 20 4 5 4 8 4 9 4 10 4 11 4 12 4 13 4 15 4 16 4 17 4 18 4 19 5 6 5 8 5 11 5 12 5 13 5 15 5 16 5 18 5 20 6 7 6 8 6 11 6 12 6 13 6 16 6 17 6 18 6 19 6 20 7 8 7 11 7 12 7 13 7 15 7 19 7 20 8 11 8 12 8 13 8 14 8 15 8 16 8 18 9 10 9 12 9 16 9 20 10 11 10 12 10 13 10 14 10 15 10 16 10 17 11 12 11 13 11 14 11 17 11 18 11 19 11 20 12 13 12 14 12 16 12 17 12 18 12 19 13 17 13 19 13 20 14 16 14 18 14 19 14 20 15 16 15 18 15 19 16 17 16 18 16 19 16 20 17 18 17 19 17 20 18 19 18 20 19 20 0 0 0 0 Answer 5: 9 3 6 8 9 10 12 15 17 19 test case 6: 20 77 1 2 1 14 1 17 1 20 2 3 2 11 2 12 2 13 2 16 3 5 3 6 3 8 3 9 3 11 3 14 3 15 3 20 4 5 4 6 4 12 4 13 4 14 4 15 4 18 5 11 5 12 5 13 5 15 5 16 5 19 5 20 6 7 6 13 6 14 6 15 6 16 6 17 7 9 7 10 7 13 7 14 7 15 7 20 8 9 8 10 8 11 8 17 8 19 8 20 9 10 9 11 9 12 9 13 9 14 9 17 9 18 9 19 9 20 10 11 10 13 10 15 10 18 11 13 11 14 11 15 11 17 11 18 11 19 12 18 13 14 13 16 14 18 15 18 15 20 16 17 16 18 17 18 18 19 0 0 0 0 Answer 6: 3 14 17 20 test case 7: 40 170 1 2 1 10 1 11 1 16 1 30 1 31 1 33 1 34 1 36 2 4 2 6 2 9 2 12 2 13 2 14 2 15 2 16 2 19 2 20 2 22 2 25 2 26 2 28 2 30 2 33 3 5 3 8 3 15 3 16 3 20 3 21 3 28 3 32 3 35 3 37 3 39 3 40 4 14 4 17 4 19 4 22 4 25 4 27 4 30 4 37 5 13 5 29 5 35 5 36 5 40 6 14 6 24 6 31 6 35 6 40 7 8 7 19 7 20 7 28 7 32 7 40 8 12 8 14 8 23 8 26 8 30 8 32 9 15 9 20 9 24 9 26 9 27 9 28 9 31 9 34 9 38 10 24 10 26 10 30 10 37 10 39 11 16 11 26 11 30 11 40 12 17 12 22 12 23 12 26 12 27 12 28 12 29 12 30 12 35 12 36 13 16 13 22 13 24 13 25 14 19 14 31 14 36 14 37 15 26 15 30 15 35 15 39 16 17 16 21 16 25 16 29 16 30 16 38 17 18 17 21 17 27 17 34 17 36 17 40 18 20 18 32 19 20 19 26 19 38 20 22 20 26 20 28 20 32 20 33 20 38 20 39 21 23 21 29 22 23 22 31 22 33 22 38 23 24 23 31 23 37 23 38 24 28 24 32 24 34 25 27 25 34 25 37 25 40 26 27 26 32 26 36 26 40 27 37 27 38 28 32 28 39 29 31 29 37 30 35 30 37 30 39 32 33 32 38 32 39 33 34 33 40 34 36 34 39 36 37 36 40 38 39 0 0 0 0 answer 7: 8 10 11 16 30 31 33 34 36 test case 8: 40 338 1 2 1 3 2 4 1 6 2 7 1 9 2 10 1 12 2 13 1 15 2 16 1 18 2 19 1 21 2 22 1 24 2 25 1 27 2 28 1 30 2 31 1 33 2 34 1 36 2 37 1 39 2 40 3 5 3 8 3 11 3 14 3 17 3 20 3 23 3 26 3 29 3 32 3 35 3 38 4 5 4 8 4 11 4 14 4 17 4 20 4 23 4 26 4 29 4 32 4 35 4 38 5 6 5 7 5 9 5 10 5 12 5 13 5 15 5 16 5 18 5 19 5 21 5 22 5 24 5 25 5 27 5 28 5 30 5 31 5 33 5 34 5 36 5 37 5 39 5 40 6 8 6 11 6 14 6 17 6 20 6 23 6 26 6 29 6 32 6 35 6 38 7 8 7 11 7 14 7 17 7 20 7 23 7 26 7 29 7 32 7 35 7 38 8 9 8 10 8 12 8 13 8 15 8 16 8 18 8 19 8 21 8 22 8 24 8 25 8 27 8 28 8 30 8 31 8 33 8 34 8 36 8 37 8 39 8 40 9 11 9 14 9 17 9 20 9 23 9 26 9 29 9 32 9 35 9 38 10 11 10 14 10 17 10 20 10 23 10 26 10 29 10 32 10 35 10 38 11 12 11 13 11 15 11 16 11 18 11 19 11 21 11 22 11 24 11 25 11 27 11 28 11 30 11 31 11 33 11 34 11 36 11 37 11 39 11 40 12 14 12 17 12 20 12 23 12 26 12 29 12 32 12 35 12 38 13 14 13 17 13 20 13 23 13 26 13 29 13 32 13 35 13 38 14 15 14 16 14 18 14 19 14 21 14 22 14 24 14 25 14 27 14 28 14 30 14 31 14 33 14 34 14 36 14 37 14 39 14 40 15 17 15 20 15 23 15 26 15 29 15 32 15 35 15 38 16 17 16 20 16 23 16 26 16 29 16 32 16 35 16 38 17 18 17 19 17 21 17 22 17 24 17 25 17 27 17 28 17 30 17 31 17 33 17 34 17 36 17 37 17 39 17 40 18 20 18 23 18 26 18 29 18 32 18 35 18 38 19 20 19 23 19 26 19 29 19 32 19 35 19 38 20 21 20 22 20 24 20 25 20 27 20 28 20 30 20 31 20 33 20 34 20 36 20 37 20 39 20 40 21 23 21 26 21 29 21 32 21 35 21 38 22 23 22 26 22 29 22 32 22 35 22 38 23 24 23 25 23 27 23 28 23 30 23 31 23 33 23 34 23 36 23 37 23 39 23 40 24 26 24 29 24 32 24 35 24 38 25 26 25 29 25 32 25 35 25 38 26 27 26 28 26 30 26 31 26 33 26 34 26 36 26 37 26 39 26 40 27 29 27 32 27 35 27 38 28 29 28 32 28 35 28 38 29 30 29 31 29 33 29 34 29 36 29 37 29 39 29 40 30 32 30 35 30 38 31 32 31 35 31 38 32 33 32 34 32 36 32 37 32 39 32 40 33 35 33 38 34 35 34 38 35 36 35 37 35 39 35 40 36 38 37 38 38 39 38 40 0 0 0 0 answer 8 12 5 8 11 14 17 20 23 26 29 32 35 38