National Olympiad in Informatics, China, 2006
Day 2, Problem 2 - The Clever Tour Guide
Alex has recently fallen in love with the job of being a tour guide. Day and night, he thinks about taking tourists to see attractions at various places. It just so happens that city M is currently hosting the NOI, where lots of people are coming to visit. To help him, many of Alex's friends have recommended him to tourists requiring a tour guide.
City M contains n attractions, where Alex has already numbered from 1 to n. Between some attractions, there are bidirectional roads. Alex can tell the tourists to meet up at any attraction point, and then take them all sightseeing. In the end, he can also pick any attraction point to end the tour. However, none of the tourists would like to go to attractions that they've already visited on the tour. So, Alex cannot bring tourists to the same attraction more than once.
Alex wishes for you to help him design a plausible route, such that the tourists can visit as many attractions as possible.
There are 10 test cases
guide10.in that will be given to your program (through standard input). They can be downloaded here for you to study: guide.zip
The first line of input will be an integer T (1 ≤ T ≤ 10), the test case number. The second line will contain two integers n and m, respectively representing the number of attractions and the number of roads. The following m lines each contain two integers a and b, indicating that there is a bidirectional road between attraction a and attraction b.
For each test case, you must correctly output on the first line p, indicating that the route you found passes through p attraction points. After that, p integers should follow, one per line, specifying the attraction points your route visits, in the order that they are visited.
0 5 5 1 2 3 2 2 4 2 5 4 5
4 1 2 4 5
There are many answers, 4 of which are listed below. You may output any one of them.
|Answer 1||Answer 2||Answer 3||Answer 4|
4 1 2 4 5
4 1 2 5 4
4 3 2 4 5
4 3 2 5 4
Your given score will be based on the difference between your answer and the correct answer. Assuming your answer is valid and the number of attractions you visit is x, also letting the result we've found to be ans, then your score out of 10 for the test case will be calculated as follows:
|12||x > ans||5||x ≥ ans*0.93|
|10||x = ans||4||x ≥ ans*0.9|
|9||x ≥ ans − 1||3||x ≥ ans*0.8|
|8||x ≥ ans − 2||2||x ≥ ans*0.7|
|7||x ≥ ans − 3||1||x ≥ ans*0.5|
|6||x ≥ ans*0.95||0||x < ans*0.5|
If there are multiple conditions satisfied, then the maximum score of the conditions is taken.
Point Value: 30 (partial)
Time Limit: 5.00s
Memory Limit: 256M
Added: Jul 23, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3