← 返回题目列表

AtCoder · s8pc_3_h

H. 炸弹搜索游戏

中文机器翻译题面 查看原题
最高分数:$1500$ 积分

问题陈述

有一个 $50 \times 50$ 字段。第 $i$ 行和第 $j$ 列的单元格表示为 $(i, j)$(0 索引)。
有一天,square1001 在这一区域放置了价值 250 美元的炸弹。每个牢房内有 1 或 0 枚炸弹。
您想通过提出一些问题来了解炸弹在哪里。

这个问题你可以问很多次。
  • 你可以询问左上角单元格为$(a, b)$、右下单元格为$(c, d)$的矩形区域内的炸弹数量。

请找到所有炸弹的位置,询问尽可能少的问题。

注意:此问题的输入/输出类型比较特殊。请阅读输入/输出。如果你想使用 scanf/printf,你必须写 fflush(stdout).

输入和输出

第一行输入遵循以下格式:
$H\W\N\K$
  • $H, W$ 是字段大小。在此问题中,$H = 50$,$W = 50$。
  • $N$ 是战场上的炸弹数量。在此问题中,$N = 250$。
  • $K$ 是模数。该整数用于回答字段的状态。

输入此内容后,您可以按照以下输出格式提出一些问题:
$? \a\b\c\d$
意思是要询问左上角单元格为$(a, b)$、右下单元格为$(c, d)$的矩形区域内的炸弹数量。

您可以通过以下格式的输入知道问题的值:
$p$
$p$ 是您问题的结果。

最后,您必须按照以下格式输出答案:
$! \答$
$ans$ 的值为 $\sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod $K$。 注:$r_{i, j}$ 是单元格$(i, j)$ 中的炸弹数量。

约束

  • $H,W = 50$
  • $N = 250$
  • $1,000,000,000 \le K \le 1,000,010,000$($K$ 是随机的)

分数

判断中有5个测试用例。
每个测试用例中的 $score$ 由以下公式定义:
  • $Q$ 是问题数。
  • 如果 $Q > 2500$,$score = 0$(错误答案)。
  • 如果 $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)$。

样本输入、输出

在以下布置的情况下,该输入/输出是可以想象的。
这个案例是$H,W=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