title: 书本整理

description:
Frank 是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以 Frank 首先将书按高度顺序排列在书架上。但是 Frank 发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。

书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有 $4$ 本书：

$1 \times 2$
$5 \times 3$
$2 \times 4$
$3 \times 1$

那么 Frank 将其排列整齐后是：

$1 \times 2$
$2 \times 4$
$3 \times 1$
$5 \times 3$

不整齐度就是 $2+3+2=7$。

已知每本书的高度都不一样，请你求出去掉 $k$ 本书后的最小的不整齐度。

inputFormat:
第一行两个数字 $n$ 和 $k$，代表书有几本，从中去掉几本（$1 \le n \le 100, 1  \le k<n$）。

下面的 $n$ 行，每行两个数字表示一本书的高度和宽度，均小于等于 $200$。

保证高度不重复

outputFormat: 一行一个整数，表示书架的最小不整齐度。


title: 生日

type: P

description: cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。

inputFormat:
输入共有 $n + 1$ 行，

第 $1$ 行为 OI 组总人数 $n$；

第 $2$ 行至第 $n+1$ 行分别是每人的姓名 $s$、出生年 $y$、月 $m$、日 $d$。

outputFormat:
输出共有 $n$ 行，

即 $n$ 个生日从大到小同学的姓名。（如果有两个同学生日相同，输入靠后的同学先输出）

samples:
3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1


title: 平台

description:
空间中有一些平台。给出每个平台的位置，请你计算从每一个平台的边缘落下之后会落到哪一个平台上。

注意，如果某两个平台的某个两边缘横坐标相同，物体从上面那个平台落下之后将不会落在下面那个平台上（即平台的范围是一个开区间，不包含端点）。平台**可能会重叠**。

从平台下落时视作从平台下方开始下落，也就是说不会落到高度相同的平台上。**如果有两个平台的高度相同且都可以被落到的话，那么会落到编号靠前的那个平台。**

inputFormat:
第一行有一个数 $N$ 表示平台的个数;

接下来 $N$ 行每行三个整数 分别是平台的高度 $H_i$，左端点的 $X$ 坐标 $L_i$，右端点的 $X$ 坐标 $R_i$。

其中，$1 \le N \le {10}^3$，$0 \le H,L,R \le 2 \times {10}^4$。

outputFormat:
输出共 $N$ 行，每行两个数，分别表示：

从第 $i$ 个平台的左边缘落下后到达的平台序号和右边缘落下以后到达的平台序号。

输入数据中第一个平台的序号是 $1$。如果某个平台的某个边缘下面没有平台了，输出 $0$。


title: 删数问题

description: 键盘输入一个高精度的正整数 $n$（不超过 $250$ 位），去掉其中任意 $k$ 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 $n$ 和 $k$，寻找一种方案使得剩下的数字组成的新数最小。

inputFormat:
输入两行正整数。

第一行输入一个高精度的正整数 $n$。

第二行输入一个正整数 $k$，表示需要删除的数字个数。

outputFormat: 输出一个整数，最后剩下的最小数。

hint: 用 $\operatorname{len}(n)$ 表示 $n$ 的**位数**，保证 $1 \leq k < \operatorname{len}(n) \leq 250$。


title: [BJWC2008] 雷涛的小猫

background: 原最大整数参见 P1012

description:
雷涛同学非常的有爱心，在他的宿舍里，养着一只因为受伤被救助的小猫（当然，这样的行为是违反学生宿舍管理条例的）。在他的照顾下，小猫很快恢复了健康，并且愈发的活泼可爱了。

可是有一天，雷涛下课回到寝室，却发现小猫不见了！经过一番寻找，才发现她正趴在阳台上对窗外的柿子树发呆…

在北京大学的校园里，有许多柿子树，在雷涛所在的宿舍楼前，就有 $N$ 棵。并且这 $N$ 棵柿子树每棵的高度都是 $H$。冬天的寒冷渐渐笼罩了大地，树上的叶子渐渐掉光了，只剩下一个个黄澄澄的柿子，看着非常喜人。而雷涛的小猫恰好非常的爱吃柿子，看着窗外树上的柿子，她十分眼馋，于是决定利用自己敏捷的跳跃能力跳到树上去吃柿子。

小猫可以从宿舍的阳台上跳到窗外任意一棵柿子树的树顶。之后，她每次都可以在当前位置沿着当前所在的柿子树向下跳 $1$ 单位距离。当然，小猫的能力远不止如此，她还可以在树之间跳跃。每次她都可以从当前这棵树跳到另外的任意一棵，在这个过程中，她的高度会下降 `Delta` 单位距离。每个时刻，只要她所在的位置有柿子，她就可以吃掉。整个“吃柿子行动”一直到小猫落到地面上为止。

雷涛调查了所有柿子树上柿子的生长情况。他很想知道，小猫从阳台出发，最多能吃到多少柿子？他知道写一个程序可以很容易的解决这个问题，但是他现在懒于写任何代码。于是，现在你的任务就是帮助雷涛写一个这样的程序。

图为 $N=3, H=10, Delta=2$ 的一个例子。小猫按照图示路线进行跳跃，可以吃到最多的 $8$ 个柿子。

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

inputFormat:
第一行有三个以空格分隔的整数，分别代表 $N,H,Delta$

接下来的 $N$ 行，每行第一个整数为 $N_i$，代表第 $i$ 棵树上的柿子数量。

接下来是 $N_i$ 个整数，每个整数 $T_{i,j}$ 代表第 $i$ 棵柿子树的 $T_{i,j}$ 高度上长有一个柿子。

outputFormat: 一个整数，即小猫最多吃到的柿子数。

hint:
### 数据范围及约定

对于全部数据，$1 \leq N, H ≤ 2000$，$0 \leq N_i ≤ 5000$，$1 ≤ Delta ≤ N,1 ≤ T_{i,j} ≤ H$。

输入文件大小不大于 40MB。注意输入输出效率。

来源 Excalibur, 2008。


title: 低价购买

description:
“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。

这里是某支股票的价格清单：

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
\textsf{日期} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \cr\hline
\textsf{价格} & 68 & 69 & 54 & 64 & 68 & 64 & 70 & 67 & 78 & 62& 98 & 87 \cr\hline
\end{array}$$

最优秀的投资者可以购买最多 $4$ 次股票，可行方案中的一种是：

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textsf{日期} & 2 & 5 & 6 & 10 \cr\hline
\textsf{价格} & 69 & 68 & 64 & 62 \cr\hline
\end{array}
$$

inputFormat:
第一行共一个整数 $N\ (1  \le  N  \le 5000)$，股票发行天数

第二行一行 $N$ 个整数，是每天的股票价格。保证是大小不超过 $2^{16}$ 的正整数。

outputFormat: 输出共一行两个整数，分别为最大购买次数和拥有最大购买次数的方案数（数据保证 $ \le 2^{31}$）当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这 $2$ 种方案被认为是相同的。


title: 学生分组

description: 有 $n$ 组学生，给出初始时每组中的学生个数，再给出每组学生人数的上界 $R$ 和下界 $L\ (L \le R)$，每次你可以在某组中选出一个学生把他安排到另外一组中，问最少要多少次才可以使 $N$ 组学生的人数都在 $[L,R]$ 中。

inputFormat:
第一行一个整数 $n$，表示学生组数；

第二行 $n$ 个整数，表示每组的学生个数；

第三行两个整数 $L,R$，表示下界和上界。

outputFormat: 一个数，表示最少的交换次数，如果不能满足题目条件输出 $-1$。

hint:
### 数据范围及约定

对于全部数据，保证 $1\le n \le 50$。


title: [ZJOI2007] 报表统计

description:
小 Q 的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小 Q 希望可以帮妈妈分担一些工作，作为她的生日礼物之一。

经过仔细观察，小 Q 发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。

在最开始的时候，有一个长度为 $n$ 的整数序列 $a$，并且有以下三种操作：

- `INSERT i k`：在原数列的第 $i$ 个元素后面添加一个新元素 $k$；如果原数列的第 $i$ 个元素已经添加了若干元素，则添加在这些元素的最后（见样例说明）。
- `MIN_GAP`：查询相邻两个元素的之间差值（绝对值）的最小值。
- `MIN_SORT_GAP`：查询所有元素中最接近的两个元素的差值（绝对值）。

于是小 Q 写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？

inputFormat:
第一行包含两个整数，分别表示原数列的长度 $n$ 以及操作的次数 $m$。

第二行为 $n$ 个整数，为初始序列，第 $i$ 个整数表示 $a_i$。

接下来的 $m$ 行，每行一个操作，即`INSERT i k`，`MIN_GAP`，`MIN_SORT_GAP` 中的一种（无多余空格或者空行）。

outputFormat: 对于每一个 `MIN_GAP` 和 `MIN_SORT_GAP` 命令，输出一行答案即可。

samples:
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

hint:
#### 样例输入输出 1 解释

一开始的序列为 $\{5,3,1\}$。

执行操作 `INSERT 2  9` 将得到 $\{5,3,9,1\}$，此时 `MIN_GAP` 为 $2$，`MIN_SORT_GAP` 为 $2$。

再执行操作 `INSERT 2  6` 将得到：$\{5,3, 9, 6, 1\}$。

注意这个时候原序列的第 $2$ 个元素后面已经添加了一个 $9$，此时添加的 $6$ 应加在 $9$ 的后面。这个时候 `MIN_GAP` 为 $2$，`MIN_SORT_GAP` 为 $1$。

---

#### 数据规模与约定

对于全部的测试点，保证 $2 \le n, m \le 5\times10^5$，$1 \leq i \leq n$，$0 \leq a_i, k \leq 5 \times 10^8$。


title: 修复公路

background: A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

description: 给出 A 地区的村庄数 $N$，和公路数 $M$，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

inputFormat:
第 $1$ 行两个正整数 $N,M$。

下面 $M$ 行，每行 $3$ 个正整数 $x,y,t$，告诉你这条公路连着 $x,y$ 两个村庄，在时间 $t$ 时能修复完成这条公路。

outputFormat: 如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 $-1$，否则输出最早什么时候任意两个村庄能够通车。


title: 波浪数

description:
波浪数是在一对**不同**数字之间交替转换的数，如 $1212121$，双重波浪数则是指在两种进制下都是波浪数的数，如十进制数 $191919$ 是一个十进制下的波浪数，它对应的十一进制数 $121212$ 也是一个波浪数，所以十进制数 $191919$ 是一个双重波浪数。特别地，只有一位的数也算作波浪数，例如 $1$。

类似的可以定义三重波浪数，三重波浪数在三种不同的进制中都是波浪数，甚至还有四重波浪数，如 $300_{(10)}=606_{(7)}=363_{(9)}=454_{(8)}=1\mathtt{A}1_{(13)}$，下标表示采用的进制。你的任务就是在指定范围内找出双重、三重、四重波浪数。

inputFormat: 单独一行包含五个用空格隔开的十进制整数 $l, r, L, R, k$。$[l, r]$ 表示应当考虑的进制的范围，$[L,R]$ 表示应当考虑的数字的范围，$k$ 表示你应该找的波浪数的重数。

outputFormat: 从小到大以十进制形式输出指定范围内的指定重数的波浪数。一行输出一个数。

hint:
### 数据范围及约定

对于全部数据，保证 $2\le l\le r\le 32$，$1\le L\le R\le 10^7$，$k\in \{2, 3, 4\}$。


title: 杂务

description:
John 的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。

当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务 $1$。

John 有需要完成的 $n$ 个杂务的清单，并且这份清单是有一定顺序的，杂务 $k\ (k>1)$ 的准备工作只可能在杂务 $1$ 至 $k-1$ 中。

写一个程序依次读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定 John 的农场有足够多的工人来同时完成任意多项任务。

inputFormat:
第1行：一个整数 $n\ (3 \le n \le 10{,}000)$，必须完成的杂务的数目；

第 $2$ 至 $n+1$ 行，每行有一些用空格隔开的整数，分别表示：

- 工作序号（保证在输入文件中是从 $1$ 到 $n$ 有序递增的）；
- 完成工作所需要的时间 $len\ (1 \le len \le 100)$；
- 一些必须完成的准备工作，总数不超过 $100$ 个，由一个数字 $0$ 结束。有些杂务没有需要准备的工作只描述一个单独的 $0$。

保证整个输入文件中不会出现多余的空格。

outputFormat: 一个整数，表示完成所有杂务所需的最短时间。


title: “非常男女”计划

description:
近来，初一年的 `XXX` 小朋友致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。

万圣节来临之际，`XXX` 准备在学校策划一次大型的 “非常男女” 配对活动。对于这次活动的参与者，`XXX` 有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，`XXX` 当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

inputFormat:
第一行有一个正整数 $n\ (1\le n \le 10^5)$，代表学校的人数。

第二行有 $n$ 个用空格隔开的数，这些数只能是 $0$ 或 $1$，其中，$0$ 代表是一个女生，$1$ 代表是一个男生。

outputFormat:
输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子区间的长度。

如果不存在男女人数相等的子区间，请输出 $0$。


title: 最大子段和

description: 给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

inputFormat:
第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

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


title: 车厢重组

description: 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 $180$ 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

inputFormat:
共两行。

第一行是车厢总数 $N( \le 10000)$。

第二行是 $N$ 个不同的数表示初始的车厢顺序。
（**注**：实际上数据中并不都在同一行，有可能分行输入）

outputFormat: 一个整数，最少的旋转次数。


title: [NOI2016] 优秀的拆分

description:
如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意**非空**字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 $ \texttt{aabaabaa} $ ，如果令 $\text{A}=\texttt{aab}$，$\text{B}=\texttt{a}$，我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。
比如我们令 $\text{A}=\texttt{a}$，$\text{B}=\texttt{baa}$，也可以用 $\text{AABB}$ 表示出上述字符串；但是，字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
2. 在一个拆分中，允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。
3. 字符串本身也是它的一个子串。

inputFormat:
每个输入文件包含多组数据。

输入文件的第一行只有一个整数 $T$，表示数据的组数。

接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$，意义如题所述。

outputFormat: 输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。

samples:
4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

hint:
### 样例解释

我们用 $S[i, j]$ 表示字符串 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串（从 $1$ 开始计数）。

第一组数据中，共有三个子串存在优秀的拆分：
$S[1,4]=\texttt{aabb}$，优秀的拆分为 $\text{A}=\texttt{a}$，$\text{B}=\texttt{b}$；
$S[3,6]=\texttt{bbbb}$，优秀的拆分为 $\text{A}=\texttt{b}$，$\text{B}=\texttt{b}$；
$S[1,6]=\texttt{aabbbb}$，优秀的拆分为 $\text{A}=\texttt{a}$，$\text{B}=\texttt{bb}$。
而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 $3$。

第二组数据中，有两类，总共四个子串存在优秀的拆分：
对于子串 $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$，它们优秀的拆分相同，均为 $\text{A}=\texttt{c}$，$\text{B}=\texttt{c}$，但由于这些子串位置不同，因此要计算三次；
对于子串 $S[1,6]=\texttt{cccccc}$，它优秀的拆分有两种：$\text{A}=\texttt{c}$，$\text{B}=\texttt{cc}$ 和 $\text{A}=\texttt{cc}$，$\text{B}=\texttt{c}$，它们是相同子串的不同拆分，也都要计入答案。
所以第二组数据的答案是 $3+2=5$。

第三组数据中，$S[1,8]$ 和 $S[4,11]$ 各有两种优秀的拆分，其中 $S[1,8]$ 是问题描述中的例子，所以答案是 $2+2=4$。

第四组数据中，$S[1,4]$，$S[6,11]$，$S[7,12]$，$S[2,11]$，$S[1,8]$ 各有一种优秀的拆分，$S[3,14]$ 有两种优秀的拆分，所以答案是 $5+2=7$。

### 数据范围

对于全部的测试点，保证 $1 \leq T \leq 10$。以下对数据的限制均是对于单组输入数据而言的，也就是说同一个测试点下的 $T$ 组数据均满足限制条件。

我们假定 $n$ 为字符串 $S$ 的长度，每个测试点的详细数据范围见下表：

| 测试点编号   | $n \leq$  | 特殊性质           |
| ------------ | --------- | ------------------ |
| $1 \sim 2$   | $300$     | $S$ 中所有字符相同 |
| $3 \sim 4$   | $2\,000$  | $S$ 中所有字符相同 |
| $5 \sim 6$   | $10$      |                    |
| $7 \sim 8$   | $20$      |                    |
| $9 \sim 10$  | $30$      |                    |
| $11 \sim 12$ | $50$      |                    |
| $13 \sim 14$ | $100$     |                    |
| $15$         | $200$     |                    |
| $16$         | $300$     |                    |
| $17$         | $500$     |                    |
| $18$         | $1\,000$  |                    |
| $19$         | $2\,000$  |                    |
| $20$         | $30\,000$ |                    |


title: [USACO06FEB] Backward Digit Sums G/S

description:
`FJ` and his cows enjoy playing a mental game. They write down the numbers from $1$ to$ N(1 \le N  \le 10)$ in a certain order and then sum adjacent numbers to produce a new list with one fewer number.  They repeat this until only a single number is left.  For example, one instance of the game (when $N=4$) might go like this:

```cpp
    3   1   2   4
      4   3   6
        7   9
         16
```
Behind `FJ`'s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number $N$.  Unfortunately, the game is a bit above `FJ`'s mental arithmetic capabilities.

Write a program to help `FJ` play the game and keep up with the cows.

inputFormat: 共一行两个正整数 $n,sum$。

outputFormat:
输出包括一行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

translation:
有这么一个游戏：

写出一个 $1\sim n$ 的排列 $a$，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少 $1$，直到只剩下一个数字位置。

下面是一个例子：

- $3,1,2,4$；
- $4,3,6$；
- $7,9$；
- $16$。

最后得到 $16$ 这样一个数字。

现在想要倒着玩这样一个游戏，如果知道 $n$，以及最后得到的数字的大小 $sum$，请你求出最初序列 $a_i$（应该是一个 $1\sim n$ 的排列）。若答案有多种可能，则输出字典序最小的那一个。

我们称序列 $a=\lang a_1,a_2,\cdots,a_n\rang$ 的字典序小于序列 $b=\lang b_1,b_2,\cdots,b_n\rang$ 的字典序，当且仅当存在一个位置 $p$，满足 $a_1=b_1,a_2=b_2,\cdots,a_{p-1}=b_{p-1},a_p<b_p$。


title: 灾后重建

background: B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

description: 给出 B 地区的村庄数 $N$，村庄编号从 $0$ 到 $N-1$，和所有 $M$ 条公路的长度，公路是双向的。并给出第 $i$ 个村庄重建完成的时间 $t_i$，你可以认为是同时开始重建并在第 $t_i$ 天重建完成，并且在当天即可通车。若 $t_i$ 为 $0$ 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 $Q$ 个询问 $(x,y,t)$，对于每个询问你要回答在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $x$ 或村庄 $y$ 在第 $t$ 天仍未重建完成，则需要输出 $-1$。

inputFormat:
第一行包含两个正整数 $N,M$，表示了村庄的数目与公路的数量。

第二行包含 $N$ 个非负整数 $t_0,t_1,\cdots,t_{N-1}$，表示了每个村庄重建完成的时间，数据保证了 $t_0 \le t_1 \le \cdots \le t_{N-1}$。

接下来 $M$ 行，每行 $3$ 个非负整数 $i,j,w$，$w$ 不超过 $10000$，表示了有一条连接村庄 $i$ 与村庄 $j$ 的道路，长度为 $w$，保证 $i\neq j$，且对于任意一对村庄只会存在一条道路。

接下来一行也就是 $M+3$ 行包含一个正整数 $Q$，表示 $Q$ 个询问。

接下来 $Q$ 行，每行 $3$ 个非负整数 $x,y,t$，询问在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少，数据保证了 $t$ 是不下降的。

outputFormat: 共 $Q$ 行，对每一个询问 $(x,y,t)$ 输出对应的答案，即在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果在第 $t$ 天无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $x$ 或村庄 $y$ 在第 $t$ 天仍未修复完成，则输出 $-1$。


title: 小木棍

background:
本题**不保证**存在**可以通过满足本题数据范围的任意数据**做法。可以通过此题的程序不一定完全正确（算法时间复杂度错误、或不保证正确性）

