問題一覧 > 通常問題

No.1429 Simple Dowsing

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 81
作問者 : 👑 evimaevima / テスター : mine691mine691
5 ProblemId : 5966 / 出題時の順位表
問題文最終更新日: 2021-03-14 13:32:12

問題文

ルンルンは、ホワイトデーにマシュマロ探知機をもらいました。

$100$ メートル四方の土地があり、この地下に黄金のマシュマロが $1$ 個埋まっています。
この土地の南西、南東、北西、北東の四隅の座標をそれぞれ $(0, 0), (100, 0), (0, 100), (100, 100)$ として、
黄金のマシュマロの座標を $(a, b)$ とすると、$a, b$ はどちらも $0$ 以上 $100$ 以下の整数であることが分かっています。
(黄金のマシュマロは小さいので、土地の境界線上に埋まっていることもあるようです。)

マシュマロ探知機の使い方は以下の通りです。

  • $p, q$ がどちらも整数であるような土地上の点 $(p, q)$ に立ち、ボタンを押す。($0 \leq p, q \leq 100$ でなければならない。)
  • すると、探知機の画面に整数 $d$ が表示される。これは、$(p, q)$ から黄金のマシュマロの位置 $(a, b)$ までの(ユークリッド)距離の二乗を表す。
  • ただし、探知機はボタンを $3$ 回押すと爆発するため、ボタンは $2$ 回までしか押してはならない。

ルンルンに探知機の使用と発掘の指示を送って、一度の発掘で黄金のマシュマロを手に入れさせてあげてください。

入出力

以下のように、標準出力に探知機の使用指示と発掘指示を送ってください。これらの記述に従わなかった場合のジャッジ結果は不定です。

  • 探知機の使用指示:
    ? $p$ $q$
    これは、点 $(p, q)$ に立って探知機のボタンを押すことを表します。ここで、$p, q$ はそれぞれ $0$ 以上 $100$ 以下の整数でなければなりません。
    探知機の画面に表示された整数 $d$($= (p - a)^2 + (q - b)^2$)は、以下のように標準入力に送られます。
    $d$
    探知機の使用指示を $3$ 回以上送ってはなりません。
  • 発掘指示:
    ! $r$ $s$
    これは、点 $(r, s)$ を発掘することを表します。ここで、$r, s$ はそれぞれ整数として出力してください。$(r, s) = (a, b)$ なら正解と判定されます。
    発掘指示はちょうど $1$ 回送り、その後ただちにプログラムを終了させてください。

注意:

  • 各指示の末尾には改行を入れ、指示を送るたびに標準出力を flush してください。そうしなかった場合のジャッジ結果は不定です。
  • 上記の二種類の指示のどちらの形式にも該当しない出力を行った場合も、ジャッジ結果は不定です。
  • 「ジャッジ結果が不定」とは、あらゆる結果があり得ることを意味します。
    (例えば、発掘指示を送らずにプログラムを終了すると、結果が Query Limit Exceeded となることがあります。)

サンプル

サンプル1
入力
5
0
出力
? 3 6
? 2 8
! 2 8

これは、黄金のマシュマロが点 $(2, 8)$ に埋まっている場合のやり取りの例です。ルンルンに送られた指示は以下の通りです。

  • 点 $(3, 6)$ に立って探知機のボタンを押せ。(画面には $5$ ($= (3 - 2)^2 + (6 - 8)^2$) と表示されました。)
  • 点 $(2, 8)$ に立って探知機のボタンを押せ。(画面には $0$ ($= (2 - 2)^2 + (8 - 8)^2$) と表示されました。)
  • 点 $(2, 8)$ を発掘せよ。(運良く一度の発掘で黄金のマシュマロを手に入れました。)

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