26180번 - Going in Circles 다국어인터랙티브

문제

Hercule Poirot, world-renowned detective, was having a lovely cup of tea in his compartment on the Disorient Express when the train conductor rushed in. "We have lost track of the number of train carriages," exclaimed the conductor. You see, this was no ordinary train, and had no first or last train carriage. Instead, the train carriages were connected to form a large cycle, causing the conductor's confusion.

Hercule thought for a moment. "That is most peculiar," he said. "But I may be able to help you." He reached over and grabbed the lamp from the side table. "You see, each train carriage has a light switch like this one. By moving between the carriages and toggling these switches, we can determine the number of train carriages."

The conductor was sceptical, but agreed to try it. "We are in a hurry," he said, "so please determine $n,ドル the number of carriages that the train consists of, in at most 3ドルn+500$ steps." Here a step counts as either moving to an adjacent carriage or toggling a light switch in the current carriage. "The only thing I am certain of is that $n$ is at least 3ドル$ and at most 5000ドル$."

입력

출력

제한

인터랙션

This is an interactive problem. Your submission will be run against an interactor, which reads the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

The interactor first sends an integer $s$ ($s \in \{0,1\}$), the state of the light switch in Hercule's initial carriage.

Your submission may then send at most 3ドルn+500$ steps¹ for Hercule to carry out, each by printing one line of the form "? $a$", where $a$ is one of the following:

• "left", to move to the adjacent train carriage in the clockwise direction,
• "right", to move to the adjacent train carriage in the counter-clockwise direction, or
• "flip", to toggle the light switch in the current train carriage.

After every step, the interactor replies with an integer $s$ ($s \in \{0,1\}$), the state of the light switch in the train carriage that Hercule is currently in, after he has carried out the requested step.

When you have determined the number of train carriages $n,ドル print one line of the form "! $n$" (3ドル \leq n \leq 5000$), after which the interaction will stop. Printing the answer does not count as a query.

The interactor is not adaptive; the initial state of the light switches is determined by the interactor before any interaction takes place. Make sure you flush the buffer after each write. Using more than 3ドルn+500$ queries will result in a wrong answer verdict.

A testing tool is provided to help you develop your solution.

¹Note that $n$ is the actual number of train carriages in the current test case, not the maximum possible number of train carriages.

노트

첨부

• testing_tool.py