本题为搜索题，本题不接受 hack 数据。[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

description:
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 $50$。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

inputFormat:
第一行是一个整数 $n$，表示小木棍的个数。
第二行有 $n$ 个整数，表示各个木棍的长度 $a_i$。

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

hint: 对于全部测试点，$1 \leq n \leq 65$，$1 \leq a_i \leq 50$。


title: 环状最大两段子段和

description: 给出一段长度为 $n$ 的环状序列 $a$，即认为 $a_1$ 和 $a_n$ 是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。

inputFormat:
第一行是一个整数 $n$，表示序列的长度。

第二行有 $n$ 个整数，描述序列 $a$，第 $i$ 个数字表示  $a_i$。

outputFormat: 一行一个整数，为最大的两段子段和是多少。

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

对于全部的测试点，保证 $2 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。


title: 最大子树和

description:
小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：

一株奇怪的花卉，上面共连有 $N$ 朵花，共有 $N-1$ 条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。

老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。

inputFormat:
第一行一个整数 $n\ (1\le N\le 16000)$。表示原始的那株花卉上共 $n$ 朵花。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 朵花的美丽指数。

接下来 $n-1$ 行每行两个整数 $a,b$，表示存在一条连接第 $a$ 朵花和第 $b$ 朵花的枝条。

outputFormat: 一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过 $2147483647$。


title: 取数游戏

description: 一个 $N\times M$ 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 $8$ 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

inputFormat:
第一行有一个正整数 $T$，表示了有 $T$ 组数据。

对于每一组数据，第一行有两个正整数 $N$ 和 $M$，表示了数字矩阵为 $N$ 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个非负整数，描述了这个数字矩阵。

outputFormat: 共 $T$ 行，每行一个非负整数，输出所求得的答案。


title: 文件压缩

background: 提高文件的压缩率一直是人们追求的目标。近几年有人提出了这样一种算法，它虽然只是单纯地对文件进行重排，本身并不压缩文件，但是经这种算法调整后的文件在大多数情况下都能获得比原来更大的压缩率。

description:
该算法具体如下：对一个长度为 $n$ 的字符串 $S$，首先根据它构造 $n$ 个字符串，其中第 $i$ 个字符串由将 $S$ 的前 $i-1$ 个字符置于末尾得到。然后把这 $n$ 个字符串按照首字符从小到大排序，如果两个字符串的首字符相等，则按照它们**在 $S$ 中的位置**从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串 $S'$ ，它的长度也是 $n$，并且包含了 $S$ 中的每一个字符。最后输出 $S'$ 以及 $S$ 的首字符在 $S'$ 中的位置 $p$。

举例：$S$ 是 `example`

1. 构造 $n$ 个字符串。

```plain
example
xamplee
ampleex
mpleexa
pleexam
leexamp
eexampl
```

2. 将字符串排序。

```plain
ampleex
example
eexampl
leexamp
mpleexa
pleexam
xamplee
```
3. 压缩结果。

$S' = \texttt{xelpame}$，$p = 7$

由于英语单词构造的特殊性，某些字母对出现的频率很高，因此在 $S'$ 中相同的字母有很大几率排在一起，从而提高 $S'$ 的压缩率。虽然这种算法利用了英语单词的特性，然而在实践的过程中，人们发现它几乎适用于所有的文件压缩。

请你编一个程序，读入 $S'$ 和 $p$，输出字符串 $S$。

保证 $S$ 仅含小写字母（所以输入的 $S'$ 也仅含小写字母）。

inputFormat:
共三行。

第一行是一个整数 $n$（$1 \le n \le 10000$），代表 $S'$ 的长度。

第二行是字符串 $S'$。

第三行是整数 $p$。

outputFormat: 一行，$S$。


title: [NOIP2008 提高组] 笨小猴

description:
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！

这种方法的具体描述如下：假设 $\text{maxn}$ 是单词中出现次数最多的字母的出现次数，$\text{minn}$ 是单词中出现次数最少的字母的出现次数，如果 $\text{maxn}-\text{minn}$ 是一个质数，那么笨小猴就认为这是个 Lucky Word，这样的单词很可能就是正确的答案。

inputFormat: 一个单词，其中只可能出现小写字母，并且长度小于 $100$。

outputFormat:
共两行，第一行是一个字符串，假设输入的的单词是 Lucky Word，那么输出 `Lucky Word`，否则输出 `No Answer`；

第二行是一个整数，如果输入单词是 `Lucky Word`，输出 $\text{maxn}-\text{minn}$ 的值，否则输出 $0$。

hint:
【输入输出样例 1 解释】

单词 `error` 中出现最多的字母 $\texttt r$ 出现了 $3$ 次，出现次数最少的字母出现了 $1$ 次，$3-1=2$，$2$ 是质数。

【输入输出样例 2 解释】

单词 `olympic` 中出现最多的字母 $\texttt i$ 出现了 $1$ 次，出现次数最少的字母出现了 $1$ 次，$1-1=0$，$0$ 不是质数。

（本处原题面错误已经修正）

noip2008 提高第一题


title: 机器人搬重物

description:
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径 $1.6$ 米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个 $N\times M$ 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：

- 向前移动 $1$ 步（`Creep`）；
- 向前移动 $2$ 步（`Walk`）；
- 向前移动 $3$ 步（`Run`）；
- 向左转（`Left`）；
- 向右转（`Right`）。

每个指令所需要的时间为 $1$ 秒。请你计算一下机器人完成任务所需的最少时间。

inputFormat: 第一行为两个正整数 $N,M\ (1\le N,M\le50)$，下面 $N$ 行是储藏室的构造，$0$ 表示无障碍，$1$ 表示有障碍，数字之间用一个空格隔开。接着一行有 $4$ 个整数和 $1$ 个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东 $\tt  E$，南 $\tt  S$，西 $\tt W$，北 $\tt N$），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

outputFormat:
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出 $-1$。

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


title: 词链

description:
如果单词 $X$ 的末字母与单词 $Y$ 的首字母相同，则 $X$ 与 $Y$ 可以相连成 $X.Y$。（注意：$X$、$Y$ 之间是英文的句号 `.`）。例如，单词 `dog` 与单词 `gopher`，则 `dog` 与 `gopher` 可以相连成 `dog.gopher`。

另外还有一些例子：
- `dog.gopher`
- `gopher.rat`
- `rat.tiger`
- `aloha.aloha`
- `arachnid.dog`

连接成的词可以与其他单词相连，组成更长的词链，例如：

`aloha.arachnid.dog.gopher.rat.tiger`

注意到，`.` 两边的字母一定是相同的。

现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了 $k$ 次就需要输出 $k$ 次。

inputFormat:
第一行是一个正整数 $n$（$1 \le n \le 1000$），代表单词数量。

接下来共有 $n$ 行，每行是一个由 $1$ 到 $20$ 个小写字母组成的单词。

outputFormat: 只有一行，表示组成字典序最小的词链，若不存在则只输出三个星号 `***`。


title: [HNOI2001] 求正整数

description:
对于任意输入的正整数 $n$，请求出具有 $n$ 个不同因子的最小正整数 $m$。

例如：$n=4$，则 $m=6$，因为 $6$ 有 $4$ 个不同整数因子 $1,2,3,6$；而且是最小的有 $4$ 个因子的整数。

inputFormat: 输入有且仅有一行一个整数，代表 $n$。

outputFormat: 输出一行一个整数，代表符合条件的最小正整数 $m$。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 5 \times 10^4$。


title: [ZJOI2007] 矩阵游戏

description:
小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 $n \times n$ 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

- 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
- 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

inputFormat:
**本题单测试点内有多组数据**。

第一行包含一个整数 $T$，表示数据的组数，对于每组数据，输入格式如下：

第一行为一个整数，代表方阵的大小 $n$。
接下来 $n$ 行，每行 $n$ 个非零即一的整数，代表该方阵。其中 $0$ 表示白色，$1$ 表示黑色。

outputFormat: 对于每组数据，输出一行一个字符串，若关卡有解则输出 `Yes`，否则输出 `No`。

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

- 对于 $20\%$ 的数据，保证 $n \leq 7$。
- 对于 $50\%$ 的数据，保证 $n \leq 50$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 200$，$1 \leq T \leq 20$。


title: 红牌

description:
某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括 $N$ 个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程，每一步政府都派了 $M$ 个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开政府”的政策，政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。

为了防止所有申请人都到效率高的工作人员去申请。这 $M \times N$ 个工作人员被分成 $M$ 个小组。每一组在每一步都有一个工作人员。申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的，一定要相邻两个步骤之间来更换，而不能在某一步骤已经开始但还没结束的时候提出更换，并且也只能从原来的小组 $I$ 更换到小组 $I+1$，当然从小组 $M$ 可以更换到小组 $1$。对更换小组的次数没有限制。

例如：下面是 $3$ 个小组，每个小组 $4$ 个步骤工作天数：

- 小组 $1$： $2, 6 ,1 ,8$；
- 小组 $2$：$3,6, 2, 6$；
- 小组 $3$：$ 4, 2 ,3 ,6$。

例子中，可以选择小组 $1$ 来完成整个过程一共花了$2+6+1+8=17$ 天，也可以从小组 $2$ 开始第一步，然后第二步更换到小组 $3$，第三步到小组 $1$，第四步再到小组 $2$，这样一共花了 $3+2+1+6=12$ 天。你可以发现没有比这样效率更高的选择。

你的任务是求出完成申请所花最少天数。

inputFormat:
第一行是两个正整数 $N$ 和 $M$，表示步数和小组数。

接下来有 $M$ 行，每行有 $N$ 个非负整数，第 $i+1(1 \le i  \le M)$ 行的第 $j$ 个数表示小组 $i$ 完成第 $j$ 步所花的天数，天数都不超过 $1000000$。

outputFormat: 一个正整数，为完成所有步所需最少天数。


title: [ZJOI2007] 时态同步

description:
小 Q 在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字 $1,2,3\cdots$ 进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。

在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激励电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。

激励电流在导线上的传播是需要花费时间的，对于每条边 $e$，激励电流通过它需要的时间为 $t_e$，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小 Q 有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小 Q 最少使用多少次道具才可使得所有的“终止节点”时态同步？

inputFormat:
第一行包含一个正整数 $N$，表示电路板中节点的个数。

第二行包含一个整数 $S$，为该电路板的激发器的编号。

接下来 $N-1$ 行，每行三个整数 $a,b,t$。表示该条导线连接节点 $a$ 与节点 $b$，且激励电流通过这条导线需要 $t$ 个单位时间。

outputFormat: 仅包含一个整数 $V$，为小 Q 最少使用的道具次数。


title: 数字生成游戏

description:
小明完成了这样一个数字生成游戏，对于一个不包含 $0$ 的数字 $s$ 来说，有以下 $3$ 种生成新的数的规则：

1.    将 $s$ 的任意两位对换生成新的数字，例如 $143$ 可以生成 $314,413,134$；

2.    将 $s$ 的任意一位删除生成新的数字，例如 $143$ 可以生成 $14,13,43$；

3.    在 $s$ 的相邻两位之间 $s_i,s_{i + 1}$ 之间插入一个数字 $x$，$x$ 需要满足 $s_i<x<s_{i + 1}$。例如 $143$ 可以生成 $1243,1343$，但是不能生成 $1143,1543$ 等。

现在小明想知道，在这个生成法则下，从 $s$ 开始，每次生成一个数，可以用然后用新生成的数生成另外一个数，不断生成直到生成 $t$ 至少需要多少次生成操作。

另外，小明给规则 $3$ 又加了一个限制，即生成数的位数不能超过初始数 $s$ 的位数。若 $s$ 是 $143$，那么 $1243$ 与 $1343$ 都是无法生成的；若 $s$ 为 $1443$，那么可以将 $s$ 删除变为 $143$，再生成 $1243$ 或 $1343$。

inputFormat:
第一行包含 $1$ 个正整数，为初始数字 $s$。

第二行包含一个正整数 $m$，为询问个数。

接下来 $m$ 行，每行一个整数 $t$（$t$ 不包含 $0$），表示询问从 $s$ 开始不断生成数字到 $t$ 最少要进行多少次操作。任两个询问独立，即上一个询问生成过的数到下一个询问都不存在，只剩下初始数字 $s$。

outputFormat: 共 $m$ 行，每行一个正整数，对每个询问输出最少操作数，如果无论如果无论也变换不成，则输出 $-1$。


title: 教主的花园

description:
教主有着一个环形的花园，他想在花园周围均匀地种上 $n$ 棵树，但是教主花园的土壤很特别，每个位置适合种的树都不一样，一些树可能会因为不适合这个位置的土壤而损失观赏价值。

教主最喜欢 $3$ 种树，这 $3$ 种树的高度分别为 $10,20,30$。教主希望这一圈树种得有层次感，所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低，并且在此条件下，教主想要你设计出一套方案，使得观赏价值之和最高。

inputFormat:
第一行为一个正整数 $n$，表示需要种的树的棵树。

接下来 $n$ 行，每行 $3$ 个不超过 $10000$ 的正整数 $a_i,b_i,c_i$，按顺时针顺序表示了第 $i$ 个位置种高度为 $10,20,30$ 的树能获得的观赏价值。

第 $i$ 个位置的树与第 $i+1$ 个位置的树相邻，特别地，第 $1$ 个位置的树与第 $n$ 个位置的树相邻。

outputFormat: 一个正整数，为最大的观赏价值和。

hint:
【样例说明】。

第 $1$ 至 $n$ 个位置分别种上高度为 $20,10,30,10$ 的树，价值最高。

【数据规模与约定】。

- 对于 $20\%$ 的数据，有 $n\le 10$；
- 对于 $40\%$ 的数据，有 $n\le 100$；
- 对于 $60\%$ 的数据，有 $n\le 1000$；
- 对于 $100\%$ 的数据，有 $4\le n\le 10^5$，并保证 $n$ 一定为偶数。


title: [USACO3.2] 阶乘问题

description:
也许你早就知道阶乘的含义，$N$ 阶乘是由 $1$ 到 $N$ 相乘而产生，如：

$$12!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times  12=479{,}001{,}600$$

$12$ 的阶乘最右边的非零位为 $6$。

写一个程序，计算 $N\ (1\le N\le5\times 10^7)$ 阶乘的最右边的非零位的值。

**注意**：$10{,}000{,}000!$ 的末尾有 $2499999$ 个零。

inputFormat: 仅一行包含一个正整数 $N$。

outputFormat: 一个整数，表示最右边的非零位的值。

hint: USACO Training Section 3.2


title: 奇怪的电梯

background: 感谢 @[yummy](https://www.luogu.com.cn/user/101694) 提供的一些数据。

description: 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（$1 \le i \le N$）上有一个数字 $K_i$（$0 \le K_i \le N$）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3, 3, 1, 2, 5$ 代表了 $K_i$（$K_1=3$，$K_2=3$，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？

inputFormat:
共二行。

第一行为三个用空格隔开的正整数，表示 $N, A, B$（$1 \le N \le 200$，$1 \le A, B \le N$）。

第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$。

outputFormat: 一行，即最少按键次数，若无法到达，则输出 `-1`。

hint:
对于 $100 \%$ 的数据，$1 \le N \le 200$，$1 \le A, B \le N$，$0 \le K_i \le N$。

本题共 $16$ 个测试点，前 $15$ 个每个测试点 $6$ 分，最后一个测试点 $10$ 分。


title: 迎接仪式

description:
LHX 教主要来 X 市指导 OI 学习工作了。为了迎接教主，在一条道路旁，一群“Orz 教主 er”穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。一旁的 Orzer 依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的 Orzer 却不太和谐。

为了简单描述这个不和谐的队列，我们用 `j` 替代“教”，`z` 替代“主”。而一个 `j` 与 `z` 组成的序列则可以描述当前的队列。为了让教主看得尽量舒服，你必须调整队列，使得 `jz` 子串尽量多。每次调整你可以交换任意位置上的两个人，也就是序列中任意位置上的两个字母。而因为教主马上就来了，时间仅够最多做 $K$ 次调整（当然可以调整不满 $K$ 次），所以这个问题交给了你。

inputFormat:
第一行，两个正整数 $N, K$，分别表示序列长度与最多交换次数。

第二行，一个长度为 $N$ 的字符串，字符串仅由字母 `j` 与字母 `z` 组成，描述了这个序列。

outputFormat: 一个非负整数，为调整最多 $K$ 次后最后最多能出现多少个 `jz` 子串。

hint:
**【样例说明】**

第 $1$ 次交换位置 $1$ 上的 `z` 和位置 $4$ 上的 `j`，变为 `jzzzj`；

第 $2$ 次交换位置 $4$ 上的 `z` 和位置 $5$ 上的 `j`，变为 `jzzjz`。

最后的串有 $2$ 个 `jz` 子串。

**【数据规模与约定】**

对于 $10 \%$ 的数据，有 $N \le 10$；
对于 $30 \%$ 的数据，有 $K \le 10$；
对于 $40 \%$ 的数据，有 $N \le 50$；
对于 $100 \%$ 的数据，有 $1 \le N \le 500$，$1 \le K \le 100$。


title: 旅行计划

description:
小明要去一个国家旅游。这个国家有 $N$ 个城市，编号为 $1$ 至 $N$，并且有 $M$ 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 $i$ 停止。

所以他就需要选择最先到达的城市，并制定一条路线以城市 $i$ 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。

现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的 $i$，都需要你为小明制定一条路线，并求出以城市 $i$ 为终点最多能够游览多少个城市。

inputFormat:
第一行为两个正整数 $N, M$。

接下来 $M$ 行，每行两个正整数 $x, y$，表示了有一条连接城市 $x$ 与城市 $y$ 的道路，保证了城市 $x$ 在城市 $y$ 西面。

outputFormat: $N$ 行，第 $i$ 行包含一个正整数，表示以第 $i$ 个城市为终点最多能游览多少个城市。


title: 第 k 小整数

description: 现有 $n$ 个正整数，要求出这 $n$ 个正整数中的第 $k$ 个最小整数（相同大小的整数只计算一次）。

inputFormat: 第一行为 $n$ 和 $k$; 第二行开始为 $n$ 个正整数的值，整数间用空格隔开。

outputFormat: 第$k$个最小整数的值；若无解，则输出 `NO RESULT`。


title: 单向双轨道

description:
如图所示，某火车站有 B、C 两个调度站，左边入口 A 处有$n$ 辆火车等待进站(从左到右以 $a,b,c,d$ 编号)，右边是出口 D，规定在这一段，火车从 A 进入经过 B、C 只能从左向右单向开，并且 B、C 调度站不限定所能停放的车辆数。

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

从文件输入 $n$ 及 $n$ 个小写字母的一个排列，该排列表示火车在出口 D 处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如 $h, L, R$ 的字母序列，其中 $h$ 为火车编号，$L$ 为 $h$ 车原先所在位置（位置都以$\verb!A,B,C,D!$ 表示），$R$ 为新位置。或者输出 `NO` 表示不能完成这样的调度。

inputFormat: 一个数 $n\ (1<n\le 15)$ 及由 $n$ 个小写字母组成的字符串。

outputFormat: 可以调度则输出最短的调度序列，当有多种方案时输出按操作 $(L,R)$ 字典序最小的方案，不可以调度时则输出 `NO`。


title: 相似基因

background:
大家都知道，基因可以看作一个碱基对序列。它包含了 $4$ 种核苷酸，简记作 `A, C, G, T`。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。

在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。

description:
两个基因的相似度的计算方法如下：

对于两个已知基因，例如 `AGTGATG` 和 `GTTAG`，将它们的碱基互相对应。当然，中间可以加入一些空碱基 `-`，例如：

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|c|} \hline
\tt A & \tt G & \tt T & \tt G & \tt A & \tt T & \texttt - & \tt G \\ \hline
\texttt - & \tt G & \tt T & \texttt - & \texttt - & \tt T & \texttt A & \tt G \\ \hline
\end{array}
$$

这样，两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：

$$
\def\arraystretch{1.5}
\begin{array}{ |c|c|c|c|c|c|} \hline
& \tt A & \tt C & \tt G & \tt T & \texttt - \\ \hline
\tt A & 5 & -1 & -2 & -1 & -3\\ \hline
\tt C & -1 & 5 & -3 & -2 & -4 \\\hline
\tt G & -2 & -3 & 5 & -2 & -2 \\\hline
\tt T & -1 & -2 & -2 & 5 & -1 \\\hline
\texttt - & -3 & -4 & -2 & -1 & * \\\hline
\end{array}
$$

那么相似度就是：$(-3)+5+5+(-2)+(-3)+5+(-3)+5=9$。因为两个基因的对应方法不唯一，例如又有：

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|} \hline
\tt A & \tt G & \tt T & \tt G & \tt A & \tt T & \tt G \\ \hline
\texttt - & \tt G & \tt T & \texttt T & \texttt A & \texttt - & \tt G \\ \hline
\end{array}
$$

相似度为：$(-3)+5+5+(-2)+5+(-1)+5=14$。规定两个基因的相似度为所有对应方法中，相似度最大的那个。

inputFormat: 共两行。每行首先是一个整数 $n$，表示基因序列的长度；隔一个空格后是一个基因序列，序列中只含 $\verb!A!,\verb!C!,\verb!G!,\verb!T!$ 四种字母。$1 \le n\le 100$。

outputFormat: 仅一行，即输入基因的相似度。


title: 01迷宫

description:
有一个仅由数字 $0$ 与 $1$ 组成的 $n \times n$ 格迷宫。若你位于一格 $0$ 上，那么你可以移动到相邻 $4$ 格中的某一格 $1$ 上，同样若你位于一格 $1$ 上，那么你可以移动到相邻 $4$ 格中的某一格 $0$ 上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

inputFormat:
第一行为两个正整数 $n,m$。

下面 $n$ 行，每行 $n$ 个字符，字符只可能是 $0$ 或者 $1$，字符之间没有空格。

接下来 $m$ 行，每行两个用空格分隔的正整数 $i,j$，对应了迷宫中第 $i$ 行第 $j$ 列的一个格子，询问从这一格开始能移动到多少格。

outputFormat: $m$ 行，对于每个询问输出相应答案。

hint:
对于样例，所有格子互相可达。

- 对于 $20\%$ 的数据，$n \leq 10$；
- 对于 $40\%$ 的数据，$n \leq 50$；
- 对于 $50\%$ 的数据，$m \leq 5$；
- 对于 $60\%$ 的数据，$n,m \leq 100$；
- 对于 $100\%$ 的数据，$1\le n \leq 1000$，$1\le m \leq 100000$。


title: 轰炸

description:
“我该怎么办？”飞行员 klux 向你求助。

事实上，klux 面对的是一个很简单的问题，但是他实在太菜了。

