title: 找出伪币

description:
给你一个装有 $n$ 枚硬币的袋子。$n$ 枚硬币中有一个是伪造的，并且那个伪造的硬币和真的硬币重量不一样。你的任务是找出这枚伪造的硬币。

为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。

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

接着 $T$ 行，每行三个正整数 $k,p,n$。

$p=-1$：伪币偏轻；$p=1$：伪币偏重；$p=0$：你不知道伪币与真币的重量对比关系。

$n$ 为一个 $k$ 位十进制正整数（没有前导 $0$）。

outputFormat: 输出 $T$ 行，每行一个整数 $m$，表示至少要称量 $m$ 次就一定能找出伪币。

hint:
对于 $40\%$ 的数据，$n\leq 10^5$。

对于 $100\%$ 的数据，$k\leq 10^4$，$3\lt n\lt 10^{10001}$，$1\leq T\leq 40$。

当 $p=0$ 时，你还需要知道伪币与真币相比是轻是重


title: 倒水问题

type: P

background: ##输入输出已更改，请不要直接提交原先的代码。

description:
假定两个水壶$A$和$B$，供水量不限。可以使用三种方法装水：
- 给一个水壶装水；
- 把一个水壶倒空；
- 从一个水壶倒进另一个水壶。

当从一个水壶倒进另一个水壶时，如果第一个水壶倒空，或者第二个水壶装满就不能再倒了。例如，一个水壶$A$是$5$加仑和另一个水壶$B$是$6$加仑，水量是$8$加仑，则从水壶$A$倒进水壶$B$时，让水壶B充满水而水壶$A$剩$3$加仑水。

问题由3个参数：$C_a$，$C_b$和$N$，分别表示水壶$A$和$B$的容量，目标水量$N$。解决问题的目标是，给出一系列倒水的步骤，使水壶$B$中的水量恰好是$N$。

inputFormat:
第一行为数据组数$T$。

接下来的$T$行，每行三个数字$C_a$，$C_b$和$N$，意义如题目所示。

$T$不超过$30$组，$0<C_a≤Cb$，$N≤C_b≤1000$，且$C_a$和$C_b$互质。

outputFormat:
输出共为$T$行，第一个数字为要达成的完成次数$a_i$（题目保证存在解）。

接下来$a_i$个数字，表示各种操作：
- 1操作:$fill A$ 意为给$A$灌满水
- 2操作:$fill B$
- 3操作:$empty A$ 意为将$A$中水倒空
- 4操作:$empty B$
- 5操作:$pour B A$ 意为将$B$中水倒到$A$中（直到$A$满或者$B$中水没有剩余）
- 6操作:$pour A B$

hint:
开启了spj。

如果你的方案比答案优，会提示UKE，此时请联系管理员修改数据。

如果你的方案比答案差，分数会相应减损。


title: 吃奶酪

description: 房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 $(0,0)$ 点处。

inputFormat:
第一行有一个整数，表示奶酪的数量 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。

outputFormat: 输出一行一个实数，表示要跑的最少距离，保留 $2$ 位小数。

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

对于全部的测试点，保证 $1\leq n\leq 15$，$|x_i|, |y_i| \leq 200$，小数点后最多有 $3$ 位数字。

#### 提示

对于两个点 $(x_1,y_1)$，$(x_2, y_2)$，两点之间的距离公式为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

---

$2022.7.13$：新增加一组 $\text{Hack}$ 数据。


title: [SHOI2002] 滑雪

description:
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
```plain
1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9
```
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 $24-17-16-1$（从 $24$ 开始，在 $1$ 结束）。当然    $25$－$24$－$23$－$\ldots$－$3$－$2$－$1$ 更长。事实上，这是最长的一条。

inputFormat: 输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$。下面是 $R$ 行，每行有 $C$ 个数，代表高度(两个数字之间用 $1$ 个空格间隔)。

outputFormat: 输出区域中最长滑坡的长度。


title: [IOI2000] 回文字串

background: IOI2000 第一题

description:
回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

比如 $\verb!Ab3bd!$ 插入 $2$ 个字符后可以变成回文词 $\verb!dAb3bAd!$ 或 $\verb!Adb3bdA!$，但是插入少于 $2$ 个的字符无法变成回文词。

**注意**：此问题区分大小写。

inputFormat: 输入共一行，一个字符串。

outputFormat: 有且只有一个整数，即最少插入字符数。

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

记字符串长度为 $l$。

对于全部数据，$0<l\le 1000$。


title: 棋盘分割

description:
将一个 $8\times 8$ 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的两部分中的任意一块继续如此分割，这样割了 $(n-1)$ 次后，连同最后剩下的矩形棋盘共有 $n$ 块矩形棋盘。（每次切割都只能沿着棋盘格子的边进行）。

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

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 $n$ 块矩形棋盘，并使各矩形棋盘总分的平方和最小。

请编程对给出的棋盘及 $n$，求出平方和的最小值。

inputFormat:
第一行为一个整数 $n\ (1<n \le 15)$。

第二行至第九行每行为 $8$ 个小于 $100$ 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

outputFormat: 仅一个数，为平方和。


title: [HNOI2004] 敲砖块

background: 无

description:
在一个凹槽中放置了 $n$ 层砖块、最上面的一层有 $n$ 块砖，从上到下每层依次减少一块砖。每块砖都有一个分值，敲掉这块砖就能得到相应的分值，如下图所示：

```cpp
14 15  4  3  23
 33  33 76  2
   2   13 11
     22 23
       31
```
如果你想敲掉第 $i$ 层的第 $j$ 块砖的话，若 $i=1$，你可以直接敲掉它；若 $i>1$，则你必须先敲掉第 $i-1$ 层的第 $j$ 和第 $j+1$ 块砖。

你现在可以敲掉最多 $m$ 块砖，求得分最多能有多少。

inputFormat:
输入文件的第一行为两个正整数 $n$ 和 $m$；接下来 $n$ 行，描述这 $n$ 层砖块上的分值 $a_{i,j}$，满足 $0\leq a_{i,j}\leq 100$。

对于 $100\%$ 的数据，满足 $1\leq n\leq 50$，$1\leq m\leq \frac{n\times(n+1)}{2}$；

outputFormat: 输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。


title: 无聊的数列

background: 无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的 YYB 想出了一道无聊的题：无聊的数列。。。

description:
维护一个数列 $a_i$，支持两种操作：

 - `1 l r K D`：给出一个长度等于 $r-l+1$ 的等差数列，首项为 $K$，公差为 $D$，并将它对应加到 $[l,r]$ 范围中的每一个数上。即：令 $a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D$。

 - `2 p`：询问序列的第 $p$ 个数的值 $a_p$。

inputFormat:
第一行两个整数数 $n,m$ 表示数列长度和操作个数。

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

接下来的 $m$ 行，每行先输入一个整数 $opt$。

若 $opt=1$ 则再输入四个整数 $l\ r\ K\ D$；

若 $opt=2$ 则再输入一个整数 $p$。

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

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

对于 $100\%$ 数据，$0\le n,m \le 10^5,-200\le a_i,K,D\le 200, 1 \leq l \leq r \leq n, 1 \leq p \leq n$。


title: 【模板】最长公共子序列

description: 给出 $1,2,\ldots,n$ 的两个排列 $P_1$ 和 $P_2$ ，求它们的最长公共子序列。

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

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\ldots,n$ 的一个排列。

outputFormat: 一个数，即最长公共子序列的长度。


title: 求m区间内的最小值

description: 一个含有 $n$ 项的数列，求出每一项前的 $m$ 个数到它这个区间内的最小值。若前面的数不足 $m$ 项则从第 $1$ 个数开始，若前面没有数则输出 $0$。

inputFormat:
第一行两个整数，分别表示 $n$，$m$。

第二行，$n$ 个正整数，为所给定的数列 $a_i$。

outputFormat: $n$ 行，每行一个整数，第 $i$ 个数为序列中 $a_i$ 之前 $m$ 个数的最小值。

hint: 对于 $100\%$ 的数据，保证 $1\le m\le n\le2\times10^6$，$1\le a_i\le3\times10^7$。


title: 砝码称重

description:
现有 $n$ 个砝码，重量分别为 $a_i$，在去掉 $m$ 个砝码后，问最多能称量出多少不同的重量（不包括 $0$）。

请注意，砝码只能放在其中一边。

inputFormat:
第 $1$ 行为有两个整数 $n$ 和 $m$，用空格分隔。

第 $2$ 行有 $n$ 个正整数 $a_1, a_2, a_3,\ldots , a_n$，表示每个砝码的重量。

outputFormat: 仅包括 $1$ 个整数，为最多能称量出的重量数量。

hint:
【样例说明】

在去掉一个重量为 $2$ 的砝码后，能称量出 $1, 2, 3$ 共 $3$ 种重量。

【数据规模】

对于 $20\%$ 的数据，$m=0$。

对于 $50\%$ 的数据，$m\leq 1$。

对于 $50\%$ 的数据，$n\leq 10$。

对于 $100\%$ 的数据，$n\leq 20$， $m\leq 4$，$m < n$，$a_i\leq 100$。


title: 铁球落地

description:
在二维坐标系内有 $n$ 个平台（定义平台是一条两端点纵坐标相同的开线段，开线段指线段两个端点不算做线段本身）和一个铁球，铁球如果下面没有物体，则每秒会下落一个单位长度。

球每次落到某个平台上后，游戏者可以选择水平向左或水平向右滚，球滚动速度是每秒 $1$ 个单位长度。由于铁球的质量不太好，每次落下的高度不能超过 $h$。

设计一种策略，使得球尽快落到地面而不被摔碎。

假设地面高度为 $0$，且无限宽。球体积相对平台极小，可以看作一个质点。**请注意，球滚动至平台的一个端点处即可下落，不需要滚动至下一个格子**。例如下图，小球在 $(9,9)$ 处已经开始下落。

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

inputFormat:
第一行有两个整数，分别代表平台个数 $n$ 和最大下落高度 $h$。

第二行有两个整数 $x, y$，表示铁球起始时在坐标为 $(x, y)$ 的位置。

第 $3$ 到第 $(n + 2)$ 行，每行三个整数，第 $(i + 2)$ 行的整数 $h_i, l_i, r_i$ 分别代表第 $i$ 个平台的端点纵坐标 $h_i$ 和左右端点的横坐标 $l_i,r_i$。

outputFormat: 输出一行一个整数表示最小的坠落时间。

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

对于全部的测试点，保证：

- $1 \leq n \leq 10^5$。
- $1 \leq x, y, h, h_i, l_i, r_i \leq 10^9$，$l_i \leq r_i$。
- 对于所有的 $h_i$，保证互不相同，$l_i$ 与 $r_i$ 也互不相同，且对于任意 $i \neq j$，保证 $l_i \neq r_j$ 。
- 数据保证有解，最终答案不超过 $10^9$。


title: 马的遍历

description: 有一个 $n \times m$ 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

inputFormat: 输入只有一行四个整数，分别为 $n, m, x, y$。

outputFormat: 一个 $n \times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $-1$）。

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

对于全部的测试点，保证 $1 \leq x \leq n \leq 400$，$1 \leq y \leq m \leq 400$。


title: [USACO1.3] 虫洞 wormhole

description:
Farmer John 周末进行高能物理实验的结果却适得其反，导致 $n$ 个虫洞出现在农场上，农场是一个二维平面，没有两个虫洞处于同一位置。

根据他的计算，FJ 知道他的虫洞两两配对，形成 $\dfrac{n}{2}$ 对配对。例如，如果 $A$ 和 $B$ 的虫洞连接成一对，进入虫洞 $A$ 的任何物体将从虫洞 $B$ 出去，方向不变；反之亦然。

然而这可能发生相当令人不快的后果。例如，假设有两个成对的虫洞 $A(1,1)$ 和 $B(3,1)$，Bessie 从 $(2,1)$ 开始朝着 $x$ 正方向移动。Bessie 将进入虫洞 $B(3,1)$，从 $A(1,1)$ 出去，然后再次进入 $B$，困在一个无限循环中！

FJ 知道他的农场里每个虫洞的确切位置。他知道 Bessie 总是向 $x$ 正方向走进来，虽然他不记得贝茜的当前位置。

请帮助 FJ 计算有多少种虫洞配对方案，使得存在一个位置，使得 Bessie 从该位置出发，会被困在一个无限循环中。

inputFormat:
第一行一个正整数 $n$，表示虫洞数量。

接下来 $n$ 行，每行两个整数 $x,y$，表示一个虫洞的坐标。

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

hint:
### 数据范围
对于 $100\%$ 的数据，$2\le n \le 12$，$0 \le x,y \le 10^9$。
保证 $n$ 为偶数。

### 样例解释

将虫洞编号为 $1 \sim 4$，然后通过将 $1,2$ 和 $3,4$ 匹配，如果 Bessie 从 $(0,0)$ 到 $(1,0)$ 之间的任意位置出发，她会陷入无限循环中。

相似的，在相同的起始点，如果配对是 $1,3$ 和 $2,4$，贝茜也会陷入循环。（如果贝西从 $3$ 进去，$1$ 出来，她会走向 $2$ ，然后被传送到 $4$，最后又回到 $3$）

仅有 $1,4$ 和 $2,3$ 的配对允许贝茜从任何二维平面上的点向 $x$ 正方向走，而不出现无限循环。

题面翻译摘自 NOCOW


title: [Violet] 樱花

background:
又到了一年樱花盛开的时节。Vani 和妹子一起去看樱花的时候，找到了一棵大大的樱花树，上面开满了粉红色的樱花。Vani 粗略估计了一下，一共有足足 $n!$ 片花瓣。

Vani 轻柔地对她说：“你知道吗？这里面的一片花瓣代表着你，我从里面随机摘一片，能和你相遇的概率只有 $1/n!$ 那么小。我该是多么的幸运，才让你今天这么近地站在我面前。相信我，我一定会把这亿万分之一的缘分变为永远。”

粉红的樱花漫天飞舞，妹子瞬间被 Vani 感动了。她轻轻地牵起了他的手，和他相依而坐。这时，她突然看到田野的尽头也长着两棵樱花树，于是慢慢地把头靠在 Vani 的肩上，在他耳边低语：“看到夕阳里的那两棵樱花树了吗？其中一棵树上的一片花瓣是你，另一棵树上的一片花瓣是我，如果有人从这棵摘下一片，从那棵采下一瓣，我们相遇的概率会不会正好是 $1/n!$ 呢？”

Vani 的大脑飞速运作了一下，立即算出了答案。正要告诉妹子，她突然又轻轻地说：“以前你总是说我数学不好，但是这种简单的题我还是会算的。你看假如左边那棵树上有 $x$ 片花瓣，右边那个有 $y$ 片花瓣，那么我们相遇的概率不就是 $1/x+1/y$ 么，不过有多少种情况能使它正好可以等于 $1/n!$ 呢？这个你就帮我算一下吧～”

显然，面对天然呆的可爱妹子，Vani 不但不能吐槽她的渣数学，而且还要老老实实地 帮她算出答案哦。

description:
求方程：

$$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n!}$$

的正整数解的组数，答案对 $10^9+7$ 取模。

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

outputFormat: 输出一行一个整数表示正整数解的组数模 $10^9+7$ 的值。


title: [HNOI2008] Cards

description:
小春现在很清闲，面对书桌上的 $n$ 张牌，他决定给每张牌染色，目前小春拥有 $3$ 种颜色：红色，蓝色，绿色。他询问 Sun 有多少种染色方案，Sun 很快就给出了答案。

进一步，小春要求染出 $S_r$ 张红色，$S_b$ 张蓝色，$S_g$ 张绿色。他又询问有多少种方案，Sun 想了一下，又给出了正确答案。最后小春发明了 $m$ 种不同的洗牌法，这里他又问 Sun 有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。

Sun 发现这个问题有点难度，决定交给你，由于答案可能很大，你只需要求出答案对于 $P$ 取模的结果。 保证 $P$ 为一个质数。

inputFormat:
第一行输入 $5$ 个整数，依次表示：$S_r,S_b,S_g,m,P$（$m\le 60,m+1<p<100$）。其中，题面所提及的 $n$ 为 $S_r+S_b+S_g$，即 $n=S_r+S_b+S_g$。

接下来 $m$ 行，每行描述一种洗牌法，每行有 $n$ 个用空格隔开的整数 $X_1X_2...X_n$，保证其为 $1$ 到 $n$ 的一个排列，表示使用这种洗牌法，第 $i$ 位变为原来的 $X_i$ 位的牌。输入数据保证任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

同时，对于 $100\%$ 的数据满足 $\max\{S_r,S_b,S_g\}\le 20$ 。

outputFormat: 不同的染色方法对 $P$ 取模的结果。

hint: 有 $2$ 种本质上不同的染色法：`RGB` 和 `RBG`，使用洗牌法 `231` 一次，可得 `GBR` 和 `BGR`，使用洗牌法 `312` 一次，可得 `BRG` 和 `GRB`。


title: [NOI2010] 能量采集

description:
栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。

栋栋的植物种得非常整齐，一共有 $n$ 列，每列有 $m$ 棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标 $(x, y)$ 来表示，其中 $x$ 的范围是 $1$ 至 $n$，$y$ 的范围是 $1$ 至 $m$，表示是在第 $x$ 列的第 $y$ 棵。

由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是 $(0, 0)$。

能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有 $k$ 棵植物，则能量的损失为 $2k + 1$。例如，当能量汇集机器收集坐标为 $(2, 4)$ 的植物时，由于连接线段上存在一棵植物 $(1, 2)$，会产生 $3$ 的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为 $1$。现在要计算总的能量损失。

下面给出了一个能量采集的例子，其中 $n = 5$，$m = 4$，一共有 $20$ 棵植物，在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。

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

在这个例子中，总共产生了 $36$ 的能量损失。

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

outputFormat: 仅包含一个整数，表示总共产生的能量损失。


title: [NOI1998] 围巾裁剪

background: NOI1998 Day2 T1

description:
裁缝有一块非常珍贵的丝绸围巾。可惜的是，围巾的某些部分已经被蛀虫给咬坏了。裁缝当然不愿意就这么把围巾给丢了，于是，他想把围巾给裁成两块小围巾送给他的两个女儿。自然，两块小围巾的面积之和越大越好。

这块围巾是一个正三角形，三条边被均匀地分成了 $N$ 段，即这个正三角形被均匀地分成了 $N^2$ 个单元，每个单元是一个面积为 $1$ 的正三角形。

如图所示为一个 $N=5$ 的围巾，图中带阴影的单元表示被蛀虫咬坏的部分。
从上往下看，围巾被分成了 $N$ 行：
- 第一行有 $1$ 个单元。
- 第二行有 $3$ 个单元，其中有 $2$ 个是形如 $\Delta$ 的，有 $1$ 个是形如 $\nabla$ 的（这两种三角形我们认为是形状相同的）。
- 第三行有 $5$ 个单元，其中有 $3$ 个是形如 $\Delta$ 的，有 $2$ 个是形如 $\nabla$ 的……

用坐标 $(X,Y)$ 给每个单元定位，第一行的单元的坐标为 $(1,1)$；第二行从左到右的三个单元的坐标依次为 $(2,1)$、$(2,2)$、$(2,3)$；……

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

围巾的剪裁条件如下：
  1. 裁成的两块小围巾形状与原来的大围巾完全相同，都是正三角形；
  2. 每一块小围巾里都不存在被蛀虫咬坏的部分；
  3. 裁剪时必须沿着单元的边界裁剪；
  4. 要求两块小围巾的面积的总和最大。

图中，最优的裁剪方法已经用粗线画了出来，面积和为 $4+9=13$。
现在需要你编一个程序来帮助裁缝解决这个问题。

inputFormat:
输入的第一行为一个整数 $N$（$1\leq N\leq100$），表示这块围巾总共被分成了 $N^2$ 个单元。第二行为一个整数 $M$（$1\leq M\leq N^2$），表示这块围巾共有 $M$ 个单元被蛀虫咬坏了。接下来的 $M$ 行，每一行有两个正整数 $X$ 和 $Y$，为这 $M$ 个被蛀虫咬坏的单元的坐标。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

outputFormat: 输出文件仅含一个整数，为你所找到的裁出两块小围巾面积总和的最大值（提示：如果找不到两个符合要求的正三角形，输出 $0$）。

hint:
#### 样例组 $\bm 1$ 解释

如「题目描述」中图所示，两块小围巾面积总和的最大值为 $4+9=13$。

#### 数据范围

- 对于 $50\%$ 的数据，$1\leq N\leq50$；
- 对于 $100\%$ 的数据，$1\leq N\leq100$，$0\leq M\leq N^2$，$1\leq X\leq N$，$1\leq Y\leq 2\times N-1$。

本题数据为 Windows（CRLF）格式。


title: 后缀表达式

description:
所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

本题中运算符仅包含 $\texttt{+-*/}$。保证对于 $\texttt{/}$ 运算除数不为 0。特别地，其中 $\texttt{/}$ 运算的结果需要**向 0 取整**（即与 C++ `/` 运算的规则一致）。

如：$\texttt{3*(5-2)+7}$ 对应的后缀表达式为：$\texttt{3.5.2.-*7.+@}$。在该式中，`@` 为表达式的结束符号。`.` 为操作数的结束符号。

inputFormat: 输入一行一个字符串 $s$，表示后缀表达式。

outputFormat: 输出一个整数，表示表达式的值。

hint: 数据保证，$1 \leq |s| \leq 50$，答案和计算过程中的每一个值的绝对值不超过 $10^9$。


title: [HAOI2008] 硬币购物

description:
共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。

