410720: GYM104090 I Guess Cycle Length

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Guess Cycle Lengthtime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

Grammy has a directed cyclic graph of $$$n$$$ vertices ($$$1\leq n\leq 10^9$$$) numbered from $$$1$$$ to $$$n$$$. A directed cyclic graph is a directed graph of $$$n$$$ vertices that form one cycle. Specifically, there are $$$n$$$ vertices and $$$n$$$ edges in the graph, and there exists a permutation $$$p_1,p_2,\ldots,p_n$$$ such that there is a one-way edge from $$$p_i$$$ to $$$p_{(i\bmod n)+1}$$$.

Initially, there is a token on a predetermined vertex.

You can ask Grammy to move the token in the following way:

"walk x" where $$$0 \leq x \leq 10^9$$$. In response to the query, Grammy will move the token through exactly $$$x$$$ edges and tell you the position of the token after moving.

You win if you guess the number of vertices in the hidden graph (number $$$n$$$) by making no more than $$$10^4$$$ queries.

The vertices in the graph and the initial position of the token are fixed in advance.

Interaction

You can make no more than $$$10^4$$$ queries. To make a query, output "walk x" ($$$0 \leq x \leq 10^9$$$) on a separate line, then you should read the response from standard input.

In response to the query, the interactor will move the token through exactly $$$x$$$ edges and output the position of the token after moving.

To give your answer, print "guess n" on a separate line, where $$$n$$$ is the size of the hidden graph ($$$1\leq n \leq 10^9$$$). The output of the answer is not counted towards the limit of $$$10^4$$$ queries.

After that, your program should terminate.

After printing a query, do not forget to output end of line and flush the output. To do this, use fflush(stdout) or cout.flush() in C++, System.out.flush() in Java, flush(output) in Pascal, or stdout.flush() in Python.

It is guaranteed that the vertices in the graph and the initial position of the token are fixed in advance.

ExampleInput

3

10

4

5

3

5
Output
walk 0

walk 1

walk 2

walk 3

walk 4

walk 6

guess 10

加入题单

上一题 下一题 算法标签: