2666 「NOI2013」小 Q 的修炼

小 Q 最近发现了一款新游戏，游戏的目标是从一个新手修炼成为武功高强的大侠。面对错综复杂的游戏世界，小 Q 要对他面临的每件事情做出谨慎的选择。例如，是否参加一个陌生人邀请的比武；同意或是拒绝用宝剑交换他人的武功秘籍......而小 Q 做出的每一个选择都有可能影响到他以后的发展：面对一个高手，若主动与之比武，很可能会损失惨重；但若不去比武，也许今后就再也见不到这个高手了。

对着这个游戏，小 Q 玩了很多次仍然玩不出他想要的结局，于是他费尽千辛万苦找到了游戏的剧本。令人惊讶的是,游戏的剧本并不像我们平时见到的剧本，反而很像代码。这个剧本是这样描述的： * 量：有 $2$ 种量，常数和变量。 * 常数：一个整数。 * 变量：初始值为 $0$ 的可变整数，不同变量用不同正整数编号区分。 * 事件：整个剧本由若干个事件构成。所有的事件按照给定的顺序从 $1$ 开始依次编号。事件共有 $3$ 种：普通事件、选择跳转和条件跳转。 * 执行位置：一个整数，表示接下来将会执行的事件编号，如果不存在这个编号的事件则停止，即游戏到了一个结局。最初的时候执行位置为 $1$。 * 普通事件：一个变量增加或减少一个量的值。之后执行位置增加 $1$。 * 选择跳转：两个整数。执行到这里时玩家需要在这两个整数中选择一个，之后执行位置将被修改为这个整数。 * 条件跳转：两个量和两个整数。执行到这里时，若第一个量小于第二个量，则执行位置将被修改为第一个整数，否则将被修改为第二个整数。

小 Q 认为，整个游戏是希望一个叫做「成就值」的变量（编号为 $1$）最大。

该题为提交答案型试题，所有输入数据 train1.in~train10.in 已在附加文件中。

输入的第一行包含两个正整数 $n, m$，表示事件的个数和变量的个数。

接下来有 $n$ 行，每行描述一个事件。这些事件按照给出的顺序依次编号为 $1$ 到 $n$。

描述量和事件的格式如下（格式中 #表示空格）

| 类型 | 格式 | 例子 | | :-: | :-: | :-: | :-: | | 常数 | c#整数 | c -2 | | 变量 | v#正整数 | v 5 | | 普通事件 | 变量#+#量 | v 1 + c 1 | | 普通事件 | 变量#-#量 | v 2 - c 2 | | 选择跳转 | s#整数 1#整数 2 | s 10 20 | | 条件跳转 | i#量 1#量 2#整数 1#整数 2 | i c 99 v 2 0 1 |

针对给定的 $10$ 个输入文件 train1.in~train10.in，你需要分别提交你的输出文件 train1.out~train10.out。

每个文件需要输出若干行，每行输出一个字符 1 或 2，表示执行过程中遇到的每个选择跳转所作的选择。输出的行数需要严格等于此次游戏执行过程中遇到的选择跳转的个数。

样例的剧本及编号如下：

1  v 2 + c 19
2  i v 2 c 3 7 3
3  s 4 7
4  v 1 + c 13
5  v 2 - c 3
6  i c 0 c 1 2 0
7  i v 2 c 5 12 8
8  s 9 12
9  v 1 + c 23
10 v 2 - c 5
11 i c 0 c 1 7 0

根据样例输出的方案，执行位置进行了如下的变化： $1\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow6\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow6\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow6\rightarrow2\rightarrow3\rightarrow7\rightarrow8\rightarrow9\rightarrow10 \rightarrow11\rightarrow7\rightarrow8\rightarrow9\rightarrow10\rightarrow11\rightarrow7\rightarrow12$ 当执行位置变成 $12$ 时，剧本结束。最终变量 $1$ 的值为 $85$。

事件 $1$ 为变量 $2$ 增加 $19$，可以认为是得到了 $19$ 单位的初始资金。

事件 $6$ 为无条件跳转到事件 $2$，可以看出这里是一个循环。从事件 $2$ 和事件 $3$ 可以看出，如果变量 $2$ 小于 $3$（资金不足一次购买）或者选择放弃则会跳出循环。循环内的事件 $4$ 和事件 $5$ 为花费 $3$ 的资金得到 $13$ 的成就值。

事件 $7$ 到 $11$ 也是一个类似的循环，只是参数有所不同。为花费 $5$ 的资金得到 $23$ 的成就值。

可以看出，样例是一个物品个数无限的背包问题。样例的输出给出的是这个背包问题的最优解。

对于每组数据,我们采用如下方式评分： * 如果你的输出不合法,得 $0$ 分。 * 如果你的输出执行了超过 $10^6$ 行剧本,得 $0$ 分。 * 如果你的输出能让剧本正常结束，得 $1$ 分。 * 如果你的输出能让剧本正常结束，且结束时成就值为正数，得 $2$ 分。

我们设置了 $8$ 个评分参数 $a_3 , a_4 , \ldots , a_{10}$。

如果你的输出能让剧本正常结束，且结束时成就值不小于 $a_s$，得 $s$ 分。

如果以上条目有多项满足，则取满足条件中的最高得分。

如何测试你的输出

我们提供 checker 这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是，首先进入终端，在终端中运行下面的命令进入本题的文件夹：

cd train

然后运行：

./checker <case_no>

其中 case_no 是测试数据的编号。例如

./checker 3

将测试 train3.out 是否可以接受。

在你调用这个程序后，checker 将根据你给出的输出文件给出测试的结果，其中包括： * 非法退出：未知错误。 * Input/Output file does not exist.：输入/输出文件不存在。 * Output invalid.：输出文件有误,此时可能包含具体错误信息。 * Correct! Your answer is x.：输出可接受,最后的成就值为 $x$。

更多功能

checker 还可以检查任意输入输出文件的测试结果，方法是在终端中运行：

cd train

./checker <input_file_name> <output_file_name>

其中 input_file_name 和 output_file_name 分别是输入输出文件的名称。例如

./checker train3.in train3.out

将测试 train3.out 是否可以接受。

使用 -w 可以输出每步运行的结果。用法是

./checker -w <input_file_name> <output_file_name>

或者

./checker -w <case_no>

例如

./checker -w train3.in train3.out

特别提示

如果选手使用自己生成输入文件进行调试，有可能因规模过大造成 checker 出错。若发生这类情况，请尝试较小规模的数据。