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

对着这个游戏，小 Q 玩了很多次仍然玩不出他想要的结局，于是他费尽千辛万苦找到了游戏的剧本。令人惊讶的是,游戏的剧本并不像我们平时见到的剧本，反而很像代码。这个剧本是这样描述的：

量：有
2
2 种量，常数和变量。
常数：一个整数。
变量：初始值为
0
0 的可变整数，不同变量用不同正整数编号区分。
事件：整个剧本由若干个事件构成。所有的事件按照给定的顺序从
1
1 开始依次编号。事件共有
3
3 种：普通事件、选择跳转和条件跳转。
执行位置：一个整数，表示接下来将会执行的事件编号，如果不存在这个编号的事件则停止，即游戏到了一个结局。最初的时候执行位置为
1
1。
普通事件：一个变量增加或减少一个量的值。之后执行位置增加
1
1。
选择跳转：两个整数。执行到这里时玩家需要在这两个整数中选择一个，之后执行位置将被修改为这个整数。
条件跳转：两个量和两个整数。执行到这里时，若第一个量小于第二个量，则执行位置将被修改为第一个整数，否则将被修改为第二个整数。
小 Q 认为，整个游戏是希望一个叫做「成就值」的变量（编号为
1
1）最大。

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

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

接下来有
�
n 行，每行描述一个事件。这些事件按照给出的顺序依次编号为
1
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
10 个输入文件 train1.in~train10.in，你需要分别提交你的输出文件 train1.out~train10.out。

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

输入输出样例
输入 #1复制
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
输出 #1复制
1
1
1
2
1
1
说明/提示
评分标准
对于每组数据，我们采用如下方式评分：

如果你的输出不合法,得
0
0 分。
如果你的输出执行了超过
1
0
6
10
6
行剧本,得
0
0 分。
如果你的输出能让剧本正常结束，得
1
1 分。
如果你的输出能让剧本正常结束，且结束时成就值为正数，得
2
2 分。
我们设置了
8
8 个评分参数
�
3
,
�
4
,
…
,
�
10
a
3
​
,a
4
​
,…,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 出错。若发生这类情况，请尝试较小规模的数据。

2
B 国在耗资百亿元之后终于研究出了新式武器——连环阵（Zenith Protected Linked Hybrid Zone）。传说中，连环阵是一种永不停滞的自发性智能武器。但经过 A 国间谍的侦察发现，连环阵其实是由
�
M 个编号为
1
,
2
,
…
,
�
1,2,…,M 的独立武器组成的。最初，
1
1 号武器发挥着攻击作用，其他武器都处在无敌自卫状态。以后，一旦第
�
i（
1
≤
�
<
�
1≤i<M）号武器被消灭，
1
1 秒种以后第
�
+
1
i+1 号武器就自动从无敌自卫状态变成攻击状态。当第
�
M 号武器被消灭以后，这个造价昂贵的连环阵就被摧毁了。

为了彻底打击 B 国科学家，A 国军事部长打算用最廉价的武器——炸弹来消灭连环阵。经过长时间的精密探测，A 国科学家们掌握了连环阵中 M 个武器的平面坐标，然后确定了
�
n 个炸弹的平面坐标并且安放了炸弹。每个炸弹持续爆炸时间为
5
5 分钟。在引爆时间内，每枚炸弹都可以在瞬间消灭离它平面距离不超过
�
k 的、处在攻击状态的 B 国武器。和连环阵类似，最初
�
1
a
1
​
号炸弹持续引爆
5
5 分钟时间，然后
�
2
a
2
​
号炸弹持续引爆
5
5 分钟时间，接着
�
3
a
3
​
号炸弹引爆
…
…以此类推，直到连环阵被摧毁。

显然，不同的序列
�
1
,
�
2
,
�
3
…
a
1
​
,a
2
​
,a
3
​
… 消灭连环阵的效果也不同。好的序列可以在仅使用较少炸弹的情况下就将连环阵摧毁；坏的序列可能在使用完所有炸弹后仍无法将连环阵摧毁。现在，请你决定一个最优序列
�
1
,
�
2
,
�
3
…
a
1
​
,a
2
​
,a
3
​
… 使得在第
�
�
a
x
​
号炸弹引爆的时间内连环阵被摧毁。这里的
�
x 应当尽量小。

输入格式
第一行包含三个整数：
�
M、
�
n 和
�
k，分别表示 B 国连环阵由 M 个武器组成，A 国有
�
n 个炸弹可以使用，炸弹攻击范围为
�
k。以下
�
M 行，每行由一对整数
�
�
,
�
�
x
i
​
,y
i
​
组成，表示第
�
i 号武器的平面坐标。再接下来
�
n 行，每行由一对整数
�
�
,
�
�
u
i
​
,v
i
​
组成，表示第
�
i 号炸弹的平面坐标。输入数据保证随机、无误、并且必然有解。

