注意到 EGOI 并没有提供本题的官方题解（2024 年的其他题目均提供），所以下面是关于此题的一篇题解。
首先有结论：最优解一定正好打开 $N$ 个横向灯泡或者 $N$ 个纵向灯泡。
- 显然存在一种方案使得打开 $N$ 个灯泡照亮所有位置：如果无法照亮所有位置，则存在一行没有横向的灯泡，那么这一行全是纵向灯泡，矛盾。
- 而 $N - 1$ 个灯泡显然无法照亮所有位置。
- 用 $N$ 个灯泡照亮所有位置，那么所有灯泡必须是同向的。
于是只需要考虑找到 $N$ 个横向灯泡或者 $N$ 个纵向灯泡即可。
考虑任取 $k$ 个灯泡，如何确定这些灯泡的方向。这些灯泡的方向共有 $2^k$ 种情况。那么可以随机选择其中若干个点亮并计算其在 $2^k$ 种情况下的表现，即可求出该方案的信息熵。随机若干次找出最优的一种点亮方案，经过若干次询问可以不断排除一些情况。
但是每次选择几个灯泡，全部确定之后再选择另外的灯泡确定不那么优秀：这一组灯泡最后几步得到的信息很少。
考虑如下算法：
- 维护一个序列，表示当前等待确定的灯泡；同时维护一个集合，表示当前所有的可能情况。
- 每次询问结束或者程序开始时，适量随机添加新的等待确定的灯泡。
- 考察若干组询问，枚举所有可能的情况计算出该询问的信息熵，找出最优秀的那组询问。
- 得到答案后，从集合中删除不符合交互库回应的情况。
该算法在 $N = 100$ 时，平均每次可以排除大约 $92\%$ 的情况，大约可以在 $75$ 次以内得出答案。
First, we have a conclusion: the optimal solution will always involve either exactly $N$ horizontal bulbs or $N$ vertical bulbs.
- It is evident that there is a scheme where turning on $N$ bulbs can illuminate all positions: if it’s impossible to illuminate all positions, then there must be a row without horizontal bulbs, which means that entire row consists of vertical bulbs, leading to a contradiction.
- Obviously, $N - 1$ bulbs cannot illuminate all positions.
- If $N$ bulbs can illuminate all positions, then all bulbs must be oriented in the same direction.
Thus, we only need to consider finding $N$ horizontal bulbs or $N$ vertical bulbs.
Consider any $k$ bulbs and how to determine their orientation. There are $2^k$ possible orientations for these bulbs. By randomly selecting a few orientations and calculating their performance in all $2^k$ cases, we can determine the information entropy of that scheme. By randomly trying several times to find the optimal lighting scheme, and through repeated queries, we can progressively eliminate some possibilities.
However, choosing a few bulbs each time and finalizing their orientations before selecting additional bulbs is not as efficient: the final steps of determining this set of bulbs provide little new information.
Consider the following algorithm:
- Maintain a sequence representing the bulbs currently waiting to be determined; also, maintain a set representing all possible situations.
- After each query or at the start of the program, randomly add a suitable number of new bulbs to the sequence of bulbs waiting to be determined.
- Examine several queries, enumerate all possible cases, and calculate the information entropy of each query to find the most effective set of queries.
- After obtaining the answer, remove the cases from the set that do not match the responses from the interaction library.
In the case where $N = 100$, this algorithm can, on average, exclude about $92\%$ of the cases per query and can usually find the answer in fewer than $75$ queries.
