Description:
All problems in this contest share the same statement, the only difference is the test your solution runs on. For further information on scoring please refer to "Scoring" section of the statement.
This is an interactive problem.
Imagine you are a treasure hunter, a very skillful one. One day you came across an ancient map which could help you to become rich. The map shows multiple forestry roads, and at each junction there is a treasure. So, you start your journey hoping to retrieve all the hidden treasures, but you don't know yet that there is a wicked wizard standing against you and craving to tangle up these roads and impede your achievements.
The treasure map is represented as an undirected graph in which vertices correspond to junctions and edges correspond to roads. Your path begins at a certain fixed vertex with a label known to you. Every time you come to a vertex that you have not been to before, you dig up a treasure chest and put a flag in this vertex. At the initial vertex you'll find a treasure chest immediately and, consequently, you'll put a flag there immediately as well.
When you are standing at the junction you can see for each of the adjacent vertices its degree and if there is a flag there. There are no other things you can see from there. Besides, the power of the wicked wizard is so great that he is able to change the location of the roads and junctions on the map without changing the graph structure. Therefore, the sequence of the roads coming from the junction $$$v$$$ might be different each time you come in the junction $$$v$$$. However, keep in mind that the set of adjacent crossroads does not change, and you are well aware of previously dug treasures at each adjacent to $$$v$$$ vertex.
Your goal is to collect treasures from all vertices of the graph as fast as you can. Good luck in hunting!
Input Format:
None
Output Format:
None
Note:
Scoring:
All problems of this contest share the same statement and differ only in the test. Each problem contains one test. Map descriptions for the test are available to look at in the archive.
Each test consists of several maps.
The solution score for the problem will be $$$0$$$ in case your solution for some map failed to get an answer "AC" or "F". If the solution correctly interacted with the interactor on all $$$t$$$ maps, the score for the task will be equal to the sum of the scores for each of the maps.
If you have successfully passed all vertices of a graph with $$$n$$$ vertices using $$$moves$$$ moves, the score for the map is calculated as follows. Denote $$$$$$base\_fraction=\frac{base\_move\_count + 1}{n},$$$$$$ $$$$$$sol\_fraction=\frac{moves+1}{n},$$$$$$ $$$$$$c=\frac{90}{\sqrt{base\_fraction - 1}}.$$$$$$
Then:
- if $$$moves \leq base\_move\_count$$$, you get $$$100-c \sqrt{sol\_fraction - 1}$$$ points.
- if $$$base\_move\_count < moves \leq 2 \cdot base\_move\_count$$$, you get $$$20 - \frac{10\cdot(moves + 1)}{base\_move\_count + 1}$$$ points.
For each problem the solution with the highest score is chosen. Please note that the maximum is chosen for the entire test as a whole, not for each separate map.
The final result of the participant is the sum of points for each of the problems.