klux 要想轰炸某个区域内的一些地方，它们是位于平面上的一些点，但是（显然地）klux 遇到了抵抗，所以 klux 只能飞一次，而且由于飞机比较破，一点起飞就只能沿直线飞行，无法转弯。现在他想一次轰炸最多的地方。

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

接下来 $n$ 行，每行有一对整数，表示一个点的坐标。没有一个点会出现两次。

outputFormat: 一个整数，表示一条直线能覆盖的最多的点数。

hint:
### 数据范围

对于全部数据，保证 $1\le n\le 700$。

本题翻译并改编自 uva270，数据及解答由 uva 提供。


title: 进制转换

description: 请你编一程序实现两种不同进制之间的数据转换。

inputFormat: 共三行，第一行是一个正整数，表示需要转换的数的进制 $n\ (2\le n\le 16)$，第二行是一个 $n$ 进制数，若 $n>10$ 则用大写字母 $\verb!A!\sim \verb!F!$ 表示数码 $10\sim 15$，并且该 $n$ 进制数对应的十进制的值不超过 $10^9$，第三行也是一个正整数，表示转换之后的数的进制 $m\ (2\le m\le 16)$。

outputFormat: 一个正整数，表示转换之后的 $m$ 进制数。


title: 最短路计数

description: 给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

inputFormat:
第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。

接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条连接顶点 $x$ 和顶点 $y$ 的边，请注意可能有自环与重边。

outputFormat: 共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。


title: 约瑟夫

description: $n$ 个人站成一圈，从某个人开始数数，每次数到 $m$ 的人就被杀掉，然后下一个人重新开始数，直到最后只剩一个人。现在有一圈人，$k$ 个好人站在一起，$k$ 个坏人站在一起。从第一个好人开始数数。你要确定一个最小的 $m$，使得在第一个好人被杀死前，$k$ 个坏人先被杀死。

inputFormat: 一行一个整数 $k$。

outputFormat: 一行一个整数 $m$。


title: 硬币翻转

description: 在桌面上有一排硬币，共 $N$ 枚，每一枚硬币均为正面朝上。现在要把所有的硬币翻转成反面朝上，规则是每次可翻转任意 $N-1$ 枚硬币（正面向上的被翻转为反面向上，反之亦然）。求一个最短的操作序列（将每次翻转 $N-1$ 枚硬币成为一次操作）。

inputFormat: 一个自然数 $N$（$N$ 为不大于 $100$ 的偶数）。

outputFormat:
第一行包含一个整数 $S$，表示最少需要的操作次数。

接下来的 $S$ 行每行分别表示每次操作后桌上硬币的状态（一行包含 $N$ 个整数 $0$ 或 $1$，表示每个硬币的状态，$0$ 表示正面向上，$1$ 表示反面向上。不允许输出多余空格。

对于有多种操作方案的情况，则只需**操作的字典序**最小输出一种。

操作的字典序是指，对于一次操作中的每个位置，$1$ 表示翻转，$0$ 表示不反转。

但是需要你输出的是每一次操作完的状态，$0$ 表示正面朝上，$1$ 表示反面朝上。


title: 连续自然数和

description:
对一个给定的正整数 $M$，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 $M$。

例子：$1998+1999+2000+2001+2002 = 10000$，所以从 $1998$ 到 $2002$ 的一个自然数段为 $M=10000$ 的一个解。

inputFormat: 包含一个整数的单独一行给出 $M$ 的值（$10 \le M \le 2,000,000$）。

outputFormat: 每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。


title: 拱猪计分

description:
「拱猪」是一种很有趣的扑克牌游戏。即使你不知道它的玩法，你也可以由它的计分方式来了解它的趣味性。假设在此我们仅考虑四个人的拱猪牌局，本题要求你根据下面的计分规则，在牌局结束时计算四位玩家所得分数。

1. 我们分别以 $\texttt S, \texttt H, \texttt D, \texttt C$ 来代表黑桃、红心、方块及梅花，并以数字 $1$ 至 $13$ 来代表 $\texttt A, \texttt 2, \dots, \texttt Q, \texttt K$ 等牌点，例如：$H_1$ 为红心 $\texttt A$，$S_{13}$ 为黑桃 $\texttt K$；
2. 牌局结束时，由各玩家持有的有关计分的牌（计分牌）仅有「猪」$S_{12}$，所有红心牌，「羊」$D_{11}$ 及「加倍」$C_{10}$ 等 $16$ 张牌，其它牌均弃置不计，若一位玩家未持有这 $16$ 张牌中任意一张，则以得零分计算；
3. 若持有 $C_{10}$ 牌的玩家只有该张牌而没有任何其它牌则得 $+50$ 分，否则将其它计分牌所得分数加倍计算；
4. 若红心牌不在同一家，则 $H_1$ 至 $H_{13}$ 等 $13$ 张牌均以负分计，其数值依次为 $-50, -2, -3, -4, -5, -6, -7, -8, -9, -10, -20, -30, -40$，且 $S_{12}$ 与 $D_{11}$ 的分值分别以 $-100$ 及 $+100$ 分计算；
5. 若红心牌 $H_1$ 至 $H_{13}$ 均在同一家，则有下列情形：

+ 所有红心牌以 $+200$ 分计算。
+ 若 $S_{12}, D_{11}$ 皆在吃下所有红心牌之一家，则此玩家得 $+500$ 分。
+ $C_{10}$ 牌依旧以前文所述原则计算。

例一：若各玩家持有计分牌如下：

1. `S12 H3 H5 H13`
2. `D11 H8 H9`
3. `C10 H1 H2 H4 H6 H7`
4. `H10 H11 H12`

则各家之得分依序为：$-148, +83, -138$ 及 $-60$。

例二：若各玩家持有计分牌如下：

1. `H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13`
2. `S12 C10`
3. `D11`
4. 无

则各家之得分依序为：$+200, -200, +100$ 及 $0$。

例三：若有一玩家持有所有 $16$ 张计分牌，则得 $+1000$ 分，其余三家均得零分。

inputFormat:
**每个输入文件包含多组数据。**

每组数据有四行，分别描述一个玩家。

每一行，第一个数为该玩家所持有计分牌总数，随后若干个符合题意的字符串描述其所持有之所有计分牌，牌数与各计分牌均以一个以上的空格分开。

相邻两组测试数据之间不包含空白行。若四家持牌数均为 $0$，表示输入文件的结束。

outputFormat:
每一行表示一组数据对应的结果，依次输出各家所得分数，共 $4$ 个整数，若非 $0$ 则包含正负号；相邻两个整数之间以一个空格分开。

符号和数字间不带空格。每组数据的输出间不带空白行。


title: [NOIP2008 提高组] 火柴棒等式

description:
给你 $n$ 根火柴棍，你可以拼出多少个形如 $A+B=C$ 的等式？等式中的 $A$、$B$、$C$ 是用火柴棍拼出的整数（若该数非零，则最高位不能是 $0$）。用火柴棍拼数字 $0\sim9$ 的拼法如图所示：

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

注意：

1. 加号与等号各自需要两根火柴棍；
2. 如果 $A\neq B$，则 $A+B=C$ 与 $B+A=C$ 视为不同的等式（$A,B,C\geq0$）；
3. $n$ 根火柴棍必须全部用上。

inputFormat: 一个整数 $n(1 \leq n\leq 24)$。

outputFormat: 一个整数，能拼成的不同等式的数目。


title: Peter 的烟

background: **温馨提醒：吸烟有害健康，请勿尝试吸烟！**

description:
Peter 有 $n$ 根烟，他每吸完一根烟就把烟蒂保存起来，$k$（$k>1$）个烟蒂可以换一个新的烟，那么 Peter 最终能吸到多少根烟呢？

与某些脑筋急转弯不同的是，Peter 并不能从异次元借到烟蒂，抽完后再还回去。

inputFormat: 每组测试数据一行包括两个整数 $n, k$（$1 < n, k \le 10^8$）。

outputFormat: 对于每组测试数据，输出一行包括一个整数表示最终烟的根数。


title: 子数整数

description:
对于一个五位数 $\overline{a_1a_2a_3a_4a_5}$，可将其拆分为三个子数：

$sub_1=\overline{a_1a_2a_3}$

$sub_2=\overline{a_2a_3a_4}$

$sub_3=\overline{a_3a_4a_5}$

例如，五位数 $20207$ 可以拆分成

$sub_1=202$

$sub_2=020\ (=20)$

$sub_3=207$

现在给定一个正整数 $K$，要求你编程求出 $10000$ 到 $30000$ 之间所有满足下述条件的五位数，条件是这些五位数的三个子数 $sub_1,sub_2,sub_3$ 都可被 $K$ 整除。

inputFormat: 一个正整数 $K$。

outputFormat: 每一行为一个满足条件的五位数，要求从小到大输出。不得重复输出或遗漏。如果无解，则输出 `No`。


title: 欢乐的跳

description:
一个 $n$ 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 $[1,n-1]$ 之间的所有整数，则称之符合“欢乐的跳”，如数组 $\{1,4,2,3\}$ 符合“欢乐的跳”，因为差的绝对值分别为：$3,2,1$。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

inputFormat: 每组测试数据第一行以一个整数 $n(1 \le n \le 1000)$ 开始，接下来 $n$ 个空格隔开的在 $[-10^8,10^8]$ 之间的整数。

outputFormat: 对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 `Jolly`，否则输出 `Not jolly`。

samples:
4 1 4 2 3
Jolly

samples:
5 1 4 2 -1 6
Not jolly


title: 点和线

description:
平面上有一些点，你可以用直线将两点连接起来。那么有多少种方法可以把这些点连续地连起来，使得任何两个线都不交叉。

显然，三个点只有一种方法。四个点最多只有 $3$ 种方法。写一个程序计算方法总数。

inputFormat: 每一行是一个点的坐标，坐标值是整数，中间用一个空格隔开。最后一个坐标是原点。任意三点不在一条直线上。

outputFormat: 输出方案总数。

hint:
最多只有 $10$  个点。

- 必须从一个点出发，途径所有点回到起点的路径才会被统计。

- 两个方案不相同当且仅当围成的简单多边形不同。


title: 奶牛分厩

description:
农夫约翰有 $N(1 \le N \le 5000)$ 头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号 $s_i$，所有的奶牛都睡在一个有 $K$ 个厩的谷仓中，厩的编号为 $0$ 到 $K-1$。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会了它们做除法，$S_i  \bmod  K$ 的值就是第 $i$ 头奶年所睡的厩的编号。

给出一组奶牛的编号，确定最小的 $K$ 使得没有二头或二头以上的奶牛睡在同一厩中。

inputFormat: 第一行一个正整数 $N$，第 $2$ 到 $N+1$ 行每行一个整数表示一头奶牛的编号。

outputFormat: 一个整数，表示要求的最小的 $K$，对所有的测试数据这样的 $K$ 是一定存在的。


title: [NOIP2008 提高组] 双栈排序

description:
Tom 最近在研究一个有趣的排序问题。如图所示，通过 $2$ 个栈 $S_1$ 和 $S_2$，Tom 希望借助以下 $4$ 种操作实现将输入序列升序排序。

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

- 操作 $\verb!a!$：将第一个元素压入栈 $S_1$。
- 操作 $\verb!b!$：将 $S_1$ 栈顶元素弹出至输出序列。
- 操作 $\verb!c!$：将第一个元素压入栈 $S_2$。
- 操作 $\verb!d!$：将 $S_2$ 栈顶元素弹出至输出序列。

如果一个 $1\sim n$ 的排列 $P$ 可以通过一系列合法操作使得输出序列为 $(1,2,\cdots,n-1,n)$，Tom 就称 $P$ 是一个“可双栈排序排列”。例如 $(1,3,2,4)$ 就是一个“可双栈排序序列”，而 $(2,3,4,1)$ 不是。下图描述了一个将 $(1,3,2,4)$ 排序的操作序列：$\texttt {a,c,c,b,a,d,d,b}$。

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

当然，这样的操作序列有可能有几个，对于上例 $(1,3,2,4)$，$\texttt{a,b,a,a,b,b,a,b}$ 是另外一个可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。

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

第二行有 $n$ 个用空格隔开的正整数，构成一个 $1\sim n$ 的排列。

outputFormat:
共一行，如果输入的排列不是“可双栈排序排列”，输出 `0`。

否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

hint:
$30\%$ 的数据满足：$n\le10$。

$50\%$ 的数据满足：$n\le50$。

$100\%$ 的数据满足：$n\le1000$。

