Ural State University collegiate programming contest (25.03.2000)

Dedicated to the 40th 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 take-off 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 Lwhere 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 A1A2…An (the vertices Ai are numbered in the clockwise order). On each side AiAi+1 an isosceles triangle AiMiAi+1 is built on the outer side of the polygon, and angle AiMiAi+1 = ai. Here An+1 = A1.

The set of angles ai 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, co-ordinates of vertices Mi and angles a i (measured in degrees). Write a program which restores co-ordinates 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 co-ordinates of points Mi. And the last n lines of the file consist of degree values of angles ai.

The output file should contain n lines of pairs of coordinates of the points Ai.

 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 a0, a1,…, an+1 (n <= 3000, -1000 <= ai <=1000). It is known that ai = (ai–1 + ai+1)/2 – ci for each i=1, 2, ..., n.

You are given a0, an+1, c1, ... , cn. Write a program which calculates a1.

The first line of an input file contains an integer n. The next two lines consist of numbers a0 and an+1 each having two digits after decimal point, and the next n lines contain numbers ci (also with two digits after decimal point), one number per line.

The output file should contain a1 in the same format as a0 and an+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 ai 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 a1·a2·…·a10. 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 non­alphabetic character. One example of beautification by TeX is that it uses ‘ ‘(two left­single­quotes) and ' ' (two right­single­quotes) to delimit quotations, rather than the mundane " (one double quote) which is provided by most keyboards. Keyboards typically do not have an oriented double­quote, but they do have a left­single­quote ( ‘ ) and right-single-quote ( ' ). TeX lets the user type two left­single­quotes (‘‘) to create a left­double­quote and two right­single­quotes (' ') to create a right­double­quote. 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 double­quotes (") into an identical text except that double quotes have been replaced by the two­character sequences required by TeX for delimiting quotations with oriented double­quotes. The double­quote (") 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