题目描述

题目译自 European Girls' Olympiad in Informatics 2024 Day2 T3. Light Bulbs

1891 年，弗雷德里克·飞利浦在埃因霍温创立灯泡公司后不久，发明了一种新奇的灯泡：它能沿水平或垂直方向照亮无限长的光线。凭借这一发现，你希望彻底改变现代家居的室内设计。

你计划与儿子杰拉德一起设计一个精巧的装置，在一个房间的 $N \times N$ 网格中安装 $N^2$ 个灯泡。你希望用最少的灯泡点亮整个房间，以节省电力。每盏灯要么是垂直的（照亮所在列的所有格子），要么是水平的（照亮所在行的所有格子）。

下图展示了垂直灯（左）和水平灯（右）的示例：

遗憾的是，安装灯泡时你没有注意，现在不记得哪些灯是水平或垂直的。为了找出用最少灯泡点亮整个房间的方法，你决定进行实验。杰拉德留在房间观察灯泡，而你在另一个房间操作开关。

在每次实验中，你打开或关闭每盏灯，杰拉德会报告总共有多少格子被点亮；如果一个格子被多盏灯照亮，只计数一次。实验中打开的灯泡数量不限，但你时间紧迫，希望尽量减少实验次数。

你的任务是帮助他们找到一个点亮整个房间且使用最少灯泡的方案。你最多可以进行 $2000$ 次实验，但实验次数越少，分数越高。

交互方式

这是一个交互式问题。

• 你的程序首先读取一行，包含一个整数 $N$，表示网格的高度和宽度。
• 然后，程序与评分程序交互。 要进行实验，首先输出一行，包含一个问号 ?。 接下来的 $N$ 行，输出一个 $N \times N$ 的网格，指定哪些灯泡被点亮。具体来说，每行输出一个长度为 $N$ 的字符串，由 0（关闭）和 1（打开）组成。 之后，程序读取一个整数 $\ell$（$0 \leq \ell \leq N^2$），表示指定灯泡点亮后照亮的格子总数。
• 当你准备回答时，输出一行，包含一个感叹号 !，后跟 $N$ 行，格式与实验中的网格相同。 为了答案被接受，灯泡必须点亮整个网格，且使用的点亮灯泡数量必须是最少的。

完成后，程序应退出。

评分程序是非自适应的，意味着灯泡网格在交互开始前已确定。

每次实验后，需刷新标准输出，否则可能被判为「Time Limit Exceeded」。在 Python 中，使用 input() 读取时自动刷新；在 C++ 中，cout << endl; 会刷新并换行；若使用 printf，需调用 fflush(stdout)。

样例 1

交互器输出	用户程序输出
5
	? 11000 00000 00000 00000 00000
10
	? 01000 01000 01000 00100 00000
13
	! 00100 00010 01000 00001 01000

在样例交互中，程序首先读取网格大小 $N = 5$。下图展示了隐藏的网格（程序不知道）以及一个可能的答案，使用 $5$ 个灯泡点亮整个网格。标记的灯泡被点亮，较深的格子表示被照亮。

程序执行了两次实验，如下图所示。在第一次实验中，使用左上角的两个垂直灯泡，点亮了 $10$ 个格子。第二次实验点亮了 $13$ 个格子。最后，程序输出答案（如上图所示）并退出。

数据范围与提示

对于所有输入数据，满足：

• $3 \leq N \leq 100$
• 你最多可进行 $2000$ 次实验（输出最终答案不算实验）。若超过此限制，将判为「Wrong Answer」。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$11$	$N = 3$
$2$	$11$	$N \leq 10$
$3$	$78$	无附加限制

在最后一个子任务中，你的分数取决于你进行的实验次数，按以下公式计算：

$$\text{score} = \begin{cases} (2000 - Q) \cdot 29 / 900 & \text{if } 200 \leq Q \leq 2000, \\ 58 + (200 - Q) \cdot 4 / 23 & \text{if } 85 \leq Q \leq 200, \\ 78 & \text{if } Q \leq 85, \end{cases} $$

其中 $Q$ 是任意测试点中使用的最大实验次数。分数将向下取整到最近的整数。

下图展示了当你的程序在所有子任务中使用相同 $Q$ 值时，获得的总分数与 $Q$ 的关系。要在此问题中获得满分 $100$ 分，你必须在每个测试点中使用最多 $85$ 次实验。

测试工具

为方便测试，我们提供了一个简单的测试工具，可在「文件」界面下载。你可以选择是否使用该工具。注意，官方评测程序与测试工具不同。

使用该工具时，需创建一个输入文件，例如 sample1.in，文件以一个数字 $N$ 开头，紧跟 $N$ 行指定网格，其中 V 表示灯泡照亮其所在列，H 表示照亮其所在行。例如：

5
VVHVH
HVHHV
VHHVV
HHHVH
HHVVV

对于 Python 程序（如 solution.py，通常运行 pypy3 solution.py）：

python3 testing_tool.py pypy3 solution.py < sample1.in

对于 C++ 程序，先编译（例如 g++ -g -O2 -std=gnu++20 -static solution.cpp -o solution.out），然后运行：

python3 testing_tool.py ./solution.out < sample1.in