2021.06.17 加强 by [SSerxhs](https://www.luogu.com.cn/user/29826)。hack 数据单独分为一个 subtask 防止混淆。

noip2008 提高第四题


title: 垃圾陷阱

description:
卡门――农夫约翰极其珍视的一条 `Holsteins` 奶牛――已经落了到 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方，它的深度为 $D$（$2 \le D \le 100$）英尺。

卡门想把垃圾堆起来，等到堆得与井深同样高或比井深更高（即，垃圾高度总和 $\geq D$）时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间 $t$（$1 \le t \le 1000$），以及每个垃圾堆放的高度 $h$（$1 \le h \le 25$）和吃进该垃圾能增加维持生命的时间 $f$（$1 \le f \le 30$），要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续 $10$ 小时的能量，如果卡门 $10$ 小时内（不含 $10$ 小时，维持生命的时间同）没有进食，卡门就将饿死。特别地，若体力值为 $0$ 时吃下垃圾或逃出井外也不会饿死。

inputFormat:
第一行为两个整数，$D$ 和 $G$（$1 \le G \le 100$），$G$ 为被投入井的垃圾的数量。

第二到第 $G+1$ 行每行包括三个整数：$T$（$1 \le T \le 1000$），表示垃圾被投进井中的时间；$F$（$1 \le F \le 30$），表示该垃圾能维持卡门生命的时间；和 $H$（$1 \le H \le 25$），该垃圾能垫高的高度。

outputFormat: 如果卡门可以爬出陷阱，输出一个整数，表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。

hint:
**【样例说明】**

卡门堆放她收到的第一个垃圾：$\mathrm{height}=9$；

卡门吃掉她收到的第 $2$ 个垃圾，使她的生命从 $10$ 小时延伸到 $13$ 小时；

卡门堆放第 $3$ 个垃圾，$\mathrm{height}=19$；

卡门堆放第 $4$ 个垃圾，$\mathrm{height}=20$。


title: 组合的输出

description:
排列与组合是常用的数学方法，其中组合就是从 $n$ 个元素中抽出 $r$ 个元素（不分顺序且 $r \le n$），我们可以简单地将 $n$ 个元素理解为自然数 $1,2,\dots,n$，从中任取 $r$ 个数。

现要求你输出所有组合。

例如 $n=5,r=3$，所有组合为：

$123,124,125,134,135,145,234,235,245,345$。

inputFormat: 一行两个自然数 $n,r(1<n<21,0 \le r \le n)$。

outputFormat:
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

**注意哦！输出时，每个数字需要 $3$ 个场宽。以 C++ 为例，你可以使用下列代码：**

```cpp
cout << setw(3) << x;
```

输出占 $3$ 个场宽的数 $x$。注意你需要头文件 `iomanip`。


title: [NOIP2010 普及组] 导弹拦截

description:
经过 $11$ 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 $0$ 时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。

某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

inputFormat: 第一行包含 $4$ 个整数 $x_1,y_1,x_2,y_2$，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为 $(x_1,y_1), (x_2,y_2)$。第二行包含 $1$ 个整数 $N$，表示有 $N$ 颗导弹。接下来 $N$ 行，每行两个整数 $x,y$，中间用一个空格隔开，表示一颗导弹的坐标 $(x,y)$。不同导弹的坐标可能相同。

outputFormat: 一个整数，即当天的最小使用代价。

hint:
两个点 $(x_1,y_1),(x_2,y_2)$ 之间距离的平方是 $(x_1-x_2)^2+(y_1-y_2)^2$。

两套系统工作半径 $r_1,r_2$ 的平方和，是指 $r_1,r_2$ 分别取平方后再求和，即 $r_1^2+r_2^2$。

### 样例 1 说明

样例 $1$ 中要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为 $18$ 和 $0$。

### 样例 2 说明

样例 $2$ 中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为 $20$ 和 $10$。

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

【数据范围】。

- 对于 $10\%$ 的数据，$N=1$。
- 对于 $20\%$ 的数据，$1\le N\le 2$。
- 对于 $40\%$ 的数据，$1\le N\le 100$。
- 对于 $70\%$ 的数据，$1\le N\le 1000$。
- 对于 $100\%$ 的数据，$1\le N\le 10^5$，且所有坐标分量的绝对值都不超过 $1000$。

NOIP2010 普及组 第三题


title: 排行榜

description:
小迈克尔住在一个小镇上，他喜欢看每周日下午发布的音乐电视评比。它每周都根据选票介绍相同的歌曲，列出这些歌曲的流行排行榜。

有一个星期日迈克尔和他的朋友在一起玩得太久了以致于未能看到新的流行榜。他非常失望，但是不久他就发现下周至少可以部分地建立出流行榜。除了每首歌曲的位置，排行榜还根据这些歌曲上周的排行列出了它们排行变动的信息，更精确地说，从这周起，不管那首歌是继续排在原位，还是排名上升或排名下降，都会给出一点说明。

编写程序，根据给定的流行榜帮助迈克尔推断出上周可能的排行榜。

inputFormat:
第一行是一个整数 $N(1≤N≤100)$，表示排行榜上歌曲的总数。

接下来的 $N$ 块列出了排行信息。每块有两行组成，第i块第一行是第 $i$ 首歌曲的名称，歌名包括最多不超过 $100$ 个英文大写字母，第二行包含下列三个单词中的一个：`UP`（歌曲在排行榜上的位置上升），`DOWN`（歌曲在排行榜上的位置下滑）或 `SAME`（排行不变），表示与上周排行榜相比，排行榜所发生的变动。

outputFormat:
$N$ 行输出一个上周可能的排行榜。

每一行包含一首歌名，即第 $i$ 行包含排行榜上第 $i$ 首歌的歌名。

注意：解不必是唯一的，但对于每一个测试数据都至少有一个解。

samples:
5
HIGHHOPES
UP
LOWFEELINGS
UP
UPANDDOWN
DOWN
IAMSTILLSTANDING
DOWN
FOOLINGAROUND
DOWN

samples:
UPANDDOWN
IAMSTILLSTANDING
FOOLINGAROUND
HIGHHOPES
LOWFEELINGS


title: 队列安排

description:
一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $1\sim N$，他采取如下的方法：

1. 先将 $1$ 号同学安排进队列，这时队列中只有他一个人；

2. $2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 $M$ 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

inputFormat:
第一行一个整数 $N$，表示了有 $N$ 个同学。

第 $2\sim N$ 行，第 $i$ 行包含两个整数 $k,p$，其中 $k$ 为小于 $i$ 的正整数，$p$ 为 $0$ 或者 $1$。若 $p$ 为 $0$，则表示将 $i$ 号同学插入到 $k$ 号同学的左边，$p$ 为 $1$ 则表示插入到右边。

第 $N+1$ 行为一个整数 $M$，表示去掉的同学数目。

接下来 $M$ 行，每行一个正整数 $x$，表示将 $x$ 号同学从队列中移去，如果 $x$ 号同学已经不在队列中则忽略这一条指令。

outputFormat: 一行，包含最多 $N$ 个空格隔开的整数，表示了队列从左到右所有同学的编号。

hint:
**【样例解释】**

将同学 $2$ 插入至同学 $1$ 左边，此时队列为：

`2 1`

将同学 $3$ 插入至同学 $2$ 右边，此时队列为：

`2 3 1`

将同学 $4$ 插入至同学 $1$ 左边，此时队列为：

`2 3 4 1`

将同学 $3$ 从队列中移出，此时队列为：

`2 4 1`

同学 $3$ 已经不在队列中，忽略最后一条指令

最终队列：

`2 4 1`

**【数据范围】**

对于 $20\%$ 的数据，$1\leq N\leq 10$。

对于 $40\%$ 的数据，$1\leq N\leq 1000$。

对于 $100\%$ 的数据，$1<M\leq N\leq 10^5$。


title: 开灯

description:
在一条无限长的路上，有一排无限长的路灯，编号为 $1,2,3,4,\dots$。

每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。

在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：

指定两个数，$a,t$（$a$ 为实数，$t$ 为正整数）。将编号为 $\lfloor a\rfloor,\lfloor 2 \times a\rfloor,\lfloor3 \times a\rfloor,\dots,\lfloor t  \times a\rfloor$ 的灯的开关各按一次。其中 $\lfloor k \rfloor$ 表示实数 $k$ 的整数部分。

在小明进行了 $n$ 次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。

幸好，小明还记得之前的 $n$ 次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

inputFormat:
第一行一个正整数 $n$，表示 $n$ 次操作。

接下来有 $n$ 行，每行两个数，$a_i,t_i$。其中 $a_i$ 是实数，小数点后一定有 $6$ 位，$t_i$ 是正整数。

outputFormat: 仅一个正整数，那盏开着的灯的编号。

hint:
记 $T=\sum \limits_{i=1}^n t_i = t_1+t_2+t_3+\dots+t_n$。

- 对于 $30\%$ 的数据，满足 $T \le 1000$；
- 对于 $80\%$ 的数据，满足 $T \le 200000$；
- 对于 $100\%$ 的数据，满足 $T \le 2000000$；
- 对于 $100\%$ 的数据，满足 $n \le 5000$，$1 \le a_i<1000$，$1 \le t_i \le T$。

数据保证，在经过 $n$ 次操作后，有且只有一盏灯是开的，不必判错。而且对于所有的 $i$ 来说，$t_i\times a_i$ 的最大值不超过 $2000000$。


title: 填涂颜色

description:
由数字 $0$ 组成的方阵中，有一任意形状的由数字 $1$ 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 $2$。例如：$6\times 6$ 的方阵（$n=6$），涂色前和涂色后的方阵如下：

如果从某个 $0$ 出发，只向上下左右 $4$ 个方向移动且仅经过其他 $0$ 的情况下，无法到达方阵的边界，就认为这个 $0$ **在闭合圈内**。闭合圈不一定是环形的，可以是任意形状，但保证**闭合圈内**的 $0$ 是连通的（两两之间可以相互到达）。

```plain
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
```
```plain
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1
```

inputFormat:
每组测试数据第一行一个整数 $n(1 \le n \le 30)$。

接下来 $n$ 行，由 $0$ 和 $1$ 组成的 $n \times n$ 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 $0$。

outputFormat: 已经填好数字 $2$ 的完整方阵。


title: 银行贷款

description: 当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。

inputFormat:
三个用空格隔开的正整数。

第一个整数表示贷款的原值 $w_0$，第二个整数表示每月支付的分期付款金额 $w$，第三个整数表示分期付款还清贷款所需的总月数 $m$。

outputFormat:
一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 $0.1\%$。

数据保证答案不超过 $300.0\%$。


title: 小A点菜

background:
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。

uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。

description:
不过 uim 由于买了一些书，口袋里只剩 $M$ 元 $(M \le 10000)$。

餐馆虽低端，但是菜品种类不少，有 $N$ 种 $(N \le 100)$，第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$。由于是很低端的餐馆，所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿，所以最多只能等待 $1$ 秒。

inputFormat:
第一行是两个数字，表示 $N$ 和 $M$。

第二行起 $N$ 个正数 $a_i$（可以有相同的数字，每个数字均在 $1000$ 以内）。

outputFormat: 一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

hint: 2020.8.29，增添一组 hack 数据 by @yummy


title: 日志分析

description:
M 海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入库和出库的规则为先进后出，即每次出库操作出库的集装箱为当前在仓库里所有集装箱中最晚入库的集装箱。

出于分析目的，分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时，每遇到一次查询操作，都要报告出当前仓库中最大集装箱的重量。

inputFormat:
包含 $N+1$ 行：

第一行为一个正整数 $N$，对应于日志内所含操作的总数。

接下来的 $N$ 行，分别属于以下三种格式之一：

- 格式 1：`0 X`，表示一次集装箱入库操作，正整数 $X$ 表示该次入库的集装箱的重量。
- 格式 2：`1`，表示一次集装箱出库操作，（就当时而言）最后入库的集装箱出库。
- 格式 3：`2`，表示一次查询操作，要求分析程序输出当前仓库内最大集装箱的重量。

当仓库为空时你应该忽略出库操作，当仓库为空查询时你应该输出 $0$。

outputFormat: 输出行数等于日志中查询操作的次数。每行为一个整数，表示查询结果。


title: 打保龄球

description:
打保龄球是用一个滚球去打击十个站立的柱，将柱击倒。一局分十轮，每轮可滚球一次或多次，以击倒的柱数为依据计分。一局得分为十轮得分之和，而每轮的得分不仅与本轮滚球情况有关，还可能与后续一两轮的滚球情况有关。即某轮某次滚球击倒的柱数不仅要计入本轮得分，还可能会计入前一两轮得分。具体的滚球击柱规则和计分方法如下：

1. 若某一轮的第一次滚球就击倒全部十个柱，则本轮不再滚球（若是第十轮则还需另加两次滚球，不妨称其为第十一轮和第十二轮，并不是所有的情况都需要滚第十一轮和第十二轮球）。该轮得分为本次击倒柱数 $10$ 与以后两次滚球所击倒柱数之和。

2. 若某一轮的第一次滚球未击倒十个柱，则可对剩下未倒的柱再滚球一次。如果这两次滚球击倒全部十个柱，则本轮不再滚球（若是第十轮则还需另加一次滚球），该轮得分为这两次共击倒柱数 $10$ 与以后一次滚球所击倒柱数之和。

3. 若某一轮两次滚球未击倒全部十个柱，则本轮不再继续滚球，该轮得分为这两次滚球击倒的柱数之和。

总之，若―轮中一次滚球或两次滚球击倒十个柱，则本轮得分是本轮首次滚球开始的连续三次滚球击倒柱数之和（其中有一次或两次不是本轮滚球）。若一轮内二次滚球击倒柱数不足十个，则本轮得分即为这两次击倒柱数之和。下面以实例说明如下(字符 `/` 表示击倒当前球道上的全部的柱)：

| 轮 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| 击球情况  |  /  |  /  |  /  |  72 |  9/ |  81  | 8/  |  / |   9/  |  /  |  8/ |
| 各轮得分 |  30  | 27  | 19 |  9   |18   | 9  | 20  | 20 |  20 |  20|
|累计总分 |  30  | 57  |76 |  85|  103 |  112 | 132  |152 | 172 | 192|

现在请你编写一个保龄球实时计分程序，用来计算和显示某轮结束后的得分情况。若某轮的得分暂时无法算出，则**不显示**该轮得分（不输出）。

inputFormat:
仅有一行，为前若干轮滚球的情况，每轮滚球用一到两个字符表示，每一个字符表示一次击球，字符 `/` 表示击倒当前球道上的全部的柱，否则用一个数字字符表示本次滚球击倒的当前球道上的柱的数目，两轮滚球之间用一个空格字符隔开。

如上例对应的输入文件内容为：`/ / / 72 9/ 81 8/ / 9/ / 8/`

outputFormat: 共两行，第一行为每轮得分，第二行为到当前轮为止的总得分。每个得分之间用一个空格隔开。


title: 刷题

description:
NOIP 临近了，小 A 却发现他已经不会写题了。好在现在离竞赛还有一段时间，小 A 决定从现在开始夜以继日地刷题。也就是说小 A 废寝忘食，一天二十四小时地刷题。

今天的日期（时间）是 yyyy 年 mm 月 dd 日 hh 时 MM 分，考试的时间是 yyyy2 年 mm2 月 dd2 日 hh2 时 MM2 分。这之间的所有时间小 A 都用来刷题了，那么考试之前他最多能刷多少题呢？注意哦，考虑闰年。

时间紧张小 A 只管数量不管质量。当然有的题目容易一些，有的题目难一些。根据小 A 的经验，他能一眼看出写出某一个题目需要的时间，以分钟记。

现在给出洛谷 Online Judge 的题目列表，请你挑出最多的题目使小A能在竞赛前写出来。

我们假设从远古到未来，历法的表示与现在一样。

inputFormat:
第一行一个整数 $N$，表示洛谷 Online Judge 的题目数，$N≤5000$。

接下来$N$行，每行一个整数表示刷该题需要用的时间，以分钟记（$ \le 10000$）。（这个题本身是什么并不重要，不是么？`小A`已经写过题目数为 $0$ 个）。

接下来两行依次是当前时间和竞赛时间。时间给出的格式是：`yyyy-mm-dd-hh:MM`，例如：`2007-06-23-02:00`，采用 $24$ 小时制，每天从 00:00 到 23:59，年份从 $0000$ 到 $9999$。

outputFormat: 一行，一个整数，NOIP 前最多刷的题目数。


title: 中位数

description: 给定一个长度为 $N$ 的非负整数序列 $A$，对于前奇数项求中位数。

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

第二行 $N$ 个正整数 $A_{1\dots N}$。

outputFormat: 共 $\lfloor \frac{N + 1}2\rfloor$ 行，第 $i$ 行为 $A_{1\dots 2i - 1}$ 的中位数。


title: [ZJOI2007] 棋盘制作

description:
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 $8 \times 8$ 大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。

而我们的主人公 `小Q`，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友 `小W` 决定将棋盘扩大以适应他们的新规则。

`小Q` 找到了一张由 $N \times M$ 个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。`小Q` 想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。

不过 `小Q` 还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。

于是 `小Q` 找到了即将参加全国信息学竞赛的你，你能帮助他么？

inputFormat: 包含两个整数 $N$ 和 $M$，分别表示矩形纸片的长和宽。接下来的 $N$ 行包含一个 $N\times M$ 的 $01$ 矩阵，表示这张矩形纸片的颜色（$0$ 表示白色，$1$ 表示黑色）。

outputFormat: 包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。


title: 兔八哥与猎人

description:
兔八哥躲藏在树林旁边的果园里。果园有 $M  \times  N$ 棵树，组成一个 $M$ 行 $N$ 列的矩阵，水平或垂直相邻的两棵树的距离为 $1$。兔八哥在一棵果树下。

猎人背着猎枪走进了果园，他爬上一棵果树，准备杀死兔八哥。

如果猎人与兔八哥位置的连线上没有其它的果树，猎人就可以看到兔八哥。

现己知猎人和兔八哥的位置，编写程序判断兔子所在的位置是否安全。

inputFormat: 第一行为 $n$，表示有 $n$ 组数据，每组数据的第一行为两个正整数 $a_x$ 和 $a_y$，表示猎人的位置，第二行为两个正整数 $b_x$ 和 $b_y$，表示兔八哥的位置。

outputFormat: 共有 $n$ 行，每行为 `yes` 或 `no` 表示兔八哥的位置是否安全。


title: 售货员的难题

background: **数据有更改**

description: 某乡有 $n\ (2\le n\le 20)$ 个村庄，有一个售货员，他要到各个村庄去售货，各村庄之间的路程 $s\ (0<s<1000)$ 是已知的，且 $A$ 村到 $B$ 村与 $B$ 村到 $A$ 村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 $1$，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

inputFormat:
村庄数 $n$ 和各村之间的路程（均是整数）。

第一行，第 $i+1$ 行第 $j$ 个数代表村庄 $i$ 到 $j$ 的单向路径的路程。

outputFormat: 最短的路程。


title: 安全逃离（数据有误）

background: **注意本题数据有误，请暂时不要提交**

description:
农夫`john`最近在研究如果发生重大事故，如何让农场里的奶牛逃离问题。他想要确信在紧急情况下，所有的奶牛都有一个安全逃离方案。因为在紧急情况下，奶牛们都会失去观察和判断能力，所以最近`john`一直在教奶牛们逃离的方法，他的方法很简单，就是任何时候都只向北方或东方逃离，北方是行坐标减1的方向，东方是列坐标加1的方向。奶牛们虽笨，不过这一点事关自己的生命，所以他们牢记在心，而且也一定会这么做。

当然也会出问题，奶牛们在逃离的方向上会横冲直撞，为了阻止奶牛之间互相冲撞造成伤害，`john`要求任何一个奶牛的逃离路线不能经过其它奶牛的初始位置。一个逃离方案是安全的如果它能够满足上面的要求，反之它就是不安全的。

奶牛们所在的土地（农场）被划分成了$r$行和$c$列的一个矩形地图。奶牛们都待在这个矩形中的某一个位置。

请帮助`john`确定给定的一个地图上是否存在一个安全的逃离方案。

比如，下面的两个图：

左边的例子表示了一个能够安全逃离的地图，因为没有任何一个奶牛的逃离路线上包括其他奶牛。右边的例子表示了一个不安全的地图，因为位于$(4,1)$的奶牛不论是向东逃离还是向北逃离，它的路线上都会有别的奶牛，从这个图中拿掉任意一头奶牛，这个地图都会变成安全的。

```plain
  安全     不安全
- ||||C--  C.....
- ||||C--  ^.....
- |C||C--  |.....
- CC++---  C-->C.
- ..CCC--  ......
```

`C` 表示奶牛，直线表示逃离路线。

inputFormat:
第$1$行：两个整数$r,c$，用1个空格隔开，表示矩形的行数和列数（均 $\le 50$）。

第$2$行：一个整数$n$，表示奶牛的个数（$ \le 100$）。

第$3$到$n+2$行：共$n$行，每行有$2$个整数，之间用$1$个空格隔开，分别表示这头奶牛所在的行和列。

outputFormat:
如果这块土地是安全的，输出 $0$。

如果移走任意一头奶牛这块土地还是不安全，输出 $-1$。如果移走一头奶牛就可以使这块土地安全，应从小到大输出所有符合要求的奶牛的编号，每个编号占一行。


title: [NOI2016] 网格

description:
跳蚤国王和蛐蛐国王在玩一个游戏。

他们在一个 $n$ 行 $m$ 列的网格上排兵布阵。其中的 $c$ 个格子中 $(0 \leq c \leq n\cdot m)$，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。

我们称占据的格子有公共边的两只跳蚤是相邻的。

我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻，或存在另一只跳蚤与这两只跳蚤都连通。

现在，蛐蛐国王希望，将某些（零个，一个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。

例如：图 $1$ 描述了一个 $n=4$，$m=4$，$c=2$ 的情况。

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

这种情况下蛐蛐国王可以通过将第二行第二列，和第三行第三列的两只跳蚤替换为蛐蛐，从而达成他的希望，如右图所示。并且，不存在更优的方案，但是可能存在其他替换两只跳蚤的方案。

你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成，你还需要最小化被替换的跳蚤的个数。

inputFormat:
每个输入文件包含多组数据。

输入文件的第一行只有一个整数 $T$，表示数据的组数。

接下来依次输入 $T$ 组数据，每组数据的第一行包含三个整数 $n, m, c$。

接下来 $c$ 行，每行包含两个整数 $x, y$ 表示第 $x$ 行，第 $y$ 列的格子被一个蛐蛐占据。每一组数据当中，同一个蛐蛐不会被多次描述。

outputFormat:
对于每一组数据依次输出一行答案。

如果这组数据中，蛐蛐国王的希望不能被达成，输出 $-1$。否则，输出被替换的跳蚤的个数的最小值。

hint:
### 样例解释

第一组数据就是问题描述中的例子。

对于第二组数据，可以将第二行第二列的一只跳蚤替换为蛐蛐，从而使得存在两只跳蚤不连通，并且不存在更优的方案。

对于第三组数据，最初已经存在两只跳蚤不连通，故不需要再进行替换。

对于第四组数据，由于最多只有一只跳蚤，所以无论如何替换都不能存在两只跳蚤不连通。

### 数据范围

对于全部的测试点，保证 $1 \leq T \leq 20$。我们记 $\sum c$ 为某个测试点中，其 $T$ 组输入数据的所有 $c$ 的总和。对于所有的测试点，$\sum c \leq 10^5$。

对于全部的数据，满足 $1 \leq n,m \leq 10^9$，$0 \leq c \leq n \times m$，$1 \leq x \leq n, 1 \leq y \leq m$。

每个测试点的详细数据范围见下表。表中的 $n,m,c$ 均是对于单个输入数据（而非测试点）而言的，也就是说同一个测试点下的 $T$ 组数据均满足限制条件；而 $\sum c$是对于单个测试点而言的。为了方便阅读，“测试点”一列被放到了表格的中间而不是左边。

| $n,m$ | 测试点 | $c$ |
| :----------: | :----------: | :----------: |
| $n*m\leq 4$ | $1$ | $c\leq n*m$ |
| $n*m\leq 8$ | $2$ | $c\leq n*m$ |
| $n*m\leq 15$ | $3$ | $c\leq n*m$ |
| $n*m\leq 30$ |  $4$| $c\leq n*m$ |
| $n*m\leq 100$ | $5$ | $c\leq n*m$ |
| $n*m\leq 300$ | $6$ | $c\leq n*m$ |
| $n*m\leq 10^3$ | $7$ | $c\leq n*m$ |
| $n*m\leq 2\times 10^4$ | $8$ | $c\leq 5$ |
| $n*m\leq 2\times 10^4$ | $9$ | $c\leq 15$ |
| $n*m\leq 2\times 10^4$ | $10$ | $c\leq 30$ |
| $n,m\leq 2\times 10^4,n*m\leq2\times 10^4$ | $11$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq10^5$  | $12$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq3\times 10^5$ | $13$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq10^6$ | $14$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 2\times 10^4,n*m\leq 10^9$ | $15$ | $\sum c\leq 2\times 10^4$ |
| $n,m\leq 10^5$ | $16$ | $\sum c\leq 10^5$ |
| $n,m\leq 10^9$ | $17$ | $c=0$ |
| $n,m\leq 10^9$ | $18$ | $c\leq 1$ |
| $n,m\leq 10^9$ | $19$ | $c\leq 2$ |
| $n,m\leq 10^9$ | $20$ | $c\leq 3$ |
| $n,m\leq 10^9$ | $21$ | $c\leq 10$ |
| $n,m\leq 10^9$ | $22$ | $c\leq 30$ |
| $n,m\leq 10^9$ | $23$ | $c\leq 300$ |
| $n,m\leq 10^9$ | $24$ | $\sum c\leq 2 \times 10^4$ |
| $n,m\leq 10^9$ | $25$ | $\sum c\leq   10^5$ |


title: 打砖块

description:
小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下：

在刚开始的时候，有 $n$ 行 $m$ 列的砖块，小红有 $k$ 发子弹。小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。（如图所示）

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

某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。

小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗？

inputFormat:
第一行有 $3$ 个正整数，$n,m,k$。表示开始的时候，有 $n$ 行 $m$ 列的砖块，小红有 $k$ 发子弹。

接下来有 $n$ 行，每行的格式如下：

$f_1~c_1~f_2~c_2~f_3~c_3\cdots f_m~c_m$

其中 $f_i$ 为正整数，表示这一行的第 $i$ 列的砖，在打碎以后的得分。$c_i$ 为一个字符，只有两种可能，`Y` 或者 `N`。`Y` 表示有一发奖励的子弹，`N` 表示没有。

所有的数与字符之间用一个空格隔开，行末没有多余的空格。

outputFormat: 仅一个正整数，表示最大的得分。

hint:
对于 $20\%$ 的数据，满足 $1  \le n,m  \le 5$，$1  \le k  \le 10$，所有的字符 $c$ 都为 `N`。

对于 $50\%$ 的数据，满足 $1  \le n,m  \le 200$，$1  \le k  \le 200$，所有的字符 $c$ 都为 `N`。

对于 $100\%$ 的数据，满足 $1  \le n,m  \le 200$，$1  \le k  \le 200$，字符 $c$ 可能为 `Y`。

对于 $100\%$ 的数据，所有的 $f$ 值满足 $1  \le f  \le 10000$。


title: 表达式的转换

description:
平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：`8-(3+2*6)/5+4` 可以写为：`8 3 2 6 * + 5 / - 4 +`

其计算步骤为：

```
8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9
```

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

inputFormat:
就一行，是一个中缀表达式。输入的符号中只有这些基本符号 `0123456789+-*/^()`，并且不会出现形如 `2*-3` 的格式。

表达式中的基本数字也都是一位的，不会出现形如 `12` 形式的数字。

所输入的字符串不要判错。

outputFormat: 若干个后缀表达式，第 $i + 1$ 行比第 $i$ 行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

hint:
运算的结果可能为负数，`/` 以整除运算。并且中间每一步都不会超过 $2^{31}$。字符串长度不超过 $100$。

注意乘方运算 `^` 是从右向左结合的，即 `2 ^ 2 ^ 3` 为 `2 ^ (2 ^ 3)`，后缀表达式为 `2 2 3 ^ ^`。

其他同优先级的运算是从左向右结合的，即 `4 / 2 / 2 * 2` 为 `((4 / 2) / 2) * 2`，后缀表达式为 `4 2 / 2 / 2 *`。

保证不会出现计算乘方时幂次为负数的情况，故保证一切中间结果为整数。


title: 路径计数2

description:
一个 $N \times N$ 的网格，你一开始在 $(1,1)$，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达 $(N,N)$，即右下角有多少种方法。

但是这个问题太简单了，所以现在有 $M$ 个格子上有障碍，即不能走到这 $M$ 个格子上。

inputFormat:
输入文件第 $1$ 行包含两个非负整数 $N,M$，表示了网格的边长与障碍数。

接下来 $M$ 行，每行两个不大于 $N$ 的正整数 $x, y$。表示坐标 $(x, y)$ 上有障碍不能通过，且有 $1≤x, y≤n$，且 $x, y$ 至少有一个大于 $1$，并请注意障碍坐标有可能相同。

outputFormat: 一个非负整数，为答案 $\bmod 100003$ 后的结果。


title: 【模板】排序

description: 将读入的 $N$ 个数从小到大排序后输出。

inputFormat:
第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

outputFormat: 将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。


title: 到天宫做客

description: 有一天，我做了个梦，梦见我很荣幸的接到了猪八戒的邀请，到天宫陪他吃酒。我犹豫了。天上一日，人间一年啊！当然，我是个闲人，一年之中也没有多少时日是必须在人间的，因此，我希望选一个最长的空闲时间段，使我在天上待的时间尽量长。记住，今年是 $4000$ 年。天上一天也是 $24$ 小时，每小时 $60$ 分，每分 $60$ 秒。

inputFormat:
第一行是一个非负整数 $N$，表示 $4000$ 年中必须呆在人间的天数。

以下共 $N$ 行，每行两个用空格隔开的正整数，即日期（月，日），输入文件保证无错误，日期无重复。

outputFormat: 一个非负整数，即在天上的时间（四舍五入精确到 $1$ 秒）。


title: [NOIP2010 普及组] 数字统计

description:
请统计某个给定范围 $[L, R]$ 的所有整数中，数字 $2$ 出现的次数。

比如给定范围 $[2, 22]$，数字 $2$ 在数 $2$ 中出现了 $1$ 次，在数 $12$ 中出现 $1$ 次，在数 $20$ 中出现 $1$ 次，在数 $21$ 中出现 $1$ 次，在数 $22$ 中出现 $2$ 次，所以数字 $2$ 在该范围内一共出现了 $6$ 次。

inputFormat: $2$ 个正整数 $L$ 和 $R$，之间用一个空格隔开。

outputFormat: 数字 $2$ 出现的次数。

hint:
$1 ≤ L ≤R≤ 100000$。

NOIP2010 普及组 第一题


title: 驾车旅游

description:
如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表，列表中包括了所有加油站的位置及其每升的油价（如 $3.25$ 元/L）。驾车者一般都有以下的习惯：

1. 除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来；
2. 在第一个停下的加油站总是将油箱加满；
3. 在加油站加油的同时，买快餐等吃的东西花去 $20$ 元。
4. 从起始城市出发时油箱总是满的。
5. 加油站付钱总是精确到 $0.1$ 元（四舍五入）。
6. 驾车者都知道自己的汽车每升汽油能够行驶的里程数。

现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。

inputFormat:
第一行是一个实数，是从出发地到目的地的距离（单位：km）。

第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量（单位：L)；第二个实数是汽车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用（单位：元）；一个整数是 $1$ 到 $50$ 间的数，表示从出发地到目的地线路上加油站的数目。

