Problem I. 158. (April 2007)

I. 158. The central star system of the Galactic Republic dispatches envoys to all other systems throughout the Galaxy to personally deliver the new flag of the Republic. Members of the Senate first thought that the fastest way to send all the flags out is to use separate spaceships to every star system. This way the outermost system gets their flag last. We will refer to this as original strategy.

The Senate later realized that envoys arriving to a system may proceed to other star systems as well. Moreover, it is also possible for several envoys to travel in the same ship together to a particular system, then, after the delivery, every envoy proceeds to different systems. (Every system has a sufficient number of ships, each capable of carrying an arbitrary number of envoys. All these ships have the same speed.) We will call this as modified strategy.

The Senate decided to organize the delivery in this latter way. However, it is required that the time needed to deliver the last flag should be no more than the corresponding time according to the original strategy.

You should compare the total length of route of the ships if they follow the original or the modified strategy.

Positions of the star systems in the Galaxy are given in the usual Cartesian coordinates. Each line of the input text file contains the X, Y and Z real coordinates of a system, separated by a space. The first line of the file corresponds to the central system. Your program reads the name of the input file from the command line, then uses the standard output to display the total length of route of the ships following the original, then the modified strategy, finally, the difference between these numbers.

The source code of your program (i158.pas, i158.cpp, $\ldots$ ) together with a short documentation (i158.txt, i158.pdf, $\ldots$ ) should be submitted.

(10 pont)

Deadline expired on May 15, 2007.

Sorry, the solution is available only in Hungarian. Google translation

A feladatra csak két teljes megoldás érkezett, ezeket adjuk mintaként: Danka Miklós András (danka.zip) munkája Pascalban és Györök Péter (gyorok.zip) megoldása Delphiben.

Statistics:

12 students sent a solution.

10 points: Danka Miklós András, Györök Péter.

8 points: 3 students.

6 points: 1 student.

4 points: 1 student.

3 points: 1 student.

2 points: 3 students.

1 point: 1 student.

Problems in Information Technology of KöMaL, April 2007

12 students sent a solution.
10 points:	Danka Miklós András, Györök Péter.
8 points:	3 students.
6 points:	1 student.
4 points:	1 student.
3 points:	1 student.
2 points:	3 students.
1 point:	1 student.

Already signed up?
New to KöMaL?