某人去商店买东西，去了 $n$ 次，对于每次购买，他带了 $d_i$ 枚 $i$ 种硬币，想购买 $s$ 的价值的东西。请问每次有多少种付款方法。

inputFormat:
输入的第一行是五个整数，分别代表 $c_1,c_2,c_3,c_4, n$。

接下来 $n$ 行，每行有五个整数，描述一次购买，分别代表 $d_1, d_2, d_3, d_4,s$。

outputFormat: 对于每次购买，输出一行一个整数代表答案。

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

* 对于 $100\%$ 的数据，保证 $1 \leq c_i, d_i, s \leq 10^5$，$1 \leq n \leq 1000$。


title: 求细胞数量

description: 一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

inputFormat:
第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 `0` 到 `9` 的字符串，代表这个 $n \times m$ 的矩阵。

outputFormat: 一行一个整数代表细胞个数。

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

对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$。


title: 【模板】旋转卡壳 | [USACO03FALL] Beauty Contest G

description: 给定平面上 $n$ 个点，求凸包直径。

inputFormat:
第一行一个正整数 $n$。
接下来 $n$ 行，每行两个整数 $x,y$，表示一个点的坐标。保证所有点的坐标两两不同。

outputFormat: 输出一行一个整数，表示答案的平方。


title: 城市环路

description:
一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。

B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路，环路之内便是 B 市中心。

整个城市可以看做一个 $n$ 个点，$n$ 条边的单圈图（保证图连通），唯一的环便是绕城的环路。保证环上任意两点有且只有 $2$ 条简单路径互通。图中的其它部分皆隶属城市郊区。

现在，有一位名叫 Jim 的同学想在 B 市开店，但是任意一条边的 $2$ 个点不能同时开店，每个点都有一定的人流量，第 $i$ 个点的人流量是 $p_i$，在该点开店的利润就等于 $p_i×k$，其中 $k$ 是一个常数。

Jim 想尽量多的赚取利润，请问他应该在哪些地方开店？

inputFormat:
第一行一个整数 $n$，代表城市中点的个数。城市中的 $n$ 个点由 $0 \sim n-1$ 编号。

第二行有 $n$ 个整数，第 $(i + 1)$ 个整数表示第 $i$ 个点的人流量 $p_i$。

接下来 $n$ 行，每行有两个整数 $u, v$，代表存在一条连接 $u$ 和 $v$ 的道路。

最后一行有一个实数，代表常数 $k$。

outputFormat: 输出一行一个实数代表答案，结果保留一位小数。

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

- 对于 $20\%$ 的数据，保证 $n \leq 100$。
- 另有 $20\%$ 的数据，保证环上的点不超过 $2000$ 个。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq p_i \leq 10^4$，$0 \leq u, v < n$，$0 \leq k \leq 10^4$，$k$ 的小数点后最多有 $6$ 位数字。


title: 圣诞夜的极光

background: 圣诞夜系列~~

description:
圣诞老人回到了北极圣诞区，已经快到 12 点了。也就是说极光表演要开始了。这里的极光不是极地特有的自然极光景象。而是圣诞老人主持的人造极光。

轰隆隆 …… 烟花响起（来自中国的浏阳花炮之乡）。接下来就是极光表演了。

人造极光其实就是空中的一幅幅 $n\times m$ 的点阵图像。只是因为特别明亮而吸引了很多很多小精灵的目光，也成为了圣诞夜最美丽的一刻。

然而在每幅 $n \times m$ 的点阵图像中，每一个点只有发光和不发光两种状态。对于所有的发光的点，在空中就形成了美丽的图画。而这个图画是以若干个（$s$ 个）图案组成的。对于图案，圣诞老人有着严格的定义：对于两个发光的点，如果他们的曼哈顿距离（对于 $A(x_1, y_1)$ 和 $B(x_2, y_2)$ ，$A$ 和 $B$ 之间的曼哈顿距离为 $|x_1-x_2|+|y_1-y_2|$ ）小于等于 $2$。那么这两个点就属于一个图案 …… 小精灵们一边欣赏着极光，一边数着每一幅极光图像中的图案数。伴着歌声和舞蹈，度过了美丽的圣诞之夜。^_^

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

接下来一共 $n$ 行，每行 $m$ 个字符。对于第 $i$ 行第 $j$ 个字符，如果其为 `-`
 ，那么表示该点不发光，如果其为 `#` ，那么表示该点发光。不可能出现其他的字符。

outputFormat: 第一行，一个数 $s$。


title: 搭配购买

description: 明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 $n$ 朵云，云朵已经被老板编号为 $1,2,3,...,n$，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

inputFormat:
第一行输入三个整数，$n,m,w$，表示有 $n$ 朵云，$m$ 个搭配和你现有的钱的数目。

第二行至 $n+1$ 行，每行有两个整数， $c_i,d_i$，表示第 $i$ 朵云的价钱和价值。

第 $n+2$ 至 $n+1+m$ 行 ，每行有两个整数 $u_i,v_i$。表示买第 $u_i$ 朵云就必须买第 $v_i$ 朵云,同理，如果买第 $v_i$ 朵就必须买第 $u_i$ 朵。

outputFormat: 一行，表示可以获得的最大价值。


title: Monkey King

description:
Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.

Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2).

And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.

inputFormat:
There are several test cases, and each case consists of two parts.

First part: The first line contains an integer N(N<=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768).