接下来 $n$ 行都是两个实数，第一个数表示从出发地到某一个加油站的距离（单位：km）；第二个实数表示该加油站汽油的价格(单位：元)。

数据项中的每个数据都是正确的，不需判错。一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离。

outputFormat: 输出一个实数，即精确到 $0.1$ 元的最小的加油和吃饭费用。


title: 数列分段 Section I

description: 对于给定的一个长度为 $N$ 的正整数数列 $A_i$，现要将其分成**连续**的若干段，并且每段和不超过 $M$（可以等于$M$），问最少能将其分成多少段使得满足要求。

inputFormat: 第1行包含两个正整数 $N,M$，表示了数列 $A_i$ 的长度与每段和的最大值，第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，如题目所述。

outputFormat: 一个正整数，输出最少划分的段数。

hint:
对于$20\%$的数据，有$N≤10$；

对于$40\%$的数据，有$N≤1000$；

对于$100\%$的数据，有$N≤100000,M≤10^9$，$M$大于所有数的最大值，$A_i$之和不超过$10^9$。

将数列如下划分：

$[4][2 4][5 1]$

第一段和为$4$，第$2$段和为$6$，第$3$段和为$6$均满足和不超过$M=6$，并可以证明$3$是最少划分的段数。


title: 数列分段 Section II

description:
对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。

将其如下分段：

$$[4\ 2][4\ 5][1]$$

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

$$[4][2\ 4][5\ 1]$$

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

inputFormat:
第 $1$ 行包含两个正整数 $N,M$。

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

outputFormat: 一个正整数，即每段和最大值最小为多少。


title: 多边形的面积

description:
给出一个没有缺口的简单多边形，它的边是垂直或者水平的，要求计算多边形的面积。

多边形被放置在一个 $xOy$ 的笛卡尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数，因此多边形的面积也为整数。

**注意：可能存在连续的三个顶点在一条直线上的情况**。

inputFormat:
第一行给出多边形的顶点数 $n$ 。

接下来 $n$ 行，每行给出多边形一个顶点的坐标值 $x$ 和 $y$，用空格隔开。

顶点按逆时针方向逐个给出。多边形最后是靠从最后一个顶点到第一个顶点画一条边来封闭的。

outputFormat: 一行，一个整数，表示多边形的面积。


title: 高手之在一起

background: 高手是可以复活的，这点我们大家都知道。

description:
高手列出了一个详尽的日程表，这次他要追求的则是一个心灵纯洁的小萝莉。他和她都是要上课的，但是也会有时间空闲，于是高手决定无时无刻都要跟着她。为了她，高手决定转学到一年级。

现在高手已经花重金买下了她的日程表，每一天都会有她的行踪。现在列出了高手方便去的地方。其中方便去的地方可以去无限次，不方便去的地方不能去。

一共有 $n$ 个方便去的地点，$m$ 天。高手想知道他在这 $m$ 天中，最多能和她在一起多久。不方便去的地方是不会列出的。

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

接下来 $n$ 行，每行一个地名，高手方便去的地方。

接下来 $m$ 行，每行一个地名，她这一天在的地方。

**地名中可能有空格。**

outputFormat: 一个整数，他们在同一个地方的天数。


title: 绘制二叉树

description:
二叉树是一种基本的数据结构，它要么为空，要么由根结点，左子树和右子树组成，同时左子树和右子树也分别是二叉树。

当一颗二叉树高度为 $m-1$ 时，共有 $m$ 层。若一棵二叉树除第 $m$ 层外，其他各层的结点数都达到最大，且叶子结点都在第 $m$ 层时，则其为一棵满二叉树。

现在，需要你用程序来绘制一棵二叉树，它由一棵满二叉树去掉若干结点而成。对于一棵满二叉树，我们需要按照以下要求绘制：

