Each day the competitors had to solve three
problems. The problems,
who was created of the team leaders, is a really tough collection.
If you want, you
can make your own contest, it's up to you. We give you the texts
(even PDF), the
test files and the time limits. The test computers run with 500
MHz. OK, two times five hours from now ...
Honeycomb problem (Finland)
Figure 1 shows a honeycomb of numbers (side length
of the honeycomb is 3). A route starts from some node in
the
uppermost row and ends at some node in the lowest row. From a
node,
the route can continue only diagonally down to the left or diagonally
down to the right. When creating a route through the honeycomb,
you
are allowed to make at most one swap of two numbers on
at
most one horizontal row of the honeycomb. (Swapping essentially
means that in one chosen row you are allowed to place the greatest
number of that row to any position on the same row.) Your task
is to
write a program that calculates the highest sum of numbers on
any
route using the ability of swapping two numbers on a chosen row.
Restrictions:
Input data:
The side length of the honeycomb is in the first row of the file
HON.IN
If the side length is n, the honeycomb consists of 2n-1
rows. Numbers on
the rows of the honeycomb are on the following 2n-1 rows
as follows:
3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
Output
data:
The highest sum is written as an integer in the file HON.OUT
In the example of figure 1:
22
In the figure 1 the correct solution (3+2+8+5+4=22) is
gray shaded. Notice
that number '5' on the 4th row (from the top) is swapped to the
3rd
position (from the left) on that row.
Time limit for each test: 5 s 6 points for each correct test |
The test files (92 Kb) |
Time Zones (Sweden)
You're a businessman that has customers all over the world. During
one day you get exactly one message from each time
zone,
including the zone you stay in. The messages come with their
sending time specified in them (the messages are
transported instantly). Unfortunately due to a millennium bug
the senders' local time is given without anything that identifies
their
time zone.
Task:
Your task is to identify from which time zones the messages originated.
In this task the number of hours, n, in one day varies
between
5 ... 60. The number of time zones is always the same as
the
number of hours and each time zone has a time displacement which
is an integral number of hours.
The zones are numbered from 0 to n-1. You are living
and
receiving the messages in ''GMT'', that is in time zone 0
without any time displacement. The time zones are counted
westward. That means that you should add z hours to the
local
time in zone z to get the time in your zone. Note that
this is
not the common way to count the zones, normally zone 2
would be
known as "-2:00".
For example, if the local time in time zone 2 is 03:15
it is
05:15 in your zone (''GMT'').
The messages can arrive anytime during the day (that is between
0:00-(n-1):59), but no two messages arrive at the same
time. The date line goes between zone 0 and the last zone
and
can thus be ignored.
Input
data:
The first row of the file ZON.IN contains the number of
hours in
one day, n, 5<=n<=60, which also is the number of
time
zones and the number of messages you received.
Each of the following n rows contains the local sending
time given
as hhmm (2 digits for hours and 2 digits for minutes where
0<=hh<=n-1 and 0<=mm<=59. The rows are
ordered in
chronological order, i.e. the first message that arrived is on
the first row.
There is one unique solution to all given test examples.
Output
data:
The output should be written to the file
ZON.OUT The file must contain a single row with n
numbers from 0 to n-1 identifying in which time
zones the n
messages originated. The first number corresponds to the first
time given in the input etc.
Example:
ZON.IN
5
0017
0250
0400
0201
0002
ZON.OUT
3 1 0 2 4
Note that message 3 must come from time-zone 0 or it would
have arrived at a time later than 4:59 which is the last
minute in the 5-hour days in this example.
Time limit for each test: 30 s 6 points for each correct test |
The test files (6 Kb) |
Electronical plate (Lithuania)
A square grid is carved on the top of a square plate. The place
where two gridlines
cross is called a node. There are nxn nodes in the grid.
The problem (center) and the solution (right)
Some nodes contain pins. The task is to connect those pins to
the nodes on the boundary
of the plate using electronic circuits. A circuit can be laid
out only on the grid (e.g.
it can't be laid out slantwise). Any two circuits can't have a
common point, therefore
any two circuits can't be laid out on the same gridline, nor on
the same node. A circuit
can't be laid out on the boundary grid (the circuit must be finished
as soon as it reaches
boundary) nor on a node, containing another pin.
An example of an electronic plate containing pins is given in
figure 2, center.
Black dots in the picture represent pins.
Problem:
Write a program to connect as many pins as possible to the nodes
on the boundary.
The pins which are already on the boundary satisfy the requirements
and there is no need
to make any circuits for them.
If there exists more that one solution find any of them.
Input
data:
Input data are given in the text file ELE.IN. The first
line of this file contains an
integer n, (3 <= n <= 15).
Each of the following n lines consists of n digits
separated by one space. The digits
can be 1 or 0. One (1) means a pin, zero
(0) means a node without a pin in the
appropriate place of the grid.
The nodes are numbered from 1 to nxn first from
left to right and then from
the top to bottom (row-major order). The number of the node the
pin is on is
the identifier of the pin.
Output
data:
Output the results to the text file ELE.OUT. Write k
- the maximum number of
pins connected to the boundary using electronic circuits - in
the first line of the file.
A circuit connecting an appropriate pin to the boundary should
be described in each of
the following k lines. First comes the identifier of the
pin, then the sequence of
letters, describing the directions of the circuit: E -
to the East, W - to the West,
N - to the North, S - to the South. One space should
be left between the identifier
and the sequence of letters, and no spaces should be left between
the letters in the sequence.
The results should be presented in the increasing order of pin
identifiers.
ELE.IN 6 6 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 |
ELE.OUT 11 E 16 NWN 17 SE 27 S 28 NWWSS 29 S |
Time limit for each test: 10 s 4 points for each correct test |
The test files (5 Kb) |
Input
data:
The first line of the file DIV.IN contains one positive
integer d, (d<=5).
This is the number of data sets. The data sets follow. The first
line of each data set contain an integer n, (2<=n<=10000).
This is the number of integers in the expression. Each of
the following n lines contains exactly one positive integer
not
greater than 1,000,000,000. The ith number is the ith
integer in the expression.
Output
data:
For each i,(1<=i<=d) your program should write to
the ith line of
the output file DIV.OUT one word YES, if the ith
input expression can be
transformed into an expression whose value is an integer number,
and the word NO in the other case.
Example:
For the input file DIV.IN
2
4
1
2
1
2
3
1
2
3
the correct result is the output file DIV.OUT:
YES
NO
Time limit for each test: 2 s 6 points for each correct test |
The test files (1160 Kb) |
Time limit for each test: 20 s 6 points for each correct test |
The test files (3 Kb) |
Mutexes (Estonia)
Modern programming languages allow writing programs that consist
of several threads
of execution. This is as if several programs are running in parallel
in the same
address space, accessing the same variables. Often the threads
need to be synchronized
with each other. For instance, one thread may need to wait for
another to complete some
computation and store the result into some variable.
The simplest tool for thread synchronization is mutex.
A mutex is a special object that
can be in locked or unlocked state. A locked mutex
is always owned by exactly
one thread. There are two operations that a thread can apply to
a mutex: LOCK and UNLOCK.
When a thread applies LOCK to a mutex that is currently unlocked,
the mutex becomes
locked and the thread acquires ownership of the mutex. If a thread
tries to apply
LOCK to a mutex that is already locked by some other thread, the
thread is blocked
until the mutex is unlocked.
When a thread applies UNLOCK to a mutex owned by the thread, the
mutex becomes unlocked. If there were other threads waiting to
LOCK the mutex, one of them is granted ownership of the mutex.
If there were several threads waiting, one is selected arbitrarily.
One of the common problems in multithreaded programs are deadlocks.
A deadlock occurs when two or more threads are waiting for each
other to release a mutex and none of them can continue. A deadlock
occurs also when a thread is waiting for a mutex that was locked
by another thread that has terminated without releasing the mutex.
Task:
You are provided descriptions of some threads and your task is
to decide whether
deadlocks can occur.
Each of the threads is a sequence of instructions of the following
form:
LOCK <mutex>
UNLOCK <mutex>
You may assume the following about the commands:
Input data:
The first line of input file MUT.IN contains the number
of threads
M, (1<= M<=5) and is followed by M blocks
describing each
thread. The first line of a block describing thread i contains
the number of
instructions in this thread Ni, (1<=Ni<=10)
and is followed by Ni
lines with instructions. Instructions do not contain extraneous
whitespace.
Output
data:
The first line of output file MUT.OUT must contain one
number: D.
D must be 1 if deadlocks are possible, or 0
if not.
If deadlocks are possible, the second line must describe a state
of program
in which a deadlock occurs. If there are several states with a
deadlock, output
any of them. In this case we are looking for complete deadlock,
in which none of
the threads can continue execution -- a thread must be either
terminated or
blocked by a mutex. If deadlocks are not possible, the line must
be empty.
State of program is described by specifying the zero-based index
of current
instruction for each thread in the order in which the threads
are presented
in input file. For a terminated thread, output -1 as the
index. The indexes
must be on a single line and separated by spaces.
Sample:
MUT.IN 2 1 LOCK X 2 LOCK Y LOCK X |
MUT.OUT 1 -1 1 |
Time limit for each test: 5 s 6p, 6p, 6p, 8p, 8p, 10p, 8p, 8p for the tests in that order. |
The test files (3 Kb) |