Africa 2
Time limit1.357sMemory limit1357 MB
Submit code that matches the judge on exactly half its hidden test cases while passing the sample, a problem about exploiting judge behavior rather than a computable answer.
- Level
Hard9 of 10
- Topics
- Implementation, Brute force, Math, Combinatorics
- Solved
- No attempts yet
Problem
Africa, the first problem of Gudeokgi Cup 2018, was an easy problem: for a first problem, you only had to read it carefully to get accepted. Brian understood all the conditions in the statement, wrote his code right away, and when the sample input produced the sample output he submitted immediately, only to get "Wrong Answer".
Convinced his code could not be wrong, Brian assumed the judging system was at fault and submitted the same code several times, but the results did not change. In the end he shouted "Why WA when AC?" and complained to the setter, who gave him the (predictable) reply that the problem had no errors. The kind setter added some unnecessary information: his code printed the correct answer for exactly half of all test cases and the wrong answer for the other half. Also, no matter how many times it was judged, the result for each test case never changed.
Hearing this story, you became curious about what code he had submitted to produce such a beautiful situation. Can you reproduce that code?
Your program must satisfy all of the following.
- Given the sample input, it must be able to receive "Accepted!!".
- For exactly half of all judging data it must be correct and for the other half incorrect. Here incorrect means the output differs from the correct answer, and no time limit exceeded or similar may occur.
- The same input must always produce the same output. In other words, you may not use random functions or the like.
- The judging data is the same as what is being used or will soon be used to judge Africa. The number of judging data entries is guaranteed to be even.
The score is as follows.
- If the total number of data entries is 2n and the number of correct test cases is n±k, the score is 100-k points, and if you get 100 points while satisfying all the conditions above, your submission is accepted.
Input
The first line contains the number of input data entries N (1 ≤ N ≤ 8).
Then N lines follow, one word per line. Each input word is one of the following eight, and no word is given more than once. botswana, ethiopia, kenya, namibia, south-africa, tanzania, zambia, zimbabwe
Output
Output the answer to the problem. All information needed to solve the problem is based on what this problem presents.