1. 结点用小写字母 `o` 表示，对于一个父亲结点，用 `/` 连接左子树，用 `\` 连接右子树。

2. 定义 $[i,j]$ 为位于第 $i$ 行第 $j$ 列的某个字符。若 $[i,j]$ 为 `/` ，那么 $[i-1,j+1]$ 与 $[i+1,j-1]$ 要么为 `o` ，要么为 `/`。若 $[i,j]$ 为 `\` ，那么 $[i-1,j-1]$ 与 $[i+1,j+1]$ 要么为 `o`，要么为 `\` 。同样，若 $[i,j]$ 为第 $1\sim m-1$ 层的某个结点 `o` ，那么 $[i+1,j-1]$ 为 `/`，$[i+1,j+1]$ 为 `\`。

3. 对于第 $m$ 层结点也就是叶子结点点，若两个属于同一个父亲，那么它们之间由 $3$ 个空格隔开；若两个结点相邻但不属于同一个父亲，那么它们之间由 $1$ 个空格隔开。第 $m$ 层左数第 $1$ 个结点之前没有空格。

最后需要在一棵绘制好的满二叉树上删除 $n$ 个结点（包括这个结点的左右子树，以及与父亲的连接），原有的字符用空格替换（空格为 `ASCII 32`，若输出 `ASCII 0` 会被算作错误答案）。

inputFormat:
第 $1$ 行包含 $2$ 个正整数 $m$ 和 $n$，为需要绘制的二叉树层数和需要删除的结点数。

接下来 $n$ 行，每行两个正整数，表示删除第 $i$ 层的第 $j$ 个结点。

outputFormat: 按照题目要求绘制的二叉树。


title: 玛丽卡

description:
麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。

因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。

在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。

麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。

玛丽卡将只从不堵车的路上通过，并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间，这样他就能保证他的女朋友离开该城市足够远。

编写程序，帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间（用分钟表示）。

inputFormat:
第一行有两个用空格隔开的数 $N$ 和 $M$，分别表示城市的数量以及城市间道路的数量。$1 \le N \le 1000$，$1 \le M \le N \times (N - 1)/2$。城市用数字 $1 \sim N$ 标识，麦克在城市 $1$ 中，玛丽卡在城市 $N$ 中。

接下来的 $M$ 行中每行包含三个用空格隔开的数 $A,B,V$。其中 $1 \le A, B \le N$，$1 \le V \le 1000$。这些数字表示在 $A$ 和城市 $B$ 中间有一条双行道，并且在 $V$ 分钟内就能通过。

outputFormat: 一行，写出用分钟表示的最长时间，在这段时间中，无论哪条路在堵车，玛丽卡应该能够到达麦克处，如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，玛丽卡就不能够赶到麦克处。

hint: 感谢 Imakf 提供的三组 hack 数据。


title: 3D模型

description:
一座城市建立在规则的 $n \times m$ 网格上，并且网格均由 $1 \times 1$ 正方形构成。在每个网格上都可以有一个建筑，建筑由若干个 $1 \times 1 \times 1$ 的立方体搭建而成（也就是所有建筑的底部都在同一平面上的）。几个典型的城市模型如下图所示：

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

现在给出每个网格上建筑的高度，即每个网格上建筑由多少个立方体搭建而成，要求这个建筑模型的表面积是多少。

inputFormat:
第 $1$ 行包含 $2$ 个正整数 $n,m$，为城市模型的长与宽。

接下来 $n$ 行，每行 $m$ 个数字字符，描述了网格每个格子高度（可见所有建筑高度都大于等于 $0$ 且小于等于 $9$）。

outputFormat: 一个非负整数，为城市模型的表面积。


title: PASTE

description:
我们用文本处理器来处理一个特殊的文本文件，该文本文件共有 $N$ 行文本，每一行文本仅包含一个自然数，第一行为 $1$、第二行为 $2$，以此类推至 $N$ 行为自然数 $N$。

假设对该文本文件执行一次“剪切和粘贴”操作含义如下：首先选定连续的若干行文本，“剪切”操作将选定的文本从文件中剪下，而“粘贴”操作将剪切下来的文本插入到文件中的其他地方。

编写一个程序求出在进行了连续若干次“剪切和粘贴”操作后，文本文件中前十行的内容。

inputFormat:
第一行包含两个用空格隔开的自然数 $N$ 和 $K$，$N$ 表示文件的总行数 $(10≤N≤100,000)$，$K$ 表示“剪切和粘贴”的总次数$(1≤k≤1000)$。

下面$K$行每一行包含一次“剪切和粘贴”操作的执行信息，每行包含三个用空格隔开自然数 $A,B,C$，其中 $1≤A≤B≤N,0≤C≤N-(B-A+1)$。$A$ 和 $B$ 表示选定文本的第一行和最后一行，$C$ 表示被剪切下来的文本待插入处的前一行，如果 $C$ 等于 $0$ 则被剪切下来的的文本将被插入到文件的开头。

outputFormat: 由十行组成，其中包含所有的操作都完成后的文本文件中前十行所包含的数字。


title: SEARCH

description:
年轻的拉尔夫开玩笑地从一个小镇上偷走了一辆车，但他没想到的是那辆车属于警察局，并且车上装有用于发射车子移动路线的装置。

那个装置太旧了，以至于只能发射关于那辆车的移动路线的方向信息。

编写程序，通过使用一张小镇的地图帮助警察局找到那辆车。程序必须能表示出该车最终所有可能的位置。

小镇的地图是矩形的，上面的符号用来标明哪儿可以行车哪儿不行。$\verb!.!$ 表示小镇上那块地方是可以行车的，而符号 $\verb!X!$ 表示此处不能行车。拉尔夫所开小车的初始位置用字符的 $\verb!*!$ 表示，且汽车能从初始位置通过。

汽车能向四个方向移动：向北（向上），向南（向下），向西（向左），向东（向右）。

拉尔夫所开小车的行动路线是通过一组给定的方向来描述的。在每个给定的方向，拉尔夫驾驶小车通过小镇上一个或更多的可行车地点。

inputFormat:
输入文件的第一行包含两个用空格隔开的自然数 $R$ 和 $C$，$1\le R\le 50$，$1\le C\le 50$，分别表示小镇地图中的行数和列数。

以下的 $R$ 行中每行都包含一组 $C$ 个符号（$\verb!.!$ 或 $\verb!X!$ 或 $\verb!*!$）用来描述地图上相应的部位。

接下来的第 $R+2$ 行包含一个自然数 $N$，$1\le N\le 1000$，表示一组方向的长度。

接下来的 $N$ 行幅行包含下述单词中的任一个：`NORTH`（北）、`SOUTH`（南）、`WEST`（西）和 `EAST`（东），表示汽车移动的方向，任何两个连续的方向都不相同。

outputFormat: 用 $R$ 行表示的小镇的地图（像输入文件中一样），字符 $\verb!*!$ 应该仅用来表示汽车最终可能出现的位置。


title: [NOIP2010 普及组] 接水问题

description:
学校里有一个水房，水房里一共装有 $m$ 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 $1$。

现在有 $n$ 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 $1$ 到 $n$ 编号，$i$ 号同学的接水量为 $w_i$。接水开始时，$1$ 到 $m$ 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学 $j$ 完成其接水量要求 $w_j$ 后，下一名排队等候接水的同学 $k$ 马上接替 $j$ 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 $j$ 同学第 $x$ 秒结束时完成接水，则 $k$ 同学第 $x+1$ 秒立刻开始接水。若当前接水人数 $n'$ 不足 $m$，则只有 $n'$ 个龙头供水，其它 $m - n'$ 个龙头关闭。

现在给出 $n$ 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。

inputFormat:
第一行两个整数 $n$ 和 $m$，用一个空格隔开，分别表示接水人数和龙头个数。

第二行 $n$ 个整数 $w_1,w_2,\ldots,w_n$，每两个整数之间用一个空格隔开，$w_i$ 表示 $i$ 号同学的接水量。

outputFormat: 一个整数，表示接水所需的总时间。

hint:
【输入输出样例 \#1 说明】

第 $1$ 秒，$3$ 人接水。第 $1$ 秒结束时，$1,2,3$ 号同学每人的已接水量为 $1,3$ 号同学接完水，$4$ 号同学接替 $3$ 号同学开始接水。

第 $2$ 秒，$3$ 人接水。第 $2$ 秒结束时，$1,2$ 号同学每人的已接水量为 $2,4$ 号同学的已接水量为 $1$。

第 $3$ 秒，$3$ 人接水。第 $3$ 秒结束时，$1,2$ 号同学每人的已接水量为 $3,4$ 号同学的已接水量为 $2$。$4$ 号同学接完水，$5$ 号同学接替 $4$ 号同学开始接水。

第 $4$ 秒，$3$ 人接水。第 $4$ 秒结束时，$1,2$ 号同学每人的已接水量为 $4,5$ 号同学的已接水量为 $1$。$1,2,5$ 号同学接完水，即所有人完成接水的总接水时间为 $4$ 秒。

【数据范围】

$1 \le n \le {10}^4$，$1 \le m \le 100$，$m \le n$；

$1 \le w_i \le 100$。

NOIP2010 普及组 第二题


title: 矩形

description: 给出一个 $n \times n$ 的矩阵，矩阵中，有些格子被染成白色，有些格子被染成黑色，现要求矩阵中白色**矩形**的数量。

inputFormat:
第一行，一个整数 $n$，表示矩形的大小。

接下来 $n$ 行，每行 $n$ 个字符，这些字符为 $\verb!W!$ 或 $\verb!B!$。其中 $\verb!W!$ 表示白格，$\verb!B!$ 表示黑格。

outputFormat: 一个正整数，为白色矩形数量。


title: 台阶问题

description: 有 $N$ 级台阶，你一开始在底部，每次可以向上迈 $1\sim K$ 级台阶，问到达第 $N$ 级台阶有多少种不同方式。

inputFormat: 两个正整数 $N,K$。

outputFormat: 一个正整数 $ans\pmod{100003}$，为到达第 $N$ 级台阶的不同方式数。


title: 洛谷团队训练 VS 传统团队训练

background:
“在中学的信息学教育领域，[洛谷](/)无疑是一个相当受欢迎的辅助网站。同时有百余所学校正在通过洛谷进行信息学竞赛（以后简称 OI）的教育。洛谷之所以如此受欢迎，是因为洛谷创新的将 OI 教育的几乎每一个环节都搬到了线上，无论是学校的竞赛教练还是学生，均可以仅仅使用这一个网站来进行练习，提升自己的能力。”

——摘自《厦门中小学教育科学研究》，2015 年 2 月号。

description:
XX 中学的两位信息组的教练正在为学校信息组是否应当将洛谷作为主要的训练工具而争论不休，最后决定采取一个量化的办法来决定是否迁移。

该中学的原来训练方法是，在机房的教师机里面用 cena 装载好测试数据，装载数据所需要 $T_a$ 时间，每一道题目都要装载。学生写好代码后，可以跑到教师机上收取程序并进行评测。但由于需要往返的路程，因此每跑一次就要浪费 $T_b$ 时间。所以也允许学生在自己的机子上装载好测试数据，可以根据自己的需要选择装载的题目，这需要花费和在教师机装载数据一样的时间 $T_a$，但是每次评测花费的时间就减少为 $T_c$。此外，该中学可能会用 Excel 记录各位同学的训练情况，如果某位同学的某道题的得分高于表格里的记录，那就会花费 $T_d$ 时间将这个成绩更新，否则就不必费那个事了，如果之前没有提交过这道题视为表格记录的程序为 $0$ 分。

而在洛谷中，只需要将题目和测试数据上传到洛谷，花费 $T_a$ 时间。每次评测学生只需花费 $T_c$ 时间即可。记录成绩？那是洛谷的事儿，一提交完就帮你整理好了表格根本不费时间。

看起来可以省下不少时间吧。。然而，支持传统训练方法的教练认为，洛谷并非 $100 \%$ 的稳定，在有的情况会无法提供服务，因此首先要将洛谷的耗时除以它的可用度（一个小于 $100\%$ 的数字 $A\%$）并去掉小数点。又因为传统观念不易纠正，总是有不信任将题目数据交给洛谷这样的想法（kkksc03：怪我咯？），因此使用洛谷的耗时还要再加上一个罚时 $H$ 以做公平比较。

现在给出该中学的训练情况，希望你帮两位教练分析一下到底该如何选择。

inputFormat:
第一行，两个整数 $N, M$，代表题目数量与学生数量。

第二行，$N$ 个整数 $P_1, P_2, \ldots, P_N$，为涉及的题目编号。

第三行，$M$ 个整数 $S_1, S_2, \ldots, S_M$，为学生的学号。

第四行，七个整数 $T_a, T_b, T_c, T_d, A, H, E$，前六个数字的意义见题目描述，$E$ 如果是 $1$ 那么在 Excel 中记录成绩，如果是 $0$ 则不记录。

第五行，一个整数 $R$，代表评测数量。

接下来 $R$ 行，评测记录，每行是 $\mathit{Pr}_i, \mathit{Sr}_i, \mathit{Sc}_i$，分别为该次评测的题目号、学号以及成绩。

outputFormat:
三行。

第一行为传统方法的的耗时。

第二行为使用洛谷包括罚时在内的耗时。

第三行是结论，如果使用洛谷的时间小于传统方法的时间，那么输出 `Use Luogu!`。否则输出 `Forget it...`。

hint:
**【样例解释 #1】**

使用传统方法的话，装载 $4$ 道题目需要 $4 \times 50=200$，$2$ 号同学和 $7$ 号同学用教师机需要时分别 $30 \times 3=90$、$30 \times 4 = 120$，但是明显自己装载 cena 只需要 $50+10 \times 3=80$、$50+10 \times 4=90$ 更优。而 $3,5$ 同学则使用教师机就好，耗时 $60,30$。$2$ 号同学的前两次评测单调递增，所以额外花费 $2 \times 5=10$ 时间记录，$3$ 号同学太弱了都是 $0$ 分所以没必要记录了，$5$ 与 $7$ 各耗费 $5$ 时间。所以这种情况总时间耗时为 $200+80+90+60+30+10+5+5=480$。

使用洛谷的话，装载题目耗费 $200$，$10$ 次评测共耗费 $10 \times10=100$，考虑稳定性时间为 $(200+100) / 93\% = 322$，所以最后总耗时为 $322+50=372$，所以决定使用洛谷。

**【数据范围】**

其中 $50\%$ 数据中，不需要进行成绩的 Excel 记录。

其中 $50\%$ 数据中，题目编号和学号均大于等于 $0$，小于等于 $1000$。

（这两种情况，可能会重叠）

对于 $100\%$ 的数据，保证 $1 \le n,m \le 1000$，$1 \le T_a, T_b, T_c,T_d,H \le 10000$，$1 \le R < 100000$，$0 \le \mathit{Sc}_i \le 100$，$1 \le A \le 100$，学号和题目号在 ${10}^8$ 之内。

实际上，根据超级监控颁发的证书，洛谷 2015 年第一季度可靠性（SLA）为 $99.36 \%$。同时观念也是可以改变的。

洛谷的优点很多都是不能量化的，其精华在于社区。和全国的 OIer 一起学习交流，不很好吗？

最后插一句，去年的【榨取 kkksc03】的布告依然有效，详情。


title: 买礼物

description:
又到了一年一度的明明生日了，明明想要买 $B$ 样东西，巧的是，这 $B$ 样东西价格都是 $A$ 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 $I$ 样东西，再买第 $J$ 样，那么就可以只花 $K_{I,J}$ 元，更巧的是，$K_{I,J}$ 竟然等于 $K_{J,I}$。

现在明明想知道，他最少要花多少钱。

inputFormat:
第一行两个整数，$A,B$。

接下来 $B$ 行，每行 $B$ 个数，第 $I$ 行第 $J$ 个为 $K_{I,J}$。

我们保证 $K_{I,J}=K_{J,I}$ 并且 $K_{I,I}=0$。

特别的，如果 $K_{I,J}=0$，那么表示这两样东西之间不会导致优惠。

注意 $K_{I,J}$ **可能大于** $A$。

outputFormat: 一个整数，为最小要花的钱数。

hint:
样例解释 $2$。

先买第 $2$ 样东西，花费 $3$ 元，接下来因为优惠，买 $1,3$ 样都只要 $2$ 元，共 $7$ 元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 $4$ 元买剩下那件，而选择用 $2$ 元。）

数据规模

对于 $30\%$ 的数据，$1\le B\le 10$。

对于 $100\%$ 的数据，$1\le B\le500,0\le A,K_{I,J}\le1000$。

2018.7.25新添数据一组


title: 口袋的天空

background:
小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

description:
给你云朵的个数 $N$，再给你 $M$ 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 $K$ 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

inputFormat:
第一行有三个数 $N,M,K$。

接下来 $M$ 行每行三个数 $X,Y,L$，表示 $X$ 云和 $Y$ 云可以通过 $L$ 的代价连在一起。

outputFormat:
对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 $K$ 个棉花糖，请输出 `No Answer`。


title: [NOI2002] 银河英雄传说

background:
公元 $5801$ 年，地球居民迁至金牛座 $\alpha$ 第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历 $799$ 年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

description:
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 $30000$ 列，每列依次编号为 $1, 2,\ldots ,30000$。之后，他把自己的战舰也依次编号为 $1, 2, \ldots , 30000$，让第 $i$ 号战舰处于第 $i$ 列，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为 `M i j`，含义为第 $i$ 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 $j$ 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：`C i j`。该指令意思是，询问电脑，杨威利的第 $i$ 号战舰与第 $j$ 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

inputFormat:
第一行有一个整数 $T$（$1 \le T \le 5 \times 10^5$），表示总共有 $T$ 条指令。

以下有 $T$ 行，每行有一条指令。指令有两种格式：

1. `M i j`：$i$ 和 $j$ 是两个整数（$1 \le i,j \le 30000$），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第 $i$ 号战舰与第 $j$ 号战舰不在同一列。

2. `C i j`：$i$ 和 $j$ 是两个整数（$1 \le i,j \le 30000$），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

outputFormat:
依次对输入的每一条指令进行分析和处理：

- 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息。
- 如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 $i$ 号战舰与第 $j$ 号战舰之间布置的战舰数目。如果第 $i$ 号战舰与第 $j$ 号战舰当前不在同一列上，则输出 $-1$。

hint:
### 样例解释

战舰位置图：表格中阿拉伯数字表示战舰编号。

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

题目中没有强制 $i \neq j$，但是实测数据中不存在 $i = j$ 的情况。


title: [JSOI2008] 星球大战

description:
很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。

某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

inputFormat:
输入文件第一行包含两个整数，$n,m$，分别表示星球的数目和以太隧道的数目。星球用 $0 \sim n-1$ 的整数编号。

接下来的 $m$ 行，每行包括两个整数 $x,y$，表示星球 $x$ 和星球 $y$ 之间有 “以太” 隧道，可以直接通讯。

接下来的一行为一个整数 $k$ ，表示将遭受攻击的星球的数目。

接下来的 $k$ 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这 $k$ 个数互不相同，且都在 $0$ 到 $n-1$ 的范围内。

outputFormat: 第一行是开始时星球的连通块个数。接下来的 $k$ 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

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

[JSOI2008]


title: [JSOI2008] 最大数

description:
现在请求你维护一个数列，要求提供以下两种操作：

1.  查询操作。

语法：`Q L`

功能：查询当前数列中末尾 $L$ 个数中的最大的数，并输出这个数的值。

限制：$L$ 不超过当前数列的长度。$(L > 0)$

2. 插入操作。

语法：`A n`

功能：将 $n$ 加上 $t$，其中 $t$ 是最近一次查询操作的答案（如果还未执行过查询操作，则 $t=0$），并将所得结果对一个固定的常数 $D$ 取模，将所得答案插入到数列的末尾。

限制：$n$ 是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

inputFormat:
第一行两个整数，$M$ 和 $D$，其中 $M$ 表示操作的个数，$D$ 如上文中所述。

接下来的 $M$ 行，每行一个字符串，描述一个具体的操作。语法如上文所述。

outputFormat: 对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

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

对于全部的测试点，保证 $1 \leq M \leq 2 \times 10^5$，$1 \leq D \leq 2 \times 10^9$。


title: [NOIP2010 普及组] 三国游戏

description:
小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。

在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有 $N$ 位武将（$N$ 为偶数且不小于 $4$），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。

游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵 $\to$ 计算机 $\to$ 小涵 $\to\dots$ ”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。

已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己的军队。 下面举例说明计算机的选将策略，例如，游戏中一共有$6$个武将，他们相互之间的默契值如下表所示：

| 武将编号 |  1   |  2   |  3   |  4   |  5   |  6   |
| :------: | :--: | :--: | :--: | :--: | :--: | :--: |
|  **1**   |      | $5$  | $28$ | $16$ | $29$ | $27$ |
|  **2**   | $5$  |      | $23$ | $3$  | $20$ | $1$  |
|  **3**   | $28$ | $23$ |      | $8$  | $32$ | $26$ |
|  **4**   | $16$ | $3$  | $8$  |      | $33$ | $11$ |
|  **5**   | $29$ | $20$ | $32$ | $33$ |      | $12$ |
|  **6**   | $27$ | $1$  | $26$ | $11$ | $12$ |      |

双方选将过程如下所示：

|        | 小涵 | 轮到计算机时可选的自由武将 |  计算机    |  计算机选将说明    |
| :----: | :--: | :----------: | :--: | :--: |
| 第一轮 | $5$ | $1,2,3,4,6$ | $\color{magenta}4$ | 小涵手中的 $5$ 号武将与 $4$ 号的默契值最高，所以计算机选择 $4$ 号。 |
| 第二轮 | $5,3$ | $1,2,6$ | $4,\color{magenta}1$ |  小涵手中的 $5$ 号和 $3$ 号武将与自由武将中配对可产生的最大默契值为 $29$，是由 $5$ 号与 $1$ 号配对产生的，所以计算机选择 $1$ 号。  |
| 第三轮 | $5,3,6$ | $2$ | $4,1,\color{magenta}2$ |      |

小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？

假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。

inputFormat:
共 $N$ 行。

第一行为一个偶数 $N$，表示武将的个数。

第 $2$ 行到第 $N$ 行里，第 $i+1$ 行有 $N-i$ 个非负整数，每两个数之间用一个空格隔开，表示 $i$ 号武将和 $i+1,i+2,\dots,N $ 号武将之间的默契值（$0≤\text{默契值}\le10^9$）。

outputFormat:
共一或二行。

若对于给定的游戏输入，存在可以让小涵获胜的选将顺序，则输出 $ 1$，并另起一行输出所有获胜的情况中，小涵最终选出的武将组合的最大默契值。如果不存在可以让小涵获胜的选将顺序，则输出 $0$。

hint:
**数据范围**

对于 $ 40\%$ 的数据有 $N≤10$。

对于 $ 70\%$ 的数据有 $ N≤18$。

对于 $100\%$ 的数据有 $4\le N≤500$。保证对于不同的武将组合，其默契值均不相同。

NOIP2010 普及组 第四题


title: [USACO1.1] 你的飞碟在这儿 Your Ride Is Here

description:
众所周知，在每一个彗星后都有一只 UFO。这些 UFO 时常来收集地球上的忠诚支持者。不幸的是，他们的飞碟每次出行都只能带上一组支持者。因此，他们要用一种聪明的方案让这些小组提前知道谁会被彗星带走。他们为每个彗星起了一个名字，通过这些名字来决定这个小组是不是被带走的那个特定的小组（你认为是谁给这些彗星取的名字呢？）。关于如何搭配的细节会在下面告诉你；你的任务是写一个程序，通过小组名和彗星名来决定这个小组是否能被那颗彗星后面的 UFO 带走。

小组名和彗星名都以下列方式转换成一个数字：最终的数字就是名字中所有字母的积，其中 $\texttt A$ 是 $1$，$\texttt Z$ 是 $26$。例如，$\texttt{USACO}$ 小组就是 $21 \times 19 \times 1 \times 3 \times 15=17955$。如果小组的数字 $\bmod 47$ 等于彗星的数字 $\bmod 47$,你就得告诉这个小组需要准备好被带走！（记住“$a \bmod b$”是 $a$ 除以 $b$ 的余数，例如 $34 \bmod 10$ 等于 $4$）

写出一个程序，读入彗星名和小组名并算出用上面的方案能否将两个名字搭配起来，如果能搭配，就输出 `GO`，否则输出 `STAY`。小组名和彗星名均是没有空格或标点的一串大写字母（不超过 $6$ 个字母）。

inputFormat:
第1行：一个长度为 $1$ 到 $6$ 的大写字母串，表示彗星的名字。

第2行：一个长度为 $1$ 到 $6$ 的大写字母串，表示队伍的名字。

hint:
题目翻译来自 NOCOW。

USACO Training Section 1.1


title: [USACO1.1] 贪婪的送礼者Greedy Gift Givers

description:
对于一群 $n$ 个要互送礼物的朋友，GY 要确定每个人送出的钱比收到的多多少。在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。

然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。

给出一群朋友，没有人的名字会长于 $14$ 字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的比送出的钱多的数目。

inputFormat:
第一行一个正整数 $n$，表示人数。
接下来 $n$ 行，每行一个字符串表示人名。

接下来有 $n$ 段内容，对于每一段：
第一行是将会送出礼物人的名字。
第二行包含二个非负整数，第一个是原有的钱的数目 ( $\in [0,2000]$ )，第二个 $g_i$ 是将收到这个人礼物的人的个数 如果 $g_i \neq 0$, 在下面 $g_i$ 行列出礼物的接受者的名字，一个名字一行。

outputFormat:
输出共 $n$ 行，每行输出一个人的名字和该人收到的钱比送出的钱多的数目。名字的顺序应该与输入第 $ 2 $ 行至 $ n+1 $ 行的顺序相同。

送出的钱永远是整数，即假设送礼人一次向 $ m $ 人送出 $ n $ 元，每个人应该得到 $ \lfloor n/m
\rfloor $ 元。剩余未送出的钱应返还给送礼者。

samples:
5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0

samples:
dave 302
laura 66
owen -359
vick 141
amr -150

hint:
【数据范围】
$1\le n \le 10$

题目翻译来自NOCOW。

USACO Training Section 1.1


title: [USACO1.1] 黑色星期五Friday the Thirteenth

description:
$13$ 号又是一个星期五，那么 $13$号在星期五比在其他日子少吗？

为了回答这个问题，写一个程序，要求计算每个月的十三号落在周一到周日的次数。给出 $n$ 年的一个周期，要求计算 $1900$ 年 $1$ 月 $1$ 日至 $1900+n-1$ 年 $12$ 月 $31$ 日中十三号落在周一到周日的次数。

这里有一些你要知道的:

1. $1900$ 年 $1$ 月 $1$ 日是星期一。
2. $4,6,11$ 和 $9$ 月有 $30$ 天，其他月份除了 $2$ 月都有 $31$ 天，闰年 $2$ 月有 $29$ 天，平年 $2$ 月有 $28$ 天。
3. 年份可以被 $4$ 整除的为闰年（$1992=4\times 498$ 所以 $1992$ 年是闰年，但是 $1990$ 年不是闰年）。
4. 以上规则不适合于世纪年。可以被 $400$ 整除的世纪年为闰年，否则为平年。所以，$1700,1800,1900,2100$ 年是平年，而 $2000$ 年是闰年。

inputFormat: 一个正整数 $n$。

outputFormat: 依次输出周六、日、一、二、三、四、五在 $13$ 日出现的次数。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 400$。

题目翻译来自NOCOW。

USACO Training Section 1.1


title: [USACO1.1] 坏掉的项链 Broken Necklace

description:
你有一条由 $n$ 个红色的，白色的，或蓝色的珠子组成的项链，珠子是随意安排的。 这里是 $n=29$ 的两个例子:

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

第一和第二个珠子在图片中已经被作记号。

图片 A 中的项链可以用下面的字符串表示：

`brbrrrbbbrrrrrbrrbbrbbbbrrrrb`

假如你要在一些点打破项链，展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大数目的珠子。

例如，在图片 A 中的项链中，在珠子 $9$ 和珠子 $10$ 或珠子 $24$ 和珠子 $25$ 之间打断项链可以收集到 $8$ 个珠子。

白色珠子什么意思?

在一些项链中还包括白色的珠子(如图片B) 所示。

当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。

表现含有白珠项链的字符串将会包括三个符号 `r`，`b`，`w` 。

写一个程序来确定从一条被给出的项链可以收集到的珠子最大数目。

inputFormat:
第一行一个正整数 $n$ ，表示珠子数目。
第二行一串长度为 $n$ 的字符串, 每个字符是 `r` ， `b` 或 `w`。

outputFormat: 输出一行一个整数，表示从给出的项链中可以收集到的珠子的最大数量。

hint:
【数据范围】
对于 $100\%$ 的数据，$3\le n \le 350$

题目翻译来自NOCOW。

USACO Training Section 1.1


title: [USACO1.2] 挤牛奶Milking Cows

description:
三个农民每天清晨 $5$ 点起床，然后去牛棚给三头牛挤奶。

第一个农民在 $300$ 秒 (从 $5$ 点开始计时) 给他的牛挤奶，一直到 $1000$ 秒。第二个农民在 $700$ 秒开始，在 $1200$ 秒结束。第三个农民在 $1500$ 秒开始，$2100$ 秒结束。

期间最长的至少有一个农民在挤奶的连续时间为 $900$ 秒 (从 $300$ 秒到 $1200$ 秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为 $300$ 秒 (从 $1200$ 秒到 $1500$ 秒)。
****

你的任务是编一个程序，读入一个有 $n$ 个农民挤 $n$ 头牛的工作时间列表，计算以下两点(均以秒为单位):

最长至少有一人在挤奶的时间段。

最长的无人挤奶的时间段。（从有人挤奶开始算起）

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

接下来 $n$ 行，每行两个非负整数 $l,r$，表示一个农民的开始时刻与结束时刻。

outputFormat: 一行，两个整数，即题目所要求的两个答案。

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

题目翻译来自NOCOW。

USACO Training Section 1.2


title: [USACO1.2] 方块转换 Transformations

description:
一块 $n \times n$ 正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

- 转 $90\degree$：图案按顺时针转 $90\degree$。

- 转 $180\degree$：图案按顺时针转 $180\degree$。

- 转 $270\degree$：图案按顺时针转 $270\degree$。

- 反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。

- 组合：图案在水平方向翻转，然后再按照 $1 \sim 3$ 之间的一种再次转换。

- 不改变：原图案不改变。

- 无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个。

只使用上述 $7$ 个中的一个步骤来完成这次转换。

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

然后 $n$ 行，每行 $n$ 个字符，全部为 `@` 或 `-`，表示初始的正方形。

接下来 $n$ 行，每行 $n$ 个字符，全部为 `@` 或 `-`，表示最终的正方形。

outputFormat: 单独的一行包括 $1 \sim 7$ 之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10$。

题目翻译来自 NOCOW。

USACO Training Section 1.2


title: [USACO1.2] 回文平方数 Palindromic Squares

description:
回文数是指从左向右念和从右向左念都一样的数。如 $12321$ 就是一个典型的回文数。

给定一个用十进制表示的正整数 $B$，输出所有 $[1,300]$ 中，它的平方用 $B$ 进制表示时是回文数的数。

inputFormat: 共一行，一个单独的正整数 $B$。

outputFormat:
每行两个 $B$ 进制的符合要求的数字，第二个数是第一个数的平方，且第二个数是回文数。

注意大于 $9$ 的数，用字母表示。如用 `A` 表示 $10$，`B` 表示 $11$，用第 $n$ 个大写字母表示 $n+9$。

hint:
【数据范围】
对于 $100\%$ 的数据，$2 \le B \le 20$

题目翻译来自NOCOW。

USACO Training Section 1.2


title: [USACO1.2] 双重回文数 Dual Palindromes

background:
如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做“回文数”。例如，$12321$ 就是一个回文数，而 $77778$ 就不是。当然，回文数的首和尾都应是非零的，因此 $0220$ 就不是回文数。

事实上，有一些数（如 $21$ ），在十进制时不是回文数，但在其它进制（如二进制时为 $10101$ ）时就是回文数。

description:
给定两个十进制数 $n,s$，然后找出前 $n$ 个满足大于 $s$ 且在不少于两种进制（二进制至十进制）上是回文数的十进制数，输出到文件上。

本问题的解决方案不需要使用大于 $32$ 位的整型数

inputFormat: 只有一行，用空格隔开的两个正整数 $n,s$。

outputFormat: $n$ 行, 每行一个满足上述要求的数，并按从小到大的顺序输出。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 15$，$1\le s \le 9999$

题目翻译来自NOCOW。

USACO Training Section 1.2


title: [USACO1.3] 混合牛奶 Mixing Milk

description:
由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。

Marry 乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格可能相同。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。

给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。

注：每天所有奶农的总产量大于 Marry 乳业的需求量。

inputFormat:
第一行二个整数 $n,m$，表示需要牛奶的总量，和提供牛奶的农民个数。

接下来 $m$ 行，每行两个整数 $p_i,a_i$，表示第 $i$ 个农民牛奶的单价，和农民 $i$ 一天最多能卖出的牛奶量。

outputFormat: 单独的一行包含单独的一个整数，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。

hint:
【数据范围】
对于 $100\%$ 的数据：
$0 \le n,a_i \le 2 \times 10^6$，$0\le m \le 5000$，$0 \le p_i \le 1000$

题目翻译来自 NOCOW。

USACO Training Section 1.3


title: [USACO1.3] 修理牛棚 Barn Repair

description:
在一个月黑风高的暴风雨夜，Farmer John 的牛棚的屋顶、门被吹飞了 好在许多牛正在度假，所以牛棚没有住满。

牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。

自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。 Farmer John 想将他购买的木板总长度减到最少。

给出 $m,s,c$，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。

inputFormat:
一行三个整数 $m,s,c$，意义如题目描述。
接下来 $c$ 行，每行包含一个整数，表示牛所占的牛棚的编号。

outputFormat: 输出一行一个整数，表示所需木板的最小总长度。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le m \le 50$，$1\le c \le s \le 200$。

USACO Training Section 1.3


title: [USACO1.3] 最长的回文 Calf Flac

description:
据说如果你给无限只母牛和无限台巨型便携式电脑（有非常大的键盘 ), 那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观（最棒的回文）。

在寻找回文时不用理睬那些标点符号、空格（但应该保留下来以便做为答案输出）, 只用考虑字母 ${\tt A}\sim {\tt Z}$ 和 ${\tt a}\sim {\tt z}$。要你寻找的最长的回文的文章是一个不超过 $20{,}000$ 个字符的字符串。我们将保证最长的回文不会超过 $2{,}000$ 个字符（在除去标点符号、空格之前）。

inputFormat: 输入文件不会超过 $20,000$ 字符。这个文件可能一行或多行，但是每行都不超过 $80$ 个字符（不包括最后的换行符）。

outputFormat:
输出的第一行应该包括找到的最长的回文的长度。

下一行或几行应该包括这个回文的原文（没有除去标点符号、空格），把这个回文输出到一行或多行（如果回文中包括换行符）。

如果有多个回文长度都等于最大值，输出最前面出现的那一个。

hint:
题目翻译来自NOCOW。

USACO Training Section 1.3


title: [USACO1.3] 牛式 Prime Cryptarithm

description:
下面是一个乘法竖式，如果用我们给定的那 $n$ 个数字来取代 `*`，可以使式子成立的话，我们就叫这个式子为牛式。

```cpp
          ***
    x      **
   ----------
         ***
        ***
   ----------
        ****
```

数字只能取代 `*`，当然第一位不能为 $0$，况且给定的数字里不包括 $0$。

注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积。

请计算出牛式的数量。

inputFormat:
第一行一个正整数 $n$，表示可用的数集。
第二行 $n$ 个正整数 $a_i$，表示可用的数。

outputFormat: 输出一行一个整数，表示牛式的总数。

hint:
### 样例解释

```
          222
    x      22
   ----------
         444
        444
   ----------
        4884
```

不需要别的数，严格符合上图的数位情况，可以证明没有其他情况。

不加入样例解释：做题人如果理解错题意会进入误区

比如不用填中间的数，位数没有要求 `34*2=68` 符合要求等误区。

### 数据规模
对于 $100\%$ 的数据，$1\le n \le 9$，$a_i \in [1,9] \cap \mathbb Z$ 且 $a_i$ 不重复。

题目翻译来自NOCOW。

USACO Training Section 1.4


title: [USACO1.4] 铺放矩形块 Packing Rectangles

description:
给定 $4$ 个矩形块，找出一个最小的封闭矩形将这 $4$ 个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。

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

$4$ 个矩形块中任一个矩形的边都与封闭矩形的边相平行，上图显示出了铺放 $4$ 个矩形块的 $6$ 种方案。

这 $6$ 种方案是唯一可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。

可能存在满足条件且有着同样面积的各种不同的封闭矩形，你应该输出所有这些封闭矩形的边长。

inputFormat: 共有 $4$ 行，每行两个正整数，表示每个矩形的边长。

outputFormat:
总行数为解的总数加一。

第一行是一个整数，代表封闭矩形的最小面积。
接下来的每一行都表示一个解，由 $p,q\space (p \leqslant q)$ 来表示。这些行必须根据 $p$ 的大小按升序排列，且所有行都应是不同的。

hint:
【数据范围】
对于 $100\%$ 的数据，输入的所有数在 $[1,50]$ 内。

题目翻译来自NOCOW。

USACO Training Section 1.4


title: [USACO1.4] [IOI1994]时钟 The Clocks

description:
考虑将如此安排在一个 $3 \times 3$ 行列中的九个时钟:

```plain
|-------|   |-------|   |-------|
|       |   |       |   |   |   |
|---o   |   |---o   |   |   o   |
|       |   |       |   |       |
|-------|   |-------|   |-------|
    A           B           C

|-------|   |-------|   |-------|
|       |   |       |   |       |
|   o   |   |   o   |   |   o   |
|   |   |   |   |   |   |   |   |
|-------|   |-------|   |-------|
    D           E           F

