H - Bombs Searching Game

Contest Duration: 2016-11-20(Sun) 11:15 - 2016-11-20(Sun) 14:15 (local time) (180 minutes)

H - Bombs Searching Game Editorial

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score:

1500

$1500$ Points

Problem Statement

There is a

50 \times 50

$50 \times 50$ field. The cell at

i

$i$ -th row and

j

$j$ -th column is denoted

(i, j)

$(i, j)$ (0-indexed).
One day, square1001 puts

250

$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)

$(a, b)$ and lower-right cell is

(c, d)

$(c, d)$ .

You can know the value of the question, from input in this format:

$p$

p

$p$ is the result of your question.

Finally, you have to output the answer following this format:

$! \ ans$

The value of

a n s

$ans$ is

\sum_{i = 0}^{H - 1} \sum_{j = 0}^{W - 1} r_{i, j} 2^{i W + j}

$\sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod

K

$K$ . Note:

r_{i, j}

$r_{i, j}$ is the number of bombs in cell

(i, j)

$(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

s c o r e

$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

$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

$1500$ 点

問題文

さて, このsquare869120Contest #3も, 最終問題となってしまった。
square1001氏は, 最終兵器として, あるダンジョンに爆弾を仕掛けた。
そのダンジョンは, 左上のマスが

(0, 0)

$(0,0)$ , 右下のマスが

(49, 49)

$(49,49)$ の

50 \times 50

$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)

$(a, b)$ , 右下のマス

(c, d)

$(c, d)$ の区間に存在する爆弾の数を聞くことである。

また, 質問の返答は, 以下のような出力で行われる。

$p$

p

$p$ は, 質問で聞いた区間に存在する爆弾の総数である。

また, 答えが分かった時に, 以下のような出力をしなければならない。

$! \ ans$

ただし,

a n s

$ans$ は以下の値であり,

r_{i, j}

$r_{i, j}$ は, マス

(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