Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 53. (April 2010)

S. 53. In this exercise we are going to do some treasure hunting again. Strategies now are different, because spy satellites can also be used. However, collecting the treasure fast still remains a challenge.

Write your program to collect treasure with the highest possible total value provided that location and value of the pieces, further a time limit for hunting are specified. Your program should decide which pieces of treasure should be picked up and in what order. You can neglect the time needed to pick up a single piece when you have touched it. You can start hunting from any piece. You cover one unit of distance in each time unit.

The map is read from the standard input. The first line contains two integers separated by a space: the number of pieces 1\leN\le1000 and the time limit 0\le T\le 1\;000\;000.

The following N lines then contain 3 integers each (separated by a space): coordinates of the ith piece 0\leXi,Yi\le10000 and its value 0\leCi\le1000.

Your solution should be written to the standard output. The first line should contain the number of pieces 1\leK\leN your program can collect, while the following K lines contain the number of the pieces to be collected in order (indexing begins with 1).

In the example, ,,Példa bemenet'' is sample input, ,,Példa kimenet'' is sample output, while ,,Az (optimális) megoldás'' is the (optimal) solution.

Your solution does not have to be optimal. Submitted solutions are ranked according to their running times in different test cases. The best program gets 10 points, the next one 9 points, while other programs 8 points.

Programs are run on a 2 GHz processor with Core 2 architecture. Your program is allowed to spend at most 10 minutes on each test case, otherwise the actual test case will not be taken into account.

The source code (s53.pas, s53.cpp, ...) together with a short documentation (s53.txt, s53.pdf, ...) -- also describing which developer environment to use for compiling, further a brief description of your solution -- should be submitted in a compressed file (s53.zip).

(10 pont)

Deadline expired on May 10, 2010.


Statistics:

6 students sent a solution.
10 points:Adrián Patrik, Borsos 607 Zalán, Éles András, Nagy 111 Miklós.
8 points:1 student.
5 points:1 student.

Problems in Information Technology of KöMaL, April 2010