Problem G
Going in Circles
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 $3n+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$.”
Interaction
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 $3n+500$ steps1 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 $3n+500$ queries will result in a wrong answer verdict.
A testing tool is provided to help you develop your solution.
| Read | Sample Interaction 1 | Write |
|---|
0
? right
1
? right
1
? right
0
? flip
1
? left
1
? left
1
? left
1
! 3
Footnotes
- Note that $n$ is the actual number of train carriages in the current test case, not the maximum possible number of train carriages.