输出格式
一行包含一个整数
�
x，表示实际使用的炸弹数。

输入输出样例
输入 #1复制
4 3 6
0 6
6 6
6 0
0 0
1 5
0 3
1 1
输出 #1复制
2
说明/提示
对于
100
%
100% 的数据，
1
≤
�
,
�
≤
100
1≤M,n≤100，
1
≤
�
≤
1000
1≤k≤1000，
0
≤
�
�
,
�
�
≤
10000
0≤x
i
​
,y
i
​
≤10000，
0
≤
�
�
,
�
�
≤
10000
0≤u
i
​
,v
i
​
≤10000。

各个测试点
2
2 秒。

3
话说我们铭铭小朋友成功的回答了爸爸的问题，自然少不了要去索要些奖励，抠门的爸爸一看报纸，嘿，门口的麦当劳在搞活动，还有免费午餐哦，不过前提条件：得正确回答麦当劳叔叔的问题。

问题是这样描述的：

“我面前有很多个小朋友，我希望你帮我找到一个最聪明的小朋友。我心目中最聪明的就是第一个跑进麦当劳大门的，我希望你帮我找出最聪明和最不聪明的小朋友，可能的最大的到达时间差。但是，小朋友只能按照一个特殊的规则前进。小朋友面前有一个
�
×
�
n×n 的格子矩阵，左下角的格子是起点，右上角的格子是大门。每个孩子每秒可以走向 上、下、左、右 前进一个格子，每个格子只能经过一次。但矩阵中间有一些障碍区，不能通过，只能绕过。”

例如，
4
×
4
4×4 的矩阵，格子
(
1
,
1
)
,
(
2
,
3
)
,
(
4
,
2
)
(1,1),(2,3),(4,2) 为障碍区，黑格子就是一条可行的路线。时间为
7
7。

输入格式
第一行为两个整数
�
,
�
n,m。

第二至第
�
+
1
m+1 行里，每行描述一个障碍区。用两个整数表示
�
,
�
x,y。

输出格式
仅一行，那个最大的时间差。

输入输出样例
输入 #1复制
4 3
1 1
2 3
4 2
输出 #1复制
4
说明/提示
2
≤
�
≤
10
2≤n≤10，
0
≤
�
≤
100
0≤m≤100，
1
≤
�
,
�
≤
�
1≤x,y≤n。

4
牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在
�
k 进制下，一个数的小数部分是纯循环的，那么它就是美的。现在，牛牛想知道：对于已知的十进制数
�
n 和
�
m，在
�
k 进制下，有多少个数值上互不相等的纯循环小数，可以用分数
�
�
y
x
​
表示,其中
1
≤
�
≤
�
,
1
≤
�
≤
�
1≤x≤n,1≤y≤m，且
�
,
�
x,y 是整数。一个数是纯循环的，当且仅当其可以写成以下形式：

�
.
�
1
˙
�
2
�
3
…
�
�
−
1
�
�
˙
a.
c
1
​

˙
​
c
2
​
c
3
​
…c
p−1
​

c
p
​

˙
​

其中，
�
a 是一个整数，
�
≥
1
p≥1；对于
1
≤
�
≤
�
1≤i≤p，
�
�
c
i
​
是
�
k 进制下的一位数字。

例如，在十进制下，
0.45454545
…
…

4
˙
5
˙
0.45454545……=0.
4
˙

5
˙
是纯循环的，它可以用
5
11
11
5
​
、
10
22
22
10
​
等分数表示；在十进制下，
0.1666666
…
…

0.1
6
˙
0.1666666……=0.1
6
˙
则不是纯循环的，它可以用
1
6
6
1
​
等分数表示。需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成
0
0 的循环或是
�
−
1
k−1 的循环；而一个小数部分非
0
0 的有限小数不是纯循环的。

输入格式
只有一行，包含三个十进制数
�
,
�
,
�
N,M,K 意义如题所述。

输出格式
一行一个整数，表示满足条件的美的数的个数。

输入输出样例
输入 #1复制
2 6 10
输出 #1复制
4
说明/提示
样例解释
满足条件的数分别是：

1
1

1.0000
…
1
1
​
=1.0000…

1
3

0.3333
…
3
1
​
=0.3333…

2
1

2.0000
…
1
2
​
=2.0000…

2
3

0.6666
…
3
2
​
=0.6666…

1
1
1
1
​
和
2
2
2
2
​
虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，
1
3
3
1
​
和
2
6
6
2
​
也只计数一次。

数据范围
对于所有的测试点，保证
1
≤
�
≤
1
0
9
1≤n≤10
9
，
1
≤
�
≤
1
0
9
1≤m≤10
9
，
2
≤
�
≤
2
×
1
0
3
2≤k≤2×10
3
。

对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：

测试点编号
�
n
�
m
�
k
1
1
≤
10
≤10
≤
20
≤20

2
=2
2
2
≤
100
≤100
≤
1
0
4
≤10
4

