P9269 [CEOI 2013] 新宝岛 / Treasure

翻译自 [CEOI 2013 Day 1](https://ceoi2013.hsin.hr/tasks/tasks_day1.pdf)。 **这是一道 IO 交互题。** 一次地震过后，亚得里亚海出现了一座新岛。在岛上发现了一个特殊装置，名叫“神谕”。尽管没有说明手册，但考古学家和计算机专家的队伍成功地理解了它的行为。 神谕提供了一些有关该岛宝藏位置的信息。该岛被分为一个 $N$ 行 $N$ 列的网格，其中行和列都从 $1$ 到 $N$ 编号。网格中的一些单元格包含宝藏。神谕只会回答以下形式的问题：“给定网格中的一个矩形，在这个矩形中，有多少个单元格包含宝藏？” **尽管神谕可以回答所有大小的矩形问题，但发现请求的信息越具体（矩形越小），神谕在回答时消耗的能量越多**。更精确地说，如果一个矩形包含 $S$ 个单元格，则神谕将使用 $1 + N \times N - S$ 个单位的能量来回答。

编写一个程序，通过与神谕交互的方式，确定该岛上所有含有宝藏的单元格的位置。我们不希望在此过程中使用过多的能量，能量使用越少越好。但是也不要求使用的能量数量是最小的，具体得分规则见最后的“说明/提示”。 这是一个交互式任务。您的程序使用标准输出向神谕提问，并通过读取标准输入来获得答案。 - 在程序开始时，它应该读取一个整数 $N$（$2 \leq N \leq 100$），表示网格的大小。 - 要向神谕提问，您的程序应输出一行包含 $4$ 个整数 $R_1$、$C_1$、$R_2$ 和 $C_2$，它们之间由空格分隔，使得 $1 \leq R_1 \leq R_2 \leq N$ 和 $1 \leq C_1 \leq C_2 \leq N$ 成立。如果条件不成立或行格式不正确，则您的程序在该测试运行中将得零分。 - 神谕将响应一个包含单个整数的行 - 包含宝藏的矩形中提供的单元格数。更确切地说，是 $R_1 \leq R \leq R_2$ 且 $C_1 \leq C \leq C_2$ 且位于行 $R$、列 $C$ 的单元格包含宝藏的单元格数（$R$，$C$）。 - 当程序完成提问（已经确定所有宝藏的位置）后，它应在新的一行上输出 `END`。然后，再输出 $N$ 行，每行包含 $N$ 个 `0` 或 `1` 字符的字符串。第 $R$ 行中的第 $C$ 个字符是 `1`，如果该行中列 $C$ 的单元格中有宝藏，则为 `0`，如果没有，则为 `1`。行从顶部到底部编号为 $1$ 到 $N$，列从左到右编号。一旦您的程序输出解决方案，程序的执行将会自动终止。 为了与评分器正确交互，需要在每个问题和写出解决方案后**刷新标准输出**，这是交互题的惯例。 在每个测试运行中，可以假定神谕必然正确回答问题，并且在交互之前宝藏的位置是确定的。换句话说，答案不会取决于程序先前问的问题（不会根据你问的问题来改变答案），它在每个测试点都是固定的。

该任务是一个交互式任务。要成功完成任务，需要编写一个程序以最大化降低向神谕提问的次数和使用的能量。在程序开始时，输入岛屿的大小 $N$。

通过输出行号和列号的方式向神谕询问包含宝藏的单元格数量。每当程序获得答案后，就要输出 `END`，然后将宝藏位置汇总并输出。最终得分将由程序使用的能量数量确定。具体评分标准在题目的最后面，具体格式可见输入输出的一组样例。

[样例解释](https://www.luogu.com.cn/paste/tpzc0qdt) 每个测试用例得分为 $10$ 分。如果程序的输出不正确，则该测试用例得零分。否则，根据神谕使用的总能量单位 $K$ 来确定分数。 具体而言: - 如果 $K ≤ \frac{7}{16} N^4 + N^2$，则得 $10$ 分。 - 否则，如果 $K ≤ \frac{7}{16} N^4 + 2N^3$，则得 $8$ 分。 - 否则，如果 $K ≤ \frac{3}{4} N^4$，则得 $4$ 分。 - 否则，如果 $K ≤ N^4$，则得 $1$ 分。 - 否则，得 $0$ 分。 此外，在至少占总分 $40\%$ 的测试数据中，$N$ 将最多为 $20$。 总而言之，**花费的能量越少，你的得分就越高**。 交互库/SPJ 提供者：@[Sprague_Garundy](https://www.luogu.com.cn/user/764746) 。