最高分数:$1500$ 积分
有一天,square1001 在这一区域放置了价值 250 美元的炸弹。每个牢房内有 1 或 0 枚炸弹。
您想通过提出一些问题来了解炸弹在哪里。
这个问题你可以问很多次。
请找到所有炸弹的位置,询问尽可能少的问题。
注意:此问题的输入/输出类型比较特殊。请阅读输入/输出。如果你想使用
问题陈述
有一个 $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 |