Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Интерактивные задачи

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

23/12/2015 | Задачи NEERC 2015 (J) |

*Ограничения: время – 2s/4s, память – 256MiB Ввод: интерактивная задача Вывод: интерактивная задача*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Consider a toy interactive problem `"OneMax"` which is defined as follows.
You know an integer `n` and there is a hidden bit string `S` of length `n`.
The only thing you may do is to present the system a bit string `Q` of length `n`,
and the system will return the number `"OneMax"(Q)` –
the number of bits which coincide in `Q` and `S` at the corresponding positions.
The name of OneMax problem stems from the fact that this problem is simpler to explain
when `S\ =\ 111…11`, so that the problem turns into maximization `"Max"`) of the number of ones (`"One"`).

When `n` is even, there is a similar (but harder) interactive problem called `"Jump"`.
The simplest way to describe the `"Jump"` is by using `"OneMax"`:

`"Jump"(Q)\ =\ {\ (("OneMax"(Q),"if"\ "OneMax"(Q)\ =\ n\ or\ "OneMax"(Q)\ =\ n//2),(0,"otherwise")):}`.

Basically, the only nonzero values of `"OneMax"` which you can see with `"Jump"`
are `n` (which means you've found the hidden string `S`) and `n//2`.

Given an even integer `n` – the problem size, you have to solve the `"Jump"` problem
for the hidden string `S` by making interactive `"Jump"` queries.
Your task is to eventually make a query `Q` such that `Q\ =\ S`.

First, the testing system tells the length of the bit string `n`.
Then, your solution asks the queries and the system answers them as given by the \textsc{Jump} definition.
When a solution asks the query `Q` such that `Q\ =\ S`, the system answers `n` and terminates,
so if your solution, after reading the answer `n`, tries reading or writing anything, it will fail.

The limit on the number of queries is `n\ +\ 500`. If your solution asks a `(n\ +\ 501)`-th query,
then you will receive the "Wrong Answer" outcome.
You will also receive this outcome if your solution terminates too early.

If your query contains wrong characters (neither 0, nor 1),
or has a wrong length (not equal to `n`), the system will terminate the testing and you will receive
the "Presentation Error" outcome.

You will receive the "Time Limit Exceeded" outcome and other errors for the usual violations.

Finally, if everything is OK (e.g. your solution finds the hidden string) on every test,
you will receive the "Accepted" outcome, in this case you will have solved the problem.

The first line of the input stream contains an even number `n` (`2\ ≤\ n\ ≤\ 1000`).
The next lines of the input stream consist of the answers to the corresponding queries.
Each answer is an integer – either `0`, `n/2`, or `n`. Each answer is on its own line.

To make a query, print a line which contains a string of length `n` which consists of characters
0 and 1 only. Don't forget to put a newline character and to flush
the output stream after you print your query.

Sample Input

2 1 0 1 2

Sample Output

01 11 10 00