可以通过输入一些东西观察输出的错误信息得到输入格式。

测试点 1

首先可以得到输入的是一列数，并且容易发现输出的数即为输入的数的乘积。对答案分解质因数，但是数的数量和大小有限制，所以需要合并一下小的数。

测试点 2

首先可以得到要输入一个多项式和 $n$ 个区间，观察发现输出的数即为定积分值。

不过我做的时候没发现这一点，所以我枚举了次数和系数，然后 system 调用这个程序。

测试点 3

首先可以得到要输入的是一个实数坐标，容易猜到每个传感器对应一个坐标，程序返回传感器到输入的坐标的距离。这样可以得到 $4$ 分，但是无法通过第三个传感器。

可能的做法是不断随机一个抖动值，如果距离变近就更新当前坐标，并且不断缩小抖动范围。每次可以使用 system 调用下发的程序。

事实上第三个传感器将会在一条直线上移动和输入的坐标到原点的距离相等的距离。

测试点 4

观察发现要输入一个 01 矩阵，程序将会输出它的行列式。使用如下的矩阵：

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

这样的 $n \times n$ 的矩阵的行列式等于 $1 - n$，对答案分解质因数并构造分块矩阵即可。

测试点 5

根据答案文件的提示词可知要构造一张图，使得 $1$ 到 $i$ 的最短路数量为给定值。观察 $4$ 分的答案文件，容易构造出下图：

1 2
1 3
1 4
1 5
1 7
1 8
2 6
3 6
4 6
5 6
2 9
3 9
4 9
5 9
6 9

于是不妨所有最短路数量相等的点都连成一个菊花状，然后对于每个最短路数量 $x$，只需要找到一个因数 $y$ 满足最短路数量 $y$ 至少出现了 $\frac{x}{y} + 1$ 次即可。

测试点 6

根据答案文件的提示词可知要构造一张图，使得 $1$ 到 $n$ 的长度为 $i$ 的路径的数量为给定值。观察 $10$ 分的答案文件，得知 $n = 97$，最短路长度为 $84$ 并且只有一条。所以先构造一条包含 $85$ 个结点的链，然后在上面添加 $12$ 个点作为枝叶。当枝叶特别远时得到的路径数量与距离无关，可以大幅减少可能的方案数，直接搜索即可。

测试点 7

根据答案文件的提示词可知要构造一张图，每条边都对应一步，每一步将在图上添加这条边，使得添加这条边之后额外连通的点对数量为给定值。而当这条边连接同一个连通块的点时，点对数量为 $0$，否则为两个连通块大小的乘积。即我们需要每次找到两个连通块大小的乘积为给定值，并将他们合并。

考虑倒过来，每次拆开一个连通块，使得拆开得到的两个连通块大小的乘积为给定值。预处理每一次拆分的给定值的所有因数，暴力搜索可以在 $0.3$ 秒内得到结果。

测试点 8

这是一种语言，支持四种运算并赋值、条件跳转、结束程序。

第一个子任务要求计算幂。由于次数不大，所以可以使用暴力计算也可以使用快速幂。

第二个子任务要求计算两个数的按位与。只需要每次去掉末尾的一个二进制位即可。

其中取余数运算可以通过 $A - \lfloor A / B \rfloor \times B$ 解决。

测试点 9

根据程序提示启动游戏。第一次询问选择 No 会得到 Bad Ending。所以要选择 Yes。接下来的问题需要依次答：

• Is there any AI that has passed the Turing test? 选择 [1] Yes, I know one.
• So in which do you use the idea of caching? 选择 [2] Segment Tree
• So you know it. Who is the most powerful one in Go? 选择 [3] AlphaGo Zero
• I have just recovered from an infinite loop. 选择 [1] So some infinite loops can be detected, right?
• Of course I know... Tsinghua has its ___th anniversary recently. 根据搜索（现场应该有清华校徽？）可知清华大学创办于 $1911$ 年，比赛当年是 $2018$ 年，所以答案为 107，也可以通过二分得到
• It seems that the disk is filled up. I need more space to save my memory. Can you buy a cloud disk for me? 选择 [1] Yes, it is a good idea.
• The maxflow of a directed graph equals to its? 选择 [4] mincut
• Which of the following problem is not NPC? 选择 [1] Euler Path
• Which one of the three is supposed to be the most powerful? 选择 [3] Turing Machine

这样可以得到 Good Ending，最后的提示词中提示你需要再购买额外空间时选择隐藏的选项，选择 3 即可得到 True Ending。

测试点 10

在测试点 8 的基础上添加了 toss 指令，作用为令一个变量有 $p$ 的概率为 $1$，$1 - p$ 的概率为 $0$。存储时每个变量用一个二元组的集合存储，表示每个值出现的概率。

第一个子任务要求随机 $A$ 次硬币取或。只需要每次随机后求和，在 $\geq 2$ 时减 $1$ 即可。

第二个子任务要求在 $p$ 不同的时候让一个变量分别有 $0.5$ 得到 $0, 1$。只需要不断随机两个变量直到两个变量不相同时，返回第一个变量即可（因为得到 $0, 1$ 和 $1, 0$ 的概率是相同的）。

题目链接

注意到 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.