AT_s8pc_3_h.爆弾ゲーム

终于到了 square869120Contest #3 的最后一题。
square1001 在一个地牢内布置了炸弹。
地牢的形状是一个 $50 \times 50$ 的网格，左上角为 $(0,0)$，右下角为 $(49,49)$。

在这个地牢中，有 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$ 的计算方法是：

• $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 个测试用例。每个测试用例的评分标准如下：

• 询问次数记为 $Q$。
• 若 $Q > 2500$ 则得分为 0 分 (错误答案)。
• 若 $930 \le Q \le 2500$ 则得分计算为 $score = \max(\lfloor 125 - 3.2\sqrt{Q - 920} \rfloor, 40)$。
• 若 $Q < 880$ 得分为满分。

输入输出示例

譬如，以下是一种可能的地牢配置：

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

注意，这些询问可能不是最佳的，并且通常还不足以完全确定地牢内的所有炸弹位置。

本翻译由 AI 自动生成