|-------|   |-------|   |-------|
|       |   |       |   |       |
|   o   |   |   o---|   |   o   |
|   |   |   |       |   |   |   |
|-------|   |-------|   |-------|
    G           H           I
```

目标要找一个最小的移动顺序将所有的指针指向 $12$ 点。下面原表格列出了 $9$ 种不同的旋转指针的方法，每一种方法都叫一次移动。
选择 $1 \sim 9$ 号移动方法，将会使在表格中对应的时钟的指针顺时针旋转
 $90$ 度。

|移动方法  | 受影响的时钟 |
| :----------: | :----------: |
| 1 | ABDE |
| 2 | ABC |
| 3 | BCEF |
| 4 | ADG |
| 5 | BDEFH |
| 6 | CFI |
| 7 | DEGH |
| 8 | GHI |
| 9 | EFHI |

例子：

```plain
9 9 12       9 12 12        9 12 12        12 12 12        12 12 12
6 6 6   5 -> 9  9  9   8 -> 9  9  9   4 -> 12  9  9   9 -> 12 12 12
6 3 6        6  6  6        9  9  9        12  9  9        12 12 12
```

**但这可能不是正确的方法，请看下文。**

inputFormat: 输入三行，每行三个正整数，表示一个时钟的初始时间，数字的含意和上面第一个例子一样。

outputFormat:
单独的一行包括一个用空格分开的将所有指针指向 $12$ 点的最短移动顺序的列表。

如果有多种方案，输出那种使其连接起来的数字最小的方案。（举例来说 $5\ 2\ 4\ 6 < 9\ 3\ 1\ 1$）。

hint:
题目翻译来自NOCOW。

USACO Training Section 1.4


title: [USACO1.4] 等差数列 Arithmetic Progressions

description:
一个等差数列是一个能表示成 $a, a+b, a+2b, \dots ,a+nb\space (n \in \mathbb N)$ 的数列。

在这个问题中 $a$ 是一个非负的整数，$b$ 是正整数。
写一个程序来找出在双平方数集合：
$$\{ x | x = p^2 + q^2 \wedge p,q \in \mathbb N \cap [0,m]\}$$
中长度为 $n$ 的等差数列。

inputFormat:
第一行一个正整数 $n$，表示要找的数列长度。
第二行一个非负整数 $m$，表示 $p,q$ 的上界。

outputFormat:
如果没有找到数列，输出 `NONE`。

如果找到了，输出一行或多行，每行由二个整数组成：$a,b$。

这些行应该以 $b$ 为第一关键字，$a$ 为第二关键字升序排序。

所求的等差数列将不会多于10,000个。

hint:
【数据范围】
对于 $100\%$ 的数据，$3 \le n \le 25$，$0 \le m \le 250$。

题目翻译来自NOCOW。

USACO Training Section 1.4


title: [USACO1.4] 母亲的牛奶 Mother's Milk

description:
农民约翰有三个容量分别是 $a,b,c$ 升的桶。

最初，$a,b$ 桶都是空的，而 $c$ 桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。

当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。

写一个程序去帮助农民找出当 $a$ 桶是空的时候，$c$ 桶中牛奶所剩量的所有可能性。

inputFormat: 单独的一行包括三个整数 $a,b,c$。

outputFormat: 只有一行，升序地列出当 $a$ 桶是空的时候，$c$ 桶牛奶所剩量的所有可能性。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le a,b,c \le 20$。

题目翻译来自NOCOW。

USACO Training Section 1.4


title: [USACO1.5] [IOI1994]数字三角形 Number Triangles

description:
观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

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

在上面的样例中，从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大权值。

inputFormat:
第一个行一个正整数 $r$ ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

outputFormat: 单独的一行,包含那个可能得到的最大的和。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le r \le 1000$，所有输入在 $[0,100]$ 范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1


title: [USACO1.5] 回文质数 Prime Palindromes

description:
因为 $151$ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 $151$ 是回文质数。

写一个程序来找出范围 $[a,b] (5 \le a < b \le 100,000,000)$（一亿）间的所有回文质数。

inputFormat: 第一行输入两个正整数 $a$ 和 $b$。

outputFormat: 输出一个回文质数的列表，一行一个。

hint:
Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为 $5$ 的回文数：

```cpp
for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

