7th Balkan Olympiad on Informatics Ioannina - Greece
|
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