問題一覧 > 通常問題

No.1187 皇帝ペンギン

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 140
作問者 : penguinmanpenguinman / テスター : kaagekaage
18 ProblemId : 4876 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-17 05:39:23

お知らせ

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

問題文

Penguinmanはとても優しいので、滅多に怒りません。そこで、ムシャクシャしているあなたは、Penguinmanを叩くことでストレスを発散することにしました。

Penguinmanが怒るかどうかには、以下の基準が存在します。

  • ある $1$ 以上 $10^3$ 以下の整数 $N$ が存在し、 $N$ 回以上叩かれた場合必ず怒り出す。
  • Penguinmanは $2$ 以上 $10^9$ 以下の整数 $D$ が嫌いなので、最終的に叩かれた回数が $D$ の正の整数倍だと、 $N$ との大小に関係なく怒り出す。
  • 上記の $2$ つの条件のどちらにも当てはまらない場合に限り、怒らない。

Penguinmanは怒ると怖いので、あなたは怒らないようにするため予め「最終的に叩かれた回数が $X$ 回だと怒り出しますか?」という質問をすることで叩ける回数を探ることにしました。

Penguinmanは忙しいので、質問する回数は限られています。具体的には $25$ 回までしか質問することができません。

質問を何回か行うことで、あなたがPenguinmanを叩ける回数の最大値を求めてください。

制約

  • $1≤N≤10^3$
  • $2≤D≤10^9$
  • $N,D$ は整数

入出力

提出されたプログラム(以下、提出プログラムと呼ぶ)は、以下の $2$ 種類のクエリのみからならなければならない。

  1. 質問クエリ
  2. \(?\) \(X\)

    上記のフォーマットで出力する必要がある。これは、「最終的に $X$ 回叩いた場合、あなたは怒り出しますか?」というPenguinmanへの質問であり、 $0\leq X\leq 10^9$ を満たす必要がある。

    これに対して、ジャッジ側のプログラム(以下、ジャッジプログラムと呼ぶ)は以下の $2$ 種類の回答のうちどちらかを標準入力から与える。

    • "out"。これは最終的にPenguinmanを $X$ 回叩いた場合、Penguinmanが怒り出すことを表す。
    • "safe"。これは最終的にPenguinmanを $X$ 回叩いた場合、Penguinmanは怒り出さないことを表す。
  3. 回答クエリ
  4. \(!\) \(X\)

    上記のフォーマットで出力する必要がある。これは、「Penguinmanを叩ける回数の最大値は $X$ である」という、テストケースに対する答えを表す。

    この場合も $0\leq X\leq 10^9$ を満たす必要がある。

注意点

  • 出力のあと、標準出力を flush せよ。従わない場合 TLE の可能性がある。
  • 回答クエリを出力した後、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は定義されていない。
  • 送られたクエリが前記の条件を満たしていない場合、ジャッジプログラムと提出プログラムのやり取りは自動的に打ち切られる。この場合のジャッジの挙動も定義されていない。
  • この問題では初めに与えられる入力はない。よって、提出プログラム側がクエリを送ることでジャッジプログラムとのやり取りが始まる。
  • 回答クエリは質問の回数には含めない。

サンプル

サンプル1
提出プログラムの出力
? 1
? 2
? 3
? 4
? 5
? 6
! 3
ジャッジプログラムの出力
safe
out
safe
out
out
out

この場合の $N,D$ はそれぞれ $4,2$ 、或いは $5,2$ です。一意には定まりません。

叩ける回数の最大値は $3$ であるため、回答クエリで $3$ を出力しています。

この提出は AC となります。

サンプル2
提出プログラムの出力
? 1
? 2
? 3
? 4
? 5
! 0
ジャッジプログラムの出力
out
out
out
out
out

この場合の $N$ は $1$ であり、$D$ の値は一意には定まりません。

叩ける回数の最大値は $0$ であるため、回答クエリで $0$ を出力しています。

この提出は AC となります。一回も叩けない、即ち $0$ 回しか叩けない場合があることに注意してください。

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