Second part: The first line contains an integer M(M<=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.

outputFormat: For each of the conflict, output -1 if the two monkeys know each other, otherwise output the strength value of the strongest monkey among all of its friends after the duel.

translation:
#### 题目描述

曾经在一个森林中居住着 $N$ 只好斗的猴子。在最初他们我行我素，互不认识。但是猴子们不能避免争吵，且两只猴子只会在不认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。

假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如  $10$ 会减少到  $5$，而  $5$ 会减少到  $2$，即向下取整）。

我们也假设每只猴子都认识它自己（是自己的朋友）。即当他是他朋友中最强壮的，他自己就会去决斗。

#### 输入格式

有多组数据，每一组数据有两部分。

第一部分：第一行包含一个整数 $N$ 表示猴子的数量。后为 $N$ 行，每行一个数字为第 $i$ 只猴子的强壮值  $s_{i}$。

第二部分：第一行包含一个整数 $M$ 表示发生了 $M$ 次冲突。后为 $M$ 行，每行两个整数 $x$ 和 $y$，表示第 $x$ 只猴子和第 $y$ 只猴子之间发生了冲突。

#### 输出格式

对于每次冲突，如果两只猴子认识对方，输出 `-1`，否则输出决斗后他们朋友中最强壮的猴子的强壮值。

#### 说明/提示

$N,M\leq 100000$，$s_{i}\leq 32768$

hint: 题目可能有多组数据


title: [USACO2.1] 城堡 The Castle

background: 我们憨厚的 USACO 主人公农夫约翰（Farmer John）以无法想象的运气,在他生日那天收到了一份特别的礼物：一张“幸运爱尔兰”（一种彩票）。结果这张彩票让他获得了这次比赛唯一的奖品——坐落于爱尔兰郊外的一座梦幻般的城堡！

description:
喜欢吹嘘的农夫约翰立刻回到有着吹嘘传统的威斯康辛老家开始吹嘘了, 农夫约翰想要告诉他的奶牛们关于他城堡的一切。他需要做一些吹嘘前的准备工作：比如说知道城堡有多少个房间，每个房间有多大。

另外，农夫约翰想要把一面单独的墙（指两个单位间的墙）拆掉以形成一个更大的房间。 你的工作就是帮农夫约翰做以上的准备，算出房间数与房间的大小。

城堡的平面图被划分成 $n \times m$ 个正方形的单位，一个这样的单位可以有 $0 \sim 4 $ 面墙环绕。城堡周围一定有外墙环绕以遮风挡雨。（就是说平面图的四周一定是墙。）

请仔细研究下面这个有注解的城堡平面图：

```plain
     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 # ->#   |   |   |   |   #   #
   #############################
```

- $\verb!#!$ 表示墙壁；
- $\verb!|!$ 和 $\verb!-!$ 表示没有墙壁；
- $\verb!->!$ 指向了一面墙，移除了这面墙我们就有一间最大的新房间。

友情提示，这个城堡的平面图是 $4 \times 7$ 个单位的。一个“房间”的是平面图中一个由 `#`、`-`、`|` 围成的格子（就是图里面的那一个个的格子）。比如说这个样例就有 $5$ 个房间。（大小分别为 $9,7,3,1,8$ 个单位（排名不分先后））

移去箭头所指的那面墙，可以使 $2$ 个房间合为一个新房间，且比移去其他墙所形成的房间都大。

城堡保证至少有 $2$ 个房间，而且一定有一面墙可以被移走。

inputFormat:
第一行两个正整数 $m,n$，表示城堡有 $n$ 行 $m$ 列。

每一个单位的数字告诉我们这个单位的东西南北是否有墙存在。每个数字是由以下四个整数中的任意个加起来的。

$1$: 在西面有墙

$2$: 在北面有墙

$4$: 在东面有墙

$8$: 在南面有墙

城堡内部的墙会被规定两次。比如说 $(1,1)$ 南面的墙，亦会被标记为 $(2,1)$ 北面的墙。

outputFormat:
输出包含如下四行:

第一行：城堡的房间数目。

第二行：最大的房间的大小

第三行：移除一面墙能得到的最大的房间的大小

第四行：移除哪面墙可以得到面积最大的新房间。

选择最佳的墙来推倒。有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。

用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（ `N`（北）或者 `E`（东））。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n,m \le 50$。

USACO 2.1

翻译来自NOCOW


title: [USACO2.1] 顺序的分数 Ordered Fractions

description:
输入一个自然数 $n$，对于一个最简分数 $a/b$（分子和分母互质的分数），满足 $1 \le b \le n,0 \le a/b \le 1$，请找出所有满足条件的分数。

这有一个例子，当 $n=5$ 时，所有解为：

$$\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34 ,\frac45,\frac11$$

给定一个自然数 $n$，请编程按分数值递增的顺序输出所有解。

注：
1、$0$ 和任意自然数的最大公约数就是那个自然数。
2、互质指最大公约数等于1的两个自然数。

inputFormat: 单独的一行一个自然数 $n$

outputFormat: 每个分数单独占一行，按照大小次序排列

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 160$。

USACO 2.1

翻译来自NOCOW


title: [USACO2.1] 三值的排序 Sorting a Three-Valued Sequence

description:
排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种 $1,2,3$。我们用交换的方法把他排成升序的。

写一个程序计算出，给定的一个 $1,2,3$ 组成的数字序列，排成升序所需的最少交换次数

inputFormat:
第一行一个正整数 $n$，表示奖牌个数。
接下来 $n$ 行，每行一个 $[1,3]$ 内的整数，表示奖牌。

outputFormat: 输出一行一个整数，表示排成升序所需的最少交换次数。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 1000$。

USACO 2.1

翻译来自NOCOW


title: [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins

description:
农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。

维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。

inputFormat:
第一行一个整数 $v$，表示需要的维他命的种类数。
第二行 $v$ 个整数，表示牛每天需要的每种维他命的最小量。

第三行一个整数 $g$，表示可用来喂牛的饲料的种数。
下面 $g$ 行，第 $n$ 行表示编号为 $n$ 饲料包含的各种维他命的量的多少。

outputFormat:
输出文件只有一行，包括牛必需的最小的饲料种数 $p$；后面有 $p$ 个数，表示所选择的饲料编号（按从小到大排列）。

如果有多个解，输出饲料序号最小的（即字典序最小）。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le v \le 25$，$1\le g \le 15$。
输入的所有整数在 $[1,1000]$ 范围内。

USACO 2.1

翻译来自NOCOW


title: [USACO2.1] 海明码 Hamming Codes

description:
给出 $n,b,d$，要求找出 $n$ 个由 $0,1$ 组成的编码，每个编码有 $b$ 位），使得两两编码之间至少有 $d$ 个单位的 “Hamming距离”。“

Hamming距离”是指对于两个编码，他们二进制表示法中的不同二进制位的数目。看下面的两个编码 `0x554` 和 `0x234`（十六进制数）

```
0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
不同位    xxx  xx
```

因为有五个位不同，所以“Hamming距离”是 $5$。

inputFormat: 一行，包括 $n,b,d$。

outputFormat:
$n$ 个编码（用十进制表示），要排序，十个一行。
如果有多解，你的程序要输出这样的解：假如把它化为 $2^b$ 进制数，它的值要最小。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 64$，$1\le b \le 8$，$1\le d \le 7$。

请解释：“必须与其他所有的数相比，Hamming 距离都符合要求，这个数才正确”

答：如样例输出，$0,7$，$0,25$，比较都符合海明码，同样 $7,25$，$7,30$，比较也符合要求，以此类推。题中至少有 $d$ 个单位，意思就是大于等于 $d$ 个单位的都可以。

USACO 2.1

翻译来自NOCOW


title: 通往奥格瑞玛的道路

background:
在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。

有一天他醒来后发现自己居然到了联盟的主城暴风城。

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。

description:
在艾泽拉斯，有 $n$ 个城市。编号为 $1,2,3,\ldots,n$。

城市之间有 $m$ 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设 $1$ 为暴风城，$n$ 为奥格瑞玛，而他的血量最多为 $b$，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

歪嘴哦不希望花很多钱，他想知道，在所有可以到达奥格瑞玛的道路中，对于每条道路所经过的城市收费的最大值，最小值为多少。

inputFormat:
第一行 $3$ 个正整数，$n,m,b$。分别表示有 $n$ 个城市，$m$ 条公路，歪嘴哦的血量为 $b$。

接下来有 $n$ 行，每行 $1$ 个正整数，$f_i$。表示经过城市 $i$，需要交费 $f_i$ 元。

再接下来有 $m$ 行，每行 $3$ 个正整数，$a_i,b_i,c_i$（$1\leq a_i,b_i\leq n$）。表示城市 $a_i$ 和城市 $b_i$ 之间有一条公路，如果从城市 $a_i$ 到城市 $b_i$，或者从城市 $b_i$ 到城市 $a_i$，会损失 $c_i$ 的血量。

outputFormat:
仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出 `AFK`。

hint:
对于 $60\%$ 的数据，满足 $n\leq 200$，$m\leq 10^4$，$b\leq 200$；

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^4$，$1\leq m\leq 5\times 10^4$，$1\leq b\leq 10^9$；

对于 $100\%$ 的数据，满足 $1\leq c_i\leq 10^9$，$0\leq f_i\leq 10^9$，可能有两条边连接着相同的城市。


title: [POI2001] [HAOI2007] 反素数

description:
对于任何正整数 $x$，其约数的个数记作 $g(x)$。例如 $g(1)=1$，$g(6)=4$。

如果某个正整数 $x$ 满足：$\forall 0 \lt i \lt x$，都有 $g(x) \gt g(i)$，则称 $x$ 为**反质数**。例如，整数 $1,2,4,6$ 等都是反质数。

现在给定一个数 $N$，你能求出不超过 $N$ 的最大的反质数么？

inputFormat: 一个数 $N$。

outputFormat: 不超过 $N$ 的最大的反质数。

hint: $1 \leq N \leq 2 \times 10^9$


title: Function

description:
对于一个递归函数 $w(a,b,c)$

- 如果 $a \le 0$ 或 $b \le 0$ 或 $c \le 0$ 就返回值$ 1$。
- 如果 $a>20$ 或 $b>20$ 或 $c>20$ 就返回 $w(20,20,20)$
- 如果 $a<b$ 并且 $b<c$ 就返回$ w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$。
- 其它的情况就返回 $w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)$

这是个简单的递归函数，但实现起来可能会有些问题。当 $a,b,c$ 均为 $15$ 时，调用的次数将非常的多。你要想个办法才行。

注意：例如 $w(30,-1,0)$ 又满足条件 $1$ 又满足条件 $2$，请按照最上面的条件来算，答案为 $1$。

inputFormat:
会有若干行。

并以 $-1,-1,-1$ 结束。

outputFormat:
输出若干行，每一行格式：

`w(a, b, c) = ans`

注意空格。


title: [USACO2.2] 序言页码 Preface Numbering

description:
给定 $n$，求 $1 \sim n$ 的 **罗马数字** 表示中，各个字符出现了多少次。

比如 $n = 5$，表示为  I, II, III, IV, V。总共有 $7$ 个 I 出现，$2$ 个 V 出现。

inputFormat: 一个整数 $n$。

outputFormat: 每行一个字符和一个数字 $k$，表示这个字符出现了 $k$ 次。字符必须按罗马数字表中的递增顺序输出。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 3500$。

翻译来自NOCOW

USACO 2.2


title: [USACO2.2] 集合 Subset Sums

description:
对于从 $1\sim n$ 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果 $n=3$，对于 $\{1,2,3\}$ 能划分成两个子集合，每个子集合的所有数字和是相等的：

$\{3\}$ 和 $\{1,2\}$ 是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）
如果 $n=7$，有四种方法能划分集合 $\{1,2,3,4,5,6,7 \}$，每一种分法的子集合各数字和是相等的:

$\{1,6,7\}$ 和 $\{2,3,4,5\}$
$\{2,5,7\}$ 和 $\{1,3,4,6\}$
$\{3,4,7\}$ 和 $\{1,2,5,6\}$
$\{1,2,4,7\}$ 和 $\{3,5,6\}$

给出 $n$，你的程序应该输出划分方案总数。

inputFormat: 输入文件只有一行，且只有一个整数 $n$

outputFormat: 输出划分方案总数。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 39$。

翻译来自NOCOW

USACO 2.2


title: [USACO2.2] 循环数 Runaround Numbers

description:
循环数是那些不包括 $0$ 且没有重复数字的整数（比如 $81362$）并且还应同时具有一个有趣的性质, 就像这个例子:

如果你从最左边的数字开始（在这个例子中 $8$）向右数最左边这个数（如果数到了最右边就回到最左边），你会停止在另一个新的数字（如果停在一个相同的数字上，这个数就不是循环数）。

就像：$8\ 1\ 3\ 6\ 2$ 从最左边接下去数 $8$ 个数字: $1\ 3\ 6\ 2\ 8\ 1\ 3\ 6$ 所以下一个数字是 $6$

重复这样做 (这次从 `6` 开始数 $6$ 个数字) 并且你会停止在一个新的数字上: $2\ 8\ 1\ 3\ 6\ 2$, 也就是 $2$

再这样做 (这次数两个): $8\ 1$

再一次 (这次一个): $3$

又一次: $6\ 2\ 8$

这时你回到了起点,在经过每个数字一次后回到起点的就是循环数。如果你经过每一个数字一次以后没有回到起点, 你的数字不是一个循环数。

给你一个数字 $m$ ，找出第一个比 $m$ 大的循环数, 输出数据保证结果能用一个无符号长整型数 $ \in [0,2^{32})$ 装下。 （追加提醒：循环数每个数位都必须要访问到）

inputFormat: 仅仅一行, 包括 $m$。

outputFormat: 仅仅一行，输出第一个比 $m$ 大的循环数。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le m \le 10^9$。

翻译来自NOCOW

USACO 2.2


title: [USACO2.2] 派对灯 Party Lamps

description:
在 IOI98 的节日宴会上，我们有 $n$ 盏彩色灯，他们分别从 $1 \sim n$ 被标上号码。这些灯都连接到四个按钮：

按钮 $1$：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。

按钮 $2$：当按下此按钮，将改变所有奇数号的灯。

按钮 $3$：当按下此按钮，将改变所有偶数号的灯。

按钮 $4$：当按下此按钮，将改变所有序号是 $3k+1 \ (k \in [0,+\infty) \cap \mathbb Z)$ 的灯。例如：$1,4,7,10 \dots$

一个计数器 $c$ 记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器 $c$ 为 $0$。

你将得到计数器 $c$ 上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。

inputFormat:
第一行一个正整数 $n$；第二行一个整数 $c$，表示最后计数器的数值。
第三行若干个整数，表示最后亮着的灯，以 `-1` 结束。
第四行若干个整数，表示最后关着的灯，以 `-1` 结束。

保证不会有灯会在输入中出现两次。

outputFormat:
每一行是所有灯可能的最后状态（没有重复）。
每一行有 $n$ 个字符，第 $i$ 个字符表示 $i$ 号灯。$0$ 表示关闭，$1$ 表示亮着。这些行必须从小到大排列（看作是二进制数）。

如果没有可能的状态，则输出一行 `IMPOSSIBLE`。

hint:
【数据范围】
对于 $100\%$ 的数据，$10 \le n \le 100$，$0 \le c \le 10^4$。

【样例解释】
在这个样例中，有三种可能的状态：

- 所有灯都关着

- $1,4,7,10$ 号灯关着，$2,3,5,6,8,9$ 亮着。

- $1,3,5,7,9$ 号灯关着，$2,4,6,8,10$ 亮着。

翻译来自NOCOW

USACO 2.2


title: 找筷子

description:
经过一段时间的紧张筹备，电脑小组的“RP 餐厅”终于开业了，这天，经理 LXC 接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的问题:筷子！

CX 小朋友找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成一双，更麻烦的是 CX 找出来的这些筷子数量为奇数，但是巧合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮 CX 找出这只落单的筷子的长度吗？

inputFormat:
第一行是一个整数，表示筷子的数量 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 根筷子的长度 $a_i$。

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

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

- 对于 $30\%$ 的数据，保证 $n \leq 10^5$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^7 + 1$，$1 \leq a_i \leq 10^9$。

#### 提示

- 请注意数据读入对程序效率造成的影响。
- 请注意本题的空间限制为 $4$ Mb。


title: [USACO2.3] 最长前缀 Longest Prefix

description:
在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列（即元素）很感兴趣。

如果一个集合 $P$ 中的元素可以串起来（元素可以重复使用）组成一个序列 $s$ ，那么我们认为序列 $s$ 可以分解为 $P$ 中的元素。元素不一定要全部出现（如下例中 `BBC` 就没有出现）。举个例子，序列 `ABABACABAAB` 可以分解为下面集合中的元素：`{A,AB,BA,CA,BBC}`

序列 $s$ 的前面 $k$ 个字符称作 $s$ 中长度为 $k$ 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列  ，设 $s'$ 是序列 $s$ 的最长前缀，使其可以分解为给出的集合 $P$ 中的元素，求 $s'$ 的长度 $k$。

inputFormat:
输入数据的开头包括若干个元素组成的集合 $O$，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 `.` 的行，集合中的元素没有重复。

接着是大写字母序列 $s$ ，长度为，用一行或者多行的字符串来表示，每行不超过 $76$ 个字符。换行符并不是序列 $s$ 的一部分。

outputFormat: 只有一行，输出一个整数，表示 S 符合条件的前缀的最大长度。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$1\le \text{card}(P) \le 200$，$1\le |S| \le 2\times 10^5$，$P$ 中的元素长度均不超过 $10$。

翻译来自NOCOW

USACO 2.3


title: [USACO2.3] 奶牛家谱 Cow Pedigrees

description:
一个有 $n$ 个节点，深度为 $k$ 的无标号完满二叉树（即每个节点的儿子数为 $0$ 或 $2$）有多少种结构？定义根节点深度为 $1$。

答案对 $9901$ 取模。

inputFormat: 两个空格分开的整数 $n,k$。

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


title: [USACO2.3] 零的数列 Zero Sum

description:
请考虑一个由 $1$ 到 $N$ 的数字组成的递增数列：$1, 2, 3, \ldots, N$。

现在请在数列中插入 `+` 表示加，或者 `-` 表示减，` `（空格） 表示空白（例如 `1-2 3` 就等于 `1-23`），来将每一对数字组合在一起（请不要在第一个数字前插入符号）。

计算该表达式的结果并判断其值是否为 $0$。 请你写一个程序找出所有产生和为零的长度为N的数列。

inputFormat: 单独的一行表示整数 $N$（$3 \leq N \leq 9$）。

outputFormat: 按照 ASCI I码的顺序，输出所有在每对数字间插入 `+`，`-`，` `（空格） 后能得到结果为零的数列。

hint:
翻译来自NOCOW

USACO 2.3


title: [USACO2.3] Money System / [USACO07OCT]Cow Cash G

description:
母牛们不但创建了它们自己的政府而且选择了建立了自己的货币系统。由于它们特殊的思考方式，它们对货币的数值感到好奇。

传统地，一个货币系统是由 $1,5,10,20,25,50,100$ 的单位面值组成的。

母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。

举例来说, 使用一个货币系统 $(1,2,5,10, \ldots)$ 产生 $18$ 单位面值的一些可能的方法是：$18 \times 1, 9 \times 2, 8 \times 2+2 \times 1, 3 \times 5+2+1$，等等。

写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数在 $64$ 位带符号整数的范围内。

inputFormat:
第一行两个整数：货币系统中货币的种类数目 $V$（$1 \leq V \leq 25$）。要构造的数量钱是 $N$（$1 \leq N \leq 10,000$）。

第二行 $V$ 个整数，代表所有可用的货币的面值。

outputFormat: 单独的一行，包含用这 $V$ 种硬币凑足 $N$ 单位货币的方案数。


title: [USACO2.3] 控制公司 Controlling Companies

description:
有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。

据说，如果至少满足了以下三个条件之一，公司 $A$ 就可以控制公司 $B$ 了：

- 公司 $A$ = 公司 $B$。
- 公司 $A$ 拥有大于 $50\%$ 的公司 $B$ 的股票。
- 公司 $A$ 控制 $K$（$K \geq 1$）个公司，记为 $C_1, \ldots, C_K$，每个公司 $C_i$ 拥有 $x_i\%$ 的公司 $B$ 的股票，并且 $x_1+ \ldots + x_K \gt 50\%$。

给你一个表，每行包括三个数 $i,j,p$：表明公司 $i$ 享有公司 $j$ 的 $p\%$ 的股票。计算所有的数对 $(h,s)$，表明公司 $h$ 控制公司 $s$。至多有 $100$ 个公司。

inputFormat:
第一行一个整数 $N$，表明表格的行数。

接下来 $N$ 行，每行三个整数 $i,j,p$，表示 $i$ 公司拥有 $j$ 公司 $p\%$ 的股份。

outputFormat:
输出零个或更多个的控制其他公司的公司。每行包括两个整数 $A,B$，表示 $A$ 公司控制了 $B$ 公司。将输出的数对以 $A$ 为第一关键字，$B$ 为第二关键字升序排列。

请不要输出控制自己的公司（即你输出的数对均要满足 $A \neq B$）。


title: 休息中的小呆

description: 当大家在考场中接受考验（折磨？）的时候，小呆正在悠闲（欠扁）地玩一个叫“最初梦想”的游戏。游戏描述的是一个叫 pass 的有志少年在不同的时空穿越对抗传说中的大魔王 chinesesonic 的故事。小呆发现这个游戏的故事流程设计得很复杂，它有着很多的分支剧情，但不同的分支剧情是可以同时进行的，因此游戏可以由剧情和剧情的结束点组成，某些剧情必须要在一些特定的剧情结束后才能继续发展。为了体验游戏的完整性，小呆决定要看到所有的分支剧情——完成所有的任务。但这样做会不会耽误小呆宝贵的睡觉时间呢？所以就请你来解决这个问题了。

inputFormat:
小呆会给你一个剧情流程和完成条件的列表，

其中第一行有一个数 $n$，表示总共有 $n$ 个剧情结束点；

第二行一个数 $m$，表示有 $m$个不同的剧情；

下面的 $m$ 行中每行有三个数，表示从剧情结束点 $i$ 必须完成一个耗费时间为 $k$ 的剧情才能到达剧情结束点 $j$。

outputFormat: 你要告诉小呆完成整个游戏至少需要多少时间，以及要经过的所有可能的剧情结束点（按升序输出）。


title: [NOI2008] 假面舞会

description:
一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。

今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。

为了使舞会更有神秘感，主办方把面具分为 $k$（$k\geq 3$）类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第 $i$ 类面具的人才能看到戴第 $i+1$  类面具的人的编号，戴第 $k$ 类面具的人能看到戴第 $1$ 类面具的人的编号。

参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己算出有多少类面具，于是他开始在人群中收集信息。

栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第 $2$ 号面具的人看到了第 $5$ 号面具的编号。栋栋自己也会看到一些编号，他也会根据自己的面具编号把信息补充进去。

由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信息不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多少类面具。由于主办方已经声明了 $k\geq 3$，所以你必须将这条信息也考虑进去。

inputFormat: 第一行包含两个整数 $n, m$，用一个空格分隔，$n$ 表示主办方总共准备了多少个面具，$m$ 表示栋栋收集了多少条信息。接下来 $m$ 行，每行为两个用空格分开的整数 $a, b$，表示戴第 $a$ 号面具的人看到了第 $b$ 号面具的编号。相同的数对 $a, b$ 在输入文件中可能出现多次。

outputFormat: 包含两个数，第一个数为最大可能的面具类数，第二个数为最小可能的面具类数。如果无法将所有的面具分为至少 $3$ 类，使得这些信息都满足，则认为栋栋收集的信息有错误，输出两个 `-1`。


title: 陶陶摘苹果（升级版）

description:
又是一年秋季时，陶陶家的苹果树结了 $n$ 个果子。陶陶又跑去摘苹果，这次他有一个 $a$ 公分的椅子。当他手够不着时，他会站到椅子上再试试。

这次与 NOIp2005 普及组第一题不同的是：陶陶之前搬凳子，力气只剩下 $s$ 了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在 $s<0$ 之前最多能摘到多少个苹果。

现在已知 $n$ 个苹果到达地上的高度 $x_i$，椅子的高度 $a$，陶陶手伸直的最大长度 $b$，陶陶所剩的力气 $s$，陶陶摘一个苹果需要的力气 $y_i$，求陶陶最多能摘到多少个苹果。

inputFormat:
第 $1$ 行：两个数 苹果数 $n$，力气 $s$。

第 $2$ 行：两个数 椅子的高度 $a$，陶陶手伸直的最大长度 $b$。

第 $3$ 行~第 $3+n-1$ 行：每行两个数 苹果高度 $x_i$，摘这个苹果需要的力气 $y_i$。

outputFormat: 只有一个整数，表示陶陶最多能摘到的苹果数。


title: 宿舍里的故事之五子棋

description:
宿舍里好多好多有趣的事！

7890653 今天看到不知何时流行的五子棋，在宿舍里拿个本子，画一些格子，一个棋盘就做好了。

当 7890653 把目光放到棋上，突发奇想……

在一个 $5 \times 5$ 的棋盘内，放上 $n$ 颗棋子，其中 $5 \le n \le 25$；

这 $n$ 颗棋子可以放到棋盘内任意一个地方，但是不能重叠在一起。于是，便会有五颗棋子排成一行，或一列，或处在同一条对角线上。不同的放法可能会出现不同个数的五子的排列。

本题你要做的是，给你一个 $n$，你要找出不同放法出现的五子连线的数量（设为 $k$），如 $n=11$，有：

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

只有这两种非负的 $k$ 值，（注意 $k$ 不重复），你要输出的便是 $k$ 值的和。

也就是 $1+2=3$。

inputFormat: 输入共一行一个数 $n$，含义如题意所示。保证 $1\le n\le 25$。

outputFormat: 输出所有可能的 $k$ 值的和。容易发现 $k\le 12$。


title: A/B Problem

description: 输入两个整数 $a,b$，输出它们的商。

inputFormat: 两行，第一行是被除数，第二行是除数。

outputFormat: 一行，商的整数部分。


title: 魔族密码

background:
风之子刚走进他的考场，就……

花花：当当当当~~偶是魅力女皇——花花！！^^（华丽出场，礼炮，鲜花）

风之子：我呕……（杀死人的眼神）快说题目！否则……-\_-###

description:
花花：……咦~~好冷~~我们现在要解决的是魔族的密码问题（自我陶醉：搞不好魔族里面还会有人用密码给我和菜虫写情书咧，哦活活，当然是给我的比较多拉\*^\_^\*）。

魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表，每个单词至少包含 $1$ 个字母，至多 $75$ 个字母。如果在一个由一个词或多个词组成的表中，除了最后一个以外，每个单词都被其后的一个单词所包含，即前一个单词是后一个单词的前缀，则称词表为一个词链。例如下面单词组成了一个词链：

- $\verb!i!$；
- $\verb!int!$；
- $\verb!integer!$。

但下面的单词不组成词链：

- $\verb!integer!$；
- $\verb!intern!$。

现在你要做的就是在一个给定的单词表中取出一些词，组成最长的词链，就是包含单词数最多的词链。将它的单词数统计出来，就得到密码了。

风之子：密码就是最长词链所包括的单词数阿……

inputFormat: 这些文件的格式是，第一行为单词表中的单词数 $N$（$1 \le N \le 2000$），下面每一行有一个单词，按字典顺序排列，中间也没有重复的单词。

outputFormat: 输出共一行，一个整数，表示密码。


title: Cantor表（升级版）

description:
现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

$$\begin{matrix}
1/1 & 1/2 & 1/3 & 1/4 & 1/5 & \cdots \cr
2/1 & 2/2 & 2/3 & 2/4 &  \cdots \cr
3/1 & 3/2 & 3/3 &  \cdots \cr
4/1 & 4/2 &  \cdots \cr
5/1 &  \cdots \cr
\end{matrix}
$$

这次与 NOIp1999 第一题不同的是：这次需输入两个分数（不一定是最简分数），算出这两个分数的积（注意需要约分至最简分数），输出积在原表的第几列第几行（若积形如 $a$（即结果为整数）或者 $1/a$，则看作表内的 $a/1$ 或 $1/a$ 结算）。

inputFormat: 共两行。每行输入一个分数（不一定是最简分数）。

outputFormat: 两个整数，表示输入的两个分数的积在表中的第几列第几行。

hint:
### 数据范围

对于全部数据，两个分数的分母和分子均小于 $10^4$。


title: 序列变换

description:
给定一个由 $n$ 个整数构成的序列 $a_1, a_2, \ldots , a_n$，你需要对它进行如下操作：

1. 输入格式 `1 x y`，表示把所有 $a_{k x}$（$k$ 为正整数，$k x \le n$）都加上 $y$。
2. 输入格式 `2 j`，表示输出 $a_j$。

inputFormat:
第一行，两个数 $n, m$，表示有 $n$ 个数，$m$ 条操作。
第二行，$n$ 个数 $a_1, a_2, \ldots , a_n$。
接下来 $m$ 行，为 $m$ 条操作。

outputFormat: 输出若干行，每行对应一次操作2。


title: 种树

description: cyrcyr 今天在种树，他在一条直线上挖了 $n$ 个坑。这 $n$ 个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr 不会在相邻的两个坑中种树。而且由于 cyrcyr 的树种不够，他至多会种 $k$ 棵树。假设 cyrcyr 有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。

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

第二行，$n$ 个整数，第 $i$ 个数表示在直线上从左往右数第 $i$ 个坑种树的获利。

outputFormat: 输出一个数，表示 cyrcyr 种树的最大获利。

hint:
对于 $20\%$ 的数据，$n\leq 20$。

对于 $50\%$ 的数据，$n\leq 6000$。

对于 $100\%$ 的数据，$1 \le n\leq 300000$，$1 \le k\leq \dfrac{n}{2}$，在一个地方种树获利的绝对值在 $10^6$ 以内。


title: 火枪打怪

description: LXL 进入到了一片丛林,结果他发现有 $n$ 只怪物排成一排站在他面前。LXL 有一杆火枪能对付这些怪物。他知道从左至右数第 $i$ 只怪物的血量是 $m_i$。现在 LXL 可以将一些子弹射向某个怪物。LXL 可以控制他所发射的子弹数量及子弹的威力值。当某个子弹射到第 $i$ 个怪物，如果这个子弹的威力值为 $p$，除了这个怪物会掉 $p$ 点血以外，它左边的第 $j$ 个怪物 $(j<i)$，也会遭到 $\max(0, p - (i - j)^2)$ 的溅射伤害（好神奇的子弹）。当某只怪物的血量小于 $0$ 时，它就死了，但它的尸体还在，即怪物的位置永远不会改变。LXL 希望只用 $k$ 发子弹，请你求出一个最小的正整数 $p$，使 LXL 用 $k$ 发子弹且每发子弹的威力值为 $p$ 就可以消灭所有怪物。

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

第二行，$n$ 个正整数，第 $i$ 个正整数表示从左至右数第 $i$ 只怪物的血量 $m_i$。

outputFormat: 一个正整数，表示子弹的最小威力值 $p$。


title: [NOI2004] 郁闷的出纳员

description:
OIER 公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把当前在公司的所有员工的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。

老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第 $k$ 多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。

好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

如果某个员工的初始工资低于最低工资标准，那么将不计入最后的答案内。

inputFormat:
第一行有两个整数 $n$ 和 $\min$。$n$ 表示下面有多少条命令，$\min$ 表示工资下界。

接下来的 $n$ 行，每行一个字符 $x$ 和一个整数 $k$，表示一条命令。命令可以是以下四种之一：

- `I k`  新建一个工资档案，初始工资为 $k$。如果某员工的初始工资低于工资下界，他将立刻离开公司。
- `A k`   把每位员工的工资加上 $k$。
- `S k`   把每位员工的工资扣除 $k$。
- `F k`    查询第 $k$ 多的工资。

在初始时，可以认为公司里一个员工也没有。

outputFormat:
对于每条 `F` 命令，你的程序要输出一行，仅包含一个整数，为当前工资第  $k$ 多的员工所拿的工资数，如果 $k$ 大于目前员工的数目，则输出 $-1$。

输出的最后一行包含一个整数，为离开公司的员工的总数。

请注意，初始工资低于工资下界的员工不算做离开公司的员工。

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

对于全部的测试点，保证：

- `I` 命令的条数不超过 $10^5$；
- `A` 和 `S` 命令的总条数不超过 $100$；
- `F` 命令的条数不超过 $10^5$；
- 每次工资调整的调整量不超过 $10^3$；
- 新员工的工资不超过 $10^5$。
- $0 \leq n \leq 3 \times 10^5$，$0 \leq \text{min} \leq 10^9$，输入的所有数字均在 $32$ 位带符号整形范围内。


title: 失落的成绩单

background: 谁都知道，录成绩是件麻烦事，可 MC 却把成绩单丢了……

description:
这一天老师要查第 $m$ 个同学的成绩，为了不挨批，MC努力回想，想起成绩单上的一个规律：

若把成绩看作是一个实数数列，则 $A_i=\dfrac{(A_{i-1})-(A_{i+1})}{2}+d$，（就是每一项为其前后两项之差除以 $2$ 再加 $d$）。此时，我告诉了 MC 一共 $n$ 项的数列首项 $A_1$ 和末项 $A_n$，以及 $d$。剩下的靠你了！

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

第二行三个实数，依次是 $d,A_1,A_n$。

outputFormat: 输出一个实数 $A_m$，保留 $3$ 位小数。


title: 肥猫的游戏

description:
野猫与胖子，合起来简称肥猫，是一个班的同学，他们也都是数学高手，所以经常在一起讨论数学问题也就不足为奇了。

一次，野猫遇到了一道有趣的几何游戏题目，便拿给胖子看。游戏要求在一个有 $n$ 个顶点凸多边形上进行，这个凸多边形的 $n-3$ 条对角线将多边形分成 $n-2$ 个三角形，这 $n-3$ 条对角线在多边形的顶点相交。三角形中的一个被染成黑色，其余是白色。

双方轮流进行游戏，当轮到一方时，他必须沿着画好的对角线，从多边形上切下一个三角形。切下黑色三角形的一方获胜。胖子一看觉得确实很有趣，不如就一起玩玩吧。假设游戏由野猫先开始，那么野猫是否有必胜的策略呢？请写一个程序帮助野猫算一算。

inputFormat:
第一行为一个整数 $n$，表示多边形的顶点数，多边形的顶点由 $0$ 至 $n-1$ 顺时针标号。

接着的 $n-2$ 行描述组成多边形的三角形。第 $i+1$ 行 $(1 \leq i \leq n-2)$ 有三个空格分隔的非负整数 $a$ 、$b$ 、$c$ ，它们是第 $i$ 个三角形的顶点编号。第一个给出的三角形是黑色的。

outputFormat: 只有一行，倘若野猫有必胜策略，输出 `JMcat Win`；否则，输出 `PZ Win`（注意大小写和空格）。

hint:
$4 \leq n \leq 5 \times 10^4$。

如果连接一个多边形中任意两点的线段都完全包含于这个多边形，则称这个多边形为凸多边形。


title: 猫狗大战

description:
新一年度的猫狗大战通过 SC（星际争霸）这款经典的游戏来较量，野猫和飞狗这对冤家为此已经准备好久了，为了使战争更有难度和戏剧性，双方约定只能选择 Terran（人族）并且只能造机枪兵。

比赛开始了，很快，野猫已经攒足几队机枪兵，试探性的发动进攻；然而，飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了，于是，便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口，飞狗的兵补给会很快，野猫看敌不过，决定撤退。这时飞狗的兵力也不足够多，所以没追出来。

由于不允许造医生，机枪兵没办法补血。受伤的兵只好忍了。

现在，野猫又攒足了足够的兵力，决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击，野猫决定把现有的兵分成两部分，从两路进攻。由于有些兵在第一次战斗中受伤了，为了使两部分的兵实力平均些，分的规则是这样的：

1. 两部分兵的个数最多只能差一个；
2. 每部分兵的血值总和必须要尽可能接近。

现在请你编写一个程序，给定野猫现在有的兵的个数以及每个兵的血格值，求出野猫按上述规则分成两部分后每部分兵的血值总和。

inputFormat: 第一行为一个整数 $n\ (1 \le n \le 200)$，表示野猫现在有的机枪兵的个数。以下的 $n$ 行每行一个整数，表示每个机枪兵的血格 $(1 \le a_i \le 40)$。

outputFormat: 一行，为两个整数，表示分成两部分后每部分兵的血值总和。要求输出的第一部分兵的血量总和不大于第二部分兵的血量总和。

hint: TO 狗狗：这道题的数据范围我已经尽量按星际的游戏规则来了，如果你再固执于由于机枪兵的攻击力一定使不能达到某些血格值或者游戏中一定要造农民不能使机枪兵的人数达到 $200$ 的话，我只能决定将那场猫狗大战的录像公开于世人了！！！


title: 买蛋糕

description:
野猫过生日，大家当然会送礼物了（咳咳，没送礼物的同志注意了哈！！），由于不知道送什么好，又考虑到实用性等其他问题，大家决定合伙给野猫买一个生日蛋糕。大家不知道最后要买的蛋糕的准确价格，而只会给蛋糕估价，即要买一个不超过多少钱的蛋糕。众 OIer 借此发挥：能否用最少的钱币数去凑成估价范围内的所有价值，使得不管蛋糕价值多少，都不用找钱……

现在问题由此引出：对于一个给定的 $n$，能否用最少的不等的正整数去组成 $n$ 以内（包括 $n$）的所有的正整数呢？如果能，最少需要多少个正整数，用最少个数又有多少不同的组成方法呢？

inputFormat: 只有一行包含一个整数 $n\ (1\le n\le 1000)$。

outputFormat: 一行两个数，第一个数是最少需要多少个数，第二个数是用最少个数的组成方案个数。两个答案用空格分隔。


title: 集合位置

description:
每次有大的活动，大家都要在一起“聚一聚”，不管是去好乐迪，还是避风塘，或者汤姆熊，大家都要玩的痛快。还记得心语和花儿在跳舞机上的激情与释放，还记得草草的投篮技艺是如此的高超，还记得狗狗的枪法永远是 S ……还有不能忘了，胖子的歌声永远是让我们惊叫的！！

今天是野猫的生日，所以想到这些也正常，只是因为是上学日，没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。

但是每次集合的时候都会出现问题！野猫是公认的“路盲”，野猫自己心里也很清楚，每次都提前出门，但还是经常迟到，这点让大家很是无奈。后来，野猫在每次出门前，都会向花儿咨询一下路径，根据已知的路径中，总算能按时到了。

现在提出这样的一个问题：给出 $n$ 个点的坐标，其中第一个为野猫的出发位置，最后一个为大家的集合位置，并给出哪些位置点是相连的。野猫从出发点到达集合点，总会挑一条最近的路走，如果野猫没找到最近的路，他就会走第二近的路。请帮野猫求一下这条第二最短路径长度。

特别地，选取的第二短路径**不会重复经过同一条路**，即使可能重复走过同一条路多次路程会更短。

inputFormat: 第一行是两个整数 $n(1 \le n \le 200)$ 和 $m(1 \le m\le 10000)$，表示一共有 $n$ 个点和 $m$ 条路，以下 $n$ 行每行两个数 $x_i$，$y_i$，$(-500 \le x_i,y_i \le 500),$ 代表第 $i$ 个点的坐标，再往下的 $m$ 行每行两个整数 $p_j$，$q_j,(1 \le p_j,q_j \le n)$，表示两个点之间有一条路，数据没有重边，**可能有自环**。

outputFormat: 只有一行包含一个数，为第二最短路线的距离（保留两位小数），如果存在多条第一短路径，则答案就是第一最短路径的长度；如果不存在第二最短路径，输出 `-1`。


title: 猩猩散步

description:
猩猩，骆驼，还有泡泡经常喜欢在饭后到操场上散步，由于猩猩的走路姿势最突出最显眼，理所应当的成为他们中的主角，所以我的题目就说猩猩散步了。（骆驼和泡泡别有意见哈，和猩猩争啥……）

当然，话说回来，猩猩在 OI 上的能力也是不容低估的，你看，散步时还会想一道与此相关的问题，这是道经典的不能再经典的问题了。

在一个 $m×n$ 的矩阵上，猩猩在左下角的顶点出现了，他只能沿着路径向上或者向右走，他的目标是“蠕动”到右上角的顶点，问他有多少路径可以选择。嗯，这个、这个、这个似乎地球人都知道怎么做，但是请注意，我有个条件没给呢！$m$ 和 $n$ 现在的最大范围是 $5\times 10^4$，这可怎么办？仔细想想吧。

inputFormat: 只有一行，包含两个整数 $m$ 和 $n$，其上限均为 $5\times 10^4$。

outputFormat: 由于最后的答案数目过大，所以只检查后 $100$ 位，输出时每行十个数字，没空格间隔，共十行，如果答案位数没超过 $100$ 位，则需要在空位上补 $0$。


title: 分梨子

description:
Finley 家的院子里有棵梨树，最近收获了许多梨子。于是，Finley 决定挑出一些梨子，分给幼稚园的宝宝们。可是梨子大小味道都不太一样，一定要尽量挑选那些差不多的梨子分给孩子们，那些分到小梨子的宝宝才不会哭闹。

每个梨子都具有两个属性值，$A_i$ 和 $B_i$，本别表示梨子的大小和甜度情况。假设在选出的梨子中，两个属性的最小值分别是 $A_0$ 和 $B_0$。只要对于所有被选出的梨子 $i$，都满足 $C_1 \times (A_i-A_0)+C_2 \times (B_i-B_0) \le C_3$（其中，$C_1,C_2$ 和 $C_3$ 都是已知的常数），就可以认为这些梨子是相差不多的，可以用来分给小朋友们。

那么，作为幼稚园园长的你，能算出最多可以挑选出多少个梨子吗？

inputFormat:
第一行一个整数 $N$（$1 \le N \le 2000$），表示梨子的总个数。

第二行三个正整数，依次为 $C_1,C_2$ 和 $C_3$（$C_1,C_2 \le 2000$，$C_3 \le 10^9$）。

接下来的 $N$ 行，每行两个整数。第 $i$ 行的两个整数依次为 $A_i$ 和 $B_i$。

outputFormat: 只有一个整数，表示最多可以选出的梨子个数。

hint:
### 样例说明

可以选择 $1,3$ 两个梨子或者 $2,3$ 两个梨子。


title: [国家集训队] 小 Z 的袜子

description:
upd on 2020.6.10 ：更新了时限。

作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 $(L,R)$ 以方便自己选择。

**然而数据中有 $L=R$ 的情况，请特判这种情况，输出`0/1`。**

inputFormat: 输入文件第一行包含两个正整数 $N$ 和 $M$。$N$ 为袜子的数量，$M$ 为小 Z 所提的询问的数量。接下来一行包含 $N$ 个正整数 $C_i$，其中 $C_i$ 表示第 $i$ 只袜子的颜色，相同的颜色用相同的数字表示。再接下来 $M$ 行，每行两个正整数 $L, R$ 表示一个询问。

outputFormat: 包含 $M$ 行，对于每个询问在一行中输出分数 $A/B$ 表示从该询问的区间 $[L,R]$ 中随机抽出两只袜子颜色相同的概率。若该概率为 $0$ 则输出 `0/1`，否则输出的 $A/B$ 必须为最简分数。（详见样例）


title: 【模板】中国剩余定理（CRT）/ 曹冲养猪

description: 自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 $16$ 头母猪，如果建了 $3$ 个猪圈，剩下 $1$ 头猪就没有地方安家了。如果建造了 $5$ 个猪圈，但是仍然有 $1$ 头猪没有地方去，然后如果建造了 $7$ 个猪圈，还有 $2$ 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

inputFormat: 第一行包含一个整数 $n$ —— 建立猪圈的次数，接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示建立了 $a_i$ 个猪圈，有 $b_i$ 头猪没有去处。你可以假定 $a_1 \sim a_n$ 互质。

outputFormat: 输出包含一个正整数，即为曹冲至少养母猪的数目。


title: 火烧赤壁

background:
曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。

隆冬的十一月，天气突然回暖，刮起了东南风。

没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。

曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！

description: 给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。

inputFormat:
第一行一个整数，表示起火的信息条数 $n$。
接下来 $n$ 行，每行两个整数 $a, b$，表示一个着火位置的起点和终点（**注意：左闭右开**）。

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

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

对于全部的测试点，保证 $1 \leq n \leq 2 \times 10^4$，$-2^{31} \leq a <  b \lt 2^{31}$，且答案小于 $2^{31}$。


title: 木牛流马

background:
孔明造出了木牛流马。

> 木牛者，方腹曲头，一脚四足，头入领中，舌著于腹。载多而行少，宜可大用，不可小使；特行者数十里，群行者二十里也。曲者为牛头，双者为牛脚，横者为牛领，转者为牛足，覆者为牛背，方者为牛腹，垂者为牛舌，曲者为牛肋，刻者为牛齿，立者为牛角，细者为牛鞅，摄者为牛秋轴。牛仰双辕，人行六尺，牛行四步。载一岁粮，日行二十里，而人不大劳。流马尺寸之数，肋长三尺五寸，广三寸，厚二寸二分，左右同。前轴孔分墨去头四寸，径中二寸。前脚孔分墨二寸，去前轴孔四寸五分，广一寸。前杠孔去前脚孔分墨二寸七分，孔长二寸，广一寸。后轴孔去前杠分墨一尺五分，大小与前同。后脚孔分墨去后轴孔三寸五分，大小与前同。后杠孔去后脚孔分墨二寸七分，后载克去后杠孔分墨四寸五分。前杠长一尺八寸，广二寸，厚一寸五分。后杠与等版方囊二枚，厚八分，长二尺七寸，高一尺六寸五分，广一尺六寸，每枚受米二斛三斗。从上杠孔去肋下七寸，前后同。上杠孔去下杠孔分墨一尺三寸，孔长一寸五分，广七分，八孔同。前后四脚，广二寸，厚一寸五分。形制如象，靬长四寸，径面四寸三分。孔径中三脚杠，长二尺一寸，广一寸五分，厚一寸四分，同杠耳。（《三国志·亮集载作木牛流马法》）

可是在现实中它有个缺陷，就是两个不能在同一行或同一列！

description: 孔明兴高采烈的叫庞统来参观，孔明存心想难一难庞统，他把 $k$ 个木牛流马放在一个大的 $n \times n$ 的格子地板上，并且给他们都染上色，想让庞统帮着算算有多少种不同的合理布局情况？

inputFormat:
第一行: $n, k, h$（$n \le 20$，$h$ 为有多少种颜色）。

接下来 $h$ 行为每种颜色多少个。

outputFormat: 合理布局情况总数。

hint: 不需要高精度，并且孔明规定在格子地板上不能翻转，也就是说如果两种布局在翻转后是一样的仍算两种。


title: 南蛮图腾

background: 自从到了南蛮之地，孔明不仅把孟获收拾的服服帖帖，而且还发现了不少少数民族的智慧，他发现少数民族的图腾往往有着一种分形的效果，在得到了酋长的传授后，孔明掌握了不少绘图技术，但唯独不会画他们的图腾，于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙，作为一个好孙子的孙子的孙子的孙子……你能做到吗？

description: 给定一个正整数 $n$，参考输出样例，输出图形。

inputFormat: 每个数据输入一个正整数 $n$，表示图腾的大小（此大小非彼大小）

outputFormat: 这个大小的图腾

hint: 数据保证，$1 \leq n \leq 10$。


title: [CTSC2000] 公路巡逻

description:
在一条没有分岔的高速公路上有 $n$ 个关口，相邻两个关口之间的距离都是 $10\rm km$ 。所有车辆在这条高速公路上的最低速度为 $60\rm km/h$ ，最高速度为 $120\rm km/h$，并且只能在关口处改变速度。

巡逻的方式是在某个时刻 $T_{i}$ 从第 $n_{i}$ 个关口派出一辆巡逻车匀速驶抵第 $n_{i+1}$ 个关口，路上耗费的时间为 $t_{i}$ 秒。

两辆车相遇是指它们之间发生超车或者两车同时到达某关口（同时出发不算相遇）。

巡逻部门想知道一辆于 $6$ 点整从第 $1$ 个关口出发去第 $n$ 个关口的车（称为目标车）最少会与多少辆巡逻车相遇，请编程计算之。假设所有车辆到达关口的时刻都是整秒。

inputFormat:
输入文件第一行为两个整数，分别为关口数 $n$ 和巡逻车数 $m$ 。

接下来的 $m$ 行每一行为一辆巡逻车的信息（按出发位置递增排序），格式为 $n_{i}$，$T_{i}$，$t_{i}$，分别表示第 $i$ 辆巡逻车的出发位置、出发时刻和路上耗费的时间，其中 $n_{i}$ 和 $T_{i}$ 为整数， $T_{i}$ 形如 `HHMMSS`，表示时、分、秒，采用 $24$ 小时制，不足两位的数用前置 $0$ 补齐。

outputFormat:
输出文件第一行为目标车与巡逻车相遇次数。

第二行为目标车与巡逻车相遇次数最少时最早到达第 $n$ 个关口的时刻（格式同输入中的 $T_{i}$ ）。


title: 丘比特的烦恼

background:
随着社会的不断发展，人与人之间的感情越来越功利化。最近，爱神丘比特发现，爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼，他越来越难找到合适的男女，并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国，找到了掌管东方人爱情的神——月下老人，向他求教。

月下老人告诉丘比特，纯洁的爱情并不是不存在，而是他没有找到。在东方，人们讲究的是缘分。月下老人只要做一男一女两个泥人，在他们之间连上一条红线，那么它们所代表的人就会相爱——无论他们身处何地。而丘比特的爱情之箭只能射中两个距离相当近的人，选择的范围自然就小了很多，不能找到真正的有缘人。

description:
情人节（Valentine's day）的午夜零时，丘比特开始了自己的工作。他选择了一组数目相等的男女，感应到他们互相之间的缘分大小，并依此射出了神箭，使他们产生爱意。他希望能选择最好的方法，使被他选择的每一个人被射中一次，且每一对被射中的人之间的缘分的和最大。

当然，无论丘比特怎么改造自己的弓箭，总还是存在缺陷的。首先，弓箭的射程尽管增大了，但毕竟还是有限的，不能像月下老人那样，做到“千里姻缘一线牵”。其次，无论怎么改造，箭的轨迹终归只能是一条直线，也就是说，如果两个人之间的连线段上有别人，那么莫不可向他们射出丘比特之箭，否则，按月下老人的话，就是“乱点鸳鸯谱”了。

作为一个凡人，你的任务是运用先进的计算机为丘比特找到最佳的方案。

inputFormat:
输入第一行为正整数 $k$，表示丘比特之箭的射程。

第二行为正整数 $n$。

随后有 $2 \times n$ 行，表示丘比特选中的人的信息，其中前 $n$ 行为男子，后 $n$ 行为女子。

每个人的信息由两部分组成：他的姓名和他的位置。姓名是长度小于 $20$ 且仅包含字母的字符串，忽略大小写的区别，位置是由一对整数表示的坐标，它们之间用空格分隔。格式为 ```x y Name```。

输入文件剩下的部分描述了这些人的缘分。每一行的格式为 ```Name1 Name2 p```。

`Name1` 和 `Name2` 为有缘人的姓名，$p$ 是他们之间的缘分值（$p$ 为小于等于 $255$ 的正整数）。

以一个 ```End``` 作为文件结束标志。

每两个人之间的缘分至多只被描述一次。如果没有被描述，则说明他们缘分值为 $1$。

outputFormat: 输出仅一个正整数，表示每一对被射中的人之间的缘分的总和。这个和应当是最大的。

samples:
2
3
0 0 Adam
1 1 Jack
0 2 George
1 0 Victoria
0 1 Susan
1 2 Cathy
Adam Cathy 100
Susan George 20
George Cathy 40
Jack Susan 5
Cathy Jack 30
Victoria Jack 20
Adam Victoria 15
End

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

CTSC2000 第二试


title: [国家集训队] Tree II

description:
一棵 $n$ 个点的树，每个点的初始权值为 $1$。
对于这棵树有 $q$ 个操作，每个操作为以下四种操作之一：

- `+ u v c`：将 $u$ 到 $v$ 的路径上的点的权值都加上自然数 $c$；
- `- u1 v1 u2 v2`：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$，保证操作完之后仍然是一棵树；
- `* u v c`：将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$；
- `/ u v`：询问 $u$ 到 $v$ 的路径上的点的权值和，将答案对 $51061$ 取模。

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

接下来 $n-1$ 行每行两个正整数 $u,v$，描述这棵树的每条边。

接下来 $q$ 行，每行描述一个操作。

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

hint:
【数据范围】
对于 $10\%$ 的数据，$1\le n,q \le 2000$；
另有 $15\%$ 的数据，$1 \le n,q \le 5\times 10^4$，没有 `-` 操作，并且初始树为一条链；
另有 $35\%$ 的数据，$1 \le n,q \le 5\times 10^4$，没有 `-` 操作；
对于 $100\%$ 的数据，$1\le n,q \le 10^5$，$0\le c \le 10^4$。

By (伍一鸣)


title: 窗口的星星

background: 小卡买到了一套新房子，他十分的高兴，在房间里转来转去。

description:
晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户。

天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。

这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

inputFormat:
本题有多组数据，第一行为 $T$，表示有 $T$ 组数据。

对于每组数据：

第一行 $3$ 个整数 $n,W,H$ 表示有 $n$ 颗星星，窗口宽为 $W$，高为 $H$。

接下来 $n$ 行，每行三个整数 $x_i,y_i,l_i$ 表示星星的坐标在 $(x_i,y_i)$，亮度为 $l_i$。

outputFormat: $T$ 个整数，表示每组数据中窗口星星亮度总和的最大值。

hint:
为了便于理解，输入样例中每组数据之间添加了空行，实际测试数据中并无空行。

小卡买的窗户框是金属做的，所以在边框上的不算在内。

### 数据范围

对于 $100\%$ 的数据：$1\le T \le 10$，$1\le n \le 10^4$，$1\le W,H \le 10^6$，$0\le x_i,y_i < 2^{31}$。


title: 鬼子进村

background: 小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

description:
县城里有 $n$ 个用地道相连的房子，第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。这时有 $m$ 个消息依次传来：

1. 若消息为 ```D x```：鬼子将 $x$ 号房子摧毁了，地道被堵上。

1. 若消息为 ```R``` ：村民们将鬼子上一个摧毁的房子修复了。

2. 若消息为 ```Q x```：有一名士兵被围堵在 $x$ 号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

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

接下来 $m$ 行，有如题目所说的三种信息共 $m$ 条。

outputFormat: 对于每一个被围堵的士兵，输出该士兵能够到达的房子数。

hint:
$1\leq n,m\leq 5\times 10^4$。

若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。


title: 积木城堡

description:
XC 的儿子小 XC 最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。

小 XC 是一个比他爸爸 XC 还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。

小 XC 想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。为了公平起见，他决定送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。

可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。

任务：

请你帮助小 XC 编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。

注意：一座城堡的高度，是组成它的所有积木的棱长之和。

inputFormat:
第一行是一个整数 $n$，表示一共有 $n$ 座城堡。

以下 $n$ 行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的**棱长**。用 `-1` 结束。

outputFormat:
一个整数，表示最后城堡的最大可能的高度。
如果找不到合适的方案，则输出 $0$。

hint:
【数据范围】
对于 $100\%$ 的数据，$1 \le n \le 100$，一座城堡中的积木不超过 $100$ 块，每块积木的棱长不超过 $100$。


title: [国家集训队] 旅游

background:
Ray 乐忠于旅游，这次他来到了 T 城。T 城是一个水上城市，一共有 $n$ 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有 $n-1$ 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度 $w$，也就是说，Ray 经过这座桥会增加 $w$ 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从 $u$ 景点到 $v$ 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

description:
给定一棵 $n$ 个节点的树，边带权，编号 $0 \sim n-1$，需要支持五种操作：

- `C i w` 将输入的第 $i$ 条边权值改为 $w$；
- `N u v` 将 $u,v$ 节点之间的边权都变为相反数；
- `SUM u v` 询问 $u,v$ 节点之间边权和；
- `MAX u v` 询问 $u,v$ 节点之间边权最大值；
- `MIN u v` 询问 $u,v$ 节点之间边权最小值。

保证任意时刻所有边的权值都在 $[-1000,1000]$ 内。

inputFormat:
第一行一个正整数 $n$，表示节点个数。
接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的边，描述这棵树。
然后一行一个正整数 $m$，表示操作数。
接下来 $m$ 行，每行表示一个操作。

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

hint:
【数据范围】

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

2020.02.04 修正了一点数据的错误
2020.03.14 加入了一组 hack 数据
2020.11.26 加入了一组 hack 数据 By @_Leaving


title: 拯救oibh总部

background: oibh 总部突然被水淹没了！现在需要你的救援……

description:
oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 `*` 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 `0` 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

inputFormat:
第一行为两个正整数 $x,y$。

接下来 $x$ 行，每行 $y$ 个整数，由 `*` 和 `0` 组成，表示 oibh 总部的建设图。

outputFormat: 输出没被水淹没的 oibh 总部的 `0` 的数量。


title: NASA的食物计划

background: NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。

description: 航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

inputFormat:
第一行 $2$ 个整数，分别代表体积最大值 $h$ 和质量最大值 $t$。

第二行 $1$ 个整数代表食品总数 $n$。

接下来 $n$ 行每行 $3$ 个数 体积 $h_i$，质量 $t_i$，所含卡路里 $k_i$。

outputFormat: 一个数，表示所能达到的最大卡路里（`int` 范围内）


title: Likecloud-吃、吃、吃

background:
问世间，青春期为何物？

答曰：“甲亢，甲亢，再甲亢；挨饿，挨饿，再挨饿！”

description:
正处在某一特定时期之中的李大水牛由于消化系统比较发达，最近一直处在饥饿的状态中。某日上课，正当他饿得头昏眼花之时，眼前突然闪现出了一个 $n \times m(n,m \le 200)$ 的矩型的巨型大餐桌，而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了 $n \times m$ 个小方格，每一个方格中都有一个圆形的巨型大餐盘，上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分（有些是负的，因为吃了要拉肚子），他决定从自己所处的位置吃到餐桌的另一侧，但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。

由于李大水牛已饿得不想动脑了，而他又想获得最大的能量，因此，他将这个问题交给了你。

每组数据的出发点都是最后一行的中间位置的下方！

inputFormat:
第一行为m n（n为奇数），李大水牛一开始在最后一行的中间的下方

接下来为m\*n的数字距阵.

共有m行,每行n个数字.数字间用空格隔开.代表该格子上的盘中的食物所能提供的能量.

数字全是整数.

outputFormat: 一个数,为你所找出的最大能量值.

hint: 快吃！快吃！快吃！


title: 找啊找啊找GF

background:
“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”

“诶，别再见啊…”

七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。

但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -\_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。

description:
sqybi 现在看中了 $n$ 个 MM，我们不妨把她们编号 $1$ 到 $n$。请 MM 吃饭是要花钱的，我们假设请 $i$ 号 MM 吃饭要花 $rmb[i]$ 块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第 $i$ 号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费 $rp[i]$ 的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞定她的时间，对于第 $i$ 个 MM 来说叫做 $time[i]$。sqybi 保证自己有足够的魅力用 $time[i]$ 的时间搞定第 $i$ 个 MM ^\_^。

sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。

sqybi 现在有 $m$ 块大洋,他也通过一段时间的努力攒到了 $r$ 的人品（这次为模拟赛出题也攒 rp 哦\~\~）。他凭借这些大洋和人品可以泡到一些 MM。他想知道，自己泡到最多的 MM 花费的最少时间是多少。

注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…

inputFormat:
输入的第一行是 $n$，表示 sqybi 看中的 MM 数量。

接下来有 $n$ 行，依次表示编号为 $1, 2, 3, \ldots , n$ 的一个 MM 的信息。每行表示一个 MM 的信息，有三个整数：$rmb$，$rp$ 和 $time$。

最后一行有两个整数，分别为 $m$ 和 $r$。

outputFormat: 你只需要输出一行，其中有一个整数，表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。

hint:
sqybi 说：如果题目里说的都是真的就好了…

sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为 $0$），他要用这些时间出七夕比赛的题来攒 rp…

**【数据规模】**

对于 $20 \%$ 的数据，$1 \le n \le 10$；
对于 $100 \%$ 的数据，$1 \le rmb \le 100$，$1 \le rp \le 100$，$1 \le time \le 1000$。
对于 $100 \%$ 的数据，$1 \le m, r, n \le 100$。


title: 精卫填海

description:
本题为改编题。

> 发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

事实上，东海未填平的区域还需要至少体积为 $v$ 的木石才可以填平，而西山上的木石还剩下 $n$ 块，每块的体积和把它衔到东海需要的体力分别为 $k$ 和 $m$。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为 $c$。

inputFormat:
输入文件的第一行是三个整数：$v,n,c$。

从第二行到第 $n+1$ 行分别为每块木石的体积和把它衔到东海需要的体力。

outputFormat: 输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出 `Impossible`（不带引号）。


title: [SDOI2006] 数字串位置 / 超长数字串

background: George 很喜欢数学，尤其是算数数系列。

description:
他最喜欢的是数字的无穷序列，结果是把所有的自然数按升序排列。这个序列开始是：$\texttt{1234567891011121314...}$

我们称这个序列为序列 $S$，然后 $S_1 = 1$, $S_2 = 2$, ... , $S_{10} = 1$, $S_{11} = 0$，依此类推.

George 现有一个数字序列 $A$ ，他想知道这个序列在 $S$ 中最早出现的位置。请你帮助他解决这个问题。

inputFormat: 输入一个字符串，表示数字序列 $A$ ，位数不超过 $200$，中间没有空格。

outputFormat: 输出使 $A_1 = S_k, A_2 = S_{k+1}, ...,A_{len_{A}} = S_{k + len(A)-1}$ 成立的最小正整数 $k$，其中 $len_{A}$ 表示序列 $A$ 的长度。

hint:
来源 Source

Ural State University Problem Archive


title: 伊甸园日历游戏

description:
Adam 和 Eve 玩一个游戏，他们先从 $1900.1.1$ 到 $2006.11.3$ 这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作：

1. 把日期的天数加 $1$，例如 $1900.1.1$ 变到 $1900.1.2$；
2. 把月份加 $1$，例如：$1900.1.1$ 变到 $1900.2.1$。

其中如果天数超过应有天数则日期变更到下个月的第 $1$ 天。月份超过 $12$ 则变到下一年的 $1$ 月。而且进行操作二的时候，如果有这样的日期：$1900.1.31$，则变成了 $1900.2.31$，这样的操作是非法的，我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。

谁先将日期变到 $2006.11.4$ 谁就赢了。如果超越了指定日期不算获胜。

每次游戏都是 Adam 先操作，问他有没有必胜策略？

inputFormat:
第一行一个整数，为数据组数。

接下来一行 $X,Y,Z$ 表示 $X$ 年 $Y$ 月 $Z$ 日。

outputFormat: 输出 `YES` 或者 `NO` 表示 Adam 是否有必胜策略。


title: 绕钉子的长绳子

description:
平面上有 $N$ 个圆柱形的大钉子，半径都为 $R$，所有钉子组成一个凸多边形。

现在你要用一条绳子把这些钉子围起来，绳子直径忽略不计。求出绳子的长度。

inputFormat:
第一行共两个数，整数 $N\ (1 \le N \le 100)$ 和实数 $R$。

接下来 $N$ 行按逆时针顺序给出 $N$ 个钉子中心的坐标。

坐标的绝对值不超过 $100$。

outputFormat: 一个数，绳子的长度，精确到小数点后 $2$ 位。

hint: 本题来自 URAL1020，翻译来自 NOCOW。


title: [NOIP2010 提高组] 引水入城

background: NOIP2010 提高组 T4

description:
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 $N$ 行 $M$ 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

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

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此，只有与湖泊毗邻的第 $1$ 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 $N$ 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

inputFormat: 每行两个数，之间用一个空格隔开。输入的第一行是两个正整数 $N,M$，表示矩形的规模。接下来 $N$ 行，每行 $M$ 个正整数，依次代表每座城市的海拔高度。

outputFormat: 两行。如果能满足要求，输出的第一行是整数 $1$，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数 $0$，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。


title: 旅行

description:
你要进行一个行程为 $7000$ 千米的旅行，现在沿途有些汽车旅馆，为了安全起见，每天晚上都不开车，住在汽车旅馆，你手里现在已经有一个旅馆列表，用离起点的距离来标识，如下：

- $[0,990,1010,1970,2030,2940,3060,3930,4060,4970,5030,5990,6010,7000]$。

但在出发之前可能还要增加一些旅馆。

现在旅行社为了节约成本，要求每天至少行驶 $A$ 公里，国家旅行社为了安全起见，要求每天最多只能行驶 $B$ 公里。

你想知道一共有多少种旅行方案。

inputFormat:
第一行输入一个整数 $A$，第二行输入一个整数 $B$，第三行输入 $N$（$0 \le N \le 20$），表示在出发之前又新增 $N$ 个汽车旅馆；

接下来 $N$ 行，每行一个整数 $m$，表示旅馆离起点的距离（$0<m<7000$）。注意：没有任意两个旅馆在同一位置。

outputFormat: 输出一共有多少种旅行方案。


title: 青蛙的约会

description:
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 $0$ 度处为原点，由东往西为正方向，单位长度 $1$ 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 $x$，青蛙 B 的出发点坐标是 $y$。青蛙 A 一次能跳 $m$ 米，青蛙 B 一次能跳 $n$ 米，两只青蛙跳一次所花费的时间相同。纬度线总长 $L$ 米。现在要你求出它们跳了几次以后才会碰面。

inputFormat: 输入只包括一行五个整数 $x,y,m,n,L$。

outputFormat: 输出碰面所需要的次数，如果永远不可能碰面则输出一行一个字符串 `Impossible`。

tags: 扩展欧几里德算法,exgcd


title: 高精求小数幂

description:
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.

This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R <= 9999.9) and n is an integer such that 0 < n <= 250.

