| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 2126 | Picnic Planning |
|
| 2127 | Sharing Chocolate |
|
| 2128 | Schedule Pairs of Jobs |
|
| 2129 | Lots of Sunlight |
|
| 2130 | March of the Penguins |
|
Description
The Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for an Annual Contortionists Meeting at a local park. However, the brothers are not only tight with regard to cramped quarters, but with money as well, so they try to find the way to get everyone to the party which minimizes the number of miles put on everyone's cars (thus saving gas, wear and tear, etc.). To this end they are willing to cram themselves into as few cars as necessary to minimize the total number of miles put on all their cars together. This often results in many brothers driving to one brother's house, leaving all but one car there and piling into the remaining one. There is a constraint at the park, however: the parking lot at the picnic site can only hold a limited number of cars, so that must be factored into the overall miserly calculation. Also, due to an entrance fee to the park, once any brother's car arrives at the park it is there to stay; he will not drop off his passengers and then leave to pick up other brothers. Now for your average circus clan, solving this problem is a challenge, so it is left to you to write a program to solve their milage minimization problem.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
Each case will consist of one problem instance. The first line will contain a single integer n indicating the number of highway connections between brothers or between brothers and the park. The next n lines will contain one connection per line, of the form name1 name2 dist, where name1 and name2 are either the names of two brothers or the word Park and a brother's name (in either order), and dist is the integer distance between them. These roads will all be 2-way roads, and dist will always be positive. The maximum number of brothers will be 20 and the maximum length of any name will be 10 characters. Following these n lines will be one final line containing an integer s which specifies the number of cars which can fit in the parking lot of the picnic site. You may assume that there is a path from every brother's house to the park and that a solution exists for each problem instance.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
For each test case, the output should consist of one line of the form
Total miles driven: xxx
where xxx is the total number of miles driven by all the brothers' cars.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Chocolate in its many forms is enjoyed by millions of people around the world every day. It is a truly universal candy available in virtually every country around the world.
You find that the only thing better than eating chocolate is to share it with friends. Unfortunately your friends are very picky and have different appetites: some would like more and others less of the chocolate that you offer them. You have found it increasingly difficult to determine whether their demands can be met. It is time to writte a program that solves the problem once and for all!
Your chocolate comes as a rectangular bar. The bar consists of same-sized rectangular pieces. To share the chocolate you may break one bar into two pieces along a division between rows or columns of the bar. You may then repeatedly break the resulting pieces in the same manner. Each of your friends insists on a getting a single rectangular portion of the chocolate that has a specified number of pieces. You are a little bit insistent as well: you will break up your bar only if all of it can be distributed to your friends, with none left over.
For exampla, Figure 9 shows one way that a chocolate bar consisting of 3 × 4 pieces can be split into 4 parts that contain 6, 3, 2, and 1 pieces respectively, by breanking it 3 times (This corresponds to the first sample input.)
Input
The input consists of multiple test cases each describing a chocolate bar to share. Each description starts with a line containing a single integer n (1 ≤ n ≤ 15), the number of parts in which the bar is supposed to be split. This is followed by a line containing two integers x and y (1 ≤ x, y ≤ 100), the dimensions of the chocolate bar. The next line contains n positive integers, giving the number of pieces that are supposed to be in each of the n parts. The input is terminated by a line containing the integer zero.
Output
For each test case, first display its case number. Then display whether it is possible to break the chocolate in the desired way: display ``Yes" if it is possible, and ``No" otherwise. Follow the format of the sample output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In a factory, there are n pairs of jobs, (pi , qi ), i = 1, 2, . . . , n, to be scheduled. Each job, pi or qi , needs 1 unit of time to process. All the jobs pi , i = 1, 2, . . . , n, must be scheduled before of all the jobs qi , i = 1, 2, . . . , n. The order among the jobs pi , i = 1, 2, . . . , n, as well as the order among the jobs qi , i = 1, 2, . . . , n, is not important. However, it is required that the time between pi and qi , measured from the starting time of pi to the starting time of qi , should be at most di , for i = 1, 2, . . . , n.
Given a sequence of n positive integers d1 , d2 , . . . , dn , we want to know whether these n pairs of jobs can be scheduled in the time interval [0, 2n] or not. We say that the problem is solvable if the n pairs of jobs can be scheduled in a time interval of length 2n units, in such a way that the time between pi and qi is at most di , for i = 1, 2, . . . , n.
For example, for n = 3, the sequence 1, 3, 5 is solvable, since we can schedule these 3 pairs of jobs as follows:
The sequence 3, 3, 4, 6 is also solvable, since we can schedule the jobs in the following way:
In this problem, you are going to design a computer program to schedule pairs of jobs with the above constraints.
Technical Specification
Assume that n < 16, and each di < 231 . For simplicity, assume that d1 ≤ d2 ≤ · · · ≤ dn , Σi=1~k di ≥ k2 for 1 ≤ k < n, and Σi=1~n di=n2. Note that, in this case, if the problem is solvable then the time between each pair of jobs (pi , qi ) is exactly di . If the solution is not unique, try to schedule the jobs so that the job qi with smaller index is finished as early as possible. For example, let the input requirements be 3 3 4 6. Then print out the solution p4 p1 p2 p3 q1 q2 q4 q3.
Input
Input file contains a set of test cases. Each test case contains a positive integer n, followed by n integers di, 1 ≤ i ≤ n. The last test case is followed by a line containing only one integer 0.
Output
Print the the job in ascending order of their starting time. Print one line for each test case and for readability print a space before each “p” and “q”. If the pairs of jobs cannot be scheduled, then print the message “no solution” in that line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Apartment Construction Management (ACM) has several new high-rise apartment buildings in suburban Shanghai. With the booming economy, ACM expects a considerable profit on apartment leases. Because their apartments receive more direct sunlight, the company claims that these are nicer than others in the area. No other buildings obstruct the sunlight path to apartments in ACM's tall buildings.
ACM wants to verify this claim by telling potential residents exactly how much sunlight a given apartment receives. To offer customers a representative sample of sunlight hours, the company wants to advertise the sunlight hours for April 6, 2005. On that day in Shanghai, the sun rises at 5:37 am, and sets at 6:17 pm.
As shown above, apartments are in a series of buildings aligned east to west. The last two digits of the apartment number identify the building, starting with 01 for the east-most building. The other digits encode the apartment floor, with 1 as the ground floor.
The sun rises in the east and travels at a constant radial speed across the sky, until setting in the west. The only shadows are created by buildings (i.e. each building can cast a shadow on one or more other buildings). An apartment is considered to receive sunlight when either its eastern or western exterior wall is fully covered in sunlight or when the sun is directly overhead.
Input
The input file contains a series of descriptions of apartment complexes. Each description starts with a line containing a single integer n (1 ≤ n < 100) that is the number of apartment buildings in the complex. The next line has two integers w, the width (in east-west direction), and h, each apartment's height in meters. Next is a list of integers m(1), d (1), m(2), d (2), ..., d (n - 1), m(n), where m(i) is the number of apartments in apartment building i, and d (i) is the distance, in meters, between the apartment building i and apartment building i + 1.
The apartment complex description is followed by an integer list of apartments to query for sunlight hours and is terminated by a zero. The input file is terminated by a line consisting of the integer zero.
Output
For each apartment complex description, output its number in the sequence of descriptions. Then for each query, output the corresponding sunlight hours, using the 24-hour time format. Truncate all times down to the nearest second. If the query refers to an apartment that does not exist, indicate that the apartment does not exist. Follow the format shown in the sample output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Somewhere near the south pole, a number of penguins are standing on a number of ice floes. Being social animals, the penguins would like to get together, all on the same floe. The penguins do not want to get wet, so they have use their limited jump distance to get together by jumping from piece to piece. However, temperatures have been high lately, and the floes are showing cracks, and they get damaged further by the force needed to jump to another floe. Fortunately the penguins are real experts on cracking ice floes, and know exactly how many times a penguin can jump off each floe before it disintegrates and disappears. Landing on an ice floe does not damage it. You have to help the penguins find all floes where they can meet.
A sample layout of ice floes with 3 penguins on them.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
- One line with the integer N (1 ≤ N ≤ 100) and a floating-point number D (0 ≤ D ≤ 100000), denoting the number of ice pieces and the maximum distance a penguin can jump.
- N lines, each line containing xi, yi, ni and mi, denoting for each ice piece its X and Y coordinate, the number of penguins on it and the maximum number of times a penguin can jump off this piece before it disappears (-10000 ≤ xi, yi ≤ 10000, 0 ≤ ni ≤ 10, 1 ≤ mi ≤ 200).
Output
Per testcase:
- One line containing a space-separated list of 0-based indices of the pieces on which all penguins can meet. If no such piece exists, output a line with the single number -1.