title: [SDOI2009] 晨跑

description:
Elaxia 最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。

现在给出一张学校附近的地图，这张地图中包含 $N$ 个十字路口和 $M$ 条街道，Elaxia 只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。

Elaxia 每天从寝室出发跑到学校，保证寝室编号为 $1$，学校编号为 $N$。

Elaxia 的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路口。

Elaxia 耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。

除了练空手道，Elaxia 其他时间都花在了学习和找 MM 上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。

可能存在 $1\rightarrow n$ 的边。这种情况下，这条边只能走一次。

inputFormat:
第一行两个整数 $N,M$，表示十字路口数和街道数。

接下来 $M$ 行，每行 $3$ 个数 $a,b,c$，表示路口 $a$ 和路口 $b$ 之间有条长度为 $c$ 的街道（单向）。

outputFormat: 一行两个整数，最长周期的天数和满足最长天数的条件下最短的路程度。


title: [SDOI2009] 虔诚的墓主人

type: P

description:
小W是一片新造公墓的管理人。公墓可以看成一块 $N×M$ 的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。

当地的居民都是非常虔诚的基督徒，他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。

一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好 $k$ 棵常青树。

形式化地，对于一个坐标为 $(x, y)$ 的墓地，以其为中心的十字架个数是这样的长度为 $4k$ 的二元组序列 $[(x_{1,1},y_{1,1}),\allowbreak(x_{1,2},y_{1,2}),\allowbreak\cdots,(x_{1,k},y_{1,k}),\allowbreak(x_{2,1},y_{2,1}),\allowbreak(x_{2,2},y_{2,2}),\allowbreak\cdots,(x_{2,k},y_{2,k}),\allowbreak(x_{3,1},y_{3,1}),\allowbreak(x_{3,2},y_{3,2}),\allowbreak\cdots,(x_{3,k},y_{3,k}),\allowbreak(x_{4,1},y_{4,1}),\allowbreak(x_{4,2},y_{4,2}),\allowbreak\cdots,(x_{4,k},y_{4,k})]$ 的方案数：

- 每一个二元组对应着一棵常青树的坐标；
- $x_{1,1}<x_{1,2}<\cdots< x_{1,k}<x$ 且 $y_{1,1}=y_{1,2}=\cdots=y_{1,k}=y$；
- $x<x_{2,1}<x_{2,2}<\cdots< x_{2,k}$ 且 $y_{2,1}=y_{2,2}=\cdots=y_{2,k}=y$；
- $y_{3,1}<y_{3,2}<\cdots< y_{3,k}<y$ 且 $x_{3,1}=x_{3,2}=\cdots=x_{3,k}=x$；
- $y<y_{4,1}<y_{4,2}<\cdots< y_{4,k}$ 且 $x_{4,1}=x_{4,2}=\cdots=x_{4,k}=x$。

小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。

inputFormat:
第一行包含两个用空格分隔的正整数 $N$ 和 $M$，表示公墓的宽和长，因此这个矩形公墓共有 $(N+1) ×(M+1)$ 个格点，左下角的坐标为 $(0, 0)$，右上角的坐标为 $(N, M)$。

第二行包含一个正整数 $W$，表示公墓中常青树的个数。

第三行起共 $W$ 行，每行包含两个用空格分隔的非负整数 $x_i$ 和 $y_i$，表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。

最后一行包含一个正整数 $k$，意义如题目所示。

outputFormat: 输出仅包含一个非负整数，表示这片公墓中所有墓地的虔诚度总和。为了方便起见，答案对 $2{,}147{,}483{,}648$ 取模。

