题目描述

Prasi 把 500 名信息学选手关进了监狱。为了释放他们，选手们必须合作解决一个问题。

Prasi 有两个数组，长度分别为 $A$ 和 $B$。保证：

两张纸条上分别写有 $A$ 和 $B$ 的值，并标明对应数组名。选手们的目标是判断哪个数组更短。

在开始前，所有选手可以约定一个共同策略。之后，Prasi 会遮住他们的眼睛，并按未知顺序让他们依次进入房间。

房间里有一块黑板、一支粉笔、一块板擦、两张写有数组长度的纸条，以及 Prasi。黑板上始终写着一个 $0$ 到 $M$ 之间的整数，初始为 $0$。当前进入房间的选手可以：

1. 看到黑板上的数字；
2. 选择查看两张纸条之一，即查看 $A$ 或 $B$ 的值；
3. 查看后，他可以：
   • 宣布哪个数组更短；或
   • 擦掉黑板上的数字，写上一个新的 $0$ 到 $M$ 之间的整数。

不能作弊，也不能使用随机策略。你需要设计一个确定性策略，使得在不超过 500 名选手依次进入房间的情况下，一定能判断 $A$ 与 $B$ 哪个更小，并且希望 $M$ 尽可能小。

实现方式

本题为函数式提交题，需要实现：

std::vector<std::vector<int>> devise_strategy(int N);

该函数只会被调用一次，参数 $N$ 是数组长度的上界。函数应返回一个二维数组 $s$，大小为 $(M+1)\times (N+1)$。

对于状态 $i$，即黑板上写着数字 $i$：

• $s[i][0]$ 表示当前选手要查看哪张纸条：
  • $s[i][0]=0$：查看 $A$；
  • $s[i][0]=1$：查看 $B$。
• 若查看到的值为 $j$，其中 $j>0$，则 $s[i][j]$ 表示接下来的动作：
  • $s[i][j]=-1$：宣布 $A<B$；
  • $s[i][j]=-2$：宣布 $B<A$；
  • $0\le s[i][j]\le M$：在黑板上写下新数字 $s[i][j]$，交给下一名选手继续。

数据范围

• $2\le N\le 5000$；
• 策略最多使用 500 次进入房间的机会。

子任务与评分

第三个子任务的部分分规则：

• $40\le M_{max}\le 60$：20 分；
• $26\le M_{max}\le 39$：$25+1.5(40-M_{max})$ 分；
• $M_{max}=25$：50 分；
• $M_{max}=24$：55 分；
• $M_{max}=23$：62 分；
• $M_{max}=22$：70 分；
• $M_{max}=21$：80 分；
• $M_{max}\le 20$：90 分。

本地测试说明

原题提供 Lgrader.cpp 用于本地测试。其输入格式为：

• 第一行：$N$；
• 接下来若干行：$A,B$；
• 最后一行：-1。

本地 grader 会输出你的策略是否能通过对应测试。

示例交互

当 $N=2$ 时，可以返回：

{{0, -1, -2}}

这表示：黑板数字始终为 $0$，当前选手查看 $A$。若 $A=1$，则一定有 $B=2$，宣布 $A<B$；若 $A=2$，则一定有 $B=1$，宣布 $B<A$。

@下发文件