```


title: [USACO1.5] 特殊的质数肋骨 Superprime Rib

description:
农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。

农民约翰确定他卖给买方的是真正的质数肋骨，是因为从右边开始切下肋骨，每次还剩下的肋骨上的数字都组成一个质数。

举例来说：$7\ 3\ 3\ 1$ 全部肋骨上的数字 $7331$ 是质数；三根肋骨 $733$ 是质数；二根肋骨 $73$ 是质数；当然,最后一根肋骨 $7$ 也是质数。$7331$ 被叫做长度 $4$ 的特殊质数。

写一个程序对给定的肋骨的数目 $n$，求出所有的特殊质数。$1$ 不是质数。

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

outputFormat: 按顺序输出长度为 $n$ 的特殊质数,每行一个。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 8$。

题目翻译来自NOCOW。

USACO Training Section 1.5


title: [USACO1.5] 八皇后 Checker Challenge

description:
一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

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

上面的布局可以用序列 $2\ 4\ 6\ 1\ 3\ 5$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $1\ 2\ 3\ 4\ 5\ 6$

列号 $2\ 4\ 6\ 1\ 3\ 5$

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

inputFormat: 一行一个正整数 $n$，表示棋盘是 $n \times n$ 大小的。

outputFormat: 前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

hint:
【数据范围】
对于 $100\%$ 的数据，$6 \le n \le 13$。

题目翻译来自NOCOW。

USACO Training Section 1.5


title: 关路灯

description:
某一村庄在一条路线上安装了 $n$ 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。

为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为 $1m/s$，每个路灯的位置（是一个整数，即距路线起点的距离，单位：$m$）、功率（$W$），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

inputFormat:
第一行是两个数字 $n$（表示路灯的总数）和 $c$（老张所处位置的路灯号）；

接下来 $n$ 行，每行两个数据，表示第 $1$ 盏到第 $n$ 盏路灯的位置和功率。数据保证路灯位置单调递增。

outputFormat: 一个数据，即最少的功耗（单位：$J$，$1J=1W\times s$）。

hint:
### 样例解释

此时关灯顺序为 `3 4 2 1 5`。

### 数据范围

$1\le n\le50$，$1\le c\le n$，$1\le W_i \le 100$。


title: 最多因子数

background: 本题疑似错题。

description:
数学家们喜欢各种类型的有奇怪特性的数。例如，他们认为 $945$ 是一个有趣的数，因为它是第一个所有约数之和大于本身的奇数。

为了帮助他们寻找有趣的数，你将写一个程序扫描一定范围内的数，并确定在此范围内约数个数最多的那个数。不幸的是，这个数和给定的范围的都比较大，用简单的方法寻找可能需要较多的运行时间。所以请确定你的算法能在几秒内完成最大范围内的扫描。

inputFormat: 只有一行，给出扫描的范围，由下界 $L$ 和上界 $U$ 确定。满足 $2\le L\le U\le10^9$。

outputFormat: 对于给定的范围，输出该范围内约数个数 $D$ 最多的数 $P$。若有多个，则输出最小的那个。请输出 $\texttt{Between }L\texttt{ and }U\texttt{, }P\texttt{ has a maximum of }D\texttt{ divisors.}$，其中 $L,U,P,D$ 的含义同前面所述。

samples: Between 1000 and 2000, 1680 has a maximum of 40 divisors.

hint: update: 2024/6/6 加上了 6 组 hack。


title: 三角形

description:
给出平面上的 $n$ 个等腰直角三角形。每个三角形用三个整数 $x,y,m$ 描述。一个三角形的三个顶点分别是 $(x,y),(x+m,y),(x,y+m)$。

你的任务是计算这些三角形覆盖的总面积。

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

接下来 $n$ 行每行描述一个三角形，包括三个整数 $x_i,y_i,m_i$。

outputFormat: 输出文件仅包含一个实数，精确到小数点后一位，表示总面积。

hint:
样例解释：

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

数据范围：$1\le n \le 2000$，$1 \le i \le n$，$-10^7 \le x_i,y_i \le 10^7$，$1\leq m_i \le 1000$。


title: 排队接水

description: 有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

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

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$。

outputFormat: 输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

hint: $1\le n \leq 1000$，$1\le t_i \leq 10^6$，不保证 $t_i$ 不重复。


title: [NOI2013] 向量内积

description:
两个 $d$ 维向量 $A=[a_1,a_2,\ldots,a_d]$ 与 $B=[b_1,b_2,\ldots,b_d]$ 的内积为其相对应维度的权值的乘积和，即：

$$(A,B)=\sum_{i=1}^d a_ib_i=a_1b_1+a_2b_2+\ldots+a_db_d$$

现有 $n$ 个 $d$ 维向量 $x_1,\ldots,x_n$ ，小喵喵想知道是否存在两个向量的内积为 $k$ 的倍数。请帮助她解决这个问题。

inputFormat:
第一行包含 $3$ 个正整数 $n,d,k$，分别表示向量的个数，维数以及待检测的倍数。

接下来 $n$ 行每行有 $d$ 个非负整数，其中第 $i$ 行的第 $j$ 个整数表示向量 $x_i$ 的第 $j$ 维权值 $x_{i,j}$。

outputFormat:
包含两个整数，用空格隔开。

如果存在两个向量 $x_p,x_q$ 的内积为 $k$ 的整数倍，则输出两个向量的编号 $p$ 与 $q$（要求 $p<q$）。如果存在多组这样的向量组合，输出其中任意一组即可。

若不存在这样的向量组合，则输出两个 $-1$。


title: 黑白棋游戏

description: 黑白棋游戏的棋盘由 $4 \times 4$ 方格阵列构成。棋盘的每一方格中放有 $1$ 枚棋子，共有 $8$ 枚白棋子和 $8$ 枚黑棋子。这 $16$ 枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有 $1$ 条公共边的 $2$ 个方格称为相邻方格。一个方格最多可有 $4$ 个相邻方格。在玩黑白棋游戏时，每一步可将任何 $2$ 个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。

inputFormat: 输入文件共有 $8$ 行。前四行是初始游戏状态，后四行是目标游戏状态。每行 $4$ 个数分别表示该行放置的棋子颜色。“ $0$ ”表示白棋；“ $1$ ”表示黑棋。

outputFormat: 输出文件的第一行是着棋步数 $n$。接下来 $n$ 行，每行 $4$ 个数分别表示该步交换棋子的两个相邻方格的位置。例如，abcd 表示将棋盘上 $(a,b)$ 处的棋子与 $(c,d)$ 处的棋子换位。

hint: 由 @zhouyonglong 提供 SPJ


title: 【模板】快速幂

description: 给你三个整数 $a,b,p$，求 $a^b \bmod p$。

inputFormat: 输入只有一行三个整数，分别代表 $a,b,p$。

outputFormat: 输出一行一个字符串 `a^b mod p=s`，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。


title: [JSOI2008] 完美的对称

description:
在峰会期间，必须使用许多保镖保卫参加会议的各国代表。代表们除了由他自己的随身保镖保护外，组委会还指派了一些其他的特工和阻击手保护他们。为了使他们的工作卓有成效，使被保卫的人的安全尽可能得到保障，保镖被分配到被保护人的各个方向。

保镖的最佳站立位置应该是这样的：被保护人应站在所有保镖的对称中心。但是，只要被保护人一移动，保镖就很难根据要人的新位置调整位置。大多数的特工都很难对此作出实时调整。

因此，安全部长决定将该过程逆转一下，保镖先站好自己的位置，然后要人在他们的对称中心找到合适的位置。如果要人随便走动，我们就对他的安全不必负责。

你的工作是使这个过程自动操作。给出一组 $N$ 个点（保镖的位置），你要找出它们的对称中心 $S$，在这儿被保护人将相对安全。下面以此类推。

首先我们给定一点 $A$ 以及对称中心 $S$，点 $A'$ 是点 $A$ 以 $S$ 为对称中心形成的像点，即点 $S$ 是线段 $AA'$ 的对称中心。

点阵组（$X$）以 $S$ 为中心的像点是由每个点的像点组成的点阵组。$X$ 是用来产生对称中心 $S$ 的，即点阵 $X$ 以 $S$ 为中心的像点的集合即为点阵 $X$ 本身。

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

inputFormat:
输入文件第一行是一个整数 $N$，$1\le N\le 20000$，接下来的 $N$ 行每行包含用空格隔开的两个整数 $X_i$ 和 $Y_i$，$-10^5\le X_i,Y_i\le 10^5$，表示这组点阵中第 $i$ 个点的笛卡尔坐标值。

因为任何两个保镖都不会站在同一个位置上，所以在给定的作业中，任何两点都不相同。但注意保镖可以站在被保护人相同的位置。

outputFormat:
输出文件仅有一行。如果给定的点阵能产生一个对称中心，则输出 $\texttt{V.I.P.  should  stay  at (}x\texttt{,}y\texttt{).}$，其中 $x$ 和 $y$ 代表中心的笛卡尔坐标值，格式为四舍五入保留至小数点后一位。

如果该组点阵无对称中心，输出 `This is a dangerous situation!`，注意输出时除了两个单词之间用一个空格隔开外，不要输出多余空格。

hint: JSOI2008 第二轮。


title: 地毯填补问题

description:
相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：

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

并且每一方格只能用一层地毯，迷宫的大小为 $2^k\times 2^k$ 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为 $1$ 秒。

inputFormat:
输入文件共 $2$ 行。

第一行一个整数 $k$，即给定被填补迷宫的大小为 $2^k\times 2^k$（$0\lt k\leq 10$）；
第二行两个整数 $x,y$，即给出公主所在方格的坐标（$x$ 为行坐标，$y$ 为列坐标），$x$ 和 $y$ 之间有一个空格隔开。

outputFormat: 将迷宫填补完整的方案：每一补（行）为 $x\ y\ c$（$x,y$ 为毯子拐角的行坐标和列坐标，$c$ 为使用毯子的形状，具体见上面的图 $1$，毯子形状分别用 $1,2,3,4$ 表示，$x,y,c$ 之间用一个空格隔开）。

hint:
spj 报错代码解释：

1. $c$ 越界；
2. $x,y$ 越界；
3. $(x,y)$ 位置已被覆盖；
4. $(x,y)$ 位置从未被覆盖。

$\text{upd 2023.8.19}$：增加样例解释。

### 样例解释

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


title: 遍历问题

description:
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

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

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

inputFormat:
共两行，第一行表示该二叉树的前序遍历结果 $s_1$，第二行表示该二叉树的后序遍历结果 $s_2$。

保证至少存在一棵二叉树满足给出的信息，$s _ 1, s _ 2$ 中只含小写字母，且在某个字符串中不存在相同的字母。

outputFormat: 输出可能的中序遍历序列的总数，结果不超过 $2^{63}-1$。


title: 智力大冲浪

description:
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者 $m$ 元。先不要太高兴，因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则：

首先，比赛时间分为 $n$ 个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限 $t_i$ 前完成。如果一个游戏没能在规定期限前完成，则要从奖励费 $m$ 元中扣去一部分钱 $w_i$，$w_i$ 为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!

inputFormat:
第一行为 $m$，表示一开始奖励给每位参赛者的钱；

第二行为 $n$，表示有 $n$ 个小游戏；

第三行有 $n$ 个数，分别表示游戏 $1$ 到 $n$ 的规定完成期限；

第四行有 $n$ 个数，分别表示游戏 $1$ 到 $n$ 不能在规定期限前完成的扣款数。

outputFormat: 输出仅一行，表示小伟能赢取最多的钱。


title: [NOI2013] 树的计数

description:
我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同，并且它们的 BFS 序也有可能相同，例如下面两棵树的 DFS 序都是 `1 2 4 5 3`，BFS 序都是 `1 2 3 4 5`。

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

现给定一个 DFS 序和 BFS 序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有 $K$ 棵不同的有根树具有这组 DFS 序和 BFS 序，且他们的高度分别是 $h_1, h_2, \ldots, h_K$，那么请你输出：

$$
\frac{h_1+h_2+\ldots+h_K}K
$$

inputFormat:
第一行包含 $1$ 个正整数 $n$，表示树的节点个数。

第二行包含 $n$ 个正整数，是一个 $1 \ldots n$ 的排列，表示树的 DFS 序。

第三行包含 $n$ 个正整数，是一个 $1 \ldots n$ 的排列，表示树的 BFS 序。

输入保证至少存在一棵树符合给定的两个序列。

outputFormat: 输出 $1$ 个实数，四舍五入保留恰好三位小数，表示树高的平均值。

hint:
如果输出文件的答案与标准输出的差不超过 $0.001$，则将获得该测试点上的分数，否则不得分。

### 数据范围

- 对于 $20\%$ 的测试数据，满足：$n \le 10$；
- 对于 $40\%$ 的测试数据，满足：$n \le 100$；
- 对于 $85\%$ 的测试数据，满足：$n \le 2 \times 10^3$；
- 对于 $100\%$ 的测试数据，满足：$2 \le n \le 2 \times 10^5$。


title: 木棍加工

description:
一堆木头棍子共有 $n$ 根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：

- 第一根棍子的准备时间为 $1$ 分钟。
- 如果刚处理完长度为 $l$，宽度为 $w$ 的棍子，那么如果下一个棍子长度为 $l_i$，宽度为 $w_i$，并且满足 $l\ge l_i$、$w\ge w_i$，这个棍子就不需要准备时间，否则需要 $1$ 分钟的准备时间。

计算处理完 $n$ 根棍子所需要的最短准备时间。比如，你有 $5$ 根棍子，长度和宽度分别为 $(4,9),(5,2),(2,1),(3,5),(1,4)$，最短准备时间为 $2$（按 $(4,9),(3,5),(1,4),(5,2),(2,1)$ 的次序进行加工）。

inputFormat:
第一行是一个整数 $n$（$n\le5000$）。

第二行是 $2n$ 个整数，分别是 $l_1,w_1,l_2,w_2,\ldots,l_n,w_n$。$l$ 和 $w$ 的值均不超过 $10000$，相邻两数之间用空格分开。

outputFormat: 仅一行，一个整数，所需要的最短准备时间。


title: 小 A 的口头禅

description: 小 A 最近有了一个口头禅 “呵呵”，于是他给出了一个矩形，让你求出里面有几个 “$\verb!hehe!$”（方向可以是向上、向下、向左、向右的直线）。

inputFormat:
第一行两个数 $n, m$，表示这个矩形的大小。

接下来 $n$ 行，每行 $m$ 个字符，表示这个矩形。

outputFormat: 一行一个数，表示有几个 “$\verb!hehe!$”。


title: 血缘关系

description:
我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之间相同基因的数量。

妖怪之间的基因继承关系相当简单：如果妖怪 $C$ 是妖怪 $A$ 和 $B$ 的孩子，则 $C$ 的任意一个基因只能是继承 $A$ 或 $B$ 的基因，继承 $A$ 或 $B$ 的概率各占 $50\%$。所有基因可认为是相互独立的，每个基因的继承关系不受别的基因影响。

现在，我们来定义两个妖怪 $X$ 和 $Y$ 的基因相似程度。例如，有一个家族，这个家族中有两个毫无关系（没有相同基因）的妖怪 $A$ 和 $B$，及它们的孩子 $C$ 和 $D$。那么 $C$ 和 $D$ 相似程度是多少呢？因为 $C$ 和 $D$ 的基因都来自 $A$ 和 $B$，从概率来说，各占 $50\%$。所以，依概率计算 $C$ 和 $D$ 平均有 $50\%$ 的相同基因，$C$ 和 $D$ 的基因相似程度为 $50\%$。需要注意的是，如果 $A$ 和 $B$ 之间存在相同基因的话，$C$ 和 $D$ 的基因相似程度就不再是 $50\%$ 了。

你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相似程度。

inputFormat:
第一行两个整数 $n\ (2 \le n \le 300)$ 和 $k$。表示家族中成员数，它们分别用 $1,2,\cdots,n$ 来表示。$k\ (0 \le k \le n-2)$ 表示这个家族中有父母的妖怪数量（其他的妖怪没有父母，它们之间可以认为毫无关系，即没有任何相同基因）。

接下来的 $k$ 行，每行三个整数 $a,b,c$，表示妖怪 $a$ 是妖怪 $b$ 的孩子。

然后是一行一个整数 $m$（$1 \le m \le n_2$），表示需要计算基因相似程度的妖怪对数。

接下来的 $m$ 行，每行两个整数，表示需要计算基因相似程度的两个妖怪。

你可以认为这里给出的家谱总是合法的。具体来说就是，没有任何的妖怪会成为自己的祖先，并且你也不必担心会存在性别错乱问题。

outputFormat: 共 $m$ 行。可 $k$ 行表示第 $k$ 对妖怪之间的基因相似程度。你必须按百分比输出，有多少精度就输出多少，而且必须准确，但不允许出现多余的 $0$（注意，$0.001$ 的情况应输出 $\verb!0.1%!$，而不是 $\verb!.1%!$）。具体格式参见样例。


title: 算24点

description:
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算 $24$ 点”。您作为游戏者将得到 $4$ 个 $1 \sim 9$ 之间的自然数作为操作数，而您的任务是对这 $4$ 个操作数进行适当的算术运算，要求运算结果等于 $24$。

您可以使用的运算只有：$\verb!+!,\verb!-!,\verb!*!,\verb!/!$，您还可以使用 $\verb!()!$ 来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，$(2\ \times 2)/4$ 是合法的，$2\times (2/4)$ 是不合法的）。下面我们给出一个游戏的具体例子：

若给出的 $4$ 个操作数是：$1$ 、 $2$ 、 $3$ 、 $7$，则一种可能的解答是 $1+2+3\ \times 7=24$。

inputFormat: 只有一行，四个1到9之间的自然数。

outputFormat:
如果有解的话，只要输出一个解。输出的是三行数据，分别表示运算的步骤。

- 其中第一行是输入的两个数和一个运算符和运算后的结果；
- 第二行是第一行的结果和一个输入的数据、运算符、运算后的结果，或者是另外两个数的输出结果；
- 第三行是前面的结果第二行的结果或者剩下的一个数字、运算符和 $\verb!=24!$。如果两个操作数有大小的话则先输出大的。

如果没有解则输出 `No answer!`。

如果有多重合法解，输出任意一种即可。

注：所有运算结果均为正整数。

hint:
感谢 chenyy 提供 special judge

---

$\text{upd 2022.8.1}$：新增加一组 Hack 数据。


title: 冗余依赖

description:
在设计关系数据库的表格时，术语“函数依赖”（FD）被用来表示不同域之间的关系。函数依赖是描述一个集合中的域的值与另一个集合中的域的值之间的关系。记号 $X \to Y$ 被用来表示当集合 $X$ 中的域被赋值后，集合 $Y$ 的域就可以确定相应的值。例如，一个数据表格包含“社会治安编号”（$S$）、“姓名”（$N$）、“地址”（$A$）、“电话”（$P$）的域，并且每个人都与某个特定的互不相同的 $S$ 值相对应，根据域 $S$ 就可以确定域 $N$ 、 $A$ 、 $P$ 的值。这就记作 $S \to \{N,A,P\}$。

写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如，如果组里包括依赖 $A \to B$ 、 $B \to C$ 和 $A \to C$，那么第三个依赖是冗余的，因为域 $C$ 可以用前两个依赖得到（域 $A$ 确定了域 $B$ 的值，同样域 $B$ 确定了域 $C$ 的值）。在 $A \to B$ 、 $B \to C$ 、 $C \to A$ 、 $A \to C$ 、 $C \to B$ 和 $B \to A$ 中，所有的依赖都是冗余的。

现在要求你编写一个程序，从给定的依赖关系中找出冗余的。

inputFormat:
第一行是一个不超过 $100$ 的整数 $n$，它表示文件中函数依赖的个数。

从第二行起每一行是一个函数依赖且互不重复，每行包含用字符 $\verb!-!$ 和 $\verb!>!$ 隔开的非空域列表。列表月包含大写的字母，函数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如 $A \to A$）。虽然文件中没有对函数依赖编号，但其顺序就是编号 $1$ 到 $n$。

outputFormat:
每一行输出一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的。格式为 $\texttt{FD}\ x\ \texttt{is redundant using FDs:}\ p_1\ p_2 \cdots p_k$。其中 $x$ 是冗余的依赖的编号，$p_1,p_2,\cdots,p_k$ 是用来证明 $x$ 是冗余依赖的依赖序列。

如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。

如果这些函数依赖中不包含冗余依赖，则输出 `No redundant FDs`。

samples:
6
P->RST
VRT->SQP
PS->T
Q->TR
QS->P
SR->V

samples:
FD 3 is redundant using FDs: 1
FD 5 is redundant using FDs: 4 6 2

hint:
### 样例 1 解释

依赖关系 $3$ 是冗余的。因为 $A\to C$ 可以使用前两个依赖关系 $A\to \{B,D\}$ 和 $\{B, D\}\to C$ 得到。


title: 走迷宫

description:
有一个 $m\times n$ 格的迷宫(表示有 $m$ 行、$n$ 列)，其中有可走的也有不可走的，如果用 $1$ 表示可以走，$0$ 表示不可以走，文件读入这 $m\times n$ 个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用 $-1$ 表示无路）。

优先顺序：左上右下。**数据保证随机生成。**

inputFormat: 第一行是两个数 $m,n(1<m,n<15)$，接下来是 $m$ 行 $n$ 列由 $1$ 和 $0$ 组成的数据，最后两行是起始点和结束点。

outputFormat:
所有可行的路径，描述一个点时用 $(x,y)$ 的形式，除开始点外，其他的都要用 `->` 表示方向。

如果没有一条可行的路则输出 $-1$。


title: 计数器

description: 一本书的页数为 $n$，页码从 $1$ 开始编起，请你求出全部页码中，用了多少个 $0,1,2\cdots 9$。每个页码不含前导 $0$，如 $n=1234$ 时第 $5$ 页不是 $0005$，只是 $5$。

inputFormat: 一个正整数 $n$，表示总的页码。

outputFormat: 输出共十行，其中第 $k$ 行为数字 $k-1$ 的个数。


title: 诸侯安置

description:
很久以前，有一个强大的帝国，它的国土成正方形状，如图所示。

这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地（正方形中的一格）。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图为 $n＝3$ 时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。

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

国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。  因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。

现在，给出正方形的边长 $n$，以及需要封地的诸侯数量 $k$，要求你求出所有可能的安置方案数。（满足 $n\le100$，$k\le2n^2-2n+1$）

由于方案数可能很多，你只需要输出方案数除以 $504$ 的余数即可。

inputFormat: 仅一行，两个整数 $n$ 和 $k$，中间用一空格隔开。

outputFormat: 一个整数，表示方案数除以 $504$ 的余数。

hint: 注意：镜面和旋转的情况属于不同的方案。


title: 括号序列

description:
定义如下规则：

1. 空串是「平衡括号序列」
2. 若字符串 $S$ 是「平衡括号序列」，那么 $\texttt{[}S\texttt]$ 和 $\texttt{(}S\texttt)$ 也都是「平衡括号序列」
3. 若字符串 $A$ 和 $B$ 都是「平衡括号序列」，那么 $AB$（两字符串拼接起来）也是「平衡括号序列」。

例如，下面的字符串都是平衡括号序列：

- `()`，`[]`，`(())`，`([])`，`()[]`，`()[()]`

而以下几个则不是：

- `(`，`[`，`]`，`)(`，`())`，`([()`

现在，给定一个仅由 `(`，`)`，`[`，`]`构成的字符串 $s$，请你按照如下的方式给字符串中每个字符配对：
1. 从左到右扫描整个字符串。
2. 对于当前的字符，如果它是一个右括号，考察它与它左侧离它**最近**的**未匹配**的的左括号。如果该括号与之对应（即小括号匹配小括号，中括号匹配中括号），则将二者配对。如果左侧未匹配的左括号不存在或与之不对应，则其配对失败。

配对结束后，对于 $s$ 中全部未配对的括号，请你在其旁边添加一个字符，使得该括号和新加的括号匹配。

inputFormat: 输入只有一行一个字符串，表示 $s$。

outputFormat: 输出一行一个字符串表示你的答案。

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

对于全部的测试点，保证 $s$ 的长度不超过 $100$，且只含  `(`，`)`，`[`，`]` 四种字符。


title: 新汉诺塔

description:
设有 $n$ 个大小不等的中空圆盘，按从小到大的顺序从 $1$ 到 $n$ 编号。将这 $n$ 个圆盘任意的迭套在三根立柱上，立柱的编号分别为 $A,B,C$，这个状态称为初始状态。

现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。

移动时有如下要求：

- 一次只能移一个盘；
- 不允许把大盘移到小盘上面。

inputFormat:
第一行一个整数，状态中圆盘总数 $n$。

接下来三行每行若干个整数，分别代表初始状态下 $A$ , $B$ , $C$ 柱子上的圆盘从上到下的编号，如果只有一个数 $0$ 就代表这根柱子上没有数。

接下来三行每行若干个整数，分别代表目标状态下 $A$ , $B$ , $C$ 柱子上的圆盘从上到下的编号，如果只有一个数 $0$ 就代表这根柱子上没有数。

outputFormat:
若干行每行一个字符串，格式为 `move I from P to Q` ，代表一个移动的操作。

接下来一行一个整数，代表从初始状态到目标状态的最少步数。

samples:
move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to B
move 2 from C to A
move 1 from B to C
7

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

对于 $100\%$ 的数据，$1 \le n \le 45$ ，$1 \le $ 每个圆盘的编号 $\le n$ 。

每行的圆盘描述是从下到上的圆盘编号。


title: 排序集合

description:
对于集合 $N=\{1,2,\cdots,n\}$ 的子集，定义一个称之为“小于”的关系：

设 $S1=\{X_1,X_2,\cdots,X_i\}$，$(X_1<X_2<\cdots<X_i)$，$S2=\{Y_1,Y_2,\cdots,Y_j\}$，$(Y_1<Y_2<\cdots<Y_j)$，如果存在一个 $k$，$(0\leq k\leq\min(i,j))$，使得 $X_1=Y_1,\cdots,X_k=Y_k$，且 $k=i$ 或 $X_{k+1}<Y_{k+1}$，则称 $S1$ “小于” $S2$。

你的任务是，对于任意的 $n(n\leq31)$ 及 $k(k<2^n)$，求出第 $k$ 小的子集。

inputFormat: 输入文件仅一行，包含两个用空格隔开的自然数，$n$ 和 $k$。

outputFormat: 输出文件仅一行，使该子集的元素，由小到大排列。空集输出 $0$。


title: [NOI2000] 青蛙过河

description:
**大小各不相同**的一队青蛙站在河左岸的石墩（记为 A）上，要过到对岸的石墩（记为 D）上去。河心有几片荷叶（分别记为 $Y_1 \dots Y_m$）和几个石墩（分别记为 $S_1\dots S_n$）。图示如下：

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

青蛙的站队和移动方法规则如下：

- 每只青蛙只能站在荷叶、石墩，或者**仅比它大一号**的青蛙背上（统称为合法的落脚点）；
- 一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点；
- 青蛙允许从左岸 A 直接跳到河心的石墩、荷叶和右岸的石墩 D 上，允许从河心的石墩和荷叶跳到右岸的石墩 D 上；
- 青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动；
- 青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回；
- 假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则 1 落在比它大一号的青蛙的背上。
- 荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。
- 每一步只能移动一只青蛙，并且移动后需要满足站队规则；
- 在一开始的时候，青蛙均站在 A 上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则 6 站在比其大一号的青蛙的背上。

青蛙希望最终能够全部移动到 D 上，并完成站队。

设河心有 $m$ 片荷叶和 $n$ 个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从 A 过到 D。

你的任务是对于给出的 $n,m$，计算并输出最多能有多少只青蛙可以根据以上规则顺利过河。

inputFormat: 输入两个整数 $n,m$。

outputFormat: 一个整数，表示最多能有多少只青蛙可以根据以上规则顺利过河。


title: 电话号码

description:
电话机上每一个数字下面都写了若干个英文字母。分布如下：

- $1\leftrightarrow \verb!a!,\verb!b!,\verb!c!$；
- $2\leftrightarrow \verb!d!,\verb!e!,\verb!f!$；
- $3\leftrightarrow \verb!g!,\verb!h!,\verb!i!$；
- $4\leftrightarrow \verb!j!,\verb!k!,\verb!l!$；
- $5\leftrightarrow \verb!m!,\verb!n!$；
- $6\leftrightarrow \verb!o!,\verb!p!,\verb!q!$；
- $7\leftrightarrow \verb!r!,\verb!s!,\verb!t!$；
- $8\leftrightarrow \verb!u!,\verb!v!,\verb!w!$；
- $9\leftrightarrow \verb!x!,\verb!y!,\verb!z!$。

现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。

inputFormat:
第一行为一个正整数 $N$ 表示单词表中单词的个数 $(N≤100)$；

第二行为一个长度不超过 $100$ 的数字串，表示密码；

接下来的 $N$ 行，每行一个长度不超过 $20$ 的单词，表示单词表。

outputFormat: 仅一行，表示翻译后的原文，如果密码无法翻译，则输出 `No Solutions!`，如果密码有多种翻译方式，则输出任意一种即可。

hint: 由 @zhouyonglong 提供SPJ


title: 编码

description:
编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。

字母表中共有 $26$ 个字母 $\mathtt{a,b,c,\cdots,z}$，这些特殊的单词长度不超过 $6$ 且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。

例如：

- $\verb!a! \to 1$；
- $\verb!b! \to 2$；
- $\verb!z! \to 26$；
- $\verb!ab! \to 27$；
- $\verb!ac! \to 28$。

你的任务就是对于所给的单词，求出它的编码。

inputFormat: 仅一行，被编码的单词。

outputFormat: 仅一行，对应的编码。如果单词不在字母表中，输出 $0$。


title: 取火柴游戏

description:
输入 $k$ 及 $k$ 个整数 $n_1,n_2,\cdots,n_k$，表示有 $k$ 堆火柴棒，第 $i$ 堆火柴棒的根数为 $n_i$；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。

谁取走最后一根火柴为胜利者。

例如：$k=2$，$n_1=n_2=2$，A 代表你，P 代表计算机，若决定 A 先取：

- A：$(2,2) \rightarrow (1,2)$，即从第一堆中取一根。
- P：$(1,2) \rightarrow (1,1)$，即从第二堆中取一根。
- A：$(1,1) \rightarrow (1,0)$。
- P：$(1,0) \rightarrow (0,0)$。P 胜利。

如果决定 $A$ 后取：

- P：$(2,2) \rightarrow (2,0)$。
- A：$(2,0) \rightarrow (0,0)$。A 胜利。

又如 $k=3$，$n_1=1$，$n_2=2$，$n_3=3$，$A$ 决定后取：

- P：$(1,2,3) \rightarrow (0,2,3)$。
- A：$(0,2,3) \rightarrow (0,2,2)$。
- A 已将游戏归结为 $(2,2)$ 的情况，不管 P 如何取 A 都必胜。

编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出 `lose`。

inputFormat:
第一行，一个正整数 $k$。

第二行，$k$ 个整数 $n_1,n_2,\cdots,n_k$。

outputFormat:
如果是先取必胜，请在第一行输出两个整数 $a,b$，表示第一次从第 $b$ 堆取出 $a$ 个。第二行为第一次取火柴后的状态。如果有多种答案，则输出 $\lang b,a\rang$ 字典序最小的答案（ 即 $b$ 最小的前提下，使 $a$ 最小）。

如果是先取必败，则输出 `lose`。

hint:
### 数据范围及约定

对于全部数据，$k \le 500000$，$n_i \le 10^9$。


title: 加工生产调度

description:
某工厂收到了 $n$ 个产品的订单，这 $n$ 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。

某个产品 $i$ 在 A、B 两车间加工的时间分别为 $A_i,B_i$。怎样安排这 $n$ 个产品的加工顺序，才能使总的加工时间最短。

这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A、B 两车间加工完毕的时间。

inputFormat:
第一行仅—个整数 $n$，表示产品的数量。

接下来一行 $n$ 个整数是表示这 $n$ 个产品在 A 车间加工各自所要的时间。

最后的 $n$ 个整数是表示这 $n$ 个产品在 B 车间加工各自所要的时间。

outputFormat:
第一行一个整数，表示最少的加工时间。

第二行是一种最小加工时间的加工顺序。


title: 最大乘积

description:
一个正整数一般可以分为几个互不相同的自然数的和，如 $3=1+2$，$4=1+3$，$5＝1+4=2+3$，$6=1+5＝2+4$。

现在你的任务是将指定的正整数 $n$ 分解成若干个互不相同的自然数（也可以不分解，就是这个数字本身）的和，且使这些自然数的乘积最大。

inputFormat: 只一个正整数 $n$，（$3 \leq n \leq 10000$）。

outputFormat:
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。


title: 种树

background: 一条街的一边有几座房子，因为环保原因居民想要在路边种些树。

description:
路边的地区被分割成块，并被编号成 $1, 2, \ldots,n$。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树，并指定了三个号码 $b$，$e$，$t$。这三个数表示该居民想在地区 $b$ 和 $e$ 之间（包括 $b$ 和 $e$）种至少 $t$ 棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

inputFormat:
输入的第一行是一个整数，代表区域的个数 $n$。

输入的第二行是一个整数，代表房子个数 $h$。

第 $3$ 到第 $(h + 2)$ 行，每行三个整数，第 $(i + 2)$ 行的整数依次为 $b_i, e_i, t_i$，代表第 $i$ 个居民想在 $b_i$ 和 $e_i$ 之间种至少 $t_i$ 棵树。

outputFormat: 输出一行一个整数，代表最少的树木个数。

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

对于 $100\%$ 的数据，保证：

- $1 \leq n \leq 3 \times 10^4$，$1 \leq h \leq 5 \times 10^3$。
- $1 \leq b_i \leq e_i \leq n$，$1 \leq t_i \leq e_i - b_i + 1$。


title: 餐巾计划问题

description:
一个餐厅在相继的 $N$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾（$i = 1, 2, \dots, N$）。餐厅可以购买新的餐巾，每块餐巾的费用为 $p$ 分；或者把旧餐巾送到快洗部，洗一块需 $m$ 天，其费用为 $f$ 分；或者送到慢洗部，洗一块需 $n$ 天（$n \gt m$），其费用为 $s$ 分（$s \lt f$）。

每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $N$ 天中餐巾使用计划，使总的花费最小。编程找出一个最佳餐巾使用计划。

inputFormat:
由标准输入提供输入数据。文件第 $1$ 行有 $1$ 个正整数 $N$，代表要安排餐巾使用计划的天数。

接下来的一行是餐厅在相继的 $N$ 天里，每天需用的餐巾数。

最后一行包含 $5$ 个正整数 $p, m, f, n, s$。$p$ 是每块新餐巾的费用；$m$ 是快洗部洗一块餐巾需用天数；$f$ 是快洗部洗一块餐巾需要的费用；$n$ 是慢洗部洗一块餐巾需用天数；$s$ 是慢洗部洗一块餐巾需要的费用。

outputFormat: 将餐厅在相继的 $N$ 天里使用餐巾的最小总花费输出。

tags: 网络流与线性规划 24 题


title: 马拉松接力赛

description:
某城市冬季举办环城 $25\rm km$ 马拉松接力赛，每个代表队有 $5$ 人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑 $1\rm km$ 、最多只能跑 $10\rm km$，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。

刘老师作为学校代表队的教练，精心选择了 $5$ 名长跑能手，进行了训练和测试，得到了这 $5$ 名选手尽力连续跑 $1\rm km$、$2\rm km$、…、$10\rm km$ 的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完 $25\rm km$ 所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。

根据测试情况及一般运动员的情况得知，连续跑 $1\rm km$ 要比连续跑 $2\rm km$ 速度快，连续跑 $2\rm km$ 又要比连续跑 $3\rm km$ 速度快……也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。

inputFormat: $5$ 行数据，分别是 $1$ 到 $5$ 号队员的测试数据，每行的 $10$ 个整数，表示某一个运动员尽力连续跑 $1\rm km$ 、 $2\rm km$、…、$10\rm km$ 所用的时间。

outputFormat: 两行，第一行是最短的时间，第二行是五个数据，分别是1到5号队员各自连续跑的公里数。

hint: @Jomoo 提供了修正后的数据


title: 扶苏的问题

description:
给定一个长度为 $n$ 的序列 $a$，要求支持如下三个操作：

1. 给定区间 $[l, r]$，将区间内每个数都修改为 $x$。
2. 给定区间 $[l, r]$，将区间内每个数都加上 $x$。
3. 给定区间 $[l, r]$，求区间内的最大值。

inputFormat:
第一行是两个整数，依次表示序列的长度 $n$ 和操作的个数 $q$。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列中的第 $i$ 个数 $a_i$。
接下来 $q$ 行，每行表示一个操作。每行首先有一个整数 $op$，表示操作的类型。
- 若 $op = 1$，则接下来有三个整数 $l, r, x$，表示将区间 $[l, r]$ 内的每个数都修改为 $x$。
- 若 $op = 2$，则接下来有三个整数 $l, r, x$，表示将区间 $[l, r]$ 内的每个数都加上 $x$。
- 若 $op = 3$，则接下来有两个整数 $l, r$，表示查询区间 $[l, r]$ 内的最大值。

outputFormat: 对于每个 $op = 3$ 的操作，输出一行一个整数表示答案。

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

- 对于 $10\%$ 的数据，$n = q = 1$。
- 对于 $40\%$ 的数据，$n, q \leq 10^3$。
- 对于 $50\%$ 的数据，$0 \leq a_i, x \leq 10^4$。
- 对于 $60\%$ 的数据，$op \neq 1$。
- 对于 $90\%$ 的数据，$n, q \leq 10^5$。
- 对于 $100\%$ 的数据，$1 \leq n, q \leq 10^6$，$1 \leq l, r \leq n$，$op \in \{1, 2, 3\}$，$|a_i|, |x| \leq 10^9$。

### 提示

请注意大量数据读入对程序效率造成的影响。


title: 扇区填数

description:
有一个圆，当输入一个整数
 $n\ (1≤n≤8)$ 后，它被分成 $n$ 个扇区，请你为每一扇区选择一个正整数。

向各个扇区放入数之后，你可以从单个扇区中选出—个数，也可以从相邻的两个或多个扇区中各选一个数，相加后形成一个新的数，请使用这些整数形成一个连续的整数序列：$1,2,3,\cdots,i$，你的任务是使 $i$ 尽可能地大。

inputFormat: 共一行一个整数 $n\ (1\le n \le 8)$。

outputFormat:
第一行是最大的 $i$，接下来的几行是所有能达到最大 $i$ 的填法。

由于圆里不分顺序，所以同一种填法可以有多种输出。为了减少这种情况，这里规定从 $1$，开始输出（因为连续数里要有 $1$，所以所填的数中肯定有 $1$）。