inputFormat: The input will consist of a set (less than 11) of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.

outputFormat: The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.

translation:
计算量非常大、精度要求非常高的问题是很常见的。举个例子，计算国家债务就是这么一项对于许多计算机系统来说非常繁重的工作。

现在有这么一个任务要求编写一个程序来计算R^n的精确值，其中R是一个实数(0.0 < R <= 9999.9)而n是一个整数（0 < n <= 250）。

输入将包含一个小于11行的文件，其中每一行包括一个R和一个n，中间用空格隔开（数量不定但是保证R的第一位在第一列而n的末位在第九列）

对于每一个输入需要有一行的输出，表示R^n的精确值。有三点要求：

1、输出不允许有前导0

2、不允许无意义的尾随0（如1.90中的0不能输出）

3、如果结果是整数，不应该打印小数点

如果你不知道如何确定输入的末尾值:

以下是一些帮助

string s; int n;

c++版while(cin >> s >> n) {…这里是你的代码}

c版while(scanf("%s%d"，s，&n)==2) //以查看scanf是否按需要的数量读取。

{…这里是你的代码}

感谢 @SLYZ_0120  提供的翻译。

hint:
If you don't know how to determine wheather encounted the end of input:

s is a string and n is an integer

C++
while(cin>>s>>n)

