Problem C
Stack of Cylinders
Suppose you launch a set of cylinders, with different radius, over a hill, in such a way they get stacked like in the figure.
Accordingly to the radius of the cylinders, only a subset will be connected forming a continuous path. In the example represented, this path is composed by cylinders 2, 3 and 6. Cylinder 2 is the path head and cylinder 6 is the path tail.
The enclosing distance d is measured from the left support point of the path head until the right point of the path tail.
Example of a stack of cylinders.
Problem
Given a sequence of cylinders, this problem consists in the evaluation of the enclosing distance and the sequence of cylinders that compose the continuous path. It is ensured that each cylinder can touch no more than one cylinder at its left and no more than one cylinder at its right.
Input
The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.
The input is a sequence of text lines, as follows.
The first text line contains the number NC (integer format) of cylinders. It is followed by a sequence of NC text lines containing, each line, a cylinder radius (integer or decimal format). The cylinder identifier is obtained from its series number in the sequence (starting at 1).
Note: the maximum number of cylinders is 100.
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.
The first text line contains one decimal number, rounded to one decimal digit, representing the enclosing distance.
The second line contains the number NP of cylinders that compose the continuous path and it is followed by NP lines containing, in the proper sequence, the identifiers of the cylinders in the continuous path.
Sample Input
7
3
25
35
5
4
32
4
Sample Output
183.1
3
2
3
6
Augusto Sousa, 2nd round of CPUP'04
(Concurso de Programa��o da Universidade do Porto 2004)
(Torneio Inter-Universit�rio de Programa��o, 2004, Round 3)
Problem A
Dividing Land
Once upon a time there existed a king that held the greatest fortune in the entire world. He had 4 sons and he loved them equally. The years passed and one day the king was dying. He decided then to give his kingdom equally to his four sons. Suppose that we represent the kingdom by set of connected squares. Some locations on a kingdom had special natural resources like gold, marked as 'G'. Other places whith no natural resources are marked with X. Here is a map of the kingdom:
XX
GG
GXXG
XXXX
The king wanted that each son had exactly the same number of squares, that all squares of the same son would be connected (vertically or horizontally) and that the shape of each son's terrain would be exactly the same, except for rotations or reflections.
He then asked all the wise men from the kingdom to find an answer for this problem and after months thinking they found the following solution (each son's terrain is indicated by a different number):
11
12
3224
3344
But if the terrain was different, could you find a solution? And if the resources were also different? And if he had a different number of children?
Problem
Your task it find if there exists a way to divide a determined terrain in N different parcels of terrain, each one exactly with the same shape (except for rotations and reflections) and the same set of natural resources.
Input
The input starts with a single number T indicating the number of test cases that follow.
Each test case starts with a line with three integer numbers L, C and N (1 ≤ L,C ≤ 10 and 1 ≤ N ≤ 5), indicating the number of lines and columns that the closest rectangle that could enclose the terrain has, and also the number N of sons that the king has.
Then follows L lines giving the map of the terrain where
· "#" indicates a square that does not belong to the kingdom
· "." means a square that belongs to the kingdom but has no natural resources
· "A-Z" (a single letter) represents a square that has a natural resource of type A-Z. (for example, G means tipe G).
The first sample input corresponds to the original map described earlier.
Output
For each test case output a single line saying only "Yes" if it is possible to divide the terrain in the specified conditions and "No" otherwise.
Sample Input
3
4 4 4
..##
GG##
G...
...G
4 4 4
..##
GG##
G...
...A
6 4 2
ABAB
CDCD
EFEF
ABAB
CDCD
EFEF
Sample Output
Yes
No
Yes
Pedro Ribeiro, 2nd round of CPUP'04
(Concurso de Programa��o da Universidade do Porto 2004)
(Torneio Inter-Universit�rio de Programa��o, 2004, Round 3)
(Concurso de Programa��o da Universidade do Porto 2004)
(Torneio Inter-Universit�rio de Programa��o, 2004, Round 3)
Problem E
Euro 2004
The European Football Championship is coming! From the 12th of June to the 4th of July, Portugal will be the sports center of the world. Everyone will do their best to make this event a memorable one.
However, an important detail is missing. The rules for the classification of the league stage have changed and everyone is a little bit confused. What would be really, really nice would be a computer program to calculate this classification, given the results of the game. Then it would also be possible to watch in real time the changes in the ranking! Here is how the classification is made:
- For a win 3 points will be awarded; for a tie, 1 point; for a defeat, 0 points
- For establishing the final places, the following criteria will be applied, in descending order of priority:
- Number of points
- Goal-Average (difference between goals scored and given)
- Number of wins (victories)
- Number of goals scored
So after the games are taken in account, this parameters are all calculated. Things get interesting when there is more than one team with the same number of points. In that case, a sub-league is considered. You must now imagine that only the games between the tied teams count, and see the new sub-classification. If that does not break the tie (in points) for all the teams, you must do a sub-sub-league for all the teams that are still tied, and so on. There is only one case when a sub-league should not be partitioned. That is when all the teams in that sub-league have the same number of points and obviously, the partition would give the exact same group of teams and parameters. In that cases, teams should be ranked according to the four parameters calculated for that sub-league. If the parameters are not sufficient, then the teams should be considered to be in the same place, and they should appear in alphabetical order.
Problem
Your task is to write a program that given the results of several games, calculates the classification of the teams using the sorting algorithm defined above.
Of course that knowing how good programmer you are, the organization has asked you to make a program that could calculate the classification of thousands of teams more than the ones that will be present in Euro'2004, in order to use the program in any situation they want.
Input
The first line of input contains an integer T which is the number of test cases that follow.
Each test case starts with a number G (1 ≤ G ≤ 10000) indicating the number of games to consider.
Then G lines follow, each one with the format "TEAM1 TEAM2 GOALS1 GOALS2", giving the result of a single game (TEAM1 scored GOALS1 goals and TEAM2 scored GOALS2). Team names are made only by lower-case letters and have a maximum length of 20.
It is not necessary that games between all the teams have been made. Of course that you should only calculate the classification based on the games that you were given. Also, some teams may play against each other more than one time.
To make the classification you should consider all the teams that played at least one game. You may assume that the number of teams is ≤ 10000
Output
The output for each test case consists of lines in the form "PLACE TEAM", in ascending order of place, where PLACE indicates the place the team got and TEAM is the name of the team. Remember that all teams that played at least one game must appear.
Output of different test cases should be separated by a single blank line.
See the example output for a more detailed explanation of how the classification was obtained on that particular cases.
Sample Input
3
6
portugal grecia 4 1
espanha russia 3 1
portugal russia 3 0
espanha grecia 1 2
portugal espanha 1 3
grecia russia 7 0
6
portugal grecia 4 1
espanha russia 1 3
portugal russia 3 0
espanha grecia 1 2
portugal espanha 1 3
grecia russia 7 0
1
brasil franca 0 0
Sample Output
1 portugal
2 espanha
3 grecia
4 russia
1 portugal
2 grecia
3 russia
4 espanha
1 brasil
1 franca
Explanation of Sample I/O
- First sample case:
Looking at the games, we see that "portugal", "espanha" and "grecia" made 6 points, and "russia" made 0 points (which automatically gives them the 4th place). A tie between the first three teams is achieved. A sub-league with only that three teams is then considered but in this sub-league all the three teams have 3 points. This tied group cannot be partitioned further and then the other parameters are considered. Since in that sub-league, "portugal" has the best goal-average, it achieves 1st place. Then comes "spain" (2nd goal-average) and finally "grecia". If necessary, the other parameters would have been taken in account.
- Second sample case:
Now, "portugal" and "grecia" are tied with 6 points, and "espanha" and "russia" have 3 points. The sub-league between "portugal" and "grecia" unties the two teams ("portugal" won against "grecia"), and in the same way the sub-league between "espanha" and "russia" unties them.
- Third sample case:
The only two teams tied the game, so they are equal in all parameters. They are in the same place and they appear in alphabetical order.
Pedro Ribeiro, 2nd round of CPUP'04
(Concurso de Programa��o da Universidade do Porto 2004)
(Torneio Inter-Universit�rio de Programa��o, 2004, Round 3) Problem F
ASCII Mandelbrot
The Mandelbrot set, named after Benoit Mandelbrot, is a fractal. Fractals are beautiful objects that display self-similarity at various scales. Magnifying a fractal reveals small-scale details similar to the large-scale characteristics. Although the Mandelbrot set is self-similar at magnified scales, the small scale details are not identical to the whole. In fact, the Mandelbrot set is infinitely complex. Yet the process of generating it is based on an extremely simple equation involving complex numbers.
The Mandelbrot set is a mathematical set, a collection of complex numbers. Remember that complex numbers have two parts: a real one and an imaginary one. The imaginary part is equal to a real number times a special number called i. For example, a valid complex number is 2.5+3i. The number i was invented because no real number can be squared (multiplied by itself) and result in a negative number. The number i is defined to be the square root of -1. So when you square an imaginary number you can get a negative number. For example, 3i squared is -9.
Real numbers can be represented on a one dimensional line called the real number line. Negative numbers like -2 are plotted to the left of zero and positive numbers like 2 are plotted to the right of zero. Any real number can be graphed on the real number line. 
Since complex numbers have two parts, a real one and an imaginary one, we need a second dimension to graph them. We simply add a vertical dimension to the real number line for the imaginary part. Since our graph is now two-dimensional, it is a plane, the complex number plane. We can graph any complex number on this plane. The dots on this graph represent the complex numbers: [2 + 1i], [-1.5 + 0.5i], [2 - 2i], [-0.5 - 0.5i], [0 + 1i], and [2 + 0i]. The Mandelbrot set is a set of complex numbers, so we graph it on the complex number plane. However, first we have to find many numbers that are part of the set. To do this we need a test that will determine if a given number is inside the set or outside the set. The test is based on the equation Z = Z2 + C. C represents a constant number, meaning that it does not change during the testing process. C is the number we are testing, the point on the complex plane that will be plotted when testing is complete. Z starts out as zero, but it changes as we repeatedly iterate this equation. With each iteration we create a new Z that is equal to the old Z squared plus the constant C. So the number Z keeps changing throughout the test.
We're not really interested in the actual value of Z as it changes, we just look at its magnitude. The magnitude of a number is its distance from zero.To calculate the magnitude of a complex number, we add the square of the number's distance from the x-axis (the horizontal real axis) to the square of the number's distance from the y-axis (the imaginary vertical axis) and take the square root of the result. As we iterate our equation, Z changes and so does its magnitude. The magnitude of Z will do one of two things. It will either stay equal to or below 2 forever, or it will eventually surpass two (strictly bigger than 2). Once the magnitude of Z surpasses 2, it will increase forever. In the first case, where the magnitude of Z stays small, the number we are testing is part of the Mandelbrot set. If the magnitude of Z eventually surpasses 2, the number is not part of the Mandelbrot set.
As we test many complex numbers we can graph the ones that are part of the Mandelbrot set on the complex number plane. If we plot thousands of points, an image of the set will appear, as illustrated in the figure in the upper right corner. We can add color to the image if we add colors to the points that are not inside the set, according to how many iterations were required before the magnitude of Z surpassed two.
To make exciting images of tiny parts of the Mandelbrot set, we just zoom in on it, trying to perceive its full infinite beauty.
Problem
Your task is to plot a region of the Mandelbrot set using only simple text, this is, only with ASCII characters.
Input
The first line of input contains an integer T which is the number of test cases that follow.
Each test case is given in a line with the following format:
"CHARS MINI MAXI PRECI MINR MAXR PRECR", where
- CHARS represents the set of chars to use in the plotting, always enclosed in quotes, and always with size 12 (the set of chars never includes quotes and spaces);
- MINI and MAXI are two real numbers representing the lower and upper bound of the imaginary part in the plot;
- MINR and MAXR are two real numbers representing the lower and upper bound of the real part in the plot;
- PRECI and PRECR are two real numbers representing the precision that the plot must have in what respects to imaginary and real part, respectively.
What you must do is to plot the following graph:
[MINI , MINR] [MINI , MINR+PRECR] (...)
[MINI+PRECI , MINR] [MINI+PRECI , MINR+PRECR] (...)
[MINI+2*PRECI, MINR] [MINI+2*PRECI, MINR+PRECR] (...)
(...) (...) (...)
(...) (...) [A,B]
where [A,B] are the last coordinates that are smaller or equal than [MAXI,MAXR].
Each one of this coordinates must be plotted as a single char. If one iteration was required before the magnitude of Z surpassed two, then the first char of CHARS is plotted, if two iterations are needed, then the second char is plotted and so on until 12 iterations. If after twelve iterations the magnitude of Z has not surpassed Z, then the char " " (space) is plotted.
Output
The output consists of the required number of lines and columns to plot the specified region of the Mandelbrot set. All lines in output should be terminated with a newline.
Different test cases should be separated by a single blank line.
Sample Input
2
"#$&/|[]+;:-." -1.2 1.2 0.1 -2 1 0.05
"1234567890AB" -1.2 -0.8 0.02 -0.5 0.5 0.02
Sample Output
########$$$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$$$$
#######$$$$$$$&&&&&&&&&&&&&&&&/////| +||///&&&&$$$$$$$$$$$$$$
######$$$$$&&&&&&&&&&&&&&&&//////||[]-;- |////&&&&$$$$$$$$$$$
#####$$$&&&&&&&&&&&&&&&&///////|||[+; -+[||////&&&&&$$$$$$$$
####$$&&&&&&&&&&&&&&&&///////||[[]+ +[||||//&&&&&&$$$$$$
###$$&&&&&&&&&&&&&&//////||[]++++;: :;+[[[ |//&&&&&$$$$$
##$$&&&&&&&&&&&&&////||||[[]. . |/&&&&&&$$$$
##$&&&&&&&&&&&//|||||||[[[+ . ][|/&&&&&&$$$
#$&&&&&&&///||].]]]]]]]]]+- ; |//&&&&&&$$
#&&&//////|||[]: . -;;- +[//&&&&&&&$
#&//////||||[]+- ]|///&&&&&&$
#/////[[[[]+. +[|///&&&&&&$
.+][|///&&&&&&&
#/////[[[[]+. +[|///&&&&&&$
#&//////||||[]+- ]|///&&&&&&$
#&&&//////|||[]: . -;;- +[//&&&&&&&$
#$&&&&&&&///||].]]]]]]]]]+- ; |//&&&&&&$$
##$&&&&&&&&&&&//|||||||[[[+ . ][|/&&&&&&$$$
##$$&&&&&&&&&&&&&////||||[[]. . |/&&&&&&$$$$
###$$&&&&&&&&&&&&&&//////||[]++++;: :;+[[[ |//&&&&&$$$$$
####$$&&&&&&&&&&&&&&&&///////||[[]+ +[||||//&&&&&&$$$$$$
#####$$$&&&&&&&&&&&&&&&&///////|||[+; -+[||////&&&&&$$$$$$$$
######$$$$$&&&&&&&&&&&&&&&&//////||[]-;- |////&&&&$$$$$$$$$$$
#######$$$$$$$&&&&&&&&&&&&&&&&/////| +||///&&&&$$$$$$$$$$$$$$
########$$$$$$$$$$&&&&&&&&&&&&&&&&&&&&&&&&&$$$$$$$$$$$$$$$$$$
333333333333333333333333333333333222222222222222222
333333333333334444433333333333333332222222222222222
333333334444444444444444433333333333322222222222222
333334444444445555555444444433333333333222222222222
334444444444558866555554444444433333333332222222222
444444444445567 9B755555444444444333333333322222222
4444444444555678B9766555544444444433333333332222222
4444444445555668A0866666554444444444333333333322222
44444444555556670 A87667765444444444433333333332222
4444444555556667 08778A75544444444443333333333322
444444555555666790 99AA 6554444444444333333333332
444444555555667889 B A76654444444444433333333333
444445555555677889A A9876655444444444443333333333
444455555556677880A B09876655544444444444333333333
44455555556677889A A9877655554444444444433333333
4455555556677899 9887665555544444444443333333
4555555566789 0AB 0988765555554444444444333333
555555566680B AAB 866555555444444444433333
5555566667A B876555555554444444433333
55566666789AB A76655555555444444443333
566666677880B B977665555555554444444333
Pedro Ribeiro, 2nd round of CPUP'04
(Concurso de Programa��o da Universidade do Porto 2004)
(Torneio Inter-Universit�rio de Programa��o, 2004, Round 3) Problem G
Cutting Polyominoes
A polyomino may be viewed as a set of squares connected by their sides. Its boundary is an orthogonal polygon. They are often classified by their number of squares, which is equal to their area if each square has area 1. We may represent a polymino in a grid as shown below. We are interested in polyominoes without holes and that have exactly one edge in each grid line that intersects them. Did you know that each polyomino results from a square (of area 1) by applying pairs of transformations INFLATE/CUT? For example, the polyomino shown on the right is obtained if one applies INFLATE (0,0), CUT (0,0), INFLATE (1,1), Cut (3,0), INFLATE (0,1), CUT (2,1), INFLATE (1,2), CUT (0,5). It easy to see that it has area 12.
We are considering that the initial northwest corner is placed in (0,0) and that x and y grow as in the figure. INFLATE} (pi,qi) means ``multiplying by 4 the area of the cell'' (i.e. square) whose northwest corner is in (p_i,q_i). For this, we must duplicate the grid line where this cell is located and then duplicate the column where the cell was located. Obviously, we can drag down cells and then drag other cells to the right. The coordinates of the polyomino are also modified: x -> x+1 iff x > pi and y -> y+1 iff y > qi. One cell can only be inflated if it belongs to the polyomino.
The sequence ``INFLATE (pi,qi) CUT (xi,yi)'' means that one must cut the rectangle defined by the points (pi+1,qi+1), (pi+1,yi), (xi, yi), (xi, qi+1). Such rectangle can only be cut if it simultaneously satisfies the following conditions:
(A) it is actually a rectangle and it is part of the polyomino;
(B) (xi,yi) is a vertex of the inflated polyomino and none of the other vertices of the inflated polyomino belongs to the rectangle (either to its interior or boundary);
(C) at least one of the points (xi,qi+1) and (pi+1,yi) is in an edge that contains (xii).
Problem
Your task is to write a program that computes the area of polyominoes that result from applying a sequence of transformations INFLATE-CUT to squares of area 1.
Input
The input is a sequence of descriptions of polyominoes's constructions, ended by 0. Each description starts with an integer r ≤ 50, which is the number of pairs INFLATE-CUT, followed by r rows, each one with four integers pi, qi, xi, yi, that mean "INFLATE (pi,qi) CUT (xi,yi)". Observe that the polyomino resulting from r INFLATE-CUT's has 2r+4 vertices.
Output
Each line of the output will have the area of the constructed polyomino or 0 if any step in the construction does not satisfy the rules just defined.
Sample Input
4
0 0 0 0
1 1 3 0
0 1 2 1
1 2 0 5
6
0 0 0 0
1 1 3 0
0 1 2 1
1 2 0 5
5 5 5 4
3 4 2 2
6
0 0 0 0
1 1 3 0
0 1 2 1
1 2 0 5
4 4 2 3
5 5 5 5
5
0 0 2 2
1 0 1 2
2 1 4 0
0 3 0 0
1 2 3 1
2
0 0 0 1
0 0 2 2
0
Sample Output
12
0
0
18
0
Ana Paula Tomás, 2nd round of CPUP'04
(Concurso de Programação da Universidade do Porto 2004)
(Torneio Inter-Universitário de Programação, 2004, Round 3) Problem A
Sunny Mountains
During their honeymoon, Mrs and Mr Smith went to the Himalayas. How they were surprised when they observed that, during the sunset, all the snow touched by the sunbeams turned red.
Such a magnificent landscape leaves everyone plenty of emotion, but Mr Smith's number obsession overcame all this. He rapidly began evaluating distances, which made Mrs Smith quite upset.
Problem
Your work is to help him calculate the size, in meters, of the mountainsides that became red as the sun sets. Mr Smith's honeymoon depends on you! Please be quick and efficient.
For the sake of simplicity, consider that, during the sunset, the sunbeams are horizontal and assume that the landscape is described by the set of coordinates of the mountain peaks and cols. This can be depicted by the following figure. A landscape, in this context, is then a sequence of peaks and cols (i.e., only a col follows a peak and conversely).
Note that, in this picture, the sunny mountainsides are emphasized by bold lines and the coordinates of the landscape are emphasized by bold points.
Thus, the goal of this problem is to calculate the total length in meters of the bold lines.
For this task consider that: (1) for all coordinates (x, y), 0 <= x <= 30000 and 0 <= y <= 8848; (2) the unit is the meter; (3) all the X-coordinates are pair-wise distinct; (4) the leftmost point has 0 as X-coordinate and the rightmost point has 0 as Y-coordinate; (5) The total number of coordinates given is n <= 100.
Input
The first line of input contains C (0 < C < 100 ), the number of test cases that follows.
Each test case starts with a line containing the number N of coordinate pairs. The remaining N lines for each test case contain the coordinates defining the landscape. Each of these lines contains two integers, x and y, separated by a single space. The first integer, x, is the X-coordinate, and the second, y, is the Y-coordinate of the considered point.
Output
The output is formed by a sequence of lines, one for each test case. Each line contains a single real number with exactly two decimal digits. This number represents the length in meters of the sunny mountainsides for the corresponding test case.
Sample Input
2
11
1100 1200
0 500
1400 100
600 600
2800 0
400 1100
1700 600
1500 800
2100 300
1800 700
2400 500
2
0 1000
1000 0
Sample Output
1446.34
1414.21
MIUP'2004: Fourth Portuguese National Programming Contest
Problem setter: Simão Melo de Sousa
Many cities provide a comprehensive public transport system, often integrating bus routes, suburban commuter train services and underground railways. Routes on such systems can be categorised according to the stations or stops along them. We conventionally think of them as forming lines (where the vehicle shuttles from one end of the route to the other and returns), loops (where the two ends of the ``branch'' are the same and vehicles circle the system in both directions) and connections, where each end of the route connects with another route. Obviously all of these can be thought of as very similar, and can connect with each other at various points along their routes. Note that vehicles can travel in both directions along all routes, and that it is only possible to change between routes at connecting stations.
To simplify matters, each route is given a designation letter from the set `A' to `Z', and each station along a route will be designated by another letter from the set `a' to `z'. Connecting stations will have more than one designation. Thus an example could be:
A common problem in such systems is finding a route between two stations. Once this has been done we wish to find the ``best'' route, where ``best'' means ``shortest time''.
Write a program that will read in details of such a system and then will find the fastest routes between given pairs of stations. You can assume that the trip between stations always takes 1 unit of time and that changing between routes at a connecting station takes 3 units of time.
Input will consist of two parts. The first will consist of a description of a system, the second will consist of pairs of stations. The description will start with a number between 1 and 26 indicating how many routes there are in the system. This will be followed by that many lines, each describing a single route. Each line will start with the route identifier followed by a `:' followed by the stations along that route, in order. Connections will be indicated by an `=' sign followed by the complete alternative designation. All connections will be identified at least once, and if there are more than two lines meeting at a connection, some or of all the alternative designations may be identified together. That is, there may be sequences such as `...hc=Bg=Cc=Abd...'. If the route forms a loop then the last station will be the same as the first. This is the only situation in which station letters will be repeated. The next portion of the input file will consist of a sequence of lines each containing two stations written contiguously. The file will be terminated by a line consisting of a single #.
Output will consist of a series of lines, one for each pair of stations in the input. Each line will consist of the time for the fastest route joining the two stations, right justified in a field of width 3, followed by a colon and a space and the sequence of stations representing the shortest journey. Follow the example shown below. Note that there will always be only one fastest route for any given pair of stations and that the route must start and finish at the named stations (not at any synonyms thereof), hence the time for the route must include the time for any inter-station transfers.
The example input below refers to the diagram given above.
4
A:fgmpnxzabjd=Dbf
D:b=Adac=Ccf
B:acd=Azefg=Cbh
C:bac
AgAa
AbBh
BhDf
#
5: Agfdjba
9: Abaz=Bdefgh
10: Bhg=Cbac=Dcf
No comments:
Post a Comment