問題一覧 > ネタ問題

No.3093 Please GCD

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 18
作問者 : PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan
1 ProblemId : 7746 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-01 22:51:54

注意

この問題は、インタラクティブ形式の問題です。

また、非常に高い確率(具体的には $99$% 以上)で $1$ 回の提出で AC できることが保証されています。ジャッジの負担となるため、連投はお控えください。

問題文

PCT 君は $1$ 以上 $N$ 以下のある正整数 $X$ を持っています。

あなたは以下の形式の質問を PCT 君にすることができます。

  • $1$ 以上 $N$ 以下のある正整数 $Y$ を聞く。PCT 君からは、$\mathrm{GCD}(X,Y)$ が返ってくる。

PCT 君の持っている正整数を当ててください。

入力

$N$

  • 入力は全て整数である。
  • $1 \le N \le 10^4$

入出力

最初に、整数 $N$ を標準入力から受け取ってください。

$N$

次に、質問クエリと回答クエリの送信方法を示します。

質問クエリ

? Y

PCT 君に整数 $Y$ で質問することを示すクエリです。

このクエリは合計 $600$ 回までしか行うことができません。

このクエリに対する解答は、以下のように標準入力に与えられます。

S

ここで、S とは以下のうちいずれかです。

  • 質問回数が $600$ 回以下の時、S は $\mathrm{GCD}(X,Y)$ です。
  • 質問回数が $600$ 回より多い場合、S は $-1$ です。

解答クエリ

! Z

PCT 君の持っている整数とあなたが予想したものを出力するクエリです。このクエリが出力された後、プログラムを直ちに終了してください。

注意

  • 出力のあと、標準出力を flush してください。
  • 解答クエリは、質問クエリの回数に含めません。
  • 上記を満たさない場合、ジャッジの挙動は不定です。
  • この問題のジャッジは適応的である可能性があります。つまり、ジャッジは今までの返答と整合性が取れる限り、PCT 君の持っている整数を変更する可能性があります。

サンプル

サンプル1
入力
5
3
出力
? 3
! 3

この場合、PCT 君の持っている整数は $X=3$ です。

質問クエリで $Y=3$ を聞かれたため、$\mathrm{GCD}(X,Y)=3$ が標準入力に与えられます。

解答クエリの $Z=3$ は、PCT 君の持っている整数と一致しているため、この場合 AC が与えられます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。