H - Bombs Searching Game Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $1500$ Points

Problem Statement

There is a $50 \times 50$ field. The cell at $i$-th row and $j$-th column is denoted $(i, j)$ (0-indexed).
One day, square1001 puts $250$ bombs in this field. In each cell, there is 1 or 0 bomb.
You want to know where the bombs are by asking some questions.

You can ask this question many times.
  • You can ask the number of bombs in the rectangular area in which upper-left cell is $(a, b)$ and lower-right cell is $(c, d)$.

Please find all bombs' positions asking as few questions as possible.

Note: This problem Input/Output type is special. Please read Input/Output. If you want to use scanf/printf, you have to write fflush(stdout).

Input and output

The first line input is following this format:
$H \ W \ N \ K$
  • $H, W$ is field size. In this problem, $H = 50$ and $W = 50$.
  • $N$ is the number of bombs in the field. In this problem, $N = 250$.
  • $K$ is modulo. This integer uses to answer the state of the field.

After this input, You can ask some questions, following this output format:
$? \ a \ b \ c \ d$
It means that you want to ask the number of bombs in the rectangular area which upper-left cell is $(a, b)$ and lower-right cell is $(c, d)$.

You can know the value of the question, from input in this format:
$p$
$p$ is the result of your question.

Finally, you have to output the answer following this format:
$! \ ans$
The value of $ans$ is $\sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod $K$. Note: $r_{i, j}$ is the number of bombs in cell $(i, j)$.

Constraints

  • $H, W = 50$
  • $N = 250$
  • $1,000,000,000 \le K \le 1,000,010,000$ ($K$ is random)

Score

There are 5 testcases in the judge.
The $score$ in each testcase is defined by following formula:
  • $Q$ is the number of questions.
  • If $Q > 2500$, $score = 0$ (Wrong Answer).
  • If $930 \le Q \le 2500$, $score = max(\lfloor 125 - 3.2\sqrt{Q - 920} \rfloor, 40)$.
  • If $880 \le Q < 930$, $score = \lfloor 288 - 22\sqrt{Q - 870} \rfloor$.
  • If $Q < 880$, $score = min(2860 - 3Q, 300)$.

Sample Input・Output

In the case of the following arrangement, this input / output is conceivable.
This case is $H,W=4$, so this example is not include in testcases.
H=4, W=4, N=4
1001
0000
0010
0100
Example of Input・Output
Input from program Output
4 4 4 1000000007
? 0 0 0 1
1
? 0 1 0 2
0
? 0 3 1 3
1
? 2 1 3 2
2
? 2 2 2 2
1
! 9225
These question is not always meaningful.
Writer: E869120
配点： $1500$ 点

問題文

さて, このsquare869120Contest #3も, 最終問題となってしまった。
square1001氏は, 最終兵器として, あるダンジョンに爆弾を仕掛けた。
そのダンジョンは, 左上のマスが $(0,0)$, 右下のマスが $(49,49)$ の $50 \times 50$ の大きさである。

その中には, 250個の爆弾が仕掛けられている。位置はすべて違うマスである。
あなたは, 全ての爆弾の位置を知ることで, そのダンジョンから脱出できる。
「そんなん、どうやって知ればいいんだよ！　全く分かんねぇじゃないか！助けてぇぇぇぇぇ！」

しかし、あなたは以下の質問を何回かできる。
  • 左上のマス $(a, b)$, 右下のマス $(c, d)$ の区間に何個爆弾があるかを聞くことができる。

しかし, 質問回数が多くなればなるほど, 爆弾の爆発する確率が高くなり, すなわち生存確率が下がる。
そのため, できるだけ少ない質問回数で爆弾250個の配置を当ててほしい。(その方が得点が高い)
あなたの挑戦を待っている。

入出力

最初, 以下のように入力される。
$H \ W \ N \ K$
  • $H, W$ はダンジョンの大きさである。この問題では, $H, W = 50$ である。
  • $N$ はダンジョンの中に含まれる爆弾の数である。この問題では, $N = 250$ である。
  • $K$ は最終的な盤面の状態を出力するために使う整数である。
次に, 次のような質問を何回かすることができる。
質問は以下のような形式で出力することによってできる。
$? \ a \ b \ c \ d$
これは, 左上のマス $(a, b)$, 右下のマス $(c, d)$ の区間に存在する爆弾の数を聞くことである。

また, 質問の返答は, 以下のような出力で行われる。
$p$
$p$ は, 質問で聞いた区間に存在する爆弾の総数である。

また, 答えが分かった時に, 以下のような出力をしなければならない。
$! \ ans$
ただし, $ans$ は以下の値であり, $r_{i, j}$ は, マス $(i, j)$ にある爆弾の個数である。
  • $ans = \sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod $K$

制約

  • $H, W = 50$
  • $N = 250$
  • $1,000,000,000 \le K \le 1,000,01,000$ ($K$はランダムに与えられる)

得点

5つのテストケースがある。各テストケースに対する得点は, 以下のように計算される。
  • 質問回数を $Q$ とする。
  • $Q > 2500$ のとき, $0$ 点 (Wrong Answer) となる。
  • $930 \le Q \le 2500$ のとき, $score = max(\lfloor 125 - 3.2\sqrt{Q - 920} \rfloor, 40)$ となる。
  • $880 \le Q < 930$ のとき, $score = \lfloor 288 - 22\sqrt{Q - 870} \rfloor$ となる。
  • $Q < 880$ のとき, $score = min(2860 - 3Q, 300)$ となる。

入出力例1

例えば, 以下のような配置の場合、以下のような入出力が考えられる。
ただし, この場合 $H = W = 4, N = 4$ なので, 実際のテストケースには存在しない。
H=4, W=4, N=4
1001
0000
0010
0100
入出力として考えられる例
プログラムへの入力 プログラムの出力
4 4 4 1000000007
? 0 0 0 1
1
? 0 1 0 2
0
? 0 3 1 3
1
? 2 1 3 2
2
? 2 2 2 2
1
! 9225
ただし, 必ずしも意味のある質問をしているとは限りません。
また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されはします。
問題作成者: E869120