{
...
}
c
while(scanf("%s%d",s,&n)==2) //to see if the scanf read in as many items as you want

{
...
}


title: [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two

description:
两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为（牛和 John）。

追击在 $10 \times 10$ 的平面网格内进行。一个格子可以是：一个障碍物，两头牛（它们总在一起），或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内（当他们相遇时），但是他们都不能进入有障碍的格子。

一个格子可以是：
- `.` 空地；
- `*` 障碍物；
- `C` 两头牛；
- `F` Farmer John。

这里有一个地图的例子：

```plain
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
```

牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍（地图边沿也是障碍），它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时，它们不会离开地图。

Farmer John 深知牛的移动方法，他也这么移动。

每次（每分钟）Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。

读入十行表示地图。每行都只包含 10 个字符，表示的含义和上面所说的相同。保证地图中只有一个 `F` 和一个 `C`。`F` 和 `C` 一开始不会处于同一个格子中。

计算 Farmer John 需要多少分钟来抓住他的牛，假设牛和 Farmer John 一开始的行动方向都是正北（即上）。 如果 John 和牛永远不会相遇，输出 0。

inputFormat: 输入共十行，每行 10 个字符，表示如上文描述的地图。

outputFormat: 输出一个数字，表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛，则输出 0。

hint:
翻译来自NOCOW

USACO 2.4


title: [USACO2.4] 穿越栅栏 Overfencing

description:
Farmer John 在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。

给定迷宫的宽度 $W$（$1 \leq W \leq 38$）及高度 $H$（$1 \leq H \leq 100$）。$2 \times H+1$ 行，每行 $2 \times W+1$ 的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）。

当然了，牛们只会水平或垂直地在 X 或 Y 轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）。

这是一个 $W=5,H=3$ 的迷宫：

```plain
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |
+-+ +-+-+-+
```
如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。

inputFormat:
第一行两个整数 $W,H$。

接下来 $2 \times H+1$ 行：每行 $2 \times W+1$ 个字符，描述一个迷宫。

outputFormat: 输出一个单独的整数，表示最坏情况下牛走出迷宫的最小步数。


title: 因式分解

background: 某天，小 W 正在上数学课，听见老师讲解因式分解增补删除及十字相乘法的技巧，感觉非常厉害，于是想用这些技巧来做题，但做着做着遇到一道不会做的题，你能帮帮他吗？

description: 在整多项式环内对多项式 $x^n-1$ 作因式分解（简单点说就是做因式分解题），要求分解到全部为素多项式为止（即最后结果不能有可继续分解的多项式）。

inputFormat: 输入共一行，一个正整数 $n$。

outputFormat:
输出一行一个字符串，表示因式分解的结果。

最后的输出中每个因式应该不含空格，在可以省略 $0$、$1$、乘号和括号的情况下应该尽可能省略。

有多个因式时，每个因式应该降幂排列，并且保证首项系数为正。

除此以外，我们要求按如下顺序排列因式：

- 优先输出次数低的因式，对于次数相同的因式，依次比较每个因式的系数，从高指数项到低指数项（包括被省略即系数为 $0$ 的项）。
- 系数首先比较绝对值，其次比较符号。规定绝对值小的系数字典序小，绝对值相同时比较符号，负号字典序比正号小。字典序越小的因式应该排在越前面输出。详见样例。


title: 求逆序对

description:
我们说$(i,j)$ 是 $a_1,a_2,\cdots,a_N$ 的一个逆序对，当且仅当 $i<j$ 且 $a_i>a_j$。例如 $[2,4,1,3,5]$ 的逆序对有 $3$ 个，分别为 $(1,3),(2, 3), (2, 4)$。现在已知 $N$ 和 $K$，求 $1,2,3,\cdots,N$ 的所有特定排列，使得这些排列的逆序对的数量恰好为 $K$。输出这些特定排列的数量。

例如 $N=5$，$K=3$ 的时候，满足条件的排列有 $15$ 个，它们是：

- $[1, 2, 5, 4, 3]$；
- $[1, 3, 4, 5, 2]$；
- $[1, 3, 5, 2, 4]$；
- $[1, 4, 2, 5, 3]$；
- $[1, 4, 3, 2, 5]$；
- $[1, 5, 2, 3, 4]$；
- $[2, 1, 4, 5, 3]$；
- $[2, 1, 5, 3, 4]$；
- $[2, 3, 1, 5, 4]$；
- $[2, 3, 4, 1, 5]$；
- $[2, 4, 1, 3, 5]$；
- $[3, 1, 2, 5, 4]$；
- $[3, 1, 4, 2, 5]$；
- $[3, 2, 1, 4, 5]$；
- $[4, 1, 2, 3, 5]$。

inputFormat: 输入共第一行，两个整数 $N$ 和 $K$。

outputFormat: 将 $1\cdots N$ 的逆序对数量为 $K$ 的特定排列的数量输出。为了避免高精度计算，请将结果对 $10000$ 取模后再输出。

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

对于全部数据，保证 $N \le 100$，$K \le N\times (N-1)/2$。


title: [USACO2.4] 牛的旅行 Cow Tours

description:
Farmer John 的农场里有很多 **牧区**。有的路径连接一些特定的牧区。**一片所有连通的牧区** 称为一个 **牧场**。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通。这样，Farmer John 就有 **多个** 牧场了。

John 想在牧场里添加 **恰好** 一条路径。对这条路径有以下限制：

一个牧场的 **直径** 就是牧场中 **最远** 的两个牧区的距离（本题中所提到的所有距离指的都是 **最短的距离**）。考虑如下的有 5 个牧区的牧场，牧区用 `*` 表示，路径用直线表示。每一个牧区都有自己的坐标：

```plain
                (15,15) (20,15)
                 D       E
                 *-------*
                 |     _/|
                 |   _/  |
                 | _/    |
                 |/      |
        *--------*-------*
        A        B       C
     (10,10)  (15,10) (20,10)
```
这个牧场的直径大约是 $12.07106$，最远的两个牧区是 A 和 E，它们之间的最短路径是 $A \to B \to E$。

这里是 John 的另一个牧场：

```plain
                         *F(30,15)
                        /
                      _/
                    _/
                   /
                  *------*
                  G      H
                  (25,10)   (30,10)
```

在这个例子中，他刚好有这两个牧场。John 将会在这两个牧场中各选一个牧区（即从 $\{A,B,C,D,E\}$ 中选择一个牧区，从 $\{F,G,H\}$ 中选择一个牧区），然后用一条路径将它们连起来，使得连通后这个新的更大的牧场的直径尽可能小。

注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵：

```plain
　 A  B  C  D  E  F  G  H
A  0  1  0  0  0  0  0  0
B  1  0  1  1  1  0  0  0
C  0  1  0  0  1  0  0  0
D  0  1  0  0  1  0  0  0
E  0  1  1  1  0  0  0  0
F  0  0  0  0  0  0  1  0
G  0  0  0  0  0  1  0  1
H  0  0  0  0  0  0  1  0
```

其他邻接表中可能直接使用行列而不使用字母来表示每一个牧区。输入数据中不包括牧区的名字。

输入文件 **至少** 包括两个不连通的牧区。

请编程找出一条连接属于两个 **不同牧场** 的牧区的路径，使得连上这条路径后，这个更大的新牧场的直径尽可能小。输出在所有合法的连接方案中，新牧场直径的最小值。

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 150$），表示牧区数。

接下来 $N$ 行，每行两个整数 $X,Y$（$0 \leq X ,Y \leq 10^5$），表示 $N$ 个牧区的坐标。注意每个牧区的坐标都是不一样的。

接下来 $N$ 行，每行 $N$ 个数字，代表邻接矩阵 $M$。第 $i$ 行第 $j$ 列的数字为 $1$，表示 $i$ 号牧区和 $j$ 号牧区之间存在一条道路直接相连；第 $i$ 行第 $j$ 列的数字为 $0$，表示 $i$ 号牧区和 $j$ 号牧区之间不存在直接相连的道路。

保证 $M_{i,j} = M_{j,i}$。

outputFormat:
只有一行，包括一个实数，表示所求直径。数字保留六位小数。

只需要打到小数点后六位即可，不要做任何特别的四舍五入处理。

hint:
样例对应题目描述中的情况。

最优解是连接 C 牧区和 G 牧区，连接后图上只有一个牧场。这个牧场的直径为 $A \to B \to C \to G \to F$，长度约为 $22.071068$。可以证明不存在更优的方案。

USACO 2.4


title: 旅行商简化版

background:
欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解，但是有办法在多项式时间内求出一个较优解。

为了简化问题，而且保证能在多项式时间内求出最优解，J.L.Bentley 提出了一种叫做 bitonic tour 的哈密尔顿环游。它的要求是任意两点 $(a,b)$ 之间的相互到达的代价 $\mathrm{dist}(a,b)=\mathrm{dist}(b, a)$ 且任意两点之间可以相互到达，并且环游的路线只能是从最西端单向到最东端，再单项返回最西端，并且是一个哈密尔顿回路。

description:
本题为著名的 NPC 难题的简化版本。

现在笛卡尔平面上有 $n\ (n \le 1000)$ 个点，每个点的坐标为 $(x,y)$，（$-2^{31}<x,y<2^{31}$，且为整数），任意两点之间相互到达的代价为这两点的欧几里德距离，现要你编程求出最短 bitonic tour。

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

接下来 $n$ 行，每行两个整数 $x,y$，表示某个点的坐标。

输入中保证没有重复的两点，保证最西端和最东端都只有一个点。

outputFormat: 一行，即最短回路的长度，保留 $2$ 位小数。

hint:
### 题目来源

《算法导论（第二版）》 15-1


title: 十字绣

background: 考古学家发现了一块布，布上做有针线活，叫做“十字绣”，即交替地在布的两面穿线。

description:
布是一个 $n\times m$ 的网格，线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一，而在绣的过程中，一针中连续的两段线必须分处布的两面。给出布两面的图案（实线代表该处有线，虚线代表背面有线），问最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。

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

inputFormat:
第一行两个数 $N$ 和 $M(1 \le N,M \le 200)$。

接下来 $N$ 行每行 $M$ 个数描述正面。

再接下来 $N$ 行每行 $M$ 个数描述反面。

每个格子的表示如下：

- $\verb!.!$ 表示空格；
- $\verb!/!$ 表示从右上角连到左下角的线；
- $\verb!\!$ 表示从左上角连到右下角的线；
- $\verb!X!$ 表示两条对角线交叉。

outputFormat: 一个数，最少要用的针数。


title: [NOIP2010 提高组] 关押罪犯

background: NOIP2010 提高组 T3

description:
S 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1\sim N$。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 $N$ 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

inputFormat: 每行中两个数之间用一个空格隔开。第一行为两个正整数 $N,M$，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 $M$ 行每行为三个正整数 $a_j,b_j,c_j$，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$。数据保证 $1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9$，且每对罪犯组合只出现一次。

outputFormat: 共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 `0`。

hint:
**输入输出样例说明**

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 $3512$（由 $2$ 号和 $3$ 号罪犯引发）。其他任何分法都不会比这个分法更优。

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

**数据范围**

对于 $30\%$ 的数据有 $N\leq 15$。

对于 $70\%$ 的数据有 $N\leq 2000,M\leq 50000$。

对于 $100\%$ 的数据有 $N\leq 20000,M\leq 100000$。


title: [NOI2003] 智破连环阵

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

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

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

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

outputFormat: 一行包含一个整数 $x$，表示实际使用的炸弹数。


title: [国家集训队] 矩阵乘法

description: 给你一个 $n \times n$ 的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第 $k$ 小数。

inputFormat:
第一行有两个整数，分别表示矩阵大小 $n$ 和询问组数 $q$。

第 $2$ 到第 $(n + 1)$ 行，每行 $n$ 个整数，表示这个矩阵。第 $(i + 1)$ 行的第 $j$ 个数表示矩阵第 $i$ 行第 $j$ 列的数 $a_{i, j}$。

接下来 $q$ 行，每行五个整数 $x_1, y_1, x_2, y_2, k$，表示一组询问，要求找到以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩形中的第 $k$ 小数。

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


title: 切蛋糕

description: Facer今天买了 $n$ 块蛋糕，不料被信息组中球球等好吃懒做的家伙发现了，没办法，只好浪费一点来填他们的嘴巴。他答应给每个人留一口，然后量了量每个人口的大小。Facer 有把刀，可以切蛋糕，但他不能把两块蛋糕拼起来，但是他又不会给任何人两块蛋糕。现在问你，facer 怎样切蛋糕，才能满足最多的人。（facer 的刀很强，切的时候不会浪费蛋糕）。

inputFormat: 第一行 $n$，facer 有 $n$ 个蛋糕。接下来 $n$ 行，每行表示一个蛋糕的大小。再一行一个数 $m$，为信息组的人数，然后 $m$ 行，每行一个数，为一个人嘴的大小。$(1\le n\le 50$，$ 1\le m\le 1024)$

outputFormat: 一行，facer最多可以填多少张嘴巴。


title: [USACO2.4] 回家 Bessie Come Home

description:
现在是晚餐时间，而母牛们在外面分散的牧场中。

Farmer John 按响了电铃，所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓（在给出的测试数据中，总会**有且只有**一只最快的母牛）。在挤奶的时候（晚餐前），每只母牛都在她自己的牧场上，一些牧场上可能没有母牛。

每个牧场由一条条道路和一个或多个牧场连接（可能包括自己）。有时，两个牧场（可能是字母相同的）之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此，所有的母牛最后都能到达谷仓，并且母牛总是走最短的路径。当然，母牛能向着任意一方向前进，并且她们以相同的速度前进。牧场被标记为 $\texttt{a} \ldots \texttt{z}$ 和 $\texttt{A} \ldots \texttt{Y}$，在用大写字母表示的牧场中有一只母牛，小写字母中则没有。 谷仓的标记是 $\texttt{Z}$，注意没有母牛在谷仓中。

**注意 $\texttt{m}$ 和 $\texttt{M}$ 不是同一个牧场**。

inputFormat:
第一行一个整数 $P$（$1\leq P \leq 10^4$），表示连接牧场（谷仓）的道路的数目。

接下来 $P$ 行，每行用空格分开的两个字母和一个正整数：被道路连接牧场的标号和道路的长度（道路长度均不超过 $10^3$）。

outputFormat: 单独的一行包含二个项目：最先到达谷仓的母牛所在的牧场的标号，和这只母牛走过的路径的长度。

hint:
翻译来自 NOCOW

USACO 2.4


title: [USACO2.4] 分数化小数 Fractions to Decimals

description:
写一个程序，输入一个形如 $\dfrac{N}{D}$ 的分数，输出它的小数形式。如果小数有循环节的话，把循环节放在一对圆括号中。

例如，$\dfrac{1}{3}=0.33333333\ldots$ 写成 $0.(3)$，$\dfrac{41}{333}= 0.123123123\ldots$ 写成 $0.(123)$，整数 $x$ 写成 $x.0$。

inputFormat: 输入包含两个整数 $N$ 和 $D$（$1 \leq N,D \leq 10^5$）。

outputFormat: 输出按照上面规则计算出的小数表达式。如果结果长度大于 $76$，每行输出 $76$ 个字符。


title: I Hate It

background: 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

description: 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

inputFormat:
第一行，有两个正整数 $n$ 和 $m$（$0<n \le 2\times 10^5,0<m<5000$），分别代表学生的数目和操作的数目。学生 ID 编号分别从 $1$ 编到 $n$。

第二行包含 $n$ 个整数，代表这 $n$ 个学生的初始成绩，其中第 $i$ 个数代表 ID 为 $i$ 的学生的成绩。

接下来有 $m$ 行。每一行有一个字符 $c$（只取 `Q` 或 `U`），和两个正整数 $a$，$b$。

- 当 $c$ 为 `Q` 的时候，表示这是一条询问操作，它询问 ID 从 $a$ 到 $b$（包括 $a,b$） 的学生当中，成绩最高的是多少；
- 当 $c$ 为 `U` 的时候，表示这是一条更新操作，如果当前 $a$ 学生的成绩低于 $b$，则把 ID 为 $a$ 的学生的成绩更改为 $b$，否则不改动。

outputFormat: 对于每一次询问操作输出一行一个整数，表示最高成绩。


title: 卡布列克圆舞曲

description:
卡布列克是一位数学家，他在研究数字时发现：任意一个不是用完全相同数字组成的四位数，如果对它们的每位数字重新排序，组成一个较大的数和一个较小的数，然后用较大数减去较小数，差不够四位数时补零，类推下去，最后将变成一个固定的数：$6174$，这就是卡布列克常数，例如：

$4321-1234=3087$。

$8730-378=8352$。

$8532-2358=6174$。

$7641-1467=6174$。

如果 $K$ 位数也照此办理，它们不是变成一个数，而是在几个数字之间形成循环，称作卡布列克圆舞曲。例如对于五位数 $54321$：

$54321-12345=41976$。

$97641-14679=82962$。

$98622-22689=75933$。

$97533-33579=63954$。

$96543-34569=61974$。

$97641-14679=82962$。

我们把 $82962,75933,63954,61974$ 称作循环节，即卡布列克圆舞曲。

inputFormat: 若干行，每行为一个待求“卡布列克圆舞曲”的起始整数 $n$。（$n<2^{31}$）

outputFormat: 每行为对应整数的循环节，数据之间用空格隔开。


title: 可怜的狗狗

description:
小卡家有  $n$ 只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。

可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第  $i$ 只到第  $j$ 只狗中第  $k$ 漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间  $[i,j]$ 不互相包含。

inputFormat:
第一行输入两个数  $n,m$， $m$ 表示嘉嘉喂食的次数

第二行  $n$ 个整数，表示第  $i$ 只狗的漂亮值为  $a_i$。

接下来  $m$ 行，每行  $3$ 个整数  $i,j,k$，表示询问这次喂食喂第  $i$ 到第  $j$ 只狗中第  $k$ 漂亮的狗的漂亮值。

outputFormat: $m$ 行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。


title: 不高兴的津津（升级版）

description:
津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每天妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。

这次与 NOIp2004 普及组第一题不同的是：假设津津不会因为其它事不高兴，但是她的不高兴会（当然高兴也会）持续到第二天。请你帮忙检查一下津津以后 $n$ 天的日程安排，看看以后 $n$ 天她会不会不高兴（计算方法：用昨天不高兴程度加上今天上课总时间减去 $8$ 后得到的数作为今天不高兴程度）；输出以后 $n$ 天结束后不高兴程度和是多少。

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

第二行至第 $n+1$ 行，每行两个数，表示这天上学时间和课外补习班时间。

outputFormat: 一个数，这 $n$ 天过后的不高兴程度和。

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

对于全部数据，上学时间和上课时间各不超过 $8$，和不超过 $16$，$n \le 3000$。


title: [USACO08MAR] Cow Travelling S

description:
奶牛们在被划分成 $N$ 行 $M$ 列（$2 \leq N,M \leq 100$）的草地上游走， 试图找到整块草地中最美味的牧草。

Farmer John 在某个时刻看见贝茜在位置 $(R_1, C_1)$，恰好 $T$（$0 \lt T \leq 15$）秒后，FJ 又在位置 $(R_2, C_2)$ 与贝茜撞了正着。FJ 并不知道在这 $T$ 秒内贝茜是否曾经到过 $(R_2, C_2)$，他能确定的只是，现在贝茜在那里。

设 $S$ 为奶牛在 $T$ 秒内从 $(R_1, C_1)$ 走到 $(R_2, C_2)$ 所能选择的路径总数，FJ 希望有一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动 $1$ 单位距离（奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。

现在你拿到了一张整块草地的地形图，其中 `.` 表示平坦的草地，`*` 表示挡路的树。你的任务是计算出，一头在 $T$ 秒内从 $(R_1, C_1)$ 移动到 $(R_2, C_2)$ 的奶牛可能经过的路径有哪些。

inputFormat:
第一行包含 $3$ 个用空格隔开的整数：$N,M,T$。

接下来 $N$ 行：第 $i$ 行为 $M$ 个连续的字符，描述了草地第 $i$ 行各点的情况，保证字符是 `.` 和 `*` 中的一个。

最后一行 $4$ 个整数 $R_1,C_1,R_2,C_2$。

hint: 奶牛在 $6$ 秒内从 $(1,3)$ 走到 $(1,5)$ 的方法只有一种，绕过她面前的树。


title: 村村通

description: 某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

inputFormat:
输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 $n$ 和道路数目 $m$ ；随后的 $m$ 行对应 $m$ 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 $1$ 到 $n$ 编号。

注意：两个城市间可以有多条道路相通。

**在输入数据的最后，为一行一个整数 $0$，代表测试数据的结尾。**

outputFormat: 对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。


title: 弹珠

description: 玛莎和比尔各自有自己的弹珠收藏。他们想重新分配收藏品，使两人能平等拥有弹珠。如果所有的弹珠的价值相同，那么他们就可以平分。但不幸的是，有一些弹珠更大，或者更美丽，所以，玛莎和比尔给每个弹珠一个 $1$ 到 $6$ 的价值。现在他们想平分这些弹珠，使每个人得到的总价值相同。不幸的是，他们发现，他们可能无法以这种方式分弹珠（即使弹珠的总价值为偶数）。例如，如果有一个价值为 $1$、一个价值为 $3$ 和两个价值为 $4$ 的弹珠，这样他们就不能把弹珠分为价值相等的两部分。因此，他们想要你写一个程序，告诉他们是否能将所有弹珠分成价值相等的两部分。

inputFormat:
输入文件有若干行，行中包含六个非负整数 $N_1,\cdots,N_6$，其中 $N_i$ 是价值为 $i$ 的弹珠的个数。最大弹珠总数将达到 $2\times 10^4$。

输入文件的最后一行是 `0 0 0 0 0 0`。不要处理这一行。

outputFormat:
对于每一组数据，输出 `Collection #k:`，$k$为输出的是第几组，接着是 `Can be divided.` 或 `Can't be divided.`。

每一组输出后多打一个空行。可以参考样例。

samples:
Collection #1:
Can't be divided.

Collection #2:
Can be divided.


title: 迎春舞会之数字舞蹈

background: HNSDFZ 的同学们为了庆祝春节，准备排练一场舞会。

description:
在越来越讲究合作的时代，人们注意的更多的不是个人物的舞姿，而是集体的排列。

为了配合每年的倒计时，同学们决定排出——“数字舞蹈”。顾名思义就是所有人一起排成若干个数字 -\_\_\_-||||  更为创新的是，每个人都是趴在地上，保证横竖。

现在给出数字及其要求摆出的大小，请你编程，模拟同学们的优美姿态。

inputFormat:
第一行为 $k$。$k$ 表示要摆出数字的大小。

第二行为全部由数字组成的字符串，即要摆出的几个数字。

outputFormat: 按题目要求输出。详见样例。

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

对于全部数据，$k \le 30$，$ 0<|s|\le 255$。除了第一个数字之外，每个数字之前有 $1$ 个空格，所有数字全部对齐。

建议大家直接输出，不要保存。

如果对于大小和 $k$ 有疑问，请自行理解。


title: [TJOI2011] 01矩阵

description: $n\times m$ 的 $01$ 矩阵，其中某些位置已经确定，为 '.' 的位置可以填 $0$ 或 $1$，求相邻两个位置不同为 $1$ 的矩阵方案数，答案模 $10007$。

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

接下来输入一个 $n\times m$ 的矩阵，由 $\verb!0!,\verb!1!,\verb!.!$ 组成。

outputFormat: 输出一个整数，为相邻两个位置不同为 $1$ 的矩阵个数。

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

对于 $100\%$ 的数据，$n\times m \le 225$。


title: [NOIP2010 提高组] 机器翻译

background: NOIP2010 提高组 T1

description:
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 $M$ 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 $M-1$，软件会将新单词存入一个未使用的内存单元；若内存中已存入 $M$ 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为 $N$ 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

inputFormat:
共 $2$ 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 $M,N$，代表内存容量和文章的长度。

第二行为 $N$ 个非负整数，按照文章的顺序，每个数（大小不超过 $1000$）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

outputFormat: 一个整数，为软件需要查词典的次数。

hint:
### 样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

1. `1`：查找单词 1 并调入内存。
2. `1 2`：查找单词 2 并调入内存。
3. `1 2`：在内存中找到单词 1。
4. `1 2 5`：查找单词 5 并调入内存。
5. `2 5 4`：查找单词 4 并调入内存替代单词 1。
6. `2 5 4`：在内存中找到单词 4。
7. `5 4 1`：查找单词 1 并调入内存替代单词 2。

共计查了 $5$ 次词典。

### 数据范围

- 对于 $10\%$ 的数据有 $M=1$，$N \leq 5$；
- 对于 $100\%$ 的数据有 $1 \leq M \leq 100$，$1 \leq N \leq 1000$。


title: [NOIP2010 提高组] 乌龟棋

background: NOIP2010 提高组 T2

description:
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

inputFormat:
每行中两个数之间用一个空格隔开。

第 $1$ 行 $2$ 个正整数 $N,M$，分别表示棋盘格子数和爬行卡片数。

第 $2$ 行 $N$ 个非负整数，$a_1,a_2,…,a_N$，其中 $a_i$ 表示棋盘第 $i$ 个格子上的分数。

第 $3$ 行 $M$ 个整数，$b_1,b_2,…,b_M$，表示 $M$ 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 $M$ 张爬行卡片。

outputFormat: 一个整数，表示小明最多能得到的分数。

hint:
每个测试点 1s。

小明使用爬行卡片顺序为 $1,1,3,1,2$，得到的分数为 $6+10+14+8+18+17=73$。注意，由于起点是 $1$，所以自动获得第 $1$ 格的分数 $6$。

对于 $30\%$ 的数据有 $1≤N≤30,1≤M≤12$。

对于 $50\%$ 的数据有 $1≤N≤120,1≤M≤50$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $20$。

对于 $100\%$ 的数据有 $1≤N≤350,1≤M≤120$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$；$0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$。


title: 包裹快递

description:
小 K 成功地破解了密文。但是乘车到 X 国的时候，发现钱包被偷了，于是无奈之下只好作快递员来攒足路费去 Orz 教主……

一个快递公司要将 $n$ 个包裹分别送到 $n$ 个地方，并分配给邮递员小 K 一个事先设定好的路线，小 K 需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小 K 得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。

为了节省燃料，小 K 希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。

inputFormat:
第 1 行为一个正整数 $n$，表示需要运送包裹的地点数。

下面 $n$ 行，第 $i+1$ 行有 3 个正整数 $x _ i, y _ i, s _ i$，表示按路线顺序给出第 $i$ 个地点签收包裹的时间段为 $[x _ i, y _ i]$，即最早为距出发时刻 $x _ i$，最晚为距出发时刻 $y _ i$，从前一个地点到达第 $i$ 个地点距离为 $s _ i$，且保证路线中 $x _ i$ 递增。

可以认为 $s _ 1$ 为出发的地方到第 $1$ 个地点的距离，且出发时刻为 $0$。

outputFormat: 仅包括一个正数，为车的最大速度最小值，结果保留两位小数。


title: [POI2004] SZP

background: 一班班花 [$\color{red}{\texttt{y}}\color{black}{\texttt{hb}}$](/user/835809) 十分可爱。

description:
班花 [$\color{red}{\texttt{y}}\color{black}{\texttt{hb}}$](/user/835809) 在英語课上管理着 $n$ 名同学。除了她以外每一名同学都监视着另一名同学。现在班花 [$\color{red}{\texttt{y}}\color{black}{\texttt{hb}}$](/user/835809) 需要选择尽量多的同学去搬英語作业，且使得对于这些同学中的每一名同学，至少有一位监视她的同学没有被选中。问班花 [$\color{red}{\texttt{y}}\color{black}{\texttt{hb}}$](/user/835809) 最多可以选择多少同学。

由于班花 [$\color{red}{\texttt{y}}\color{black}{\texttt{hb}}$](/user/835809) 太可爱了，所以没有人监视她，也可以认为她的学号是 $0$。

如果一个人没有被监视，那么她就不能被选择。

inputFormat:
第一行只有一个整数，$n$ 代表同学的数量。同学的学号从 $1$ 到 $n$ 编号。

接下来 $n$ 行每行一个整数 $a_k$ 表示同学 $k$ 将要监视同学 $a_k$，$1 \le k \le n$，$1 \le a_k \le n$，$a_k \ne k$。

outputFormat: 一个数，最多能有多少同学参加入这个任务。


title: 三倍经验

description:
数字金字塔由 $n$ 行整数组成，第 $i(1\le i\le n)$ 行有 $i$ 个数字，一个示例如下。
```text
        7
      3   9
    8   1   0
  2   7   4   4
4   5   2   6   5
```
现在你在金字塔的顶部（第一行），你希望走到金字塔的底部（第 $n$ 行），每一步你只能走向当前所在位置的左下方的数字或者右下方的数字。同时作为一个强大的小朋友，你可以选择金字塔中的不多于 $k$ 个数字让他们成为原来的 $3$ 倍。

你会收集你路上经过的所有位置上的数字，最后的得分即为收集的数字之和，求最大得分。

inputFormat:
第一行输入两个整数 $n,k$，表示数字金字塔的行数和乘 $3$ 的数字个数最大值；
接下来 $n$ 行，其中的第 $i$ 行有 $i$ 个以空格隔开的整数依次表示数字金字塔第 $i$ 行的数字 $a_{i,1},a_{i,2},a_{i,3}...a_{i,i}$。

outputFormat: 一行一个整数，表示最大得分。

hint:
对于 $30\%$ 的数据，满足 $k\le n\le 6$，并且对于任意 $1\le i\le n$，$1\le j\le i$ 满足 $0\le a_{i,j}\le 100$；
对于 $100\%$ 的数据，满足 $1\le n\le100$，$0\le k\le \dfrac{n(n+1)}{2}$，且对于任意 $1\le i\le n$，$1\le j\le i$ 满足 $|a_{i,j}|\le 10^9$。


title: [USACO04DEC] Dividing the Path G

description:
约翰的奶牛们发现山脊上的草特别美味。为了维持草的生长，约翰打算安装若干喷灌器。

为简化问题，山脊可以看成一维的数轴，长为 $L\ (1\le L\le 10^6)$，而且 $L$ 一定是一个偶数。每个喷灌器可以双向喷灌，并有确定的射程，该射程不短于 $A$，不长于 $B$，$A$，$B(1\le A\le B\le 10^3)$ 都是给出的正整数。它所在位置的两边射程内，都属它的灌溉区域。

现要求山脊的每一个区域都被灌溉到，而且喷灌器的灌溉区域不允许重叠。约翰有 $N(1\le N\le 10^3)$ 只奶牛，每一只都有特别喜爱的草区，第 $i$ 奶牛的草区是 $[S_i,E_i]$，不同奶牛的草区可以重叠。现要求，每只奶牛的草区仅被一个喷灌器灌溉。

注意：

1. 数轴 $L$ 从 $0$ 开始标记（即坐标范围 $0\sim L$）
2. 喷灌器坐标和射程必须为整数，对于坐标为 $i$ 射程为 $x$ 的喷灌器，它的灌溉范围为 $[i-x,i+x]$。
3. 浇灌区间必须在山脊范围内。例如，不能在 $0$ 位置放一个半径为 $1$ 的浇灌器。

寻找最少需要的喷灌器数目。

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

第二行两个整数 $A,B$。

然后 $N$ 行每一行两个整数 $S_i,E_i$（$1\le S_i < E_i\le L$）。

outputFormat: 一行，输出所需的最少洒水器数量。如果无法为农夫约翰设计喷头配置，则输出 $-1$。


title: [USACO3.1] 最短网络 Agri-Net

background: Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

description:
FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 $10^5$。

inputFormat:
第一行农场的个数 $N$（$3 \leq N \leq 100$）。

接下来是一个 $N \times N$ 的矩阵，表示每个农场之间的距离。理论上，他们是 $N$ 行，每行由 $N$ 个用空格分隔的数组成，实际上，由于每行 $80$ 个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是 $0$，因为不会有线路从第 $i$ 个农场到它本身。

outputFormat: 只有一个输出，其中包含连接到每个农场的光纤的最小长度。

hint:
题目翻译来自NOCOW。

USACO Training Section 3.1


title: [USACO05MAR] Out of Hay S

description:
Bessie 计划调查 $N$（$2 \leq N \leq 2\,000$）个农场的干草情况，它从 $1$ 号农场出发。农场之间总共有 $M$（$1 \leq M \leq 10^4$）条双向道路，所有道路的总长度不超过 $10^9$。有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

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

接下来 $M$ 行，每行三个用空格隔开的整数 $A_i,B_i,L_i$，表示 $A_i,B_i$ 之间有一条道路，长度为 $L_i$。

outputFormat: 一个整数，表示最小生成树中的最长边的长度。


title: [NOIP1997 普及组] 棋盘问题

background: NOIP1997 普及组第一题

description:
设有一个 $N \times M$ 方格的棋盘 $(1≤N≤100,1≤M≤100)$

求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。

例如：当 $N=2, M=3$ 时：

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

正方形的个数有 $8$ 个：即边长为 $1$ 的正方形有 $6$ 个；边长为 $2$ 的正方形有 $2$ 个。

长方形的个数有 $10$ 个：

即

- $2 \times 1$ 的长方形有 $4$ 个：

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

- $1 \times 2$ 的长方形有 $3$ 个：

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

- $3 \times 1$ 的长方形有 $2$ 个：

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

- $3 \times 2$ 的长方形有 $1$ 个：

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

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

outputFormat: 一行两个整数，表示正方形的个数与长方形的个数。


title: [NOIP1997 提高组] 棋盘问题

background:
NOIP1997 提高组第一题

[P5512](https://www.luogu.com.cn/problem/P5512) 为本题数据加强版。

本题实际的数据的范围是 $1\le N\le 5$。不保证存在可以通过原数据范围的非打表做法。

description:
在 $N \times N$（$1 \le N \le 10$）的棋盘上，填入 $1, 2, \dots, N ^ 2$ 共 $N ^ 2$ 个数，使得任意两个相邻的数之和为素数。

例如：当 $N = 2$ 时，有：

| $1$ | $2$ |
| :-----------: | :-----------: |
| $4$ | $3$ |

其相邻数的和为素数的有：

$1+2,1+4,4+3,2+3$

当 $N=4$ 时，一种可以填写的方案如下：

| $1$ | $2$ | $11$ | $12$ |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $16$ | $15$ | $8$ | $5$ |
| $13$ | $4$ | $9$ | $14$ |
| $6$ | $7$ | $10$ | $3$ |

在这里我们约定：左上角的格子里必须填数字 $1$。

inputFormat: 一个数 $N$。

outputFormat: 如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出 `NO`。


title: [USACO08OCT] Watering Hole G

description:
Farmer John 的农场缺水了。

他决定将水引入到他的 $n$ 个农场。他准备通过挖若干井，并在各块田中修筑水道来连通各块田地以供水。在第 $i$ 号田中挖一口井需要花费 $W_i$ 元。连接 $i$ 号田与 $j$ 号田需要 $P_{i,j}$（$P_{j,i}=P_{i,j}$）元。

请求出 FJ 需要为使所有农场都与有水的农场相连或拥有水井所需要的最少钱数。

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

接下来 $n$ 行，每行一个整数 $W_i$。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 个数表示连接 $i$ 号田和 $j$ 号田需要的费用 $P_{i,j}$。

outputFormat: 输出最小开销。


title: 亲戚

background: 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

description: 规定：$x$ 和 $y$ 是亲戚，$y$ 和 $z$ 是亲戚，那么 $x$ 和 $z$ 也是亲戚。如果 $x$，$y$ 是亲戚，那么 $x$ 的亲戚都是 $y$ 的亲戚，$y$ 的亲戚也都是 $x$ 的亲戚。

inputFormat:
第一行：三个整数 $n,m,p$，（$n,m,p \le 5000$），分别表示有 $n$ 个人，$m$ 个亲戚关系，询问 $p$ 对亲戚关系。

以下 $m$ 行：每行两个数 $M_i$，$M_j$，$1 \le M_i,~M_j\le n$，表示 $M_i$ 和 $M_j$ 具有亲戚关系。

接下来 $p$ 行：每行两个数 $P_i,P_j$，询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。

outputFormat: $p$ 行，每行一个 `Yes` 或 `No`。表示第 $i$ 个询问的答案为“具有”或“不具有”亲戚关系。


title: [APIO2012] 派遣

background: 在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。

description:
在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。

现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。

你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。

写一个程序，给定每一个忍者 $i$ 的上级 $B_i$，薪水 $C_i$，领导力 $L_i$，以及支付给忍者们的薪水总预算 $M$，输出在预算内满足上述要求时顾客满意度的最大值。

inputFormat:
第一行包含两个整数 $N$ 和 $M$，其中 $N$ 表示忍者的个数，$M$表示薪水的总预算。

接下来 $N$ 行描述忍者们的上级、薪水以及领导力。其中的第i行包含三个整数 $B_i,C_i,L_i$ 分别表示第 $i$ 个忍者的上级，薪水以及领导力。Master 满足 $B_i=0$，并且每一个忍者的老板的编号一定小于自己的编号 $B_i\lt i$。

outputFormat: 一行一个整数，表示在预算内顾客的满意度的最大值。


title: 数字反转（升级版）

background:
**以下为原题面，仅供参考:**

给定一个数，请将该数各个位上数字反转得到一个新数。

这次与 NOIp2011 普及组第一题不同的是：这个数可以是小数，分数，百分数，整数。整数反转是将所有数位对调；小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分；分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母；百分数的分子一定是整数，百分数只改变数字部分。整数新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零；小数新数的末尾不为 $0$（除非小数部分除了 $0$ 没有别的数，那么只保留1个 $0$）；分数不约分，分子和分母都不是小数（约分滴童鞋抱歉了，不能过哦。输入数据保证分母不为 $0$），本次没有负数。

description:
给定一个数，请将该数各个位上数字反转得到一个新数。

这次与 NOIp2011 普及组第一题不同的是：这个数可以是小数，分数，百分数，整数。

- 整数反转是将所有数位对调。

- 小数反转是把整数部分的数反转，再将小数部分的数反转，不交换整数部分与小数部分。

- 分数反转是把分母的数反转，再把分子的数反转，不交换分子与分母。

- 百分数的分子一定是整数，百分数只改变数字部分。

inputFormat: 一个实数 $s$

outputFormat: 一个实数，即 $s$ 的反转数

hint:
**【数据范围】**

- 对于 $25\%$ 的数据，$s$ 是整数，不大于 $20$ 位；
- 对于 $25\%$ 的数据，$s$ 是小数，整数部分和小数部分均不大于 $10$ 位；
- 对于 $25\%$ 的数据，$s$ 是分数，分子和分母均不大于 $10$ 位；
- 对于 $25\%$ 的数据，$s$ 是百分数，分子不大于 $19$ 位。

**【数据保证】**

- 对于整数翻转而言，整数原数和整数新数满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数和原来的数字的最高位数字不应为零。

- 对于小数翻转而言，其小数点前面部分同上，小数点后面部分的形式，保证满足小数的常见形式，也就是末尾没有多余的 $0$（小数部分除了 $0$ 没有别的数，那么只保留 $1$ 个 $0$。若反转之后末尾数字出现 $0$，请省略多余的 $0$）

- 对于分数翻转而言，分数不约分，分子和分母都不是小数。输入的分母不为 $0$。与整数翻转相关规定见上。

- 对于百分数翻转而言，见与整数翻转相关内容。

数据不存在负数。


title: 梦中的统计

background: Bessie 处于半梦半醒的状态。过了一会儿，她意识到她在数数，不能入睡。

description:
Bessie 的大脑反应灵敏，仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码（$0 \ldots 9$）：每一个数码在计数的过程中出现过多少次？

给出两个整数 $M$ 和 $N$，求在序列 $[M, M + 1, M + 2, \ldots, N - 1, N]$ 中每一个数码出现了多少次。

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

outputFormat: 第 $1$ 行: 十个用空格分开的整数，分别表示数码 $0 \ldots 9$ 在序列中出现的次数。

hint: 数据保证，$1 \leq M \leq N \leq 2 \times 10^9$，$N-M \leq 5 \times 10^5$。


title: 尴尬的数字

background: Bessie 刚刚学会了不同进制数之间的转换，但是她总是犯错误，因为她的两个前蹄不能轻松的握住钢笔。

description:
每当 Bessie 将一个数转换成新的进制时，她总会写错一位数字。例如，她将 14 转化成 2 进制数，正确的结果是 1110，但她可能会写成 0110 或 1111。Bessie 从不会意外的增加或删减数字，所以她可能会写出以 0 开头的错误数字。

给出 Bessie 转换后 $N$ 的 2 进制形式和 3 进制形式，请计算出 $N$ 的正确数值（用十进制表示）。$N$ 可能会达到 $10^9$，输入数据保证解的存在唯一性。

inputFormat:
第一行，$N$ 的 2 进制表示（有一位是错误的数字）。

第二行，$N$ 的 3 进制表示（有一位是错误的数字）。

outputFormat: $N$ 的正确值。


title: 幸福的路

description:
每天，John 都要为了农场里 $n$（$1 \leq n\leq 10$） 头牛的健康和幸福四处奔波。

每头牛的位置可以描述为一个二维坐标，John 从坐标原点 $(0,0)$ 出发。为了使路径更有趣，John 决定只沿着平行于坐标轴的方向行走，这样只能沿着东西南北方向运动。而且只有到达某头牛的坐标后 John 才会改变行走的方向（当然，如果有必要，John 也会穿过某头牛的坐标而不改变行走的方向。）

如果 John 改变行走的方向，他会原地转 $90^\circ$ 或者 $180^\circ$。John 的路径必须保证检查完所有牛后返回原点。

John 可以穿过某头牛的坐标而不改变方向任意次，请计算出有多少条路径满足 John 能检查完 $n$ 头牛，在每头牛的坐标处恰好改变一次方向。同一条路径从不同方向经过要计算两次。

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

第二行到第 $n+1$ 行，第 $i+1$ 行是两个用空格隔开的整数 $x$ 和 $y$，表示第 $i$ 头牛的坐标（$-1000 \leq x,y \leq 1000$）。

outputFormat: 一行一个整数，表示路径的量。如果没有满足要求则输出 $0$。


title: Kruscal的加法

background: 奶牛 Kruscal 认为人类的加法太落后了。比如说有时候想要用加法计算 `+15*3`，只能写成 `+15+15+15`，真是浪费精力啊！于是，Kruscal 决定开发出一种新的加法算式。

description:
当然，新的算式也是建立在原本算式的基础上的，不同就在于上式可以直接写成 `+++15`，同理，对于 `-15*3` 这样的算式可以写成 `---15`。一段时间后，Kruscal 又被那无穷多个 `+-` 号囧到了，于是他又将这个算式改进了一下。

比如 `+15*3` 又可以写成 `+(3)15`，同样，`-15*3` 等价于 `-(3)15`。但从上面可以看出，对于乘数较小的情况，如 `+++15` 这样的表述还是很方便的，于是在新的算式中还是保留了这种形式。

对于算式还要做一点特殊的说明：`+15*3` 转换成 Kruscal 型算式时可以写成 `+++15` 或 `+(3)15`，但不可以写成 `++(2)15` 这样的形式。

对于算式 `23+15*3-2` 可以表示为以下几种形式：`23+++15-2`、`23+(3)15-2`、`+23+++15-2`、`+23+(3)15-2、+(1)23+(3)15-(1)2`。不会出现如下几种形式：`(1)23+++15-2`、`+23++(2)15-(1)2`、`23+++15-2+(0)100`、`23-(-3)15-2`。

inputFormat: 一行，一个 Kruscal 型算式。

outputFormat: 一行，为运算结果。

hint: 对于 $100 \%$ 的数据，算式长度不超过 $2000$。


title: 色板游戏

background: 阿宝上学了，今天老师拿来了一块很长的涂色板。

description:
色板长度为 $L$，$L$ 是一个正整数，所以我们可以均匀地将它划分成 $L$ 块 $1$ 厘米长的小方格。并从左到右标记为 $1, 2, \dots L$。

现在色板上只有一个颜色，老师告诉阿宝在色板上只能做两件事：

1. `C A B C` 指在 $A$ 到 $B$ 号方格中涂上颜色 $C$。
2. `P A B` 指老师的提问：$A$ 到 $B$ 号方格中有几种颜色。

学校的颜料盒中一共有 $T$ 种颜料。为简便起见，我们把他们标记为 $1, 2, \dots T$. 开始时色板上原有的颜色就为 $1$ 号色。 面对如此复杂的问题，阿宝向你求助，你能帮助他吗？

inputFormat:
第一行有3个整数 $L (1 \le L \le 10^5), T (1 \le T \le 30) 和 O (1 \le O \le 10^5)$。 在这里 $O$ 表示事件数。

接下来 $O$ 行, 每行以 `C A B C` 或 `P A B` 得形式表示所要做的事情（这里 $A, B, C$ 为整数, 可能 $A> B$，这样的话需要你交换 $A$ 和 $B$）。

outputFormat: 对于老师的提问，做出相应的回答。每行一个整数。


title: 运动员最佳匹配问题

description:
羽毛球队有男女运动员各 $n$ 人。给定 $2$ 个 $n \times n$ 矩阵 $P$ 和 $Q$。$P_{i,j}$ 是男运动员 $i$ 和女运动员 $j$ 配对组成混合双打的男运动员竞赛优势；$Q_{i,j}$ 是女运动员 $i$ 和男运动员 $j$ 配合的女运动员竞赛优势。

但是，由于技术配合和心理状态等各种因素影响，$P_{i,j}$ 不一定等于 $Q_{j,i}$。男运动员 $i$ 和女运动员 $j$ 配对组成混合双打的男女双方竞赛优势为 $\bm{P_{i,j} \times Q_{j,i}}$。

现在，请你设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

inputFormat: 第一行有 $1$ 个正整数 $n$ $(1 \le n \le 20)$。接下来的 $2n$ 行，每行 $n$ 个数。前 $n$ 行是 $P$，后 $n$ 行是 $Q$。

outputFormat: 将计算出的男女双方竞赛优势的总和的最大值输出。


title: [USACO5.2] 蜗牛的旅行Snail Trails

description:
萨丽·斯内尔（Sally Snail，蜗牛）喜欢在 $N\times N$ 的棋盘上闲逛（$1<n \le 120$）。

她总是从棋盘的左上角出发。棋盘上有空的格子（用 $\verb!.!$ 来表示）和 $B$ 个路障（用 $\verb!#!$ 来表示）。

下面是这种表示法的示例棋盘：

$$
\boxed{\quad\begin{aligned}
\verb!   A  B  C  D  E  F  G  H! \\
\verb!1  S  .  .  .  .  .  #  .! \\
\verb!2  .  .  .  .  #  .  .  .! \\
\verb!3  .  .  .  .  .  .  .  .! \\
\verb!4  .  .  .  .  .  .  .  .! \\
\verb!5  .  .  .  .  .  #  .  .! \\
\verb!6  #  .  .  .  .  .  .  .! \\
\verb!7  .  .  .  .  .  .  .  .! \\
\verb!8  .  .  .  .  .  .  .  .! \\
\end{aligned}\quad}$$

萨丽总是垂直（向上或者向下）或水平（向左或者向右）地走。她可以从出发地（总是记作 $\tt A1$）向下或者向右走。一旦萨丽选定了一个方向，她就会一直走下去。如果她遇到棋盘边缘或者路障，她就停下来，并且转过 $90$ 度。她不可能离开棋盘，或者走进路障当中。并且，萨丽从不跨过她已经经过的格子。当她再也不能走的时候，她就停止散步。

这里是上面的棋盘上的一次散步路线图示：

$$
\boxed{\quad\begin{aligned}
\verb!   A  B  C  D  E  F  G  H! \\
\verb!1  S--------------+  #  .! \\
\verb!2  .  .  .  .  #  |  .  .! \\
\verb!3  .  .  .  .  .  |  .  .! \\
\verb!4  .  .  .  .  .  +-----+! \\
\verb!5  .  .  .  .  .  #  .  |! \\
\verb!6  #  .  .  .  .  .  .  |! \\
\verb!7  +-----------------+  |! \\
\verb!8  +--------------------+! \\
\end{aligned}\quad}$$

萨丽向右走，再向下，向右，向下，然后向左，再向上，最后向右走。这时她遇到了一个她已经走过的格子，她就停下来了。但是，如果她在 $\tt F5$ 格遇到路障后选择另外一条路——向我们看来是左边的方向转弯，情况就不一样了。

你的任务是计算并输出，如果萨丽聪明地选择她的路线的话，她所能够经过的最多格子数。

inputFormat: 输入的第一行包括 $N$ —棋盘的大小，和 $B$ —路障的数量（$1 \le B \le 200$）。接下来的 $B$ 行包含着路障的位置信息。下面的样例输入对应着上面的示例棋盘。下面的输出文件表示问题的解答。注意，当 $N>26$ 时，输入文件就不能表示 $\tt Z$ 列以后的路障了。（这句话不用专门理他。其实就是从 $A$ 的 ASCII 码开始向后顺延，不管是什么字母就行了）

outputFormat: 输出文件应该只由一行组成，即萨丽能够经过的最多格子数。


title: [USACO12JAN] Mountain Climbing S

description:
Farmer John has discovered that his cows produce higher quality milk when they are subject to strenuous exercise.  He therefore decides to send his N cows (1 <= N <= 25,000) to climb up and then back down a nearby mountain!

Cow i takes U(i) time to climb up the mountain and then D(i) time to climb down the mountain.  Being domesticated cows, each cow needs the help of a farmer for each leg of the climb, but due to the poor economy, there are only two farmers available, Farmer John and his cousin Farmer Don.  FJ plans to guide cows for the upward climb, and FD will then guide the cows for the downward climb.  Since every cow needs a guide, and there is only one farmer for each part of the voyage, at most one cow may be climbing upward at any point in time (assisted by FJ), and at most one cow may be climbing down at any point in time (assisted by FD).  A group of cows may temporarily accumulate at the top of the mountain if they climb up and then need to wait for FD's assistance before climbing down.  Cows may climb down in a different order than they climbed up.

Please determine the least possible amount of time for all N cows to make the entire journey.

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

第 $2$ 到第 $N+1$ 行，每行两个用空格隔开的整数 $U(i)$ 和 $D(i)$。

$(1 \le U(i),D(i) \le 50,000)$。

outputFormat: 一行一个整数，表示所有 $N$ 头牛完成旅程的最短时间。

translation:
农场主约翰发现他的奶牛剧烈运动后产奶的质量更高，所以他决定让 $N$ 头 $(1 \le N \le 25,000)$ 奶牛去附近爬山再返回来。

第 $i$ 头奶牛用时 $U(i)$ 爬上山，用时 $D(i)$ 下山。作为家畜，奶牛们每段路都要有农夫的帮助，可是由于经济疲软，农场里只有两个农夫 John 和 Don。John 计划引导奶牛爬山，Don 引导奶牛下山。虽然每个奶牛都需要向导，但每段旅途只有一名农夫。所有任何时刻只有一头奶牛爬山也只能有一头奶牛下山，奶牛爬上山后，可以暂时停留在山顶上等待 Don 的帮助。奶牛上山的顺序和下山的顺序不一定要相同。

请计算出所有 $N$ 头牛完成旅程的最短时间。


title: 还是 N 皇后

description: 正如题目所说，这题是著名的 $N$ 皇后问题。

inputFormat: 第一行有一个 $N$。接下来有 $N$ 行 $N$ 列描述一个棋盘，`*` 表示可放，`.` 表示不可放。

outputFormat: 输出方案总数。


title: [NOIP2016 提高组] 玩具谜题

background: NOIP2016 提高组 D1T1

description:
小南有一套可爱的玩具小人，它们各有不同的职业。

有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：

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

这时 singer 告诉小南一个谜题：“眼镜藏在我左数第 $3$ 个玩具小人的右数第 $1$ 个玩具小人的左数第 $2$ 个玩具小人那里。”

小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。

小南一边艰难地辨认着玩具小人，一边数着:

singer 朝内，左数第 $3$ 个是 archer。

archer 朝外，右数第 $1$ 个是 thinker。

thinker 朝外，左数第 $2$ 个是 writer。

所以眼镜藏在 writer 这里！

虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜題具体可以描述为：

有 $n$ 个玩具小人围成一圈，已知它们的职业和朝向。现在第 $1$ 个玩具小人告诉小南一个包含 $m$ 条指令的谜題，其中第 $z$ 条指令形如“向左数/右数第 $s$ 个玩具小人”。你需要输出依次数完这些指令后，到达的玩具小人的职业。

inputFormat:
输入的第一行包含两个正整数 $n,m$，表示玩具小人的个数和指令的条数。

接下来 $n$ 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中 $0$ 表示朝向圈内，$1$ 表示朝向圈外。保证不会出现其他的数。字符串长度不超过 $10$ 且仅由英文字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间用一个空格隔开。

接下来 $m$ 行，其中第 $i$ 行包含两个整数 $a_i,s_i$，表示第 $i$ 条指令。若 $a_i=0$，表示向左数 $s_i$ 个人；若 $a_i=1$，表示向右数 $s_i$ 个人。 保证 $a_i$ 不会出现其他的数，$1 \le s_i < n$。

outputFormat: 输出一个字符串，表示从第一个读入的小人开始，依次数完 $m$ 条指令后到达的小人的职业。

samples:
7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2

hint:
**样例 1 说明**

这组数据就是【题目描述】中提到的例子。

**子任务**

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

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

其中一些简写的列意义如下:

- 全朝内：若为 $\surd$，表示该测试点保证所有的玩具小人都朝向圈内；

- 全左数：若为 $\surd$，表示该测试点保证所有的指令都向左数，即对任意的 $1\leq z\leq m, a_i=0$；

- $s=1$：若为 $\surd$，表示该测试点保证所有的指令都只数 $1$ 个，即对任意的 $1\leq z\leq m,s_i=1$；

职业长度为 $1$：若为 $\surd$，表示该测试点保证所有玩具小人的职业一定是一个长度为 $1$ 的字符串。


title: 膜拜

description:
神牛有很多…当然…每个同学都有自己衷心膜拜的神牛。

某学校有两位神牛，神牛甲和神牛乙。新入学的 $n$ 位同学们早已耳闻他们的神话。

所以，已经衷心地膜拜其中一位了。现在，老师要给他们分机房。但是，要么保证整个机房都是同一位神牛的膜拜者，或者两个神牛的膜拜者人数差不超过 $m$。另外，现在 $n$ 位同学排成一排，老师只会把连续一段的同学分进一个机房。老师想知道，至少需要多少个机房。

inputFormat:
输入文件第一行包含两个整数 $n$ 和 $m$。

第 $2$ 到第 $(n + 1)$ 行，每行一个非 $1$ 即 $2$ 的整数，第 $(i + 1)$ 行的整数表示第 $i$ 个同学崇拜的对象，$1$ 表示甲，$2$ 表示乙。

outputFormat: 输出一个整数，表示最小需要机房的数量。

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

- 对于 $30\%$ 的数据，保证 $1 \le n,m \le 50$。
- 对于 $100\%$ 的数据，保证 $1 \le n,m \le 2500$。


title: 牛宫

description:
AP 神牛准备给自己盖一座很华丽的矩形宫殿。于是，他看中了一块 $N \times M$ 的矩形空地。

空地中每个格子都有自己的海拔高度 $a_{i,j}$。AP 想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是 0，平均数都会算吧？）。而且，AP 希望他的宫殿尽量大，能够容纳更多的人来膜拜他。请问 AP 的宫殿最后会有多大？

inputFormat: 第一行为 $N$ 和 $M$。之后 $N$ 行，每行 $M$ 个数，描述的空地的海拔 $a_{i,j}$。

outputFormat: 输出宫殿最大面积。


title: 加等式

description: 对于一个整数集合，我们定义“加等式”如下：集合中的某一个元素可以表示成集合内其他元素之和。如集合 ${1,2,3}$ 中就有一个加等式：$3=1+2$。而且 $3=1+2$ 和 $3=2+1$ 是相同的加等式，也是这个集合唯一的加等式。给定一个整数集合，编程找出其加等式的个数。

inputFormat:
第一行为 $t$，表示测试数据组数。

接下来 $t$ 行，每行表示一组测试数据。其中第一个数 $m$，表示集合元素的个数，接下来 $m$ 个不同的整数 $x_i$，表示集合元素。

outputFormat: 对于每个输入数据，输出一个整数，表示其中加等式的个数。


title: 统计天数

description:
炎热的夏日，KC 非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天气。

经历千辛万苦，他收集了连续 $N(1 \leq N \leq 10^6)$ 天的最高气温数据。

现在，他想知道最高气温一直上升的最长连续天数。

inputFormat:
第 1 行：一个整数 $N$ 。$1 \leq N \leq 10^6$

第 2 行：$N$个空格隔开的整数，表示连续 $N$ 天的最高气温。$0 \leq$ 最高气温 $\leq 10^9$ 。

outputFormat: 1 行：一个整数，表示最高气温一直上升的最长连续天数。


title: 赛跑

background: 赛跑

description:
SH的跑步成绩一直不太理想。为了帮助SH提高成绩，KC决定和他进行一次赛跑。比赛的起点设在农场主的屋前，他们同时出发，沿着同一方向，直到跑到终点----农场远处的一棵树下。

他们的跑步速度在一些时间段内是恒定的。比如：SH在前３个时间段速度是５，接着６个时间段内速度是１０。他们的比赛总时间相同。他们希望能统计出在整个比赛过程中领先顺序的变化次数。举个例子，某个时刻SH领先，下个时刻KC领先，这就是一次领先顺序的变化；如果某个时刻SH领先，接下来一段时间KC赶上来并和SH齐头并进，但最终还是超过了SH，这也是一次领先顺序的变化。

inputFormat:
第１行：N和M（1 <= N, M <= 1000）。

接下来的N行：每行两个整数，描述SH跑步的一段，分别表示该段SH跑步的速度和持续这种速度的时间。所有的数据范围 [1..1000]。

再接下来的M行：每行两个整数，描述KC跑步的一段，分别表示该段KC跑步的速度和持续这种速度的时间。所有的数据范围 [1..1000]。

outputFormat: 一行：整个比赛过程中领先顺序的变化次数。

hint:
输入：SH在前 $2$ 个单位时间内速度是 $1$，接着 $1$ 个单位时间内速度是 $4$，接着 $1$ 个单位时间内速度是 $1$，最后 $10$ 个单位时间内速度是 $2$。KC在前 $3$ 个个单位时间内速度是 $2$，接着 $2$ 个单位时间内速度是 $2$，最后 $9$ 个单位时间内速度是 $3$。

输出：比赛开始后KC领先，直到第 $5$ 个单位时间SH超过KC（第一次领先顺序变化），接着第 $7$ 个单位时间时，KC又反超SH，变成领先（第二次领先顺序变化）。


title: Generic Cow Protests

description:
约翰家的 $n$ 头奶牛聚集在一起，排成一列，正在进行一项抗议活动。第 $i$ 头奶牛的理智度为 $a_i$。
约翰希望奶牛在抗议时保持理性，为此，他打算将所有的奶牛隔离成若干个小组，每个小组内的奶牛的理智度总和都要不小于零。
由于奶牛是按直线排列的，所以一个小组内的奶牛位置必须是连续的。请帮助约翰计算一下，最多分成几组。

inputFormat:
第一行一个正整数 $n$，表示牛的数目。
接下来 $n$ 行，每行一个整数，表示每个牛的理智度。

outputFormat: 若存在合法分组方案，输出一行一个整数表示答案；否则输出 `Impossible`。


title: KC 喝咖啡

description:
话说 KC 和 SH 在福州的时候常常跑去 85°C 喝咖啡或者其他的一些什么东西。

这天，KC 想要喝一杯咖啡，服务员告诉他，现在有 $n$ 种调料，这杯咖啡只可以加入其中的 $m$ 种（当然 KC 一定会加入 $m$ 种，不会加入少于 $m$ 种的调料），根据加入的调料不同，制成这杯咖啡要用的时间也不同，得到的咖啡的美味度也不同。

KC 在得知所有的 $n$ 种调料后，作为曾经的化竞之神的他，马上就知道了所有调料消耗的时间 $c _ i$ 以及调料的美味度 $v _ i$。由于 KC 急着回去刷题，所以他想尽快喝到这杯咖啡，但他又想喝到美味的咖啡，所以他想出了一个办法，他要喝到 $\dfrac{\sum v _ i}{\sum c _ i}$ 最大的咖啡，也就是单位时间的美味度最大的咖啡。

现在，KC 把调料信息告诉了 SH，要 SH 帮他算出喝到的咖啡的 $\dfrac{\sum v _ i}{\sum c _ i}$，但 SH 不想帮 KC 算这东西，于是 KC 就只能拜托你来算了。

注释：$\sum$ 表示求和，所以 $\dfrac{\sum v _ i}{\sum c _ i}$ 表示美味度的总和除以消耗时间的总和。

inputFormat:
输入数据共三行。

第一行为一个整数 $n, m$，表示调料种数和能加入的调料数。

接下来两行，每行为 $n$ 个数，第一行第 $i$ 个整数表示调料 $i$ 的美味度 $v _ i$，第二行第 $i$ 个整数表示调料 $i$ 消耗的时间 $c _ i$。

outputFormat: 一个实数 $T$，表示 KC 喝的咖啡的最大 $\dfrac{\sum v _ i}{\sum c _ i}$，保留三位小数。

hint:
**样例 1 解释**：

KC 选 $2$ 号和 $3$ 号调料，$\dfrac{\sum v _ i}{\sum c _ i} = \dfrac{2 + 3}{2 + 1} = 1.667$。

可以验证不存在更优的选择。

**数据范围**：

对 $20 \%$ 的数据：$1 \leq n \leq 5$。

对 $50 \%$ 的数据：$1 \leq n \leq 10$。

对 $80 \%$ 的数据：$1 \leq n \leq 50$。

对 $100 \%$ 的数据：$1 \leq n \leq 200, 1 \leq m \leq n, 1 \leq c[i], v[i] \leq 1 \times 10 ^ 4$。

数据保证答案不超过 $1000$。


title: 眼红的Medusa

description: 虽然 Miss Medusa 到了北京，领了科技创新奖，但是她还是觉得不满意。原因是：他发现很多人都和她一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。

inputFormat:
第一行两个整数 $n, m$，表示有 $n$ 个人获得科技创新奖，$m$ 个人获得特殊贡献奖。

第二行 $n$ 个正整数，表示获得科技创新奖的人的编号。

第三行 $m$ 个正整数，表示获得特殊贡献奖的人的编号。

outputFormat: 输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。

hint:
对于 $60\%$ 的数据，$0 \leq n, m \leq 1000$，获得奖项的人的编号 $\lt 2 \times 10^9$；

对于 $100\%$ 的数据，$0 \leq n, m \leq 10^5$，获得奖项的人的编号 $\lt 2 \times 10^9$。

输入数据保证第二行任意两个数不同，第三行任意两个数不同。


title: 计算分数

description: Csh 被老妈关在家里做分数计算题，但显然他不愿意做这么多复杂的计算。况且在家门口还有 Xxq 在等着他去一起看电影。为了尽快地能去陪 Xxq 看电影，他把剩下的计算题交给了你，你能帮他解决问题吗？

inputFormat:
输入一行，为一个分数计算式。

计算式中只包含数字、`+`、`-`、`/`。其中 `/` 为分数线，分数线左边为分子，右边为分母。输入数据保证不会出现繁分数。如果输入计算式的第一项为正，不会有前缀 `+` 号；若为负，会有前缀 `-` 号。

所有整数均以分数形式出现。

outputFormat:
输出一行，为最后的计算结果（用为整数则用整数表示，否则用最简分数表示）。

保证答案内出现的所有数（如果答案是分数即为分子和分母）均在 $32$ 位带符号整数的表示范围之内。

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

对于所有测试点，输入计算式长度在 $100$ 以内，分子、分母在 $1000$ 以内。同时保证，直接从前往后直接计算分数的和或者差，然后立刻化简，这么做的中间结果不会超过 int 的范围。

注意输入的分数不一定是最简分数。

------------
2024/2/13 添加 2 组 hack 数据。


title: 栈的操作

background: 管理备注：本题因证明难度极高，做题难度低，故评为灰题

description:
现在有四个栈，其中前三个为空，第四个栈从栈顶到栈底分别为 $1,2,3,\cdots ,n$。每一个栈只支持一种操作：弹出并压入。它指的是把其中一个栈 A 的栈顶元素 $x$ 弹出，并马上压入任意一个栈 B 中。但是这样的操作必须符合一定的规则才能进行。

- 规则 $1$：A 栈不能为空。
- 规则 $2$：B 栈为空或 $x$ 比 B 栈栈顶要小。

对于给定的 $n$，请你求出把第四个栈的 $n$ 个元素全部移到第一个栈的最少操作次数。

由于最少操作次数可能很多，请你把答案对 $10^6+7$ 取模。

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

outputFormat: 一行，一个正整数，为把最少操作次数 $\bmod (10^6+7)$ 的值。


title: 超级数

description:
设x的约数个数为 $f(x)$，若 $\forall i\in [1,n)\cap \mathbb{Z^+},f(n)>f(i)$，就把 $n$ 称作 `supernumber`。

给出 $m$ 个数 $a_1,a_2,\ldots,a_m$，请分别输出不大于 $a_1$，不大于 $a_2$，...，不大于 $a_m$ 的最大 `supernumber`。

inputFormat:
第一行有一个整数，代表 $m$。

第 $2$  到第 $(m+1)$ 行，每行一个整数，其中第  $(i+1)$ 行的整数为 $a_i$。

outputFormat: 共 $m$ 行，每行一个整数，其中第 $i$ 行为不大于 $a_i$ 的最大`supernumber`。


title: 正误问题

description: 小 bobo 迷上了逻辑值运算。但小 bobo 算的头都晕了，也没算出个所以然。他只好找到你，让你帮他解决这个问题。

inputFormat: 一个字符串表达逻辑式子，内只包含 `true`，`false`，`or`，`and`，`not` 和空格，(不包含括号和 `xor`)，优先级同 pascal。(从高到低依次为 `not`，`and`，`or`)，同级左边先算，如果逻辑式有误则输出 `error`。

outputFormat: 输出一行表示运算结果：`true` 或者 `false`，如果无法得到结果的输出 `error`。

samples:
true or false and false
true

hint:
对于全部数据，保证输入数据串长小于 $255$。

本题结果为 `true`，`false`，`error` 各占 $\dfrac{1}{3}$，允许“骗分”，但不值得，因为是“水题”。

---

- $\text{upd 2022.7.21}$：新增加 $5$ 组 [Hack 数据](https://www.luogu.com.cn/discuss/459823)。


title: 最小花费

description: 在 $n$ 个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 $A$ 最少需要多少钱使得转账后 $B$ 收到 $100$ 元。

inputFormat:
第一行输入两个正整数 $n,m$，分别表示总人数和可以互相转账的人的对数。

以下 $m$ 行每行输入三个正整数 $x,y,z$，表示标号为 $x$ 的人和标号为 $y$ 的人之间互相转账需要扣除 $z\%$ 的手续费 $(z<100)$。

最后一行输入两个正整数 $A,B$。数据保证 $A$ 与 $B$ 之间可以直接或间接地转账。

outputFormat: 输出 $A$ 使得 $B$ 到账 $100$ 元最少需要的总费用。精确到小数点后 $8$ 位。


title: 切绳子

description: 有 $N$ 条绳子，它们的长度分别为 $L_i$。如果从它们中切割出 $K$ 条长度相同的绳子，这 $K$ 条绳子每条最长能有多长？答案保留到小数点后 $2$ 位(直接舍掉 $2$ 位后的小数)。

inputFormat: 第一行两个整数 $N$ 和 $K$，接下来 $N$ 行，描述了每条绳子的长度 $L_i$ 。

outputFormat: 切割后每条绳子的最大长度。答案与标准答案误差不超过 $0.01$ 或者相对误差不超过 $1\%$ 即可通过。


title: 奶牛浴场

description:
由于 John 建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John 决定在牛场中建造一个大型浴场。但是 John 的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John 希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于 Clevow 了。你还能帮助 Clevow 吗？

John 的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。

Clevow 当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。

inputFormat:
输入文件的第一行包含两个整数 $L$ 和 $W$，分别表示牛场的长和宽。

文件的第二行包含一个整数 $n$，表示产奶点的数量。

以下 $n$ 行每行包含两个整数 $x$ 和 $y$，表示一个产奶点的坐标。

所有产奶点都位于牛场内，即：$0 \le x \le L$，$0 \le y \le W$。

outputFormat: 输出文件仅一行，包含一个整数 $S$，表示浴场的最大面积。

hint:
对于所有数据，$0 \le n \le 5 \times 10^3$，$1 \le L,W \le 3 \times 10^4$。

Winter Camp 2002

感谢 @凯瑟琳98 提供了 4 组 hack 数据。


title: 哥德巴赫猜想（升级版）

background:
1742 年 6 月 7 日，哥德巴赫写信给当时的大数学家欧拉，正式提出了以下的猜想：任何一个大于 $9$ 的奇数都可以表示成 $3$ 个质数之和。质数是指除了 $1$ 和本身之外没有其他约数的数，如 $2$ 和 $11$ 都是质数，而 $6$ 不是质数，因为 $6$ 除了约数 $1$ 和 $6$ 之外还有约数 $2$ 和 $3$。**需要特别说明的是 $1$ 不是质数。**

这就是哥德巴赫猜想。欧拉在回信中说，他相信这个猜想是正确的，但他不能证明。

从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。

description:
现在请你编一个程序验证哥德巴赫猜想。

先给出一个奇数 $n$，要求输出 $3$ 个质数，这 $3$ 个质数之和等于输入的奇数。

inputFormat: 仅有一行，包含一个正奇数 $n$，其中 $9 < n < 20000$。

outputFormat: 仅有一行，输出 $3$ 个质数，这 $3$ 个质数之和等于输入的奇数。相邻两个质数之间用一个空格隔开，最后一个质数后面没有空格。如果表示方法不唯一，请输出第一个质数最小的方案，如果第一个质数最小的方案不唯一，请输出第一个质数最小的同时，第二个质数最小的方案。


title: yyy loves Easter_Egg I

background: Soha 的出题效率着实让人大吃一惊。OI，数学，化学的题目都出好了，物理的题还没有一道。于是，Huntfire，absi2011，redbag 对 soha 进行轮番炸，准备炸到 soha 出来，不料，人群中冲出了个 kkksc03……

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

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

yyy loves OI（Huntfire），yyy loves Maths（redbag），yyy loves Chemistry（absi2011）对 yyy loves Physics（soha）进行轮番炸，轰炸按照顺序进行，顺序为 Huntfire，redbag，absi2011。

现在这一题中，我们不考虑太复杂的队形形式。我们认为只要这一句内含有且恰好含有一次@，@的人和上一句话一样就算为队形。

比如以下也视为队形：

- `yyy loves OI : @yyy loves Microelectronic`
- `yyy loves Maths : @yyy loves Microelectronic 我佩服soha的出题效率`
- `yyy loves OI : @yyy loves Microelectronic +1`
- `yyy loves Chemistry : +1 @yyy loves Microelectronic`

若 @ 的人与第一个人不同，就算队形被打破。若这个人在队形被打破之前出来发言了，或者就是他打破队形了，就算（油）炸成功了。

若（油）炸成功，输出 `Successful @某某某 attempt`，若队形被破坏先输出 `Unsuccessful @某某某 attempt`，再输出队形第一次被破坏的行数与第一次破坏队形的人的 $\text{id}$。

如果队形一直没被打破，就先输出 `Unsuccessful @某某某 attempt`，再输出队形的长度，最后输出 `Good Queue Shape`。

~~p.s.yyy loves Microelectronic 是 kkksc03~~

inputFormat: $N$ 行，为轰炸开始后的一段消息记录，每行一条消息。消息格式：「消息发送者+`:`+消息内容」，每行消息长度不超过 $1000$。（中文用拼音代替）

outputFormat:
若（油）炸成功，输出 `Successful @某某某 attempt`，若队形被破坏第一行输出 `Unsuccessful @某某某 attempt`，接下来一行输出队形第一次被破坏的行数，第三行输出第一次破坏队形的人的 $\text{id}$。
如果队形一直没被打破，就先输出 `Unsuccessful @某某某 attempt`，再输出队形的长度，最后输出 `Good Queue Shape`。

samples:
yyy loves OI : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Maths : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Chemistry : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Microelectronic : ni men wu liao me
yyy loves OI : @yyy loves Physics wo pei fu ni de chu ti xiao lv

samples:
Unsuccessful @yyy loves Physics attempt
4
yyy loves Microelectronic

samples:
yyy loves OI : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Maths : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Chemistry : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves OI : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Maths : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Chemistry : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves OI : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Maths : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Chemistry : @yyy loves Physics wo pei fu ni de chu ti xiao lv
yyy loves Physics : ni men gou le

hint:
**@yyy loves Physics 我佩服你的出题效率**

此题仅吐槽 soha，纪念出题者的队形，此队形长达 $91$ 行。

对于 $100\%$ 的数据,每行消息长度 $\le$ $10^3$。

- 保证行数不超过 $5\times 10^4$；
- 保证输入文件大小不超过 $4\text{MB}$；
- 保证第一个说话的一定在 @ 某人；
- 保证大家的名字都是 $\text{yyy loves ***}$ 的格式；
- 保证每个人说的话中没有 `:`；
- 保证第一个说话的一定艾特了一个人且只 @ 了一个人；
- 保证第一个说话的一定不会艾特自己；
- 保证文件结束一定有一行空行，方便你判定文件结束；
- 并不保证后面说话的艾特了几个人 然而艾特人数不为一个人视为破坏队形；
- 并不保证后面说话是否会反复艾特同一个人；
- 并不保证被炸的人一定破坏队形；
- 并不保证这一题是或不是压轴题；
- 并不保证这一套比赛存在压轴题；
- 并不保证下一套比赛和这一套比赛一样水；
- 并不保证群里除了这 $4$ 个人和 kkksc03 以外没有别人了；
- 并不保证你没 AC 这题的情况下吐槽 soha 不会出事儿；
- AC 了可以吐槽 soha 一句，soha 不会介意。


title: A+B Problem（升级版）

background: 小明这在写作业，其中有一道A+B Problem ，他想啊想啊想，就是想不出来，于是就找到了会编程的你......

description: 这里的 $A+B$ 是很奇特的。它是按质数的顺序来进位的。例如：$1,0+2,1$ ＝ $1,0,1$（用 $\verb!,!$ 来分隔每一位）。个位是 $2$ 进制，十位是 $3$ 进制，百位是 $5$ 进制，千位是 $7$ 进制，万位是 $11$ 进制……两个加数的最高位是万位（万位可能有两位）。

inputFormat: 输入一个形如 $1,0+2,1$ 字符串 $s$。

outputFormat: 输出相加后的结果。


title: 倒水

description:
一天，CC 买了 $N$ 个容量可以认为是无限大的瓶子，开始时每个瓶子里有 $1$ 升水。接着 CC 发现瓶子实在太多了，于是他决定保留不超过 $K$ 个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。（不能丢弃有水的瓶子）

显然在某些情况下 CC 无法达到目标，比如 $N = 3$、$K = 1$。此时 CC 会重新买一些新的瓶子（新瓶子容量无限，开始时有 $1$ 升水），以达到目标。

现在 CC 想知道，最少需要买多少新瓶子才能达到目标呢？

inputFormat: 一行两个正整数 $N, K$（$1 \le N \le 2 \times 10^9$，$K \le 1000$）。

outputFormat: 一个非负整数，表示最少需要买多少新瓶子。


title: 魔法照片

description: 一共有 $n$ 个人（以 $1\sim n$ 编号）向佳佳要照片，而佳佳只能把照片给其中的 $k$ 个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值 $W_i$。然后将初始权值从大到小进行排序，每人就有了一个序号 $D_i$（取值同样是 $1\sim n$）。按照这个序号对 $10$ 取模的值将这些人分为 $10$ 类。也就是说定义每个人的类别序号 $C_i$ 的值为 $(D_i-1)\bmod 10 +1$，显然类别序号的取值为 $1 \sim 10$。第 $i$ 类的人将会额外得到 $E_i$ 的权值。你需要做的就是求出加上额外权值以后，最终的权值最大的 $k$ 个人，并输出他们的编号。**在排序中，如果两人的 $E_i$ 相同，编号小的优先。**

inputFormat:
第一行输入用空格隔开的两个整数，分别是 $n$ 和 $k$。

第二行给出了 $10$ 个正整数，分别是 $E_1\sim E_{10}$。

第三行给出了 $n$ 个正整数，第 $i$ 个数表示编号为  $i$ 的人的权值 $W_i$。

outputFormat: 只需输出一行用空格隔开的 $k$ 个整数，分别表示最终的 $W_i$ 从高到低的人的编号。

hint: 对于 $100\%$ 的数据，$1\leq n\leq 20000$，$1\leq k\leq n$，保证所有数据均在 `int` 范围之内。