Ural State University collegiate programming contest (25.03.2000)
Dedicated to the 40^{th} annyversary of mathemathical faculty
(http://acm.usu.ru/)
Problem A. A funny game.
There are several airports in one country, and there are flights between some of them. One can fly from any airport to any other, probably with some changes. For any pair of airports there exists only one sequence of flights that connects them.
Two terrorists play a game. They make moves in turn. Each move consists of the following operations. A player mines an airport, chooses a flight and flies away together with his colleague. After the takeoff he actuates a radio–controlled fuse. As a result the airport that the terrorists have just left is destroyed, and all the flights to and from this airport are no longer possible. After the aircraft lands the other player makes his move, and so forth. One loses if one cannot make a move.
Given an initial list of flights and the number of an airport where the terrorists are at the start of the game, write a program which would determine who wins if the terrorists play a perfect game (each chooses the best move).
The first line of an input file contains two integers: N and K separated with a space. Here N is the number of airports (N <= 1000) and K is the number of an airport, which is the starting point of the game (1 <= K<= N). The next n–1 lines of the file contain pairs of integers separated with a space. These integers are numbers of airports, connected with a flight (all the flights are symmetric and are mentioned only once). There are at most 20 flights to each airport. Input data are always correct.
If the player who starts the game wins, the program should write:
‘First player wins flying to airport L’ where L is the number of an airport to which the players should fly first. If there are more than one such airports, the program should find one of them that has the minimal number. Otherwise the program should write ‘First player loses’.
Sample input.txt: 
Sample output.txt: 
4 3 
First player wins flying to airport 2 
3 2 

3 1 

1 4 
Problem B. Geometrical dreams.
There is a polygon A_{1}A_{2}…A_{n} (the vertices A_{i} are numbered in the clockwise order). On each side A_{i}A_{i+1 }an isosceles triangle A_{i}M_{i}A_{i+1} is built on the outer side of the polygon, and angle A_{i}M_{i}A_{i+1 }= a_{i}. Here A_{n+1} = A_{1}.
The set of angles a_{i} satisfies a condition that the sum of angles in any of its nonempty subsets is not aliquot to 360 degrees.
You are given n <= 50, coordinates of vertices M_{i} and angles a _{i} (measured in degrees). Write a program which restores coordinates of the polygon vertices.
The first line of an input file contains an integer n. The next n lines contain pairs of real numbers which are coordinates of points M_{i}. And the last n lines of the file consist of degree values of angles a_{i}.
The output file should contain n lines of pairs of coordinates of the points A_{i}.
Sample input.txt: 
Sample output.txt: 
3 
1 1 
0 2 
1 3 
3 3 
3 1 
2 0 

90 

90 

90 
Problem C. Simple calculations.
There is a sequence of n+2 elements a_{0}, a_{1},…, a_{n+1} (n <= 3000, 1000 <= a_{i} <=1000). It is known that a_{i} = (a_{i–1} + a_{i+1})/2 – c_{i} for each i=1, 2, ..., n.
You are given a_{0}, a_{n+1}, c_{1}, ... , c_{n}. Write a program which calculates a_{1}.
The first line of an input file contains an integer n. The next two lines consist of numbers a_{0} and a_{n+1} each having two digits after decimal point, and the next n lines contain numbers c_{i} (also with two digits after decimal point), one number per line.
The output file should contain a_{1} in the same format as a_{0} and a_{n+1}.
Sample input 
Sample output 
1 
27.85 
50.50 

25.50 

10.15 
Problem D. Superlong sums.
The creators of a new programming language D++ have found out that whatever limit for SuperLongInt type they make, sometimes programmers need to operate even larger numbers. A limit of 1000 digits is so small... You have to find the sum of two numbers with maximal size of 1.000.000 digits.
The first line of an input file contains a single number N (1<=N<=1000000) — the length of the integers (in order to make their lengths equal, some leading zeroes can be added). It is followed by these integers written in columns. That is, the next N lines contain two digits each, divided by a space. Each of the two given integers is not less than 1, and the length of their sum does not exceed N. Output file should contain exactly N digits in a single line representing the sum of these two integers.
Sample input 
Output for the sample input 
4 
4750 
0 4 

4 2 

6 8 

3 7 
Problem E. Brave balloonists.
Ten mathematicians are flying on a balloon over the Pacific ocean. When they are crossing the equator they decide to celebrate this event and open a bottle of champagne. Unfortunately, the cork makes a hole in the balloon. Hydrogen is leaking out and the balloon is descending now. Soon it will fall into the ocean and all the balloonists will be eaten by hungry sharks.
But not everything is lost yet. One of the balloonists can sacrifice himself jumping out, so that his friends would live a little longer. Only one problem still exists ¾ who is the one to get out. There is a fair way to solve this problem. First, each of them writes an integer a_{i} not less than 1 and not more than 10000. Then they calculate the magic number N that is the number of positive integer divisors of the product a_{1}·a_{2}·…·a_{10}. For example, the number of positive integer divisors of 6 is 4 (they are 1,2,3,6). The hero (a mathematician who will be thrown out) is determined according to the last digit of N. Your task is to find this digit.
Input file contains ten numbers separated by a space. Output file should consist of a single digit from 0 to 9 — the last digit of N.
Sample input 
Output for the sample input 
1 
9 
2 

6 

1 

3 

1 

1 

1 

1 

1 
Problem F. Preparing an article.
TeX is the leading typesetting system for mathematics, science, and engineering and has been adopted as standard by the American Mathematical Society. LaTeX was developed later by Leslie Lamport. It is based on TeX and provides a set of higher level commands for production of complex documents. In TeX or LaTeX, any text editor program may be used to enter and modify the input text. The source text contains the actual text as well as formatting commands beginning with \. Commands are delimited by any nonalphabetic character. One example of beautification by TeX is that it uses ‘ ‘(two leftsinglequotes) and ' ' (two rightsinglequotes) to delimit quotations, rather than the mundane " (one double quote) which is provided by most keyboards. Keyboards typically do not have an oriented doublequote, but they do have a leftsinglequote ( ‘ ) and rightsinglequote ( ' ). TeX lets the user type two leftsinglequotes (‘‘) to create a leftdoublequote and two rightsinglequotes (' ') to create a rightdoublequote. Now, you have a text only file containing at most 250 lines at most 80 symbols each, as source or input, and you want to use TeX to beautify it. Rather than doing everything by hand, as the first step of automation you want to convert the quotes into the TeX format by using a program. This program will convert the text with doublequotes (") into an identical text except that double quotes have been replaced by the twocharacter sequences required by TeX for delimiting quotations with oriented doublequotes. The doublequote (") characters should be replaced appropriately by proper double single quotes depending on whether it is an opening or closing quotation mark. Question of nested quotations does not arise. The first " must be replaced by ‘‘, the next by '', the next by ‘‘, the next by '', and so on. An opening double quote must have its closing quote in the same paragraph. If a match is not found in the same paragraph for an opening quote, this quote has to be deleted. Paragraph ends in the source text are marked either by at least one blank line, or a \par command or both. Your program must also be careful about the \" command which is used to produce umlaut or dieresis (\"e leads to ë). These are to be left untouched.
Input:
Input will consist of several lines of text containing a number of double quotes ("), as well as some TeX commands. End of file will be marked by an \endinput command.
Output:
Output will be an exact replica of the input, except the double quotes are to be modified according to the rules described above.
Sample Input
There is no "q in this sentence. \par
"Talk child," said the unicorn.
She s\"aid, "\thinspace ‘Enough!', he said."
\endinput
Sample Output
There is no q in this sentence. \par
‘‘Talk child,’’ said the unicorn.
She s\"aid, ‘‘\thinspace ‘Enough!', he said.''
\endinput
Problem G. Simple game on a grid.
There is an infinite grid and an m´ n rectangle of stones on it (1 <= m,n <= 1000). The stones are located in the knots of the grid.
A following game for a single player is being played. One stone can jump over another along a vertical or a horizontal line. A stone which had been overjumped is taken away. The purpose of the game is to minimize number of stones on a grid.
Given a pair of numbers m and n separated with one space in an input file you are to write a program which should determine a minimal number of the stones left on the grid.
Sample input 
Sample output 
3 4 
2 
Problem H. Rabbit hunt.
A good hunter kills two rabbits with one shot. Of course, it can be easily done since for any two points we can always draw a line containing the both. But killing three or more rabbits in one shot is much more difficult task. To be the best hunter in the world one should be able to kill the maximal possible number of rabbits. Assume that rabbit is a point on the plane with integer x and y coordinates. Having a set of rabbits you are to find the largest number K of rabbits that can be killed with single shot, i.e. maximum number of points lying exactly on the same line. No two rabbits sit at one point.
Input:
An input file contains an integer N (2<=N<=200) specifying the number of rabbits. Each of the next N lines in the file contains the x coordinate and the y coordinate (in this order) separated by a space (1000<=x,y<=1000).
Output:
The output file contains the maximal number K of rabbits situated in one line.
Sample Input File: 
Output File: 
6 
5 
7 122 

8 139 

9 156 

10 173 

11 190 

100 1 