Sziasztok!
Az első kérdésem az lenne, hogy pénteken a szünet befolyásolja a
foglakozást is?
És küldenék még egy feladatot is, a 2006-os CH24 EC-en volt anno (lehet,
hogy többen ismeritek):
Problem B: Building Pipe Systems
In the country of Elbonia, the citizens are gettingtir ed of havingno
sanitation system.
Together, they have saved some money to build a new pipe system that
will connect
their houses to the communal sanitation system. But since this is a
small country,
where most of the people have small incomes, they really want to build
the cheapest
system possible. The largest cost in this whole endeavour will be the
pipes that must
be put in the ground, connecting all the houses. Therefore, they need
your help in
minimizingthe total length of these pipes.
A pipe system will connect all the houses together. The houses may either be
connected house to house, or they may be connected via arbitrarily
positioned junction
points. Since Elbonia consists entirely of mud, the cost of layingdo wn
the pipes is
uniform over all the land. In other words, the only thingt hat matters
is that the total
length of pipes is as small as possible.
Input
Each test case contains the layout of one town. The consists of a number
N, denoting
the number of houses. Followingthis number come N lines, each
containtinga pair
xi yi denotingthe position of one house. The values xi and yi are both
floatingp oint
numbers of single precision length.
Output
For each test case, you will need to produce an output that represents a
fully-connected
pipe system. The smaller the total length of this pipe system, the
higher the value
of your solution will be. The representation of this pipe system should
consist of the
followingelemen ts.
On the first line, a number M, where N ≤ M < 10 · N, denoting the number of
points on the pipe system. Followingthis come M lines, each containinga
pair xi yi
denotingthe position of one house or one junction. The first N lines
should contain
the house locations from the input in the same order, while the next M −
N lines
contain your choosen junction postitions.
Followingthis, on a new line, the number K of pipes that your pipe
system has. On
the following K lines, you should print pairs aj bj of numbers, where 0
≤ aj, bj <M)
and aj = bj, specifyingthe points connected by the pipe. Furthermore,
each pair aj bj
may only occur once in the pipe system. The indexingo f the points is
zero-based.
Scoring
Your base score for a test case will be calculated as follows. Let Val
be the length of
your solution, and Opt be the length of the best solution of any team,
including the
judges’ solution. Then the base score of your solution is given by
1002−Val/Opt.
In other words, if your solution matches the best solution, the base
score will be 100,
and if your solution is twice as longas the best solution, the base
score will be 1.
Üdv.
Robi
Show replies by date