Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

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