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 自动生成**

无

无

### 制約 - $ 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 $Q ### 入出力例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 ただし, 必ずしも意味のある質問をしているとは限りません。 また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されはします。