Lamps on a Circle
Contest: Codeforces Global Round 8
Difficulty rating: 2600
Tags: games, implementation, interactive, math

This is an interactive problem.

John and his imaginary friend play a game. There are $$$n$$$ lamps arranged in a circle. Lamps are numbered $$$1$$$ through $$$n$$$ in clockwise order, that is, lamps $$$i$$$ and $$$i + 1$$$ are adjacent for any $$$i = 1, \ldots, n - 1$$$, and also lamps $$$n$$$ and $$$1$$$ are adjacent. Initially all lamps are turned off.

John and his friend take turns, with John moving first. On his turn John can choose to terminate the game, or to make a move. To make a move, John can choose any positive number $$$k$$$ and turn any $$$k$$$ lamps of his choosing on. In response to this move, John's friend will choose $$$k$$$ consecutive lamps and turn all of them off (the lamps in the range that were off before this move stay off). Note that the value of $$$k$$$ is the same as John's number on his last move. For example, if $$$n = 5$$$ and John have just turned three lamps on, John's friend may choose to turn off lamps $$$1, 2, 3$$$, or $$$2, 3, 4$$$, or $$$3, 4, 5$$$, or $$$4, 5, 1$$$, or $$$5, 1, 2$$$.

After this, John may choose to terminate or move again, and so on. However, John can not make more than $$$10^4$$$ moves.

John wants to maximize the number of lamps turned on at the end of the game, while his friend wants to minimize this number. Your task is to provide a strategy for John to achieve optimal result. Your program will play interactively for John against the jury's interactor program playing for John's friend.

Suppose there are $$$n$$$ lamps in the game. Let $$$R(n)$$$ be the number of turned on lamps at the end of the game if both players act optimally. Your program has to terminate the game with at least $$$R(n)$$$ turned on lamps within $$$10^4$$$ moves. Refer to Interaction section below for interaction details.

For technical reasons hacks for this problem are disabled.

Interaction format:
Initially your program will be fed a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of lamps in the game. Then the interactor will wait for your actions.

To make a move, print a line starting with an integer $$$k$$$ ($$$1 \leq k \leq n$$$), followed by $$$k$$$ distinct integers $$$l_1, \ldots, l_k$$$ ($$$1 \leq l_i \leq n$$$) — indices of lamps you want to turn on. The indices may be printed in any order. It is allowed to try to turn on a lamp that is already on (although this will have no effect).

If your move was invalid for any reason, or if you have made more than $$$10^4$$$ moves, the interactor will reply with a line containing a single integer $$$-1$$$. Otherwise, the reply will be a line containing a single integer $$$x$$$ ($$$1 \leq x \leq n)$$$, meaning that the response was to turn off $$$k$$$ consecutive lamps starting from $$$x$$$ in clockwise order.

To terminate the game instead of making a move, print a line containing a single integer $$$0$$$. The test will be passed if at this point there are at least $$$R(n)$$$ lamps turned on (note that neither $$$R(n)$$$, nor the verdict received are not communicated to your program in any way). This action does not count towards the number of moves (that is, it is legal to terminate the game after exactly $$$10^4$$$ moves).

To receive the correct verdict, your program should terminate immediately after printing $$$0$$$, or after receiving $$$-1$$$ as a response.

Don't forget to flush your output after every action.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
When $$$n = 3$$$, any John's move can be reversed, thus $$$R(3) = 0$$$, and terminating the game immediately is correct.

$$$R(4) = 1$$$, and one strategy to achieve this result is shown in the second sample case.

Blank lines in sample interactions are for clarity and should not be printed.

Example input:
3

Example output:
0

Example input:
4

1

Example output:
2 1 3

0

Editorial:
Let try to come up with an upper bound on $$$R(n)$$$. Let $$$x$$$ be the number of currently turned on lamps. Consider our last move that resulted in increasing $$$x$$$ (after the response was made), and suppose it turned on $$$k$$$ lamps. If the opponent could then find a segment of $$$k$$$ consecutive lamps and turn them off, the move could be reverted. From this we can conclude that $$$x$$$ could not be too large.
Indeed, after the move $$$x + k$$$ lamps should have been divided into segments of length at most $$$k - 1$$$ each (since the opponent couldn't turn $$$k$$$ lamps off), separated by turned off lamps. The number of segments should have been at least $$$\frac{x + k}{k - 1}$$$, and the same bound applies to the number of separating lamps. Thus we must have had $$$x + k + \frac{x + k}{k - 1} \leq n$$$. After some boring transformations we obtain $$$x \leq n - k - \frac{n}{k} + 1$$$. It follows that $$$x$$$ can not be increased past this threshold with turning on $$$k$$$ lamps.
This implies that $$$x$$$ can not be increased past $$$\max_k \left(n - k - \frac{n}{k} + 1\right)$$$ with any move, thus $$$R(n) \leq \max_k \left(n - k - \left\lceil\frac{n}{k}\right\rceil + 1\right)$$$.
On the other hand, let's take such a $$$k$$$ that maximizes $$$n - k - \left\lceil\frac{n}{k}\right\rceil + 1$$$, and adopt the following strategy:
• Pick $$$\left\lceil\frac{n}{k}\right\rceil$$$ lamps that divide the circle into segments of length $$$\leq k - 1$$$ each, and never turn these lamps on. We can choose these lamps greedily at distance $$$k$$$ from each other, until we go full circle (at that point the distance from the last to the first lamp may be less than $$$k$$$).
• On each move, turn on any $$$k$$$ lamps except for the forbidden ones. Since the turned on lamps never form a segment of length $$$k$$$, we will successfully increase $$$x$$$ with this move.
• We stop once there are less than $$$k$$$ non-forbidden lamps to turn on. At this point we will have $$$x \geq n - \left\lceil\frac{n}{k}\right\rceil - k + 1$$$, thus $$$R(n)$$$ can not be less than this value.
We've determined that $$$R(n) = \max_k \left(n - k - \left\lceil\frac{n}{k}\right\rceil + 1\right)$$$, and provided a quite simple strategy to achieve this result. For large $$$n$$$, the maximum is attained at $$$k \approx \sqrt{n}$$$, thus $$$R(n) \approx n - 2\sqrt{n}$$$.