2009 World Finals hosted by KTH CPC 2009 ou acm progratmimilg牌IM|m Problem a A Careful Approach Input: approach If you think participating in a programming contest is stressful, imagine being an air traffic controller. With human lives at stake, an air traffic controller has to focus on tasks while working under constantly changing conditions as well as dealing with unforeseen events Consider the task of scheduling the airplanes that are landing at an airport. Incoming airplanes report their positions, directions, and speeds, and then the controller has to devise a landing schedule that brings all airplanes safely to the ground. Generally, the more time there is between successive landings, the""safer"a landing schedule is. This extra time gives pilots the opportunity to react to changing weather and other surprises Luckily, part of this scheduling task can be automated -this is where you come in. You will be given scenarios of airplane landings. Each airplane has a time window during which it can safely land. You must compute an order for landing all airplanes that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible. For example, if three airplanes land at 10: 00am, 10: 05am, and 10: 15am, then the smallest gap is five minutes, which occurs between the first two airplanes. Not all gaps have to be the same, but the smallest gap hould be as large as possible The input file contains several test cases consisting of descriptions of landing scenarios. Each test case starts with a line containing a single integer n(2<ns8), which is the number of airplanes in the scenario. This is followed by n lines, each containing two integers a, bi, which give the beginning and end of the closed interval [ai, bi] during which the i plane can land safely. The numbers a; and b, are specified in minutes and satisfy 0≤a1≤b≤1440 The input is terminated with a line containing the single integer zero Outpul For each test case in the input, print its case number(starting with 1)followed by the minimum achievable time gap between successive landings. Print the time split into minutes and seconds, rounded to the closest second Follow the format of the sample output Sample Input Output for the Sample Input Case1:7:30 010 Case2:20:00 1015 010
Problem A A Careful Approach Input: approach.in If you think participating in a programming contest is stressful, imagine being an air traffic controller. With human lives at stake, an air traffic controller has to focus on tasks while working under constantly changing conditions as well as dealing with unforeseen events. Consider the task of scheduling the airplanes that are landing at an airport. Incoming airplanes report their positions, directions, and speeds, and then the controller has to devise a landing schedule that brings all airplanes safely to the ground. Generally, the more time there is between successive landings, the “safer” a landing schedule is. This extra time gives pilots the opportunity to react to changing weather and other surprises. Luckily, part of this scheduling task can be automated – this is where you come in. You will be given scenarios of airplane landings. Each airplane has a time window during which it can safely land. You must compute an order for landing all airplanes that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible. For example, if three airplanes land at 10:00am, 10:05am, and 10:15am, then the smallest gap is five minutes, which occurs between the first two airplanes. Not all gaps have to be the same, but the smallest gap should be as large as possible. Input The input file contains several test cases consisting of descriptions of landing scenarios. Each test case starts with a line containing a single integer n (2 ≤ n ≤ 8), which is the number of airplanes in the scenario. This is followed by n lines, each containing two integers ai, bi, which give the beginning and end of the closed interval [ai, bi] during which the i th plane can land safely. The numbers ai and bi are specified in minutes and satisfy 0 ≤ ai ≤ bi ≤ 1440. The input is terminated with a line containing the single integer zero. Output For each test case in the input, print its case number (starting with 1) followed by the minimum achievable time gap between successive landings. Print the time split into minutes and seconds, rounded to the closest second. Follow the format of the sample output. Sample Input Output for the Sample Input 3 0 10 5 15 10 15 2 0 10 10 20 0 Case 1: 7:30 Case 2: 20:00
This page intentionally left blank
This page intentionally left blank
2009 World Finals hosted by Kth CPC 2009 以acm International Collegiate Programming Contest Problem b My Bad Input file: bad. in A logic circuit maps its input through various gates to its output with no feedback loops in the circuit. The input and output are an ordered set of logical values, represented here by ones and zeros. The circuits we consider are comprised of and gates(which output I only when their two inputs are both 1), or gates(which output I when one or both of their inputs are 1), exclusive or(xor) gates(which output 1 only when exactly one of the two inputs is 1), and not gates( which output the complement of their single input). The figures below show two Figure 1: Circuit with 2 gates Figure 2: Circuit with 4 gates Unfortunately, real gates sometimes fail. Although the failures may occur in many different ways, this problem limits attention to gates that fail in one of three ways: 1)al ways inverting the correct output, 2)always yielding 0, and 3)always yielding 1. In the circuits for this problem, at most one gate will fail You must write a program that analyzes a circuit and a number of observations of its input and output to see if the circuit is performing correctly or incorrectly. If at least one set of inputs produces the wrong output, your program must also attempt to determine the unique failing gate and the way in which this gate is failing. This may not always be possible Input The input consists of multiple test cases, each representing a circuit with input and output descriptions. Each test case has the following parts in order 1. A line containing three positive integers giving the number of inputs(Ns8), the number of gates(Gs19) nd the number of outputs(Us19)in the 2. One line of input for each gate. The first line describes gate gr. If there are several gates, the next line describes gate g2, and so on. Each of these lines contains the gate type(a=and, n=not, o=or, and x=exclusive or), and identification of the input(s)to the gate. Gate input comes from the circuit inputs (i1, i2,.or the output of another gate(g1, g 2,. 3. A line containing the numbers of the gates connected to the U outputs u, u2,.. For example, if there are three outputs, and uy comes from gs, u2 from gl, and us from ga, then the line would contain: 5 1 4 4. A line containing an integer which is the number of observations of the circuits behavior(B) 5. Finally B lines, each containing N values(ones and zeros) giving the observed input values and U values giving the corresponding observed output values. No two observations have the same input values Consecutive entries on any line of the input are separated by a single space. The input is terminated with a line containing three zeros
Problem B My Bad Input file: bad.in A logic circuit maps its input through various gates to its output with no feedback loops in the circuit. The input and output are an ordered set of logical values, represented here by ones and zeros. The circuits we consider are comprised of and gates (which output 1 only when their two inputs are both 1), or gates (which output 1 when one or both of their inputs are 1), exclusive or (xor) gates (which output 1 only when exactly one of the two inputs is 1), and not gates (which output the complement of their single input). The figures below show two circuits. or not i1 g2 i2 g1 o1 Figure 1: Circuit with 2 gates Figure 2: Circuit with 4 gates Unfortunately, real gates sometimes fail. Although the failures may occur in many different ways, this problem limits attention to gates that fail in one of three ways: 1) always inverting the correct output, 2) always yielding 0, and 3) always yielding 1. In the circuits for this problem, at most one gate will fail. You must write a program that analyzes a circuit and a number of observations of its input and output to see if the circuit is performing correctly or incorrectly. If at least one set of inputs produces the wrong output, your program must also attempt to determine the unique failing gate and the way in which this gate is failing. This may not always be possible. Input The input consists of multiple test cases, each representing a circuit with input and output descriptions. Each test case has the following parts in order. 1. A line containing three positive integers giving the number of inputs (N ≤ 8), the number of gates (G ≤ 19), and the number of outputs (U ≤ 19) in the circuit. 2. One line of input for each gate. The first line describes gate g1. If there are several gates, the next line describes gate g2, and so on. Each of these lines contains the gate type (a = and, n = not, o = or, and x = exclusive or), and identification of the input(s) to the gate. Gate input comes from the circuit inputs (i1, i2, …) or the output of another gate (g1, g2, …). 3. A line containing the numbers of the gates connected to the U outputs u1, u2, …. For example, if there are three outputs, and u1 comes from g5, u2 from g1, and u3 from g4, then the line would contain: 5 1 4 4. A line containing an integer which is the number of observations of the circuit’s behavior (B). 5. Finally B lines, each containing N values (ones and zeros) giving the observed input values and U values giving the corresponding observed output values. No two observations have the same input values. Consecutive entries on any line of the input are separated by a single space. The input is terminated with a line containing three zeros
For each circuit in the input, print its case number(starting with 1), followed by a colon and a blank, and then the circuit analysis, which will be one of the following(with replaced by the appropriate gate number) i output inverte Gate is failing; output stuck at 0 Gate is failing output stuck at 1 Unable to totally classify the failure The circuits pictured in Figure I and Figure 2 are used in the first and last sample test cases Sample Input Output for the Sample Input Case 1: No faults detected fy the fai Case 3: Gate l is failing; output stuck at Case 4: Gate l is failing; output inverted Case 5: g failing; output stuck at 0 100 11 1i2 011i 0 3 104 n 4123 3 0 0101 0 11100 00001
Output For each circuit in the input, print its case number (starting with 1), followed by a colon and a blank, and then the circuit analysis, which will be one of the following (with # replaced by the appropriate gate number): No faults detected Gate # is failing; output inverted Gate # is failing; output stuck at 0 Gate # is failing; output stuck at 1 Unable to totally classify the failure The circuits pictured in Figure 1 and Figure 2 are used in the first and last sample test cases. Sample Input Output for the Sample Input 2 2 1 o i1 i2 n g1 2 2 1 0 0 0 0 1 2 1 1 a i1 i2 1 1 1 0 1 2 1 1 a i1 i2 1 2 1 0 1 1 1 1 1 1 1 n i1 1 2 1 1 0 0 3 4 4 n g4 a i1 i2 o i2 i3 x i3 i1 2 3 4 1 4 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 Case 1: No faults detected Case 2: Unable to totally classify the failure Case 3: Gate 1 is failing; output stuck at 1 Case 4: Gate 1 is failing; output inverted Case 5: Gate 2 is failing; output stuck at 0
2009 World Finals hosted by KTH CPC 2009 以acm International Collegiate Programming Contest 工EMmm Problem c The return of carl Input file: carl. in Carl the ant is back! When we last left him(Problem A, 2004 World Finals), Carl was a little mixed-up, always taking strange, zigzag paths when traveling. But now, Carl has straightened out his life- literally. He now al ways takes the straightest, shortest path between any pair of points. This sounds simple, except for one small thing: Carl now spends most of his time on a paperweight in the shape of a regular octahedron. You may recall that an octahedron is one of the five Platonic solids and consists of eight equilateral triangles, as shown in Figure 3: Regular octahedron Carl has an innate(some say in-ant)ability to always take the shortest path when going from any starting point to any destination point on the paperweight. Your job is to verify this by determining the length of the shortest path when given two such points, not necessarily distinct. Input The input contains multiple test cases. Each test case consists of four integers 01, 91, 02 and o2, where 0 s0i<360 and0 soi s 180. The first two are the spherical coordinates of the start point, and the last two the spherical coordinates of the destination point. As shown in Figure 3, 0, is the azimuth and i is the zenith angle, both of them given in degrees The input is terminated by a line containing four negative ones The paperweight is fixed for all test cases as follows: the octahedron is centered on the origin and each vertex any supporting mechanisms that may be necessary to hold the paperweight in the correct posie ero and ignore lies on one of the axes. Every edge is exactly 10 cm long. You should suppose that Carls size is ze
Problem C The Return of Carl Input file: carl.in Carl the ant is back! When we last left him (Problem A, 2004 World Finals), Carl was a little mixed-up, always taking strange, zigzag paths when traveling. But now, Carl has straightened out his life – literally. He now always takes the straightest, shortest path between any pair of points. This sounds simple, except for one small thing: Carl now spends most of his time on a paperweight in the shape of a regular octahedron. You may recall that an octahedron is one of the five Platonic solids and consists of eight equilateral triangles, as shown in Figure 3. Figure 3: Regular octahedron Carl has an innate (some say in-ant) ability to always take the shortest path when going from any starting point to any destination point on the paperweight. Your job is to verify this by determining the length of the shortest path when given two such points, not necessarily distinct. Input The input contains multiple test cases. Each test case consists of four integers θ1, φ1, θ2 and φ2, where 0 ≤ θi < 360 and 0 ≤ φi ≤ 180. The first two are the spherical coordinates of the start point, and the last two are the spherical coordinates of the destination point. As shown in Figure 3, θi is the azimuth and φi is the zenith angle, both of them given in degrees. The input is terminated by a line containing four negative ones. The paperweight is fixed for all test cases as follows: the octahedron is centered on the origin and each vertex lies on one of the axes. Every edge is exactly 10 cm long. You should suppose that Carl’s size is zero and ignore any supporting mechanisms that may be necessary to hold the paperweight in the correct position
For each test case, print the case number(starting with 1)and the length in centimeters of the shortest path from the start point to the destination point, rounded to the nearest thousandth. Follow the format of the sample Sample Input Output for the Sample Input 0909090 Case1:10.000 Case2:8.660 000180 Case3:17.321
Output For each test case, print the case number (starting with 1) and the length in centimeters of the shortest path from the start point to the destination point, rounded to the nearest thousandth. Follow the format of the sample output. Sample Input Output for the Sample Input 0 90 90 90 0 90 90 45 0 0 0 180 -1 -1 -1 -1 Case 1: 10.000 Case 2: 8.660 Case 3: 17.321
2009 World Finals hosted by KTH CPC 2009 以acm International Collegiate Programming Contest Problem d Conduit Packing Input File: conduit in Allied Conduit Manufacturing(ACM)makes metal conduit tubes with round cross-sections that enclose many different types of wires. The circular cross-section of a wire can have a diameter up to 20 millimeters(20000 micrometers). ACM needs a program to compute the minimum diameter of a conduit that can hold 4 wires with ified dia rS Figure 4 shows examples of fitting four wires of different sizes into conduits of minimum diameters Figure 4: Fitting wires inside conduits Your program must take the diameters of wires and determine the minimum inside diameter of the conduit that can hold the wires Input The input file contains several test cases. Each test case consists of a line with four integers, dl, d2, d3, and d, the diameters of the wires in micrometers. The integers satisfy20000≥d1≥d≥d≥d4>0. The last test case is followed by a line containing a single integer zero Outpt or each test case, print the number of the test case(starting with 1)followed by the minimum conduit diameter in micrometers, rounded to the nearest integer. Follow the format of the sample output Output for the sample Input 10000100001000010000 Case1:24142 1000010000100003000 Case2:21547 120001200036003600 Case3:24000
Problem D Conduit Packing Input File: conduit.in Allied Conduit Manufacturing (ACM) makes metal conduit tubes with round cross-sections that enclose many different types of wires. The circular cross-section of a wire can have a diameter up to 20 millimeters (20000 micrometers). ACM needs a program to compute the minimum diameter of a conduit that can hold 4 wires with specified diameters. Figure 4 shows examples of fitting four wires of different sizes into conduits of minimum diameters. Figure 4: Fitting wires inside conduits Your program must take the diameters of wires and determine the minimum inside diameter of the conduit that can hold the wires. Input The input file contains several test cases. Each test case consists of a line with four integers, d1, d2, d3, and d4, which are the diameters of the wires in micrometers. The integers satisfy 20000 ≥ d1 ≥ d2 ≥ d3 ≥ d4 > 0. The last test case is followed by a line containing a single integer zero. Output For each test case, print the number of the test case (starting with 1) followed by the minimum conduit diameter in micrometers, rounded to the nearest integer. Follow the format of the sample output. Sample Input Output for the Sample Input 10000 10000 10000 10000 10000 10000 10000 3000 12000 12000 3600 3600 0 Case 1: 24142 Case 2: 21547 Case 3: 24000
This page intentionally left blank
This page intentionally left blank
2009 World Finals hosted by Kth CPC 2009 以acm International Collegiate Programming Contest Problem e Fare and balanced Input fare in landling traffic congestion is a difficult challenge for young urban planners. Millions of drivers, each with different goals and each making independent choices, combine to form a complex system with sometimes predictable, sometimes chaotic behavior. As a devoted civil servant, you have been tasked with optimizing rush hour traffic over collections of roads All the roads lie between a residential area and a downtown business district. In the morning, each person living in the residential area drives a route to the business district. The morning commuter traffic on any particular road travels in only one direction, and no route has cycles(morning drivers do not backtrack) Each road takes a certain time to drive, so some routes are faster than others. Drivers are much more likely to choose the faster routes, leading to congestion on those roads. In order to balance the traffic as much as possible you are to add tolls to some roads so that the perceived"cost" of every route ends up the same. However, to avoid annoying drivers too much, you must not levy a toll on any driver twice, no matter which route he or she Figure 5 shows a collection of five roads that form routes from the residential area(at intersection 1)to the downtown business district(at intersection 4). The driving cost of each road is written in large blue font. The dotted arrows show the three possible routes from 1 to 4. Initially the costs of the routes are 10, 8 and 12. After adding a toll of cost 2 to the road connecting I and 4 and a toll of cost 4 to the road connecting 3 and 4, the cost of each route becomes 12 10+2=12 10+2 5+3+4=12 3+4 z 2) Figure 5: Roads connecting residential area at intersection 1 to business district at intersection 4 You must determine which roads should have tolls and how much each toll should be so that every route from start to finish has the same cost(driving time cost possible toll)and no route contains more than one toll road Additionally, the tolls should be chosen so as to minimize the final cost. In some settings, it might be impossible to impose tolls that satisfy the above conditions Input consists of several test cases. A test case starts with a line containing an integer N(2SN<50000), whicl is the number of road intersections, and r(I srs50000), which is the number of roads. Each of the next R lines contains three integers xh, yi, and c (Isx,ysN,IsCs1000), indicating that morning traffic takes road i from intersection x, to intersection y with a base driving time cost of cp. Intersection I is the starting residential
Problem E Fare and Balanced Input: fare.in Handling traffic congestion is a difficult challenge for young urban planners. Millions of drivers, each with different goals and each making independent choices, combine to form a complex system with sometimes predictable, sometimes chaotic behavior. As a devoted civil servant, you have been tasked with optimizing rushhour traffic over collections of roads. All the roads lie between a residential area and a downtown business district. In the morning, each person living in the residential area drives a route to the business district. The morning commuter traffic on any particular road travels in only one direction, and no route has cycles (morning drivers do not backtrack). Each road takes a certain time to drive, so some routes are faster than others. Drivers are much more likely to choose the faster routes, leading to congestion on those roads. In order to balance the traffic as much as possible, you are to add tolls to some roads so that the perceived “cost” of every route ends up the same. However, to avoid annoying drivers too much, you must not levy a toll on any driver twice, no matter which route he or she takes. Figure 5 shows a collection of five roads that form routes from the residential area (at intersection 1) to the downtown business district (at intersection 4). The driving cost of each road is written in large blue font. The dotted arrows show the three possible routes from 1 to 4. Initially the costs of the routes are 10, 8 and 12. After adding a toll of cost 2 to the road connecting 1 and 4 and a toll of cost 4 to the road connecting 3 and 4, the cost of each route becomes 12. Figure 5: Roads connecting residential area at intersection 1 to business district at intersection 4 You must determine which roads should have tolls and how much each toll should be so that every route from start to finish has the same cost (driving time cost + possible toll) and no route contains more than one toll road. Additionally, the tolls should be chosen so as to minimize the final cost. In some settings, it might be impossible to impose tolls that satisfy the above conditions. Input Input consists of several test cases. A test case starts with a line containing an integer N (2 ≤ N ≤ 50000), which is the number of road intersections, and R (1 ≤ R ≤ 50000), which is the number of roads. Each of the next R lines contains three integers xi, yi, and ci (1 ≤ xi, yi ≤ N, 1 ≤ ci ≤ 1000), indicating that morning traffic takes road i from intersection xi to intersection yi with a base driving time cost of ci. Intersection 1 is the starting residential
area, and intersection N is the goal business district. Roads are numbered from I to R in the given input order Every intersection is part of a route from I to N, and there are no cycles The last test case is followed by a line containing two zeros Output For each test case, print one line containing the case number(starting with 1), the number of roads to toll (1), and the final cost of every route. On the next Tlines, print the road number i and the positive cost of the toll to apply to that road. If there are multiple minimal cost solutions, any will do. If there are none, print No solution. Follow the format of the sample output Sample inpu Output for Sample Input 321 54 246 Case 2: No solution 410 34 231 232
area, and intersection N is the goal business district. Roads are numbered from 1 to R in the given input order. Every intersection is part of a route from 1 to N, and there are no cycles. The last test case is followed by a line containing two zeros. Output For each test case, print one line containing the case number (starting with 1), the number of roads to toll (T), and the final cost of every route. On the next T lines, print the road number i and the positive cost of the toll to apply to that road. If there are multiple minimal cost solutions, any will do. If there are none, print No solution. Follow the format of the sample output. Sample Input Output for Sample Input 4 5 1 3 5 3 2 1 2 4 6 1 4 10 3 4 3 3 4 1 2 1 1 2 2 2 3 1 2 3 2 0 0 Case 1: 2 12 4 2 5 4 Case 2: No solution