=
2
=2
3
3
≤
1
0
3
≤10
3

=
2
=2
4
4
≤
1
0
4
≤10
4

=
2
=2
5
5
≤
10
≤10
≤
20
≤20

3
=3
6
6
≤
100
≤100
≤
1
0
4
≤10
4

=
3
=3
7
7
≤
1
0
3
≤10
3

=
3
=3
8
8
≤
1
0
4
≤10
4

=
3
=3
9
9
≤
10
≤10
≤
20
≤20
≤
100
≤100
10
10
≤
100
≤100
≤
1
0
4
≤10
4

≤
100
≤100
11
11
≤
1
0
3
≤10
3

≤
1
0
3
≤10
3

12
12
≤
1
0
4
≤10
4

13
13
≤
1
0
5
≤10
5

≤
1
0
8
≤10
8

≤
100
≤100
14
14
≤
2
×
1
0
5
≤2×10
5

≤
1
0
3
≤10
3

15
15
≤
5
×
1
0
5
≤5×10
5

16
16
≤
1
0
6
≤10
6

≤
1
0
8
≤10
8

≤
100
≤100
17
17
≤
2
×
1
0
6
≤2×10
6

≤
1
0
3
≤10
3

18
18
≤
5
×
1
0
6
≤5×10
6

19
19
≤
1
0
7
≤10
7

≤
1
0
8
≤10
8

100
100
20
20
≤
2
×
1
0
7
≤2×10
7

≤
1
0
3
≤10
3

21
21
≤
2
×
1
0
7
≤2×10
7

22
22
≤
1
0
8
≤10
8

≤
1
0
8
≤10
8

23
23
≤
1
0
8
≤10
8

≤
1
0
8
≤10
8

24
,
25
24,25
提示
这部分将提供一个将分数化为对应的小数的方法，如果你已经熟悉这个方法，你不必阅读本提示。

分数可以通过除法，用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起，设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第
�
a 位和小数点后第
�
b 位（特殊地：如果其中一个对应的商数位是个位，则认为
�

0
a=0；不妨设
�
<
�
a<b），则其循环部分可以用小数点后第
�
+
1
a+1 位到小数点后第
�
b 位的循环来表示。

例如：在十进制下，将
5
11
11
5
​
转化为小数时，个位开始的商数依次为
4
,
5
,
4
,
…
4,5,4,…，对应的余数分别为
6
,
5
,
6
,
…
6,5,6,…。余数第一次重复出现的位置是个位和小数点后第
2
2 位,那么
�

0
,
�

2
a=0,b=2。

�

0
,
�

2
a=0,b=2 即其循环部分可以用小数点第
1
1 位到第
3
3 位来表示。表示为：
5
11

0.45454545
…

4
˙
5
˙
11
5
​
=0.45454545…=0.
4
˙

5
˙
。

在十进制下，将
1
6
6
1
​
转化为小数时,个位开始的商数依次为
1
,
6
,
6
,
…
1,6,6,…，对应的余数分别为
4
,
4
,
4
,
…
4,4,4,…。余数第一次重复出现的位置是小数点后第
1
1 位和小数点后第
2
2 位,即其循环部分可以用小数点后第
2
2 位来表示。表示为：
1
6

0.1666
…
…

0.1
6
˙
6
1
​
=0.1666……=0.1
6
˙
。

需要注意的是：商数重复出现并不代表进入了循环节。

5
明天就要考近代史了，小明决定把要背的历史事件，根据事件发生的年份，按顺序从小到大抄在一张纸上。可是他抄的时候，相邻两个年份相隔太近了。例如1894,1911,1949这三个时间，由于相隔太近，纸上写的是：189419111949。

这使小明很苦恼，于是他准备编写个程序把这些年份还原成应该的样子。那么，怎么才能够正确地还原呢？

首先，这些年份是按时间顺序严格递增排列的，所以，还原后的也必须满足这点要求。但如果仅仅是这样，那么1,89,419,111949也满足要求。显然，最后的年份不可能有这么大，所以，小明要求在这个条件下，最后一个数要最小。

加了这个限制后，18,94,1911,1949也满足条件，但因为是近代史，第一个年份也不会这么早，所以，小明还要在保证最后一个数最小的前提下，第一个数要尽量大。并在保证第一个数最大的情况下，第二个数最大……以此类推。

注意：在本题中，数字前的前导0是被允许的。

输入格式
输入文件名：input.txt

输入文件包含多行，每一行是一个由不超过2000个数字组成的字符串，表示一个测试例子。一个输入文件中最多包含1000个测试例子。

输出格式
输出文件名：output.txt

相对于输入文件的每一个测试例子，你的程序要输出对应的一行，即是分割后的数字序列，相邻两个数用一个逗号分割。

输入输出样例
输入 #1复制
189419111949
1000010
输出 #1复制
1894,1911,1949
1,000010