title: 魔杖

description:
Smart 在春游时意外地得到了一种好东西——一种非常珍贵的树枝。这些树枝可以用来做优质的魔杖！

选择怎样的切割方式来制作魔杖非常重要，关键问题是——一把魔杖既不能太长、又不能太短，且制作出来的魔杖不能有冲突……

Smart 得到的这些树枝在属性上完全相同。每一根树枝都有 $n$ 段（用 $1$~ $n$ 编号），给定了每段的长度 $l$ 和每段的魔力值 $m$ 。你可以做的就是选择一段或连续的几段，把它们作为一个整体切下来，再用来制作魔杖。但是一根魔杖的长度不能太长，不能大于给定的值 $h$；也不能太短，不能小于给定的值 $low$ 。

魔杖有一个奇怪的要求：如果某一根魔杖的制作材料是另一根魔杖的一部分，则这两根魔杖之间将发生冲突。比如说树枝有三段，从左到右的长度分别为 $4$ 、 $1$ 、 $3$ ，Smart需要长度为 $4$ 到 $5$ 之间的魔杖。他可以用一根树枝的前两段做出一个长度为 $5$ 的魔杖，用一根树枝的后两段做出长度为 $4$ 的魔杖；但他决不能用一根树枝的前两段做了魔杖后再单独使用另一根树枝的第一段做成魔杖，因为前者包含了后者的所有成分，这会导致冲突。

我们假设 Smart 可以得到任意多这样的树枝。 Smart 需要制作出若干个互不冲突的魔杖，使所有魔杖的魔力值之和最大。（魔杖的长度就是组成它的那些段的长度的总和，魔力值亦然）。

inputFormat:
第一行有三个用空格隔开的整数，分别表示 $n$、$low$、$h$。

第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $l_i$ 。

第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $m_i$。

outputFormat: 输出一行一个整数，表示能够获得的魔力值的最大值。


title: 魔法阵

type: P

description:
魔法阵是一个 $n \times m$ 的格子（高 $n$，宽 $m$），$n \times m$ 为偶数。Smart 手中有 $n \times m$ 个宝石（以 $1 \sim n \times m$ 编号）。Smart 从最右上角的格子开始走，从一个格子可以走到上、下、左、右 $4$ 个相邻的格子，但不能走出边界。每个格子必须且仅能到过 $1$ 次，这样 Smart 一共走了 $n \times m$ 个格子停止（随便停哪里）。Smart 每进入一个格子，就在该格子里放入一颗宝石。他是按顺序放的，也就是说——第 $i$ 个进入的格子放入 $i$ 号宝石。

如果两颗宝石的编号对 $\frac{n \times m}{2}$ 取模的值相同，则认为这两颗宝石相互之间有微妙的影响。也就是说，我们按照宝石的编号对 $\frac{n \times m}{2}$ 取模的值，将宝石分成 $\frac{n \times m}{2}$ 对，其中每对都恰有两颗宝石。对于每一对宝石，设第一颗宝石在第 $a$ 行第 $b$ 列，另一颗宝石在第 $c$ 行第 $d$ 列，那么定义这 $2$ 个宝石的魔力影响值为 $k_1 \times \lvert a - c \rvert + k_2 \times \lvert b - d \rvert$。

需要你求出的是，在所有合乎题意的宝石摆放方案中，所有成对的宝石间的最大魔力影响值的最小值为多少。换句话说，如果我们定义对 $\frac{n \times m}{2}$ 取模的值为 $i$ 的一对宝石的魔力影响值为 $a_i$。你需要求出的就是 $\max \{ a_i : i=0,1,2,\ldots \}$ 的最小值。

inputFormat: 只有一行用空格隔开的四个整数，分别是 $n, m, k_1, k_2$。

outputFormat: 只需输出一个整数，即题目所要求的“所有成对的宝石间的最大魔力影响值的最小值”。


title: 四方定理

description: 四方定理是众所周知的：任意一个正整数$n$，可以分解为不超过四个整数的平方和。例如：$25=1^{2}+2^{2}+2^{2}+4^{2}$，当然还有其他的分解方案，$25=4^{2}+3^{2}$和$25=5^{2}$。给定的正整数$n$，编程统计它能分解的方案总数。注意：$25=4^{2}+3^{2}$和$25=3^{2}+4^{2}$视为一种方案。

inputFormat: 第一行为正整数$t$($t\le 100$)，接下来$t$行，每行一个正整数$n$($n\le 32768$)。

outputFormat: 对于每个正整数$n$，输出方案总数。


title: [NOI2016] 循环之美

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

$$a.\dot{c_1} c_2 c_3 \dots c_{p - 1} \dot{c_p}$$

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

