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
Lodˇ
e
lode.c, lode.cpp, Lode.java
In 1999, there were another three contests at the Czech Technical University: faculty round
(FEL++), CTU Open, and Central Europe Regional Contest. The enthusiasm of the "founding
fathers" had decreased a little bit and there was no wonder. They had been organizing two or
three competitions a year for a period of five years. What had once been fun turned into hard
work. Fortunately, many new organizers arose from the former contestants, so the tradition
could go on.
The problem Lodˇ was added to the 1999 contest at the very last moment and it was intended
e
to be an easy one. Now you may find out yourselves how difficult or easy it was.
Juliet reads an interesting sci-fi book. In one chapter, the main character needs to solve a problem
of maximizing the utilization of cargo spaceships. The ships transport valuable items that have
the form of D-dimensional mesh with the size of 3 nodes in each dimension. The nodes are
formed by balls of the same weight. The connections between balls are so light that their
weight is negligible compared to the weight of balls. This means that the weight of any item is
determined solely by the number of its nodes. On the other hand, the value of such an item is
equal to the number of nodes plus the number of connections.
zero dimension
first dimension
second dimension
weight = 1
weight = 3
weight = 9
price = 1
price = 5
price = 21
Each spaceships has a limited tonnage and we want to maximize the total value of items that may
be stored in the ship without exceeding the tonnage. Your task is to decide what items of what
dimension should be loaded to maximize their total value, providing that we have an unlimited
supply of items of all dimensions.
Input Specification
The first line of the input contains the number of test cases N . Each test case then consists
of a single line containing one positive integer number K < 10 000 000 giving the ship cargo
capacity.
Output Specification
For each test case, print one line containing space-separated non-negative numbers Xm Xm-1
. . . X1 X0, where Xm > 0 and Xi (0 i m) is the number of items of the i-th dimension that
we need to store to maximize their total value.
Sample Input
4
1
100
175
9841
Output for Sample Input
1
10201
20111
111111111