問題一覧 > 通常問題

No.2962 Sum Bomb Bomber

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

ストーリー

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

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

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

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

問題文

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

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

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

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

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

    制約

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

    • 入出力

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

    NN

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

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

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

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

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

    • 注意点

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

    • サンプル

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

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