SHUNT - Scavenger Hunt
You are playing a scavenger hunt game organized by your school.
Assume the school is an infinite 2D field. The rules of the game are quite simple: There are n people from the organization, numbered from 1 to n. Person i is located at position (xi, yi). All you have to do is go to (xi, yi) and let the i-th person see you, for all 1 ≤ i ≤ n. You can run from a position (xa, ya) to a position (xb, yb) in dist((xa,ya),(xb,yb)) seconds, where dist(P,Q) is the euclidian distance between points P and Q.
Initially, you are at the same position of person 1, who already saw you. Also, initially you only know the position of person 1. To find out the position of some other person, you need to ask someone. Every person knows the position of all the others. However, if you ask person i where person j is, it will take him Wi,j seconds to answer. Your task is to find a sequence of questions and runnings that let you finish the game quickly. This is a partial problem - you do not need to find an optimal solution, but your score will be proportional to the solution you find.
Input/Output
This is an iterative problem. Your program will "talk" to the judge directly via the standard input and output.
There are no more than 20 test cases. For each test case, the judge will start by printing
START n
x1 y1
W1,1 W1,2 ... W1,n
W2,1 W2,2 ... W2,n
...
Wn,1 Wn,2 ... Wn,n
(Assume 2≤n≤40 and 0≤ xi,yi,Wi,j≤104).
After reading that, your program should print commands. A command must be one of these:
- ASK i ask the person that saw you last where the person i is. The judge will reply by printing ANSWER xi yi . You'll get "Runtime Error" if (1 ≤ i ≤ n) doesn't hold.
- GO i go to the position of the person i and let him see you. The judge will reply by printing MOVED . You'll get "Runtime Error" if (1 ≤ i ≤ n) doesn't hold or if you don't know the position of the person i yet.
- FINISH finish the game. The judge will reply by printing OK length , where length is the total time spent by you in the game of the test case in seconds, with exactly 3 fractional digits (this is just a "bonus"; your program should be able to calculate length by itself). You'll get "Wrong Answer" if you haven't been to everyone's position at least once.
- You'll get "Runtime error" if your program prints something different from the commands described above.
Imediatally after printing OK length , the judge will start another test case by printing START ... . If there are no more test cases, the judge will print END instead. In this case, your program should terminate.
Please notice that you are allowed to ask more than one question or to not ask any questions at all to a person.
Attention: the program should clear the output buffer after printing each line. It can be done using fflush(stdout) command or by setting the proper type of buffering at the beginning of the execution - setlinebuf(stdout).
Also, while reading data from the judge in C/C++ using scanf, avoid hardcoding the commands you known you'll receive. For instance, prefer to use scanf("%s %d",start_string,&n) instead of scanf("START %d",&n).
Score
For each test case, pi = min(1.0, length/greedy), where length is the total time spent by you, and greedy is the length obtained by a program that prints ASK 2 GO 2 ASK 3 GO 3 ... ASK n GO n FINISH.
Your final score will be equal to ceil[ (∑(pi*ni)/∑ni)*100 ], where ni is the value of n in the i-th test case. The lower your score is, the better you're ranked.
Exemple
This is an exemple of the executation of a program that obtains greedy as the total spend time (and thus gets the score 100):
Judge:
START 3
0 0
1 2 3
4 5 6
7 8 9
Program: ASK 2
Judge: ANSWER 2 2
Program: GO 2
Judge: MOVED
Program: ASK 3
Judge: ANSWER 1 1
Program: GO 3
Judge: MOVED
Program: FINISH
Judge:
OK 12.243
END
Program: <terminates>
hide comments
Francky:
2014-11-15 23:58:42
According to admins, the issue should be fixed with next language upgrade. Please be patient. |
|
Min_25:
2014-11-07 20:46:02
@Ricardo Oliveira [UFPR]
|
Added by: | Ricardo Oliveira [UFPR] |
Date: | 2013-04-08 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own problem |