Problems

DAY 1
Problem 1: Paving Roads (30 points)

In an isolated area of a poor country there exist N towns connected by roads. Every pair of towns is not necessarily connected by a direct road but there is a path connecting them. All these roads are unpaved. The government is interested in paving some of these roads, so that with these paved roads:

* there is a paved path from any of these towns to any other town, and
* this does not hold if any of these (paved) roads is left unpaved

In order to find the most preferable paving, the government wants to obtain the number of all the different possible pavings.

INPUT
Your program should read the input from the file INPUT.TXT, as follows: The first line contains the number of towns N (2 <= N <= 20) and the number of roads R (N-1 <= R <= 190) as two positive integer numbers separated by a space character. The next R lines describe the town connections as pairs of integers K and L, denoting a road connecting the K-th and L-th town (0 <= K, L <= N-1).

OUTPUT
Your program should produce its output into the file OUTPUT.TXT as follows:
There will be only one line of text, containing the number of different possible pavings.

EXAMPLE                                                          

INPUT.TXT                                                         OUTPUT.TXT
4 4                                                                        3
0 2
0 1
0 3
1 3

Time Limit per Test: 5 seconds

DAY 1
Problem 2: The Flip Game (40 points)

There is an ancient solitaire game named "the flip game". It consists of an array of M rows and 9 columns of two-colored pegs, with a black and a white side. When a peg with its white side showing is flipped, it shows its black side, and the other way around.

In each move of the game the player flips an entire row or an entire column.

The objective of the game is to leave as few pegs on their black side on the board as possible, by doing any number of moves.

INPUT
Your program should read the input from the file INPUT.TXT. The first line contains one positive integer number M (1 <= M <= 1000), denoting the number of rows in the game board. The next M consecutive lines contain exactly 9 characters, which are "0"s or "1"s, separated by one space character, where "0" means a peg showing its white side and "1" means a peg showing its black side.

OUTPUT
Your program should produce its output into the file OUTPUT.TXT as follows:
There will be only one line of text, containing the minimum possible number of pegs showing their black side, which are left on the game board.

EXAMPLE

INPUT.TXT                                                         OUTPUT.TXT
4                                                                           1
1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0

Time Limit per test: 3 seconds

DAY 1
Problem 3: Guarding a Gallery (30 points)

Gallery 'El Greco' consists of a single room whose walls have either a north-south direction or a west-east direction. Moreover its floor plan forms a single closed polygonal line and there are no objects of any kind inside the room. There are precious paintings on every wall and the gallery owner wants to hire a guard to guard them. So, he's interested in determining whether there is any point in the gallery from where the guard can see all the walls. Note that a wall is still visible even if the guard is located along the line of the wall.

INPUT
Your program should read the input from the file INPUT.TXT, as follows: The first line contains the number N (4 <= N <= 1000) of the corners of the gallery. On the N following lines there are pairs of integers X and Y denoting the coordinates of the corners in a clock-wise order (0 <= X, Y <= 1000).

OUTPUT
Your program should produce its output into the file OUTPUT.TXT as follows:
There will be only one line of text, containing the integer coordinates of a point in the gallery from where the guard can
see all the walls; the coordinates should be separated by one space character. There may be many possible such points, output only one. If no such point exists then your program should output "NO POINT".


EXAMPLE

INPUT.TXT                                                         OUTPUT.TXT
6                                                                           70 10
0 0
0 50
50 50
50 100
100 100
100 0

Time Limit per Test: 1 second

DAY 2
Problem 1: Crime Statistics (30 points)

A police officer has undertaken the duty to produce statistical data about the crime in a large city. His/her project is to find for a convex area in the city how many of the committed crimes took place there.

INPUT
Your program should read the input from the file INPUT.TXT as follows. The first line contains an integer N (3 <= N <= 1000) which represents the number of corners of the convex area in question. The N following lines contain two integers X and Y each (ranging from -1000 to 1000) separated by a space character, which represent the coordinates of the corners in order around the area's border. The next line contains an integer M (1 <= M <= 10000) which is the number of committed crimes. The following M lines contain two integers X and Y each (ranging from -1000 to 1000) separated by a space character, which represent the coordinates of the location of a crime.

OUTPUT
Your program should write its output to the file OUTPUT.TXT as follows. There is one line containing an integer, which is the number of crimes that took place inside or on the border of the specified area.

EXAMPLE

INPUT.TXT                                                         OUTPUT.TXT
4                                                                           1
0 0
0 100
100 100
100 0
2
50 50
-30 50

Time Limit per Test: 1 second

DAY 2
Problem 2: River Highwater (30 points)

Westmouth and Eastmouth are two towns located on the west and east banks of river Highwater respectively; Westmouth is to the south of Eastmouth. The river's banks, which are polygonal lines, are such that an east-west line intersects each one of them in exactly one point. Captain Hook sails frequently between the two towns. In order to minimize his fuel expenses, he would like to find the shortest route from Westmouth to Eastmouth.

INPUT
Your program should read the input from the file INPUT.TXT as follows.
The first line contains two integers M and N (2 <= M, N <= 2000) which represent the number of corners of the west and east bank respectively. The M lines that follow contain two integers X and Y each (0 <= X, Y <= 3600), which represent the coordinates of the west bank's corners from Westmouth to a point at the same geographic latitude (that is, the same Y-coordinate) as Eastmouth. The N lines that follow contain two integers X and Y each (0 <= X, Y <= 3600), which represent the coordinates of the east bank's corners from a point at the same geographic latitude (that is, the same Y-coordinate) as Westmouth to Eastmouth.

OUTPUT
Your program should write its output to the file OUTPUT.TXT as follows.
The lines contain two integers X and Y each, separated by a space character, which are the coordinates of the corners of the route from Westmouth to Eastmouth. (It is clear that the first line should have the coordinates of Westmouth and the last line the coordinates of Eastmouth).

EXAMPLE

INPUT.TXT                                                         OUTPUT.TXT
3 3                                                                        0 0
0 0                                                                        50 50
50 50                                                                    50 100
0 150                                                                    100 150
100 0
50 100
100 150

Time Limit per Test: 1 second

DAY 2
Problem 3: Knowing people (40 points)

A gathering is taking place in a large room. Each participant may know none, some, or all the other participants. We want to see whether there is a way to place all these people in a queue, so that for everyone in the queue, his/her acquaintances located behind him/her all know each other.

INPUT
Your program should read an input file INPUT.TXT that has the following structure.
The first line contains the total number N of people (1 <= N <= 50). The second line contains the total number M of pairs of people that know each other (0 <= M <= 1225). Each of the following M lines contains two integers I and J (1 <= I, J <= N) separated by a space character and indicates that persons I and J know each other.
.
OUTPUT
Your program should produce an output file OUTPUT.TXT that should be as follows.
The first line contains the string "YES" if there is a way to place all the people in a queue; otherwise, the string "NO" should appear in the output. If the answer is "YES", the next line of the output file contains a proper sequence of the N people, separated by space character (from the front to the end).

EXAMPLE

INPUT.TXT                                                         OUTPUT.TXT
5                                                                           YES
7                                                                           1 2 4 5 3
1 2
3 1
2 3
2 4
4 3
3 5
4 5

Time Limit per Test: 1 second

Back