UOJ Logo Universal Online Judge

UOJ

#123. 【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 - v 2
选择跳转s#整数1#整数2s 10 20
条件跳转i#量1#量2#整数1#整数2i c 99 v 2 0 1

输出格式

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

每个文件需要输出若干行,每行输出一个字符“1”或“2”,表示执行过程中遇到的每个选择跳转所作的选择。

输出的行数需要严格等于此次游戏执行过程中遇到的选择跳转的个数。

样例一

input

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

output

1
1
1
2
1
1

explanation

根据样例输出的方案,执行位置进行了如下的变化:

1 → 2 → 3 → 4 → 5 → 6 → 2 → 3 → 4 → 5 → 6 → 2 → 3 → 4 → 5 → 6 → 2 → 3 → 7 → 8 → 9 → 10 → 11 → 7 → 8 → 9 → 10 → 11 → 7 → 12

当执行位置变成 $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, \dots, a_{10}$。如果你的输出能让剧本正常结束,且结束时成就值不小于 $a_s$,得 $s$ 分。如果以上条目有多项满足,则取满足条件中的最高得分。

形式化地讲,设在你的方案中,变量 $1$ 最终的值为 $v_1$。当你的输出合法时,你的分数将会由下表给出:

得分条件得分条件
10$v_1 \geq a_{10}$5$a_5 \leq v_1 < a_6$
9$a_9 \leq v_1 < a_{10}$4$a_4 \leq v_1 < a_5$
8$a_8 \leq v_1 < a_9$3$a_3 \leq v_1 < a_4$
7$a_7 \leq v_1 < a_8$2$0 < v_1 < a_3$
6$a_6 \leq v_1 < a_7$1$v_1 \leq 0$

在终端中先切换到该试题的目录下:(windows用户请使用cmd)

cd train

我们提供checker这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是,在终端中运行

./checker_linux64 <case_no>

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

./checker_linux64 3

将测试 train3.out 是否可以接受。(windows用户请使用checker_win32 3)(什么你是windows 64位?放心吧可以运行win32应用程序的。)

当然我们有对应的linux 32位版本:checker_linux32。如果linux用户发现无法运行程序,请尝试执行chmod +x checker_linux64chmod +x checker_linux32后重试。

其它操作系统请安装 node.js 然后使用 node checker.js <case_no> 运行checker。

在你调用这个程序后,checker将根据你给出的输出文件给出测试的结果。

更多功能

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

./checker_linux64 <input_filename> <output_file_name>

其中 input_file_nameoutput_file_name 分别是输入输出文件的名称。

例如:

./checker_linux64 train3.in train3.out

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

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

./checker_linux64 -w <input_file_name> <output_file_name>

或者

./checker_linux64 -w <case_no>

例如

./checker_linux64 -w train3.in train3.out

下载

输入数据及checker下载


或者逐个上传: