Hide

Problem M
Sequence Guessing

You are tasked with creating a secret sequence of integers that is difficult to guess.

The sequence is subject to the following constraints:

  • The first number in the sequence must be $0$.

  • The last number in the sequence must be $100\, 000$.

  • Each number in the sequence must be either $1$ or $2$ greater than the one preceding it.

At first, all you need to reveal is the length of the sequence.

Then, an adversary will guess the numbers in the sequence one at a time.

  • If the guessed number is in your sequence, you must reveal exactly where in the sequence it appears.

  • If the guessed number is not in your sequence, you must simply reveal that it is not in the sequence. This is considered a “miss”.

Note that because you are not forced to write down the sequence in advance, you can “cheat” by changing the sequence you have in mind, so long as it does not contradict the information you have revealed so far. It turns out that under these conditions, you can always force the adversary to get $33\, 333$ misses before they can guess every number in your sequence. Your job is to write a program that does so.

Interaction

This is an interactive problem.

Your program should begin by printing $k$ $(2 \leq k \leq 100\, 001)$, the length of your sequence, as a single integer on a single line. After this, you will receive one integer $x$ on a single line. This integer is guaranteed to be between $-1$ and $100\, 000$ inclusive.

  • If $x = -1$, the adversary has given up; your program should print all $k$ integers in your sequence in order, one line per integer, and then exit. The adversary is guaranteed to give this input after it has gotten $33\, 333$ misses, though it may do so earlier. After printing all $k$ integers, your program should exit. If you print a valid sequence consistent with your previous responses, your submission will be considered correct for this test case.

  • If $x$ is not in your sequence, print $-1$ on a single line.

  • If $x$ is in your sequence, print a single integer $i$ on a single line, such that $x$ is the $i$th (1-indexed) number in the sequence. If you have printed every integer from $1$ to $k$, your program should now exit, and your submission will receive a Wrong Answer verdict.

Do not forget to flush the output after every integer you print.

After this, if your program has not yet exited, the process will repeat, with you receiving another single integer. The adversary is guaranteed to never repeat integers.

The adversary may employ different guessing strategies on different runs.

Read Sample Interaction 1 Write
50001
0
1
1
-1
-1
0
2
<omitted 49997 lines for brevity>
99998
100000

Please log in to submit a solution to this problem

Log in