問題一覧 > 通常問題

No.2962 Sum Bomb Bomber

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 52
作問者 : Sinonen / テスター : 遭難者
ProblemId : 11524 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-16 16:11:30
コンテストの他の問題:

ストーリー

またまた、スイカ畑に爆弾が隠されてしまいましたが、今度は違う能力でオートサーチして対処しましょう。

探査機も直接的なものになっています。

できるだけスイカを守るため、そして、安全にするためご協力をお願いします。

ここらへんでトラウマおいておきますね。Cos Bomb Crasher (これのせいでなんか責められました。)

問題文

点 $A$ と点 $B$ のマンハッタン距離を $\text{dist}(A,B)$ と記すことにします。

$N$ 個の格子点 $D_i(1\leq i \leq N)$ があり、それぞれの座標は $(x_i,y_i)$ です。$N$ は与えられますが、それぞれの座標は与えられません。

次のクエリを $300$ 回まで尋ねることが出来ます。

  • 格子点$A$を選ぶ。$\sum_{i=1}^{N}\text{dist}(A,D_i)$ が与えられる。

    • このクエリを用いて、格子点の中で $\sum_{i=1}^{N}\text{dist}(A,D_i)$ が最小となる格子点$A$を求めてください。ただし正解が複数ある場合はその中の $1$ つを求めれば正解となります。

    制約

  • $1 \leq N \leq 100$
  • $N$ は整数
  • $-10^8 \leq x_i,y_i \leq 10^8(1\leq i \leq N)$
  • $D_i(1\leq i \leq N)$は格子点
  • それぞれの座標はテストケース毎に固定である。つまり、クエリ内容によって座標が変動することはない。

    • 入出力

    まず始めに$N$が与えられます。 

    $N$

    $A$の座標を $(x,y)$ でクエリを送る際は、以下の様に出力してください。 
    $1$ $x$ $y$

    ただし、以下の制約を満たす必要があります。
  • $-10^9 \leq x,y \leq 10^9$
  • $A$は格子点

    • クエリの答えを $d$ とすると以下の形で与えられます。 
    $d$

    答えの座標をを $(x,y)$ で出力する際は、以下の様に出力してください。 
    $2$ $x$ $y$

    ただし、以下の制約を満たす必要があります。
  • $-10^9 \leq x,y \leq 10^9$
  • 答えの点は格子点

    • 注意点

  • 各出力のたびに末尾改行と出力の flush をしてください。そうしなかった場合、ジャッジ結果がTLEやWAになる可能性があります。
  • 不正な出力や動作に対するジャッジは不定です。余分な空白や改行などを出力しないよう注意してください。
  • 答えの座標を出力した場合、すぐにプログラムを終了してください。終了しなければジャッジ結果は不定です。
  • 解答の出力はクエリ回数に含まれません。

    • サンプル

    以下は一例です。
    プログラム側の出力ジャッジ側の出力説明
    1まず、始めに $N$ が渡されます。このとき、ジャッジ側では $(x_1,y_1)=(1,0)$ を隠し持っています。
    1 2 3クエリとして $(x_A,y_A)=(2,3)$ をジャッジ側に送りました。
    4$\text{dist}(A,D_1)=4$ なので $4$ が与えられます。
    1 1 0クエリとして $(x_A,y_A)=(1,0)$ をジャッジ側に送りました。
    0$\text{dist}(A,D_1)=0$ なので $0$ が与えられます。
    2 1 0答えとして $(1,0)$ を出力しました。これ以上小さくすることができないので正解となります。

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