hint:
图中，以墓地 $(2, 2)$ 和 $(2, 3)$ 为中心的十字架各有 $3$ 个，即它们的虔诚度均为 $3$。其他墓地的虔诚度为 $0$。

 ![](https://cdn.luogu.com.cn/upload/pic/1589.png)

对于 $30\%$ 的数据，满足 $1 ≤ N, M ≤ 10^3$。

对于 $60\%$ 的数据，满足 $1 ≤ N, M ≤ 10^6$。

对于 $100\%$ 的数据，满足 $1 ≤ N, M ≤ 10^9$，$0 ≤ x_i ≤ N$，$0 ≤ y_i ≤ M$，$1 ≤ W ≤ 10^5$，$1 ≤ k ≤ 10$。

存在 $50\%$ 的数据，满足 $1 ≤ k ≤ 2$。

存在 $25\%$ 的数据，满足 $1 ≤ W ≤ 10^4$。


title: [SDOI2008] 沙拉公主的困惑

description: 大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为 $1$ 到 $N$ 的阶乘，但是，政府只发行编号与 $M!$ 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于数量可能非常大，你只需计算出答案对 $R$ 取模后的结果即可。

inputFormat:
第一行为两个整数 $T$ 和 $R$，其中 $T$ 为该组中测试数据数目，$R$ 为模数。

接下来 $T$ 行，每行一对整数 $N$ 和 $M$，具体意义见题目描述。

outputFormat: 共 $T$ 行，对于每一对 $N$ 和 $M$，输出 $[1, N!]$ 中与 $M!$ 互质的数的数量对 $R$ 取模后的值。


title: [SDOI2009] 细胞探索

description:
生物课上，老师开始为同学们介绍细胞。为了加深同学们的印象，老师在一张N×M的矩阵中定义了一种细胞，矩阵中仅有井号“#”和点“.”：

细胞由细胞核、细胞质及细胞膜构成。细胞核是一个4连通（上下左右相连）的全为“#”的连通块，它必须实心，即不能存在一个4连通的“.”连通块被其完全包围（所谓完全包围指的是，这个“.”连通块不能位于矩阵边界相邻，且它的4相邻格子均属于包含它的“#”连通块）。细胞膜是一个8连通（上下左右，以及4个对角方向）的全为“#”的非实心连通块。细胞膜仅包围一个4连通的区域，且这个区域内有且仅有一个细胞核，这个区域剩下的位置全为“.”。

所有连通块必须极大化，即一个8连通块周围不能找到一个“#”与这个连通块的任意一个“#”8连通；同样，对于一个4连通块周围不能找到一个“#”与这个连通块的任意一个“#”4连通。

现在，老师画了一幅图画，并让小E回答图画中一共有几个细胞，并把图画中不属于任何一个细胞的“#”改成“.”。

inputFormat:
输入文件explore.in的第一行包含两个用空格分隔的正整数N和M，表示矩阵的高和长。

接下来一个N行M列的矩阵，矩阵中仅含井号“#”和点“.”，保证没有多余字符。

outputFormat:
输出文件explore.out第一行包含一个整数，表示输入的矩阵中的细胞数。

接下来一个N行M列的矩阵，矩阵中仅含井号“#”和点“.”，表示更改后的图画。

hint:
对于20%的数据，满足1 ≤ N, M ≤ 20。

另有20%的数据，满足所有“#”都属于某一个正确的细胞。

对于100%的数据，满足1 ≤ N, M ≤ 1,000。


title: [SDOI2009] 学校食堂

description:
小 F 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。 由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是 $a$，这一道为 $b$，则做这道菜所需的时间为 $(a\operatorname{or}b)-(a\operatorname{and}b)$，而做第一道菜是不需要计算时间的。其中，$\operatorname{or}$ 和 $\operatorname{and}$ 表示整数逐位或运算及逐位与运算，C 语言中对应的运算符为 `|` 和 `&`。

学生数目相对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间。因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间。

虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有一定容忍度的。也就是说，队伍中的第 $i$ 个同学，最多允许紧跟他身后的 $B_i$ 个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒。因此，食堂做菜还得照顾到同学们的情绪。 现在，小 F 想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完这些菜最少需要多少时间。

inputFormat: 第一行包含一个正整数 $C$，表示测试点的数据组数。 每组数据的第一行包含一个正整数 $N$，表示同学数。 每组数据的第二行起共 $N$ 行，每行包含两个用空格分隔的非负整数 $T_i$ 和 $B_i$，表示按队伍顺序从前往后的每个同学所需的菜的口味和这个同学的忍受度。 每组数据之间没有多余空行。

outputFormat: 包含 $C$ 行，每行一个整数，表示对应数据中食堂完成所有菜所需的最少时间。

hint:
对于第一组数据：

同学 1 允许同学 2 或同学 3 在他之前拿到菜；同学 2 允许同学 3 在他之前拿到菜；同学 3 比较小气，他必须比他后面的同学先拿菜。

一种最优的方案是按同学 3、同学 2、同学 1、同学 4、同学 5 做菜，每道菜所需的时间分别是 0、8、1、6 及 1。

**数据规模和约定**

- 对于 $30\%$ 的数据，满足 $1 \le N \le 20$。

- 对于 $ 100\% $ 的数据，满足 $1 \le N \le 1000,0 \le T_i \le 1000,0 \le B_i \le 7，1 \le C \le 5$。

- 存在 $30\%$ 的数据，满足 $0 \le B_i \le 1$。

- 存在 $65\%$ 的数据，满足 $0 \le B_i \le 5$。

- 存在 $45\%$ 的数据，满足 $0 \le T_i \le 130$。


title: [SDOI2008] 仪仗队

description:
作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N \times N$ 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

![](https://cdn.luogu.com.cn/upload/pic/1149.png)

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

inputFormat: 一行，一个正整数 $N$。

outputFormat: 输出一行一个数，即 C 君应看到的学生人数。


title: [SHOI2009] 舞会

description: OItown要举办了一年一度的超级舞会了，作为主办方的Constantine为了使今年的舞会规模空前，他邀请了许多他的好友和同学去。舞会那天，恰好来了n个男生n个女生。Constantine发现，一般情况下，舞伴之间，总是男伴总是比女伴长得高，不过，偶尔也是有特殊情况的。所以，Constantine现在想知道，如果把这2n个人恰好配成n对舞伴，有多少种搭配方法，而且他要求最多只有k对舞伴之间女伴比男伴高。现在，Constantine需要参加SHTSC的你帮助他算出这个答案，当然啦，他会先告诉你这2n个同学的身高。

inputFormat: 第一行：两个整数n、k，含义如问题中所示。 第2行到第n+1行：n个整数，表示n个男生的身高。 第n+2行到第2n+1行：n个整数，表示n个女生的身高。 表示身高的正整数，都不超过 。

outputFormat: 输出文件只有一个，即满足n对舞伴中最多只有k对舞伴之间女伴比男伴高的男女搭配方案数。

hint:
评分
如果你的输出文件与标准答案完全相符，你将获得该测试点的全部分数，否则得零分。

N< = 200

K< = N


title: [SHOI2007] 书柜的尺寸

description:
Tom 不喜欢那种一字长龙式的大书架，他只想要一个小书柜来存放他的系列工具书。Tom 打算把书柜放在桌子的后面，这样需要查书的时候就可以不用起身离开了。

显然，这种书柜不能太大，Tom 希望它的体积越小越好。另外，出于他的审美要求，他只想要一个三层的书柜。为了物尽其用，Tom 规定每层必须至少放一本书。现在的问题是，Tom 怎么分配他的工具书，才能让木匠造出最小的书柜来呢？

Tom很快意识到这是一个数学问题。每本书都有自己的高度 $h_i$ 和厚度 $t_i$。我们需要求的是一个分配方案，也就是要求把所有的书分配在 $S_1$、$S_2$ 和 $S_3$ **三个非空集合**里面的一个，不重复也不遗漏，那么，很明显，书柜正面表面积（$S$）的计算公式就是：

$$S=\left(\sum_{j=1}^3 \max_{i \in S_j} h_i\right) \times \left(\max_{j=1}^3 \sum_{i \in S_j} t_i\right) $$

由于书柜的深度是固定的（显然，它应该等于那本最宽的书的长度），所以要求书柜的体积最小就是**要求 $S$ 最小**。Tom 离答案只有一步之遥了。不过很遗憾，Tom 并不擅长于编程，于是他邀请你来帮助他解决这个问题。

inputFormat:
第一行一个整数 $n$，代表书本的个数。

接下来 $n$ 行每行有两个整数 $h_i$ 和 $t_i$，代表每本书的高度和厚度。

outputFormat: 只有一行，即输出最小的 $S$。

hint: 对于全部数据，$3 \leq n \leq 70$，$150 \leq h_i \leq 300$，$5 \leq t_i \leq 30$。


title: [SHOI2009] 会场预约

background:
## 形式化描述

你需要维护一个在数轴上的线段的集合 $S$，支持两种操作：

`A l r` 表示将 $S$ 中所有与线段 $[l,r]$ 相交的线段删去，并将 $[l,r]$ 加入 $S$ 中。

`B` 查询 $S$ 中的元素数量。

对于 `A` 操作，每次还需输出删掉的元素个数。

description:
PP 大厦有一间空的礼堂，可以为企业或者单位提供会议场地。

这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。

一般来说，如果 PP 大厦方面事先已经接受了一个会场预约（例如从 $10$ 日到 $15$ 日），就不会再接受与之相冲突的预约（例如从 $12$ 日到 $17$ 日）。

不过，有时出于经济利益，PP 大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。 于是，礼堂管理员 QQ 的笔记本上经常记录着这样的信息：（本题中为方便起见，所有的日期都用一个整数表示）例如，如果一个为期 $10$ 天的会议从 $90$ 日开始到 $99$ 日，那么下一个会议最早只能在 $100$ 日开始。（此处前后矛盾，若无法理解请参考形式化描述。）

最近，这个业务的工作量与日俱增，礼堂的管理员 QQ 希望参加 SHTSC 的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作：

`A` 操作：有一个新的预约是从 $start$ 日到 $end$ 日，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便 QQ 与自己的记录相校对。

`B` 操作：请你的系统返回当前的仍然有效的预约的总数。

inputFormat:
第一行一个正整数 $n$，表示操作个数。
接下来 $n$ 行，每行表示一个操作，都是上面两种中的一个。

outputFormat: 输出 $n$ 行，每行一个整数，表示对应操作的答案。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 2\times 10^5$，$1\le l \le r \le 10^5$。


title: [SHOI2007] 宝石纪念币

description:
Constantine刚结束在MySky Island的度假，正准备离开的时候，他想送给她的好朋友YY一份特别的礼物——MySky Island上特别的手工艺品宝石纪念币。
宝石纪念币的一面上刻着小岛的名字MySky，或者收礼物的人，比如“to YY”。不过特别的是，每枚纪念币的反面，依次均匀的镶着一圈共n颗彩色的宝石。例如，下面是一个n=7时的简单例子：

![](https://cdn.luogu.com.cn/upload/pic/19775.png)

因为纪念币是圆的，所以如果两种“宝石颜色的排布”经过旋转后对应位置的颜色相重合，就认为它们是相同的排布方式（请注意：纪念币只有一面镶宝石，所以两种排布若经过翻转以后是可以重合的，但只经过旋转无法使两者重合，则认为他们是不同的排布）。例如下面的两种排布方式就是相同的：

![](https://cdn.luogu.com.cn/upload/pic/19776.png)

另外，由于MySky Island当地的习俗，每枚钱币上都只能嵌奇数颗宝石，不然就认为是不吉利的。

宝石纪念币是现场制作的，游客可以选择自己喜欢的颜色的宝石。所以Constantine选出了他最喜欢的17种颜色（你如果要问为什么选这么多的话，只能告诉你因为17是他的幸运数字）。他想知道，如果按他要求把这17种颜色的宝石都用上的话，可以制作出多少枚不同的纪念币。

由于答案可能很大，你只需要计算答案的最后120位就可以了。

inputFormat: 输入文件只有一行，包含一个正奇数n 1< = N < =10^9

outputFormat: 输出文件包含1行，表示不同纪念币的枚数的最后120位。这120位从高位到低位依次输出，位数不足的用0在高位补足。


title: [SHOI2007] 交通网络

description:
著名的城市交通规划师L.Serenade为OItown的各个城堡之间设计了一套的地铁交通网络。每一条地铁线路都用来双向连通两个城堡。因为是建在地下的不同深度，所以这些地铁线路是可以“交叉”的。

OItown的居民们的生活和工作都在不同的城堡中进行，于是，每个OItown的居民都要在每天早晨从家出发，乘地铁去工作，当然地铁换乘是允许的。不过每个居民都会选择换乘次数最少的乘车方式。如果有多种乘车方式，这些乘车方式所需要的换乘次数一样，那么居民每天都会等概率的随机选择其中一种。

现在L.Serenade想请你为他计算出，每天每条地铁线路在早晨的平均客流量。他会告诉你，每个居民的家和工作地址，还有他设计的地铁交通网络的全部信息。

当然L.Serenade保证，交通网络能把城市连为一体，而且任意两个城堡之间的最优乘车方式（即换成次数最少的）不超过2^63-1种。

inputFormat:
输入文件的第一行有两个整数n、m，分别表示OItown里的城堡数（这些城堡用1.2.3...n标号）和地铁线路的数量。

接下去m行，每行包含两个整数，x、y，表示这两个城堡之间有一条地铁线路。注意，两个城堡之间最多只有一条地铁线路，且每条地铁线路只被输入文件描述一次。

最后的n行，每行有n个整数。

第i行的第j个非负整数Ci，j表示每天早晨有Ci，j个OItown的居民要从i城堡去j城堡。输入数据保证Ci，i=0。

outputFormat: 输出文件有m行，每行依次表示每条地铁线路每天早晨的平均客流。精确到小数点后一位。整数也应输出一位小数，例如1应输出为1.0。

hint:
样例说明：从城堡1到城堡六的使得换乘次数最少的乘车方式共有3种：1-2-4-6；1-2-5-6；1-3-5-6。所以每个人都有1/3的概率选择这其中的每一种。

N< = 300

M< = N\*(N-1) div 2

0< = C(i,j) < = 100


title: [SHOI2007] 园丁的烦恼

background:
很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。

有一天国王漫步在花园里，若有所思，他问一个园丁道： “最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”

“那么本质上它是一个深度优先搜索，陛下。”园丁深深地向国王鞠了一躬。

“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”

“是的，显然这是一道经典的动态规划题，早在 N 元 $4002$ 年我们就已经发现了其中的奥秘了，陛下。”

“该死的，你究竟是什么来头？”

“陛下息怒，干我们的这行经常莫名其妙地被问到和 OI 有关的题目，我也是为了预防万一啊！” 王者的尊严受到了伤害，这是不可容忍的。

description:
看来一般的难题是难不倒这位园丁的，国王最后打算用车轮战来消耗他的实力： “年轻人，在我的花园里有 $n$ 棵树，每一棵树可以用一个整数坐标来表示，一会儿，我的 $m$ 个骑士们会来轮番询问你某一个矩阵内有多少树，如果你不能立即答对，你就准备走人吧！”说完，国王气呼呼地先走了。

这下轮到园丁傻眼了，他没有准备过这样的问题。所幸的是，作为“全国园丁保护联盟”的会长——你，可以成为他的最后一根救命稻草。

inputFormat:
第一行有两个整数 $n, m$，分别表示树木个数和询问次数。

接下来 $n$ 行，每行两个整数 $x, y$，表示存在一棵坐标为 $(x, y)$ 的树。有可能存在两棵树位于同一坐标。

接下来 $m$ 行，每行四个整数 $a, b, c, d$，表示查询以 $(a, b)$ 为左下角，$(c, d)$ 为右上角的矩形内部（包括边界）有多少棵树。

outputFormat: 对于每个查询，输出一行一个整数表示答案。

hint:
#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n, m \leq 10$。
- 对于 $100\%$ 的数据，保证 $0 \leq n \leq 5 \times 10^5$，$1 \leq m \leq 5 \times 10^5$，$0 \leq x, y, a, b, c, d \leq 10^7$，$a \leq c$，$b \leq d$。


title: 小Z的情书

background: 众所周知，小 Z 是高富帅的典范和代表，所以他很很多很多的妹纸。小 Z 要写情书给他的妹纸了，作为一个谨慎的人，他当然不会直白的写在纸上（否则被那群损友发现岂不糟了？）。

description:
虽然小 Z 谨小慎微，但是还是被狡猾的小 D 给发现了其中的玄机。作为一个大方的人，小 D 自然要把这个秘密拿出来给大家共享啦~小 Z 开始有两张 $N \times N$ 大小的纸一张是透明的、一张是有字的。然后小 Z 把透明的纸上有些格子涂黑了。接着把这两张纸一起给他的妹纸，妹纸事先和小 Z 约定好了，按照如下方法阅读：首先先把透明的纸盖在另一张纸上，然后把露出来的字母从上到下从左到右写下来，然后转个 $90$ 度，再读一遍……这样子一共读四遍……详见样例。

小 D 不知从哪把情书弄来了，请大家一起来欣赏，顺便请大家把内容打出来看看。

inputFormat:
第 $1$ 行，一个整数 $N$；

第 $2$ 到第 $N+1$ 行，每行 $N$ 个字符，代表 skj 的透明纸，`O` 没有涂黑的地方，`#` 代表被涂黑的地方；

第 $N+2$ 到第 $2N+1$ 行，每行 $N$ 个字符，仅包含大写字母，如描述中所示，是另一张纸。

outputFormat: 一行，情书的内容。

samples:
4
##O#
#O#O
####
###O
ARAO
PCEM
LEEN
TURC


title: 小 Z 的栈函数

description:
小 Z 最近发现了一个神奇的机器，这个机器的所有操作都是通过维护一个栈来完成的，它支持如下 11 个操作：

- $\texttt{NUM} ~x$：栈顶放入 $x$。
- $\texttt{POP}$：抛弃栈顶元素。
- $\texttt{INV}$：将栈顶元素取出，然后放入它的相反数。
- $\texttt{DUP}$：再放入一个和栈顶元素相同的数。
- $\texttt{SWP}$：交换栈顶的两个元素。
- $\texttt{ADD}$：取出栈顶的两个元素，两元素相加，所得结果放入栈内。
- $\texttt{SUB}$：取出栈顶的两个元素，第二个元素减去第一个元素，所得结果放入栈内。
- $\texttt{MUL}$：取出栈顶的两个元素，两元素相乘，所得结果放入栈内。
- $\texttt{DIV}$：取出栈顶的两个元素，第二个元素整除以第一个元素，所得结果放入栈内。
- $\texttt{MOD}$：取出栈顶的两个元素，第二个元素取模以第一个元素，所得结果放入栈内。
- $\texttt{END}$：结束这个程序。

然后，小 Z 用上面的 11 种操作写了一个一元函数 $f(x)$。$x$ 就是放入栈里面第一个初始元素。然后经过这个函数的一系列操作，当函数结束的时候，正常情况下，栈里面会有唯一的一个元素。剩下的这个元素就作为函数 $f(x)$ 的返回值。

小 Z 有 $n$ 个询问，询问每个值 $x$ 经过上述函数所映射出的 $f(x)$ 是多少。但是这个由于机器太老了，跑起东西来太慢了，小 Z 又是一个急性子，所以请你们写一个程序，来帮助小 Z 计算他查询的 $f(x)$。

还有，由于这台机器太破了，所以如果运算过程中有数字的绝对值大于 $1000000000$，机器将产生故障。

inputFormat:
输入首先有若干行，仅包含上述 11 个操作，用来描述函数 $f(x)$ 的操作，函数的结束保证以 $\texttt{END}$ 结尾.

接下来有一个整数，表示询问的个数 $n$。

接下来 $n$ 行，每行一个整数 $x$，表示询问 $f(x)$ 的值。

**输入数据不保证合法**。

outputFormat:
输出 $n$ 行，每行表示一个询问的结果。按如下规则输出：

- 如果最后栈内不是一个元素，输出 `ERROR`。
- 如果运算过程中有数字的绝对值大于 $1000000000$，输出 `ERROR`。
- 如果输入数据不合法，导致中途退出，输出 `ERROR`。
- 否则输出对应的 $f(x)$。

hint:
### 数据规模与约定

对于全部测试点，保证函数的操作步数不超过 $2000$，$1 \leq n \leq 2000$，$|x| \leq 10^{9}$。


title: 小Z的笔记

background: 小Z由于写情书浪费了太多时间，导致他外语课都没有好好听。为什么是外语课而不是英语课？因为小Z也不知道这门课学的是什么语言。

description:
由于没有好好听课，小Z的笔记全都记的杂乱无章，出现了好多错误的地方。小Z的笔记是如此的糟糕，以至于他只记了一句例句，而且自己还不知道是什么意思……然后在老师讲语法的时候，小Z又零星的记了几个字母对，老师说，这几个字母对是绝对不能相邻的，而且相邻是不关心字母的顺序的，比如老师说，“ab”不能相邻，那么相同的，“ba”也不能相邻。

现在小Z到家了，打开了上课的笔记，然后他发现笔记有很多自相矛盾的地方：为什么下面的不能相邻的字母对会出现在上面的例句里面呢？纠结再三，小Z觉得下面的东西相对比较简单，所以记错的概率比较小……他决定在上面的例句里面擦掉几个字母，使得句子变得合法。

但是小Z还有其他作业要做呢，来不及整理笔记了，就把这个艰巨的任务留给了大家，请问大家，小Z最少要擦掉几个字母，才能使得上面的例句合法？

inputFormat:
第一行：一个整数N。

第二行：一个长度为N的字符串，只包含小写字母，代表小Z记下的例句。

第三行：一个整数M，代表不能相邻的字母对的个数。

接下来M行：每行两个小写字母，代表不能相邻的字母对，因为小Z太不认真了，所以可能有重复。

outputFormat: 一行，一个整数，最少要擦除的字母数。

hint:
【数据规模】

对于10%的数据，M=0；

对于另外30%的数据，N<=1000；

对于100%的数据，N<=100000，M<=400。


title: [SDOI2009] Bill的挑战

description:
Sheng_bill 不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致 Sheng_bill  极度的不满。于是他再次挑战你。这次你可不能输。

这次，比赛规则是这样的：

给出 $N$ 个长度相同的字符串（由小写英文字母和 `?` 组成），$S_1,S_2,\dots,S_N$，求与这 $N$ 个串中的刚好 $K$ 个串匹配的字符串 $T$ 的个数，答案对 $1000003$ 取模。

若字符串 $S_x(1\le x\le N)$ 和 $T$ 匹配，满足以下条件：
1. $|S_x|=|T|$。
2. 对于任意的 $1\le i\le|S_x|$，满足 $S_x[i]= \texttt{?}$ 或者 $S_x[i]=T[i]$。

其中 $T$ 只包含小写英文字母。

inputFormat:
**本题包含多组数据**。

第一行一个整数 $T$，表示数据组数。

对于每组数据，第一行两个整数，$N$ 和 $K$。

接下来 $N$ 行，每行一个字符串 $S_i$。

outputFormat: 每组数据输出一行一个整数，表示答案。


title: [NOI2015] 荷马史诗

background: > 追逐影子的人，自己就是影子 —— 荷马

description:
Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》 组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 $n$ 种不同的单词，从 $1$ 到 $n$ 进行编号。其中第 $i$ 种单词出现的总次数为 $w_i$。Allison 想要用 $k$ 进制串 $s_i$ 来替换第 $i$ 种单词，使得其满足如下要求：

对于任意的 $1\leq i, j\leq n$ ，$i\ne j$ ，都有：$s_i$ 不是 $s_j$ 的前缀。

现在 Allison 想要知道，如何选择 $s_i$，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的 $s_i$ 的最短长度是多少？

一个字符串被称为 $k$ 进制字符串，当且仅当它的每个字符是 $0$ 到 $k-1$ 之间（包括 $0$ 和 $k-1$ ）的整数。

字符串 $str1$ 被称为字符串 $str2$ 的前缀，当且仅当：存在 $1 \leq t\leq m$ ，使得 $str1 = str2[1..t]$。其中，$m$ 是字符串 $str2$ 的长度，$str2[1..t]$ 表示 $str2$ 的前 $t$ 个字符组成的字符串。

inputFormat:
输入的第 $1$ 行包含 $2$ 个正整数 $n, k$ ，中间用单个空格隔开，表示共有 $n$ 种单词，需要使用 $k$ 进制字符串进行替换。

接下来 $n$ 行，第 $i + 1$ 行包含 $1$ 个非负整数 $w_i$，表示第 $i$ 种单词的出现次数。

outputFormat:
输出包括 $2$ 行。

第 $1$ 行输出 $1$ 个整数，为《荷马史诗》经过重新编码以后的最短长度。

第 $2$ 行输出 $1$ 个整数，为保证最短总长度的情况下，最长字符串 $s_i$ 的最短长度。


title: 正则表达式

background: 小Z童鞋一日意外的看到小X写了一个正则表达式的高级程序，这个正则表达式程序仅仅由字符“0”,“1”，“.”和“\*”构成，但是他能够匹配出所有在OJ上都AC的程序的核心代码！小Z大为颇感好奇，于是他决定入侵小X的电脑上去获得这个正则表达式的高级程序。

description:
在 Internet 网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在 $A$ 到 $B$ 的连接不一定存在 $B$ 到 $A$ 的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在 $A$ 到 $B$ 的连接的同时也存在 $B$ 到 $A$ 的连接的话，那么 $A$ 和 $B$ 实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为 $0$。

现在小 Z 告诉你整个网络的构成情况，他希望知道从他的电脑（编号为 $1$），到小 X 的电脑（编号为 $n$）所需要的最短传输时间。

inputFormat:
第一行两个整数 $n,m$，表示有 $n$ 台电脑，$m$ 个连接关系。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示从电脑 $u$ 到电脑 $v$ 传输信息的时间为 $w$。

outputFormat: 输出文件仅一行为最短传输时间。

hint:
- 对于  $40\%$ 的数据，$1\leq n\leq 10^3$, $1\leq m\leq 10^4$；
- 对于  $70\%$ 的数据，$1\leq n\leq 5 \times 10^3$， $1\leq m\leq 10^5$；
- 对于  $100\%$ 的数据，$1\leq n\leq 2 \times 10^5$， $1\leq m\leq 10^6$。

保证答案在 `int` 范围内。


title: 背单词

background: 小明对英语一窍不通，令老师十分头疼。于是期末考试前夕，小明被逼着开始背单词……

description: 老师给了小明一篇长度为N的英语文章，然后让小明背M个单词。为了确保小明不会在背单词时睡着，老师会向他提Q个问题，每次老师随机选择一个区间L..R，小明要回答在这段文字中他背过的单词总共出现过多少次。

inputFormat: 第一行两个整数M、Q如前所述。第二行为英语文章。接下来M行每行一个需要背的单词。接下来Q行每行一个询问，包含两个整数L、R（含端点），即给定的文字区间。

outputFormat: Q行，对每个询问输出一行表示答案。


title: [CERC2016] 外观分析 Appearance Analysis

description:
你在萨格勒布拍摄了一张电气工程与计算机“C”楼的照片，它的尺寸相同的窗户整齐地排列在行列上。一些窗户上画着美妙的图案，你现在正在尝试分析有多少本质不同的创意画。

我们用一个r行c列的矩形格子图来描述一张照片。每个窗户都占据了一个矩形区域，并且所有窗户都有着相同的尺寸。一个窗户里的每个格子要么是空白的（用“.”表示），要么是被画过的（用“+”表示）。两个窗户的图案被认为是相同的，当且仅当其中有一个窗户旋转90度、180度、270度或360度后，放在另一个窗户上会完全匹配（包括边框）。当比较图案时，我们不允许翻转窗户。

所有窗户都规则地分布在行列中，窗户之间的边框用一格“#”字符表示。确切地说，在上下相邻的两个窗户之间，有恰好一行“#”字符，同时在第一行窗户之上或者最后一行窗户之下，也有恰好一行“#”字符。同理，在左右相邻的两个窗户之间，有恰好一列“#”字符，同时在第一列窗户之左或者最后一列窗户之右，也有恰好一列“#”字符。窗户的行数与列数是任意的，窗户的长宽也是任意的，不一定是正方形。但是，每个窗户至少占据一个格子，而且所有窗户的尺寸都是相同的。

请统计有多少本质不同的创意画。

inputFormat:
第一行包含两个正整数r,c(3<=r,c<=111)，分别表示照片的行数和列数。

接下来r行，每行c个字符，分别表示照片的每一行。

outputFormat: 输出一行一个整数，即本质不同的创意画的数量。


title: 乘积最大3

description:
请你找出 $M$ 个和为 $N$ 的正整数，他们的乘积要尽可能的大。

输出字典序最小的一种方案。

inputFormat: 一行，两个正整数 $N,M$

outputFormat: $M$ 个和为 $N$ 的，乘积尽可能的大的正整数。


title: 选学霸

description: 老师想从 $n$ 名学生中选 $m$ 人当学霸，但有 $k$ 对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 $m$ 尽可能接近。

inputFormat:
第一行，三个正整数 $n,m,k$。

接下来 $k$ 行，每行 $2$ 个数，表示一对实力相当的人的编号（编号为 $1,2,\cdots n$）。

outputFormat:
共一行，表示既不让同学们抗议，又与原来的 $m$ 尽可能接近的选出学霸的数目。

如果有两种方案与 $m$ 的差的绝对值相等，选较小的一种。

hint: 对于 $100\%$ 的数据，满足 $1 \le n,m \le 2 \times 10^4$。


title: [NOIP1996 提高组] 挖地雷

description: 在一个地图上有 $N\ (N \le 20)$ 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

inputFormat:
有若干行。

第 $1$ 行只有一个数字，表示地窖的个数 $N$。

第 $2$ 行有 $N$ 个数，分别表示每个地窖中的地雷个数。

第 $3$ 行至第 $N+1$ 行表示地窖之间的连接情况：

第 $3$ 行有 $n-1$ 个数（$0$ 或 $1$），表示第一个地窖至第 $2$ 个、第 $3$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。如第 $3$ 行为 $11000\cdots 0$，则表示第 $1$ 个地窖至第 $2$ 个地窖有路径，至第 $3$ 个地窖有路径，至第 $4$ 个地窖、第 $5$ 个 $\dots$ 第 $n$ 个地窖没有路径。

第 $4$ 行有 $n-2$ 个数，表示第二个地窖至第 $3$ 个、第 $4$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。

……

第 $n+1$ 行有 $1$ 个数，表示第 $n-1$ 个地窖至第 $n$ 个地窖有否路径连接。（为 $0$ 表示没有路径，为 $1$ 表示有路径）。

outputFormat:
第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

hint:
**【题目来源】**

NOIP 1996 提高组第三题


title: [国家集训队] 礼物

background: 一年一度的圣诞节快要来到了。每年的圣诞节小 E 都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小 E 心目中的重要性不同，在小 E 心中分量越重的人，收到的礼物会越多。

description: 小 E 从商店中购买了 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人礼物数量为 $w_i$。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模 $P$ 后的结果。

inputFormat:
输入的第一行包含一个整数 $P$，表示模数。
第二行包含两个整数 $n$ 和 $m$，分别表示小 E 从商店购买的礼物数和接受礼物的人数。
第 $3$ 到第 $(m + 2)$ 行，每行一个整数，第 $(i + 2)$ 行的整数 $w_i$ 表示送给第 $i$ 个人的礼物数量。

outputFormat: 若不存在可行方案，则输出 `Impossible`，否则输出一个整数，表示模 $P$ 后的方案数。


title: 贪婪大陆

background: 面对蚂蚁们的疯狂进攻，小 FF 的 Tower defence 宣告失败……人类被蚂蚁们逼到了 Greed Island 上的一个海湾。现在，小 FF 的后方是一望无际的大海，前方是变异了的超级蚂蚁。小 FF 还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造 SCV 布置地雷以阻挡蚂蚁们的进攻。

description: 小 FF 最后一道防线是一条长度为 $n$ 的战壕，小 FF 拥有无数多种地雷，而 SCV 每次可以在 $[L, R]$ 区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小 FF 在某些时候可能会询问你在 $[L',R']$ 区间内有多少种不同的地雷，他希望你能尽快的给予答复。

inputFormat:
第一行为两个整数 $n$ 和 $m$，$n$ 表示防线长度，$m$ 表示 SCV 布雷次数及小 FF 询问的次数总和。

接下来有 $m$ 行，每行三个整数 $q,l,r$：

- 若 $q=1$，则表示 SCV 在 $[l, r]$ 这段区间布上一种地雷；
- 若 $q=2$，则表示小 FF 询问当前 $[l, r]$ 区间总共有多少种地雷。

outputFormat: 对于小 FF 的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。


title: 公路维修问题

description: 由于长期没有得到维修，A国的高速公路上出现了 $n$ 个坑。为了尽快填补好这 $n$ 个坑，A国决定对 $m$ 处地段采取交通管制。为了求解方便，假设A国的高速公路只有一条，而且是笔直的。现在给出 $n$ 个坑的位置，请你计算，最少要对多远的路段实施交通管制？

inputFormat: 输入数据共两行，第一行为两个正整数 $n, m(2\le m \le n\le 15000)$。第二行给出了 $n$ 个坑的坐标（坐标值均在长整范围内，按从小到大的顺序给出，且不会有两个点坐标相同）。

outputFormat: 仅一行，为最小长度和。


title: 小Z的 k 紧凑数

description:
小 Z 在草稿纸上列出了很多数，他觉得相邻两位数字差的绝对值不超过 k 的整数特别奇特，称其为 k 紧凑数。

现在小 Z 想知道 [l，r] 内有多少个 k 紧凑数，希望你帮帮他。

inputFormat: 第一行包含三个整数 l，r，k。

outputFormat: 第一行包含一个整数，表示 [l，r] 内 k 紧凑数的个数。

hint:
【数据规模】

对于 30% 的数据，r − l ≤ 10^5；

对于另外 30% 的数据，l = 1，r 为 10 的倍数；

对于 100% 的数据，1 ≤ l ≤ r ≤ 10^18，0 ≤ k ≤ 8。


title: 小Z的传感器

description:
众所周知，小 Z 家是个豪宅，有 $n$ 个房间，并通过 $m$ 条通道相连（家当然是连通的）。

有一天，小 Y 想趁小 Z 不在偷偷光顾他家，并决定到他家的每个房间至少逛一次。不幸的是，小 X 家有 $k$ 个房间装了传感器，该传感器会在第一次有人到访的时候返回信息。

当小 Z 回到家时，就发现小 Y 来过了，小 Y 也如实地告诉了小 Z 自己到每个房间至少逛了一次。

然而，小 Z 仔细研究了传感器返回信息的先后顺序，怀疑个别传感器可能返回信息有延迟。

为了验证自己的推断，连同这一次在内，他一共让小 Y 到他家来了 $q$ 次。他想判断每次传感器返回信息的先后顺序是否可能出现，希望你帮帮他。

inputFormat:
第一行包含四个整数 $n$，$m$，$k$，$q$。

接下来 $m$ 行，每行包含两个整数 $x$，$y$，表示房间 $x$ 和房间 $y$ 有一条双向通道相连。

接下来 q 行，每行包含 k 个整数，表示每次按先后顺序返回信息的传感器所在房间的编号。

outputFormat: $q$ 行，每行包含一个字符串“Yes”或“No”，表示每次传感器返回信息的先后顺序是否可能出现。

hint:
【数据规模】

对于 $10\%$ 的数据，$n \le 2$；

对于 $30\%$ 的数据，$n \le 3$；

对于 $60\%$ 的数据，$n \le 10000，m \le 20000，k \le 10$；

对于 $100\%$ 的数据，$1 \le k \le n \le 10^5,1 \le m \le 2 \times 10^5,1 \le q \le 5,x \neq y$。


title: 小Z的车厢

description:
小 Z 的家乡有一列在环形铁轨上行驶的火车，共停靠 $n$ 个站（$1$ 号站到 $n$ 号站顺时针排列）。

众所周知，春运是一件非常可怕的事情。不幸的是，小 Z 是铁路公司的员工，现在他收到了 $m$ 条除夕凌晨的订票申请，每个申请 $(x, y, z)$ 表示有 $z$ 个人要从 $x$ 号站顺时针坐到 $y$ 号站，同时，当火车停靠到 $x$ 号站时，所有要在 $x$ 站上车的人都会上车，所有要在 $x$ 号站下车的人都会下车。

由于始发站不确定，现在小 Z 想知道至少需要分配给这列火车多少节车厢（每节车厢可容纳 $36$ 人）才能顺利完成该铁路运输，希望你帮帮他。

inputFormat:
第一行包含两个整数 $n, m$。

接下来 $m$ 行，每行包含三个整数 $x, y, z$。

outputFormat: 第一行包含一个整数，表示至少需要分配给这列火车的车厢数。


title: 杀蚂蚁

background: 说“善有善报，恶有恶报，不是不报……”。小 FF 一心只顾自己企业的壮大而没顾及自己的采矿业对 Greed Island 上生态环境的破坏，Greed Island 的环境日益恶劣。终于，岛上的蚂蚁们变异了，它们决定对小 FF 的矿区进行攻击，欲将岛上的人类驱逐出去……面对蚂蚁们的进攻，人类节节败退。无奈之下，小 FF 请来了全宇宙最强的防御系统制造商派来的工程机器人——SCV，希望能够阻挡蚂蚁的攻势。

description:
经过小 FF 的研究，他发现蚂蚁们每次都走同一条长度为 $n$ 个单位的路线进攻，且蚂蚁们的经过一个单位长度所需的时间为 $T$ 秒。也就是说，只要小 FF 在条路线上布防且给蚂蚁造成沉痛伤害就能阻止蚂蚁的进军。

SCV 擅长制造的防御塔有三种，分别是激光塔，放射塔和干扰塔，他们可以在一个单位长度内修建一座防御塔。三种防御塔的作用如下：

激光塔：使用高能激光，当蚂蚁从塔前经过时每秒对蚂蚁造成 $r$ 点伤害。

放射塔：释放放射性元素，当蚂蚁经过这座塔后，每一秒受到 $g$ 点伤害。

干扰塔：干扰塔负责干扰蚂蚁们的信息素，使得蚂蚁在经过这座塔后，经过之后每一个单位长度的时间变成 $T+b$。

当然，放射塔和干扰塔的效果是可以叠加的，也就是说如果敌人经过 $x$ 座放射塔，那么敌人每秒钟会受到 $x \times g$ 点伤害；同理，如果敌人经过 $y$ 座干扰塔，那么敌人经过一个单位长度的时间将变为 $T + y \times b$。

现在距离蚂蚁的下一轮进攻还有足够长的时间，你这个“NewBe\_One”计划的首席工程师现在被任命为战略总参谋长，因此你必须设计一个给蚂蚁们造成最大伤害的布塔方案。

inputFormat: 输入数据仅一行，$5$ 个整数 $n,r,g,b,T$ 中间用一个空格隔开。它们分别表示你可以布防的总长度，激光塔的效果、放射塔的效果和干扰塔的效果。

outputFormat: 输出仅一个整数，代表你的方案给敌人带来的最大伤害值。

hint:
#### 样例解释

第 $1$ 号位置为放射塔，第 $2,3$ 号位置建造干扰塔，第 $4,5$ 号位置建造激光塔。

#### 数据范围

对于 $30\%$ 的数据：$1 \leq n \leq 20$；

对于 $60\%$ 的数据：$1 \leq n \leq 1024,0 \leq r,g,b \leq 65536,0 \leq T \leq 3$；

对于另外 $40\%$ 的数据：$1 \leq n \leq 400,0 \leq r,g,b \leq 2^{31}-1,0 \leq t \leq 1000$。


title: 公路通行税

description:
在 PALMIA 国家内，有 $N$ 个城市由公路相连（每条公路恰好双向连接两个城市）。经由一条公路或多条公路，从任一城市出发可以到达其余各个城市。直到今年，公路上才要征收公路通行税。在每条公路的中间，有一征税员，从每一辆经由此路的车收取 1 PALMIA COIN（1PC）。

政府官员决定减少收税员而推行公路印花。如果一辆车欲进入一条公路，就必须将这张印花贴在窗上。

政府官员决定：一年的公路印花的价值相当于在两个最远城市之间进行 $100$ 次旅行所需的费用。两个城市之间的距离是从一个城市到达第二个城市所需经过的最少数目的公路数。

你的任务是编写一个程序计算出公路印花的价值。

inputFormat: 输入文件中包含几组数据。每组的第一行包括整数 $N$ 和 $M$（中间被一个空格隔开），$N$ 是该国家中城市的数目，$M$ 是公路的数目（$1\le N\le1000$，$1\le M\le25000$）。城市由整数进行编号，从 $1$ 到 $N$ 。接下来的 $M$ 行，每行均包含一对整数 $A$，$B$（$1\le A,B\le N$），中间由一空格隔开，代表在城市 $A$ 与 $B$ 之间有一条公路。在最后一组数后仅有一行，是两个 $0$，中间被一空格隔开。

outputFormat: 对输入文件中的各组数据，输出文件中包含一行，表示公路印花的价值。


title: 选举预测

background: 科学院的领袖Dunkelheit 的任期，随着局势的平复很快就要结束了。于是，这次具有非凡意义的科学院新领袖的选举很快就要开始了。

description:
选举的第一步是辩论赛。它的规则是这样的：如果当前剩下的候选人多于 $2$ 人，那么就从中任选 $2$ 人进行辩论。输者退出比赛，胜利者继续留在比赛中，如此直到只剩下一个候选人，他就取得了辩论赛的胜利。

辩论赛的胜者在后面的选举中将会更占优势，所以说人们都很关注这次比赛的结果，历史学家 Geheimnis 也不例外。

他收集了所有 $n$ 个候选人的资料，发现如果两个候选人以前曾经比赛过，那么这两个人再次比赛的时候比赛结果是很难改变的（可以认为是不可能）。按照 Geheimnis 掌握的情报，你需要帮助他判断那些候选人有可能取得胜利。

inputFormat:
第一行包含一个正整数 $n$，表示候选人的数目。

之后 $n$ 行，候选人从 $1$ 开始编号，第 $i+1$ 行描述第 $i$ 个候选人。第一个数为 $k$，后面 $k$ 个编号，表示候选人 $i$ 之前赢过的候选人。

outputFormat: 输出一行。第一个数为 $c$，表示有 $c$ 个候选人有可能取得胜利；之后 $c$ 个数表示他们的编号。

hint:
【数据范围】
对于 $50\%$ 的数据，$n \le 200$。
对于 $100\%$ 的数据，$n \le 10^6$，胜负关系不会超过 $10^6$ 对。


title: 星际导航

description:
$\text{sideman}$ 做好了回到 $\text{Gliese}$ 星球的硬件准备，但是 $\text{sideman}$ 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 $N$ 个顶点和 $M$ 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

$\text{sideman}$ 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 $(A, B)$，$\text{sideman}$ 想知道从顶点 $A$ 航行到顶点 $B$ 所经过的最危险的边的危险程度值最小可能是多少。作为 $\text{sideman}$ 的同学，你们要帮助 $\text{sideman}$ 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

inputFormat:
第一行包含两个正整数 $N$ 和 $M$，表示点数和边数。

之后 $M$ 行，每行三个整数 $A$，$B$ 和 $L$，表示顶点 $A$ 和 $B$ 之间有一条边长为 $L$ 的边。顶点从 $1$ 开始标号。

下面一行包含一个正整数 $Q$，表示询问的数目。

之后 $Q$ 行，每行两个整数 $A$ 和 $B$，表示询问 $A$ 和 $B$ 之间最危险的边危险程度的可能最小值。

outputFormat: 对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 $\text{impossible}$。

hint:
对于 $40\%$ 的数据，满足 $N \leq 1000, M \leq 3000, Q \leq 1000$。

对于 $80\%$ 的数据，满足 $N \leq 10000, M \leq 10^5, Q \leq 1000$。

对于 $100\%$ 的数据，满足 $N \leq 10^5, M \leq 3 \times 10^5, Q \leq 10^5, L \leq 10^9$。数据不保证没有重边和自环。


title: [USACO14JAN] Bessie Slows Down S

background: 奶牛题

description:
Bessie the cow is competing in a cross-country skiing event at the winter Moolympic games.  She starts out at a speed of 1 meter per second. However, as she becomes more tired over time, she begins to slow down. Each time Bessie slows down, her speed decreases: she moves at 1/2 meter per second after slowing down once, then 1/3 meter per second after slowing down twice, and so on.

You are told when and where Bessie slows down, in terms of a series of events.  An event like this:

T 17
means that Bessie slows down at a specific time -- here, 17 seconds into the race.  An event like this:

D 10
means that Bessie slows down at a specific distance from the start -- in this case, 10 meters.

Given a list of N such events (1 <= N <= 10,000), please compute the amount of time, in seconds, for Bessie to travel an entire kilometer.  Round your answer to the nearest integer second (0.5 rounds up to 1).

贝西正在参加一项滑雪比赛。她从起点出发的时候，速度恒定为每秒 1 米。然而，随着比赛进程的增加，她会犯很多错误，每次失误都会使她的速度下降。当她第一次失误后，速度会下降到每秒1/2 米，第二次失误后，速度会下降到每秒 1/3 米，第 k 次失误后，速度会下降到每秒 1/(k + 1) 米。

约翰记录了贝西的所有失误，一共有 N 个。有两种失误，一种发生在比赛开始后的某个时间点，另一种发生在赛道的某个位置上。有时，贝西可能在某个时间点到达某个位置，而恰好在这个时间点和位置上都有一次失误的记录，这两个记录要算作不同的失误，会对贝西的速度造成两次影响。比赛的终点距离起点有 1000 米，请问贝西需要多少时间才能滑过终点？

inputFormat:
第一行：单个整数 N ，1 ≤ N ≤ 10000

第二行到第 N + 1 行：每行开头有个大写字母，代表贝西的一个失误类型：

– 如果是 T，接下来会有一个整数 S，表示在比赛开始后的第 S 秒钟整发生了一次失误，

1 ≤ S ≤ 10^7

– 如果是 D，接下来会有一个整数 X，表示在距离起点 X 米处发生了一次失误，1 ≤ X ≤

1000

outputFormat:
单个整数：表示贝西需要多少秒才能滑到终点，如果精确的时间不是整数，则用四舍五入的方

法向最接近的整数取整

hint:
前 10 秒，贝西的速度是每秒 1 米，她滑了 10 米。然后她遭遇了第一次失误，在接下

来的 20 秒内，她又滑了 10 米。之后她遭遇了第二次失误，还剩下 980 米，所以她共计花去

10 + 20 + 2940 = 2970 秒才完成比赛


title: Hz吐泡泡

background: Hz大大是一种可爱的动物（神）。他很喜欢吐泡泡（更喜欢写作业）。

description: 这天，Hz大大心血来潮，吐了n个不同的泡泡玩（保证没有重复的泡泡）。因为他还要写作业，所以他请你帮他把这些泡泡排序成树（左子树<=根<右子树）。输出它的后序遍历。

inputFormat:
共2行。

第一行，1个整数n。(1<=n<=300000)

第二行，n个数，代表泡泡的大小。

outputFormat:
共2行。

第一行，输出树的深度。

第二行，输出数的后序遍历。

详见样例输出。

hint: 水题一道。


title: 翻硬币

description:
小 Z 离开家的时候忘记带走了钱包，掉下的硬币在桌子上排成了一列。正在等着哥哥回来的小 D 坐在桌子旁边，无聊地翻着桌子上的硬币。

出于某种爱好，小 D 一次一定会同时翻转 $M$ 枚硬币。由于小 D 是一个爱动脑的小学生，这样进行了若干次之后她很快想到了一个问题：有多少种方法能够在 $K$ 次翻转后把硬币由原来的状态变成现在这样呢？

因为小 D 是个好学的小学生，她只需要你告诉她方案数对 $10^9+7$ 取模的值以方便她进行验算就可以了。

inputFormat:
第一行，包含三个字符 $N,K,M$，表示硬币的数量，翻转的次数和每次翻转的硬币数量。

第 $2 \sim 3$ 行，包含 $N$ 个字母，表示硬币在一开始的状态和最终要变成的状态。$1$ 表示正面而 $0$ 表示背面。

outputFormat: 一行包含一个整数，表示方案数对 $10^9+7$ 取模的值。


title: 数列编辑器

description:
小 Z 是一个爱好数学的小学生。最近，他在研究一些关于整数数列的性质。

为了方便他的研究，小Z希望实现一个叫做“Open Continuous Lines Processor”的数列编辑器。

一开始，数列编辑器里没有数字，只有一个光标。这个数列编辑器需要支持五种操作。

- `I x` 在当前光标前插入数字 $x$。
- `D` 删除当前光标前的数字。
- `L` 光标向前移动一个数字。
- `R` 光标向后移动一个数字。
- `Q k` 设光标之前的数列是 $\{a_1,a_2,\cdots,a_n\}$，输出第 $k$ 位及之前最大的前缀和，保证 $k\leqslant n$。

inputFormat:
第一行包含一个数字 $N$，表示操作的个数。

接下来包含 $N$ 行，每行包含一条命令。

outputFormat: 对于每个 `Q k` 命令，输出一个整数表示这个操作的答案。

hint:
### 数据范围

对于 $50\%$ 的数据，$N\leqslant1000$；

对于 $80\%$ 的数据，$N\leqslant10^5$；

对于 $100\%$ 的数据，$N\leqslant10^6$，插入的数字绝对值大小不会超过 $1000$。

题目保证不会在数列编辑器为空时进行 `D` 操作。


title: 炉石collection

description:
小 Z 最近沉迷于一个叫做炉石 collection 的游戏。在游戏中，你需要使用排在 $N \times N$ 的矩阵内的卡牌来击败你的敌人。

在这个游戏中，排兵布阵是游戏的一个重要内容，例如“日怒保卫者”和“上古看守者”放在一起可以起到更好的效果。为了游戏的平衡性，同样种类的卡牌最多只能出战 $2$ 张。

在一次激烈的战斗之后，小 Z 想要重新编排他的队伍。在游戏中，小 Z 可以支付 $A$ 枚金币让你任意横向交换卡牌，支付 $B$ 枚金币让你任意纵向交换卡牌。

你只需要支付一次金币就可以进行某种类型的交换任意次，直到你停下并进行另一种类型的交换，此时需要支付另一种类型交换的费用。例如，“横向交换-横向交换-纵向交换-纵向交换-纵向交换-横向交换-纵向交换”总共要支付 $2A + 2B$ 枚金币。

小 Z 想要知道，他最少要支付多少金币把他目前的布置变换成他想要的布置。

inputFormat:
第一行包含三个数字 $N,A,B$，分别表示矩阵的大小，横向交换的费用，纵向交换的费用。

接下来 $N$ 行每行包含 $N$ 个整数，表示开始交换前矩阵内每个位置卡牌的类型。

接下来 $N$ 行每行包含 $N$ 个整数，表示目标矩阵内每个位置卡牌的类型。

outputFormat: 输出最少需要支付多少金币能够把目前的布置变换成他想要的布置。如果不能变换成功，输出 `Fail`。

hint:
对于 $68\%$ 的数据，答案最多只需要支付 $1$ 次费用。

对于 $86\%$ 的数据，答案最多只需要支付 $2$ 次费用。

对于 $100\%$ 的数据，$1 \leq n \leq 300,1 \leq A,B \leq 1000000,1 \leq$ 卡牌类型的标号 $\leq 100000$。


title: 最后的迷宫

background:
哈利•波特作为三强争霸赛的第四名选手，历尽艰险闯到了最后一关——迷宫。

现在，迷宫里只剩下哈利和塞德里克了，哈利只有在塞德里克前面拿到奖杯，才能赢得比赛。哈利只要能看到奖杯，就可以用飞来咒拿到它，所以，现在的问题是哈利如何能尽早地看到奖杯。

description: 哈利的视力非常好，他能从迷宫的一端沿直线看到迷宫的另一端（但他只能看八个方向——东北，东，东南，南，西南……），而且他跑得非常快，跑一步（向上、下、左、右移动一格）只需要 $1\text{s}$。但迷宫是不透光的，而且，要烧掉迷宫的墙也不容易，所以哈利决定绕到一个能够看到奖杯的地方。现在，哈利希望你能帮他确定最短需要多长时间才能拿到奖杯。

inputFormat:
第一行为 $2$ 个数 $N,M$ 表示迷宫的规模（$N$ 为高，$M$ 为宽）

接下来是 $N \times M$ 的迷宫，$\texttt{O}$ 表示空地，$\texttt{X}$ 表示墙。

最后是多对数据，分别是奖杯坐标及哈利的坐标（显然不可能在墙上），每对占一行，$0$ 为结束标志。

outputFormat: 根据每对数据，计算哈利拿到奖杯的最短时间，每对一行。如果魔法部有意难为选手，用墙将奖杯包围了起来，输出 $\texttt{Poor Harry}$。

hint:
对于 $30\%$ 的数据，有 $N\times M\le100$；

对于 $60\%$ 的数据，有 $N\times M\le1600$；

对于 $100\%$ 的数据，有 $N\times M\le16384$。

询问数据对数不超过 $512$。


title: Mzc和男家丁的游戏

background: mzc 与 djn 的第二弹。

description:
mzc 家很有钱（开玩笑），他家有 $n$ 个男家丁（做过上一弹的都知道）。他把她们召集在了一起，他们决定玩捉迷藏。现在 mzc 要来寻找他的男家丁，大家一起来帮忙啊！

由于男家丁数目不多，再加上 mzc 大大的找人水平很好，所以一次只需要找一个男家丁。

inputFormat:
第一行有两个数 $n,m$，表示有 $n$ 行 $m$ 列供男家丁躲藏，

之后 $n$ 行 $m$ 列的矩阵，`m` 表示 mzc，`d` 表示男家丁，`#` 表示不能走，`.` 表示空地。

outputFormat:
一行，若有解：一个数 $sum$，表示找到男家丁的最短移动次数。

若无解：输出 `No Way!`。

hint:
$3 \leq m,n \leq 2000$。

由于 mzc 大大十分着急，所以他只能等待 $1s$。


title: [CERC2016] 二分毯 Bipartite Blanket

description:
在二分图中，所有点被划分成了两个不相交的集合 $A$ 和 $B$，每条边都恰好连接着某个 $A$ 和某个 $B$。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配 $M$ 覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是 $M$ 中至少一条边的端点。

给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。

给定一个参数 $t$，请统计有多少点集 $V$，满足 $V$ 的权值不小于 $t$，且 $V$ 被至少一个匹配 $M$ 覆盖。

inputFormat:
第一行包含两个正整数 $n,m$，分别表示 $A$ 集合的点数和 $B$ 集合的点数。

接下来 $n$ 行，每行 $m$ 个 01 字符，其中第 $i$ 行第 $j$ 列为 $1$ 表示 $A_i$ 和 $B_j$ 之间有一条边。

接下来一行包含 $n$ 个正整数 $v_1,v_2,\cdots,v_n$，分别表示 $A$ 中每个点的权值。

接下来一行包含 $m$ 个正整数 $w_1,w_2,\cdots,w_m$，分别表示 $B$ 中每个点的权值。

最后一行包含一个正整数 $t$，表示参数 $t$。

outputFormat: 输出一行一个整数，即满足条件的点集个数。

hint: $1\leq n,m\leq 20$，$1\leq v_i,w_i\leq 10^7$，$1\leq t\leq 4\times 10^8$。


title: [CERC2016] 凸轮廓线 Convex Contour

description:
一些几何图形整齐地在一个网格图上从左往右排成一列。它们占据了连续的一段横行，每个位置恰好一个几何图形。每个图形是以下的三种之一：

1. 一个恰好充满单个格子的正方形。

2. 一个内切于单个格子的圆。

3. 一个底边与格子重合的等边三角形。

 ![](https://cdn.luogu.com.cn/upload/pic/4685.png)

已知每个格子的边长都为 $1$，请求出这些几何图形的凸包的周长。

inputFormat:
第一行包含一个正整数 $n$，表示几何图形的个数。

第二行包含 $n$ 个字符，从左往右依次表示每个图形，`S` 表示正方形，`C` 表示圆形，`T` 表示等边三角形。

outputFormat: 输出一行一个实数，即凸包的周长。与答案的绝对或相对误差不超过 $10^{-6}$ 时被认为是正确的。


title: [CERC2016] 舞动的盘子 Dancing Disks

description:
Luka非常擅长解决汉诺塔问题，他发明了一种类似汉诺塔的使用盘子和柱子的游戏。这个游戏有n个不同大小的盘子以及36根柱子。盘子按照大小从小到大依次被编号为1到n。柱子形成了6行6列的矩阵，从上到下每行依次被编号为1到6，从左到右每列依次被编号为1到6。

 ![](https://cdn.luogu.com.cn/upload/pic/4686.png)

游戏一开始，n个盘子都被堆叠在左上角坐标为(1,1)的柱子上。对于每一次操作，玩家可以选择一个柱子，取出最顶上若干个盘子，然后选择右边或者下面的某个柱子，将取出的盘子全部堆叠在其顶上（不会翻转顺序）。游戏的目标是把所有盘子都移动到(6,6)，且自底向上大小依次递减。

给定游戏的初始局面，请找到任意一组玩通关的方法。数据保证解必定存在。

inputFormat:
第一行包含一个正整数n(1<=n<=40000)，表示盘子的数目。

第二行包含n个正整数d\_1,d\_2,...,d\_n(1<=d\_i<=n)，自底向上表示(1,1)柱子上每个盘子的编号。

输入数据保证不存在两个盘子的编号相同。

outputFormat:
输出m行，m表示你的解中游戏操作的次数。

其中第i行包含4个参数r\_i,c\_i,p\_i,n\_i，表示第i步操作，即你选择了(r\_i,c\_i)最上方的n\_i(n\_i>=1)个盘子，然后往p\_i方向移动。

如果向右移动，那么p\_i为“R”（不含引号）；如果向下移动，那么p\_i为“D”（不含引号）。

若有多组方案，输出任意一组。


title: [CERC2016] 自由的套娃 Free Figurines

description:
俄罗斯套娃是一些尺寸递增的木制雕像，它们可以嵌套在一起。每个套娃可以放进一个更大的套娃，也可以被放入一个更小的套娃。每个套娃内部最多只能直接嵌套一个套娃，但是那个套娃内部还可以继续嵌套。

给定n个尺寸互不相同的套娃，按尺寸从小到大依次编号为1到n。如果套娃a被直接嵌入套娃b，那么我们称b是a的父亲，如果一个套娃没有父亲，那么我们称它是自由的。一组镶嵌方案可以用每个套娃的父亲来表示。

我们可以每步可以做以下两种操作中的任意一种：

1.把一个自由的套娃直接嵌入一个更大的没有被放入东西的套娃。

2.选择一个不自由的套娃，将其从其父亲中取出。

给定初始局面，请计算达到目标局面的最小的操作步数。

inputFormat:
第一行包含一个正整数n(1<=n<=100000)，表示套娃的个数。

第二行包含n个整数p\_1,p\_2,...,p\_n(0<=p\_i<=n)，依次表示初始局面中每个套娃的父亲，0表示自由套娃。

第三行包含n个整数q\_1,q\_2,...,q\_n(0<=q\_i<=n)，依次表示目标局面中每个套娃的父亲，0表示自由套娃。

输入数据保证初始局面和目标局面均合法。

outputFormat: 输出一行一个整数，即最小操作步数。


title: Mzc和体委的争夺战

background: mzc 与 djn 第四弹。

description:
mzc 家很有钱（开玩笑），他家有 $n$ 个男家丁（做过前三弹的都知道）。但如此之多的男家丁吸引来了我们的体委（矮胖小伙），他要来与 mzc 争夺男家丁。

mzc 很生气，决定与其决斗，但 cat 的体力确实有些不稳定，所以他需要你来帮他计算一下最短需要的时间。

inputFormat:
第一行有两个数 $n,m.n$ 表示有 $n$ 个停留站，m表示共有m条路。

之后 $m$ 行，每行三个数 $a_i,b_i,c_i$，表示第 $a_i$ 个停留站到第 $b_i$ 个停留站需要 $c_i$ 的时间。注意，这是双向的。也就是说，从 $b_i$ 个停留站到第 $a_i$ 个停留站也需要 $c_i$ 的时间。

outputFormat: 一行，输出 $1$ 到 $n$ 最短时间。

hint:
$1\le n \leq 2500$，$1\le m \leq 2\times10^5$，$1\le c_i\le 10^6$。

由于 mzc 大大十分着急，所以他只能等待 1s。


title: [CERC2016] 地理哈希网格 Geohash Grid

description:
“地理哈希”是一个将二维平面坐标编码为整数的过程，这将为数据库中地理数据的存储和查询带来方便。在这个问题中，一个地图是一个建立在标准二维笛卡尔坐标系上的2^n行2^n列的矩形网格，越往右x坐标越大，越往上y坐标越大。一个地图格子是一个单位正方形，满足其左下角的点的坐标为(x,y)，其中0<=x,y<2^n。

在2^n行2^n列的地图上一共有2^(2n)个格子。对于一个格子c，它的地理哈希值h(c)是一个2n位的非负二进制整数。从最高位开始考虑整个地图，然后重复下面两个步骤n次，即可得到c的地理哈希值h(c)：

1.把地图分成左右两个面积相等的区域，如果格子c在左半边，那么这一位是0，否则是1。然后将考虑范围缩小到c所在的那半边地图。

2.把地图分成上下两个面积相等的区域，如果格子c在下半边，那么这一位是0，否则是1。然后将考虑范围缩小到c所在的那半边地图。

一个“地理哈希区间”[a,b]表示所有哈希值在[a,b]之间的格子。通常应用中，我们会用一些地理哈希区间去近似表示地图。给定一个格子集合C，以及一个正整数t，那么C的最优t近似是指使用不超过t个地理哈希区间，覆盖住所有C中的格子（覆盖其它格子是允许的），同时满足覆盖住的区域的面积最小。

给定一个地图以及一个格子集合C，C用一个边平行于坐标轴的简单多边形来表示。然后给定q个询问t\_1,t\_2,...,t\_q，对于每个询问t\_k，你需要求出C的最优t\_k近似覆盖住的区域的面积。

inputFormat:
第一行包含一个正整数n(1<=n<=30)，表示地图的尺寸的以2为底的对数。

第二行包含一个正整数m(4<=m<=200)，表示多边形顶点的个数。

接下来m行，每行两个整数x\_i,y\_i(0<=x\_i,y\_i<=2^n)，按逆时针依次表示多边形每个顶点的坐标。

输入数据保证多边形不自交，边平行于坐标轴，且不存在相邻两条边是平行的。

接下来一行包含一个正整数q(1<=q<=100000)，表示询问的个数。

接下来q行，每行一个正整数t\_1,t\_2,...,t\_q(1<=t\_i<=10^9)，依次表示每个询问。

outputFormat: 输出q行，每行一个正整数，依次回答每个询问。

hint:
 ![](https://cdn.luogu.com.cn/upload/pic/4687.png)

区间[3,29]、[33,33]和[36,37]组成最优3近似，其覆盖住的总面积为30。


title: [USACO13JAN] Painting the Fence S

description:
Farmer John has devised a brilliant method to paint the long fence next to his barn (think of the fence as a one-dimensional number line).  He simply attaches a paint brush to his favorite cow Bessie, and then retires to drink a cold glass of water as Bessie walks back and forth across the fence, applying paint to any segment of the fence that she walks past.

Bessie starts at position 0 on the fence and follows a sequence of N moves (1 <= N <= 100,000).  Example moves might be "10 L", meaning Bessie moves 10 units to the left, or "15 R", meaning Bessie moves 15 units to the right.  Given a list of all of Bessie's moves, FJ would like to know what area of the fence gets painted with at least K coats of paint.  Bessie will move at most 1,000,000,000 units away from the origin during her walk.

Farmer John 想出了一个给牛棚旁的长围墙涂色的好方法。（为了简单起见，我们把围墙看做一维的数轴，每一个单位长度代表一块栅栏）

他只是简单的把刷子蘸满颜料，系在他最喜欢的奶牛Bessie上，然后让Bessie来回地经过围墙，自己则在一旁喝一杯冰镇的凉水。（……-\_-|||)

Bessie 经过的所有围墙都会被涂上一层颜料。Bessie从围墙上的位置0出发，并将会进行N次移动(1 <= N <= 100,000)。比如说，“10 L”的意思就是Bessie向左移动了10个单位。再比如说“15 R”的意思就是Bessie向右移动了15个单位。

给出一系列Bessie移动的清单。FJ 想知道有多少块栅栏涂上了至少K层涂料。注意：Bessie最多会移动到离原点1,000,000,000单位远的地方。

inputFormat:
\* 第1行： 两个整数： N K

\* 第2...N+1 行： 每一行都描述了Bessie的一次移动。 （比如说 “15 L"）

outputFormat:
\* 一个整数：被至少涂上K层涂料的栅栏数

（注意：输出的最后一定要输出换行符！否则会WA）

hint:
PS1：来源：usaco jan silver P01 想看原题的请戳http://www.usaco.org/index.php?page=viewproblem2&cpid=226）

PS2：测试数据也可以在在http://www.usaco.org/index.php?page=jan13problems上下载，还可以看到题解（不过是英文的:-D）

PS3:如果有翻译的问题或题目的不理解，可以在问答后面留言的说。


title: [USACO13JAN] Square Overlap S

description:
Farmer John is planning to build N (2 <= N <= 50,000) square fenced-in pastures on his farm, each of size exactly K x K (1 <= K <= 1,000,000). Pasture i is centered at point (x\_i, y\_i) with integer coordinates in the range -1,000,000...1,000,000.  However, in his haste to complete his plans, FJ realizes that he may have accidentally placed two pastures in locations that overlap (by overlap, this means the two pastures share a positive area in common).  No two pastures share the exact same center point.

Given the locations of each of the planned square pastures, please help FJ compute the area shared by the two overlapping pastures.  Output zero if no two squares overlap, and -1 if overlap occurs between more than a single pair of pastures.

在一个直角坐标系中，有N个边长为K的正方形。

给出每一个正方形的中心，请判断所有的正方形是否有重叠。

输入数据保证每一个正方形的中心不重合

inputFormat:
\* 第1行 ：两个正整数： N , K

其中：2 <= N <= 50 000 ，1 <= K <= 1 000 000 ，K保证是偶数

\*第2 .. i+1行：每行有两个整数xi，yi，描述了第i个正方形的中心。

其中：xi，yi均在[-1 000 000，1 000 000]内

outputFormat:
只输出一行：

如果没有正方形重叠，输出“0”；如果有且只有一对正方形重叠，输出它们重叠的面积；如果有两对及以上的正方形重合，输出"-1";

注意：在输出答案后一定要输换行符！


title: 奶牛芭蕾

description:
她的期末汇报演出就在下周，于是Farmer Jhon 就帮她建一个长方形的舞台。

为了防止Bessie从舞台边缘掉下，FJ决定要建一个足够大的舞台。

Bessie的舞蹈将会占用一个由许多1 x 1的正方形方块组成的长方形的区域。为了方便，我们把Bessie的四只脚按如下方式简写：

FR : 前右脚（Front right foot）

FL ：前左脚（Front left foot）

RR ：后右脚（Rear right foot）

RL ：后左脚（Rear left foot）

Bessie将会从一个如下的四个相邻的格子出发，同时她会面向北方。

FL FR

RL RR

Bessie的舞蹈会依据总数为N（1 <= N <= 1000 ) 的指令进行。每一条指令都指示Bessie将一只脚移动一个格子，或者顺时针旋转90°

其中，移动的指示由三个字符组成，其中前两个是脚的代号，最后一个代表脚移动的方向（"F" - 向前 "B" - 向后 "R" - 向右 "L" - 向左）

比如说， "FRF"代表着Bessie的前右脚向前移动一个格子,"RLR"代表她的后左脚将向右移一个格子

当然，我们这里说的方向是以Bessie正面对的方向决定的。

另一方面，旋转的指令也是3个字符，其中前两个字母也是脚的代号，代表着旋转的支点。最后一个字母总是为"P"(pivot)。

比如说， "FRP"代表着Bessie将以前右脚为支点，顺时针旋转90°。

如果我们从图中看，假设现在Bessie的脚是这样的,她正朝向北方。

.. .. ..

.. .. FR

.. FL ..

.. RL RR

那么在进行指令"FRP"之后，她的脚的位置将变成下面这样，同时她将会朝向左边：

RL FL ..

RR .. FR

.. .. ..

.. .. ..

现在已知N条Bessie的舞蹈的指令，请你计算她的整个舞蹈所需要的最小的长方形舞台，使得Bessie的脚不会落到舞台之外。

如果无论怎么样，她都会使自己的两个脚移动到相同的格子里，那么她就会被绊倒，并搞砸这次表演。

在这样的情况下，请输出-1。

不过这是Bessie会被绊倒的唯一的原因，因为她在经过练习之后，身体十分的柔软，可以轻松的做到任何奇怪的动作（比如说把后脚伸到前脚的前面）

（吐槽：那你就不能两只脚放在一起？）

(吐槽2：如果你觉得里面的配图有点怪异的话，就把它复制到记事本 ，把字体改成Courier New即可）

inputFormat:
第一行是整数N ( 1 <= N <= 1000)

第二至N+1行是如题所述的指令，每行有三个字符

outputFormat: 一行，输出舞台的最小面积


title: [USACO13OPEN] What's Up With Gravity S

description:
Captain Bovidian is on an adventure to rescue her crew member, Doctor Beefalo.  Like all great adventures, this story plays out in a two dimensional N by M grid (1 <= N, M <= 500), representing a side view of the captain's world.  Some grid cells are empty while others are blocked and cannot be traversed.

Unfortunately, Captain Bovidian cannot jump.  She must obey the following rules of physics while traversing her world.

1) If there is no cell directly underneath Captain Bovidian (that is, if she is at the edge of the grid), then she flies out into space and fails her mission.

2) If the cell directly underneath Captain Bovidian is empty, then she falls into that cell.

3) Otherwise:

a) Captain Bovidian may move left or right if the corresponding cell exists and is empty.

b) Or, Captain Bovidian may flip the direction of gravity.

When Captain Bovidian changes the direction of gravity, the cell that's 'underneath' her (as mentioned in rules 1 and 2) toggles between the cell with one higher row index and the cell with one lower row index (the first row in the input has index 1, and the last row has index N). Initially, the cells with one higher row index are underneath Captain Bovidian.

Doctor Beefalo is lost somewhere in this world.  Help Captain Bovidian arrive at her cell using the least number of gravity flips as possible.  If it is impossible to reach Doctor Beefalo, please output -1.

Bovidian 船长正在拯救她的船员，Beefalo 博士。

和所有伟大的冒险故事一样，这个故事也是发生在一个2D平面上的。囧

这个平面是M\*N的格子组成的网格，代表着船长的世界的一个侧视图。

有些格子是空的，另一些则是实心的，并且不能直接通过。

很不幸的是，船长跳不起来。她必须遵守这个世界的特殊物理法则。

1）如果船长的正下方没有方块（换句话说，即使她正在网格的边缘），那么她就会掉入宇宙中，同时意味着冒险失败。

2）如果船长的正下方的方块是空的，那么她就会掉到这个方块，

3）在不满足1）与2）的情况下，船长可以做一下的事情：

a) 如果左边(或右边）的方格是空的，那么她可以走到那个格子。

b船长可以翻转重力的方向

当船长改变翻转重力的方向时，我们就改变船长”下方“的定义。

”下方“的定义只能是两种

(A)比船长位置所在的方格的列编号更大的格子，

(B)比船长位置所在的方格的列编号更小的格子,

一开始的时候，“下方”的定义是比船长位置所在方格的列编号更大的格子。

Beefalo博士正迷失在这个世界中的某一处，请帮助船长从起点到达博士的地方。

如果可以到达，请输出最少需要的翻转重力的次数。

如果不可以到达，请输出-1

inputFormat:
第1行输入两个整数 N,M

第2行到N+1行中，第i+1行则是代表船长世界的第i行。每行有M个字符。

其中","代表着一个空的格子，"#"代表着一个实心的格子，"C"代表着船长的位置，"D"代表着博士的位置。

outputFormat:
一行，输出一个整数。

如果船长可以到达，请输出最少需要的翻转重力的次数。

如果不可以到达，请输出-1

hint:
输出解释：

首先，船长在（4,2），接着她翻转重力，到达（2,2）

接着她向右走走到（2,4），接着她第二次翻转重力，到达（4,4）

然后她继续向右走到（4,5），最后在翻转一次重力，到达博士所在的（3,5）


title: Blink

description:
Farmer John 对于农场里昏暗的灯光很不满，于是他刚刚装上一个装饰精美的新吊灯。

这个吊灯由 $N(3 \le N \le 16)$ 个灯组成，并排成一个**圆圈**。

奶牛们对于这个新的发光装置很有兴趣。他们喜欢玩这样的一个游戏：

在在时刻 $T$ 时，对于每一盏灯 $i$，如果在时刻 $T-1$ 时，$i$ 左边的灯 $(1<i\le n$ 时为 $i-1$，$i=1$ 时，为 $n)$ 是开的，那么**改变第 $i$ 盏灯的状态**，否则不做操作。

他们会在 $B(1 \le B \le 10^{15})$ 个单位的时间里一直进行这样的操作。

**请注意，$B$ 可能会超过一般的 $32$ 位整数的范围。**

现在已知每一个灯的初始状态，请计算出在经过 $B$ 个单位的时间后，每一个灯的状态。

inputFormat:
第 $1$ 行是两个整数，$N$ 和 $B$。

第 $2 \sim 1+N$ 中，第 $i+1$ 行描述了灯的初始状态，用 $0$ (关) 与 $1$ (开) 表示。

outputFormat: $N$ 行，第 $i$ 行应输出一个整数，描述灯的最终状态，用 $0$ (关) 与 $1$ (开) 表示。


title: Photo

description:
Farmer John 打算给他的 $n$ 头奶牛照相。

他们排成一条线，并且依次取 $1\sim n$ 作为编号。

每一张照片可以拍摄到这列奶牛中一个连续的区间中的奶牛。

对于每一头奶牛，FJ 都想要让 Ta 至少出现在一张照片里。

不幸的是，有 $k$ 对关系不好的奶牛，他们拒绝出现在同一张照片里。

已知所有关系不好的奶牛所在的位置，请计算出 FJ 需要的最小需要拍摄的照片数量。

inputFormat:
第一行：两个整数:$n$，$k$。

第 $2\ldots k+1$ 行中，第 $i+1$ 行有两个整数，记为 $a_i$ 与 $b_i$。它们代表着处在队列中第 $a_i$ 头奶牛与第 $b_i$ 头奶牛是关系不好的，它们不能出现在同一张照片里。

outputFormat: 一个整数，代表 FJ 需要的最小需要拍摄的照片数量。


title: Haywire

description:
Farmer John有 $N$ 只奶牛（$4 \leq N \leq 12$，$N$ 是偶数）。

他们建立了一套原生的系统，使得奶牛与他的朋友可以通过由干草保护的线路来进行对话交流。

每一头奶牛在这个牧场中正好有 $3$ 个朋友，并且他们必须把自己安排在一排干草堆中。

一条长 $L$ 的线路要占用刚好 $L$ 堆干草来保护线路。

比如说，如果有两头奶牛分别在草堆 $4$ 与草堆 $7$ 中，并且他们是朋友关系，那么我们就需要用 $3$ 堆干草来建造线路，使他们之间能够联系。

假设每一对作为朋友的奶牛都必须用一条单独的线路来连接，并且我们可以随便地改变奶牛的位置，请计算出我们建造线路所需要的最少的干草堆。

inputFormat:
第 $1$ 行：一个整数 $N$。为了方便，我们给奶牛用 $1\sim N$ 的数字进行编号。

第 $2, 3, \cdots, N + 1$ 行：每一行都有三个在 $1\sim N$ 中的整数。第 $i+1$ 行的数字代表着第 $i$ 头奶牛的三个朋友的编号。显然，如果奶牛 $i$ 是奶牛 $j$ 的三个朋友之一，那么奶牛 $j$ 也是奶牛 $i$ 的三个朋友之一。

outputFormat: 一个整数，代表着建造线路需要的干草堆数量的最小值。

hint: 样例解释： 奶牛最好的排列是 `6, 5, 1, 4, 2, 3`, 这个时候我们只需要 $17$ 个单位的干草堆。


title: [USACO13OPEN] Fuel Economy S

description:
Farmer John has decided to take a cross-country vacation. Not wanting his cows to feel left out, however, he has decided to rent a large truck and to bring the cows with him as well!

The truck has a large tank that can hold up to G units of fuel (1 <= G <= 1,000,000).  Unfortunately, it gets very poor mileage: it consumes one unit of fuel for every unit of distance traveled, and FJ has a total of D units of distance to travel along his route (1 <= D <= 1,000,000,000).

Since FJ knows he will probably need to stop to refill his tank several times along his trip, he makes a list of all the N fuel stations along his route (1 <= N <= 50,000).  For each station i, he records its distance X\_i from the start of the route (0 <= X\_i <= D), as well as the price Y\_i per unit of fuel it sells (1 <= Y\_i <= 1,000,000).

Given this information, and the fact that FJ starts his journey with exactly B units of fuel (0 <= B <= D), please determine the minimum amount of money FJ will need to pay for fuel in order to reach his destination. If it is impossible for him to reach the destination, please output -1. Note that the answer to this problem may not fit into a standard 32-bit integer.

Farmer John 决定去一次跨国旅游度假。为了不让他的奶牛们感到被抛弃，他决定租一辆大卡车来带他的奶牛们一起旅行。

这辆卡车有一个很大的油箱，可以装下 $G$ 个单位的油（$1 \le G \le {10}^6$），不幸的是，卡车的耗油量也很大，卡车每运动一个单位的距离，就要消耗一个单位的油。Farmer John 要在他的旅程中走 $D$ 个单位的距离。（$1 \le D \le {10}^9$）

因为 FJ 直到他可能要几次在旅途中停下，给油箱加油，所以他把在旅途沿路上的 $N$ 个加油站的记录做成了表格。对于第 $i$ 个加油站，他记录了加油站与起点的距离 $X_i$（$0 \le X_i \le D$），以及加油站中每单位油的价格 $Y_i$（$1 \le Y_i \le {10}^6$）。

已知以上所给的信息，以及 FJ 在路途开始时拥有的燃油的数量 $B$（$0 \le B \le D$），请计算出 FJ 到达目的地时花费的油费用的最小值。如果 FJ 无法到达旅途的终点，那么请输出 `-1`。本题的答案可能无法使用 32 位整数储存。

inputFormat:
第一行： 四个整数：$N, G, B, D$

接下来 $N$ 行：每一行都有两个整数 $X_i$ 与 $Y_i$，意义如上所述

outputFormat: 一个整数，如果 FJ 无法到达旅途的终点，那么输出 `-1`，否则输出 FJ 到达目的地时花费的油费用的最小值。

hint: 样例解释：FJ 先移动 $2$ 个单位，然后停下购买 $2$ 个单位的油（要花费 $40 \times 2$）。然后一直前进到距离起点 $5$ 个单位的地方，此时油箱为空。这时向油箱里加满油（要花费 $7 \times 10$）。再向前走 $5$ 个单位，加 $2$ 个单位的油（花费 $12 \times 2$）。最后一直走到终点。此时总花费是 $174$。


title: [USACO04OPEN] Turning in Homework G

description:
贝茜有 $ C $ ( $ 1 \leq C \leq 1000 $ )门科目的作业要上交，之后她要去坐巴士和奶牛同学回家。

每门科目的老师所在的教室排列在一条长为 $ H $ ( $ 1 \leq H \leq 1000 $ )的走廊上，他们只在课后接收作业，交作业不需要时间。贝茜现在在位置0，她会告诉你每个教室所在的位置，以及走廊出口的位置。她每走1个单位的路程，就要用1秒。她希望你计算最快多久以后她能交完作业并到达出口。

inputFormat:
第一行：三个整数 $C$，$H$ 和 $B$，$1 \le C \le 1000,1 \le H \le 1000,0 \le B \le H$。

第二行到 $C+1$ 行：第 $i+1$ 行有两个整数 $X_i$ 和 $T_i$，$0 \le X_i \le H,0 \le T_i \le 10000$。

 $B$ 表示车站位置。

 $X_i$ 表示第  $i$ 份作业应该在  $X_i$ 这个位置交。

 $T_i$ 表示这个位置（教室）的这个科目老师（也就是收这份作业的老师）下课的时间。

outputFormat: 单个整数，表示贝西交完作业后走到车站的最短时间

hint: 走到坐标 8 处，第 9 分钟交一本作业，等到第 12 分钟时，交另一本作业。再走到坐标 4 处交作业，最后走到坐标 3 处，交最后一本作业，此地就是车站所在位置，共用时 22 分钟


title: [USACO14MAR] Watering the Fields S

description:
Due to a lack of rain, Farmer John wants to build an irrigation system to

send water between his N fields (1 <= N <= 2000).

Each field i is described by a distinct point (xi, yi) in the 2D plane,

with 0 <= xi, yi <= 1000.  The cost of building a water pipe between two

fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his

fields are linked together -- so that water in any field can follow a

sequence of pipes to reach any other field.

Unfortunately, the contractor who is helping FJ install his irrigation

system refuses to install any pipe unless its cost (squared Euclidean

length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all

his fields with a network of pipes.

给定 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$，如果想连通第 $i$ 个点与第 $j$ 个点，需要耗费的代价为两点的距离。第 $i$ 个点与第 $j$ 个点之间的距离使用欧几里得距离的平方进行计算，即：
$$(x_i-x_j)^2+(y_i-y_j)^2$$
我们规定耗费代价小于 $c$ 的两点无法连通，求使得每两点都能连通下的最小代价，如果无法连通输出 `-1`。

inputFormat:
\* Line 1: The integers N and C.

\* Lines 2..1+N: Line i+1 contains the integers xi and yi.

第一行两个整数 $n,c$ 代表点数与想要连通代价不能少于的一个数。
接下来 $n$ 行每行两个整数 $x_i,y_i$ 描述第 $i$ 个点。

outputFormat:
\* Line 1: The minimum cost of a network of pipes connecting the

fields, or -1 if no such network can be built.

一行一个整数代表使得每两点都能连通下的最小代价，如果无法连通输出 `-1`。

hint:
INPUT DETAILS:

There are 3 fields, at locations (0,2), (5,0), and (4,3).  The contractor

will only install pipes of cost at least 11.

OUTPUT DETAILS:

FJ cannot build a pipe between the fields at (4,3) and (5,0), since its

cost would be only 10.  He therefore builds a pipe between (0,2) and (5,0)

at cost 29, and a pipe between (0,2) and (4,3) at cost 17.

Source: USACO 2014 March Contest, Silver

### 数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le x_i,y_i \le 1000$，$1 \le c \le 10^6$。

### 说明

Translated by 一只书虫仔。


title: [USACO14MAR] The Lazy Cow S

description:
It's a hot summer day, and Bessie the cow is feeling quite lazy.  She wants

to locate herself at a position in her field so that she can reach as much

delicious grass as possible within only a short distance.

The field Bessie inhabits is described by an N by N grid of square cells

(1 <= N <= 400).  The cell in row r and column c (1 <= r,c <= N) contains

G(r,c) units of grass (0 <= G(r,c) <= 1000).  From her initial square in

the grid, Bessie is only willing to take up to K steps (0 <= K <= 2\*N).

Each step she takes moves her to a cell that is directly north, south,

east, or west of her current location.

For example, suppose the grid is as follows, where (B) describes Bessie's

```cpp
50    5     25*   6     17
14    3*    2*    7*    21
99*   10*   1*(B) 2*    80*
8     7*    5*    23*   11
10    0     78*   1     9
```

initial position (here, in row 3, column 3):

If K=2, then Bessie can only reach the locations marked with \*s.

Please help Bessie determine the maximum amount of grass she can reach, if

she chooses the best possible initial location in the grid.

奶牛贝茜非常懒惰，她希望在她的地盘内找到一点最佳位置居住，以便在有限的步数内可以吃到尽量多的青草。

她的地盘是一个 $N \times N(1\le N \le 400)$ 的矩阵，第 $r$ 行 $c$ 列包含 $G(r,c)$ 单位的青草 $(0 \le G(r,c) \le 1000)$。从她的居住点，她最多愿意走 $K$ 步 $(0 \le K \le 2 \times N)$，每一步她可以走到上与她相邻的某个格子。

inputFormat:
\* Line 1: The integers N and K.

\* Lines 2..1+N: Line r+1 contains N integers describing row r of the

grid.

outputFormat:
\* Line 1: The maximum amount of grass Bessie can reach, if she chooses

the best possible initial location (the location from which

she can reach the most grass).

hint:
OUTPUT DETAILS:

In the example above, Bessie can reach 342 total units of grass if she

locates herself in the middle of the grid.

Source: USACO 2014 March Contest, Silver


title: [USACO14MAR] Mooo Moo S

description:
Farmer John has completely forgotten how many cows he owns!  He is too embarrassed to go to his fields to count the cows, since he doesn't want the cows to realize his mental lapse.  Instead, he decides to count his cows secretly by planting microphones in the fields in which his cows tend to gather, figuring that he can determine the number of cows from the total volume of all the mooing he hears.

FJ's N fields (1 <= N <= 100) are all arranged in a line along a long straight road.  Each field might contain several types of cows; FJ owns cows that come from B different breeds (1 <= B <= 20), and a cow of breed i moos at a volume of V(i) (1 <= V(i) <= 100).  Moreover, there is a strong wind blowing down the road, which carries the sound of mooing in one direction from left to right: if the volume of mooing in some field is X, then in the next field this will contribute X-1 to the total mooing volume (and X-2 in the field after that, etc.). Otherwise stated, the mooing volume in a field is the sum of the contribution due to cows in that field, plus X-1, where X is the total mooing volume in the preceding field.

Given the volume of mooing that FJ records in each field, please compute the minimum possible number of cows FJ might own.

The volume FJ records in any field is at most 100,000.

### 题目背景
农夫约翰完全忘了他有多少头牛了！他不好意思到牧场里去数牛，因为他不想让牛意识到他的健忘。取而代之的是，他决定在奶牛聚集的牧场里安装麦克风，秘密计算出他能从中听到的所有牛叫声的总音量，以便以此确定奶牛的数量。
### 题目描述
$FJ$ 的 $N(1\le N\le 100)$ 个牧场都是沿着一条笔直的道路分布的。每一个牧场可能有许多种品种的奶牛； $FJ$ 拥有 $B(1\le B\le 20)$ 个不同品种的奶牛，而第 $i$ 种奶牛的叫声音量为 $V_i(1\le V_i \le 100)$ 。此外，有一股强风沿着道路吹来，将牛的叫声从左往右传递，如果某个牧场的总音量是 $x$ ，那么它将传递 $x-1$ 的音量到右边的下一个牧场。这就意味着，一个牧场里的总音量是处在该牧场的奶牛所发出的音量加上左边前一个牧场的总音量 $-1$ 。数据保证，每一个牧场内由该牧场所有奶牛所发出的总音量最多为$10^5$。
### 输入格式
第 $1$ 行：两个用空格分隔的整数 $N$ 和 $B$。
第 $2...B+1$ 行：第 $i+1$ 行包含整数 $V_i$ 。
第 $B+2...B+N+1$ 行：第 $B+i+1$ 行表示在第 $i$ 个牧场内所能监听到的总音量。
### 输出格式
共一行，即 $FJ$ 拥有的最小奶牛数量。

如果 FJ 不可能拥有一种牧场配置满足给出的条件，输出 `-1`。
### 说明/提示
#### 输入说明：
$FJ$ 拥有 $5$ 个牧场，每个牧场总音量从左到右分别为为$0、17、16、20、19$。 $FJ$ 有两种不同品种的奶牛；第一种奶牛的叫声音量是 $5$，第二种奶牛的叫声音量是 $7$ 。
#### 输出说明：
$2$ 号牧场场有  $2$ 头 $1$ 号品种的奶牛， $1$ 头 $2$ 号品种奶牛；还有一头牛在 $4$ 号牧场，共 $4$ 头奶牛。

inputFormat:
\* Line 1: The integers N and B.

\* Lines 2..1+B: Line i+1 contains the integer V(i).

\* Lines 2+B..1+B+N: Line 1+B+i contains the total volume of all mooing

in field i.

outputFormat:
\* Line 1: The minimum number of cows owned by FJ, or -1 if there is no

configuration of cows consistent with the input.

hint:
INPUT DETAILS:

FJ owns 5 fields, with mooing volumes 0,17,16,20,19.  There are two breeds

of cows; the first moos at a volume of 5, and the other at a volume of 7.

OUTPUT DETAILS:

There are 2 cows of breed #1 and 1 cow of breed #2 in field 2, and there is

another cow of breed #1 in field 4.

Source: USACO 2014 March Contest, Silver


title: [HAOI2007] 上升序列

description:
对于一个给定的 $S=\{a_1,a_2,a_3,…,a_n\}$ , 若有 $P=\{a_{x_1},a_{x_2},a_{x_3},…,a_{x_m}\}$ , 满足 $(x_1<x_2<…<x_m)$  且 $(a_{x_1}<a_{x_2}<…<a_{x_m})$ 。那么就称 $P$ 为 $S$ 的一个上升序列。如果有多个 $P$ 满足条件，那么我们想求字典序最小的那个。

任务：

给出 $S$ 序列，给出若干询问。对于第 $i$ 个询问，求出长度为 $L_i$ 的上升序列，如有多个，求出字典序最小的那个（即首先 $x_1$ 最小，如果不唯一，再看 $x_2$ 最小……），如果不存在长度为 $L_i$ 的上升序列，则打印 `Impossible`。

inputFormat:
第一行一个 $N$，表示序列一共有 $N$ 个元素。

第二行 $N$ 个数，为 $a_1, a_2 , \cdots , a_n$。

第三行一个 $M$，表示询问次数。下面接 $M$ 行每行一个数 $L$，表示要询问长度为 $L$ 的上升序列。

outputFormat: 对于每个询问，如果对应的序列存在，则输出，否则打印 `Impossible`。

hint: $N \le 10000$，$M \le 1000$，保证数据随机。


title: [HAOI2007] 理想的正方形

description: 有一个 $a \times b$ 的整数组成的矩阵，现请你从中找出一个 $n \times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

inputFormat:
第一行为 $3$ 个整数，分别表示 $a,b,n$ 的值。

第二行至第 $a+1$ 行每行为 $b$ 个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

outputFormat: 仅一个整数，为 $a \times b$ 矩阵中所有“ $n \times n$ 正方形区域中的最大整数和最小整数的差值”的最小值。


title: [HAOI2007] 分割矩阵

description:
将一个 $a\times b$ 的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了 $(n-1)$ 次后，原矩阵被分割成了 $n$ 个矩阵。（每次分割都只能沿着数字间的缝隙进行）

原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成 $n$ 个矩阵，并使各矩阵总分的均方差最小。

请编程对给出的矩阵及 $n$，求出均方差的最小值。

inputFormat:
第一行为 $3$ 个整数，表示 $a,b,n(1<a,b,n\le 10)$ 的值。

第二行至第 $a+1$ 行每行为 $b$ 个小于 $100$ 的非负整数，表示矩阵中相应位置上的分值。每行相邻两数之间用一个空格分开。

outputFormat: 仅一个数，为均方差的最小值。（四舍五入精确到小数点后 $2$ 位）


title: [HAOI2007] 覆盖问题

description: 某人在山上种了 $N$ 棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定 用 $3$ 个 $L \times L$ 的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第 $i$ 棵小树的坐标为 $(X_i,Y_i)$ ，$3$ 个 $L \times L$ 的正方形的边要求平行于坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求 $L$ 最小值。

inputFormat: 接下来有 $N$ 行，第 $i+1$ 行有 $2$ 个整数 $X_i,Y_i$，表示第 $i$ 棵树的坐标，保证不会有 $2$ 个树的坐标相同。

outputFormat: 一行，输出最小的 $L$ 值。


title: [HAOI2007] 修筑绿化带

description:
为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在花坛四周修建一片绿化带，让花坛被绿化带围起来。

如果把公园看成一个 $M\times N$ 的矩形，那么花坛可以看成一个 $C\times D$ 的矩形，绿化带和花坛一起可以看成一个 $A\times B$ 的矩形。

如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，绿化带的肥沃度为 $A\times B$ 块的肥沃度减去 $C\times D$ 块的肥沃度。

为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。

inputFormat:
第一行有六个正整数 $M,N,A,B,C,D$。

接下来一个 $M\times N$ 的数字矩阵，其中矩阵的第 $i$ 行 $j$ 列元素为一个整数 $x_{i,j}$，表示该花园的第 $i$ 行第 $j$ 列的土地 “肥沃度”。

outputFormat: 一个正整数，表示绿化带的最大肥沃程度。

hint:
对于 $30\%$ 的数据，$1\leq M,N\leq 50$。

对于 $100\%$ 的数据，$1\leq M,N\leq 1000$，$1\leq A\leq M$，$1\leq B\leq N$，$1\leq C\leq A-2$，$1\leq D\leq B-2$，$1\leq x_{i,j}\leq 100$。


title: [HAOI2012] 容易题

description:
有一个长度为 $m$ 的正整数数列 $A$，满足 $\forall i \in A, i \in [1, n]$。

现在给定一些限制（$A_x$ 不能为 $y$）。设数列 $A$ 的积为 $\prod A$，求所有可能数列的积相加起来的和。

换言之，令 $S$ 为所有可能的数列情况 $\{A, A', \ldots\}$，求

$$ \sum_{T \in S} \prod T $$

答案对 $10 ^ 9 + 7$ 取模。

inputFormat:
第一行三个正整数 $n, m, k$。$n, m$ 如题目所示，$k$ 表示限制的条数。

接下来 $k$ 行，每行两个正整数 $x, y$ 表示限制 $A_x \neq y$。

outputFormat:
一行一个正整数表示答案。

如果没有任何合法数列，输出 $0$。


title: [HAOI2012] 高速公路

background: Y901 高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。

description:
Y901 高速公路是一条由 $n-1$ 段路以及 $n$ 个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为 $1 \sim n$，从收费站 $i$ 行驶到 $i+1$（或从 $i+1$ 行驶到 $i$）需要收取 $v_i$ 的费用。高速路刚建成时所有的路段都是免费的，即所有 $v_i = 0$。

政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

无聊的小 A 同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题：对于给定的 $l,r$，在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$，那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?

inputFormat:
第一行有两个整数，分别表示收费站个数 $n$，和询问与调整费用的总数 $m$。

接下来 $m$ 行，每行表示一次调整或询问，首先有一个字符 $op$。

- 若 $op$ 为 `C`，则后面有三个整数 $l, r, v$，表示将第 $l$ 个收费站到第 $r$ 个收费站之间所有**道路**的通行费用增加 $v$。
- 若 $op$ 为 `Q`，则后面有两个整数 $l, r$，对于给定的 $l, r$，请回答小 A 的问题。

outputFormat:
对于每次询问，输出一行一个既约分数表示答案。

若答案为一个整数 $a$，请输出 `a/1`。


title: [HNOI2001] 矩阵乘积

description:
已知矩阵：

$$A_{m\times n}=\begin{bmatrix}a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots\\ a_{m,1} & a_{m,2} & \cdots &a_{m,n} \end{bmatrix} ,B_{n\times p}=\begin{bmatrix}b_{1,1} & b_{1,2} & \cdots & b_{1,p}\\ b_{2,1} & b_{2,2} & \cdots & b_{2,p} \\ \vdots & \vdots & \ddots & \vdots\\ b_{n,1} & b_{n,2} & \cdots &b_{n,q} \end{bmatrix}$$

当矩阵 $A$ 的列数与矩阵 $B$ 的行数相同时，则 $A$ 与 $B$ 可以相乘，其乘积为一个 $m\times p$ 的矩阵 $D$：

$$D_{m\times p}=\begin{bmatrix} d_{1,1} & d_{1,2} & \cdots & d_{1,p}\\ d_{2,1} & d_{2,2} & \cdots & d_{2,p} \\ \vdots & \vdots & \ddots & \vdots\\ d_{m,1} & d_{m,2} & \cdots & d_{m,p}\end{bmatrix}$$

其中 $d_{i,j}=\sum^n_{k=1} a_{i,k} \times b_{k,j}$，简记为 $D=A\times B$。

现已知三个矩阵 $A,B,C$，这三个矩阵大多数元素为 $0$，我们把这种矩阵称为稀疏矩阵。因此，我们采用三元组 $i,j,a$ 来表示矩阵的第 $i$ 行第 $j$ 列的值为 $a$ 其余未列出的元素均为 $0$；在计算机中，我们仅给出非零元素的三元组，而且使用行优先法给出稀疏矩阵的三元组，首先是第一行按列给出，然后是第二行按列给出……

例如，矩阵：$\begin{bmatrix}1&0&0&0\\0&0&2&-1\\0&1&2&3\\0&0&0&0\end{bmatrix}$ 那么，矩阵的三元组表示为：

```plain
1 1 1
2 3 2
2 4 -1
3 2 1
3 3 2
3 4 3
```

你的任务就是：计算矩阵 $D=A\times B\times C$。

inputFormat:
第一行为两个正整数 $x,y$，分别表示输出结果所在的行和列。

第二行为四个整数 $m,n,o,p$，表明 $A$ 为$m\times n$ 的矩阵，$B$ 为 $n\times o$ 的矩阵，$C$ 为 $o\times p$ 的矩阵。

第三行以后的每一行有三个整数分别是矩阵的三元组表示法中的一个元素的值，每个矩阵之间有一个空行。表示的顺序是矩阵 $A,B,C$。

outputFormat: 仅一个整数，为 $D$ 的第 $x$ 行第 $y$ 列的元素的值。

hint:
#### 数据规模与约定
对于全部的测试点，保证 $1\le m,n,o,p\le 6\times 10^3$，三元数组的总个数不大于 $6\times 10^3$。数据之间用空格分开。


title: [HNOI2001] 软件开发

description:
某软件公司正在规划一项 $n$ 天的软件开发计划，根据开发计划第 $i$ 天需要 $n_i$ 个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。

消毒方式有两种，$A$ 种方式的消毒需要 $a$ 天时间，$B$ 种方式的消毒需要 $b$ 天，$A$ 种消毒方式的费用为每块毛巾 $f_A$, $B$ 种消毒方式的费用为每块毛巾 $f_B$，而买一块新毛巾的费用为 $f$（新毛巾是已消毒的，当天可以使用）。公司经理正在规划在这 $n$ 天中，每天买多少块新毛巾、每天送多少块毛巾进行 $A$ 种消毒和每天送多少块毛巾进行 $B$ 种消毒。当然，公司经理希望费用最低。

你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行 $A$ 种消毒和多少毛巾进行 $B$ 种消毒，使公司在这项 $n$ 天的软件开发中，提供毛巾服务的总费用最低。

inputFormat:
第一行为六个整数 $n,a,b,f,f_A,f_B$。

第二行为 $n$ 个整数 $n_1,n_2,\ldots,n_n$。

outputFormat: 仅一个整数，为最少的费用。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，保证 $b>a$，$f>f_A>f_B$，$1\le f,f_A,f_B\le 60$，$1\le n\le 10^3$。


title: [HNOI2001] 产品加工

description:
某加工厂有 A、B 两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。

某一天，加工厂接到  $n$ 个产品加工的任务，每个任务的工作量不尽一样。

你的任务就是：已知每个任务在 A 机器上加工所需的时间  $t_1$，B 机器上加工所需的时间  $t_2$ 及由两台机器共同加工所需的时间  $t_3$，请你合理安排任务的调度顺序，使完成所有  $n$ 个任务的总时间最少。

inputFormat:
第一行为一个整数  $n$。

接下来  $n$ 行，每行三个非负整数  $t_1,t_2,t_3$，分别表示第  $i$ 个任务在 A 机器上加工、B 机器上加工、两台机器共同加工所需要的时间。如果所给的时间  $t_1$ 或  $t_2$ 为  $0$ 表示任务不能在该台机器上加工，如果  $t_3$ 为  $0$ 表示任务不能同时由两台机器加工。

outputFormat: 仅一行一个整数，表示完成所有  $n$ 个任务的最少总时间。

hint: 对于所有数据，有  $1\le n\le 6\times 10^3$， $0\le t_1,t_2,t_3\le 5$。


title: [HNOI2001] 棋盘变换

description:
一个 $n\times n$ 的棋盘，在其中填入 $1$ 和 $-1$。经过一次变换后，方格里的每个数将会变成变换之前与之相邻的四个数的积。例如：

![](https://cdn.luogu.com.cn/upload/image_hosting/2q4jbad8.png)

但有一些状态，变换前和变换后是一样的，例如全部是 $1$ 的状态。这种状态被称为不变状态。

你的任务是要找到所有本质不同的不变状态（旋转或翻转之后的状态被视为是本质上相同的）。

inputFormat: 一行一个正整数 $n$。

outputFormat: 一行一个正整数表示所有本质不同的方案数。

hint:
$1\le n\le 30$。

题目给出范围内，不变状态总数 $<9\times 10^3$。


title: [HNOI2001] 遥控赛车比赛

description:
全国遥控赛车大赛近日在星沙举行。竞赛选用一块大小为 $N\times M$ 的场地作为竞赛场地，要求选手的赛车在最短的时间内从起点移动到终点。虽然赛场地形高低有少许的起伏，但并不存在无法到达的地点。但是在赛场上增加了许多无法穿越的障碍物，若赛车在到达终点前撞上障碍物，就视为任务失败。

在赛车的马力和灵活性等性能相差较小的情况下，要控制速度极快的赛车绕开障碍物移动到终点，关键是提高选手的反应灵敏度，即两次改变赛车运动方向所间隔的最短时间，也可称为选手的反应时间。使自己能够更快地控制赛车改变前进的方向。

当然，由于选手反应灵敏度的不同，可选择的路径就会大不相同。如图 $1$ 和图 $2$ 所示，对于同一个赛场，两位选手的反应时间分别为 $2$ 秒和 $1$ 秒，而其到达终点所需的时间分别为 $18$ 秒和 $16$ 秒（赛车每秒可沿当前方向移动一格，从起点出发时算改变一次方向）。

由图 $1$ 和图 $2$ 可知，赛车的最短路线长度是由选手的反应灵敏度所决定的，当选手的反应很慢时，可能就不会存在可行的路径。你的任务是：在能够完成赛程（即存在从起点到终点的路径）的条件下，求出选手每个可能的反应时间所对应的最短路线长度。

![](https://cdn.luogu.com.cn/upload/pic/1294.png)

inputFormat:
第一行包含两个整数 $N$ 和 $M$，表示赛场的行数和列数。$1≤N, M≤100$。

第二行有四个整数 $x1$、$y1$、$x2$、$y2$，表示赛程的起点和终点的位置分别为 $(x1, y1$ 和 $x2,y2$。

接下来 $N$ 行是一个 $N×M$ 的 0-1 矩阵，矩阵中第 $i$ 行第 $j$ 列元素 $A_{i,j}=1$ 表示赛场中位置 $(i,j)$ 为赛道，$A_{i,j}=0$ 表示赛场中位置 $(i,j)$ 有障碍物。

outputFormat: 输出文件可能有多行，其中每行输出一个可能的选手反应时间及该时间所对应的最短路线长度。输出文件中必须包含所有符合题目要求的选手反应时间。注意：由于选手的反应时间不可能很慢，因而不必考虑选手反应时间大于 $10$ 秒的情况，只需输出 $10$ 以内（包含 $10$）的解。


title: [HNOI2001] 洗牌机

description:
剀剀和凡凡有 $n$ 张牌（依次标号为 $1,2,\ldots,n$）和一台洗牌机。假设 $n$ 是奇数。洗牌机的功能是进行如下的操作：对所有位置 $i(1\le i\le n)$，如果位置 $i$ 上的牌是 $j$，而且位置 $j$ 上的牌是 $k$，那么通过洗牌机后位置 $i$ 上的牌将是 $k$。

剀剀首先写下数值 $1,2,\ldots,n$ 的一个随机排列：$a_1,a_2,\ldots,a_n$。然后他这样来排列牌的顺序：位置 $a_i$ 放置牌 $a_{i+1}$, （对于 $1\le i\le n-1$），而 $a_n$ 放置牌 $a_1$。这样排列后，牌的顺序就为 $x_1,x_2,\ldots ,x_n$。然后，他把这种顺序排列的牌放入洗牌机洗牌 $s$ 次，得到牌的顺序为 $p_1,p_2,\ldots,p_n$。现在，剀剀把牌的最后顺序和洗牌次数告诉凡凡，要凡凡猜出牌的最初顺序 $x_1,x_2,\ldots,x_n$。

inputFormat:
第一行为整数 $n$ 和 $s$。

第二行为牌的最终顺序  $p_1,p_2,\ldots,p_n$。

outputFormat: 为一行，即牌的最初顺序 $x_1,x_2,\ldots,x_n$。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，保证 $1\le n,s\le 10^3$。

数据保证，从 $i=1$ 开始，设第 $i$ 张牌上数是 $j$，则赋值 $i=j$ 后继续此操作，最终会遍历所有牌。


title: [HNOI2001] 洋洋吃蛋糕

description:
洋洋是有名的“小馋猫”。他爱吃许多东西，但也有一些不爱吃的东西。一天，洋洋发现家中有一块刚烤好的长方形的蛋糕，而且蛋糕里放上了各种各样的东西，有爱吃的草莓，奶酪，也有不爱吃的核桃仁。这使得洋洋有一些为难，到底是吃还是不吃呢？这时，爷爷看出了洋洋的烦恼，然后说：你若能够遵守以下几条规则的话，蛋糕可以随便吃：

1. 蛋糕的尺寸为 $n\times m$，在吃之前，需先把蛋糕划分成 $n\times m$ 个单位蛋糕块，然后对每一个单位蛋糕块按照自己的喜好给其打分，分数越高表示越爱吃，反之则表示越不爱吃。这个分数为这一个单位蛋糕块的好吃程度值。

1. 每一个单位蛋糕块要么全部被吃掉，要么不吃。

1. 被吃掉的蛋糕块必须成长方形或正方形，是由一些单位蛋糕块组成的，且蛋糕块的两边必须和原来的大蛋糕块的两边平行。一块蛋糕块的好吃程度值就是所有组成这个蛋糕块的单位蛋糕块的分数之和。

1. 被吃掉的蛋糕块的尺寸任意，且块数也任意。

1. 为了保持蛋糕块的美观，所有被吃掉的蛋糕块在原来的大蛋糕块中的位置不能相邻，且不能重叠。如图 1 和图 2 的吃法是不允许的，而图 3 和图 4 的吃法是允许的。
![](https://cdn.luogu.com.cn/upload/pic/1295.png)
1. 所有被吃掉的蛋糕块的好吃程度值之和最大。

爷爷的话并没有消去洋洋的烦恼，因为他只能做好第一点，而不知如何选择蛋糕块。于是，洋洋请你帮忙选择蛋糕块，以使得所有被吃掉的蛋糕块的好吃程度值之和最大。

inputFormat:
第一行是两个整数 $n$ 和 $m$。

以下 $n$ 行是一个 $n$ 行 $m$ 列的矩阵，第 $i$ 行第 $j$ 列的整数表示单位蛋糕块 $(i,j)$ 的好吃程度值 $c$。

outputFormat: 只有一个数，即为最大的好吃程度值。


title: [HNOI2002] 沙漠寻宝

description:
传说在漫无边际的沙漠中有一个古代城市的废墟，里面埋藏了大量的宝藏。听到这个消息的人一个又一个的前去寻宝，却没有发现一个回来的人。

探险家Jack是冒险者队伍中的后起之秀，它加入冒险者队伍的时间虽然不长，却屡屡依靠自己过人的智慧使自己和队友们脱离了险境。“明知山有虎，偏向虎山行”。 在Jack探险队的宗旨的指引下，Jack和他的队友们踏上了沙漠寻宝的旅程。

“我发现沙漠废墟了。”在一名队员的叫喊声中，Jack隐约看到了一些古代城市的残垣断壁和一个通道。 “一定就是这里了。”Jack带领着大家进入了通道。

然而，不幸的事情发生了。就在Jack他们进入通道的同时，通道的入口“轰”的一声就关闭了。Jack和他的队友走到了通道的尽头，正前方是一个巨大的铁门。最令人奇怪的是，铁门竟然使用的是一个极度先进的带有键盘和显示器的电子密码锁，铁门旁还赫然写着开锁的方法：“想到得到我的宝藏的人们，到这里的路途很辛苦吧！不过这一切很快就会结束的，这个铁门就是你们的葬身之地。除非你们能够计算出我屏幕上程序的结果，并且通过键盘输入进去，这扇门就会打开，里面就是我所有的宝藏”

我们的Jack果然不负众望，他打开了他的行囊，拿出了一个类似保险箱的东西。“没见过吗？这是最新型的笔记本电脑，没有它，我再怎么天才也不可能打开这扇门的。”面对大家疑惑的目光，Jack打开了笔记本电脑的开关。

“这个宝藏主人的程序十分的奇怪，我虽然没见过，但根据我的猜测，它的结构应该是这样的：

程序共包含6种语句：start,end,loop,continue,write,以及?=\*形式的语句。

start是程序的开始标志，其对应了一个结束标志end。

loop后面空一格并紧跟了一个表达式\*，表达式\*的值N表示即将循环N次，对应的循环结束标志也是end。

continue表示程序跳转到当前循环对应的end语句，break表示程序将跳出当前的循环。

write后面空一格并紧跟了一个表达式\*，表示要输出表达式\*的值，也就是要输入到密码锁中的内容。

?=\*是赋值语句，?是变量的名字，\*计算出来的值是要给?的。

另外，值得庆幸的是，变量名只允许使用’a’..’z’这26个小写字母，表达式也只允许使用加减乘除四种运算和以及括号，参与运算的也只能是26个变量或者是整数（允许不止一位整数）。表达式不会超过80个字符。”

“希望Jack能很快将锁打开。”大家心里默念着。

给定程序对所有语句的执行次数的总和小于2000000次。

inputFormat: 输入文件为program.in，给出了宝藏主人的程序。其中任两条语句用若干个空格或回车符隔开。

outputFormat: 输出文件为program.out，是你要输入密码锁的内容。每次输出占一行。

samples:
start
     i=0
     j=0
     loop 100
          i=i+1
          j=j+i
          continue
          loop 10
               write j
          end
     end
     loop 100
          j=j+1
          break
          j=j+1
     end
     write j
end


title: [HNOI2002] Tinux系统

description:
在 dos 系统诞生以前，美国曾研究出一种类似的操作系统，名为 Tinux 系统。但由于硬件设施的制约，Tinux 系统有许多的缺点。下面就对 Tinux 系统作一个简单的介绍：

Tinux 系统是 Tiger 博士为美国军方研制开发的一种操作系统，该系统对文件的存储方式类似于 dos 系统，像一棵树一样，每一个叶子节点表示一个文件，每一个非叶子节点表示一个目录。其中定义 $i$ 级子目录表示从根目录开始访问，一直访问到该子目录（不包括该子目录）需要访问的目录的个数为 $i$ 的目录，所以根目录下的目录为一级子目录，其他的目录以此类推。但是在同一子目录下，受到硬件的制约 Tinux 系统最多只能够存储 $k$ 个文件或子目录，也就是说这棵树里面的每一个非叶子节点最多只有 $k$ 个子节点。这样就导致在文件数量较多的情况下，访问存储在该系统当中的文件 A，往往要先访问一系列的子目录，我们称这些子目录为文件 A 的上级目录。例如下面这一个例子：

![](https://cdn.luogu.com.cn/upload/image_hosting/11pz60gn.png)

当我们要访问文件 A4A2A1 时就必须先访问它的上级目录：一级子目录 A4 和二级子目录 A4A2。

Tinux 系统在存储文件时，给每一个子目录都分配了 $k$ 个指针，分别指向存放在该目录下的每一个文件和每一个目录，因此对文件的访问实质上就是对指针的访问。但是由于硬件原因，这 $k$ 个指针不尽相同，因此访问它们的时间也不同，访问第 $i$ 个指针所耗费的时间为 $P_i$。但是对于两个不同的子目录（不管它们各自属于哪一级目录）而言它们各自所拥有的 $k$ 个指针是相同的。

Tinux 系统最大的缺点是访问一个目录时，必须把该目录下所有的文件读入到内存当中来，这些文件包括在其各级子目录当中的文件，例如上面那一个例子，访问 A4 那一个目录，就必须把 A4A1，A4A2A1，A4A2A2，A4A3 这四个文件都读入到内存当中来，访问一个目录所需要的时间为 $P_i \times x$（$x$ 表示该目录及其各级子目录下文件的个数，$P_i$ 表示指向该目录的指针的访问时间）。因此根据上面介绍的访问方法，单独访问一个文件所需要的总时间为访问其所有上级目录（不包括根目录）所需要的时间与访问指向该文件的指针所需要的时间的和，例如上面那一个例子，访问文件 A4A2A1 需要的时间 = 访问目录 A4 的时间 + 访问目录 A4A2 的时间 + 访问指向文件 A4A2A1 的指针需要的时间。

现在，tiger 博士准备将 $n$ 个文件存储到一个空的 Tinux 系统当中，希望你帮助他设计一个程序找到一种最优的存储方法，使得单独访问这 $n$ 个文件所需要的时间总和最小。

inputFormat: 文件的第一行为两个正整数 $n, k$，接下来的 $k$ 行每行有一个正整数 $P_i$。

outputFormat: 输出仅一个正整数，表示在最优存储方案下，单独访问这 $n$ 个文件所需要的时间总和（结果小于 $2^{31}$）。

hint:
![](https://cdn.luogu.com.cn/upload/pic/1296.png)

**【数据范围】**

$1 \le n \le 1000$，$2 \le k \le 150$，$1 \le P_i \le 150$。


title: [HNOI2002] 跳蚤

description:
Z 城市居住着很多只跳蚤。在 Z 城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有 $N+1$ 个自然数。其中最后一个是 $M$，而前 $N$ 个数都不超过 $M$，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数 $S$，然后向左，或向右跳 $S$ 个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。

比如当 $N=2,M=18$ 时，持有卡片 $(10, 15, 18)$ 的跳蚤，就可以完成任务：他可以先向左跳 $10$ 个单位长度，然后再连向左跳 $3$ 次，每次 $15$ 个单位长度，最后再向右连跳 $3$ 次，每次 $18$ 个单位长度。而持有卡片 $(12, 15, 18)$ 的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。

当确定 $N$ 和 $M$ 后，显然一共有 $M^ N$ 张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。

inputFormat: 输入文件有且仅有一行，包括用空格分开的两个整数 $N$ 和 $M$。

outputFormat:
输出文件有且仅有一行，即可以完成任务的卡片数。

$1\le N\le M\le 10^8$，且$M^N\le 10^{16}$。


title: [HNOI2002] 填数游戏

description:
某商店最近开展了一个答题有奖的促销活动，公司经理将若干道有一定难度的问题贴到了商场的宣传栏内，如果你能够做出其中一道的话，你就能够获得优惠购买商品的权利。一段日子以后，大多数题目都被消费者们找出了答案，可是惟独有一道题目难倒了所有的人，这道题目是这样描述的：

将不同的完全平方数填满 $n \times m$ 的矩形方格表中的每一个小方格，使得每行、每列的和也是完全平方数（这个和必须小于 ${10}^{17}$）。希望你找到一种合理的方案。

Tiger 希望自己能够获得优惠购物的权利，于是他找到了准备参加 NOI2002 的你，希望你能够帮他设计一个程序找到一种合理的方案。

inputFormat: 输入文件中仅有一行，为两个正整数 $n, m$（$2 \le n, m \le 15$）。

outputFormat: 如果有解的话，输出 $n$ 行，每行有 $m$ 个数，表示一种合理的填数方案，无解时输出 `No answer`。


title: [HNOI2002] 公交车路线

description:
在长沙城新建的环城公路上一共有 $8$ 个公交站，分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站 A 到公交站 D，你就至少需要换 $3$ 次车。

 ![](https://cdn.luogu.com.cn/upload/pic/1297.png)

Tiger 的方向感极其糟糕，我们知道从公交站 A 到公交 E 只需要换 $4$ 次车就可以到达，可是 tiger 却总共换了 $n$ 次车，注意 tiger 一旦到达公交站 E，他不会愚蠢到再去换车。现在希望你计算一下 tiger 有多少种可能的乘车方案。

inputFormat: 仅有一个正整数 $n$，表示 tiger 从公交车站 A 到公交车站 E 共换了 $n$ 次车。

outputFormat: 输出一个正整数表示方案数，由于方案数很大，请输出方案数除以 $1000$ 后的余数。

hint:
8 条路线分别是：

(A→B→C→D→C→D→E)，(A→B→C→B→C→D→E)，

(A→B→A→B→C→D→E)，(A→H→A→B→C→D→E)，

(A→H→G→F→G→F→E)，(A→H→G→H→G→F→E)，

(A→H→A→H→G→F→E)，(A→B→A→H→G→F→E)。

#### 数据范围

$4\le n\le10^7$。


title: [HNOI2002] 营业额统计

description:
Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

我们定义，一天的最小波动值 = $\min\{|\text{该天以前某一天的营业额}-\text{该天营业额}|\}$。

特别地，第一天的最小波动值为第一天的营业额。

inputFormat: 第一行为正整数 $n$（$n \leq 32767$） ，表示该公司从成立一直到现在的天数，接下来的 $n$ 行每行有一个整数 $a_i$（$|a_i| \leq 10^6$) ，表示第 $i$ 天公司的营业额，可能存在负数。

outputFormat: 输出一个正整数，即每一天最小波动值的和，保证结果小于 $2^{31}$。


title: [HNOI2002] Kathy函数

description:
Tiger 非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向 Tiger 介绍了 Kathy 函数，Kathy 函数是这样定义的：

$$
\left\{
\begin{aligned}
&f(1)=1\\
&f(3)=3\\
&f(2n)=f(n)\\
&f(4n+1)=2f(2n+1)-f(n)\\
&f(4n+3)=3f(2n+1)-2f(n)
\end{aligned}
\right.
$$

Tiger 对 Kathy 函数产生了浓厚的兴趣，他通过研究发现有很多的数 $n$ 都满足 $f(n)=n$。

对于一个给定的数 $m$，他希望你求出所有的满足 $f(n)=n$ 的正整数 $n$ 的个数，其中 $n\leq m$。

inputFormat: 输入只有一行一个整数，表示 $m$。

outputFormat: 输出一行一个整数，表示 $n$。

hint:
#### 数据规模与约定

对于全部的测试点，保证 $1 \leq m \leq 10^{100}$。


title: [HNOI2002] 彩票

description:
某地发行一套彩票。彩票上写有 $1$ 到 $M$ 这 $M$ 个自然数。彩民可以在这 $M$ 个数中任意选取 $N$ 个不同的数打圈。每个彩民只能买一张彩票，不同的彩民的彩票上的选择不同。

每次抽奖将抽出两个自然数 $X$ 和 $Y$。如果某人拿到的彩票上，所选 $N$ 个自然数的倒数和，恰好等于 $\dfrac{X}{Y}$，则他将获得一个纪念品。

已知抽奖结果 $X$ 和 $Y$。现在的问题是，必须准备多少纪念品，才能保证支付所有获奖者的奖品。

inputFormat: 输入文件有且仅有一行，就是用空格分开的四个整数 $N$，$M$，$X$，$Y$。

outputFormat: 输出文件有且仅有一行，即所需准备的纪念品数量。

hint:
$1 \leq X, Y \leq 100$，$1 \leq N \leq 10$，$1 \leq M \leq 50$。

输入数据保证输出结果不超过 $10^5$。


title: [USACO14FEB] Auto-complete S

description:
Bessie the cow has a new cell phone and enjoys sending text messages, although she keeps making spelling errors since she has trouble typing on such a small screen with her large hooves.  Farmer John has agreed to help her by writing an auto-completion app that takes a partial word and suggests how to complete it.

The auto-completion app has access to a dictionary of W words, each consisting of lowercase letters in the range a..z, where the total number of letters among all words is at most 1,000,000.  The app is given as input a list of N partial words (1 <= N <= 1000), each containing at most 1000 lowercase letters.  Along with each partial word i, an integer K\_i is also provided, such that the app must find the (K\_i)th word in alphabetical order that has partial word i as a prefix.  That is, if one ordered all of the valid completions of the ith partial word, the app should output the completion that is (K\_i)th in this sequence.

inputFormat:
\* Line 1: Two integers: W and N.

\* Lines 2..W+1: Line i+1: The ith word in the dictionary.

\* Lines W+2..W+N+1: Line W+i+1: A single integer K\_i followed by a    partial word.

outputFormat:
\* Lines 1..N: Line i should contain the index within the dictionary

(an integer in the range 1..W) of the (K\_i)th completion (in

alphabetical order) of the ith partial word, or -1 if there

are less than K\_i completions.

translation:
### 题目描述

有 $w$ 个由小写字符构成的字典和 $n$ 个询问。每个询问由一个字符串 $s$ 和一个整数 $k$ 构成，求在字典序排序下字典内由 $s$ 为前缀的第 $k$ 字符串在输入字典的位置。若不存在，则输出 $-1$

### 输入格式

第 $1$ 行是两个整数 $w$ 和 $n$

第 $2$ 行到第 $w$ + $1$ 行为字典中的第 $i$ - $1$ 个，每行由字符串构成（$i$ 指输入的第 $i$ 行）

第 $w$ + $2$ 行到第 $w$ + $n$ + $1$ 行由一个整数 $k$ 和一个字符串 $s$ 构成

### 输出格式

第 $1$ 行到第 $n$ 行是对于每个询问的结果，由一个整数构成

### 说明/提示
对于 $100\%$ 的数据，$w \le 30000$，$1\le n \le 1000$，字典内每个字符串的长度均小于等于 $1000$，且字典的单词总长不超过 $10 ^ 6$。

样例解释：

对于第 $1$ 个询问，含义为在字典中找到以 ```a``` 为前缀且按字典序排序后第 $4$ 个字符串，而字典中以 ```a``` 为前缀且按字典序排序后为 $\{$  ```aa```，```aaa```，```aab```，```ab```，```abc```，```ac``` $\}$，第 $4$ 个是 ```ab```，其在输入中为第 $3$ 个，故输出为 $3$

同理，对于第 $2$ 个和第 $3$ 个询问是在字典中找到以 ```da``` 为前缀且按字典序排序后的第 $2$ 和第 $4$ 个字符串。而以 ```da``` 为前缀的字符串按字典序排序后为 $\{$```daa```，```dab```，```dadba``` $\}$，故第 $2$ 个为 ```dab``` ，其在输入中为第 $1$ 个，故第 $2$ 个输出为 $1$，而该序列中没有第 $4$ 个，故第 $3$ 个询问无解，输出 $-1$

来源：USACO 2014 Feburary Contest Silver

翻译：@[zymooll](/user/289296)

samples:
10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

hint:
OUTPUT DETAILS:

The completions of a are {aa,aaa,aab,ab,abc,ac}. The 4th is ab, which

is listed on line 3 of the dictionary.  The completions of da are

{daa,dab,dadba}. The 2nd is dab, listed on line 1 of the dictionary.

There is no 4th completion of da.

Source: USACO 2014 Feburary Contest, Silver


title: [CERC2016] 机棚障碍 Hangar Hurdles

description:
你正在评估一些关于一个巨型飞机仓库的建设计划。飞机仓库的地面可以表示为 $n$ 行 $n$ 列的网格图，其中每个格子要么是空的，要么有障碍物。行从上到下依次被编号为 $1$ 到 $n$，列从左到右依次被编号为 $1$ 到 $n$。

存放飞机零件的大型集装箱能在飞机仓库的地面上自由移动是很重要的。我们可以将每个集装箱看作一个以某个格子为中心的边平行于坐标轴的正方形。对于一个奇数 $k$，一个尺寸为 $k$ 的集装箱是一个包含 $k$ 行 $k$ 列的正方形。一个集装箱的坐标为其中心格子的坐标。集装箱可以向上下左右移动，但不能碰到障碍物，且不能移出仓库的边界。

给定 $q$ 对格子 $A_k$ 和 $B_k$，对于每对格子，请找到能从 $A_k$ 移动到 $B_k$ 的集装箱的最大尺寸，注意这个尺寸也要是一个奇数。

inputFormat:
第一行包含一个正整数 $n$（$2\le n \le 1000$），表示仓库的尺寸。

接下来 $n$ 行，每行 $n$ 个字符，描述整个仓库，其中 `.` 表示空格子，`#` 表示障碍物。

接下来一行包含一个正整数 $q$（$1\le q\le 300000$），表示询问的个数。

接下来 $q$ 行，每行四个正整数 $A_x,A_y,B_x,B_y$（$1\le A_x,A_y,B_x,B_y\le n$），分别表示 $A$ 和 $B$ 的坐标。

输入数据保证 $A$ 和 $B$ 是不同的空格子。

outputFormat: 输出 $q$ 行，每行一个整数，对于每个询问输出最大尺寸，如果不存在解，那么输出 $0$。


title: [NOIP2014 普及组] 螺旋矩阵

background: NOIP2014 普及组 T3

description:
一个 $n$ 行 $ n$ 列的螺旋矩阵可由如下方法生成：

从矩阵的左上角（第 $1$ 行第 $1$ 列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入 $1, 2, 3, \dots, n^2$，便构成了一个螺旋矩阵。

下图是一个 $n = 4$ 时的螺旋矩阵。

$$\begin{pmatrix}
 1 &    2  &   3   &  4 \\
12 &   13  &  14   &  5 \\
11 &   16  &  15   &  6 \\
10 &    9  &   8   &  7 \\
\end{pmatrix}$$

现给出矩阵大小 $n$ 以及 $i$ 和 $j$，请你求出该矩阵中第 $i$ 行第 $j$ 列的数是多少。

inputFormat: 共一行，包含三个整数 $n$, $i$, $j$，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。

outputFormat: 一个整数，表示相应矩阵中第 $i$ 行第 $j$ 列的数。

hint:
【数据说明】

对于 $50\%$ 的数据，$1 \leqslant n \leqslant 100$;

对于 $100\%$ 的数据，$1 \leqslant n \leqslant 30,000,1 \leqslant i \leqslant n,1 \leqslant j \leqslant n$。


title: 统计方形（数据加强版）

background: 1997年普及组第一题

description: 有一个 $n \times m$ 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

inputFormat: 一行，两个正整数 $n,m$（$n \leq 5000,m \leq 5000$）。

outputFormat: 一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。


title: 二面体群

description:
考虑在一个单位圆周上的 $n$ 个点，$n$ 个点的标号为 $K=0,1,\ldots,n-1$。初始的时候 $K$ 相对于 X 轴的角度为 $\dfrac{360 \times k}{n}$ 度，这里的角度是相对于 X 轴的逆时针角度。我们将在这组点上运行 2 种不同类型的操作：

1. 顺时针旋转 $\dfrac{360}{n}$度
2. 相对于 X 轴的映射

对于给定的操作序列，如果结果相同，我们只对最短的操作序列感兴趣。结果相同是指对于不同的操作序列，最后的操作结果中每一个单一点的位置都是一样的。

操作序列以字符串的形式给出，该字符串中只含有字母 `r` 和 `m`。`r` 代表顺时针旋转，`m` 代表单独映射（到右边并且对称）。字符串中如果有多个字母连续出现要简写成 `<字母><数字>` 的形式，为了方便起见，字母如果单独出现也写成这种形式。如 `rrmrrrrrrrrrrrr` 可以写成 `r2 m1 r12`，每个操作序列一行。

inputFormat:
输入共两行。

第一行一个数 $N$，表示圆周上点的个数。

第二行为按上面的方式缩写的操作序列，所有的数字都是正整数，并且小于$10^8$ 。在输入文件中没有空行，并且每一行的字符个数都小于 $10^5$。

outputFormat: 输出最短操作序列。若无需操作则什么都不输出。


title: [SHOI2002] 取石子游戏|【模板】威佐夫博弈

description: 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法：一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

inputFormat:
输入共一行。

第一行共两个数 $a, b$，表示石子的初始情况。

outputFormat:
输出共一行。

第一行为一个数字 $1,0$ 或 $-1$，如果最后你是胜利者则为 $1$；若失败则为 $0$；若结果无法确定则为 $-1$。


title: 质量检测

description:
为了检测生产流水线上总共 $N$ 件产品的质量，我们首先给每一件产品打一个分数 $A$ 表示其品质，然后统计前 $M$ 件产品中质量最差的产品的分值 $Q[m] = min\{A_1, A_2, ... A_m\}$，以及第 2 至第 $M + 1$ 件的 $Q[m + 1], Q[m + 2] $... 最后统计第 $N - M + 1$ 至第 $N$ 件的 $Q[n]$。根据 $Q$ 再做进一步评估。

请你尽快求出 $Q$ 序列。

inputFormat:
输入共两行。

第一行共两个数 $N$、$M$，由空格隔开。含义如前述。

第二行共 $N$ 个数，表示 $N$ 件产品的质量。

outputFormat:
输出共 $N - M + 1$ 行。

第 1 至 $N - M + 1$ 行每行一个数，第 $i$ 行的数 $Q[i + M - 1]$。含义如前述。


title: [CERC2016] 不可见的整数 Invisible Integers

description:
《隐形的整数》是一个简单的猜数游戏。在这个游戏中，给定n个提示，玩家将尝试去猜一个仅包含自然数1到9的数字序列，满足所有n个提示。每个提示是一个包含若干互不相同的1到9之间的整数序列，它是这样生成的：

1.随机选择一个序列中的位置作为起点。

2.随机选择任意一个方向，左或者右。

3.从起点开始沿着选定的方向走，遍历完这个方向的每个数字，将每个数字第一次出现的顺序记录下来。

请找到长度最短的满足所有n个提示的序列。

inputFormat:
第一行包含一个正整数n(1<=n<=10)，表示提示的个数。

接下来n行，每行若干个互不相同的1到9之间的整数，依次表示每个提示，每一行以0为终止。

outputFormat: 输出一行一个整数，即最短长度，若无解则输出-1。

hint:
一个可行的序列是(1,2,1,4,1,3,4)。

对于提示序列(1,2)，可以选择位置3，然后往左走。

对于提示序列(3,4)，可以选择位置6，然后往右走。

对于提示序列(1,4,3)，可以选择位置3，然后往右走。

对于提示序列(3,1,4,2)，可以选择位置6，然后往左走。

对于提示序列(1,2,4,3)，可以选择位置1，然后往右走。


title: [NOI2005] 瑰丽华尔兹

background:
你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？

众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼・布德曼・T.D.・柠檬・1900，朋友们都叫他 1900。

1900 在 20 世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上。很不幸，他刚出生就被抛弃，成了孤儿。1900 孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的世界。也许是对他命运的补偿，上帝派可爱的小天使艾米丽照顾他。可能是天使的点化，1900 拥有不可思议的钢琴天赋：从未有人教，从没看过乐谱，但他却能凭着自己的感觉弹出最沁人心脾的旋律。当 1900 的音乐获得邮轮上所有人的欢迎时，他才 8 岁，而此时，他已经乘着海轮往返欧美大陆 50 余次了。

虽说是钢琴奇才，但 1900 还是个孩子，他有着和一般男孩一样的好奇和调皮，只不过更多一层浪漫的色彩罢了：这是一个风雨交加的夜晚，海风卷起层层巨浪拍打着弗吉尼亚号，邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手迈克斯・托尼晕船了，1900 招呼托尼和他一起坐到舞厅里的钢琴上，然后松开了固定钢琴的闸，于是，钢琴随着海轮的倾斜滑动起来。准确的说，我们的主角 1900…

description:
不妨认为舞厅是一个 $N$ 行 $M$ 列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。

艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长，这样 1900 会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。

inputFormat:
输入文件的第一行包含 $5$ 个数 $N$, $M$, $x$, $y$ 和 $K$。$N$ 和 $M$ 描述舞厅的大小，$x$ 和 $y$ 为钢琴的初始位置；我们对船体倾斜情况是按时间的区间来描述的，且从 $1$ 开始计算时间，比如 “在 $[1, 3]$ 时间里向东倾斜，$[4, 5]$ 时间里向北倾斜”，因此这里的 $K$ 表示区间的数目。

以下 $N$ 行，每行 $M$ 个字符，描述舞厅里的家具。第 $i$ 行第 $j$ 列的字符若为 `.`，则表示该位置是空地；若为 `x`，则表示有家具。

以下 $K$ 行，顺序描述 $K$ 个时间区间，格式为：$s_i t_i d_i (1 \leq i \leq K)$。表示在时间区间 $[s_i, t_i]$ 内，船体都是向 $d_i$ 方向倾斜的。$d_i$ 为 $1$, $2$, $3$, $4$ 中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。输入保证区间是连续的，即

$s_1 = 1$

$s_i = t_{i-1} + 1 (1 < i \leq K)$

$t_K = T$

outputFormat: 输出文件仅有 $1$ 行，包含一个整数，表示钢琴滑行的最长距离 (即格子数)。

hint:
钢琴的滑行路线：

 ![](https://cdn.luogu.com.cn/upload/pic/1307.png)

钢琴在“×”位置上时天使使用一次魔法，因此滑动总长度为 $6$。

【数据范围】

$50\%$ 的数据中，$1\leq N, M\leq 200，T\leq 200$；

$100\%$ 的数据中，$1\leq N$, $M \leq 200$，$K \leq 200$，$T\leq 40000$。


title: [USACO14JAN] Recording the Moolympics S

description:
Being a fan of all cold-weather sports (especially those involving cows),Farmer John wants to record as much of the upcoming winter Moolympics as possible.

The television schedule for the Moolympics consists of N different programs(1 <= N <= 150), each with a designated starting time and ending time.  FJ has a dual-tuner recorder that can record two programs simultaneously.

Please help him determine the maximum number of programs he can record in total.

农民约翰热衷于所有寒冷天气的运动（尤其是涉及到牛的运动）， 农民约翰想录下尽可能多的电视节目。 moolympics 的节目时间表有 $N$ 个不同的节目 （$1\le N\le 150$），每个节目给定开始时间和结束时间。FJ 有一个双调谐器录音机，可以同时录制两个节目。 请帮助他确定他能录制的节目的最大数量。

inputFormat:
\* Line 1: The integer N.

\* Lines 2..1+N: Each line contains the start and end time of a single program (integers in the range 0..1,000,000,000).

- 第 $1$ 行：整数 $N$。
- 第 $2$ 到第 $N+1$ 行：每行包含单个节目的开始和结束时间（范围为 $0…1000000000$ 的整数）。

outputFormat:
\* Line 1: The maximum number of programs FJ can record.

仅一行，FJ可以记录的最大节目数量。

hint:
INPUT DETAILS:

The Moolympics broadcast consists of 6 programs.  The first runs from time 0 to time 3, and so on.

OUTPUT DETAILS:

FJ can record at most 4 programs.  For example, he can record programs 1 and 3 back-to-back on the first tuner, and programs 2 and 4 on the second tuner.

Source: USACO 2014 January Contest, Silver


title: [CQOI2007] 余数求和

description:
给出正整数 $n$ 和 $k$，请计算

$$G(n, k) = \sum_{i = 1}^n k \bmod i$$

其中 $k\bmod i$ 表示 $k$ 除以 $i$ 的余数。

inputFormat: 输入只有一行两个整数，分别表示 $n$ 和 $k$。

outputFormat: 输出一行一个整数表示答案。


title: [清华集训2012] 模积和

background: 数学题，无背景。

description:
求

$$\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j$$

mod 19940417 的值

inputFormat: 输入只有一行两个整数 $n$，$m$。

hint:
#### 数据规模与约定

- 对于 $10\%$ 的数据，保证 $n,m \leq 10^3$。
- 对于 $30\%$ 的数据，保证 $n,m \leq 10^6$。
- 另有 $30\%$ 的数据，保证 $n \leq 100$。
- 对于 $100\%$ 的数据，保证 $1 \leq n,m \leq 10^9$。


title: 一中校运会之百米跑

background:
在一大堆秀恩爱的 \*\* 之中，来不及秀恩爱的苏大学神踏着坚定（？）的步伐走向了 $100$ 米跑的起点。这时苏大学神发现，百米赛跑的参赛同学实在是太多了，连体育老师也忙不过来。这时体育老师发现了身为体育委员的苏大学神，便来找他帮忙。

可是苏大学神需要热身，不然跑到一半就会抽（筋）、于是他就找到了你。。。如果你帮助体育老师解决了问题，老师就会给你 $5$ 个积分。

description:
假设一共有 $N$（$2\leq N\leq 2\times 10^4$）个参赛选手。（尼玛全校学生都没这么多吧）

老师会告诉你这 $N$ 个选手的名字。

接着会告诉你 $M$（$1\leq M\leq 10^6$）句话，即告诉你学生 A 与学生 B 在同一个组里。

如果学生 A 与学生 B 在同一组里，学生 B 与学生 C 也在同一组里，就说明学生 A 与学生 C 在同一组。

然后老师会问你 $K$（$1\leq K\leq 10^6$）句话，即学生 X 和学生 Y 是否在同一组里。

若是则输出 `Yes.`，否则输出 `No.`。

inputFormat:
第一行输入 $N$ 和 $M$。

接下来 $N$ 行输入每一个同学的名字。

再往下 $M$ 行每行输入两个名字，且保证这两个名字都在上面的 $N$ 行中出现过，表示这两个参赛选手在同一个组里。

再来输入 $K$。

接下来输入 $K$ 个体育老师的询问。

outputFormat: 对于每一个体育老师的询问，输出 `Yes.` 或 `No.`。

samples:
10 6
Jack
Mike
ASDA
Michel
brabrabra
HeHe
HeHE
papapa
HeY
Obama
Jack Obama
HeHe HeHE
brabrabra HeHe
Obama ASDA
papapa Obama
Obama HeHE
3
Mike Obama
HeHE Jack
papapa brabrabra


title: [NOIP2014 普及组] 子矩阵

background: NOIP2014 普及组 T4

description:
给出如下定义：

1. 子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。

    例如，下面图中选取第 $2,4$ 行和第 $2,4,5$ 列交叉位置的元素得到一个 $2 \times 3$ 的子矩阵如下所示。

|$9$|$\color{#6a5acd}3$|$3$|$\color{#6a5acd}3$|$\color{#6a5acd}9$|
|:-|:-|:-|:-|:-|
|$\color{#6a5acd}9$|$\color{blue}4$|$\color{#6a5acd}8$|$\color{blue}7$|$\color{blue}4$|
|$1$|$\color{#6a5acd}7$|$4$|$\color{#6a5acd}6$|$\color{#6a5acd}6$|
|$\color{#6a5acd}6$|$\color{blue}8$|$\color{#6a5acd}5$|$\color{blue}6$|$\color{blue}9$|
|$7$|$\color{#6a5acd}4$|$5$|$\color{#6a5acd}6$|$\color{#6a5acd}1$|

此矩阵的其中一个 $2\times3$ 的子矩阵是：

|$4$|$7$|$4$|
|:-|:-|:-|
|$8$|$6$|$9$|

2. 相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。

3. 矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。

本题任务：给定一个 $n$ 行 $m$ 列的正整数矩阵，请你从这个矩阵中选出一个 $r$ 行 $c$ 列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。

inputFormat:
第一行包含用空格隔开的四个整数 $n,m,r,c$，意义如问题描述中所述，每两个整数之间用一个空格隔开。

接下来的 $n$ 行，每行包含 $m$ 个用空格隔开的整数，用来表示问题描述中那个 $n$ 行 $m$ 列的矩阵。

outputFormat: 一个整数，表示满足题目描述的子矩阵的最小分值。


title: 语文成绩

background: 语文考试结束了，成绩还是一如既往地有问题。

description: 语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

inputFormat:
第一行有两个整数 $n$，$p$，代表学生数与增加分数的次数。

第二行有 $n$ 个数，$a_1 \sim a_n$，代表各个学生的初始成绩。

接下来 $p$ 行，每行有三个数，$x$，$y$，$z$，代表给第 $x$ 个到第 $y$ 个学生每人增加 $z$ 分。

outputFormat: 输出仅一行，代表更改分数后，全班的最低分。


title: [HNOI2004] FTP服务器

background: File Transfer Protocol，文件传输协议，简称 FTP。人们可以通过 FTP 实现资源共享。一般的情况下用户访问一个 FTP 服务器是通过类似资源管理器的形式对该服务器上的资源进行浏览，并且不同权限的用户可以实现下载文件/文件夹，上传文件/文件夹。

description:
一个FTP服务器的所有资源都以文件的形式按树形结构存储在不同的文件夹里，最低一级的是根目录（即根文件夹），根目录里有若干个文件和文件夹，每一个文件夹里都可以拥有 $0$ 个或多个文件及文件夹，同一文件夹里不存在名称相同的文件和文件夹。

一个用户包含三个属性：

- $\text{userType}$：用户类型；
- $\text{userState}$：用户状态（用户正在执行的操作）；
- $\text{userPosition}$：用户当前所处的位置（即用户正在浏览的文件夹）。

用户分 $3$ 种类型：上传用户 $\text{uploadUser}$，下载用户 $\text{downloadUser}$，匿名用户 $\text{guest}$。

操作分 $3$ 种类型：浏览 $\text{scan}$，下载 $\text{download}$，上传 $\text{upload}$。

用户的权限是指用户允许进行的操作。不同类型的用户的权限是不同的。

任何一个用户是不能进行其没有权限的操作的，例如：一个匿名用户想要下载一个文件或者文件夹是不允许的。

一个文件/文件夹包含三个属性：

- $\text{fileName/folderName}$：文件名（不包含空格和回车）；
- $\text{fileSize/folderSize}$：文件大小
（单位 $\text{byte}$，$0 <\mathrm{filesize}< 10^5$，$0<\mathrm{folderSize}< 10^8$，文件夹的大小是它里面所包含的所有文件大小的总和）；
- $\text{fileState/folderState}$：当前状态，当前状态有两种：
  - 一种为正常 $\text{normal}$（文件/文件夹为正常状态时，允许用户对其进行操作）；
  - 另一种为上传未完成 $\text{uploading}$（处在此种状态时，用户只能够对其进行浏览操作，如果一个文件夹中有一个或多个文件处于 $\text{uploading}$ 状态，那么这个文件夹也处于 $\text{uploading}$ 状态）。

一个 FTP 服务器除了它所拥有的文件资源外，还有如下属性：

1. 访问用户的最大数量（包括所有不同类型的用户） $\text{maxUserNumber}<100$。如果当前访问用户数量已经达到最大值的话，其他新的用户对服务器的访问将是失败的。
2. 服务器的最大流量 $\text{maxServerFlux}<10^7$。
3. 单个用户允许的最大下载/上传流量 $\text{maxUserFlux}$。

FTP 服务器运行的最小时间单位为秒。

每一个用户在同一时刻只能进行一种操作。用户下载和上传文件/文件夹是需要一定时间的，而这个时间决定于用户流量 $\text{userFlux}$，单位为 $\text{byte/second}$，注意如果某一时刻文件/文件夹仍须上传/下载的大小（$>0$）小于 $\text{userFlux}$ 的话，上传/下载时间仍将按照一秒钟看待。

而 $\text{userFlux}$ 的值是如何确定的呢？

 $$\mathrm{userFlux} = \min(\mathrm{presentMaxUserFlux},\mathrm{maxUserFlux})$$

其中，$\text{presentMaxUserFlux}$ 为当前服务器的单个用户最大流量：

$$\mathrm{presentMaxUserFlux} = \lfloor \mathrm{maxServerFlux} / \mathrm{userTotal}\rfloor$$

（$\text{userTotal}$ 表示该时刻的正在进行上传和下载操作的用户数量）

一个用户通过一系列命令实现其在 FTP 服务器上的相关操作。下面介绍这些命令：

### $\verb!connect!$ 命令

- 格式：$\verb![name] + 空格 + connect + 空格 + 参数A!$。
- 例：$\verb!tsinghua connect 1!$。
- 表示在名叫 $\verb!name!$ 的用户请求以 $\verb!A!$ 身份连接到服务器上。如果当前的最大使用用户还没达到 $\text{maxUserNumber}$，并且该用户未连接到服务器，则连接成功，服务器反馈回一个相关信息 $\verb!success!$。否则反馈信息为 $\verb!unsuccess!$。一旦连接成功，用户其所处的位置 $\text{userPosition}$ 为服务器的根目录。$A=1$ 表示上传用户，$A=2$ 下载表示用户，$A=3$ 表示匿名用户。

### $\verb!quit!$ 命令

- 格式：$\verb![name] + 空格 + quit!$。
- 例：$\verb!tsinghua quit!$。
- 表示名叫 $\verb!name!$ 的用户断开与服务器的连接。如果用户未连接反馈 $\verb!unsuccess!$，否则反馈 $\verb!success!$。（注意用户在任何状态下都可以断开与服务器的连接）。

### $\verb!cd!$ 命令

- 格式：$\verb![name] + 空格 + cd + 空格 + [folderName/文件夹名称]!$。
- 例：$\verb!THU cd FD!$。
- 表示名叫 $\verb!name!$ 的用户希望从当前所处的文件夹进入该文件夹中的一个名叫 $\text{folderName}$ 的文件夹。如果名叫 $\text{folderName}$ 的文件夹存在并且处于 $\text{normal}$ 状态，则改变用户当前所处位置 $\text{userPosition}$，反馈相关信息 $\verb!success!$，如果该文件夹不存在或该用户没有成功连接，则反馈信息为 $\verb!unsuccess!$。

### $\verb!cd..!$ 命令

- 格式：$\verb![name] + 空格 + cd..!$。
- 例：$\verb!9# cd..!$。
- 表示名叫 $\verb!name!$ 的用户希望从当前所处的文件夹返回到他的上一级文件夹。如果用户处于根目录或者用户未连接，则命令执行失败返回 $\verb!unsuccess!$，否则返回 $\verb!success!$，并且改变用户所处位置 $\text{userPosition}$。

### $\verb!download!$ 命令

- 格式：$\verb![name] + 空格 + download + 空格 + [name1]!$。
- 例：$\verb!A download 1.txt!$。
- 表示名叫 $\verb!name!$ 的用户希望从当前所处文件夹下载名为 $\verb!name1!$ 的文件或者文件夹。如果用户未连接，用户没有下载权限，名为 $\verb!name1!$ 的文件/文件夹不存在，或者该文件/文件夹处于 $\text{uploading}$ 状态时，反馈信息 $\verb!unsuccess!$，否则返回 $\verb!success!$ 并且开始下载该文件/文件夹。（一旦一个下载命令开始执行，那么执行该命令的用户所下载的是下载命令执行的那一时刻的那一个文件/文件夹，也就是说如果一个用户正在下在某个文件夹，在下载过程中，有另外一用户在这个文件夹里面上传文件，那么原下载用户是不可能下载到这个新上传的文件的）。

### $\verb!upload!$ 命令

- 格式：$\verb![name] + 空格 + upload + 空格 + [name1] + 空格 + [size]!$。
- 例：$\verb!A upload B 1!$。
- 表示名叫 $\verb!name!$ 的用户希望在当前所处的文件夹上传一个名叫 $\verb!name1!$ 的大小为 $\text{size}$ 的文件/文件夹。注意：
  - 用户通过 $\verb!upload!$ 命令上传文件夹只能为空文件夹，当 $\text{size}=0$ 表示上传文件夹，size>0表示上传文件。
  - 如果当前目录已经存在了同名的文件/文件夹，用户未成功连接或者用户没有上传权限，反馈信息 $\verb!unsuccess!$，否则反馈 $\verb!success!$，并且开始上传文件/文件夹。（如果一个用户想要上传一个非空文件夹，是很容易通过一系列 $\verb!upload!$ 以及 $\verb!cd!$ 命令实现的）。

---

除上传文件和下载文件/文件夹命令需要耗时外，其他的命令都不需要执行时间。

你的任务是模拟一个 FTP 服务器在某一时间段内的运行过程。

inputFormat:
一开始你将从文件中获得 FTP 的服务器的初始信息。第一行为 $3$ 个正整数，分别表示 $\text{maxUserNumber},\text{maxServerFlux},\text{maxUserFlux}$。接下来的若干行描述 $\text{server}$ 里已有文件资源的存储情况。

第一行总是描述的根目录中的一个文件或者文件夹。

如果某一行描述的是一个文件或者文件夹那么该行的数据为 $\verb!name + 空格 + size!$，如果 $\text{size}=0$ 表示这是一个文件夹，否则表示一个大小为 $\text{size}$ 的文件。

如果某一行描述的是一个文件夹，那么接下来的若干行描述的都是这个文件夹里的内容，直到一个与之对应的减号为止。这些数据都是递归描述的。因为一开始就是描述整个根目录里的文件和文件夹，所以文件信息的最后一行也为减号。（参看输入示例）。

下面的每一行为 $\verb!time + 空格 + order!$ 的形式给出，例如 $\verb!4 ares connect 1!$ 表示：在服务器开启后 $4$ 秒钟，名叫 $\verb!ares!$ 的用户请求以 $\text{uploadUser}$ 的身份连接到服务器上来。

输入的最后一行为一个字符串 $\verb!down!$。

所有输入命令的时刻 $\text{time}$ 都以命令出现的先后递增，同一时刻的命令以输入中出现的先后顺序确定其执行顺序。

outputFormat: 请你将每一条命令的反馈信息输出。

samples:
5 200 200
unzip.exe 100
xxxx 50
bin 0
tpx.exe 200
turbo.exe 300
tpx.tp 400
temp 0
-
-
readme.txt 100
-
0 ares connect 2
0 ares download zip.exe
1 ares download bin
5 ares download xxxx
6 ares cd bin
6 ares connect 1
6 ares quit
7 ares connect 1
7 rosen connect 2
7 ares cd bin
8 ares upload A 300
9 rosen download bin
10 rosen download bin
down

samples:
success
unsuccess
success
unsuccess
success
unsuccess
success
success
success
success
success
unsuccess
success

hint: 来源：HNOI2004 经过修改。


title: 添加括号

background:
给定一个正整数序列a(1)，a(2)，...，a(n),(1<=n<=20)

不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。

例如:

给出序列是4，1，2，3。

第一种添括号方法:

((4+1)+(2+3))=((5)+(5))=(10)

有三个中间和是5，5，10，它们之和为:5+5+10=20

第二种添括号方法

 (4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)

中间和是3，6，10，它们之和为19。

description: 现在要添上n-1对括号，加法运算依括号顺序进行，得到n-1个中间和，求出使中间和之和最小的添括号方法。

inputFormat: 共两行。 第一行，为整数n。(1< =n< =20) 第二行，为a(1),a(2),...,a(n)这n个正整数，每个数字不超过100。

outputFormat: 输出3行。 第一行，为添加括号的方法。 第二行，为最终的中间和之和。 第三行，为n-1个中间和，按照从里到外，从左到右的顺序输出。

hint: 范围在题目上有说明。


title: 合并神犇

background: loidc 来到了 NOI 的赛场上，他在那里看到了好多神犇。

description:
神犇们现在正排成一排在刷题。每个神犇都有一个能力值 $p_i$。loidc 认为坐在附近的金牌爷能力参差不齐非常难受。于是 loidc 便想方设法对神犇们进行人道主义合并。

loidc 想把神犇的能力值排列成从左到右单调不减。他每次可以选择一个神犇，把他合并到两侧相邻的神犇上。合并后的新神犇能力值是以前两位犇的能力值之和。每次合并完成后，被合并的两个神犇就会消失。合并后的新神犇不能再分开（万一他俩有女朋友咋办）因此每次合并后神犇的总数会减 1。

loidc 想知道，想治好他的强迫症需要合并多少次。

inputFormat:
第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $p_i$。

outputFormat: 一行一个整数表示 loidc 需要合并的次数。


title: loidc，跑起来

background: loidc 在路上诱拐了一个幼女。（他不是哲学家么！？）

description:
现在他已经被 cony 追杀。loidc 逃到一个迷宫中，cony 也追到了这儿。迷宫由编号由 $1$ 到 $n$ 的方块组成。每两个不同的方块将被得知它们是否与另一个相邻。现在已知 loidc 和 cony 所处迷宫的位置。在迷宫中的人可以选择留在原地不动，还是移到相邻的方格中。

迷宫具有如下性质：

它不包括三角形，也就是没有任意三个不同的方块，它们两两相邻，

每一个人到达都能到达任意一个方块。

一次追杀由许多回合组成。在一个回合内，每一个人移一步。每一个回合由 loidc 开始。如果 loidc 与 cony 在同一个方格中相遇，那么我们就可能永远见不到 loidc 了。

loidc 非常害怕，他请求你告诉他是否会被 cony 抓住，多少回合 cony 赶上他。(假设两个人都足够聪明)

inputFormat: 第一行有 $4$ 个整数 $n,m,a,b$，它们用单个空格分隔，（$2 \leq n \leq 3000, n-1 \leq m \leq 15000,1 \leq a,b \leq n,a < b$）。它们分别表示迷宫中的方块数目，相邻的一对方块（双向）数目，相邻两个方格中有且仅有一条边，loidc，cony所处的位置。下面 $m$ 行，一行包含两个用一个空格分开的整数，表示每一对相邻的方块编号。

outputFormat: 一个单词 `NO`，如果 cony 不能赶上 loidc；或者一个整数，如果 cony 能赶上 loidc 的最少游戏轮数。


title: 就是干！

background:
loidc 有着特别的作死技巧，但是有一天他特别的技巧失效了。

Mr.Cao 发现了他在与其他哲学家摔跤，于是 Mr.Cao 带着浩浩荡荡的老师大军来讨伐 Loidc。

description:
眼看着老师大军浩浩荡荡的向机房前进。LOI 的同学们决定动用自己的力量来保卫他们的好朋友 loidc。现在每个人都要挑选自己的武器——两根木棍。一根用做远距离投掷，另一根用做近距离搏斗。每个人都想挑到最好的，但这是不可能的。但是为了让多数人满意，也为了减少大家的矛盾。cony 设计了一个矛盾指数，这个指数就是每个人的不舒服指数和，不舒服指数就 $(L1-L2)^2$，其中 $L1,L2$ 分别是两根木棍的长度。

cony 决定让矛盾指数最少，于是他来向你寻求帮助，希望你能告诉他矛盾指数至少有多少。

inputFormat:
第一行两个数 $m,n$。

表示有 $n$ 个人，$m$ 个木棍。

接下来 $m$ 个数表示每个木棍（肯定有解）。

outputFormat: 一个数，最少的矛盾指数。


title: 情书

background: 一封好的情书需要撰写人全身心的投入。CYY同学看上了可爱的c**想对她表白，但却不知道自己写的情书是否能感动她，现在他带着情书请你来帮助他。

description:
为了帮助CYY，我们定义一个量化情书好坏的标准感动值。判断感动值的方法如下:

1. 在情书的一句话中若含有给定词汇列表中的特定单词，则感动值加1，但每一单词在同一句话中出现多次感动值不叠加，不同单词不受影响。保证输入的单词不重复。
2. 每句话以英文句号定界。
3. 全文不区分大小写。

inputFormat:
第一行包含一个数字n，表示导致感动值提升的词汇列表中单词的数量，随后n行是给定单词，每行一个。保证单词只包含英文字母。

最后一行为情书正文，保证只包含以下几种字符: 英文字母、数字、空格、英文逗号、英文句号。

outputFormat: 一个数字g，表示情书带来的感动值。

hint: 对于所有的数据，保证1 ≤ n ≤ 100，每个单词不超过50字符，全文不超过1000字符。


title: 命运的彼方

background: kkksc03 与 lzn 踏上了一次寻宝之旅，经过 kkksc03 与 lzn 的不懈努力，终于解开了所有的谜题，依靠御风飞翔之术越过了大河。终点距离他们只有一步之遥了……

description:
他们现在位于的地方，是连接古代和现代两个世界的结界法阵。一般来说，即使是神也是不能跨越时空的，但是， lin\_toto 给了他们一点提示，告诉了他们这个法阵的玄机。并告诉 kkksc03 与 lzn，只要同心协力，就可以改变命运，突破结界的枷锁。

lin\_toto 带他们走到了法阵的前方。展示在他们面前的是一堵巨大却残缺的墙，由若干组连续魔力砖组成（每个魔力砖均为正方体，大小均为 $1\times1\times1$），且各组魔力砖的高度各不相同。根据经验，只有让最少连续 $K$ 组成这堵墙的魔力砖的高度相同，才能突破法阵的入口，召唤来自神界的帮助，跨越时空。

两人可完成的操作如下：从墙上搬走一块砖，或是从旁边的魔力砖堆（假设可用的魔力砖无限）中拿一块砖放置在墙上。每搬运一块砖都会耗费 kkksc03 与 lzn 一点能量值。lzn 希望让两人所耗费的能量值最少。

现在kkksc03带着这个问题找到了聪明的你，你能帮他计算出他所需付出的最少能量值吗？

inputFormat: 一行两个正整数 $N, K$。下面 $N$ 行，每行代表这组魔力砖的高度 $H _ i$。

outputFormat: 一个整数，表示所需付出的最少能量值。

hint:
对于 $10\%$ 的数据, 有 $1≤ N ≤ 10, 2 ≤ K ≤ N, 0 ≤ H _ i ≤ N$。

对于 $20\%$ 的数据，有 $K = 2$。

对于 $40\%$ 的数据，有 $1≤ N ≤ 500, 2 ≤ K ≤ N, 0 ≤ H _ i ≤ N$。

对于 $80\%$ 的数据，有 $1≤ N ≤ 10 ^ 5 , 2 ≤ K ≤ N, 0 ≤ H _ i ≤ 10 ^ 6$。

对于 $100\%$ 的数据，有 $1≤ N ≤ 5\times 10 ^ 5 , 2 ≤ K ≤ N, 0 ≤ H _ i ≤ 10 ^ {12}$，并且所有 $H _ i$ 互不相同。


title: 路边的水沟

background: 某市有一个巨大的水沟网络，可以近似看成一个 $n \times m$ 的矩形网格，网格的每个格点都安装了闸门，我们将从水沟网络右下角的闸门到左上角的闸门的一条路径称为水流。

description: 现给定水沟网的长和宽，求该水沟网中所有只包含向左和向上移动的水流数量。

inputFormat: 输入共 $1$ 行，包含两个整数 $n$ 和 $m$。

outputFormat: 输出一个数字 $ans$，即水流的数量。由于答案可能很大，请输出答案对 $1000000007$ 取模的结果。


title: 琪琪的项链

background: Piet项目的一对开发者laosb(吕世博)与scjyholy(叶嘉琪)最近一直为中国学生站长联盟的童鞋们所津津乐道，不仅仅因为他们天天在某群中秀恩爱，而且他们还经常被用作题目背景。现在我们以他们为背景来引出一道问题。

description:
话说laosb在与scjyholy配对成功1周年后，laosb花光了其所有的积蓄，为scjyholy买了一条项链。但是，他发现店中项链的样式实在太少，于是他想买回一条项链，组成自己的独特样式，以使scjyholy感动。

首先laosb把项链中所有珠子取下，然后从左到右，选出若干珠子（至少1颗），组成新的项链。因为项链珠子有很多颜色，laosb希望知道他一共能组合出多少种不同的样式。

如图所示，假设原始的项链有3颗珠子：蓝、黄、蓝，这样他一共有如下的选择方法：

 ![](https://cdn.luogu.com.cn/upload/pic/1.png)

由于答案可能很大，请输出答案 mod M的结果。

inputFormat:
输入第1行，两个整数N、M，其中N为原始珠子数目。

输入第2行，N个非负整数，每个整数代表一颗珠子颜色，相同整数表示颜色相同。

outputFormat: 输出一个整数，表示样式总数 mod M的值。


title: 爱的供养

background:
在很久很久以前，有一只野心勃勃的骑士 Mori，带领自己的军队，征战世界，所向披靡……

有一天，他跨过千山万水，越过重重山岭，来到了一个美丽的（程序）国度。在这里，他与 Soha 公主一见钟情，并最终坠入爱河。

从此，他们幸福快乐地生活在了一起……

description:
但好日子却不长久。Mori 的手下大将恶魔猎手在此时背叛了他，自立为王，率领深藏在世界之轴的龙族叛变，并掳走了 Soha 公主。Mori 在与恶魔猎手的战斗中，遭遇围杀，被困在一个荒芜人烟的大岛上。但在经过勘探后，他惊喜地发现，Soha 也同时被恶魔猎手关押在这座岛上！

经过精心研究，Mori 发现关押 Soha 的地牢需要若干把钥匙才能打开，而钥匙则被埋藏在一系列的法阵中。凭借着自己的身手与魔力，Mori 是能够破解法阵、获得钥匙的。法阵是一个 $M\times N$ 大小的矩阵，法阵中的每一格都具有自己的高度。其中，有一部分格中埋藏着钥匙，但 Mori 法力不足，无法直接挖取。而他发现，只需从埋藏着钥匙的格子出发向四周的格子走，并在不少于 $T$ 个的独立法阵格子中施法（包括埋藏钥匙的格子本身也要施法），便可挖出钥匙。换句话说，在他每次挖掘钥匙之前，都必须先从埋藏钥匙的格子开始，走过周围的 $T-1$ 个不重复的格子。

虽然 Mori 施法不需要耗费体力，但他在移动的过程中，需要耗费一定量的体力（体育不及格 233）。从一个格子移动到另一个格子中所耗费的体力值为两个格子的高度值之差的绝对值。

对于每个埋藏钥匙的格子来说，定义其难度值 $P$ 为在施法过程中，每次在各个格子间移动的所需耗费的体力的最大值。

而 Mori 则希望让这个难度值越小越好。因为，只有保留足够多的体力，他才能营救 Soha，并两人合力打败恶魔猎手的背叛。

所以，他想知道所有埋藏钥匙的点的难度值的和最小值可以是多少？

inputFormat:
第 $1$ 行，三个整数 $M$、$N$、$T$。

接下来 $M$ 行，每行 $N$ 个整数，为各格的高度。

接下来 $M$ 行，每行 $N$ 个 $0$ 或 $1$， $1$ 代表该格点埋藏有钥匙。

outputFormat: 一个整数，代表难度值的和的最小值。

hint:
$1 ≤ M, N ≤ 600$

$1 ≤ T ≤ M\times N$


title: loidc，想想看

background: 话说 loidc 现在正在家闲的无聊，这天 loidc 正在观看比赛，他突然很有兴趣想了解一段时间内中国队获得金牌的情况。

description: 还有一点，loidc 有特殊能力，可以预知未来，他可以准确的猜到中国队在某一个单位时间内获得的金牌数。但是，还有但是！由于工作量太大，再加上猜金牌要费很多的体力，所以他无法准确的计算出一段时间内获得的金牌数最大的单位时间是哪个，就因为这样 loidc 很郁闷。他思索来思索去就想到了你，因为他知道你是个 OIer，所以他对你呵呵一笑就把问题交给你了，loidc 希望你能在 1 s 内得出答案。

inputFormat:
第一行一个 $n$，表示有 $n$ 个时间段。

接下来一行有 $n$ 个数 $a_i$，$a_i$ 表示 loidc 猜到的中国队在第 $i$ 个时间段内获得的金牌数。

然后，第三行有一个数 $m$，表示 loidc 有个问题。

接下来有 $m$ 行，每行有 $2$ 个数分别为 $x_i$，$y_i$，表示要询问在时间段 $[x_i,y_i]$ 内中国队获得金牌数最大的是哪个单位时间。

loidc 有一个习惯，他问问题是有先后的，也就是说后一个问题总是在前一个问题之后提出的。

注意对于第 $i$ 个提问和第 $i+1$ 个提问严格的有 $x_i \le x_{i+1}$、$y_i \le y_{i+1}$。

outputFormat: 一共 $m$ 行，每行一个 $k_i$，表示第 $i$ 个询问的答案。

hint:
$30\%$：$n \le 1000$，$m \le 1000$。

$100\%$：$n \le {10}^5$，$m \le {10}^5$。

其他有关输入输出均小于 `maxlongint`。

数据保证 $a_i$ 没有相同的。


title: loidc，卖卖萌

background:
loidc 萌萌哒。

他最近一直在靠卖萌追求他的真爱——vivym，经过几轮攻势后 vivym 酱眼看就要被他所攻略。擅长数据结构的 vivym 决定利用强大的数据结构之力帮助自己逃脱。

description: vivym 给了 loidc 一串阿拉伯数字。他将一个数串的每个数字之和定义为该数串的数串和，vivym 要求 loidc 求出数串中有多少个子串的数串和为正数。他想了半天总是解决不好，于是他便将这一棘手的问题交给了编程能力极强的你，他希望你能在 1 s 内解决。不然 vivym 就要闪现过墙幽灵疾步跑掉了。

inputFormat:
第一行一个数 $n$，表示数串的长度。

第二行一共 $n$ 个数，它就是那串阿拉伯数字。

outputFormat: 一个数，表示数串中有多少个子串的数串和为正数。

hint:
- 对于 $30\%$ 的数据：$n\leq 10^3$；
- 对于 $100\%$ 的数据：$1 \leq n\leq 10^5$。

题目读入的其他变量均介于 $-100\ldots 100$ 之间。


title: loidc，看看海

background:
loidc喜欢大海。在他放假的时候他经常一个人跑到海边独自玩耍。

在浪花的冲击下，他可以忘记打代码的烦躁，真是惬意极了。

虽然今天是周六，但今天可是11.8号。在早晨放松之余他可不能忘掉OI知识。

description:
loidc准备带着LOI的队员们考完试后到海边玩耍。所以他想写一个程序让队员们了解在一段时间内海浪的情况。他的命令是这样的x y k输入的，这是要询问在时间[x,y]内海浪高度第k小的单位时刻是那个时刻。

但是在他刚准备打开Dev-pas++ 的时候，loidc发现他的电脑坏掉了。于是一向喜欢偷懒的他就向你求助。他希望你能在1S内完成程序的运行。

当然loidc会提前告诉你所有时段海浪的高度，这点你放心。至于他是如何得到的，这就不得而知了。

inputFormat:
第一行一个数n，表示总时间段。

第二行n个数，一次表示1~n单位时刻海浪的高度。（数据保证各个时刻海浪高度均不相同）

第三行一个数m，表示有m个询问。

接下来m行，每行3个数x y k，表示一个询问。（数据保证k<=y-x+1）

outputFormat: 一共m行，是每个询问的回答。


title: [HNOI2002] DNA分子的最佳比对

description:
$\operatorname{DNA}$ 分子是人类遗传信息的载体，它间接地指导蛋白质的合成。$\operatorname{DNA}$ 分子是由四种核苷酸组成的长链，这四种核苷酸分别是腺嘌呤核苷酸（用 $\operatorname{A}$ 代表）、鸟嘌呤核苷酸（用 $\operatorname{G}$ 代表）、胞嘧啶核苷酸（用 $\operatorname{C}$ 代表）和胸腺嘧啶核苷酸（用 $\operatorname{T}$ 代表）。习惯上用一个字符集为 $\{\operatorname{A,T,C,G}\}$ 的字符串来表示一个 $\operatorname{DNA}$ 分子序列，如 $\operatorname{CGTTAGA}$ 。

在生物进化过程中， $\operatorname{DNA}$ 分子可能发生各种各样的突变。这种突变形成了生物遗传信息的改变，从而使生物得以分化，构成了生物的多样性。

主要的突变有三种：

1. 在一个 $\operatorname{DNA}$ 序列中插入一个新的核苷酸，

2.  $\operatorname{DNA}$ 序列中丢失了一个核苷酸，

3.  $\operatorname{DNA}$ 序列中的某个核苷酸被另一个核苷酸所取代。

所谓两个 $\operatorname{DNA}$ 序列的一个比对是寻找一种排列方式，使得两个 $\operatorname{DNA}$ 序列在同样的位置上有相同的核苷酸，而若在同样的位置上两个DNA序列的核苷酸不同，则是由三种突变之一得到。例如，对两个 $\operatorname{DNA}$ 序列 $T_1 =\operatorname{ATCAG}$ ， $T_2 =\operatorname{ACTAG}$ ，可以按如下方式比对，（ $-$ 表示空白）

比对一：

| $T_1$ | $T_2$ |
| :----------- | :----------- |
| $A$ | $A$ |
| $T$ | $-$ |
| $C$ | $C$ |
| $-$ | $T$ |
| $A$ | $A$ |
| $G$ | $G$ |

也可以按如下方式比对

比对二：

| $T_1$ | $T_2$ |
| :----------- | :----------- |
| $A$ | $A$ |
| $T$ | $C$ |
| $C$ | $T$ |
| $A$ | $A$ |
| $G$ | $G$ |

如果两个 $\operatorname{DNA}$ 序列在相同的位置上有越多相同的核苷酸对，则表明它们之间越相似，即它们存在功能上的相似性和进化史上的亲缘关系。

对于两个 $\operatorname{DNA}$ 序列的一个比对，规定如下得分方式：

1. 一个同样的位置上有相同的核苷酸对，则可得 $1$ 分；

2. 一个同样的位置上有不同的核苷酸对，则得 $0$ 分；

3. 如果在某个位置上一个序列有核苷酸，而另一个序列在该位置上为 $-$，则得 $-2$ 分。例如，比对一的得分是 $0$ 分，比对二的得分是 $3$ 分。

问题是：对于两个 $\operatorname{DNA}$ 序列，寻找一种比对方式，使得它们的得分最高。

inputFormat:
输入数据共有两行。

第一行为 $\text{DNA}$ 序列 $T _ 1$，第二行为 $\text{DNA}$ 序列 $T _ 2$。序列的长度不大于 $1000$。序列中的字母是英文小写或者大写字母。

outputFormat: 程序运行结束时，在屏幕上输出所找出的最大的得分。


title: [HNOI2002] 高质量的数据传输

inputFormat:
输入文件ROUTING.IN

共有2n+1行。

第1行是网络的节点数n，数据要传输的两个结点的序号i，j，其中结点数n不大于200。第2行到第n+1行是时延t的邻接矩阵，其元素tkl的值是第k个结点到第l个结点的边的时延，当其值=-1时表示第k个结点到第l个结点无边。显然该邻接矩阵是对称矩阵。第n+2行到第2n+1行是丢失率p的邻接矩阵，其元素pkl的值是第k个结点到第l个结点的边的丢失率，已精确到小数点后4位，当其值=-1时表示第k个结点到第l个结点无边。显然该邻接矩阵是对称矩阵。

outputFormat:
输出文件ROUTING.OUT

共1行，输出所找出的路径的时延和丢失率（精确到小数点后4位）。


title: [HNOI2002] 奶牛的运算

description:
最近，Farmer John 农场里的奶牛正在学习数学基础课。这天，奶牛 Besty 学会了加减法运算和括号的使用。

Farmer John 为了考察 Besty 的学习情况，写了如下一个算式：

$S =A_1-A_2-\ldots-A_n$

接着，Farmer John 告诉 Besty，这个算式中省略了 $K$ 个括号。将这 $K$ 个括号加入该算式中，就会得到一种算式方案。

例如：$S=A_1-A_2-A_3-A_4$，$K = 2$，则 $S = (A_1)-A_2 - (A_3- A_4)$ 就是一种算式方案。

而对任意两个算式方案，$S'$ 和 $S''$ 本质不同是指：存在某数列 $A_1,\ldots,A_n$ 满足 $S'\ne S''$。否则就是本质相同。

例如：$S'=(A_1)-A_2-(A_3-A_4)$ 与 $S''=(A_1-A_2)-(A_3-A_4)$ 就是本质相同的算式方案。

现在，Farmer John 告诉奶牛 Besty 算式中项的个数 $N$ 和括号的个数 $K$（数列 $A$ 是变量，我们不需要关心它），他想考考 Besty 究竟有多少本质不同的算式方案。

inputFormat: 输入文件仅一行，依次为两个整数 $N$ 和 $K$。（$1<N,K<100$）。

outputFormat: 输出文件仅一行，为本质不同的算式方案数。


title: [HNOI2002] 交换

description:
给定 $n$ 个整数寄存器 $r_1,r_2,\cdots,r_n$。我们定义一个比较交换指令 $\text{CE}(a,b)$ 如下：如果 $r_a$ 中的值大于 $r_b$ 中的值，则交换寄存器 $r_a$ 和 $r_b$ 中的值。其中，$1\leq a<b\leq n$。

一个比较交换程序（简称为 CE-程序）就是一个有限交换指令序列。称一个 CE-程序为 MIN-程序，如果在该程序执行之后，寄存器 $r_1$ 中的值是所有寄存器中的值的最小者；如果一个 CE-程序在删除其中任意一条交换指令后，仍然是一个 MIN-程序，则称该 CE-程序是可靠的 MIN-程序。

你的任务是：给定一个 CE-程序 P，编程求出至少在程序 P 的尾部增加多少条指令才能使程序 P 成为可靠的 MIN-程序。

例如，考虑下列三个寄存器的 CE-程序：

$\text{CE}(1, 2)$，$\text{CE}(2, 3)$，$\text{CE}(1, 2)$。

我们仅需要增加两条指令：$\text{CE}(1, 3)$，$\text{CE}(1, 2)$ 就可使该 CE-程序成为可靠的 MIN-程序。

inputFormat:
共两行，第一行为用空格分开的两个整数 $n,m$；其中 $n$ 为寄存器个数（$2\leq n\leq 10 ^ 4$），$m$ 为 CE-程序的指令条数（$0\leq m\leq20000$）。

接下来为 $m$ 条指令 $\text{CE}(a,b)$，$a,b$ 之间用逗号分隔，两条指令之间也用逗号分隔。

outputFormat: 共一行一个整数即应该增加的最少指令条数。


title: [HNOI2002] 树的排序

description:
1. 空树编号为 $0$，只有根节点的树编号为 $1$；
2. 设 $m$ 为一任意非负整数，那么任意一棵有 $m$ 个节点的树的编号小于任意一棵有 $m+1$ 个节点的树；
3. 设 $A,B$ 是两棵节点数相同的树（$A,B$ 不相同），则 $A$ 编号比 $B$ 小时，一定满足下面两个条件之一（反之亦然）：
   1. $A$ 左子树编号小于 $B$ 左子树编号；
   2. $A$ 左子树编号等于 $B$ 左子树编号（即 $A,B$ 左子树形态相同），且 $A$ 右子树编号小于 $B$ 右子树编号；
4. 编号按照正常的规则，编号应是连续的非负整数，任意一棵树唯一对应一个编号，任意一个非负整数唯一对应一棵树。

（注：上述树均指二叉树）

inputFormat:
仅 $1$ 行，为一个整数 $n$，$1\le n\le 500{,}000{,}000$。

对于 $10\%$ 的数据，保证树节点个数不超过三个。

outputFormat:
仅 $1$ 行，为对应编号为 $n$ 的二叉树。按下列方式输出：

- 如果是一个结点的二叉树，则输出 $X$；
- 如果二叉树的左、右子树分别为 $L$ 和 $R$，$L,R$ 的输出形式分别为 $L'$ 和 $R'$，则输出为 $\texttt{(}L'\texttt{)}X\texttt{(}R'\texttt{)}$，当左子树为空时，输出为 $X\texttt{(}R'\texttt{)}$，当左子树为空时 $\texttt{(}L'\texttt{)}X$。


title: [HNOI2002] 灌溉问题

description:
久居山区的人们一直都为水源的问题而烦恼，缺水使得他们的农田无法获得好的收成。最近，一条好消息传来：政府将提供资金为他们开凿一条水道，将唯一的水源¬——山顶一个湖泊中的水引入他们的村落。人们顿时都高兴了起来，他们的农田终于可以丰收了。

然而，在开凿水道时，人们却遇到了一个难题：怎样开凿才能得到最大的丰收呢？

要知道，山顶的水是非常有限的，并不可能灌溉到每一个地区。而且，不同地区的土地肥沃程度也是不一样的。虽然并非只有河流经过的地区才能被灌溉，但也不可能将水从很远的地方引过来。你现在必须想办法帮他们解决这个问题。

首先，你可以将这个山区划分成N\*N的区域，湖泊的位置(x,y)，以及每个区域的海拔高度（开凿出的河流显然只能从高往低流），还有每块区域的土地价值也是已知的。同时，需要注意的是，你的河流是不允许有分支（支流）的，最多只能灌溉M块土地，而且被灌溉的土地只能在离河流的R格范围以内（包含对角线）。

注意：河流经过的地区土地依然保持其价值，可以选择是否对其灌溉。

你的目的就是找出一条最好的开凿河流的方法，使得能灌溉的土地价值总和最高。

inputFormat:
文件第一行为三个整数N,M,R，分别给出区域的边长，最多灌溉的土地数和被灌溉土地到河流的最大允许距离。(N<=20,M<=100,R<=5)

文件的第二行为两个整数x,y，给出了湖泊的位置。

接下来是两个N\*N的矩阵，第一个矩阵是各区域的海拔高度，第二个矩阵是各区域的土地价值。

outputFormat: 输出文件为river.out。    文件中只有一个整数max，是你的程序计算出的最大价值。


title: [HNOI2002] 农场的果树

description:
Farmer John 的农场环境优美，其中生长了许多苹果树，而苹果正是 Farmer John 农场里奶牛最喜爱的食物！

一天，闲来无事的奶牛 Besty 坐在苹果树下。她忽然发现，农场里的苹果树都是的二叉树！——当然，这种二叉树并不是严格意义上的二叉树，它可能有左子树而不存在右子树，反之也有可能。

刚学过 Computer Science 的 Besty 给二叉树上每个节点记录下其左子树的节点个数。例如下面的一棵树：

```cpp
                3
              /  \
             1     3
            / \   / \
           0   0  1  0
                 / \
                0   0
```
随后，用先序遍历给这棵树编码，需要注意的是叶子节点上的数值不必考虑。为了更方便表述，Besty 又在这样的编码前加入一个数字：该树上节点总数。于是，上面这棵数的编码就是：9 3 1 3 1。

这样一来，每一种编码就对应了一棵唯一的二叉树。

Besty 还发现，农场里的所有二叉树的节点总数都相同！并且在节点总数确定的情况下，对任意的合法编码，农场里都存在唯一的一棵树与之对应！

于是，Besty 将所有的二叉树按照上述编码规则编码，然后以编码为关键字进行字典排序。

现在，对于一个给定的编码，奶牛 Besty 想知道字典排序紧跟其后的编码是什么。

inputFormat:
输入文件名：next.in

输入文件有一行，为一个二叉树的编码。保证节点总数不超过 $5\times10^3$。

outputFormat:
输出文件名：next.out

输出文件有一行，为按字典排序紧跟其后的编码是什么。如果输入的编码是最后一个，则输出 `-1`。


title: [NOI2015] 小园丁与老司机

description:
小园丁 Mr. S 负责看管一片田野，田野可以看作一个二维平面。田野上有 $n$ 棵 许愿树，编号 $1,2,3,\dots,n$ ，每棵树可以看作平面上的一个点，其中第 $i$ 棵树 $(1 \leq i \leq n)$ 位于坐标 $(x_i, y_i)$ 。任意两棵树的坐标均不相同。

老司机 Mr. P 从原点 $(0,0)$ 驾车出发，进行若干轮行动。每一轮，Mr. P 首先选择任意一个满足以下条件的方向：

1.为左、右、上、左上 $45\degree$、右上 $45\degree$ 五个方向之一。

2.沿此方向前进可以到达一棵他尚未许愿过的树。

完成选择后，Mr.P 沿该方向直线前进，必须到达该方向上距离最近的尚未许愿的树，在树下许愿并继续下一轮行动。如果没有满足条件的方向可供选择，则停止行动。他会采取最优策略，在尽可能多的树下许愿。若最优策略不唯一，可以选择任意一种。

不幸的是，小园丁 Mr.S 发现由于田野土质松软，老司机 Mr.P 的小汽车在每轮行进过程中，都会在田野上留下一条车辙印，一条车辙印可看作以两棵树（或原点和一棵树）为端点的一条线段。

在 Mr.P 之后，还有很多许愿者计划驾车来田野许愿，这些许愿者都会像 Mr.P 一样任选一种最优策略行动。Mr.S 认为非左右方向（即上、左上  $45\degree$、右 上 $45\degree$ 三个方向）的车辙印很不美观，为了维护田野的形象，他打算租用一些轧路机，在这群许愿者到来之前夯实所有“可能留下非左右方向车辙印”的地面。“可能留下非左右方向车辙印”的地面应当是田野上的若干条线段，其中每条线段都包含在某一种最优策略的行进路线中。每台轧路机都采取满足以下三个条件的工作模式：

1.从原点或任意一棵树出发。

2.只能向上、左上 $45\degree$、右上 $45\degree$ 三个方向之一移动，并且只能在树下改变方向或停止。

3.只能经过“可能留下非左右方向车辙印”的地面，但是同一块地面可以 被多台轧路机经过。

现在 Mr. P 和 Mr. S 分别向你提出了一个问题：

1.请给 Mr.P 指出任意一条最优路线。

2.请告诉 Mr.S 最少需要租用多少台轧路机。

inputFormat:
第 $1$ 行包含 $1$ 个正整数 $n$，表示许愿树的数量。

接下来 $n$ 行，第 $i+1$ 行包含 $2$ 个整数 $x_i,y_i$，中间用单个空格隔开，表示第 $i$ 棵许愿树的坐标。

outputFormat:
包括 $3$ 行。

第 $1$ 行输出 $1$ 个整数 $m$，表示 Mr. P 最多能在多少棵树下许愿。

输出文件的第 $2$ 行输出 $m$ 个整数，相邻整数之间用单个空格隔开，表示 Mr.P 应该依次在哪些树下许愿。

输出文件的第 $3$ 行输出 $1$ 个整数，表示 Mr. S 最少需要租用多少台轧路机。

hint:
#### 样例 1 解释

最优路线共 $2$ 条，可许愿 $3$ 次：$(0,0) \rightarrow (1,1) \rightarrow (-1,1) \rightarrow (-2,2)$ 或 $(0,0) \rightarrow (0,8) \rightarrow (0,9) \rightarrow (0,10)$。

至少 $3$ 台轧路机，路线是 $(0,0) \rightarrow (1,1)$，$(-1,1) \rightarrow (-2,2)$ 和 $(0,0) \rightarrow (0,8) \rightarrow (0,9) \rightarrow (0,10)$。

#### 样例 2 解释

最优路线唯一：$(0,0) \rightarrow (0,1) \rightarrow (-2,1) \rightarrow (2,1) \rightarrow (3,2)$，可许愿 $4$ 次。其中在 $(0,1)$ 许愿后，从 $(-2,1)$ 出发沿着向右的方向能够到达的最近的未许愿过的树是 $(2,1)$，所以可以到达 $(2,1)$。

而如果沿着 $(0,0) \rightarrow (0,1) \rightarrow (2,1) \rightarrow (-2,1)$ 的方向前进，此时 $(-2,1)$ 右边所有树都是许愿过的，根据题目条件规定，停止前进。故无法获得最优解。

$(0,0) \rightarrow (0,1)$ 与 $(2,1) \rightarrow (3,2)$ 会留下非左右方向车辙印，需 $2$ 台轧路机。

![](https://cdn.luogu.com.cn/upload/pic/1509.png)


title: 被 yyh 虐的 mzc

background: mzc 与 djn 第三弹。

description:
mzc 家很有钱（开玩笑），他家有 $n$ 个男家丁（做过前两弹的都知道）。但这些都不足以挽救他被 yyh 虐的命运。于是他向你们发起了求救。

mzc 要派出男家丁与 yyh 大战，但他只能承载质量为 $m$ 的男家丁，现在他想知道她们（你没有看错）的战斗力之和是否打得过 yyh。

inputFormat:
第一行有三个数 $n,m,k$，$n$ 表示有 $n$ 个男家丁，$m$ 表示能承载 $m$ 表的质量，$k$ 表表示 yyh 表的战斗力。

之后 $n$ 行，每行两个数 $a_i,b_i$，分别表示第 $i$ 个男家丁的质量和战斗力。

outputFormat:
两行，若打得过（大于或等于），输出 `yes`；

若打不过，输出 `no`。

第二行输出最高战斗力。

hint:
对于 $20\%$ 的数据，$n \le 1000$。

对于 $100\%$ 的数据，$n,m \le 10^5$，$0\le a_i,b_i \le 10$。

由于 mzc 大大十分着急，所以他只能等待一秒。


title: [HNOI2003] 24点游戏

description:
为了培养小孩的计算能力，大人们经常给小孩玩这样的游戏：从一副扑克牌中任意抽出 $4$ 张扑克，要小孩用 `+`、`-`、`*`、`/` 和括号组成一个合法的表达式，并使表达式的值为 $24$ 点。这种游戏就是所谓的“$24$ 点游戏”。

请你编程求出对于给出的任意 $4$ 个正整数 $a$、$b$、$c$、$d$，请你编程求出这 $4$ 个整数能组成多少个值为 $24$ 的不同表达式。

inputFormat: 输入文件共一行，为四个正整数 $a$、$b$、$c$、$d$。（$0 \le a, b, c, d \le 100$）

outputFormat: 输出文件为由 $a$、$b$、$c$、$d$ 组成的值为 $24$ 的表达式个数，如没有，输出 $0$。


title: [HNOI2003] 操作系统

description:
写一个程序来模拟操作系统的进程调度。假设该系统只有一个 CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。

如果一个进程到达的时候 CPU 是空闲的，则它会一直占用 CPU 直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用 CPU，而老的只有等待。

如果一个进程到达时，CPU 正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。

一旦 CPU 空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。

inputFormat: 输入包含若干行，每一行有四个自然数（均不超过 $10^8$），分别是进程号，到达时间，执行时间和优先级。不同进程有不同的编号，不会有两个相同优先级的进程同时到达。输入数据已经按到达时间从小到大排序。输入数据保证在任何时候，等待队列中的进程不超过 $15000$ 个。

outputFormat: 按照进程结束的时间输出每个进程的进程号和结束时间。


title: [HNOI2003] 消防局的设立

description:
2020 年，人类在火星上建立了一个庞大的基地群，总共有 $n$ 个基地。起初为了节约材料，人类只修建了 $n-1$ 条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地 $A$ 到基地 $B$ 至少要经过 $d$ 条道路的话，我们称基地A到基地B的距离为 $d$。

由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过 $2$ 的基地的火灾。

你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。

inputFormat: 输入文件的第一行为 $n$（$1 \leq n \leq 1000$），表示火星上基地的数目。接下来的 $n-1$ 行每行有一个正整数，其中文件第 $i$ 行的正整数为 $a_i$，表示从编号为 $i$ 的基地到编号为 $a_i$ 的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有 $a_i\lt i$。

outputFormat: 仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。


title: [HNOI2003] 激光炸弹

description:
一种新型的激光炸弹，可以摧毁一个边长为 $m$ 的正方形内的所有目标。现在地图上有 $n$ 个目标，用整数 $x_i$ , $y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $v_i$。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 $m$ 的边必须与 $x$ 轴，$y$ 轴平行。若目标位于爆破正方形的边上，该目标不会被摧毁。

现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。

可能存在多个目标在同一位置上的情况。

inputFormat:
输入的第一行为整数 $n$ 和整数 $m$；

接下来的 $n$ 行，每行有 $3$ 个整数 $x, y, v$，表示一个目标的坐标与价值。

outputFormat: 输出仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过 $32767$ ）。