루미 알고리즘

#1391다이아Iterated Quiz

PO 2016 훈련 캠프코딩출제 Emanuel Gedin, Simon Lindholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
191 ≤ N ≤ 10, M must be at most 2^N.
2111 ≤ N ≤ 1000, M must be at most 2N.
3151 ≤ N ≤ 1000, M must be at most N + 2.
465N = 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.

출처 표기

출처: Programmeringsolympiaden 2016년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.