例如，在十进制下，$0.45454545……=0.\dot {4} \dot {5}$ 是纯循环的，它可以用 $\frac {5}{11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666……=0.1\dot6$ 则不是纯循环的，它可以用 $\frac 16$ 等分数表示。需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环；而一个小数部分非 $0$ 的有限小数不是纯循环的。

inputFormat: 只有一行，包含三个十进制数 $N,M,K$ 意义如题所述。

outputFormat: 一行一个整数，表示满足条件的美的数的个数。


title: [USACO07OPEN] Catch That Cow S

description: FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 $x$ 和 $y$，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 $2\times x$ 的位置。计算他至少需要几步追上他的牛。

inputFormat:
第一行为一个整数 $t\ ( 1\le t\le 10)$，表示数据组数；

接下来每行包含一个两个正整数 $x,y\ (0<x,y \le 10^5)$，分别表示 FJ 和牛的坐标。

outputFormat: 对于每组数据，输出最少步数。


title: 泥泞路

description: 暴雨过后，FJ 的农场到镇上的公路上有一些泥泞路，他有若干块长度为 $L$ 的木板可以铺在这些泥泞路上，问他至少需要多少块木板，才能把所有的泥泞路覆盖住。

inputFormat:
第一行为正整数 $n$ 和 $L$，分别表示有多少段泥泞路和木板的长度；

接下来 $n$ 行，每一行两个整数 $s$ 和 $e$，表示每一段泥泞路的起点和终点。

outputFormat: 仅一个正整数，表示木板数。


title: 失踪的7

description: 远古的 Pascal 人也使用阿拉伯数字来进行计数，但是他们又不喜欢使用 $7$ ，因为他们认为 $7$ 是一个不吉祥的数字，所以 Pascal 数字 $8$ 其实表示的是自然数中的 $7$，$18$ 表示的是自然数中的 $16$ 。请计算，在正整数 $n$ 范围以内包含有多少个 Pascal 数字。

inputFormat: 第一行为正整数 $t$，接下来 $t$ 行，每行一个正整数 $n$，且保证输入 $n$ 的是 Pascal 数字

outputFormat: 对于每个正整数 $n$，输出 $n$ 以内的 Pascal 数的个数。

hint: 对于所有数据，$1 \leq t \leq 10000$，$1 \leq n \leq 2^{32}-1$。


title: 阶乘数码

description: 求 $n!$ 中某个数码出现的次数。

inputFormat: 第一行为 $t(t \leq 10)$，表示数据组数。接下来 $t$ 行，每行一个正整数 $n(n \leq 1000)$ 和数码 $a$。

outputFormat: 对于每组数据，输出一个整数，表示 $n!$ 中 $a$ 出现的次数。


title: 互质

description: 输入两个正整数 $n$ 和 $k$，求与 $n$ 互质的第 $k$ 个正整数。

inputFormat: 仅一行，为两个正整数 $n$ 和 $k$。

outputFormat: 一个正整数，表示与 $n$ 互质的第 $k$ 个正整数。

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

对于所有的数据，保证 $1 \leq n \le 10^6$，$1 \leq k\le 10^8$。


title: 因子和

description:
输入两个整数 $a$ 和 $b$，求 $a^b$ 的因子和。

由于结果太大，只要输出它对 $9901$ 取模的结果。

inputFormat: 仅一行，为两个整数 $a$ 和 $b$。

outputFormat: 输出一行一个整数表示答案对 $9901$ 取模的结果。

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

对于全部的测试点，保证 $1 \leq a \leq 5 \times 10^7$，$0 \leq b \leq 5 \times 10^7$。


title: 护卫队

description: 护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队达到了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。

inputFormat: 第一行包含三个整数，第一个整数表示该桥所能承受的最大载重量（用吨表示）；第二个整数表示该桥长度（用千米表示）；第三个整数表示该护卫队中车辆的总数（$n\lt 1000$）。接下来的几行中，每行包含两个正整数 $W$ 和 $S$（用空格隔开），$W$ 表示该车的重量（用吨表示），$S$ 表示该车过桥能达到的最快速度（用千米/小时表示）。车子的重量和速度是按车子排队等候时的顺序给出的。

outputFormat: 输出文件应该是一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该桥所需的最短时间（用分钟表示）。


title: 信封问题

description: 某人写了 $n$ 封信和 $n$ 个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

inputFormat: 一个信封数 $n$，保证 $n \le 20$。

outputFormat: 一个整数，代表有多少种情况。


title: [USACO10OCT] Lake Counting S

description: Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John's field, determine how many ponds he has.

inputFormat: Line 1: Two space-separated integers: N and M \* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

outputFormat: Line 1: The number of ponds in Farmer John's field.

translation:
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 $N\times M(1\leq N\leq 100, 1\leq M\leq 100)$ 的网格图表示。每个网格中有水（`W`） 或是旱地（`.`）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入第 $1$ 行：两个空格隔开的整数：$N$ 和 $M$。

第 $2$ 行到第 $N+1$ 行：每行 $M$ 个字符，每个字符是 `W` 或 `.`，它们表示网格图中的一排。字符之间没有空格。

输出一行，表示水坑的数量。

hint: OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.


title: 语句解析

background: 木有背景……

description: 一串长度不超过 $255$ 的 PASCAL 语言代码，只有 $a,b,c$ 三个变量，而且只有赋值语句，赋值只能是一个一位的数字或一个变量，每条赋值语句的格式是 `[变量]:=[变量或一位整数];`。未赋值的变量值为 $0$ 输出 $a,b,c$ 的值。

inputFormat: 一串符合语法的 PASCAL 语言，只有 $a,b,c$ 三个变量，而且只有赋值语句，赋值只能是一个一位的数字或一个变量，未赋值的变量值为 $0$。

outputFormat: 输出 $a,b,c$ 最终的值。

hint: 输入的 PASCAL 语言长度不超过 $255$。


title: 垂直柱状图

description: 写一个程序从输入文件中去读取四行大写字母（全都是大写的，每行不超过 $100$ 个字符），然后用柱状图输出每个字符在输入文件中出现的次数。严格地按照输出样例来安排你的输出格式。

inputFormat: 四行字符，由大写字母组成，每行不超过 $100$ 个字符

outputFormat: 由若干行组成，前几行由空格和星号组成，最后一行则是由空格和字母组成的。在任何一行末尾不要打印不需要的多余空格。不要打印任何空行。

samples:
THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!

hint: 每行输出后面不允许出现多余的空格。


title: 结算日

background: 借债还债

description: “不放债不借债”，贝西多么希望自己可以遵循这个忠告。她已经和她的 $N(1 \leq N \leq 100,000)$ 个朋友有了债务关系，或者借债了，或者放债了。她的 $N$ 个朋友依次标号为 $1\dots N$。 结算日终于来临了。她知道，朋友欠她的钱比她欠朋友的钱多。她的朋友们分布在一条直线上，第 $i$ 头奶牛站的位置距离谷仓 $i$ 米。贝西打算沿着这条直线行走，从欠她钱的奶牛手里收钱回来，并且还钱给她欠钱的奶牛。 当她沿直线移动的时候，她可以要求任何欠她钱的奶牛还全部的钱。当她有足够的钱可以还清她的某个债，就可以把钱给对应的奶牛还清她的债。奶牛 $i$ 欠贝西 $D_i$ 元 $(-1,000 \leq D_i \leq 1,000,D_i \neq 0)$，负数表示贝西欠奶牛 $i$ 钱。 贝西从谷仓出发，位置为 $0$，初始贝西没有钱。贝西收回她的所有借债，并且还清她的欠债所需行走的最短距离是多少？注意：她必须在最后一头奶牛所在的位置，完成她的行走。

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

接下来第 $2 \dots N+1$ 行，第 $i+1$ 行包含一个整数 $D_i$

outputFormat: 一个整数，贝西收回借债并且还清欠债，所需要行走的最短距离（单位为米）


title: [NOIP2016 提高组] 天天爱跑步

background: NOIP2016 提高组 D1T2

description:
小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含 $n$ 个结点和 $n-1$ 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $m$ 个玩家，第 $i$ 个玩家的起点为 $s_i$，终点为 $t_i$。每天打卡任务开始时，所有玩家在第 $0$ 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 $j$ 的观察员会选择在第 $w_j$ 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 $w_j$ 秒也正好到达了结点 $j$。小 C 想知道每个观察员会观察到多少人?

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一 段时间后再被观察员观察到。 即对于把结点 $j$ 作为终点的玩家：若他在第 $w_j$ 秒前到达终点，则在结点 $j$ 的观察员不能观察到该玩家；若他正好在第 $w_j$ 秒到达终点，则在结点 $j$ 的观察员可以观察到这个玩家。

inputFormat:
第一行有两个整数 $n$ 和 $m$。其中 $n$ 代表树的结点数量, 同时也是观察员的数量, $m$ 代表玩家的数量。

接下来 $n-1$ 行每行两个整数 $u$ 和 $v$，表示结点 $u$ 到结点 $v$ 有一条边。

接下来一行 $n$ 个整数，其中第 $j$ 个整数为 $w_j$ , 表示结点 $j$ 出现观察员的时间。

接下来 $m$ 行，每行两个整数 $s_i$，和 $t_i$，表示一个玩家的起点和终点。

对于所有的数据，保证 $1\leq s_i,t_i\leq n, 0\leq w_j\leq n$。

outputFormat: 输出 $1$ 行 $n$ 个整数，第 $j$ 个整数表示结点 $j$ 的观察员可以观察到多少人。

hint:
**样例 1 说明**

对于 $1$ 号点，$w_i=0$，故只有起点为 $1$ 号点的玩家才会被观察到，所以玩家 $1$ 和玩家 $2$ 被观察到，共有 $2$ 人被观察到。

对于 $2$ 号点，没有玩家在第 $2$ 秒时在此结点，共 $0$ 人被观察到。

对于 $3$ 号点，没有玩家在第 $5$ 秒时在此结点，共 $0$ 人被观察到。

对于 $4$ 号点，玩家 $1$ 被观察到，共 $1$ 人被观察到。

对于 $5$ 号点，玩家 $1$ 被观察到，共 $1$ 人被观察到。

对于 $6$ 号点，玩家 $3$ 被观察到，共 $1$ 人被观察到。

**子任务**

每个测试点的数据规模及特点如下表所示。

提示：数据范围的个位上的数字可以帮助判断是哪一种数据类型。

| 测试点编号 | $n=$ | $m=$ | 约定 |
| :--------: | :----: | :----: | :----: |
|     $1\sim 2$      |  $991$   |  $991$   | 所有人的起点等于自己的终点，即 $\forall i,\ s_i=t_i$  |
|     $3\sim 4$      |  $992$   |  $992$   | 所有 $w_j=0$  |
|     $5$      |  $993$   |  $993$   | 无  |
|     $6\sim 8$      |  $99994$   |  $99994$   | $\forall i\in[1,n-1]$，$i$ 与 $i+1$ 有边。即树退化成 $1,2,\dots,n$ 按顺序连接的链  |
|     $9\sim 12$      |  $99995$   |  $99995$   | 所有 $s_i=1$  |
|     $13\sim 16$      |  $99996$   |  $99996$   | 所有 $t_i=1$  |
|     $17\sim 19$      |  $99997$   |  $99997$   | 无  |
|     $20$      |  $299998$   |  $299998$   | 无  |

**提示**

（提示：由于原提示年代久远，不一定能完全反映现在的情况，现在已经对该提示做出了一定的修改，提示的原文可以在[该剪贴板](https://www.luogu.com.cn/paste/3fneb8m6)查看）

在最终评测时，调用栈占用的空间大小不会有单独的限制，但在我们的工作环境中默认会有 $1 \text{MiB}$ 的限制。 这可能会引起**函数调用层数较多时，程序发生栈溢出崩溃**，程序中**较深层数的递归**往往会导致这个问题。如果你的程序需要用到较大的栈空间，请务必注意该问题。

我们可以使用一些方法修改调用栈的大小限制。

- Linux

我们可以在终端中输入下列命令：`ulimit -s 1048576`。此命令的意义是，将调用栈的大小限制修改为 $1048576\text{KiB}=1 \text{GiB}$。

例如，对于如下程序 `sample.cpp`：

```cpp
#include <bits/stdc++.h>
using namespace std;
int f[1000005];
void dfs(int a){
	if(a == 0){
		f[a] = 0;
		return;
	}
	dfs(a - 1);
	f[a] = f[a - 1] + 1;
}
int main(){
	dfs(1000000);
	return 0;
}
```

将上述源代码用命令 `g++ sample.cpp -o sample` 编译为可执行文件 `sample` 后，使用 `./sample` 执行程序。

如果在没有使用命令 `ulimit -s 1048576` 的情况下运行该程序，`sample` 会因为栈溢出而崩溃；如果使用了上述命令后运行该程序，该程序则不会崩溃。

特别地，当你打开多个终端时，它们并不会共享该命令，你需要分别对它们运行该命令。

请注意，调用栈占用的空间会计入总空间占用中，和程序其他部分占用的内存共同受到内存限制。

- Windows

如果你使用 Windows 下的 Dev-C++，请选择 `工具-编译选项` 并在如下区域填入以下命令 `-Wl,--stack=1073741824`，填入后注意确认“编译时加入以下命令的”的框是**已勾选**状态。

此处 `1073741824` 的单位是 $\text{B/Bytes}$。

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


title: A+B Problem（高精）

description: 高精度加法，相当于 a+b problem，**不用考虑负数**。

inputFormat: 分两行输入。$a,b \leq 10^{500}$。

outputFormat: 输出只有一行，代表 $a+b$ 的值。


title: Sramoc问题

description: 话说员工们整理好了筷子之后，就准备将快餐送出了，但是一看订单，都傻眼了:订单上没有留电话号码,只写了一个  $sramoc(k,m)$ 函数，这什么东西？什么意思？于是餐厅找来了资深顾问团的成员，YQ，SC，HQ，经过大量的查阅，大家获得了一些信息，$sramoc(k,m)$ 表示用数字 $0,1,2,\dots k-1$ 组成的正整数中能被 $m$ 整除的最小数。例如 $k=2,m=7$ 的时候，$sramoc(2,7)=1001$。自然电话号码就是 $1001$，为了尽快将快餐送出，电脑组的童鞋们埋头算起了这个齐葩的号码。。。

inputFormat: 第 $1$ 行为两个整数 $k,m$。

outputFormat: 仅 $1$ 行，那个电话号码（最小的数）。


title: 斯诺登的密码

background: 根据斯诺登事件出的一道水题

description:
2013 年 X 月 X 日，俄罗斯办理了斯诺登的护照，于是他混迹于一架开往委内瑞拉的飞机。但是，这件事情太不周密了，因为 FBI 的间谍早已获悉他的具体位置——但这不是最重要的——最重要的是如果要去委内瑞拉，那么就要经过古巴，而经过古巴的路在美国的掌控之中。

丧心病狂的奥巴马迫降斯诺登的飞机，搜查时却发现，斯诺登杳无踪迹。但是，在据说是斯诺登的座位上，发现了一张纸条。纸条由纯英文构成：`Obama is a two five zero.`（以 `.` 结束输出，只有 $6$ 个单词+一个句号，句子开头如没有大写亦为合法）这句话虽然有点无厘头，但是警官陈珺骛发现这是一条极其重要的线索。他在斯诺登截获的一台笔记本中找到了一个 C++ 程序，输入这条句子后立马给出了相对应的密码。陈珺鹜高兴得晕了过去，身为警官的你把字条和程序带上了飞机，准备飞往曼哈顿国际机场，但是在飞机上检查的时候发现——程序被粉碎了！飞机抵达华盛顿只剩 $5$ 分钟，你必须在这 $5$ 分钟内编写（杜撰）一个程序，免受上司的 $10000000000 \bmod 10$ 大板。破译密码的步骤如下：

（1）找出句子中所有用英文表示的数字 $(\leq 20)$，列举在下：

正规：`one two three four five six seven eight nine ten eleven twelve`
           `thirteen fourteen fifteen sixteen seventeen eighteen nineteen             twenty`

非正规：`a both another first second third`。为避免造成歧义，`another` 算作 $1$ 处理。

（2）将这些数字平方后对 $100$ 取模，如 $00,05,11,19,86,99$。

（3）把这些两位数按数位排成一行，组成一个新数，如果开头为 $0$，就去 $0$。

（4）找出所有排列方法中最小的一个数，即为密码。

// 数据已经修正 By absi2011 如果还有问题请联系我

inputFormat: 一个含有 $6$ 个单词的句子。

outputFormat: 一个整型变量（密码）。如果没有符合要求的数字出现，则输出 $0$。


title: B进制星球

background: 进制题目，而且还是个计算器~~

description: 话说有一天，小 Z 乘坐宇宙飞船，飞到一个美丽的星球。因为历史的原因，科技在这个美丽的星球上并不很发达，星球上人们普遍采用 $B\ (2 \le B \le 36)$ 进制计数。星球上的人们用美味的食物招待了小 Z，作为回报，小 Z 希望送一个能够完成 $B$ 进制加法的计算器给他们。现在小 Z 希望你可以帮助他，编写实现 $B$ 进制加法的程序。

inputFormat:
数据数据共三行。

第一行，一个十进制的整数，表示进制 $B$；

第二行和第三行，每行一个 $B$ 进制数正整数。数字的每一位属于 $\{\tt 0,1,2,3,4,5,6,7,8,9,A,B\cdots\}$。

outputFormat: 一个 $B$ 进制数，表示输入的两个数的和。

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

记 $n,m$ 分别表示两个 $B$ 进制数字的长度。

对于全部数据，$1\le n,m\le 2000$。


title: 迷宫

description:
给定一个 $N \times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

inputFormat:
第一行为三个正整数 $N,M,T$，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 $SX,SY,FX,FY$，$SX,SY$ 代表起点坐标，$FX,FY$ 代表终点坐标。

接下来 $T$ 行，每行两个正整数，表示障碍点的坐标。

outputFormat: 输出从起点坐标到终点坐标的方案总数。

hint: 对于 $100\%$ 的数据，$1 \le N,M \le 5$，$1 \le T \le 10$，$1 \le SX,FX \le n$，$1 \le SY,FY \le m$。


title: [USACO07FEB] Lilypad Pond G

description:
FJ has installed a beautiful pond for his cows' aesthetic enjoyment and exercise.

The rectangular pond has been partitioned into square cells of M rows and N columns (1 ≤ M ≤ 30; 1 ≤ N ≤ 30). Some of the cells have astonishingly sturdy lilypads; others have rocks; the remainder are just beautiful, cool, blue water.

Bessie is practicing her ballet moves by jumping from one lilypad to another and is currently located at one of the lilypads. She wants to travel to another lilypad in the pond by jumping from one lilypad to another.

Surprising only to the uninitiated, Bessie's jumps between lilypads always appear as a chess-knight's move: one move in one direction and then two more in the orthogonal direction (or perhaps two in one direction and then one in the orthogonal direction).

Farmer John is observing Bessie's ballet drill and realizes that sometimes she might not be able to jump to her destination lilypad because intermediary lilypads are missing.

Ever thrifty, he wants to place additional lilypads so she can complete her quest (perhaps quickly, perhaps by using a large number of intermediate lilypads). Of course, lilypads cannot be placed where rocks already intrude on a cell.

Help Farmer John determine the minimum number of additional lilypads he has to place, and in how many ways he can place that minimum number.

inputFormat:
第一行两个用空格分开的整数 $M$ 和 $N$。

第二行到 $M+1$ 行，第 $i+1$ 行有 $N$ 个用空格分开的整数，描述了池塘第 $i$ 行的状态：

- $0$ 为水，$1$ 为莲花，$2$ 为岩石，$3$ 为贝西所在的起点，$4$ 为贝西想去的终点。

outputFormat:
第一行一个整数，需要增加的最少莲花数；如果无解，输出 $-1$。

第二行输出放置这些莲花的方案数量，保证这个数字可用一个 $64$ 位的有符号整数，表示。

特别地，如果第一行是 $-1$，不要输出第二行。

translation:
为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 $M$ 行 $N$ 列个方格（$1 \le M,N \le 30$）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。

贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。

贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。

约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然，莲花不能放在石头上。

请帮助约翰确定必须要添加的莲花的最少数量，以及有多少种放置这些莲花的方法。

hint:
### 样例解释

池塘分成四行五列，贝西的起点在第二行第一列，想去的终点在第四行第四列，池塘里一共有三朵莲花和一块石头。

最少需要两朵莲花，有三种方式可以放置，

如下 $\verb!X!$ 所示：

$$\begin{bmatrix}
\verb!10000! \\
\verb!30X00! \\
\verb!00200! \\
\verb!0X040! \\
\end{bmatrix},\begin{bmatrix}
\verb!10X00! \\
\verb!30000! \\
\verb!0X200! \\
\verb!00040! \\
\end{bmatrix},\begin{bmatrix}
\verb!10X00! \\
\verb!3000X! \\
\verb!00200! \\
\verb!00040! \\
\end{bmatrix}
$$


title: [USACO09FEB] Fair Shuttle G

description:
Although Farmer John has no problems walking around the fair to collect prizes or see the shows, his cows are not in such good shape; a full day of walking around the fair leaves them exhausted. To help them enjoy the fair, FJ has arranged for a shuttle truck to take the cows from place to place in the fairgrounds.

FJ couldn't afford a really great shuttle, so the shuttle he rented traverses its route only once (!) and makes N (1 <= N <= 20,000) stops (conveniently numbered 1..N) along its path. A total of K (1 <= K <= 50,000) groups of cows conveniently numbered 1..K wish to use the shuttle, each of the M\_i (1 <= M\_i <= N) cows in group i wanting to ride from one stop S\_i (1 <= S\_i < E\_i) to another stop E\_i (S\_i < E\_i <= N) farther along the route.

The shuttle might not be able to pick up an entire group of cows (since it has limited capacity) but can pick up partial groups as appropriate.

Given the capacity C (1 <= C <= 100) of the shuttle truck and the descriptions of the groups of cows that want to visit various sites at the fair, determine the maximum number of cows that can ride the shuttle during the fair.

inputFormat:
第一行：包括三个整数：$K,N$ 和 $C$，彼此用空格隔开。

第二行到 $K+1$ 行：在第 $i+1$ 行，将会告诉你第 $i$ 组奶牛的信息：$S_i,E_i$ 和 $M_i$，彼此用空格隔开。

outputFormat: 第一行：可以坐班车的奶牛的最大头数。

translation:
逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠 $N(1 \leq N\leq 20000)$ 个地点（所有地点都以 $1$ 到 $N$ 之间的一个数字来表示）。现在奶牛们分成 $K(1\leq K\leq 50000)$ 个小组，第i 组有 $M_i(1\leq M_i\leq N)$ 头奶牛，他们希望从 $S_i$ 跑到 $E_i(1\leq S_i< E_i\leq N)$。

由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小组里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是 $C(1\leq C\leq 100)$，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。


title: 路径统计

description: “RP 餐厅” 的员工素质就是不一般，在齐刷刷的算出同一个电话号码之后，就准备让 HZH,TZY 去送快餐了，他们将自己居住的城市画了一张地图，已知在他们的地图上，有 $N$ 个地方，而且他们目前处在标注为 “1” 的小镇上，而送餐的地点在标注为 “N” 的小镇。（有点废话）除此之外还知道这些道路都是单向的，从小镇 $I$ 到 $J$ 需要花费 $D[I, J]$ 的时间，为了更高效快捷的将快餐送到顾客手中，他们想走一条从小镇 $1$ 到小镇 $N$ 花费最少的一条路，但是他们临出发前，撞到因为在路上堵车而生气的 FYY，深受启发，不能仅知道一条路线，万一。。。于是，他们邀请 FYY 一起来研究起了下一个问题：这个最少花费的路径有多少条？

inputFormat:
输入文件第一行为两个空格隔开的数 $N, E$，表示这张地图里有多少个小镇及有多少边的信息。

下面 $E$ 行，每行三个数 $I, J, C$，表示从 $I$ 小镇到 $J$ 小镇有道路相连且花费为 $C$。（注意，数据提供的边信息可能会重复，不过保证 $I \ne J$，$1 \leq I, J\leq N$）。

outputFormat:
输出文件包含两个数，分别是最少花费和花费最少的路径的总数。保证花费最少的路径的总数不超过 $2^{30}$。

两个不同的最短路方案要求：路径长度相同（均为最短路长度）且最短路经过的点的编号序列不同。

若城市 $N$ 无法到达则只输出一个 `No answer`。

hint:
对于 $30\%$ 的数据 $N\leq 20$；

对于 $100\%$ 的数据 $1\leq N\leq 2000$，$0\leq E\leq N\times (N-1)$，$1\leq C\leq 10$。


title: 最小回文数

description:
回文数是从左向右读和从右向左读结果一样的数字串。

例如：$121$、$44$ 和 $3$ 是回文数，$175$ 和 $36$ 不是。

对于一个给定的 $N$，请你寻找一个回文数 $P$，满足 $P > N$。

满足这样条件的回文数很多，你的任务是输出其中最小的一个。

inputFormat: 一行，一个正整数 $N$。$N$ 的数值小于 ${10}^{100}$，并且 $N$ 没有前导 $0$。

outputFormat: 你的程序应该输出一行，最小的回文数 $P$（$P > N$）。


title: 鸿山洞的灯

description:
已知 $n$ 盏灯以及每盏灯的位置 $p_i$，$p_i$ 均不相等，当两盏灯之间的距离小于 $dist$ 时，若这个安全距离里面还有灯是亮着时，就可以关掉这些灯（即若第 $i-1$ 盏与第 $i+1$ 盏的距离 $\leq dist$，则可以关掉第 $i$ 盏）。

求在保证洞里的光线是充足的情况下，一段区域里能删除的灯的最大值。

距离洞口最近和最远的两盏灯必须是亮着。

inputFormat:
第一行两个数，$n$ 和 $dist$。

第二行 $n$ 个数，即每盏灯的位置 $p_i$。

outputFormat: 一个数，即一段区域里能删除的灯的最大值。

hint: 对于 $100\%$ 的数据，$1\leq n\leq 10^5$，保证 $dist$ 在 `int` 整型范围之内。


title: 循环的数字

description:
你曾经因为看见一样的东西一遍又一遍地重复、循环而对电视节目感到厌烦么？好吧，虽然我并不关心电视节目的好坏，不过有时却也很像那样不断循环的数字。

让我们假定两个不同的正整数 $(n, m)$ 是循环的，当且仅当你能通过将 $n$ 末端的几个数字移到它的首端而不改变移动的数字的顺序并使整个数字变成 $m$ 。举个例子，$(12345, 34512)$ 就是一对循环的数字，因为你能把 $12345$ 中末尾的 $345$ 移到 $12$ 前面，从而得到 $34512$。注意，为了成为一对循环的数字，$n$ 和 $m$ 位数必须相同。无论 $n$ 或 $m$ 都没有前置的 $0$。

现在给定正整数 $A$ 和 $B$，并保证 $A$ 和 $B$ 位数相同且均没有前置 $0$，求存在多少循环的正整数对 $(n, m)$，使得 $A \leq n \le m \leq B$ ？

inputFormat: 本题有共有 $10$ 个测试点。 每个输入文件包含 $1$ 行。 第 $1$ 行有两个用空格隔开的正整数 $A$ 和 $B$。

outputFormat: 每个输出文件应包含一个正整数 $x$，表示共有 $x$ 组循环的正整数对 $(n,m)$ 使得 $A \leq n \le m \leq B$。

hint: $1\le A,B \leq 2\times 10^6$。


title: [yLOI2018] 树上的链

description:
给定一棵有 $n$ 个节点的树。每个节点有一个点权和一个参数。节点 $i$ 的权值为 $w_i$，参数为 $c_i$。$1$ 是这棵树的根。

现在，对每个节点 $u$（$1 \leq u \leq n$），请在树上你找到最长的一条链 $v_1, v_2, \dots v_m$，满足如下条件：

1. $v_1 = u$。
2. 对 $2 \leq i \leq m$， 有 $v_i$ 是 $v_{i - 1}$ 的父节点。
3. 链上节点的点权和不超过 $c_u$，即 $\sum_{j = 1}^m w_{v_j} \leq c_u$。

inputFormat:
第一行是一个整数，表示树的节点数 $n$。
第二行有 $n - 1$ 个整数 $p_2, p_3, \dots p_n$，其中 $p_i$ 表示节点 $i$ 的父节点。
第三行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的权值 $w_i$。
第四行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的参数 $c_i$。

outputFormat: 输出一行 $n$ 个用空格隔开的整数，第 $i$ 个整数表示节点 $i$ 对应的链的最长长度。

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

对全部的测试点，保证 $1 \leq u, v \leq n \leq 10^5$，$1 \leq p_i \lt i$，$1 \leq w_i \leq c_i \leq 10^9$。


title: 跑路

description: 小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 $6:00$ 之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑 $2^k$ 千米（$k$ 是任意自然数）。当然，这个机器是用 `longint` 存的，所以总跑路长度不能超过 `maxlongint` 千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点 $1$，公司为点 $n$，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证 $1$ 到 $n$ 至少有一条路径。

inputFormat:
第一行两个整数 $n,m$，表示点的个数和边的个数。

接下来 $m$ 行每行两个数字 $u,v$，表示一条 $u$ 到 $v$ 的边。

outputFormat: 一行一个数字，表示到公司的最少秒数。

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

$1 \to 1 \to 2 \to 3 \to 4$，总路径长度为 $4$ 千米，直接使用一次跑路器即可。

**【数据范围】**

$50\%$ 的数据满足最优解路径长度 $\leq 1000$；

$100\%$ 的数据满足 $2\leq n \leq 50$，$m \leq 10 ^ 4$，最优解路径长度 $\leq$ `maxlongint`。


title: 爱与愁的心痛

background:
（本道题目隐藏了两首歌名，找找看哪~~~）

《爱与愁的故事第一弹·heartache》第一章。

《我为歌狂》当中伍思凯神曲《舞月光》居然没赢给萨顶顶，爱与愁大神心痛啊~~~而且最近还有一些令人伤心的事情，都让人心痛（最近真的很烦哈)……

description: 最近有 $n$ 个不爽的事，每句话都有一个正整数刺痛值（心理承受力极差）。爱与愁大神想知道连续 $m$ 个刺痛值的和的最小值是多少，但是由于业务繁忙，爱与愁大神只好请你编个程序告诉他。

inputFormat:
第一行有两个用空格隔开的整数，分别代表 $n$ 和 $m$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $a_i$ 代表第 $i$ 件事的刺痛值 $a_i$。

outputFormat: 输出一行一个整数，表示连续 $m$ 个刺痛值的和的最小值是多少。

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

- 对于 $30\%$ 的数据，保证 $n \leq 20$。
- 对于 $60\%$ 的数据，保证 $n \leq 100$。
- 对于 $90\%$ 的数据，保证 $n \leq 10^3$。
- 对于 $100\%$ 的数据，保证 $0 \leq m \leq n \leq 3 \times 10^3$，$1 \leq a_i \leq 100$。


title: 西游记公司

background: 一道极其无厘头的题目。

description:
事情是这样的：

西游记中的孙沙猪三徒弟在西天取经之后开始进入厦门大学经贸系学习经济，在 $1$ 个小时的学习后，他们用特殊手段毕业了。

然后，他们创办了三个公司：“花果山生态旅游山庄集团公司” “高老庄猪肉美食城有限公司” 和 “流沙河轮渡有限公司”。虽然这三家公司出自 “经卷出版社” 社长唐三藏的徒弟们，但是每家公司都仍然保持着 $0$ 元以下的财政收入。

于是，他们想到了一个无聊的方法：向别人偷！其中，孙悟空偷猪八戒的平底锅之前，猪八戒可以一直抢沙和尚的笔记本。

现在，作为猪八戒手下首席智士的你，要帮助既聪明又愚蠢的猪八戒用那种不正当的手段挽救这个公司！

你可以这样做：你已经知道孙悟空什么时候要来偷猪八戒的东西，而猪八戒又要在什么时间去抢沙和尚的东西，又知道猪八戒每秒钟可以偷沙和尚 $n$ 台笔记本，帮猪八戒算一算，自己在有限的时间内能偷到沙和尚多少台笔记本，使得他有足够的时间来防御大师兄。

inputFormat:
第一行：一个时间，为 时：分：秒 形式，表示猪八戒打算去偷沙和尚笔记本的时间；

第二行：一个时间，为 时：分：秒 形式，表示孙悟空打算去偷猪八戒平底锅的时间。

**注：时间可能有前导零，也有可能没有。**

第三行：一行一个整数 $n$，表示猪八戒一秒能偷沙和尚的笔记本数。

保证第一行的时间要比第二行的时间早。

outputFormat: 一个整数，表示猪八戒能偷沙和尚笔记本的个数。

hint: 对于 $100\%$ 的数据，保证两个时间合法，$n<32768$。


title: 疯狂的采药

background: 此题为纪念 LiYuxiang 而生。

description:
LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

inputFormat:
输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

outputFormat: 输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

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

- 对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
- 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。


title: 爱与愁的一千个伤心的理由

background:
（本道题目隐藏了两首歌名，找找看哪~~~）

《爱与愁的故事第一弹·heartache》第二章。

经历了心痛后，爱与愁大神不行了。

description:
月落乌啼问爱与愁大神为什么，爱与愁大神写了一个数字 $n$（$n \le 9999$），说翻译成英语就知道为什么了。月落乌啼接过这个数字后，本想翻译成英语，但是班主任叫他去帮个忙。他想尽快知道答案，于是这个艰巨的任务就拜托你了。

标准美式英语，仅在末两位 $ \le 10$ 时加 `and` 且没有连字符。

inputFormat: 只有一行，一个数 $n$（$n \le 9999$）

outputFormat: 一行英文，表示 $n$ 翻译成英语的答案。

hint: 输出行初不大写。按标准美式英语输出，即两个非零的数中间没零则不加 `and`，行末无句号。


title: 三连击（升级版）

description:
将 $1, 2,\ldots, 9$ 共 $9$ 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 $A:B:C$，试求出所有满足条件的三个三位数，若无解，输出 `No!!!`。

//感谢黄小U饮品完善题意

inputFormat: 三个数，$A,B,C$。

outputFormat: 若干行，每行 $3$ 个数字。按照每行第一个数字升序排列。

hint:
保证 $A<B<C$。

---

$\text{upd 2022.8.3}$：新增加二组 Hack 数据。


title: 解一元二次方程的烦恼

background: JosephZheng 在写数学作业的预习。他往往使用 Casio 来帮忙解一元二次方程。但是 Casio 有一个问题，就是当 $\Delta=b^2-4ac$ 为一个大素数或大合数时，其开平方的结果会以小数显示，而不是老师要求的二次根式形式。JosephZheng 很是苦恼，一遇到这种情况就要手动解方程。一天他再也忍不住了，于是打开了电脑，编了一个 prime 程序……于是悲剧的 OIer 们就要跟着疯狂的 JosephZheng 一起编这个程序，呵呵……

description: 废话少说，给你一个大数 $N$（不一定在 int64 范围内），让你进行素性判断，然后分解质因数。当然，初中数学题不可能有大于 int64 的数让你判断素性，因此超过范围的数可以忽略不计。为了让程序更加贴心，JosephZheng 多了一些要求，会在输入输出中给出具体情况。

inputFormat: 一个大数 $N$（$N$ 为非负整数），其中这个数的各个数位之间可以插入各种符号，例如 $1234$ 可以为 `1 - 2alsdkjf3！@￥%！@@@##￥……！￥#-4` 等。你需要在这一长串乱码中找出这个要判断的数。输入数据可能有多组，如果读到一行没有数字的字串即结束。字符串长度可能大于 $255$。

outputFormat:
在读入数据之前先输出 `Enter the number=`，需要换行。

然后输出 `Prime?`，问号后有一个空格，但不要换行。

如果是质数则输出 `Yes!` 否则输出 `No!`。此时换行。

若果是质数就 halt，若是小于 $2$ 的数则在输出 `No!` 后也 halt。若是合数则分解质因数。如果该数大于四千万则输出 `The number is too large!`，然后 halt。否则分解质因数。输出结果的方式在输出样例中会详细给出。每组数据之间空一行。

samples:
Enter the number=
Prime? No!
4=2^2

Enter the number=

samples:
Enter the number=
Prime? Yes!

Enter the number=

samples:
Enter the number=
Prime? No!
15=3^1*5^1

Enter the number=
Prime? No!

Enter the number=
Prime? No!
The number is too large!

Enter the number=

samples:
Enter the number=
Prime? No!
12=2^2*3^1

Enter the number=

hint:
编这道题的 JosephZheng 有些无聊，但是很考验基本功哦！仔细审题！

水题一道。。。


title: 漂亮字串

description:
Caima 认为 $\tt O$ 和 $\tt X$ 是最优美的两个字母，由 $\tt O,X$ 组成的串是最优美的串。在这些最优美的串中，如果任意只包含 $\tt X$ 的子串，长度不超过 $\max_{\tt X}$，任意只包含 $\tt O$ 的子串，长度不超过 $\max_{\tt O}$，而整个串最多有 $\rm count_{\tt O}$ 个 $\tt O$，$\rm count_{\tt X}$ 个 $\tt X$。那么这个就是超级优美无敌串。

现在 Caima 想知道最长的超级优美无敌串有多长，希望你告诉他。

inputFormat:
输入包含多行，至文件结束为止。

每行四个数，依次是 $\rm count_{\tt O},\rm count_{\tt X},\rm max_{\tt O},\rm max_{\tt X}$。

outputFormat: 每组数据输出一行，一个数表示最长的超级优美无敌串的长度。

hint:
### 样例 2 解释

- $\tt XOXOXOX$。

### 数据范围及约定

最多 $1000$ 组数据，

其中 $30\%$ 的数据 $0\le \rm count_{\tt O},\rm count_{\tt X},\rm max_{\tt O},\rm max_{\tt X} \le 20$，且数据组数不超过 $20$ 组。

对于全部数据，$0 \le \rm count_{\tt O},\rm count_{\tt X},\rm max_{\tt O},\rm max_{\tt X}\le 10^6$。


title: 集合

description:
Caima 给你了所有 $[a,b]$ 范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数，如果这两个整数拥有大于等于 $p$ 的公共质因数，那么把它们所在的集合合并。

重复如上操作，直到没有可以合并的集合为止。

现在 Caima 想知道，最后有多少个集合。

inputFormat: 一行，共三个整数 $a,b,p$，用空格隔开。

outputFormat: 一个数，表示最终集合的个数。


title: 释放囚犯

description:
Caima 王国中有一个奇怪的监狱，这个监狱一共有 $P$ 个牢房，这些牢房一字排开，第 $i$ 个紧挨着第 $i+1$ 个（最后一个除外）。现在正好牢房是满的。

上级下发了一个释放名单，要求每天释放名单上的一个人。这可把看守们吓得不轻，因为看守们知道，现在牢房中的 $P$ 个人，可以相互之间传话。如果某个人离开了，那么原来和这个人能说上话的人，都会很气愤，导致他们那天会一直大吼大叫，搞得看守很头疼。如果给这些要发火的人吃上肉，他们就会安静点。

inputFormat:
第一行两个整数 $P$ 和 $Q$，$Q$ 表示释放名单上的人数；

第二行 $Q$ 个整数，表示要释放哪些人，保证按递增的顺序给出。

outputFormat: 仅一行，表示最少要给多少人次送肉吃。

hint:
### 样例说明 #1

先释放 $14$ 号监狱中的罪犯，要给 $1$ 到 $13$ 号监狱和 $15$ 到 $20$ 号监狱中的 $19$ 人送肉吃；再释放 $6$ 号监狱中的罪犯，要给 $1$ 到 $5$ 号监狱和 $7$ 到 $13$ 号监狱中的 $12$ 人送肉吃；最后释放 $3$ 号监狱中的罪犯，要给 $1$ 到 $2$ 号监狱和 $4$ 到 $5$ 号监狱中的 $4$ 人送肉吃。

### 数据规模与约定

- 对于 $50\%$ 的数据，$1 \le P \le 100$，$1 \le Q \le 5$；
- 对于 $100\%$ 的数据，$1 \le P \le 10^3$，$1 \le Q \le 100$，$Q \le P$，保证释放的人所在的牢房编号按递增的顺序给出。


title: [CEOI2007] 树的匹配 Treasury

description: 给一棵树，你可以匹配有边相连的两个点，问你这棵树的最大匹配是多少，并且计算出有多少种最大匹配。

inputFormat:
第一行一个整数 $N$，表示有多少个结点。

接下来 $N$ 行，每行第一个整数，表示要描述的那个结点。然后一个整数 $m$，表示这个结点有 $m$ 个儿子，接下来 $m$ 个整数，表示它的 $m$   个儿子的编号。

outputFormat: 输出两行，第一行输出最大匹配数，第二行输出最大匹配方案数。


title: 单词缩写

description:
树树发现好多计算机中的单词都是缩写，如 GDB 是全称 Gnu DeBug 的缩写。但是，有时候缩写对应的全称会不固定，如缩写 LINUX 可以理解为：

1. LINus’s UniX
2. LINUs’s miniX
3. Linux Is Not UniX

现在树树给出一个单词缩写，以及一个固定的全称（若干个单词组成，空格隔开）。全称中可能会有无效的单词，需要忽略掉，一个合法缩写要求每个有效单词中至少有一个字符出现在缩写中，所写必须按顺序出现在全称中。

对于给定的缩写和一个固定的全称，问有多少种解释方法？解释方法为所写的每个字母在全称每个有效单词中出现的位置，有一个字母位置不同，就认为是不同的解释方法。

inputFormat:
第一行输入一个 $N$，表示有 $N$ 个无效单词。

接下来 $N$ 行分别描述一个由小写字母组成的无效单词。

最后是若干个询问，先给出缩写（只有大写字母），然后给出一个全称，读入以 `LASTCASE` 结束。

outputFormat: 对于每个询问先输出缩写，如果当前缩写不合法，则输出 `is not a valid abbreviation`，否则输出 `can be formaed in i ways`（$i$表示解释方法数）。

samples:
2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE

samples:
ACM can be formed in 2 ways
RADAR is not a valid abbreviation

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

对于全部数据，$1 \le N \le 100$，每行字符串长度不超过 $150$，询问次数不超过 $20$，最后方案数不超过 $10^9$。


title: 求和

description:
高斯还是个小 P 孩的时候就求出

$$\sum_{i=1}^n i= \frac{n \times (n+1)}{2}$$

LT 还是个小 P 孩的时候求出

$$\sum_{i=1}^{n-1} \frac{1}{i\times (i+1)}=1-\frac{1}{n}$$

现在，你还是个小 P 孩的时候，你要求出：

$$\sum_{i=1}^n \frac{1}{\prod_{j=i}^{i+m-1}j}=S$$

inputFormat: 输入两个整数 $n, m$。

outputFormat: 输出占两行，第一行一个整数 $X$，第二行整数 $Y$，表示 $S=\frac{X}{Y}$，且 $X$ 和 $Y$ 互质。


title: 象棋比赛

description:
有 $N$ 个人要参加国际象棋比赛，该比赛要进行 $K$ 场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。

在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为增加比赛的可观度，观众希望 $K$ 场对弈中双方的等级差的总和最小。

比如有 $7$ 个选手，他们的等级分别是 $30,17,26,41,19,38,18$，要进行 $3$ 场比赛。最好的安排是选手 $2$ 对选手 $7$，选手 $7$ 对选手 $5$，选手 $6$ 对选手 $4$。此时等级差的总和等于 $(18-17)+(19-18)+(41-38)=5$ 达到最小。

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

接下来有 $N$ 行，第 $i$ 行表示第 $i-1$ 个人等级。

outputFormat: 在第一行输出最小的等级差的总和。

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

- 在 $90\%$ 的数据中，$1 \le N \le 3000$；
- 在 $100\%$ 的数据中，$1 \le N \le 100000$。

保证所有输入数据中等级的值小于 $10^9$，$1 \le K \le N-1$。


title: [CQOI2009] 中位数

description: 给出 $1,2,...,n$ 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 $b$。中位数是指把所有元素从小到大排列后，位于中间的数。

inputFormat: 第一行为两个正整数 $n$ 和 $b$，第二行为 $1,2,...,n$ 的排列。

outputFormat: 输出一个整数，即中位数为 $b$ 的连续子序列个数。

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

对于 $30\%$ 的数据中，满足 $n \le 100$；

对于 $60\%$ 的数据中，满足 $n \le 1000$；

对于 $100\%$ 的数据中，满足 $n \le 100000,1 \le b \le n$。


title: 合并序列

description: 有 $N$ 个单词和字符串 $T$，按字典序输出以字符串 $T$ 为前缀的所有单词。

inputFormat:
输入文件第一行包含一个正整数 $N$；

接下来 $N$ 行，每行一个单词，长度不超过 $100$；

最后一行包含字符串 $T$。

outputFormat: 按字典序升序输出答案。

hint:
【数据规模】

对于 $60\%$ 的数据，满足 $1 \le N \le 1000$；

对于 $100\%$ 的数据，满足 $1 \le N \le 100000$ 且所有字符均为小写字母。


title: 邮递员送信

description: 有一个邮递员要送东西，邮局在节点 $1$。他总共要送 $n-1$ 样东西，其目的地分别是节点 $2$ 到节点 $n$。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。这个邮递员每次只能带一样东西，并且**运送每件物品过后必须返回邮局**。求送完这 $n-1$ 样东西并且**最终回到邮局**最少需要的时间。

inputFormat:
第一行包括两个整数，$n$ 和 $m$，表示城市的节点数量和道路数量。

第二行到第 $(m+1)$ 行，每行三个整数，$u,v,w$，表示从 $u$ 到 $v$ 有一条通过时间为 $w$ 的道路。

outputFormat: 输出仅一行，包含一个整数，为最少需要的时间。

hint:
对于 $30\%$ 的数据，$1 \leq n \leq 200$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^3$，$1 \leq m \leq 10^5$，$1\leq u,v \leq n$，$1 \leq w \leq 10^4$，输入保证任意两点都能互相到达。


title: 求和

description: 求 $1^b+2^b+\cdots + a^b$ 的和除以 $10^4$ 的余数。

inputFormat:
**本题有多组数据。**

第一行一个整数 $N$，表示共有 $N$ 组测试数据。

对于每组数据，一行两个整数 $a,b$。

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


title: 序列合并

description: 有两个长度为 $N$ 的**单调不降**序列 $A,B$，在 $A,B$ 中各取一个数相加可以得到 $N^2$ 个和，求这 $N^2$ 个和中最小的 $N$ 个。

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

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

第三行 $N$ 个整数 $B_{1\dots N}$。

outputFormat: 一行 $N$ 个整数，从小到大表示这 $N$ 个最小的和。


title: 点的移动

description: 平面上有 $N$ 个整数坐标点。如果将点 $(x_0,y_0)$ 移动到 $(x_1,y_1)$，则需要的代价为 $|x_0-x_1|+|y_0-y_1|$。求使得 $K(K=1, \cdots ,N)$ 个点在同一位置上最少需要的代价。

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

接下来 $N$ 行，每行两个正整数 $x_i$ 和 $y_i$，为第 $i$ 个点的坐标，不超过 $10^6$。

【数据规模】。

对于 $100\%$ 的数据中，满足 $1 \le N \le 50$。

outputFormat: 输出共 $N$ 行，第 $i$ 行为使得有 $i$ 个点在统一位置的最少代价。


title: 二进制

description:
有三个整数 $A,B,C$，以下用 $N_{(2)}$ 表示 $N$ 的二进制（没有前导 $0$）。

设 $A_{(2)},B_{(2)},C_{(2)}$ 的最大长度为 $L$，你需要构造三个正整数 $X,Y,Z$，满足以下条件：

1. $X_{(2)},Y_{(2)},Z_{(2)}$ 的长度都不超过 $L$。
2. $A_{(2)}$ 与 $X_{(2)}$ 中 $1$ 的个数相同。
3. $B_{(2)}$ 与 $Y_{(2)}$ 中 $1$ 的个数相同。
4. $C_{(2)}$ 与 $Z_{(2)}$ 中 $1$ 的个数相同。
5. $X+Y=Z$。

inputFormat:
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来 $T$ 行，每行三个正整数 $A,B,C$。

outputFormat:
输出共 $T$ 行，每行一个答案。

输出最小的 $Z$。如果没有合法的 $Z$ 则输出 $-1$。


title: 禽兽的传染病

background: mxj 的启发。

description: 禽兽患传染病了。一个禽兽会每轮传染 $x$ 个禽兽。试问 $n$ 轮传染后有多少禽兽被传染？

inputFormat: 两个非负整数 $x$ 和 $n$。

outputFormat: 一个整数，即被传染的禽兽数。

hint: 保证 $x,n$ 以及答案都在 $64$ 位无符号整数的表示范围内。


title: 跳跃

background: NOIP 即将迎来周年华诞。在这一个春秋的历程里，NOIP 领导全国 oier，建设高效、稳定、快捷、开放的社会主义现代化  OI。在新的一年里，YZOJ 将再接再厉，积极探寻成长之路，更好地为广大 oier 服务。

description:
青蛙小 C 听说 NOIP 要办周年庆比赛，兴冲冲得来到了 Z 市，初始时他在坐标 $x_0$ 处，小 C 是一只善于跳跃的青蛙，若当前他处在坐标 $x$ 处，每一次跳跃，他可以跳到 $4x+3$ 或 $8x+7$ 处，且由于体力原因，他最多能跳 $100000$ 次。

根据 Z 市的传说，坐标位置为 $10^9+7$ 的整数倍的位置（如 $10^9+7,2\times 10^9+14$）可以传送到 YZOJ。

小 C 想知道，最少跳几次能传送到 YZOJ。

inputFormat: 输入的第一行包含一个整数 $x_0$ 表示青蛙的初始位置，保证 $x_0$ 在的范围在 $[1,10^9+6]$。

outputFormat: 输出一个整数，表示最少所需步数，若在 $100000$ 步内还无法传送到 YZOJ，则输出 $-1$。


title: Einstein学画画（数据有误）

background: **本题数据有误，请不要提交。**

description:
Einstein 学起了画画。

此人比较懒\~\~，他希望用最少的笔画画出一张画……

给定一个无向图，包含 $n$ 个顶点（编号 $1 \sim n$），$m$ 条边，求最少用多少笔可以画出图中所有的边。

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

接下来 $m$ 行，每行两个数 $a, b$（$a \ne b$），表示 $a, b$ 两点之间有一条边相连。

一条边不会被描述多次。

outputFormat: 一个数，即问题的答案。


title: 三元上升子序列

description:
Erwin 最近对一种叫 `thair` 的东西巨感兴趣。。。

在含有 $n$ 个整数的序列 $a_1,a_2,\ldots,a_n$ 中，三个数被称作`thair`当且仅当 $i<j<k$ 且 $a_i<a_j<a_k$。

求一个序列中 `thair` 的个数。

inputFormat:
开始一行一个正整数 $n$,

以后一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

outputFormat: 一行一个整数表示 `thair` 的个数。


title: 逛画展

description:
博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。

游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 $a,b$，数据保证一定有解。

若存在多组解，**输出 $a$ 最小的那组**。

inputFormat:
第一行两个整数 $n,m$，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 $n$ 个整数 $a_i$，代表画第 $i$ 幅画的名师的编号。

outputFormat: 一行两个整数 $a,b$。


title: [SCOI2010] 连续攻击游戏

description: lxhgww 最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有 $2$ 个属性，这些属性的值用 $[1,10000]$ 之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww 遇到了终极 boss，这个终极 boss 很奇怪，攻击他的装备所使用的属性值必须从 $1$ 开始连续递增地攻击，才能对 boss 产生伤害。也就是说一开始的时候，lxhgww 只能使用某个属性值为 $1$ 的装备攻击 boss，然后只能使用某个属性值为 $2$ 的装备攻击 boss，然后只能使用某个属性值为 $3$ 的装备攻击 boss……以此类推。现在 lxhgww 想知道他最多能连续攻击 boss 多少次？

inputFormat: 输入的第一行是一个整数 $N$，表示 lxhgww 拥有 $N$ 种装备接下来 $N$ 行，是对这 $N$ 种装备的描述，每行 $2$ 个数字，表示第 $i$ 种装备的 $2$ 个属性值。

outputFormat: 输出一行，包括 $1$ 个数字，表示 lxhgww 最多能连续攻击的次数。


title: [SCOI2010] 生成字符串

description: lxhgww 最近接到了一个生成字符串的任务，任务需要他把 $n$ 个 $1$ 和 $m$ 个 $0$ 组成字符串，但是任务还要求在组成的字符串中，在任意的前 $k$ 个字符中，$1$ 的个数不能少于 $0$ 的个数。现在 lxhgww 想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

inputFormat: 输入数据只有一行，包括 $2$ 个数字 $n$ 和 $m$。

outputFormat: 输出数据是一行，包括 $1$ 个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以 $20100403$ 的余数

hint:
对于 $30\%$ 的数据，保证 $1\leq m\leq n\leq 10^3$。

对于 $100\%$ 的数据，保证 $1\leq m\leq n\leq 10^6$。


title: 规划

description: 某地方有 $N$ 个工厂，有 $N-1$ 条路连接它们，且它们两两都可达。每个工厂都有一个产量值和一个污染值。现在工厂要进行规划，拆除其中的 $M$ 个工厂，使得剩下的工厂依然连成一片且总产量 / 总污染的值最大。

inputFormat:
第一行两个整数 $N,M$ 表示工厂个数和要拆除的个数。

第二行 $N$ 个正整数 $w_i$，表示每个工厂的产值 。

第三行 $N$ 个正整数 $c_i$，表示每个工厂的污染值。

接着 $N-1$ 行，每行两个正整数 $a,b\ (1 \le a,b \le N)$ 表示 $a,b$ 之间相连。

outputFormat: 输出 总产量/总污染 的最大值，保留一位小数。


title: 完美数

description:
考古队员小星在一次考察中意外跌入深渊，穿越到了一个神秘的荒漠。这里有许多超越他认识的事物存在，例如许多漂浮在空中的建筑，例如各种奇怪的动物。

在这片荒漠的中央，小星发现了一个巨大的类似神庙的建筑，为了脱离这片空间，小星决定前去探索。

在临近神庙大门时，突然跳出了一个人面狮（不是斯芬达克斯）！它咆哮着：

“我是这里的守卫，要想通过这里，必须回答出我的一系列问题，否则，我就吃了你。”

人面狮告诉小星，问题总是这样的模式：比 $X$ 大的第 $N$ 小的回文数是多少。

小星想，这个问题看来不难，于是问答开始了。

“比 $1$ 大的第 $1$ 小回文数数是多少？”

“$2$”

“比 $17$ 大的第 $2$ 小的回文数是多少？”

“$33$”

“比 $98$ 大的第 $2$ 小的回文数是多少？”

“$101$”

“那比 948237 大的第 2339587 小的回文数是多少？”

“\*（•%（\*•—#•#￥\*—%（\*—%”

为了避免被守卫吃掉，小星只好打开笔记本想借助电脑，却意外地发现可以通过网络（网通？电信？宇宙通？）找到你，于是这个问题就拜托给你了！

inputFormat:
本题每一个数据包含有多组数据。

对于每一个数据包，第一行一个数 $T$，表示总共有 $T$ 组数据。

对于每一组数据，包括两行，第一行为 $X$，第二行为 $N$，表示当前询问是比 X 大的第 N 小的回文数是多少。

outputFormat: 对于每一组数据输出一行，表示询问的结果。


title: 跳马问题

background: 在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……

description:
中国象棋半张棋盘如图 $1$ 所示。马自左下角 $(0,0)$ 向右上角 $(m,n)$ 跳。规定只能往右跳，不准往左跳。比如图 $1$ 中所示为一种跳行路线，并将路径总数打印出来。

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

inputFormat: 只有一行：两个数 $n$，$m$。

outputFormat: 只有一个数：总方案数 $total$。


title: 序列

description: 有一个整数序列，它的每个数各不相同，我们不知道它的长度是多少（即整数个数），但我们知道在某些区间中间至少有多少个整数，用区间（$L_i,R_i,C_i$）来描述，表示这个整数序列中至少有 $C_i$ 个数来自区间 $[L_i,R_i]$，给出若干个这样的区间，问这个整数序列的长度最少能为多少？

inputFormat:
第一行一个整数 $N$，表示区间个数；

接下来 $N$ 行，每行三个整数 $L_i,R_i,C_i$，描述一个区间。

outputFormat: 仅一个数，表示该整数序列的最小长度。

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

对于全部数据，$1\le N \le 1000$，$0 \le L_i \le R_i \le 1000$，$1 \le C_i \le R_i-L_i+1$。


title: [国家集训队] happiness

description:
高一一班的座位表是个 $n\times m$ 的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。

作为计算机竞赛教练的 scp 大老板，想知道如何分配可以使得全班的喜悦值总和最大。

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

接下来是六个矩阵。

- 第一个矩阵为 $n$ 行 $m$ 列。此矩阵的第 $i$ 行第 $j$ 列的数字表示座位在第 $i$ 行第 $j$ 列的同学选择文科获得的喜悦值。
- 第二个矩阵为 $n$ 行 $m$ 列。此矩阵的第 $i$ 行第 $j$ 列的数字表示座位在第 $i$ 行第 $j$ 列的同学选择理科获得的喜悦值。
- 第三个矩阵为 $n-1$ 行 $m$ 列。此矩阵的第 $i$ 行第 $j$ 列的数字表示座位在第 $i$ 行第 $j$ 列的同学与第 $i+1$ 行第 $j$ 列的同学同时选择文科获得的额外喜悦值。
- 第四个矩阵为 $n-1$ 行 $m$ 列。此矩阵的第 $i$ 行第 $j$ 列的数字表示座位在第 $i$ 行第 $j$ 列的同学与第 $i+1$ 行第 $j$ 列的同学同时选择理科获得的额外喜悦值。
- 第五个矩阵为 $n$ 行 $m-1$ 列。此矩阵的第 $i$ 行第 $j$ 列的数字表示座位在第 $i$ 行第 $j$ 列的同学与第 $i$ 行第 $j+1$ 列的同学同时选择文科获得的额外喜悦值。
- 第六个矩阵为 $n$ 行 $m-1$ 列。此矩阵的第 $i$ 行第 $j$ 列的数字表示座位在第 $i$ 行第 $j$ 列的同学与第 $i$ 行第 $j+1$ 列的同学同时选择理科获得的额外喜悦值。

outputFormat: 输出一个整数，表示喜悦值总和的最大值。

hint:
### 样例解释

两人都选理，则获得 $100+110+1000$ 的喜悦值。

对于 $100\%$ 的数据，$1\le n,m \le 100$，且所有喜悦值均为小于等于 $5000$ 的非负整数。


title: 锁

description:
给出 $N$ 和 $K$，要求生成从 $0$ 到 $2^N-1$ 的一个序列，序列的第一项为 $0$，并且该序列满足以下三个条件：

1. 序列长度为 $2^N$，保证 $0$ 到 $2^N-1$ 的每个数都用了且只用了一次。
2. 序列中任意两相邻的数都是由前一个数在其二进制下，改变了具有相同值的若干个位而形成的，即把其中若干个 $0$ 变为 $1$，或把其中若干个 $1$ 变为 $0$，并且只能二选一。
3. 当存在多个序列满足前两个条件的时候，要保证字典序最小，即由前一个数生成后一个数的时候，要挑值最小的数（当然是满足前两个条件的情况下）。

现问你这个序列前 $K$ 项中的最大值是多少，输出其二进制形式，注意一定要输出 $N$ 位，包括前导零。

inputFormat: 仅一行两个整数 $N,K$。

outputFormat: 一个二进制表示的数，为所求的答案。


title: 看守

description:
给出 $d$ 维空间的 $n$ 个点，求曼哈顿距离最大的两个点的曼哈顿距离。

两个 $d$ 维的点 $(x_1,x_2,\ldots,x_d)$，$(y_1,y_2,\ldots,y_d)$ 的曼哈顿距离定义为 $|x_1-y_1|+|x_2-y_2|+\ldots+|x_d-y_d|$。

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

接下来 $n$ 行，每行 $d$ 个整数描述一个点的坐标。

outputFormat: 输出最大的曼哈顿距离。

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

- 对于 $60\%$ 的数据，保证 $d\le2$。
- 对于 $100\%$ 的数据，保证 $2\le n\le10^6$，$d\le4$，且坐标每一维保证 $1\le x_i\le 10^5$。


title: [USACO07OCT] Obstacle Course S

description:
Consider an N x N (1 <= N <= 100) square field composed of 1

by 1 tiles. Some of these tiles are impassible by cows and are marked with an 'x' in this 5 by 5 field that is challenging to navigate:

```cpp
. . B x .
. x x A .
. . . x .
. x . . .
. . x . .
```
Bessie finds herself in one such field at location A and wants to move to location B in order to lick the salt block there.  Slow, lumbering creatures like cows do not like to turn and, of course, may only move parallel to the edges of the square field. For a given field, determine the minimum number of ninety degree turns in any path from A to B. The path may begin and end with Bessie facing in any direction. Bessie knows she can get to the salt lick.

inputFormat: 第一行一个整数 $N$,下面 $N$ 行，每行 $N$ 个字符，只出现字符：$\verb!.!,\verb!x!,\verb!A!,\verb!B!$，表示上面所说的矩阵格子，每个字符后有一个空格。

outputFormat: 一个整数：最少转弯次数。如果不能到达，输出 $-1$。

translation: $N\times N\ (1\le N\le 100)$ 方格中，$\verb!x!$ 表示不能行走的格子，$\verb!.!$ 表示可以行走的格子。卡门很胖，故而不好转弯。现在要从 $A$ 点走到 $B$ 点，请问最少要转 $90$ 度弯多少次？

hint:
只可以上下左右四个方向行走，并且不能走出这些格子之外。开始和结束时的方向可以任意。

### 数据范围及约定

对于全部数据，保证 $2\le N\le 100$。


title: 田忌赛马

description:
我国历史上有个著名的故事： 那是在 $2300$ 年以前。齐国的大将军田忌喜欢赛马。他经常和齐王赛马。他和齐王都有三匹马：常规马，上级马，超级马。一共赛三局，每局的胜者可以从负者这里取得 $200$ 银币。每匹马只能用一次。齐王的马好，同等级的马，齐王的总是比田忌的要好一点。于是每次和齐王赛马，田忌总会输 $600$ 银币。

田忌很沮丧，直到他遇到了著名的军师――孙膑。田忌采用了孙膑的计策之后，三场比赛下来，轻松而优雅地赢了齐王 $200$ 银币。这实在是个很简单的计策。由于齐王总是先出最好的马，再出次好的，所以田忌用常规马对齐王的超级马，用自己的超级马对齐王的上级马，用自己的上级马对齐王的常规马，以两胜一负的战绩赢得 $200$ 银币。实在很简单。

如果不止三匹马怎么办？这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边，把齐王的马放右边。田忌的马 A 和齐王的 B 之间，如果田忌的马胜，则连一条权为 $200$ 的边；如果平局，则连一条权为 $0$ 的边；如果输，则连一条权为 $-200$ 的边……如果你不会求最佳匹配，用最小费用最大流也可以啊。 然而，赛马问题是一种特殊的二分图最佳匹配的问题，上面的算法过于先进了，简直是杀鸡用牛刀。现在，就请你设计一个简单的算法解决这个问题。

inputFormat: 第一行一个整数 $n$ ，表示他们各有几匹马（两人拥有的马的数目相同）。第二行 $n$ 个整数，每个整数都代表田忌的某匹马的速度值（$0 \le $ 速度值 $\le 100$）。第三行 $n$ 个整数，描述齐王的马的速度值。两马相遇，根据速度值的大小就可以知道哪匹马会胜出。如果速度值相同，则和局，谁也不拿钱。

outputFormat: 仅一行，一个整数，表示田忌最大能得到多少银币。


title: 塔

description: 小明很喜欢摆积木，现在他正在玩的积木是由 $N$ 个木块组成的，他想用这些木块搭出两座高度相同的塔，一座塔的高度是搭建它的所有木块的高度和，并且一座塔至少要用一个木块。每个木块只能用一次，也可以不用。目前已知每块木块的高度，小明想知道在最终两个塔的高度相同的情况下，他所能搭的塔的最大高度是多少，你能帮助他吗？

inputFormat:
第一行为一个整数 $N$，表示木块个数。

第二行是 $N$ 个整数，表示 $N$ 块木块的高度。

outputFormat: 仅一个整数，表示能搭建的塔的最大高度，若不能搭建两座相同高度的塔，则输出 `-1`。

hint: 对于 $100\%$ 的数据，$N \le 50$ ，每块木块的高度 $h$ 满足 $1 \le h \le 500000$，所有木块的高度总和 $\le 500000$。


title: 圆

description:
给出 $n$ 个圆，保证任意两个圆都不相交且不相切。

然后给出两个点 $(x_1,y_1),(x_2,y_2)$，保证均不在某个圆上。现在要从 $(x_1,y_1) \to (x_2,y_2)$ 画条曲线，问这条曲线最少穿过多少次圆的边界？

inputFormat:
- 第一行为一个整数 $n$，表示圆的个数；
- 第二行是 $n$ 个整数，表示 $n$ 个圆的 $x$ 坐标；
- 第三行是 $n$ 个整数，表示 $n$ 个圆的 $y$ 坐标；
- 第四行是 $n$ 个整数，表示 $n$ 个圆的半径 $r$；
- 第五行是四个整数 $x_1,y_1,x_2,y_2$。

outputFormat: 仅一个整数，表示最少要穿过多少次圆的边界。

hint:
【数据范围】

对于 $100\%$ 的数据，$1\le n \le 50$，$|x|,|y| \le 1000$，$1 \le r \le 1000$。

保证圆之间没有公共点。


title: [USACO04DEC] Cow Ski Area G

description:
约翰的表哥罗恩生活在科罗拉多州。他近来打算教他的奶牛们滑雪，但是奶牛们非常害羞，不敢在游人组织的度假胜地滑雪。没办法，他只好自己建滑雪场了。罗恩的雪场可以划分为 $W$ 列 $L$ 行 $(1\le W\le 500, 1\le L\le 500)$，每个方格有一个特定的高度 $H(0\le H\le 9999)$。奶牛可以在相邻方格间滑雪，而且不能由低到高滑。

为了保证任意方格可以互通，罗恩打算造一些直达缆车。缆车很强大，可以连接任意两个方格，而且是双向的。而且同一个方格也可以造多台缆车。但是缆车的建造费用贵得吓人，所以他希望造尽量少的缆车。那最少需要造多少台呢？

inputFormat:
第 $1$ 行：$W$，$L$。

接下来输入宽 $W$ 高 $L$ 的矩阵地图。

outputFormat: 输出最小需要的缆车数。


title: OSU!

background: 原 《产品排序》 参见P2577

description:
osu 是一款群众喜闻乐见的休闲软件。

我们可以把 osu 的规则简化与改编成以下的样子:

一共有 $n$ 次操作，每次操作只有成功与失败之分，成功对应 $1$，失败对应 $0$，$n$ 次操作对应为 $1$ 个长度为 $n$ 的 01 串。在这个串中连续的  $X$ 个 $1$ 可以贡献 $X^3$ 的分数，这 $x$ 个 $1$ 不能被其他连续的 $1$ 所包含（也就是极长的一串 $1$，具体见样例解释）

现在给出 $n$，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 $1$ 位小数。

inputFormat: 第一行有一个正整数 $n$，表示操作个数。接下去 $n$ 行每行有一个 $[0,1]$ 之间的实数，表示每个操作的成功率。

outputFormat: 只有一个实数，表示答案。答案四舍五入后保留 $1$ 位小数。


title: 小朋友的球

description: @发源于 小朋友最近特别喜欢球。有一天他脑子抽了，从口袋里拿出了 $N$ 个不同的球，想把它们放到 $M$ 个相同的盒子里，并且要求每个盒子中至少要有一个球，他好奇有几种放法，于是尝试编程实现，但由于他天天不好好学习，只会上 B 站看游泳教练，于是他向你求助。

inputFormat: 多组数据，每行两个数 $N,M$。

outputFormat: 每组数据一行，表示方案数。

hint:
- 对于 $20\%$ 的数据，满足 $N,M \leq 10$；
- 对于 $100\%$ 的数据，满足 $1 \leq N,M \leq 100$，一个测试文件最多有 $10$ 组测试数据。


title: 炸铁路

description:
A 国派出将军 uim，对 B 国进行战略性措施，以解救涂炭的生灵。

B 国有 $n$ 个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。

uim 发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为 key road。

uim 为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。

然而，只有一发炮弹（A 国国会不给钱了）。所以，他能轰炸哪一条铁路呢？

inputFormat:
第一行 $n,m\ (1 \leq n\leq 150$，$1 \leq m \leq 5000)$，分别表示有 $n$ 个城市，总共 $m$ 条铁路。

以下 $m$ 行，每行两个整数 $a, b$，表示城市 $a$ 和城市 $b$ 之间有铁路直接连接。

outputFormat:
输出有若干行。

每行包含两个数字 $a,b$，其中 $a<b$，表示 $\lang a,b\rang$ 是 key road。

请注意：输出时，所有的数对 $\lang a,b\rang$ 必须按照 $a$ 从小到大排序输出；如果$a$ 相同，则根据 $b$ 从小到大排序。


title: 选书

description:
学校放寒假时，信息学奥赛辅导老师有 $1,2,3,\cdots,x$ 本书，要分给参加培训的 $x$ 个人，每人只能选一本书，但是每人有两本喜欢的书。

老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。

inputFormat:
第 $1$ 行一个数 $x$。

第 $2$ 行至第 $1+x$ 行，每行两个数，表示 $a_i$ 喜欢的书的序号。

outputFormat: 只有一个数，总方案数 $\mathit{total}$。

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

对于全部数据，$1\le x\le 20$。

$\text{update 2022/03/07}$，阮行止

本题原始数据中，最后一个数据点的 x 为 $0$，期望输出为  $0$。考虑到这个数据不合理，予以删去。现在提交这个题目不会遇到 $x=0$ 的数据点。


title: 购物

description: 你就要去购物了，现在你手上有 $N$ 种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出 $1$ 到 $X$ 之间的任意值。

inputFormat: 第一行两个数 $X, N$，以下 $N$ 个数，表示每种硬币的面值。

outputFormat: 最少需要携带的硬币个数，如果无解输出 `-1`。


title: [国家集训队] 拉拉队排练

description:
艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。

拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，$n$ 位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。

一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练。$n$ 个女生从左到右排成一行，每个人手中都举了一个写有 $26$ 个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。

雨荨发现，如果连续的一段女生，有奇数个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。

现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前 $K$ 个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以 $19930726$ 的余数是多少就行了。

inputFormat:
第一行为两个正整数 $n$ 和 $K$，含义如题面所述。

接下来一行为 $n$ 个字符，代表从左到右女生拿的牌子上写的字母。

outputFormat: 输出一个整数，代表题目描述中所写的乘积除以 $19930726$ 的余数，如果总的和谐小群体个数小于 $K$，输出一个整数 $-1$。


title: 数位平方和

description:
定义 $S(n)$ 表示 $n$ 的各个数位的 $k$ 次方的和。

定义 $H(n)$ 为满足 $H(n) \le \min\{n, H(S(n))\}$ 的最大值。

求$\sum_{i=A}^{B} H(i) \bmod (10^7 + 7)$。

inputFormat: 一行三个数 $k, A, B$。


title: 扩散

description:
一个点每过一个单位时间就会向四个方向扩散一个距离，如图。

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

两个点 $a$ 、 $b$ 连通，记作 $e(a,b)$，当且仅当 $a,b$ 的扩散区域有公共部分。连通块的定义是块内的任意两个点 $u,v$ 都必定存在路径 $e(u,a_0),e(a_0,a_1),\cdots,e(a_k,v)$。给定平面上的 $n$ 个点，问最早什么时刻它们形成一个连通块。

inputFormat: 第一行一个数 $n$，以下 $n$ 行，每行一个点坐标。

outputFormat: 一个数，表示最早的时刻所有点形成连通块。

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

对于 $20\%$ 的数据，满足 $1 \le N \le 5;1 \le X_i,Y_i \le 50$。

对于 $100\%$ 的数据，满足 $1 \le N \le 50$，$1 \le X_i,Y_i \le 10^9$。


title: 数7

description:
$1337$ 个人排成一个圈，从 $1$ 号人开始报数，初始方向是 $1,2,3\dots$。如果某个人报的数是 $7$ 的倍数或数字中含有 $7$，那么报数的方向就反一下。问报数字 $X$ 的是第几号人？

**比如初始 $20$ 个数字的情况是：**

| 数字 $X$ | 报的人的编号 |
| :----------: | :----------: |
| $1$ | $1$ |
| $2$ | $2$ |
| $3$ | $3$ |
| $4$ | $4$ |
| $5$ | $5$ |
| $6$ | $6$ |
| $7$ | $7$ |
| $8$ | $6$ |
| $9$ | $5$ |
| $10$ | $4$ |
| $11$ | $3$ |
| $12$ | $2$ |
| $13$ | $1$ |
| $14$ | $1337$ |
| $15$ | $1$ |
| $16$ | $2$ |
| $17$ | $3$ |
| $18$ | $2$ |
| $19$ | $1$ |
| $20$ | $1337$ |

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

outputFormat: 一行一个整数，表示最终报数字 $X$ 的是第几号人。

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

对于 $30\%$ 的数据，满足 $X\leq10^6$；

对于 $90\%$ 的数据，满足 $X\leq10^8$；

对于 $100\%$ 的数据，满足 $X\leq10^9$。


title: 山

description:
给出一座山，如图。

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

现在要在山上的某个部位装一盏灯，使得这座山的任何一个部位都能够被看到。

给出最小的 $y$ 坐标，如图的 `+` 号处就是 $y$ 坐标最小的安装灯的地方。

inputFormat:
第一行一个数 $N$，表示这座山由 $N$ 个点构成；

接下来 $N$ 行从左到右给出了这座山的构造情况，每行两个数 $X_i, Y_i$，表示一个折点，保证 $X_i > X_{i-1}$。

outputFormat: 仅输出一行，为最小的 $y$ 坐标，当你的答案与标准答案相差不超过 $0.01$ 时，则被认为是正确的。


title: 正方形计数

description: 给定平面上 $N$ 个点，你需要计算以其中 $4$ 个点为顶点的正方形的个数。注意这里的正方形边不一定需要和坐标轴平行。

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

接下来 $N$ 行每行两个数，表示点的坐标。

outputFormat: 一个数表示正方形的个数。

hint:
对于 $20\%$ 的数据，满足 $1\leq N\leq 20$。

对于 $100\%$ 的数据，满足 $1\leq N\leq 500$，$-50\leq X_i, Y_i\leq 50$，点不会重合。


title: 前缀单词

description:
一组单词是安全的，当且仅当不存在一个单词是另一个单词的前缀，这样才能保证数据不容易被误解。现在你手上有一个单词集合 $S$，你需要计算有多少个子集是安全的。

注意空集永远是安全的。

inputFormat: 第一行一个数 $n$，表示集合的大小，以下 $n$ 行。每行一个由 $\verb!a!\cdots\verb!z!$ 构成的字符串。

outputFormat: 安全子集的个数。

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

- 对 $30\%$ 的数据，满足 $1 \le n \le 10$。
- 对于 $100\%$ 的数据，满足 $1 \le n \le 50$，字符串长度 $ \le 50$，没有两个字符串是完全相同的。


title: 数列

description:
给定一个长度是 $n$ 的数列 $A$ ，我们称一个数列是完美的，当且仅当对于其任意子段的和都是正的。

现在你有一个操作可以改变数列，选择一个区间 $[l,r]$ 满足 $\sum\limits_{i = l}^r A_i < 0$ ,其中 $1 < l \le r < n$。

令 $S = \sum\limits_{i = l}^r A_i$ ，对于 $A_{l - 1}$ 和 $A_{r + 1}$ 分别加上 $S$，$A_l$ 和 $A_r$ 分别减去 $S$（如果 $l = r$ 就减两次）。问最少几次这样的操作使得最终数列是完美的。

inputFormat:
第 $1$ 行一个数 $n$ ，以下 $n$ 个数。

第 $2$ 行至第 $n + 1$ 行，第 $i$ 行一个数 $A_i$。

outputFormat: 一个数表示最少的操作次数，如果无解输出 $-1$。


title: [USACO04DEC] Cleaning Shifts S

description:
一天有 $T(1\le T\le 10^6)$ 个时段。约翰正打算安排他的 $N(1\le N\le 2.5\times 10^4)$ 只奶牛来值班，打扫打扫牛棚卫生。每只奶牛都有自己的空闲时间段 $ [S_i,E_i](1\le S_i\le E_i\le T)$，只能把空闲的奶牛安排出来值班。而且，每个时间段必需有奶牛在值班。

那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出 $-1$。

outputFormat: 一行，输出最少安排的奶牛数。

hint:
$1\le T\le 10^6$，$N\le 2.5\times 10^4$，$1\le S_i\le E_i\le T$。

$\text{Update On 2023/08/08}$：添加了一组hack数据，详情见[这里](https://www.luogu.com.cn/discuss/613052)。叉掉了时间复杂度为 $\mathcal O(nt)$ 的错解。


title: [USACO04DEC] Bad Cowtractors S

description: 奶牛贝茜被雇去建设 $N(2\le N\le 10^3)$ 个牛棚间的互联网。她已经勘探出 $M(1\le M\le 2\times 10^4)$ 条可建的线路，每条线路连接两个牛棚，而且会花费 $C(1\le C\le 10^5)$。农夫约翰吝啬得很，他希望建设费用最少甚至他都不想给贝茜工钱。贝茜得知工钱要告吹，决定报复。她打算选择建一些线路，把所有牛棚连接在一起，让约翰花费最大。但是她不能造出环来，这样约翰就会发现。

inputFormat:
第 $1$ 行：$N$，$M$。

第 $2$ 到 $M+1$ 行：三个整数，表示一条可能线路的两个端点和费用。

outputFormat: 一行，表示最大的花费。如果不能建成合理的线路，就输出 $-1$。


title: [USACO04DEC] Tree Cutting S

description: 约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了。贝茜很愤怒，打算狠狠报复。她打算破坏刚建成的约翰的网络。约翰的网络是树形的，连接着 $N$ 个牛棚。她打算切断某一个牛棚的电源，使和这个牛棚相连的所有电缆全部中断。之后，就会存在若干子网络。为保证破坏够大，每一个子网的牛棚数不得超过总牛棚数的一半，那哪些牛棚值得破坏呢？

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

第 $2$ 到 $N$ 行：每行输入两个整数，表示一条电缆的两个端点。

outputFormat: 按从小到大的顺序，输出所有值得破坏的牛棚。如果没有一个值得破坏，就输出 `NONE`。


title: [USACO05FEB] Rigging the Bovine Election S

description:
农场被划分为 $5\times 5$ 的格子，每个格子中都有一头奶牛，并且只有荷斯坦（标记为 `H`）和杰西（标记为 `J`）两个品种。如果一头奶牛在另一头上下左右四个格子中的任一格里，我们说它们相连。奶牛要大选了。现在杰西奶牛们想选择 $7$ 头相连的奶牛，划成一个竞选区，使得其中它们品种的奶牛比荷斯坦的多。

要求你编写一个程序求出方案总数。

inputFormat: $5$ 行，表示农场的情况。

outputFormat: 输出划区方案总数。


title: [USACO05FEB] Feed Accounting S

description:
约翰想知道上一船饲料是什么时候运到的。在饲料运到之前，他的牛正好把仓库里原来的饲料全吃光了。他收到运来的 $F1(1\le F1\le 10^6)$ 千克饲料。遗憾的是，他已经不记得这是哪一天的事情了。到第 $D(1\le D\le 2\times 10^3)$ 天为止，仓库里还剩下 $F2(1\le F2\le F1)$ 千克饲料。

约翰养了 $C(1\le C\le 100)$ 头牛，每头牛每天都吃掉恰好 $1$ 千克饲料。由于不同的原因，牛们从某一天开始在仓库吃饲料，又在某一天离开仓库，所以不同的两天可能会有差距很大的饲料消耗量。每头牛在来的那天和离开的那天都在仓库吃饲料。给出今天的日期 $D$，写一个程序，判断饲料**最近**一次运到是在什么时候。今天牛们已经吃过饲料了，并且饲料运到的那天牛们还没有吃过饲料。

**如果最终的答案有多个可能，请输出最大的（即，最近的）那一个。**

inputFormat:
第 $1$ 行：四个整数 $C$，$F1$，$F2$，$D$，用空格隔开。

第 $2$ 到 $C+1$ 行：每行是用空格隔开的两个数字，分别表示一头牛来仓库吃饲料的时间和离开的时间。

outputFormat: 一个正整数，即上一船饲料运到的时间。

hint:
### 样例解释

上一次运来了 $14$ 千克饲料，现在饲料还剩下 $4$ 千克。最近 $10$ 天里，有 $3$ 头牛来吃过饲料。

约翰在第 $6$ 天收到 $14$ 千克饲料，当天吃掉 $2$ 千克，第 $7$ 天吃掉 $2$ 千克，第 $8$ 天吃掉 $3$ 千克，第 $9$ 天吃掉 $2$ 千克，第 $10$ 天吃掉 $1$ 千克，正好还剩 $4$ 千克。

### 数据规模

$1\le F2\le F1\le 10^6$，$1\le D\le 2\times 10^3$，$1\le C\le 100$。


title: [USACO05FEB] Part Acquisition S

description: 奶牛们接到了寻找一种新型挤奶机的任务，为此它们准备依次经过 $N(1\le N\le 5\times 10^4)$ 颗行星，在行星上进行交易。为了方便，奶牛们已经给可能出现的 $K(1\le K\le 10^3)$ 种货物进行了由 $1$ 到 $K$ 的标号。由于这些行星都不是十分发达。没有流通的货币，所以在每个市场里都只能用固定的一种货物去换取另一种货物。奶牛们带着一种上好的饲料从地球出发，希望在使用的物品的种类数量最少的情况下，最终得到所需要的机器。饲料的标号为 $1$，所需要的机器的标号为 $K$。如果任务无法完成，输出 $-1$。

inputFormat:
第 $1$ 行是两个数字 $N$ 和 $K$。

第 $2$ 到 $N+1$ 行，每行是两个数字 $A_i$ 和 $B_i$，表示第 $i$ 颗行星为得到 $A_i$ 愿意提供 $B_i$。

outputFormat: 输出最少经手物品数。

hint:
奶牛们至少需要 $4$ 种不同标号的物品，先用 $1$ 去交换 $3$，再用 $3$ 去交换 $2$，最后用 $2$ 交换得到 $5$。

$1\le N\le 5\times 10^4$，$1\le K\le 10^3$。


title: [USACO05FEB] Secret Milking Machine G

description: 约翰正在制造一台新型的挤奶机，但他不希望别人知道。他希望尽可能久地隐藏这个秘密。他把挤奶机藏在他的农场里，使它不被发现。在挤奶机制造的过程中，他需要去挤奶机所在的地方 $T$ 次。他的农场里有秘密的地道，但约翰只在返回的时候用它。农场被划分成 $N$ 块区域，用 $1$ 到 $200$ 标号。这些区域被 $P$ 条道路连接，每条路有一个小于 $10^6$ 的长度 $L$。两块区域之间可能有多条道路连接。为了减少被发现的可能，约翰不会两次经过农场上的任何一条道路。当然了，他希望走最短的路。请帮助约翰寻找这 $T$ 次从仓库走到挤奶机所在地的路线。仓库是区域 $1$，挤奶机所在地是区域 $N$。我们现在要求的是约翰经过的这些道路中最长的路的长度最小是多少，当然他不能重复走某一条路。请注意，我们要求的不是最短的总路程长度，而是所经过的直接连接两个区域的道路中最长的道路的最小长度。数据保证约翰可以找到 $T$ 条没有重复的从仓库到挤奶机所在区域的路。

inputFormat:
第 $1$ 行是 $3$ 个整数 $N$、$P$ 和 $T$，用空格隔开。

第 $2$ 到 $P+1$ 行，每行包括 $3$ 个整数，$A_i$，$B_i$，$L_i$。表示区域 $A_i$、$B_i$ 之间有一条长度为 $L_i$ 的道路。

outputFormat: 输出只有一行，包含一个整数，即约翰经过的这些道路中最长的路的最小长度。

hint:
选择 $1-2-3-7$ 和 $1-6-7$ 两条路线．这些路线中最长路的最小长度是 $5$。

对于 $100\%$ 的数据满足：$2\le N\le 200$，$1\le P\le 4\times 10^4$，$1\le T\le 200$，每条路的长度 $\le 10^6$。


title: [USACO05FEB] Jersey Politics G

description:
在 Wisconsin（地名），有 $3 \times k$ 个城市，依次标号为 $1, 2, \cdots, 3 \times k$，每个城市共有 $1000$ 头奶牛。Jersey（人名）在这些城市中各占有 $w _ 1, w _ 2, \cdots, w _ {3 \times k}$（$0 \leq w _ i \leq 1000$）头奶牛。

你需要将这些城市平分为 $3$ 组。显然，此时每组城市中总共有 $1000 \times k$ 头奶牛。

你需要保证，在至少两组城市中，Jersey 占有的奶牛总数**严格大于** $1000 \times k$ 的一半。

求一种可行的分配方案。

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

然后 $3\times k$ 行，一行一个整数 $w_i$。

outputFormat: 输出有三组，第 $i$ 组输出 $k$ 行，表示第 $i$ 个区域的城市编号。

hint:
可能会有多组解，输出任意一组即可。

$1\le k\le 60$。


title: [USACO05FEB] Aggressive cows G

description:
农夫约翰建造了一座有 $n$ 间牛舍的小屋，牛舍排在一条直线上，第 $i$ 间牛舍在 $x_i$ 的位置，但是约翰的 $m$ 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

inputFormat:
第一行用空格分隔的两个整数 $n$ 和 $m$；

第二行为 $n$ 个用空格隔开的整数，表示位置 $x_i$。

outputFormat: 一行一个整数，表示最大的最小距离值。

hint:
把牛放在 $1$，$4$，$8$ 这三个位置，距离是 $3$。容易证明最小距离已经最大。

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$0 \le x_i \le 10^9$，$2 \le m \le n$。

不保证 $a$ 数组单调递增。


title: 烦恼的高考志愿

background: 计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

description:
现有 $m$ 所学校，每所学校预计分数线是 $a_i$。有 $n$ 位学生，估分分别为 $b_i$。

根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

inputFormat:
第一行读入两个整数 $m,n$。$m$ 表示学校数，$n$ 表示学生数。

第二行共有 $m$ 个数，表示 $m$ 个学校的预计录取分数。第三行有 $n$ 个数，表示 $n$ 个学生的估分成绩。

outputFormat: 输出一行，为最小的不满度之和。

hint:
数据范围：

对于 $30\%$ 的数据，$1\leq n,m\leq1000$，估分和录取线 $\leq10000$；

对于 $100\%$ 的数据，$1\leq n,m\leq100000$，估分和录取线 $\leq 1000000$ 且均为非负整数。


title: 神奇的四次方数

background: 在你的帮助下，v 神终于帮同学找到了最合适的大学，接下来就要通知同学了。在班级里负责联络网的是 dm 同学，于是 v 神便找到了 dm 同学，可 dm 同学正在忙于研究一道有趣的数学题，为了请 dm 出山，v 神只好请你帮忙解决这道题了。

description: 将一个整数 $m$ 分解为 $n$ 个四次方数的和的形式，要求 $n$ 最小。例如，当 $m=706$ 时，因为 $706=5^4+3^4$，所以有 $n=2$。可以证明此时 $n$ 最小。

inputFormat: 一行，一个整数 $m$。

outputFormat: 一行，一个整数 $n$。


title: 奇怪的分组

background: 终于解出了 dm 同学的难题，dm 同学同意帮 v 神联络。可 dm 同学有个习惯，就是联络同学的时候喜欢分组联络，而且分组的方式也很特别，要求第 $i$ 组的的人数必须大于他指定的个数 $C_i$。在 dm 同学联络的时候，v 神在想，按照 dm 同学的规则一共可以有多少种方案呢？他想啊想，终于……没想出来。于是他又想到了聪明的你，你能帮 v 神算出按照 dm 同学的规则有多少种分组方案吗？

description: v 神的班级共有 $N$ 个人，dm 同学想把同学分成 $M$ 组联络，要求第 $i$ 组的人数必须大于给定的正整数 $C_i$，求有多少不同的方案（两个是相同的方案当且仅当对于任意的一队 $i$，两个方案的第 $i$组同学数量相等）。由于结果很大，所以你只需要输出模 $10^9+7$ 的值。

inputFormat: 第一行两个整数 $N$ 和 $M$，后面有 $M$ 行，每行一个整数，表示 $C_i$。

outputFormat: 仅有一行，一个整数，方案数模 $10^9+7$ 的值。


title: 最大正方形II

background: 忙完了学校的事，v 神终于可以做他的“正事”：陪女朋友散步。一天，他和女朋友走着走着，不知不觉就来到了一个千里无烟的地方。v 神正要往回走，如发现了一块牌子，牌子上有有一行小字和一张图，小字说道：“找到图上最大的交错正方形之后和我联系，这块地就是你的了。”在房价疯长的年代，v 神当然不愿错过这个机会，于是开始找了起来……以 v 神的能力当然找不出来了，你能帮 v 神找出来吗？

description: 图上有一个矩阵，由 $N\times M$ 个格子组成，这些格子由两种颜色构成，黑色和白色。请找到面积最大的且内部是黑白交错（即两个相连的正方形颜色不能相同）的正方形。

inputFormat: 第一行两个整数 $N$ 和 $M$，分别表示行数和列数。接下来有 $N$ 行，每行 $M$ 个数，$0$ 或 $1$ 分别表示这个格子是黑色或白色。

outputFormat: 仅有一行，表示满足条件最大正方形的边长。


title: 过家家

description:
有 $2n$ 个小学生来玩过家家游戏，其中有 $n$ 个男生，编号为 $1$ 到 $n$，另外 $n$ 个女生，编号也是 $1$ 到 $n$。每一个女生可以选择一个和她不吵嘴的男生来玩，除此之外，如果编号为 $X$ 的女生的朋友（也是女生，且编号为 $Y$）不和编号为 $Z$ 的男生吵嘴，那么 $X$ 也可以选择 $Z$。此外，朋友关系是可以传递的，比如 $a$ 和 $b$ 是朋友，$b$ 和 $c$ 是朋友，那么我们可以认为 $a$ 和 $c$ 也是朋友。注意，一个男生可以被多个女生选择为玩伴。

当每一位女生都选择了玩伴，那么他们会开始新一轮游戏。在每一轮后，每个女生都会开始去找一个新的男生做玩伴（以前没选过）。而且每一个女生最多能强制 $k$ 个男生接受，无论他们以前是否吵嘴。

现在你的任务就是确定这 $2n$ 个小学生最多能玩几轮游戏。

inputFormat:
第一行有四个整数 $n,m,k,f$（$3 \le n \le 250$，$0 < m < n^{2}$，$0 \le f < n$）。

$n$ 表示有 $2n$ 个小学生，其中 $n$ 个男生 $n$ 个女生。

接下来 $m$ 行，每行包含两个数字 $a,b$ 表示编号为 $a$ 的女生和编号为 $b$ 的男生从没吵嘴过。

再接下来 $f$ 行，每行包含两个数字 $c,d$ 表示编号为 $c$ 的女生和编号为 $d$ 的女生是朋友。

outputFormat: 对于每组数据，输出一个整数，表示 $2n$ 个小学生最多能玩几轮。


title: 入门

description:
不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。

由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。

注意：瓷砖可以重复走过，但不能重复计数。

inputFormat:
第一行两个正整数 $W$ 和 $H$，分别表示小路的宽度和长度。

以下 $H$ 行为一个 $H\times W$ 的字符矩阵。每一个字符代表一块瓷砖。其中，`.` 代表安全的砖，`#` 代表不安全的砖，`@` 代表第一块砖。

outputFormat: 输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）。

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

对于全部的测试点，保证 $1 \leq W,H\le 20$。


title: 考验

description:
大家知道，黄药师不仅武功高超，而且酷爱音乐和诗歌。看到桃花岛来了个新客人，而且不是靠真武功进来的，就准备为难为难你。

他写了一首 $N$ 行诗句的诗歌，美中不足的是这些诗句并不押韵，黄药师非常想遵循古诗的押韵。诗歌被分为若干段，每段都是四行诗。每一句诗都有一个韵脚，假如 $A$ 和 $B$ 表示两种不同的韵脚，每段四行诗的韵脚只可能是 `AABB`，`ABAB`，`ABBA` 和 `AAAA` 中的一种。

黄药师将诗句的韵脚都编了号，具有相同编号的句子代表有相同的韵脚。现在，黄药师想删掉一些句子，使得剩下的都是遵循押韵规则的四行诗，而且不允许改变诗句的顺序。

现在就问你：如何找出满足条件最长的诗歌？

inputFormat:
第 $1$ 行为一个整数 $N\ (1 \le N \le 4000)$，代表黄药师写的诗歌的句子数。

第 $2$ 行为 $N$ 个整数，分别表示每一行诗的韵脚，这些数字都是不超过 $10^9$ 的正数，每个数之间用 $1$ 个空格隔开。

outputFormat: 一行一个整数k，为黄药师最多能够得到的四行诗个数。


title: 游览

description:
顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！

你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。

我们把桃花岛抽象成了一个图，共 $n$ 个点代表路的相交处，$m$ 条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。

你的任务是：把所有不同的路线游览完一共要花多少时间？

inputFormat:
第一行为 $5$ 个整数 $n,m,s,t,t_0$，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从 $1$ 到 $n$）和你乘船从岛东头到西头一次的时间。

以下 $m$ 行，每行 $3$ 个整数 $x,y,t$，表示从点 $x$ 到点 $y$ 有一条行走耗时为 $t$ 的路。

每一行的多个数据之间用一个空格隔开。

outputFormat: 假设总耗时为 $total$，则输出 $total\ \bmod 10000$ 的值（$total$ 对 $10000$ 取余）。


title: 挑战

description:
桃花岛其实也没什么好玩的，黄蓉经常偷偷跑到江湖上与洪七公等人玩。于是，黄药师就经常想一些游戏与女儿玩，为了是把黄蓉留在身边，江湖险恶啊！

这次黄药师又想了一种模拟游戏，游戏是这样的：她把整个桃花岛划分成一个坐标系。游戏开始前，黄蓉站在平面坐标系的一个点上，而她的闺房在坐标系的另一个点上，任何时候，她可以从当前所在点跨一步达到她周围的上、下、左、右四个点，黄药师不断地说四个字“东（E）”、“南（S）”、“西（W）”、“北（N）”，则黄蓉就想象着不断地从一个点走到另一个点，直至到自己的闺房为止。

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

比如，黄蓉开始时站在 $\rm A$ 点，她的家在 $\rm B$ 点，黄药师连续说了一串：$\verb!NNNENNWWWSSW!$，则走了如下一个线路。然后，黄药师会问黄蓉：中间有没有走“弯路”了？即有没有捷径好走？比如，下图中就有多条捷径，可以从 $\rm C$ 走 $\verb!NN!$ 而到 $\rm E$，或走 $\verb!WW!$ 直接到 $\rm D$。

注意：捷径必须是直线。

黄药师听说你是一个程序设计高手，就想请你编个程序帮他测测这个游戏的难度，以便改进游戏规则后再让黄蓉挑战。

你的任务是：找一条最短的捷径。

inputFormat:
第一行是一个整数 $n$（$3\le n\le 2.5\times 10^5$）表示黄药师所报出的字符串长度。

第二行是一个由 $\verb!N!,\verb!E!,\verb!S!,\verb!W!$ 组成的字符串，都是大写字母且中间没有空格。

我们把游戏的起点记为 $0$，把黄蓉的闺房（即游戏的终点）记为 $n$，中间的每一个落脚点都依次标记一个自然数。

outputFormat:
输出只有一行，由 $3$ 个数字和 $1$ 个字符组成，中间用1个空格隔开。

- 第 $1$ 个数字表示最短捷径的长度。
- 第 $2$ 个数字表示最短捷径的开始点。
- 第 $3$ 个数字表示最短捷径的结束点。
- 最后一个字符表示最短捷径的方向（同样用 $\verb!N!,\verb!E!,\verb!S!,\verb!W!$ 中的一个表示）。

如果最短捷径存在多个解，那么输出开始点标号最小的那一条。如果仍然有多个解，那么输出结束点标号最大的。数据保证一定存在满足条件的最短捷径。


title: 机器人小Q

description: 成功派送完这个大单后，餐厅决定引入一名新成员：机器人小 Q。小 Q 的到来让餐厅的客源增加了不少，但是，一段时间之后，新的问题又出现了，小 Q 和我们可不一样，如果要让他工作的话，我们得给他输入能量以保持体力，而小 Q 的能量菜单表上已经按一定顺序给出了 $N$ 个单位的能量值，但是每个单位的能量由于来源不同，需要消耗一定的时间摄入。已知小 Q 每天充电的时间上限值为 $119$，如果时间超出的话就会自动崩溃，大家都想让小 Q 留下来，经过研究之后，决定派 HWX 和 XYF 去和老板谈判，考虑角度不一样，LXC 老板才不想听什么辛酸流泪史，他只想知道，若是想让小 Q 获得 $k$ 单位的能量（也就是能量表中可以不接受某些能量）最少需要几天来充电。

inputFormat:
第一行，两个整数，$N,K$ 分别表示小 Q 的能量菜单上有 $N$ 个单位的能量，想获取其中的 $k$ 个。

第二行，$N$个整数，分别是第 $i$ 个单位能量需要的充电时间。

outputFormat:
仅一行，一个整数，为最少需要天数。

如果永远不能达到题目要求，输出 `You can't do it.`

hint:
### 样例解释

只接收 $1,1,118$。显然这需要 $2$ 天。

### 数据规模

对于 $30\%$ 的数据，有 $1\le K\le N\le 20$。

对于 $100\%$ 的数据，有 $1\le K\le N\le 3000$。


title: 新单词接龙问题

description:
给定一个包含 $n$ 个单词的字典，从中选择若干个单词，按字典序进行单词接龙，使得接龙的长度最大。

新单词接龙的规则：

1. 单词变换：单词 $w_i$ 添加一个字母，删除一个字母，或修改一个字母可以得到单词 $w_i+1$；
2. 字典序接龙：$w_1,w_2,\cdots,w_n$，满足字典序。

inputFormat: 第一行一个整数 $n$（$1 \le n \le 25,000$），表示字典中单词的总数。接下来 $n$ 行，按字典序输入 $n$ 个单词，每行一个字符串，表示单词，单词仅由小写字母组成，长度在 $1$ 至 $16$ 以内。

outputFormat: 输出一行一个整数，表示能获得的单词接龙的最大长度。

hint:
### 样例解释

长度为 $5$ 的单词接龙为：$\texttt{dig\underline afigafin\underline afine\underline awine}$。


title: 方程求解

description: 给一个方程，形如 $X+Y=Z$ 或 $X-Y=Z$。给出了其中两个未知数，请求出第三个数。未知数用 `?` 表示，等式中也许会出现一些多余的空格。

inputFormat: 输入一行一个字符出代表方程。

outputFormat: 一行一个整数表示`?`代表的值。

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

对于 $100\%$ 的数，保证 $0\le X,Y,Z\lt10^9$，输入的字符串一定为题目给定的形式且长度不超过 $10^6$。


title: 贪婪的Copy

description: Copy 从卢牛那里听说在一片叫 yz 的神的领域埋藏着不少宝藏，于是 Copy 来到了这个被划分为 $n$ 个区域的神地。卢牛告诉了Copy这里共有 $n$ 个宝藏，分别放在第 $P_i$ 个 $(1\le P_i\le N)$ 区域。Copy还得知了每个区域之间的距离。现在 Copy 从 $1$ 号区域出发，要获得所有的宝藏并到 $n$ 号区域离开。Copy 很懒，只好来找你为他寻找一条合适的线路，使得他走过的距离最短。

inputFormat:
第一行一个正整数 $N(1\le N\le 100)$

接下来一个 $N\times N$ 的矩阵，第 $i+1$ 行第 $j$ 列的数字表示区域 $i,j$ 之间的距离。每个距离用空格隔开，距离保证 $i\to j\le 1000$。请注意的 $i \to j$ 距离并不一定等于 $j \to i$ 的距离。

第 $N+2$ 行一个整数 $P(0\le P\le 10)$。

第 $N+3$ 行共 $P$ 个用空格隔开的整数，表示有宝藏的区域编号。

outputFormat: 一个整数，为 Copy 获得全部宝藏需要的最短距离。数据保证答案小于等于 maxlongint。

hint:
- 对 $30\%$ 的数据，$1\le n\le 15$，其余如题所述。
- 对 $100\%$ 的数据，全部数据范围如题所述。


title: 部落卫队

description:
原始部落 byteland 中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何 $2$ 个人都不是仇敌。

给定 byteland 部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。若有多种方案可行，输出字典序最大的方案。

inputFormat: 第 $1$ 行有 $2$ 个正整数 $n$ 和 $m$，表示 byteland 部落中有 $n$ 个居民，居民间有 $m$ 个仇敌关系。居民编号为 $1,2, \cdots ,n$。接下来的 $m$ 行中，每行有 $2$ 个正整数 $u$ 和 $v$，表示居民 $u$ 与居民 $v$ 是仇敌。

outputFormat: 第 $1$ 行是部落卫队的人数；文件的第 $2$ 行是卫队组成 $x_i$，$1 \le i \le n$，$x_i=0$ 表示居民 $i$ 不在卫队中，$x_i=1$ 表示居民 $i$ 在卫队中。

hint:
对于 $60\%$ 数据：$n \le 20$，$m \le 100$。

对于所有数据：$n \le 100,m \le 3000$。数据从所有合法数据从随机均匀取样。


title: 突击考试

description: 一日，老师决定进行一次突击考试。已知每个学生都有一个考试能力等级，教室里一共有 $N$ 个课桌，按照顺序排成一列，每张课桌可以坐两个人，第 $i$ 张课桌坐的两个人的能力等级为$A_i,B_i$。现在老师决定对能力等级为 $K$ 的人进行测验。他会从这 $N$ 排中选择连续的 $L$ 排进行测验，要求这 $L$ 排中的每一排至少有一个人考试能力等级为 $K$。现在我们想知道 $L$ 的最大值以及对应的等级 $K$。

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

第 $2$ 至第 $N+1$ 行：每行两个整数，表示 $A_i,B_i$。

outputFormat: 两个整数 $L$ 和 $K$，要求在 $L$ 最大的条件下 $K$ 最小。

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

对于全部数据，$1 \le N \le 100,000$，$1 \le A[i],B[i] \le 5$。


title: 那个什么密码2

background: 原题为 https://www.luogu.com.cn/problem/P1079。

description: 与原题一模一样、具体不同请见输入格式

inputFormat:
第一行输入密钥

第二行输入明文

第三行输入一个正整数 $M$, 代表操作个数.

每个操作将 $[a,b]$ 的字符全部倒转，比如 abc 倒转为 cba.

接下来 $M$ 行，每行输入两个正整数 $a$, $b$。

outputFormat: 输出一行,输出密文。

hint: 由 zxy 大神原创、本人在洛谷上传。


title: 寻找最优美做题曲线

background: nodgd 是一个喜欢写程序的同学，前不久（好像还是有点久了）洛谷 OJ 横空出世，nodgd 同学当然第一时间来到洛谷 OJ 刷题。于是发生了一系列有趣的事情，他就打算用这些事情来出题恶心大家……

description:
洛谷 OJ 刷题有个有趣的评测功能，就是系统自动绘制出用户的“做题曲线”。所谓做题曲线就是一条曲线，或者说是折线，是这样定义的：假设某用户在第 $b_i$ 天 AC 了 $c_i$ 道题，并且 $b_i$ 严格递增，那么该用户的做题曲线就是平面上点 $(i,c_i)$ 依次连出的一条折线。比如你在第 $1$ 天做了 $3$ 道题，第 $3$ 天做了 $4$ 道题，第 $6$ 天做了 $1$ 道题，那么你在前 $6$ 天的做题曲线就是从点 $(1,3)$ 到点 $(2,4)$ 到点 $(3,1)$ 的连续折线。

nodgd 同学可以预测出自己未来 $N$ 天每条能够 $AC$ 题目的数量，同时有一个很无趣的爱好，就是单调递增，nodgd 强迫自己的做题曲线保持严格的单调递增。但是出于某些原因，nodgd 在某些日子（共有 $K$ 天）必须刷题，而且刷题数量一定是预计的数量（体现 nodgd 的神预测）。nodgd 同学想知道，在这样的情况下，自己最多有多少天可以刷题，不过 nodgd 同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题……要做，就拜托你来帮他算算了。

inputFormat:
第一行两个正整数，$N$ 和 $K$，表示 nodgd 预测了未来 $N$ 天每天做题的数量，其中 $K$ 天必须刷题。

第二行 $K$ 个正整数 $p_i$，表示第 $p_i$ 天必须刷题 $(1 \le p_i\le N$，保证每个 $p_i$ 不同）。

第三行 $N$ 个正整数 $c_i$，表示在第 $i$ 天 nodgd 可以 $AC$ 的题目数量必须是 $c_i$。

outputFormat:
输出共一行。

如果能找到严格递增的做题曲线：一个正整数，表示 nodgd 最多有多少天可以刷题。

如果找不到严格递增的做题曲线：直接输出 `impossible`（不加引号，全是小写字母）。

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

对于全部数据，

- $1 \le N \le 500000$，$1 \le K \le N/2$；
- $1 \le p[i] \le N$，保证每个 $p[i]$ 不同，不保证 $p[i]$ 按大小顺序输入；
- $1 \le c[i] \le 10^9$。


title: 爱与愁过火

background:
（本道题目隐藏了两首歌名，找找看哪~~~）

《爱与愁的故事第一弹·heartache》第三章。

爱与愁大神说这是ta的伤心指数，只不过现在好很多了，翻译只是看你无聊让你动动脑筋罢了（shit~~~）。虽然月落乌啼嘴上骂着：“我去年买了个表……纽曼表……”，但是结果还是请爱与愁大神去Pizza Hut吃了一顿。

description:
到了 Pizza Hut，爱与愁大神由于不爽，所以存心想坑月落乌啼的钱，他点了 $m$ 样菜，每样菜 $a_i$ 元。月落乌啼预计只用 $n$ 元，于是他让爱与愁大神重新从这 $m$ 样菜中选 $r$ 样。

爱与愁大神还是想坑钱，于是他打电话给你，让你编一个程序告诉他有几种方案可以从 $m$ 样菜中点取 $r$ 样菜但是还能超过月落乌啼的预计 $n$ 元。

inputFormat:
第一行三个数 $m$，$r$，$n$。

第二行 $m$ 个数，每道菜需要的钱 $a_i$，两个数之间有空格。

outputFormat: 只有一个整数，表示方案总数。

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

对于 $100\%$ 数据，$m \le 30$，$r \le m$，$m \le a_i \le 90n \le 2700$。


title: 全排列问题

description: 按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

inputFormat: 一个整数 $n$。

outputFormat:
由 $1 \sim n$ 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 $5$ 个场宽。

hint: $1 \leq n \leq 9$。


title: 刷题比赛

background:
nodgd 是一个喜欢写程序的同学，前不久洛谷 OJ 横空出世，nodgd 同学当然第一时间来到洛谷 OJ 刷题。
于是发生了一系列有趣的事情，他就打算用这些事情来出题恶心大家……

description:
洛谷OJ当然算是好地方，nodgd 同学打算和朋友分享一下。于是他就拉上了他的朋友 Ciocio 和 Nicole 两位同学一起刷题。喜欢比赛的他们当然不放过这样一次刷题比赛的机会！

在第 $1$ 天 nodgd,Coicoi,Nicole 都只做了 $1$ 道题。

在第 $2$ 天 nodgd,Coicoi,Nicole 都只做了 $3$ 道题。

他们都有着严格的刷题规则，并且会在每一天都很遵守规则的刷一定量的题。

1、nodgd 同学第 $k+2$ 天刷题数量
$$a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1$$

2、Ciocio 同学第 $k+2$ 天刷题数量
$$b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k$$

3、Nicole 同学第 $k+2$ 天刷题数量
$$c_{k+2} = xc_{k+1}+yc_k + a_{k+1} + b_{k+1} + z^k+k+2$$

（以上的字母 $p,q,r,t,u,v,w,x,y,z$ 都是给定的常数，并保证是正整数）

于是他们开始了长时间的刷题比赛！一共进行了 $n$ 天

但是时间是可贵的，nodgd 想快速知道第 $n$ 天每个人的刷题数量。
不过 nodgd 同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题…… 要做，就拜托你来帮他算算了。

由于结果很大，输出结果 $\bmod \space m$ 的值即可。

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

第二行四个正整数 $p,q,r,t$。

第三行三个正整数 $u,v,w$。

第四行三个正整数 $x,y,z$。

outputFormat:
共三行，每行一个名字 + 一个空格 + 一个整数。
依次是 nodgd,Ciocio,Nicole 和他们在第 $n$ 天刷题数量 $\bmod \space m$ 的值。


title: [USACO5.5] 隐藏口令 Hidden Password

description:
有时候程序员有很奇怪的方法来隐藏他们的口令。Binny 会选择一个字符串 $S$（由 $N$ 个小写字母组成，$5 \le N \le 5 \times {10}^6$），然后他把 $S$ 顺时针绕成一个圈，每次取一个做开头字母并顺时针依次取字母而组成一个字符串。这样将得到一些字符串，他把它们排序后取出第一个字符串。把这个字符串的第一个字母在原字符串中的位置减 $1$ 做为口令。

如字符串 `alabala`，按操作的到 $7$ 个字符串，排序后得：

`aalabal`

`abalaal`
`alaalab`
`alabala`
`balaala`
`laalaba`
`labalaa`

第一个字符串为 `aalabal`，这个 `a` 在原字符串位置为 $7$，$7-1=6$，则 $6$ 为口令。

inputFormat:
第一行：一个数：$N$

第二行开始：字符串：$S$（每 $72$ 个字符一个换行符）

outputFormat: 一行，为得到的口令

hint:
题目满足：

$30 \%$ 的数据 $n \le {10}^4$。
$70 \%$ 的数据 $n \le {10}^5$。
$100 \%$ 的数据 $1 \le n \le 5 \times {10}^6$。

时限 1s

题目翻译来自NOCOW。

USACO Training Section 5.5

// 20170523 新增数据四组


title: 地铁涨价

description:
博艾市除了有海底高铁连接中国大陆、台湾与日本，市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有 $N$ 个地铁站，同时有 $M$ 小段地铁连接两个不同的站。

地铁计价方式很简单。从 A 站到 B 站，每经过一小段铁路（连接直接相邻的两个点的一条边），就要收取 $1$ 博艾元。也就是说，从 A 站到 B 站，选择的路径不一样，要价也会不同。

我们认为凡华中学在 $1$ 号地铁站。学生们通过地铁通勤，他们当然知道选择最短路来坐车的话，票价最便宜。

然而博艾地铁公司经营不善，一直亏损，于是他们打算提价。提价一次就是将一小段铁路原来收费 $1$ 元改收 $2$ 元。同一小段的铁路不会多次提价。他们打算提价 $Q$ 次。

学生们知道，如果他们到学校的一条最短路径中的一小段提价了，可以改变路径，使总票价不变。然而随着一条一条的铁路被提价，当居住在某个站附近的学生发现，提价后，没有任何一种方案可以从家到学校的费用和初始费用相等时，就会不满。

现在地铁公司希望知道，对于每一次涨价，有多少个站，学生会因为涨价而不满呢？

inputFormat:
第一行为三个整数 $N,M,Q$。

接下来 $M$ 行，每行 $2$ 个整数 $a_i,b_i,$ 表示第 $i$ 条铁路连接的两个站。$i$ 表示铁路编号。

接下来 $Q$ 行，每行一行整数 $r_j$，表示每次涨价的铁路编号。

outputFormat: 输出共 $Q$ 行。每行一个整数表示不满的车站数量。


title: [NOI2016] 区间

description:
在数轴上有 $n$ 个闭区间从 $1$ 至 $n$ 编号，第 $i$ 个闭区间为 $[l_i,r_i]$ 。

现在要从中选出 $m$ 个区间，使得这 $m$ 个区间共同包含至少一个位置。换句话说，就是使得存在一个 $x$ ，使得对于每一个被选中的区间 $[l_i,r_i]$，都有 $l_i \leq x \leq r_i$ 。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。

区间 $[l_i,r_i]$ 的长度定义为 $(r_i-l_i)$ ，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 $-1$。

inputFormat:
第一行包含两个整数，分别代表 $n$ 和 $m$。

第 $2$ 到第 $(n + 1)$ 行，每行两个整数表示一个区间，第 $(i + 1)$ 行的整数 $l_i, r_i$ 分别代表第 $i$ 个区间的左右端点。

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


title: 麦当劳叔叔的难题

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

问题是这样描述的：

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

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

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

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

outputFormat: 仅一行，那个最大的时间差。

hint: $2\le n\le 10$，$0\le m\le 100$，$1\leq x,y\leq n$。


title: 切蛋糕

description:
今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 $n$ 个相同的小块，每小块都有对应的幸运值。

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 $m(m\le n)$ 小块的蛋糕。

请你帮他从这 $n$ 小块中找出**连续**的 $k(1 \le k\le m)$ 块蛋糕，使得其上的总幸运值最大。

**形式化地**，在数列 $\{p_n\}$ 中，找出一个子段 $[l,r](r-l+1\le m)$，最大化 $\sum\limits_{i=l}^rp_i$。

inputFormat:
第一行两个整数 $n,m$。分别代表共有 $n$ 小块蛋糕，小 Z 最多只能吃 $m$ 小块。

第二行 $n$ 个整数，第 $i$ 个整数 $p_i$ 代表第 $i$ 小块蛋糕的幸运值。

outputFormat: 仅一行一个整数，即小 Z 能够得到的最大幸运值。


title: [USACO16DEC] Lots of Triangles P

description:
Farmer John is thinking of selling some of his land to earn a bit of extra income. His property contains $N$ trees ($3 \leq N \leq 300$), each described by a point in the 2D plane, no three of which are collinear. FJ is thinking about selling triangular lots of land defined by having trees at their vertices; there are of course $L = \binom{N}{3}$ such lots he can consider, based on all possible triples of trees on his property.

农民约翰希望通过卖出他拥有的一部分土地来增加收入。他在这片土地上种了$N$棵树($3\le N\le 300$)，每棵树都可以用一个二维网格图上的一个坐标来表示，没有三棵树是共线的。约翰想以3棵树做顶点围成三角形来分割地，以确定地的大小和形状，基于约翰所有树可能组成的三树组合，当然有$L = \binom{N}{3}$种可能考虑分割贩卖的土地切块。

A triangular lot has value $v$ if it contains exactly $v$ trees in its interior (the trees on the corners do not count, and note that there are no trees on the boundaries since no three trees are collinear). For every $v = 0 \ldots N-3$, please help FJ determine how many of his $L$ potential lots have value $v$.

一块分出的三角形土地有价值$v$，$v$的大小决定于土地上树的数量，树的数量=土地价值=v （顶点上的树不算，网格图边界不种树）。当$v=0,1...N-3$时，请帮约翰求出有多少三角形地$L$拥有价值$v$。

inputFormat:
The first line of input contains $N$.

The following $N$ lines contain the $x$ and $y$ coordinates of a single tree; these are both integers in the range $0 \ldots 1,000,000$.

输入的第一行为树的棵数$N$。

接下来的$N$行分别为不同树在二维网格图上的坐标；它们都是介于$0$和$1000000$之间的的整数；行和列数间用空格隔开。

outputFormat:
Output $N-2$ lines, where output line $i$ contains a count of the number of lots having value $i-1$.

输出$N-2$行，其中第$i$行是价值$v$等于$i-1$的土地块数量。


title: 双调序列

description:
电脑组的童鞋们经常玩一些智力 PK 小游戏，某月某日，发源于小朋友又发明了一种新的序列：双调序列，所谓的双调呢主要是满足如下条件描述：

假定有 $n$（$n \le 1000$）个整数（都在 `long int` 范围内，即 $-2147483648 \sim 2147483647$），双调序列的第一个数是 $n$ 个整数中的最大数，第二个数是 $n$ 个整数中的最小数，第三个数是 $n$ 个数中的第二大数，第四个数是 $n$ 个数中的第二小数……取过的数不能再取，依次类推，直到结束。

聪明的你听完描述就抿嘴笑了吧？那就请你用程序正确的帮他找出这 $n$ 个数的双调序列。

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

接下来 $n$ 行给出了题目中所述的 $n$ 个整数，每行包含一个整数。

outputFormat: 有 $n$ 行，每行为一个整数，是满足条件的双调序列


title: 钓鱼

description:
话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽，为了表示安慰和鼓励，VIP999 决定请他吃一次“年年大丰收”，为了表示诚意，他还决定亲自去钓鱼。

但是，因为还要准备 NOIP2013, z 老师只给了他 $H$ 个小时的空余时间，假设有 $n$ 个鱼塘都在一条水平路边，从左边到右编号为 $1,2,3\dots n$ 。

VIP 是个很讲究效率的孩子，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。他测出从第 $i$ 个湖到 $i+1$ 个湖需要走 $5 \times t_i$ 分钟的路，还测出在第 $i$ 个湖边停留，第一个 $5$ 分钟可以钓到鱼 $f_i$，以后再每钓 $5$ 分钟鱼，鱼量减少 $d_i$。为了简化问题，他假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼。请编程求出能钓最多鱼的数量。

inputFormat:
第一行：湖的数量 $n$。

第二行：时间 $h$（小时）。

第三行：$n$ 个数，$f_1,f_2,\dots,f_n$。

第四行：$n$ 个数，$d_1,d_2,\dots,d_n$。

第五行：$n-1$ 个数，$t_1,t_2,\dots,t_{n-1}$

outputFormat: 一个数，所能钓鱼的最大数量。


title: 图形复原

description:
HWX 小朋友对几何的热爱在电脑组是出了名的，号称“每题必解”，这天，LXC 在玩 logo 的时候突然想到了一个题目，刚好可以去测试一下他封号的虚实，于是，他 logo 编程画了一个 $n$ 边形，并且将 $n$ 个顶点用 $1, 2, 3, \ldots, n$ 这 $n$ 个连续自然数随手编了个号，为了增加难度，他又画了一些不相交的对角线。如下图：

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

他把所有的边和对角线都写在一张纸上，对于上图，他写了：$(1, 3)$、$(3, 2)$、$(2, 4)$、$(4, 5)$、$(5, 1)$、$(1, 4)$、$(3, 4)$。正得意的时候，电脑突然自动重启了，郁闷的是，他忘记保存刚才的 logo 程序了，此刻的他很想利用纸上记录的信息将这个 $n$ 边形的编号复原，电脑组的你能帮助他吗？

inputFormat:
第一行 $n$（$n \le 50$）

下面若干行，每行两个数 $a, b$，表示纸上记录的信息。

outputFormat: 仅一行，按字典序较小的顺序依次输出顶点的编号。对于上面的例子，你的输出应该是 `1 3 2 4 5`。


title: 最大加权矩形

description:
为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 $n\times n$ 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 $[-127,127]$ ,例如

```plain
 0 –2 –7  0
 9  2 –6  2
-4  1 –4  1
-1  8  0 –2
```

在左下角：

```plain
9  2
-4  1
-1  8
```

和为 $15$。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

inputFormat: 第一行：$n$，接下来是 $n$ 行 $n$ 列的矩阵。

outputFormat: 最大矩形（子矩阵）的和。


title: 月落乌啼算钱（斐波那契数列）

background:
（本道题目木有隐藏歌曲……不用猜了……）

《爱与愁的故事第一弹·heartache》最终章。

吃完 pizza，月落乌啼知道超出自己的预算了。为了不在爱与愁大神面前献丑，只好还是硬着头皮去算钱……

description:
算完钱后，月落乌啼想着：“你坑我！”于是当爱与愁大神问多少钱时，月落乌啼说了一堆乱码。爱与愁大神说：“算了算了，我只问第 $n$ 样菜价格多少？”月落乌啼写出了：

$$F_n=\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

由于爱与愁大神学过编程，于是就用 $1$ 分钟的时间求出了 $F_n$ 的结果。月落乌啼为此大吃一惊。你能学学爱与愁大神求出 $F_n$ 的值吗？

inputFormat: 一行一个自然数 $n$。

outputFormat: 只有 $1$ 行一个实数 $F_n$，保留两位小数。

hint: 对于所有数据：$0 \leq n\leq 48$。


title: [NOI2016] 国王饮水记

description:
跳蚤国有 $n$ 个城市，伟大的跳蚤国王居住在跳蚤国首都中，即 $1$ 号城市中。

跳蚤国最大的问题就是饮水问题，由于首都中居住的跳蚤实在太多，跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用，这导致跳蚤国王也经常喝不上水。

于是，跳蚤国在每个城市都修建了一个圆柱形水箱，这些水箱完全相同且足够高。一个雨天后，第 $i$ 个城市收集到了高度为 $h_i$ 的水。由于地理和天气因素的影响，任何两个不同城市收集到的水高度互不相同。

跳蚤国王也请来蚂蚁工匠帮忙，建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时，可以指定任意多的城市，将这些城市的水箱用地下连通系统连接起来足够长的时间之后，再将地下连通系统关闭。由连通器原理，这些城市的水箱中的水在这次操作后会到达同一高度，并且这一高度等于指定的各水箱高度的平均值。

由于地下连通系统的复杂性，跳蚤国王至多只能使用 $k$ 次地下连通系统。

跳蚤国王请你告诉他，首都 $1$ 号城市水箱中的水位最高能有多高？

inputFormat:
输入的第一行包含三个正整数 $n,k,p$ 分别表示跳蚤国中城市的数量，跳蚤国王能使用地下连通系统的最多次数，以及你输出的答案要求的精度。$p$ 的含义将在输出格式中解释。

接下来一行包含 $n$ 个正整数，描述城市的水箱在雨后的水位。其中第 $i$ 个正整数 $h_i$ 表示第 $i$ 个城市的水箱的水位。保证 $h_i$ 互不相同，$1 \leq h_i \leq 10^5$。

outputFormat:
仅一行一个实数，表示 $1$ 号城市的水箱中的最高水位。

这个实数只可以包含非负整数部分、小数点和小数部分。其中非负整数部分为必需部分，不加正负号。若有小数部分，则非负整数部分与小数部分之间以一个小数点隔开。若无小数部分，则不加小数点。

你输出的实数在小数点后不能超过 $2p$ 位，建议保留至少 $p$ 位。数据保证参考答案与真实答案的绝对误差小于 $10^{-2p}$。

你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 $10^{-p}$。

如果你的输出与参考答案的绝对误差不小于 $10^{-p}$ 但小于 $10^{-5}$，你可以获得该测试点 $40\%$ 的分数。


title: 矩阵 II

background: usqwedf 改编系列题。

description:
如果你在百忙之中抽空看题，请自动跳到第六行。

众所周知，在中国古代算筹中，红为正，黑为负……

给定一个 $1\times 2n$ 的矩阵（usqwedf：这不是一个 $2n$ 的队列么），现让你自由地放入红色算筹和黑色算筹，使矩阵平衡[即 $\forall i \in[1, 2n]$，$1\sim i$ 格中红色算筹个数大于等于黑色算筹]。

问有多少种方案满足矩阵平衡（注意红色算筹和黑色算筹的数量必须相等）。

inputFormat: 正整数 $n$。

outputFormat: 方案数 $t$ 对 $100$ 取模后的结果。

hint:
样例解释：

- 方案一：红，黑，红，黑

- 方案二：红，红，黑，黑

数据范围：

$1\le n\le 100$


title: 高手过愚人节

background: 高手组织大家过愚人节、联欢会要打出一些横幅。高手想表现得文艺一点，于是他就用一些普通人看不懂的乱码作为横幅内容。但是在这个时候，他也想让横幅更美观。

description: 现在给出 $n$ 个著名的乱七八糟的乱码，高手要知道每条乱码的最美观连续子序列的长度，在高手的心目中，只有回文串才是美观的。这代表着他纯洁的爱情，又有着回环往复的美，最重要的是，对于转回了一年级的高手来说，想要求出这个太难了，因此他找到了你。（OIer 无所不能！）

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

接下来 $n$ 行每行一条乱码。

outputFormat: $n$ 行，每行为对应乱码的最美观子串的长度，即最长回文子串长（但是由于高手听不懂，我们不会这样说）。

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

对于全部数据，$1\le n\le 10$，$1\le |s_i|\le 10^7$。


title: 东风谷早苗

description:
在幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。早苗的新模型可以按照输入的命令进行移动，命令包含 $\verb|E|$、$\verb|S|$、$\verb|W|$、$\verb|N|$ 四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，自然不会只单单执行一个命令，它可以执行命令串。对于输入的命令串，每一秒它会按照命令行动一次。而执行完命令串最后一个命令后，会自动从头开始循环。在 $0$ 时刻时早苗将钢达姆放置在了 $(0,0)$ 的位置，并且输入了命令串。她想要知道 $T$ 秒后钢达姆所在的位置坐标。

假设当前钢达姆的位置是 $(x,y)$。那么对于四种方向的移动，它坐标的改变分别为：

- 向东移动，坐标改变改变为 $(x+1,y)$；
- 向南移动，坐标改变改变为 $(x,y-1)$；
- 向西移动，坐标改变改变为 $(x-1,y)$；
- 向北移动，坐标改变改变为 $(x,y+1)$。

inputFormat:
第一行共一个字符串 $S$，表示早苗输入的命令串，保证至少有 $1$ 个命令。

第二行共一个正整数 $T$。

outputFormat: 第一行有两个整数，表示 $T$ 秒时，钢达姆的坐标。

hint:
用 $|S|$ 表示早苗输入的命令串的长度。

- 对于 $60\%$ 的数据，$T\le 5\times 10^5$，$|S|\le 5\times 10^3$。
- 对于 $100\%$ 的数据，$T \le 2\times 10^9$，$|S|\le  5\times 10^3$。


title: 琪露诺

description:
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。

某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。

小河可以看作一列格子依次编号为 $0$ 到 $N$，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 $i$ 时，她只移动到区间 $[i+L,i+R]$ 中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。

每一个格子都有一个冰冻指数 $A_i$，编号为 $0$ 的格子冰冻指数为 $0$。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 $A_i$。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。

但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。

开始时，琪露诺在编号 $0$ 的格子上，只要她下一步的位置编号大于 $N$ 就算到达对岸。

inputFormat:
第一行三个正整数 $N, L, R$。

第二行共 $N+1$ 个整数，第 $i$ 个数表示编号为 $i-1$ 的格子的冰冻指数 $A_{i-1}$。

outputFormat: 一个整数，表示最大冰冻指数。


title: 上白泽慧音

description:
在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。

人间之里由 $N$ 个村庄（编号为 $1\cdots N$）和 $M$ 条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用 $1$ 和 $2$ 来标记。如果存在由村庄 $A$ 到达村庄 $B$ 的通路，那么我们认为可以从村庄 $A$ 到达村庄 $B$，记为 $(A,B)$。当 $(A,B)$ 和 $(B,A)$ 同时满足时，我们认为 $A,B$ 是绝对连通的，记为 $\langle A,B\rangle$。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄 $X,Y$ 都满足 $\langle X,Y\rangle$。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在 $1,3,4$ 和 $2,5,6$ 这两个最大连通区域时，输出的是 $1,3,4$。

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

第 $2$ 行至第 $M+1$ 行，每行有三个正整数 $a,b,t$。若 $t = 1$ 则表示存在从村庄 $a$ 到 $b$ 的单向道路，若 $t = 2$ 表示村庄 $a,b$ 之间存在双向通行的道路。保证每条道路只出现一次。

outputFormat:
第一行输出 $1$ 个整数，表示最大的绝对连通区域包含的村庄个数。

第二行输出若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。


title: 计算π

background: 《爱与愁的故事第二弹·compute》第一章。

description: 中秋至，博饼声铿锵不断。爱与愁大神兴致勃勃地到学校博饼，结果抱回家的只有一秀二举。爱与愁大神十分生气，打电话给月落乌啼：“喂，帮我算出圆周率小数点后 $n(n \le 10000)$ 位，速度……”然后就挂了电话，也不知道月落乌啼正准备去上课。月落乌啼只好请到了你，让你编一个程序求出圆周率小数点后 $n$ 位。

inputFormat: 只有一行一个整数 $n$。

outputFormat:
输出包含若干行。

第一行一个字符串 $\verb!3.!$；

第二行开始输出圆周率的小数部分。$10$ 个数一个空格，$50$ 个数一次回车。


title: 计算e

background:
《爱与愁的故事第二弹·compute》最终章。

自然对数的底数 $e$ 是一个著名的无理数，其近似值为 $2.718281828\cdots$ 有计算 $e$ 的公式如下：

$$e=\sum_{n=0}^{\infty}\frac{1}{n!}$$

其中 $n!$ 表示 $n$ 的阶乘，即 $n!=1\times 2\times 3\times \cdots \times n$。

description: 月落乌啼竟然这么快就回复了圆周率小数点后10000位？！不可能，他肯定求了别人。爱与愁大神再次为难月落乌啼：“帮我算一算 $e$ 后 $n(n \le 10000)$ 位，速度！！！”月落乌啼想求别人，结果他发现由于刚才跟你通话已经用完了手机的所有电。关键时刻只能靠自己。如果现在你是他，你会怎么编这个程序？

inputFormat: 只有一行：$n$

outputFormat:
若干行。

第一行：$2$.

第二行开始：$e$ 的小数部分。$10$ 个数一个空格，$50$ 个数一次回车。


title: 最小密度路径

description: 给出一张有 $N$ 个点 $M$ 条边的加权有向无环图，接下来有 $Q$ 个询问，每个询问包括 $2$ 个节点 $X$ 和 $Y$，要求算出从 $X$ 到 $Y$ 的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。

inputFormat:
第一行包括两个整数 $N$ 和 $M$。

以下 $M$ 行，每行三个数字 $A,B,W$，表示从 $A$ 到 $B$ 有一条权值为 $W$ 的有向边。

再下一行有一个整数 $Q$。

以下 $Q$ 行，每行一个询问 $X$ 和 $Y$，如题意所诉。

outputFormat: 对于每个询问输出一行，表示该询问的最小密度路径的密度（保留 $3$ 位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。


title: [NOI1999] 生日蛋糕

background: [数据加强版 link](https://www.luogu.com.cn/problem/T148457)

description:
7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 $i$（$1 \leq i \leq M$）层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。当 $i \lt M$ 时，要求 $R_i \gt R_{i+1}$ 且 $H_i \gt H_{i+1}$。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。

请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S=\dfrac{Q}{\pi}$ 最小。

（除 $Q$ 外，以上所有数据皆为正整数）

inputFormat:
第一行为一个整数 $N$（$N \leq 2 \times 10^4$），表示待制作的蛋糕的体积为 $N\pi$。

第二行为 $M$（$M \leq 15$），表示蛋糕的层数为 $M$。

outputFormat: 输出一个整数 $S$，若无解，输出 $0$。


title: [TJOI2011] 序列

description:
一数列 $A=\{a_1,a_2,\ldots,a_n\}$，根据数列 $A$ 计算数列 $B=\{b_1,b_2,\ldots,b_n\}$，其中：

$$
b_i=
\begin{cases}
a_1 &, i=1 \\
\min_{1 \leq j < i}\left|a_i-a_j\right| &, i\gt 1
\end{cases}
$$

求 $\sum\limits^n_{i=1}b_i$。

inputFormat: 第一行是一个正整数 $T$，表示测试数据的组数。接下来有 $T$ 行，每行表示一组测试数据。每行以一个正整数 $n$ 开始，表示数列 $A$ 中元素的个数；然后是 $n$ 个非负整数，依次表示 $a_1,a_2,\ldots,a_n$ 的值。

outputFormat: 对于每组测试数据，输出数列 $B$ 的所有的元素之和。


title: 猜数（IO交互版）

description:
评测机会在区间 $[1,10^9]$ 中选择一个整数，你应该写一个代码来猜测它。你最多可以问评测机 $50$ 个问题。

对于每一次询问，你可以向评测机询问区间 $[1,10^9]$ 中的一个整数，评测机会返回:

 - 0，如果它为答案（即评测机所选的数字），且程序应该在此之后停止询问。
 - -1，如果它小于答案。
 - 1，如果它大于答案。

每次询问，你需要向**标准输出**输出一个 $[1,10^9]$ 中的整数，**然后清空缓冲区**。

你可以使用如下语句来清空缓冲区：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

然后你需要从**标准输入**中输入一个整数，代表评测机返回的结果。

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

设 $n$ 为答案。

- 对于 $50\%$ 的数据，保证 $n \leq 51$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^9$。

[本题交互库](https://www.luogu.com.cn/paste/uaece7av)。

#### 提示

本题参考程序：

```cpp
#include <cstdio>
#include <iostream>

int main() {
  for (int l = 1, r = 1000000000, mid = (l + r) >> 1, res; l <= r; mid = (l + r) >> 1) {
    std::cout << mid << std::endl;
    std::cin >> res;
    if (res == 0) {
      return 0;
    } else if (res == -1) {
      l = mid + 1;
    } else if (res == 1) {
      r = mid - 1;
    } else {
      puts("OvO, I AK IOI"); // this statement will never be executed.
    }
  }
  return 0;
}
```


title: 最大约数和

description: 选取和不超过 $S$ 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

inputFormat: 输入一个正整数 $S$。

outputFormat: 输出最大的约数之和。


title: 字母迷宫

description:
打败了 DIABLO，Mini 进入了迷宫。这是个奇怪的迷宫，迷宫的每一个地点要么有一个用来传送的门，要么是障碍。Mini 现在站在迷宫的原点处，但是眼看远在 $(N,N)$ 的公主就要被转移，Mini 心情焦急万分，为了能最快地到达公主处救出公主，Mini 希望能走一条最快的路径。注意，Mini 可以把迷宫的 $(1,1)$ 或 $(1,N)$ 或 $(N,1)$ 处当作原点。

迷宫里，某些地点会有门，将门激活，Mini 就会被传送到某个地点，当然，魔王 Bill 只创造了三种门，所以迷宫里最多有就只有三种门，而且在这个迷宫中要到达下一个点必须通过门。。（什么逻辑 TUT。。）

在迷宫中，可能会遇到的三种门分别如下：

- 时空之门，Mini 可以往上下左右四个方向中的任意一个方向传送一格；
- 海洋之门，Mini 可以往上下左右四个方向中的任意一个方向传送两格；
- 天堂之门，Mini 需要停留一步，聚气，然后可以往左上左下右上右下四个方向中的任意一个方向传送一格。

当然，使用每一个门都算作一步。

当然还有障碍，如果有障碍，那么这个点没有门且这个点不能被传送到。

但是，魔王 Bill 有可能创造出了一个完全无法到达 $(N,N)$ 的迷宫，所以，当从三个原点出发都无法到达 $(N,N)$ 时，请输出 `No answer`。注意，原点算作一步（Mini 一开始站在 $(1,1)$ 或 $(1,N)$ 或 $(N,1)$ 的位置，然后走一步到原点，所以原点算作一步）。

inputFormat:
第一行一个数 $N$，表示迷宫的大小 $N\times N$。

以下 $N$ 行，每行 $N$ 个字符，表示迷宫的示意图。字符要么是字母 ABC，要么是障碍。

A 表示时空之门，B 表示海洋之门，C 表示天堂之门，障碍用 $*$ 表示。

outputFormat: 输出为 Mini 从原点处走到公主处的最快路径长度。无解输出 `No answer`。


title: 创意吃鱼法

background: 感谢@throusea 贡献的两组数据

description:
回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^\_\*）。她发现，把大池子视为 $01$ 矩阵（$0$ 表示对应位置无鱼，$1$ 表示对应位置有鱼）有助于决定吃鱼策略。

在代表池子的 $01$ 矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。

猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？

inputFormat: 第一行有两个整数 $n$ 和 $m$（$n,m≥1$），描述池塘规模。接下来的 $n$ 行，每行有 $m$ 个数字（非 $0$ 即 $1$）。每两个数字之间用空格隔开。

outputFormat: 只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。


title: [NOI2016] 旷野大计算

background: **提示：若是使用“提交代码”的方式进行提交，在评测时会给程序输入一个数字（1, 2, 3, ..., 10）表示测试点编号，请在程序中直接输出对应测试点的答案。**

description:
随着人类计算机技术的发展，计算机的能力不断提升，让跳蚤国王非常羡慕。

终于有一天，跳蚤国王发布政令：大力发展跳蚤国的计算机产业！然而，跳蚤国尚未进行工业革命，无法制造出电子计算机所需的元器件。但是跳蚤国王想出了一个绝妙的想法：把每只跳蚤作为一个计算节点，每只跳蚤只完成一个特定的小任务。

跳蚤国王带领 $n$ 只跳蚤来到了一片旷野上，把跳蚤作为计算节点在旷野上排列好，并编号为 $1$ 到 $n$。每个计算节点会把某几个（也有可能是 $0$ 个）计算节点的结果作为输入，计算得到输出。除此之外，跳蚤国王还有一个巨型的终端，可以从终端输入和输出数据，这台终端和所有计算节点组成了一台计算机。

记第 $t$ 个计算节点的输出为 $x_t$，该节点的操作可分为以下几种类型：

| 名称 | 操作符（类型） | 操作数 | 计算结果 |
|-|-|-|-|
| 输入节点 | `I` | 无 | 从终端读入一个实数作为 $x_t$ |
| 输出节点 | `O` | $i$ | $x_t = x_i$，并将 $x_t$ 输出到终端 |
| 加法节点 | `+` | $i,j$ | $x_t = x_i+x_j$ |
| 偏移节点 | `C` | $i,c$ | $x_t=x_i+c$ |
| 取反节点 | `-` | $i$ | $x_t=-x_i$ |
| 左移节点 | `<` | $i,k$ | $x_t=x_i\cdot 2^k$ |
| 右移节点 | `>` | $i,k$ | $x_t=x_i\cdot 2^{-k}$ |
| S 型节点 | `S` | $i$ | $x_t=s(x_i)$ |
| 比较节点 | `P` | $i,j$ | $x_t=\begin{cases}-1 &x_i<x_j\\ 0 &x_i=x_j\\1 &x_i>x_j\\\end{cases}$|
| Max 节点 | `M` | $i,j$ | $x_t=\begin{cases}x_i &x_i>x_j\\x_j &x_i \leq x_j\end{cases}$ |
| 乘法节点 | `*` | $i,j$ | $x_t=x_i \cdot x_j$ |

其中，$s(x)$ 的定义如下：（$e$ 为自然常数,其值约为 $2.718281828459045\ldots$）

$$s\left ( x \right )=\frac{1}{1+e^{-x}}$$

$s(x)$ 的函数图像如下图所示：

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

上述表格中的操作数 $i,j$ 均要小于当前节点的编号 $t$，这样随着跳蚤国王的一声令下，跳蚤就可以按编号从小到大的顺序，依次获得输入然后计算输出。每个跳蚤的计算能力都是有限的，他们仅可以精确到十进制小数点后 $90$ 位，超过的部分将会被四舍五入。同理，上述表格中的操作数 $c$ 的小数部分也不能超过 $90$ 位。另外，左移节点和右移节点中的操作数 $k$ 必须是非负整数，且不能超过 $10^4$。

把跳蚤排列好后，野心勃勃的跳蚤国王决心测试一下这台由跳蚤组成的计算机的计算能力，于是蝈蝈大臣给跳蚤国王献上了十个计算任务。完成每个计算任务均需要从终端获取输入，进行中间计算，再用输出节点将结果输出。具体任务说明如下：

| 编号 | 输入 | 输入限制 | 输出 |
|-|-|-|-|
| $1$ | $a,b$ | $\lvert a \rvert, \lvert b \rvert \le 10^9$，小数部分不超过 $9$ 位 | $-2a-2b$ |
| $2$ | $a$ | $\lvert a \rvert \le 10^9$，小数部分不超过 $9$ 位 | $\dfrac{1}{1+e^{17a}}$ |
| $3$ | $a$ | $\lvert a \rvert \le 10^9$，小数部分不超过 $9$ 位 | $\begin{cases}-1 & a \lt 0 \\ 0 & a = 0 \\ 1 & a \gt 0\end{cases}$ |
| $4$ | $a$ | $\lvert a \rvert \le 10^9$，小数部分不超过 $9$ 位 | $\lvert a \rvert$，即 $a$ 的绝对值 |
| $5$ | $a_1, \dots, a_{32}$ | $a_1, \dots, a_{32} \in \{0, 1\}$ | 把 $a_1, \dots, a_{32}$ 从左到右看成一个二进制整数，高位在左低位在右，输出该整数的值 |
| $6$ | $a$ | $0 \le a \lt 2^{32}$，$a$ 为整数 | 输出 $32$ 个整数，从高位到低位输出 $a$ 的二进制表示（不足 $32$ 位的在高位补 $0$） |
| $7$ | $a,b$ | $0 \le a, b \lt 2^{32}$，$a,b$ 均为整数 | $a, b$ 按位异或的结果 |
| $8$ | $a$ | $\lvert a \rvert \le 10^9$，小数部分不超过 $9$ 位 | $\dfrac{a}{10}$ |
| $9$ | $a_1, \dots, a_{16}$ | $\lvert a_1 \rvert, \dots, \lvert a_{16} \rvert \le 10^9$，小数部分不超过 $9$ 位 | 输出 $16$ 个实数，表示 $a_1, \dots, a_{16}$ 从小到大排序后的结果 |
| $10$ | $a,b,m$ | $0 \le a, b \lt 2^{32}$，$1 \le m \lt 2^{32}$，$a,b,m$ 均为整数 | $a \cdot b$ 除以 $m$ 的余数 |

跳蚤国王发现自己没有足够的能力设计这样的计算机。于是他找到了来参加 NOI 的你。请你依次设计每个计算节点的类型及操作数，完成蝈蝈大臣给的这 10 个计算任务，且要求使用的计算节点数尽量少。

inputFormat:
所有输入数据 `nodes1.in` $\sim$ `nodes10.in`，分别对应 10 个计算任务。

每组输入数据仅包含一个整数，表示需要解决的计算任务编号。

因只供评测机内部使用，洛谷不提供本题输入数据的下载，若有需要请自行生成。

outputFormat:
输出文件为 `nodes1.out` $\sim$ `nodes10.out`，分别对应相应的输入文件。

对于每组输入数据，你需要依次输出若干行，第 $i$ 行描述第 $i$ 个计算节点。

描述每个计算节点时，首先一个字符表示该计算节点的类型，接下来若干个数按顺序表示该计算节点的内置参数。字符与数，数与数之间均用空格隔开。

输出的行数不能超过 $10^4$ 行。

hint:
该样例输出为第一个计算任务一个可能的构造。共用了 $10$ 个计算节点，可获得 $3$ 分。

我们提供了十个评分文件 `nodes1.ans` $\sim$ `nodes10.ans`，分别对应每个计算任务。

每个评分文件共 $10$ 行，第 $i$ 行一个评分参数 $w_i$，具体意义将在下面给出。

本题中，每个测试点单独进行评分，每个测试点 $10$ 分。

如果选手的输出格式不合法或者参数不符合题目约定,则得 $0$ 分。

否则，按照以下规则判定选手的输出是否正确：

- 首先测评器会生成若干组输入数据，并将输入数据代入你构造的计算机。
- 如果在代入某一组输入数据时：你构造的计算机的计算过程中，某个计算节点的计算结果的绝对值超过 $10^{1000}$，则得 $0$ 分；
- 你构造的计算机的输出中的某个值与预期的输出值相差超过 $10^{-9}$，则认为你的输出不正确，得 $0$ 分。
- 否则，我们认为你的计算机能完成给定的计算任务，并按照以下规则得分。

对于每个测试点，我们设置了 $10$ 个评分参数 $w_1$,$w_2$,$w_3$,…,$w_9$,$w_{10}$。

假设共使用了 $n$ 个计算节点,你的分数将会由下表给出：

 | 得分 | 条件 | 得分 | 条件 |
| :----------: | :----------: | :----------: | :----------: |
| 10 | $n≤w_{10}$ | 5 | $n≤w_5$ |
| 9 | $n≤w_9$ | 4 | $n≤w_4$ |
| 8 | $n≤w_8$ | 3 | $n≤w_3$ |
| 7 | $n≤w_7$ | 2 | $n≤w_2$ |
| 6 | $n≤w_6$ | 1 | $n≤w_1$ |

若不符合表中所有条件，得 $0$ 分；若符合表中的多个条件，则取分数最高的。

除此之外，使用**比较节点、Max 节点和乘法节点**的代价是极为**昂贵**的。因此，这三种节点**每使用一种**，就会从你这个测试点的得分中**倒扣 $4$ 分**。

注意这里是按使用节点的**种类数**计算扣分，**与使用次数无关**。例如多次使用比较节点，只会扣除 $4$ 分；又如同时使用了比较节点和乘法节点，**即使各只使用了一次，也会扣除 $8$ 分**。

一个测试点至多被扣到 $0$ 分，即使分数不够扣除，也不会出现负数。


title: 洛谷的文件夹

description:
kkksc03 是个非凡的空想家！在短时间内他设想了大量网页，然后总是交给可怜的 lzn 去实现。

洛谷的网页端，有很多文件夹，文件夹还套着文件夹。

例如：$\verb!/luogu/application/controller!$ 表示根目录下有一个名称为 $\verb!luogu!$ 的文件夹，这个文件夹下有一个名称 $\verb!application!$ 的文件夹，其中还有名为 $\verb!controller!$ 的文件夹。

每个路径的第 $1$ 个字符总是 $\verb!/!$，且没有两个连续的 $\verb!/!$，最后的字符不是 $\verb!/!$。所有名称仅包含数字和小写字母。

目前根目录是空的。kkksc03 想好了很多应该有的文件夹路径名。问题是，需要是使这些文件夹都存在，需要新建几个文件夹呢？

inputFormat:
输入文件第 $1$ 行为一个正整数 $N$。

接下来 $N$ 行，每行为一个描述路径的字符串，长度均不超过 $100$。

outputFormat: 输出应包含 $N$ 行，每行 $1$ 个正整数，第 $i$ 行输出若要使第 $1$ 个路径到第 $i$ 个路径存在，最少需要新建多少个文件夹。

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

- 对于 $20\%$ 数据，有 $N \le 20$；
- 对于 $50\%$ 数据，有 $N \le 200$；
- 另有 $30\%$ 数据，有对于所有路径最多存在两个 $\verb!/!$（包含第 $1$ 个字符）；
- 对于所有数据，$N \le 1000$。


title: 表达式括号匹配

description: 假设一个表达式有英文字母（小写）、运算符（`+`、`-`、`*`、`/`）和左右小（圆）括号构成，以 `@` 作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则输出 `YES`；否则输出 `NO`。表达式长度小于 $255$，左圆括号少于 $20$ 个。

inputFormat: 一行：表达式。

outputFormat: 一行：`YES` 或 `NO`。

hint: 表达式长度小于 $255$，左圆括号少于 $20$ 个。


title: Diamond A&B(1)

background: 由于本题较难，将本题拆做两题，分别为 diamond A 以及 diamond B。本题为 Diamond A。

description:
教主上电视了！这个消息绝对是一个爆炸性的新闻。一经传开，大街上瞬间就没人了（都回家看电视去了），商店打烊，工厂停业。大家都把电视机的音量开到最大，教主的声音回响在大街小巷。

小 L 给小 X 慌乱地打开自己家的电视机，发现所有频道都播放的是教主的采访节目（-\_-bbb）。只见电视屏幕上的教主笑意吟吟，给大家出了一道难题：

一个边长为 $n$ 的大菱形被均匀地划分成了 $n\times n$ 个边长为 $1$ 的小菱形组成的网格，但是网格中部分边被抹去了，小 $L$ 想知道，大菱形内有多少个平行四边形，这些平行四边形内不存在边（平行四边形内是空的）。

教主说，如果谁写出了程序，移动用户请将程序发送到 xxxx，联通用户请将程序发送到 xxxx……如果答对这个题，将有机会参加抽奖，大奖将是教主签名的 Orz 教主 T-Shirt 一件！这个奖品太具有诱惑力了。于是你需要编一个程序完成这么一道题。

inputFormat:
输入的第一行为一个正整数 $n$，为大菱形的边长。

以下 $2n$ 行，每行 $2n$ 个字符，字符为空格，$\verb!/!$，$\verb!\!$ 中的一个。

前 $n$ 行，第 $i$ 行中居中有 $2i$ 个字符，这 $2i$ 个字符中位置为奇数的字符只可能为 $\verb!/!$ 或者空格，位置为偶数的字符只可能为 $\verb!\!$ 或空格，若为空格表示这样一条边不存在，其余字符均为空格，描述了大菱形的上半部分。

后 $n$ 行，第 $i$ 行居中有有 $2(n-i+1)$ 个字符，与上半部分类似地描述了菱形的下半部分。

输入文件保证大菱形的轮廓上没有边被抹去。

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

以下 $2\times n+1$ 行，改为矩形后各边的输出，$1$ 表示有边，$0$ 表示无边。


title: Diamond A&B(2)

background: 由于本题较难，将本题拆做两题，分别为 diamond A 以及 diamond B。本题为 Diamond B。

outputFormat: 输出仅包括一个整数，为满足要求的平行四边形个数。


title: 最小圆覆盖

description: 给出 $N$ 个点，让你画一个最小的包含所有点的圆。

inputFormat:
第一行一个整数 $N$ 表示点的个数。

接下来 $N$ 行每行两个实数 $x_i,y_i$ 表示点的坐标。最多两位小数。

outputFormat:
第一行一个实数表示圆的半径。

第二行两个实数表示圆心的坐标。

本题开启 spj，您的答案与标准答案误差不超过 $10^{-9}$ 时，视为正确。


title: 矩阵 III

background: usqwedf 改编系列题。

description: 给定一个 $n\times m$ 的矩阵，问从左上角走到右下角有多少条路径，保留 $17$ 位有效数字（也就是从第 $18$ 位有效数字以后均输出 $0$）。

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

outputFormat: 路径数目 $t$。


title: 采购特价商品

background: 《爱与愁的故事第三弹·shopping》第一章。

description: 中山路店山店海，成了购物狂爱与愁大神的“不归之路”。中山路上有 $n$（$n \leq 100$）家店，每家店的坐标均在 $-10000$ 至 $10000$ 之间。其中的 $m$ 家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗？

inputFormat:
共 $n+m+3$ 行：

第一行：整数 $n$。

接下来 $n$ 行：每行两个整数 $x$ 和 $y$，描述了一家店的坐标。

接下来一行：整数 $m$。

接下来 $m$ 行：每行描述一条通路，由两个整数 $i$ 和 $j$ 组成，表示第 $i$ 家店和第 $j$ 家店之间有通路。

接下来一行：两个整数 $s$ 和 $t$，分别表示原点和目标店。

outputFormat: 仅一行：一个实数（保留两位小数），表示从 $s$ 到 $t$ 的最短路径长度。


title: 离开中山路

background: 《爱与愁的故事第三弹·shopping》最终章。

description: 爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 $x_1,y_1$ 处，车站在 $x_2,y_2$ 处。现在给出一个 $n \times n(n \le 1000)$ 的地图，$0$ 表示马路，$1$ 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 $1$）。你能帮他解决吗？

inputFormat:
第 $1$ 行包含一个数 $n$。

第 $2$ 行到第 $n+1$ 行：整个地图描述（$0$ 表示马路，$1$ 表示店铺，注意两个数之间没有空格）。

第 $n+2$ 行：四个数 $x_1,y_1,x_2,y_2$。

outputFormat: 只有 $1$ 行，即最短到达目的地距离。


title: 好奇怪的游戏

background:
《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。

description:
爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：\*\*\*（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点 $x_1,y_1$ 和 $x_2,y_2$ 上。它们得从点 $x_1,y_1$ 和 $x_2,y_2$ 走到 $(1,1)$。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到 $(1,1)$ 的最少步数，你能帮他解决这个问题么？

注意不能走到 $x$ 或 $y$ 坐标 $\le 0$ 的位置。

inputFormat:
第一行两个整数 $x_1,y_1$。

第二行两个整数 $x_2,y_2$。

outputFormat:
第一行一个整数，表示黑马到 $(1,1)$ 的步数。

第二行一个整数，表示白马到 $(1,1)$ 的步数。


title: H数

description:
所谓 H 数，是指只含有 $2,3,5,7$ 这些质因数的数，如 $630$ 是 H 数，而 $22$ 不是。

现在要求输出第 $n$ 个 H 数，为了方便起见将 $H[1]$ 定为 $1$。已知 $n$ 不超过 $10000$，最后数据在 int64 范围之内。

inputFormat: 一个数 $n$(如题目)

outputFormat: 第 $n$ 个H数

hint: 穷举会爆掉，要用生成法，最好加优化，不然空间复杂度比较大


title: 出栈序列

description: 给定一个由 $n$ 个元素构成的序列，你需要将其中的元素按顺序压入一个大小为 $c$ 的栈并弹出。元素按它们的出栈顺序进行排列，会得到一个新的序列。我们知道，这样的序列会有很多种，请输出所有新序列中第一个元素最小的序列（若第一个元素最小的序列有多个，则令第二个尽可能小；若仍有多个，则令第三个最小，以此类推）。

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

第二行，$n$ 个数，为序列中 $n$ 个元素的值。

outputFormat: 输出 $n$ 个数，为满足要求的序列。


title: 贪吃虫

background: 我们都知道一个很著名的游戏——贪吃蛇。它的一大特点是当前一个食物被吃掉后，后一个食物才会出现。今天我们要做的另一个游戏——贪吃虫也很类似。

description:
贪吃虫有 $k$ 条，在一棵有 $n$ 个节点的树上，每只虫子都在不同的节点上。第一个食物到来时，所有的 $k$ 只虫会从它们当前的位置出发，前往食物的位置。它们的移动遵循如下规则：

- 这棵树上的任何两个节点之间有且仅有一条路，所有的贪吃虫沿着唯一的路径前往食物所在的位置；
- 如果有一只贪吃虫到达了食物所在的位置，食物马上就被吃掉了；
- 如果有另外一只贪吃虫在某一只贪吃虫通往食物的道路上，那么距离食物较远的那只虫子会停止移动，停留在当前的节点上；
- 如果有多只虫子尝试进入同一个节点，只有编号最小的虫子能够到达，其它的贪吃虫停留在它们当前的位置上；
- 吃掉食物的那只虫子会停留在食物的位置上；
- 食物被吃掉之后会出现在树上的另外一个节点上。这时所有的贪吃虫会重新出发，尝试再一次吃掉食物。为了简化过程，我们假设从一个节点移动到相邻的节点需要花费一个单位时间。

inputFormat:
第 $1$ 行一个整数 $n$，表示树上的节点个数。

第 $2$ 至 $N$ 行，第 $i+1$ 行包含了一个两个整数 $:A_i,B_i$，表示从节点 $A_i$ 到节点 $B_i$ 有一条边直接相连。

第 $N+1$ 行有一个整数 $k$，表示树上贪吃虫的个数。

第 $N+2$ 至 $N+1+k$ 行，第 $N+1+i$ 行有一个整数 $P_i$，表示第 $i$ 只贪吃虫开始时的位置，任何两只贪吃虫的初始位置不相同。

第 $N+2+k$ 行：有一个整数 $h$，表示食物一共在树上出现了多少次。

接下来的 $h$ 行，每行一个整数，表示食物依次出现的位置。

outputFormat: 输出一共包含 $k$ 行，第 $i$ 行有两个整数 $C_i$ 和 $D_i$。分别表示第 $i$ 只贪吃虫最终停留的位置和这只贪吃虫吃到食物的次数。

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

对于全部数据，$1 \le n \le 5000$，$1 \le k \le 1000$，$k \le n$，$1 \le h \le 500$。


title: 点菜

description: 有 $n$ 个人到一家餐馆点菜。这家餐馆总共有 $m$ 道菜，每一道菜都有两个属性——美味度和价格。这 $n$ 个人每周都会来一次，每次只会点一道菜或不点。在这 $n$ 个人中，有 $p$ 个人比较挑剔，他们只能接受美味度大于等于一定值的菜；有 $q$ 个人比较贫穷，他们只能点价格小于等于一定值的菜。现在请你计算：这些人至少要来几周，才可能能把餐馆的所有的菜都点过一遍？

inputFormat:
第 $1$ 行，四个正整数 $n,m,p,q$。

第 $2 \sim m+1$ 行，每行两个数，表示菜的美味度和价格。

第 $m+2$ 行 $p$ 个数，表示 $p$ 个挑剔的人分别能接受的菜的美味度的下限。

第 $m+3$ 行 $q$ 个数，表示 $q$ 个贫穷的人分别能点的菜的价格的上限。

outputFormat: 一行一个数，即这些人最少要来的周数。若不论这些人来几周都不可能把菜点过一遍，输出 $-1$。


title: 球迷购票问题

description:
盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。

按售票处规定，每位购票者限购一张门票，且每张票售价为 $50$ 元。在排成长龙的球迷中有 $n$ 个人手持面值 $50$ 元的钱币，另有 $n$ 个人手持面值 $100$ 元的钱币。假设售票处在开始售票时没有零钱。试问这 $2n$ 个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。

例如当 $n=2$ 时，用 A 表示手持 $50$ 元面值的球迷，用 $B$ 表示手持 $100$ 元钱的球迷。则最多可以得到以下两组不同的排队方式，使售票员不至于找不出钱。

- 第一种：$\mathtt{[A,A,B,B]}$；
- 第二种：$\mathtt{[A,B,A,B]}$。

对于给定的 $n$，计算 $2n$ 个球迷有多少种排队方式，可以使售票处不至于找不出钱。

inputFormat: 一个整数，代表 $n$ 的值。

outputFormat: 一个整数，表示方案数。

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

对于全部数据，$0 \le n \le 20$。


title: 斐波那契的拆分

background: 无

description: 已知任意一个正整数都可以拆分为若干个斐波纳契数，现在，让你求出 $n$ 的拆分方法。

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

接下来 $t$ 行，每行一个整数 $n$（如题）。

outputFormat: $t$ 行，每行一个字符串，表示拆分方法（格式：$n=a_1+a_2+a_3+\ldots+a_n$ ），要求从小到大输出。

hint:
若有多组数据，以个数最小的为准，若仍有多组，输出右边尽量大的一组。

对于$100\%$的数据，$t \leq 1000$，$1 \leq n \leq 10^{9}$。


title: [NOI2009] 描边

description:
小 Z 是一位杰出的数学家。聪明的他特别喜欢研究一些数学小问题。

有一天，他在一张纸上选择了 $n$ 个点，并用铅笔将它们两两连接起来，构成 $\dfrac{n(n-1)}{2}$ 条线段。由于铅笔很细，可以认为这些线段的宽度为 $0$。

望着这些线段，小 Z 陷入了冥想中。他认为这些线段中的一部分比较重要，需要进行强调。因此小 Z 拿出了毛笔，将它们重新进行了描边。毛笔画在纸上，会形成一个半径为 $r$ 的圆。在对一条线段进行描边时，毛笔的中心（即圆心）将从线段的一个端点开始，沿着该线段描向另一个端点。下图即为在一张 $4$ 个点的图中，对其中一条线段进行描边强调后的情况。

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

现在，小 Z 非常想知道在描边之后纸面上共有多大面积的区域被强调，你能帮助他解答这个问题么？

inputFormat:
本题是一道提交答案型试题，所有的输入文件 `path1.in` $\sim$ `path10.in` 已在相应目录下。

输入文件请点击 [这里](http://pan.baidu.com/s/1gfeLZqz) 下载。

输入文件的第一行为一个正整数 $n$，表示选择的点的数目。

第二行至第 $n+1$ 行，其中：第 $i+1$ 行中为两个实数 $x_i,y_i$，表示点 $i$ 的坐标为 $(x_i,y_i)$。

第 $n+2$ 行为一个正整数 $m$，表示小 Z 认为比较重要的线段的条数。

第 $n+3$ 行至第 $n+m+2$ 行，每行有两个正整数 $a,b$，表示一条线段。其中 $a,b$ 两个数分别表示该线段的两个端点的编号。

第 $n+m+3$ 行中为一个实数 $r$，表示毛笔在纸上形成的圆的半径。

第 $n+m+4$ 行中为四个实数 $p_1,p_2,p_3,p_4$，即评分使用的参数。

outputFormat: 输出文件 `path*.out` 仅一行一个数，即为描边后被强调区域的总面积。

hint:
每个测试点单独评分。

本题设有 $4$ 个评分参数 $p_1,p_2,p_3,p_4$（$p_1 \lt p_2 \lt p_3 \lt p_4$），已在输入文件中给出。

你的得分将按照如下规则给出：

- 若你的答案与标准答案相差不超过 $p_1$，则该测试点你将得到满分；
- 否则，若你的答案与标准答案相差不超过 $p_2$，则你将得到该测试点 $70\%$ 的分数；
- 否则，若你的答案与标准答案相差不超过 $p_3$，则你将得到该测试点 $40\%$ 的分数；
- 否则，若你的答案与标准答案相差不超过 $p_4$，则你将得到该测试点 $10\%$ 的分数；
- 否则，该测试点你的得分为 $0$。


title: 通天之分组背包

background: 直达通天路·小 A 历险记第二篇

description: 自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

inputFormat:
两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

outputFormat: 一个数，最大的利用价值。

hint: $0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 `int` 范围内。


title: [NOI2009] 管道取珠

description:
管道取珠是小 X 很喜欢的一款游戏。在本题中，我们将考虑该游戏的一个简单改版。游戏画面如图 1 所示：

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

游戏初始时，左侧上下两个管道分别有一定数量的小球（有深色球和浅色球两种类型），而右侧输出管道为空。每一次操作，可以从左侧选择一个管道，并将该管道中最右侧的球推入右边输出管道。

例如：我们首先从下管道中移一个球到输出管道中，将得到图 2 所示的情况。

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

假设上管道中有 $n$ 个球, 下管道中有 $m$ 个球，则整个游戏过程需要进行 $n+m$ 次操作，即将所有左侧管道中的球移入输出管道。最终 $n+m$ 个球在输出管道中从右到左形成输出序列。

爱好数学的小 X 知道，他共有 $\dbinom{n+m}{m}$ 种不同的操作方式，而不同的操作方式可能导致相同的输出序列。举个例子，对于图 3 所示的游戏情形：

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

我们用 A 表示浅色球，B 表示深色球。并设移动上管道右侧球的操作为 U，移动下管道右侧球的操作为 D，则共有 $\binom{2+1}{1}=3$ 种不同的操作方式，分别为 UUD，UDU，DUU；最终在输出管道中形成的输出序列（从右到左）分别为 BAB，BBA，BBA。可以发现后两种操作方式将得到同样的输出序列。

假设最终可能产生的不同种类的输出序列共有 $K$ 种，其中：第 $i$ 种输出序列的产生方式（即不同的操作方式数目）有 $a_i$ 个。聪明的小 X 早已知道，

$$
\sum a_i=\binom{n+m}{m}
$$

因此，小 X 希望计算得到：

$$
\sum a_i^2
$$

你能帮助他计算这个值么？由于这个值可能很大，因此只需要输出该值对 $1024523$ 取模后的结果。

inputFormat:
输入文件中的第一行为两个整数 $n,m$，分别表示上下两个管道中球的数目。

第二行中为一个长度为 $n$ 的字符串，表示上管道中从左到右球的类型。其中：A 表示浅色球，B 表示深色球。

第三行中为一个长度为 $m$ 的字符串，表示下管道中从左到右球的类型。

保证两个字符串都只包含 A,B 两个字母。

outputFormat: 输出一个整数，即为 $\sum a_i^2$ 对 $1024523$ 取模的结果。

hint:
### 样例解释

样例对应图 3。

共有两种不同的输出序列形式，序列 BAB 有 $1$ 种产生方式，而序列 BBA 有 $2$ 种产生方式，因此答案为 $5$。

### 数据范围

- 对于 $30\%$ 的数据，满足 $m,n \leq 12$；
- 对于 $100\%$ 的数据，满足 $1 \leq m,n \leq 500$。


title: 通天之潜水

background: 直达通天路·小 A 历险记第三篇

description: 在猴王的帮助下，小 A 终于走出了这篇荒山，却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船，但好在小 A 有 $n$ 个潜水工具。由于他还要背重重的背包，所以他只能背 $m$ 重的工具，又因为他的力气并不是无限的，河却很宽，所以他只能背有 $v$ 阻力的工具。但是这条河下有非常重要的数据，所以他希望能够停留的时间最久。于是他找到了你，让你告诉他方案。

inputFormat:
三个数 $m, v, n$ 如题目所说。

接下来 $n$ 行，每行三个数 $a_i, b_i, c_i$ 分别表示所含的重力，阻力，能够支撑的时间。

outputFormat:
第一行一个数，表示最长的时间。

接下来一行，若干个数，表示所选的物品。

hint:
对于 $100 \%$ 的数据，$1 \le m, v \le 200$，$1 \le n \le 100$。

数据保证一定有方案。

若有多种方案，输出前面尽量小的方案。


title: 通天之汉诺塔

background: 直达通天路·小A历险记第四篇

description:
在你的帮助下，小 A 成功收集到了宝贵的数据，他终于来到了传说中连接通天路的通天山。但是这距离通天路仍然有一段距离，但是小 A 突然发现他没有地图！！！但是幸运的是，他在山脚下发现了一个宝箱。根据经验判断（小 A 有经验吗？），地图应该就在其中！

在宝箱上，有三根柱子以及在一根柱子上的 $n$ 个圆盘。小 A 在经过很长时间判断后，觉得这就是 hanoi 塔！（这都要琢磨）。但是移动是需要时间的，所以小 A 必须要通过制造延寿药水来完成这项任务。现在，他请你告诉他需要多少步完成，以便他造足够的延寿药水。

inputFormat: 一个数 $n$，表示有 $n$ 个圆盘。

outputFormat: 一个数 $s$，表示需要 $s$ 步。

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

对于所有数据，$n \le 15000$。


title: 正方形

description: 有 $n$ 个大小不一的正方形，现将它们依次以 $45$ 度斜放入第一象限，每个正方形都要与 $x$ 轴有一个交点，且不能与之前放入的正方形重叠。在此前提下，正方形与 $x$ 轴交点的坐标应尽可能小。问这样放置后，从上往下看，至少能部分被看见的正方形有哪些？

inputFormat: 每个测试点包含多组测试数据。每个测试数据的第一行是一个整数 $n$，第二行是 $n$ 个正整数，表示每个正方形的边长。输入以一行单独的 $0$ 结束。

outputFormat: 对于每个测试数据输出一行，增序输出至少可看到部分的正方形的编号，用空格隔开。

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

### 数据范围及约定

- 对于 $50\%$ 的数据，$n \le 10$；
- 对于 $100\%$ 的数据，$n \le 50$ 正方形的大小不超过 $30$。


title: 偶数

description: 给定一个正整数 $n$，请输出杨辉三角形前 $n$ 行的偶数个数对 $1000003$ 取模后的结果。

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

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


title: 埃及分数

description:
**来源：BIO 1997 Round 1 [Question 3](http://www.olympiad.org.uk/papers/1997/bio/bio97r1q3.html)**

在古埃及，人们使用单位分数的和（形如 $\dfrac{1}{a}$ 的，$a$ 是自然数）表示一切有理数。如：$\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}$，但不允许 $\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}$，因为加数中有相同的。对于一个分数 $\dfrac{a}{b}$，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：
$$
\begin{aligned}
\frac{19}{45} &= \frac{1}{3} + \frac{1}{12} + \frac{1}{180}\\
\frac{19}{45} &= \frac{1}{3} + \frac{1}{15} + \frac{1}{45}\\
\frac{19}{45} &= \frac{1}{3} + \frac{1}{18} + \frac{1}{30}\\
\frac{19}{45} &= \frac{1}{4} + \frac{1}{6} + \frac{1}{180}\\
\frac{19}{45} &= \frac{1}{5} + \frac{1}{6} + \frac{1}{18}\\
\end{aligned}
$$
最好的是最后一种，因为 $\dfrac{1}{18}$ 比 $\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}$ 都大。
注意，可能有多个最优解。如：
$$
\begin{aligned}
\frac{59}{211} &= \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}\\
\frac{59}{211} &= \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}\\
\end{aligned}
$$
由于方法一与方法二中，最小的分数相同，因此二者均是最优解。

给出 $a,b$，编程计算最好的表达方式。保证最优解满足：最小的分数 $\ge \cfrac{1}{10^7}$。

inputFormat: 一行两个整数，分别为 $a$ 和 $b$ 的值。

outputFormat: 输出若干个数，自小到大排列，依次是单位分数的分母。


title: 翻转游戏 (加强版)

description: kkke 在一个 $n\ \times n$ 的棋盘上进行一个翻转游戏。棋盘的每个格子上都放有一个棋子，每个棋子有 $2$ 个面，一面是黑色的，另一面是白色的。初始的时候，棋盘上的棋子有的黑色向上，有的白色向上。现在 kkke 想通过最少次数的翻转，使得棋盘上所有的棋子都是同一个颜色向上的（即全是黑色向上的，或全是白色向上的）。每次翻转的时候，kkke 可以选择任意一个棋子，将它翻转，同时，与它上下左右分别相邻的 $4$ 个棋子也必须同时翻转。

inputFormat:
输入的第一行是一个整数 $n$，表示棋盘的大小是 $n\times n$。

接下来有 $n$ 行，每行包括 $n$ 个字母，表示初始的棋盘状态。如果字母是 $\tt w$，则表示这个棋子当前是白色向上的，如果字母是 $\tt b$，则表示这个棋子当前是黑色向上的。

outputFormat: 输出为一行，如果无法翻转出目标状态，则输出`Impossible`，否则输出一个整数，表示 kkke 最少需要翻转的次数。

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

- 对于 $30\%$ 的数据，$1 \le n \le 4$；
- 对于 $100\%$ 的数据，$1 \le n \le 16$。


title: 手机

description:
一般的手机的键盘是这样的：

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

要按出英文字母就必须要按数字键多下。例如要按出 $\tt x$ 就得按 $9$ 两下，第一下会出 $\tt w$，而第二下会把 $\tt w$ 变成 $\tt x$。$0$ 键按一下会出一个空格。

你的任务是读取若干句只包含英文小写字母和空格的句子，求出要在手机上打出这个句子至少需要按多少下键盘。

inputFormat: 一行句子，只包含英文小写字母和空格，且不超过 200 个字符。

outputFormat: 一行一个整数，表示按键盘的总次数。

hint: NOI 导刊 2010 普及（10）


title: 液体滴落

description:
在平面中有若干线段 $L_i$（**不一定互不相交**），组成一个又一个轨道，有一滴液体从上方滴落下来，如果碰到轨道就沿着轨道向下滚，从轨道较低的一端离开轨道，在轨道中不受任何影响，否则就垂直滴落，问最后液滴从什么位置落出整个系统。

相信这个题目一定难不倒你。

inputFormat:
第一行两个整数 $N$ 和 $S$，表示有 $N$ 条线段，液滴从横坐标为 $S$ 的地方落下。

以下 $N$ 行，每行四个整数 $x_{i1}$，$y_{i1}$，$x_{i2}$，$y_{i2}$ 描述每条线段的端点位置。注意线段不包括两个端点，液体可以从一端点处滴下而不碰到斜面。

outputFormat: 一行一个整数：表示最终液体落下的位置（横坐标）。

hint:
对于 $50\%$ 的数据，$1\le n\le100$，$|x|,|y|,|S| \le500$；

对于 $100\%$ 的数据，$1\le n\le 10^5$，$|x|,|y|,|S|≤10^9$。

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


title: 家族

description: 在一个与世隔绝的岛屿上，有一个有趣的现象：同一个家族的人家总是相邻的（这里的相邻是指东南西北四个方向），不同的家族之间总会有河流或是山丘隔绝，但同一个家族的人不一定有相同姓氏。现在给你岛上的地图，求出岛上有多少个不同的家族。岛上的地图有 $n$ 行，每行有若干列，每个格子中要么是空格，表示大海，要么是 $\text{``{\tt *}''}$，表示河流或山丘，要么是小写字母，表示一户人家的姓氏。

inputFormat: 第一行是个数字 $N$，表示下面信息的行数。接下来是 $N$ 行字符，每行由小写字母和 $\texttt *$ 号组成，有些行的最前面也可能包含若干连续的空格，表示这些区域是大海，每一行最多不超过 $200$ 个字符。

outputFormat: 一个数字，表示家族数。

samples:
4
*zlw**pxh
l*zlwk*hx*
w*tyy**yyy
        zzl

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

- $10\%$ 的数据，$n≤1$。
- $30\%$ 的数据，$n≤10$。
- $100\%$ 的数据，$n≤100$，每一行最多不超过 $200$ 个字符。

NOI导刊 2010 普及（10）


title: 天路

description:
“那是一条神奇的天路诶 ~~~，把第一个神犇送上天堂 ~~~ ”，XDM 先生唱着这首“亲切”的歌曲，一道猥琐题目的灵感在脑中出现了。

和 C_SUNSHINE 大神商量后，这道猥琐的题目终于出现在本次试题上了，旨在难到一帮大脑不够灵活的 OIer 们（JOHNKRAM 真的不是说你……）。

言归正传，小 $X$ 的梦中，他在西藏开了一家大型旅游公司，现在，他要为西藏的各个景点设计一组铁路线。但是，小 $X$ 发现，来旅游的游客都很挑剔，他们乘火车在各个景点间游览，景点的趣味当然是不用说啦，关键是路上。试想，若是乘火车一圈转悠，却发现回到了游玩过的某个景点，花了一大堆钱却在路上看不到好的风景，那是有多么的恼火啊。

所以，小 $X$ 为所有的路径定义了两个值，$V_i$ 和 $P_i$，分别表示火车线路的风景趣味度和乘坐一次的价格。现在小 $X$ 想知道，乘客从任意一个景点开始坐火车走过的一条回路上所有的 $V$ 之和与 $P$ 之和的比值的最大值。以便为顾客们推荐一条环绕旅游路线（路线不一定包含所有的景点，但是不可以存在重复的火车路线）。

于是，小 $X$ 梦醒之后找到了你……

inputFormat:
第一行两个正整数 $N,M$，表示有 $N$ 个景点，$M$ 条火车路线，火车路线是单向的。

以下 $M$ 行，每行 $4$ 个正整数，分别表示一条路线的起点，终点，$V$ 值和 $P$ 值。

注意，两个顶点间可能有多条轨道，但一次只能走其中的一条。

outputFormat:
一个实数，表示一条回路上最大的比值，保留 $1$ 位小数。

若没有回路，输出 $-1$。


title: 淘汰赛制

description:
淘汰赛制是一种极其残酷的比赛制度。$2^n$ 名选手分别标号 $1,2,3,\cdots,2^n-1,2^n$，他们将要参加 $n$ 轮的激烈角逐。每一轮中，将所有参加该轮的选手按标号从小到大排序后，第 $1$ 位与第 $2$ 位比赛，第 $3$ 位与第 $4$ 位比赛，第 $5$ 位与第 $6$ 位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛（不会有平局）。这样，每轮将淘汰一半的选手。$n$ 轮过后，只剩下一名选手，该选手即为最终的冠军。

现在已知每位选手分别与其他选手比赛获胜的概率，请你预测一下谁夺冠的概率最大。

inputFormat: 第一行是一个整数 $n(1 \le n \le 10)$，表示总轮数。接下来 $2^n$ 行，每行 $2^n$ 个整数，第 $i$ 行第 $j$ 个是 $p_{i,j}$。（$0 \le p_{i_j} \le 100$，$p_{i,i}=0$，$p_{i,j}+p_{j,i}=100$），表示第 $i$ 号选手与第 $j$ 号选手比赛获胜的概率。

outputFormat: 输出只有一个整数 $c$，表示夺冠概率最大的选手编号（若有多位选手，输出编号最小者）。


title: 方程的解

description:
佳佳碰到了一个难题，请你来帮忙解决。对于不定方程 $a_1+a_2+\cdots +a_{k-1}+a_k=g(x)$，其中 $k\ge 2$ 且 $k\in \mathbb{N}^*$，$x$ 是正整数，$g(x)=x^x \bmod 1000$（即 $x^x$ 除以 $1000$ 的余数），$x,k$ 是给定的数。我们要求的是这个不定方程的正整数解组数。

举例来说，当 $k=3,x=2$ 时，方程的解分别为：
$$\begin{cases} a_1=1\\ a_2=1\\ a_3=2 \end{cases}$$
$$\begin{cases} a_1=1\\ a_2=2\\ a_3=1 \end{cases}$$
$$\begin{cases} a_1=2\\ a_2=1\\ a_3=1 \end{cases}$$

inputFormat: 输入有且只有一行，为用空格隔开的两个正整数，依次为 $k,x$。

outputFormat: 输出有且只有一行，为方程的正整数解组数。


title: [ZJOI2006] 物流运输

description:
物流公司要把一批货物从码头 A 运到码头 B。由于货物量比较大，需要 $n$ 天才能运完。货物运输过程中一般要转停好几个码头。

物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。

但是修改路线是—件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个 $n$ 天的运输计划，使得总成本尽可能地小。

inputFormat:
第一行是四个整数 $n,m,k,e$。$n$ 表示货物运输所需天数，$m$ 表示码头总数，$k$ 表示每次修改运输路线所需成本，$e$ 表示航线条数。

接下来 $e$ 行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度。其中码头 A 编号为 $1$，码头 B 编号为 $m$。单位长度的运输费用为 $1$。航线是**双向**的。

再接下来一行是一个整数 $d$，后面的 $d$ 行每行是三个整数 $p,a,b$。表示编号为 $p$ 的码头在 $[a,b]$ 天之内无法装卸货物。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头 A 到码头 B 的运输路线。

outputFormat:
包括了一个整数表示最小的总成本。
总成本为 $n$ 天运输路线长度之和 $+ k \times$ 改变运输路线的次数。

hint:
【数据范围】
对于 $100\%$ 的数据，$1 \le n \le 100$，$1\le m \le 20$, $1 \le k \le 500$, $1 \le e \le 200$。

【样例输入说明】

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

上图依次表示第 $1$ 至第 $5$ 天的情况，阴影表示不可用的码头。

【样例输出说明】

前三天走 $1 \to 4 \to 5$，后两天走 $1 \to 3 \to 5$，这样总成本为 $(2+2)\times 3+(3+2)\times 2+10=32$。

\_NOI导刊2010提高（01）


title: 符文之语

background: 传说中珠穆朗玛峰下有座古代人修建的神庙，神庙的地下室里有古代王室的遗产，但数千年来从未有人到达过……探险者小 FF 一直梦想成为世界上最富有的人和最杰出的探险家并被永载史册。在证明了这个洞确实存在后，小 FF 做好了充足准备，来到了神庙。

description:
当小 FF 来到神庙时，神庙已经破败不堪了。但神庙的中央有一个光亮如新的石台。小 FF 走近石台，发现石台上有一个数串，而数串的上方刻着一串古老的符文之语。精通古符文之语的小 FF 不费吹灰之力就读懂了文章的意思，其大意是：

对于石台上的一串数字，你可以在适当的位置加入乘号（设加了 $k$ 个，当然也可不加，即分成 $k+1$ 个部分），设这 $k+1$ 个部分的乘积（如果 $k=0$，则乘积即为原数串的值）对 $m$ 的余数（即 $\bmod\ m$）为 $x$；

现求 $x$ 能达到的最小值及该情况下 $k$ 的最小值，以及 $x$ 能达到的最大值及该情况下的 $k$ 的最小值（可以存在 $x$ 的最小值与最大值相同的情况）。

小 FF 还知道，如果他找到了正确的答案，那么就可以通往神庙的下层了。但这个问题似乎不太好解决，小 FF 就找到了你，并答应找到财宝以后和你二八分（当然你拿二……）。

inputFormat:
第一行为数串，且数串中不存在 $0$；

第二行为 $m$。

outputFormat: 四个数，分别为 $x$ 的最小值和该情况下的 $k$，以及 $x$ 的最大值和该情况下的 $k$，相邻两个数之间用一个空格隔开。

hint:
记 $L$ 表示字符串的长度。

- 对于 $30\%$ 的数据：$2 \le L \le 50$；
- 对于 $100\%$ 的数据：$2 \le L \le 1000$，$2 \le m \le 50$。

NOI 导刊 $2010$ 提高（$02$）