Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2014
Kolonie
kolonie.c, kolonie.cpp, Kolonie.java
In 1996, the Czech Technical University already organized the 2nd year of the programming
contest. The problem set contained a very interesting problem about n-dimensional hyperex
hypergons. This single problem gave a uniting theme to the whole 1996 CTU Open contest:
all problems involved the launch of a fictional hyper-cosmic spaceship Nostromo. This quickly
became a tradition and since then, CTU Open Contest problem sets have common themes.
We wanted to present the Hyperex Hypergons to you today but we finally decided that they are
a little bit too difficult (no team did even try to solve it back in 1996), so we only recommend
the problem to your attention -- maybe you would like to give it a try and solve it after this
contest is over? We will publish the problem statement on our web page. For this competition,
we instead present you an English translation of another problem from the 1996 set.
An important task of the hyper-cosmic spaceship Nostromo is to establish a permanent base on
the orbit of the planet MX8-26B in the Centaurus constellation. The base is built from complexes
composed of identical hexagonal cubicles. Each of the six sides of each cubicle contains a hole
serving either as a passage to a neighboring cubicle or as a window in case when no cubicle of
the finished base is neighboring at this side. The complexes can be composed of the cubicles in
many different ways.
The travelers have a given number of complexes of several shapes at their disposition. Every
cubicle in the finished base accommodates as many people as the number of windows it has.
Write a program to determine whether it is possible to build a base for the prescribed number
of people given the descriptions of available complexes.
Input Specification
The first line of the input contains the number of test cases N . The first line of each test
case contains two space-separated positive integers P ≤ 1 000 000 and T ≤ 1000, where P is
the number of inhabitants for whom the base is to be built and T is the number of shapes of
available complexes.
Each of the following T lines contains integers separated by spaces describing one shape of
a complex. The first two numbers on each of these lines are integers C and S, where C (0 ≤
C ≤ 1000) is the number of available complexes of this shape and S (1 ≤ S ≤ 1000) is the
number of cubicles that make up the complex. It is known that every complex is connected and
the hexagonal bottom bases of its cubicles lie in one plane.
The following S pairs of integers are the x and y coordinates of the centers of the hexagonal
bases of the cubicles in a hexagonal coordinate system. The coordinates satisfy -10 000 000 ≤
x, y ≤ 10 000 000. The angle between the x-axis of the hexagonal coordinate system and the x-
axis of the Cartesian coordinate system is -30◦. The angle between the y-axis of the hexagonal
coordinate system and the x-axis of the Cartesian coordinate system is +30◦. See the following
figure with drawings of five shapes from the first test case of the sample input.
Output Specification
For each test case, print exactly one line. If it is possible to build the base, the line says "Je
treba X celku.", where X is the minimal possible number of complexes when the shapes
and their connections are chosen optimally. Otherwise print "Kapacita zakladny je pouze
X lidi.", where X is the maximal number of people that can fit inside the optimal base built
from all of the available complexes.
Sample Input
Output for Sample Input
3
Je treba 3 celku.
50 5
Kapacita zakladny je pouze 10 lidi.
10 1 0 0
Je treba 2 celku.
34001
0
2
0
2
1
45000
1
0
2
1
120
66001
0
2
0
0
11102
17102
0
0
1
1
1210212
11 1
2100
10 2
100 1 1 1
02001
0
