영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Ann Britt-Caroline is playing a game against Daniel. Daniel has asked Ann N yes-or-no questions, which she now must answer. However, the questions are seemingly impossible to answer, e.g.
- What is the airspeed velocity of an unladen swallow?
- Is the statement “This statement is false” true?
- Is P = NP?
- ...
Very hard questions indeed. To make the game a bit more fun (and to put the Iterated in Iterated Quiz), Daniel allows Ann to answer all the questions many times. For a number of rounds, she will answer all of the N questions simultaneously. Daniel will then tell her how many questions she got right.
The goal of the game is to use as few rounds as possible to answer all the questions correctly. Help her play Iterated Quiz against Daniel!
Interaction
First, your program should read the number N (1 ≤ N ≤ 1000), the number of questions.
When you want to make a guess for the questions, print a string of length N, consisting of 0's or 1's. The i:th character being 1 means that you guess that the answer to question i is yes, and 0 means that you guess that the answer is no.
Then, your program should read an integer, the number of questions that you guessed correctly.
If your guess is entirely correct, the judge will stop your program and you will have solved the current testcase.
Make sure to flush the output after each query, otherwise you may get a Time Limit Exceeded. In C++, this can be done for example with cout << flush; or fflush(stdout);, in Python with stdout.flush() and in Java with System.out.flush();.
To facilitate the testing of your solution, we provide a simple tool that you can download. See “attachments” at the bottom of the Kattis problem page. Refer to the comment at the top of the file for a description of how it can be used.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
Let M be the number of rounds your program needs to answer all the questions correctly.
| Group | Points | Constraints |
|---|---|---|
| 1 | 9 | 1 ≤ N ≤ 10, M must be at most 2^N. |
| 2 | 11 | 1 ≤ N ≤ 1000, M must be at most 2N. |
| 3 | 15 | 1 ≤ N ≤ 1000, M must be at most N + 2. |
| 4 | 65 | N = 1000, M must be at most N. |
For group 4, the scoring works as follows. Assume that your program needs M rounds in the worst case.
If M ≥ 1000, you will get 0 points. Otherwise, you will score
65 · min { 1, (1000-M)/(1000-420) }
points on the group. In other words, your score increases linearly as the number of rounds decreases from 1000 to 420. If you never use more than 420 rounds, you will get 65 points on group 4.
Explanation of the sample
Suppose that the correct answer to all questions is 1101. In the first guess, questions 1 and 3 are correctly guessed. In the second guess, all questions but question 4 have been correctly guessed. The last guess is entirely correct, and therefore the interaction ends.