Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
ある日、京都大学の地下の調査によって、今は失われし古の超技術が使われた競プロ装置が発掘されました。
この装置に、一つの正整数が答えである競技プログラミングの問題と正整数 q を入力するとその競技プログラミングの問題の答えを q で割った余りが出力されます。
ただし、この装置の出力は古の文字で書かれているため、出力が偶数か奇数かしか判別することができません。
あなたはこの装置を使って、答えが 1\leq X \leq 10^9 を満たす正整数 X であり、長年誰にも解かれていない競技プログラミングの問題を解くことにしました。
ただし、この装置を使う度に京都大学に膨大な使用料を払う必要があり、使える資金に余裕がないため装置の使用回数は 30 回以下にして、 X を求めてください。
入出力
この問題では最初に与えられる入力は無い。
解答プログラムは次の形式の出力をすることで競プロ装置を利用できる。
? q
ここで q は 1 \leq q \leq 10^9 を満たす正整数で競プロ装置に入力される。末尾には改行を出力せよ。
次に、競プロ装置の出力を表す文字列が以下の形式で与えられる。
r
r は even
または odd
である。意味は次のとおりである。
even
のとき、 X を q で割った余りは偶数である。odd
のとき、 X を q で割った余りは奇数である。
上記の競プロ装置の利用回数の上限は 30 回である。 30 回を超えて ? q
の形式の出力をした場合は Query Limit Exceeded となる。
何回か競プロ装置を利用した後、あなたは問題の解 X を当てる。あなたが問題の解であると思う値を answer とすると、
! answer
というフォーマットで出力する。末尾には改行を出力せよ。解を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。
また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。
各出力の後には、出力をフラッシュする必要があることに注意せよ。例えば C/C++ では競プロ装置の利用の際 q を
printf("? %d\n", q); fflush(stdout);
と出力すればよい。
制約
- 1 \leq X \leq 10^9
- 1 \leq q \leq 10^9
- X, q は整数
- 競プロ装置の利用は 30 回までしか行えない。
入出力例
X = 3 である場合に、以下のような入出力が考えられる。
解答プログラムの出力 | 解答プログラムへの入力 | 説明 |
---|---|---|
? 1 | 競プロ装置に 1 を入力して使用する | |
even | X を 1 で割った余りは 0 で、これは偶数である | |
? 2 | 競プロ装置に 2 を入力して使用する | |
odd | X を 2 で割った余りは 1 で、これは奇数である | |
? 5 | 競プロ装置に 5 を入力して使用する | |
odd | X を 5 で割った余りは 3 で、これは奇数である | |
! 3 | X は 3 であると解答している |
これは入出力の一つの例であり、意味のある入出力をしているとは限らない。