CF1368F Lamps on a Circle

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.

N/A

N/A

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.