title: [SDOI2010] 猪国杀

description:
### 游戏背景

《猪国杀》是一种多猪牌类回合制游戏，一共有 $3$ 种角色：主猪，忠猪，反猪。每局游戏主猪有且只有 $1$ 只，忠猪和反猪可以有多只，每只猪扮演 $1 $ 种角色。

### 游戏目的

主猪 / $\texttt{MP}$：自己存活的情况下消灭所有的反猪。
忠猪 / $\texttt{ZP}$：不惜一切保护主猪，胜利条件与主猪相同。
反猪 / $\texttt{FP}$：杀死主猪。

### 游戏过程

游戏开始时，每个玩家手里都会有 $4$ 张牌，且体力上限和初始体力都是 $4$ 。

开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从 $ 1 , 2, 3 \ldots n , 1 \ldots $ 的顺序）依次行动。

每个玩家自己的回合可以分为 2 个阶段：

* **摸牌阶段**：从牌堆顶部摸 $2$ 张牌，依次放到手牌的最右边；
* **出牌阶段**：你可以使用任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。当然，要满足如下规则：
  1. 如果没有猪哥连弩，每个出牌阶段只能使用 $1$ 次「杀」来攻击；
  2. 任何牌被使用后被弃置（武器是装备上）；被弃置的牌以后都不能再用，即与游戏无关。

### 各种牌介绍

每张手牌用 $1$ 个字母表示，字母代表牌的种类。

#### 基本牌

- 『桃 / $\texttt{P}$』在自己的回合内，如果自己的体力值不等于体力上限，那么使用 $1$ 个桃可以为自己补充 $1$ 点体力，否则不能使用桃；桃只能对自己使用；在自己的回合外，如果自己的血变为 $0$ 或者更低，那么也可以使用。

- 『杀 / $\texttt{K}$』在自己的回合内，对攻击范围内除自己以外的 $1$ 名角色使用。如果没有被『闪』抵消，则造成 $1$ 点伤害。无论有无武器，杀的攻击范围都是 $1$。

- 『闪 / $\texttt{D}$』当你受到杀的攻击时，可以弃置 $1$ 张闪来抵消杀的效果。

#### 锦囊牌

- 『决斗 / $\texttt{F}$』出牌阶段，对除自己以外任意 $1$ 名角色使用，由目标角色先开始，自己和目标角色轮流弃置 $1$ 张杀，首先没有杀可弃的一方受到 $1$ 点伤害，另一方视为此伤害的来源。

- 『南猪入侵 / $\texttt{N}$』出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置 $1$ 张杀，否则受到 $1$ 点伤害。

- 『万箭齐发 / $\texttt{W}$』和南猪入侵类似，不过要弃置的不是杀而是闪。

- 『无懈可击 / $\texttt{J}$』在目标锦囊生效前抵消其效果。每次有 $1$ 张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会；效果：用于决斗时，决斗无效并弃置；用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对 $1$ 个角色产生效果）；用于无懈可击时，成为目标的无懈可击被无效。

#### 装备牌

- 『猪哥连弩 / $\texttt{Z}$』武器，攻击范围 $1$ ，出牌阶段你可以使用任意张杀; 同一时刻最多只能装 $1$ 把武器；如果先前已经有了 $1$ 把武器，那么之后再装武器的话，会弃置以前的武器来装现在的武器。

### 特殊事件及概念解释

* **伤害来源**：杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪，决斗的伤害来源如上；

* **距离**：两只猪的距离定义为沿着逆时针方向间隔的猪数 $+1$ 。即初始时 $1$ 和 $2$ 的距离为 $1$ ，但是 $2$ 和 $1$ 的距离就是 $n-1$ 。注意一个角色的死亡会导致一些猪距离的改变；

* **玩家死亡**：如果该玩家的体力降到 $0$ 或者更低，并且自己手中没有足够的桃使得自己的体力值回到 $1$ ，那么就死亡了，死亡后所有的牌（装备区，手牌区）被弃置；

* **奖励与惩罚**：反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸 $3$ 张牌。忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置。

注意：一旦达成胜利条件，游戏立刻结束，因此即使会摸 $3$ 张牌或者还有牌可以用也不用执行了。

现在，我们已经知道每只猪的角色、手牌，还有牌堆初始情况，并且假设每个角色会按照如下的行为准则进行游戏，你需要做的就是告诉小猪 iPig 最后的结果。

### 几种行为

* **献殷勤**：使用无懈可击挡下南猪入侵、万箭齐发、决斗；使用无懈可击抵消表敌意；
* **表敌意**：对某个角色使用杀、决斗；使用无懈可击抵消献殷勤；
* **跳忠**：即通过行动表示自己是忠猪。跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意；
* **跳反**：即通过行动表示自己是反猪。跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤。

**注意：忠猪不会跳反，反猪也不会跳忠；不管是忠猪还是反猪，能够跳必然跳**。

### 行动准则

#### 共性

* 每个角色如果手里有桃且生命值未满，那么必然吃掉；
* 有南猪入侵、万箭齐发、必然使用；有装备必然装上；
* 受到杀时，有闪必然弃置；
* 响应南猪入侵或者万箭齐发时候，有杀 / 闪必然弃置；
* 不会对未表明身份的猪献殷勤（**包括自己**）。

#### 特性

 - 主猪：
   + 主猪会认为「没有跳身份，且用南猪入侵 / 万箭齐发对自己造成伤害的猪」是**类**反猪（没伤害到不算，注意类反猪并没有表明身份），如果之后跳了，那么主猪会重新认识这只猪；
   + 对于每种表敌意的方式，对逆时针方向能够执行到的第一只类反猪或者已跳反猪表；如果没有，那么就不表敌意；
   + 决斗时会不遗余力弃置杀；
   + 如果能对已经跳忠的猪或自己献殷勤，那么一定献；如果能够对已经跳反的猪表敌意，那么一定表。
 - 忠猪：
   + 对于每种表敌意的方式，对「逆时针方向能够执行到的第一只已经跳反的猪」表，如果没有，那么就不表敌意；
   + 决斗时，如果对方是主猪，那么不会弃置杀，否则，会不遗余力弃置杀；
   + 如果有机会对主猪或者已经跳忠的猪献殷勤，那么一定献。
 - 反猪：
   + 对于每种表敌意的方式，如果有机会则对主猪表，否则，对「逆时针方向能够执行到的第一只已经跳忠的猪」表，如果没有，那么就不表敌意；
   + 决斗时会不遗余力弃置杀；
   + 如果有机会对已经跳反的猪献殷勤，那么一定献。

限于 iPig 只会用 P++ 语言写 A + B，他请你用 Pigcal (Pascal)、P (C) 或 P++ (C++) 语言来帮他预测最后的结果。

inputFormat:
输入文件第一行包含两个正整数 $ n $ $ (2 \leqslant n \leqslant 10) $ 和 $m$ $ (m \leqslant 2000) $，分别代表玩家数和牌堆中牌的数量。数据保证牌的数量够用。

接下来 $n$ 行，每行 $5$ 个字符串，依次表示对第 $i$ 只猪的角色和初始 $4 $ 张手牌描述。编号为 $1$ 的肯定是主猪。

再接下来一行，一共 $m$ 个字符串，按照从牌堆顶部到牌堆底部的顺序描述每张牌。

**注意：所有的相邻的两个字符串都严格用 $1$ 个空格隔开，行尾没有多余空格**。

outputFormat:
输出数据第一行包含一个字符串代表游戏结果。如果是主猪胜利，那么输出 $\texttt{MP}$ ，否则输出 $\texttt{FP}$ 。数据保证游戏总会结束。

接下来 $n$ 行，第 $i$ 行是对第 $i$ 只猪的手牌描述（注意只需要输出手牌），按照手牌从左往右的顺序输出，相邻两张牌用 $1$ 个空格隔开，行末尾没有多余空格。如果这只猪已阵亡，那么只要输出 $\texttt{DEAD}$ 即可。

**注意：如果要输出手牌而没有手牌的话，那么只需输出 $1$ 个空行**。

**由于数据问题，若牌堆已空，按照每次抽牌抽到的都是最后一张。**

samples:
3 10
MP D D F F
ZP N N N D
FP J J J J
F F D D J J F F K D

hint:
### 样例解释

第一回合：
* 主猪没有目标可以表敌意；
* 接下来忠猪使用了 $3$ 张南猪入侵，主猪掉了 $3$ 点体力，并认为该角色为类反猪，$3$ 号角色尽管手里有无懈可击，但是因为自己未表明身份，所以同样不能对自己用，乖乖掉 $3$ 点体力；

下一回合：
* 反猪无牌可出；
* 接下来主猪对着类反猪爆发，使用 $4$ 张决斗，忠猪死亡，结果主猪弃掉所有牌；
* 下来反猪摸到 $1$ 张杀直接杀死主猪获胜。

### 子任务

一共 $20$ 组测试数据，每个点 $5$ 分。

$10\%$ 的数据没有锦囊牌，另外 $20\%$ 的数据没有无懈可击。


title: 【模板】k 短路 / [SDOI2010] 魔法猪学院

type: P

background: 注：对于 $k$ 短路问题，A\* 算法的最坏时间复杂度是 $O(nk \log n)$ 的。虽然 A\* 算法可以通过本题原版数据，但可以构造数据，使得 A\* 算法在原题的数据范围内无法通过。事实上，存在使用可持久化可并堆的算法可以做到在 $O((n+m) \log n + k \log k)$ 的时间复杂度解决 $k$ 短路问题。详情见 [OI-Wiki](https://oi-wiki.org/graph/kth-path/)。

description:
iPig 在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig 对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒$\ldots$。

iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素$\ldots$等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 $1$ 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 $N$ 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾$\ldots$现在的你呀！

注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

inputFormat:
第一行三个数 $N, M, E$，表示 iPig 知道的元素个数（元素从 $1$ 到 $N$ 编号），iPig 已经学会的魔法个数和 iPig 的总能量。

后跟 $M$ 行每行三个数 $s_i, t_i, e_i$ 表示 iPig 知道一种魔法，消耗 $e_i$ 的能量将元素 $s_i$ 变换到元素 $t_i$。

outputFormat: 一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。

hint:
有意义的转换方式共 $4$ 种：

$1\to 4$，消耗能量 $1.5$。

$1\to 2\to 1\to 4$，消耗能量 $4.5$。

$1\to3\to4$，消耗能量 $4.5$。

$1\to2\to3\to4$，消耗能量 $4.5$。

显然最多只能完成其中的 $3$ 种转换方式（选第一种方式，后三种方式任选两个），即最多可以转换 $3$ 份样本。

如果将 $E=14.9$ 改为 $E=15$，则可以完成以上全部方式，答案变为 $4$。

### 数据规模

占总分不小于 $10\%$ 的数据满足 $N \leq 6,M \leq 15$。

占总分不小于 $20\%$ 的数据满足 $N \leq 100,M \leq 300,E\leq100$ 且 $E$ 和所有的 $e_i$ 均为整数（可以直接作为整型数字读入）。

所有数据满足 $2 \leq N \leq 5000$，$1 \leq M \leq 200000$，$1 \leq E \leq 10 ^ 7$，$1 \leq ei\leq E$，$E$ 和所有的 $e_i$ 为实数。

### 数据更新日志

- 2010/xx/xx：原版数据；
- 2018/03/02：@[kczno1](/user/9168) 添加了 [一组数据](/discuss/35616)；
- 2018/04/20：@[X_o_r](/user/25188) 添加了 [一组数据](/discuss/40205)；
- 2021/01/08：@[LeavingZ](/user/215697) 添加了 [两组数据](/discuss/291028)。


title: [SDOI2011] 打地鼠

description:
2020.4.29 数据更新。

打地鼠是这样的一个游戏：地面上有一些地鼠洞，地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时，用锤子砸其头部，砸到的地鼠越多分数也就越高。

游戏中的锤子每次只能打一只地鼠，如果多只地鼠同时探出头，玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了，所以你改装了锤子，增加了锤子与地面的接触面积，使其每次可以击打一片区域。如果我们把地面看做 $m\times n$ 的方阵，其每个元素都代表一个地鼠洞，那么锤子可以覆盖 $r\times c$ 区域内的所有地鼠洞。但是改装后的锤子有一个缺点：每次挥舞锤子时，对于这的区域中的所有地洞，锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中，每个地洞必须至少有 $1$ 只地鼠，且如果某个地洞中地鼠的个数大于 $1$，那么这个地洞只会有 $1$ 只地鼠被打掉，因此每次挥舞锤子时，恰好有$r\times c$ 只地鼠被打掉。由于锤子的内部结构过于精密，因此在游戏过程中你不能旋转锤子（即不能互换 $r$ 和 $c$）。

你可以任意更改锤子的规格(即你可以任意规定 $r$ 和 $c$ 的大小)，但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后，再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠，至少需要挥舞锤子的次数。

Hint：由于你可以把锤子的大小设置为 $1\times 1$，因此本题总是有解的。

inputFormat:
第一行包含两个正整数 $m$ 和 $n$；

下面 $m$ 行每行 $n$ 个正整数描述地图，每个数字表示相应位置的地洞中地鼠的数量。

outputFormat: 输出一个整数，表示最少的挥舞次数。

hint:
【样例说明】

使用 $2\times 2$ 的锤子，分别在左上、左下、右上、右下挥舞一次。

【数据规模和约定】

对于 $30\%$ 的数据，$m$, $n\leq 5$ ；

对于 $60\%$ 的数据，$m$, $n\leq 30$ ；

对于 $100\%$ 的数据，$1\leq m$, $n\leq 100$ ，其他数据不小于 $0$，不大于 $10^5$ 。


title: [SDOI2011] 计算器

background: 2024-8-11 update: 新增一组 hack。

description:
你被要求设计一个计算器完成以下三项任务：

1. 给定 $y,z,p$，计算 $y^z \bmod p$ 的值；
2. 给定 $y,z,p$，计算满足 $xy \equiv z \pmod p$ 的最小非负整数 $x$；
3. 给定 $y,z,p$，计算满足 $y^x \equiv z \pmod p$ 的最小非负整数 $x$。

为了拿到奖品，全力以赴吧！

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

第一行包含两个正整数 $T,K$，分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。

以下 $T$ 行每行包含三个正整数 $y,z,p$，描述一个询问。

outputFormat:
输出文件包括 $T$ 行。

对于每个询问，输出一行答案。

对于询问类型 2 和 3，如果不存在满足条件的，则输出 `Orz, I cannot find x!`。


title: [SDOI2011] 染色

description:
给定一棵 $n$ 个节点的无根树，共有 $m$  个操作，操作分为两种：

1. 将节点 $a$ 到节点 $b$ 的路径上的所有点（包括 $a$ 和 $b$）都染成颜色 $c$。
2. 询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 `112221` 由三段组成：`11`、`222`、`1`。

inputFormat:
输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 $n$ 和操作个数 $m$。

第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数 $w_i$ 代表结点 $i$ 的初始颜色。

第 $3$ 到第 $(n + 1)$ 行，每行两个用空格隔开的整数 $u, v$，代表树上存在一条连结节点 $u$ 和节点 $v$ 的边。

第 $(n + 2)$ 到第 $(n + m + 1)$ 行，每行描述一个操作，其格式为：

每行首先有一个字符 $op$，代表本次操作的类型。

- 若 $op$ 为 `C`，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 $a, b, c$，代表将 $a$ 到 $b$ 的路径上所有点都染成颜色 $c$。
- 若 $op$ 为 `Q`，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 $a, b$，表示查询 $a$ 到 $b$ 路径上的颜色段数量。

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

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

对于 $100\%$ 的数据，$1 \leq n, m \leq 10^5$，$1 \leq w_i, c \leq 10^9$，$1 \leq a, b, u, v \leq n$，$op$ 一定为 `C` 或 `Q`，保证给出的图是一棵树。

除原数据外，还存在一组不计分的 hack 数据。


title: [SDOI2011] 拦截导弹

description:
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

inputFormat:
第一行包含一个正整数 $n$，表示敌军导弹数量。

下面 $n$ 行按顺序给出了敌军所有导弹信息。第 $i+1$
 行包含两个正整数 $h_i$ 和 $v_i$，分别表示第 $i$ 枚导弹的高度和速度。

outputFormat:
输出包含两行。

第一行为一个正整数，表示最多能拦截掉的导弹数量；

第二行包含 $n$ 个 $0$ 到 $1$ 之间的实数，第 $i$ 个数字表示第 $i$ 枚导弹被拦截的概率（你可以保留任意多位有效数字）。

hint:
保证总方案数不超过 C++ 中 double 类型的存储范围。

### 数据范围及约定

- 均匀分布着约 $30\%$ 的数据，所有 $v_i$ 均相等；
- 均匀分布着约 $50\%$ 的数据，满足 $1\le h_i,v_i\le 1000$。
- 对于 $30\%$ 的数据，满足 $1\le n\le 1000$；
- 对于 $100\%$ 的数据，$1\le n\le 5\times 10^4$，$1\le h_i,v_i\le 10^9$。

### 评分标准

对于每个测试点，若输出的第一行与标准输出相同，则得到该测试点 $40\%$ 的分数，若输出文件的第二行的每个数与标准输出的误差均不大于 $10^{-4}$，则得到该测试点 $60\%$ 的分数，两项相加作为该测试点总得分。


title: [SDOI2011] 工作安排

description:
你的公司接到了一批订单。订单要求你的公司提供 $n$ 类产品，产品被编号为 $1 \sim n$，其中第 $i$ 类产品共需要 $C_i$ 件。公司共有 $m$ 名员工，员工被编号为 $1 \sim m$ 员工能够制造的产品种类有所区别。一件产品必须完整地由一名员工制造，不可以由某名员工制造一部分配件后，再转交给另外一名员工继续进行制造。

我们用一个由 $0$ 和 $1$ 组成的 $m \times n$ 的矩阵 $A$ 来描述每名员工能够制造哪些产品。矩阵的行和列分别被编号为 $1 \sim m$ 和 $1 \sim n$，$A_i,j$ 为 $1$ 表示员工 $i$ 能够制造产品 $j$，为 $0$ 表示员工 $i$ 不能制造产品 $j$。

如果公司分配了过多工作给一名员工，这名员工会变得不高兴。我们用愤怒值来描述某名员工的心情状态。愤怒值越高，表示这名员工心情越不爽，愤怒值越低，表示这名员工心情越愉快。员工的愤怒值与他被安排制造的产品数量存在某函数关系，鉴于员工们的承受能力不同，不同员工之间的函数关系也是有所区别的。

对于员工 $i$，他的愤怒值与产品数量之间的函数是一个 $S_i+1$ 段的分段函数。当他制造第 $1 \sim T_{i,1}$ 件产品时，每件产品会使他的愤怒值增加 $W_{i,1}$，当他制造第 $T_{i,1}+1 \sim T_{i,2}$ 件产品时，每件产品会使他的愤怒值增加 $W_{i,2}$ ……为描述方便，设 $T_{i,0}=0,T_{i,s_{i+1}}=+\infty$，那么当他制造第 $T_{i,j-1}+1 \sim T_{i,j}$ 件产品时，每件产品会使他的愤怒值增加 $W_{i,j}$，$1 \le j \le S_i+1$。

你的任务是制定出一个产品的分配方案，使得订单条件被满足，并且所有员工的愤怒值之和最小。由于我们并不想使用Special Judge，也为了使选手有更多的时间研究其他两道题目，你只需要输出最小的愤怒值之和就可以了。

inputFormat:
https://cdn.luogu.com.cn/upload/pic/1608.png

第一行包含两个正整数 $m$ 和 $n$，分别表示员工数量和产品的种类数；

第二行包含 $n$ 个正整数，第 $i$ 个正整数为 $C_i$；

以下 $m$ 行每行 $n$ 个整数描述矩阵 $A$；

下面 $m$ 个部分，第 $i$ 部分描述员工 $i$ 的愤怒值与产品数量的函数关系。每一部分由三行组成：第一行为一个非负整数 $S_i$，第二行包含 $S_i$ 个正整数，其中第 $j$ 个正整数为 $T_{i,j}$，如果 $S_i=0$ 那么输入将不会留空行（即这一部分只由两行组成）。第三行包含 $S_i+1$ 个正整数，其中第 $j$ 个正整数为 $W_{i,j}$。

outputFormat: 仅输出一个整数，表示最小的愤怒值之和。

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

- 存在 $30\%$ 的数据，保证 $1\le n,m\le 30$；
- 均匀分布着约 $30\%$ 的数据，满足 $S_i = 0$；
- 均匀分布着约 $30\%$ 的数据，满足 $S_i \le 1$（不包含上述 $S_i = 0$ 的数据）。

对于全部数据，满足 $1\le m,n\le 250$，$0\le S_i\le 5$，$0\le A_{i, j}\le 1$，$0< T_{i, j}< T_{i, j + 1}$，$0< W_{i,j} < W_{i, j + 1}$。所有数据均不大于 $10^5$。


title: [SDOI2011] 迷宫探险

description:
这是一个单人游戏。

游戏开始时，玩家控制的人物出生在迷宫的某个位置，玩家的目标是控制人物走到迷宫的某个出口（出口可能有多个）。

迷宫里有 $k$ 类陷阱（用  `A`,`B`,`C`……表示，相同字母代表相同类型的陷阱），每类陷阱可能是有害的或无害的，而在游戏开始时玩家并不知道哪些陷阱是有害的，哪些是无害的。

同一类陷阱的状态相同，即用同一个字母标志的陷阱要么全部有害，要么全部无害，不会发生一部分有害而另一部分无害的情况。任何陷阱状态的组合都有一个发生概率，考虑下例：

当 $k=2$ 时，迷宫内共有两类陷阱，分别用 `A` 和 `B` 表示，陷阱状态的组合共有 $4$ 种：-
- `A` 是无害陷阱，`B` 是无害陷阱。
- `A` 是有害陷阱，`B` 是无害陷阱；
- `A` 是无害陷阱，`B` 是有害陷阱；
- `A` 是有害陷阱，`B` 是有害陷阱；

下列表格是一个合法的概率表格：

|  | `A` 是无害陷阱 | `A` 是有害陷阱 |
| -----------: | -----------: | -----------: |
| **`B` 是无害陷阱** | $36\%$ | $24\%$ |
| **`B` 是有害陷阱** | $24\%$ | $16\%$ |

当 $k=3$ 时，会有 $8$ 种不同的陷阱状态组合，如果我们依然坚持使用概率表格，那么这个表格将会是三维的（$2\times 2 \times 2$，每一维对应着一类陷阱）。当 $k\ge 3$ 时，这将使得题目难以描述。因此我们使用一个大小为 $2^{k}$ 的数组 $p$ 来描述每种情况发生的可能性，$p$ 的下标范围为 $0\sim 2^{k}-1$。

$p$ 是这样生成的：

对于每个可能的陷阱状态组合，考虑所有 $k$ 类陷阱，令 $1$ 表示某个陷阱有害，$0$ 表示某个陷阱无害，把 `A` 作为二进制数的第 $0$ 位（从右边开始计数），`B` 作为第 $1$ 位，`C` 作为第 $2$ 位……通过以上操作，我们可以得到一个 $k$ 位的二进制数，把它转化成十进制后，$2^{k}$ 种陷阱状态的组合将会与整数 $0\sim2^{k}-1$ 一一对应。

设 $S = \displaystyle\sum_{i=0}^{2^k-1} p_i$，则陷阱状态组合 $i$ 出现的概率为 $\dfrac {p_{i}} {S}$。

上述表格对应的一个合法数组 $p$ 为 $36,24,24,16$。

当然同一个概率表格可能会对应多个数组 $p$（事实上有无数个数组 $p$ 能够迎合表格数据），例如上述表格同时也对应着下面的数组 $p$：$72,48,48,32$。

玩家控制的人物初始情况下有 $H$ 点生命，当人物踏上某个陷阱时，如果这个陷阱是有害的，那么会损失 $1$ 点生命，否则这个陷阱是无害的，不损失生命。无论上述哪种情况发生，玩家会立刻得到这个陷阱的信息（有害或无害）。一旦生命小于等于 $0$，玩家控制的人物会立刻死亡。

迷宫可以看作 $m\times n$ 的方格地图，每个元素可能是：
- `.`：表示这是平地，可以通过；
- `#`：表示这是墙，不能通过；
- `A`，`B` ，`C`……：表示这是一个陷阱；
- `$`：表示这是起点，地图中有且仅有一个；
- `@`：表示这是终点，地图中可以有多个，也可以一个也没有。

人物可以向上下左右四个方向行走，不可以走对角线，也不可以走出地图。

给定 $m\times n$ 的地图、$k$、$h$ 以及大小为 $2^{k}$ 的概率数组。你的任务是求出在执行最优策略时，人物能活着走出迷宫的概率。

inputFormat:
第一行包含 $4$ 个整数，分别表示 $m,n,k,H$；

下面 $m$ 行每行 $n$ 个字符描述迷宫地图；

最后一行包含 $2^{k}$ 个非负整数描述数组 $p$，数组下标从 $0$ 开始。

outputFormat: 仅包含一个数字，表示在执行最优策略时，人物活着走出迷宫的概率。四舍五入保留 $3$ 位小数。


title: [SDOI2011] 黑白棋

description:
小 A 和小 B 又想到了一个新的游戏。

这个游戏是在一个 $1 \times n$ 的棋盘上进行的，棋盘上有 $k$ 个棋子，一半是黑色，一半是白色。

最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

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

小 A 可以移动白色棋子，小 B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 $1$ 到 $d$ 个棋子。

每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。

小 A 和小 B 轮流操作，现在小 A 先移动，有多少种初始棋子的布局会使他胜利呢？

inputFormat: 输入三个数 $n,k,d$。

outputFormat: 输出小 A 胜利的方案总数。答案对 $10^9+7$ 取模。

hint:
- 对于 $30\%$ 的数据，有 $k=2$。
- 对于 $100\%$ 的数据，有 $1 \leq d \leq k \leq n \leq 10^4$，$k$ 为偶数，$k \leq 100$。


title: [SDOI2011] 消防

description:
某个国家有 $n$ 个城市，这 $n$ 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 $z_i$。

这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。

现在这个国家的经费足以在一条边长度和不超过 $s$ 的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。

你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

inputFormat:
输入包含 $n$ 行：

第 $1$ 行，两个正整数 $n$ 和 $s$，中间用一个空格隔开。其中 $n$ 为城市的个数，$s$ 为路径长度的上界。设结点编号以此为$1,2,\ldots,n$。

从第 $2$ 行到第 $n$ 行，每行给出 $3$ 个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，```2 4 7```表示连接结点 $2$ 与 $4$ 的边的长度为 $7$。

outputFormat: 输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。


title: [SDOI2011] 火星移民

description:
在 2xyz 年，人类已经移民到了火星上。由于工业的需要，人们开始在火星上采矿。火星的矿区是一个边长为 $N$ 的正六边形，为了方便规划，整个矿区被分为 $6 \times N \times N$ 个正三角形的区域（如图 $1$）。

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

整个矿区中存在 $A$ 矿，$B$ 矿，$C$ 矿三个矿场，和 $a$ 厂，$b$ 厂，$c$ 厂三个炼矿厂。每个三角形的区域可以是一个矿场、炼矿厂、山地、或者平地。

现在矿区管理局要求建立一个交通系统，使得矿场和对应炼矿厂之间存在一条公路，并且三条公路互不交叉（即一个三角形区域中不存在两条以上运输不同矿的公路）。两个三角形区域是相邻的当且仅当这两个三角形存在公共边，只有相邻的两个区域之间才能建一段路，建这段路的费用为 $1$。

注意，山地上是不能建公路的。由于火星金融危机的影响，矿区管理局想知道建立这样一个交通系统最少要花多少费用。更多的，当局向知道有多少种花费最小的方案。

inputFormat:
第 $1$ 行一个整数 $N$。表示这个矿区是边长为 $N$ 的正六边形。

接下来有 $6\times N\times N$ 的整数，分为 $2\ \times N$ 行，表示矿区当前区域的情况。$0$ 表示平地，$1,2,3$ 表示对应的矿区或者炼矿厂，$4$ 表示山地。（样例 $1$ 对应图 $2$）。

可能有多组数据，请处理到文件结尾。

outputFormat: 对于每组数据，包含两个整数，表示最小费用和达到最小费用的方案数。如果找不到符合要求的方案，输出 $\verb!-1 -1!$。由于方案数可能过大，所以请把方案数 $\bmod (10^9+7)$。

hint:
样例2解释

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

【数据规模和约定】

对于 $50\%$ 的数据，$N \le 4$。

对于 $100\%$ 的数据，$N \le 6$。


title: [SDOI2011] 贪食蛇

description:
相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。

活动区域：

贪食蛇的活动区域是一个 $R$ 行 $C$ 列的网格 $A$，贪食蛇活动不能超过这个网格的范围。第 $i$ 行第 $j$ 列的方格用 $A_{i,j}$ 表示。每个方格有一个整数权值，记作 $w(A_{i,j})$。$0 \leq w(A_{i,j}) \leq 8$，$w(A_{i,j}) = 0$时，$A_{i,j}$ 禁止进入；$w(A_{i, j}) > 0$时，$A_{i, j}$ 允许进入。

方向：

对于 $P = (X_0, Y_0)$、$Q = (X_1, Y_1)$，有以下四种基本方向：

- 正左(L)：$X_0 = X_1$ 且 $Y_0 = Y_1 - 1$，则称 $P$ 位于 $Q$ 的正左方向。
- 正右(R)：$X_0 = X_1$ 且 $Y_0 = Y_1 + 1$，则称 $P$ 位于 $Q$ 的正右方向。
- 正上(U)：$X_0 = X_1 - 1$ 且 $Y_0 = Y_1$，则称 $P$ 位于 $Q$ 的正上方向。
- 正下(D)：$X_0 = X_1 + 1$ 且 $Y_0 = Y_1$，则称 $P$ 位于 $Q$ 的正下方向。

贪食蛇：

贪食蛇 $B$ 是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为 $m$，则贪食蛇从头到尾，用 $B_1, B_2, \dots, B_m$表示。记 $p$ 为贪食蛇的形态，若 $B_i$ 位于第 $X_i$ 行第 $Y_i$ 列，则 $p(B_i)=(X_i, Y_i)$。初始情况下，$m = 4$，且运动过程中始终需要满足以下限制：

- 对于 $B_i$ 和 $B_{i + 1}$ $(1 \leq i < m)$，就是贪食蛇的前、后相邻两部分，必须满足 $B_i$ 位于 $B_{i + 1}$ 的L、R、U、D四个方向之一。
- 对于 $B_i$ 和 $B_j$ $(1 \leq i < j \leq m)$，$p(B_i) = (X_i, Y_i)$，$p(B_j) = (X_j,Y_j)$，需要满足 $X_i \neq X_j$ 或 $Y_i \neq Y_j$ 。也就是说，贪食蛇身体的任意一部分不能相交。

食物：

贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上，食物不会重叠。每个食物只能被吃一次。

贪食蛇的运动：

如果贪食蛇的头部 $B1$ 的L、R、U、D四个方向之一的 $A_{i, j}$ 能进入，且 $A_{i, j}$ 上不存在食物，则贪食蛇可以向该方向运动，新的头部位于 $A_{i, j}$ 上。记 $p'$ 为贪食蛇新的形态，则：

- $p'(B_k) = p(B_{k - 1})$，当 $2 \leq k \leq m$。
- $p'(B_k) = (i, j)$，当 $k = 1$。

贪食蛇的进食：

如果贪食蛇的头部 $B_1$ 的L、R、U、D四个方向之一的 $A_{i, j}$ 能进入，且 $A_{i,j}$ 上存在食物，则贪食蛇可以向该方向进食，新的头部位于 $A_{i, j}$ 上，蛇的新长度 $m'=m+1$。记 $p'$ 为贪食蛇新的位置，则：

- $p'(B_k) = p(B_{k-1})$，当 $2 \leq k \leq m'$。
- $p'(B_k) = (i,j)$，当 $k = 1$.

注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置，因为在变换后头部和尾部仍不会重叠。

运动或进食所需要的时间：

贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是P，运动或进食后头部所在的方格是 $Q$，则此次运动或进食的所消耗的时间为 $|w(P) - w(Q)| + 1$。

游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。

inputFormat:
第一行，两个正整数 $R, C$。

接下来 $R$ 行，每行 $C$ 个没有空格分隔的数字。其中第 $i$ 行第 $j$ 个数字为 $w(A_{i, j})$。

接下来 $4$ 行，每行 $2$ 个正整数。第 $i$ 行的两个整数 $X_i, Y_i$，表示 $p(B_i) = (X_i, Y_i)$。

接下来一个正整数 $N$，表示食物的数量。

接下来 $N$ 行，每行 $2$ 个正整数 $i, j$，表示 $A_{i, j}$上存在一个食物。

outputFormat:
如果贪食蛇不能吃到所有的食物，输出 `No solution.`。

否则，输出：

第一行，一个整数，表示所需花费的时间；

第二行，一个由 L、R、U、D 组成的字符串，表示贪食蛇前进的方案。如果存在多种可能，你只需输出任意一种。

hint:
- 对于 $20\%$ 的数据，$N \leq 1$；
- 对于 $30\%$ 的数据，$R \times C \leq 36$；
- 对于 $40\%$ 的数据，$N \leq 2$；
- 对于 $60\%$ 的数据，$N \leq 3$；
- 对于 $100\%$ 的数据，$N \leq 4$，$R \leq 12$，$C \leq 12$。


title: [SDOI2011] 保密

description:
现在，保密成为一个很重要也很困难的问题。如果没有做好，后果是严重的。比如，有个人没有自己去修电脑，又没有拆硬盘，后来的事大家都知道了。

当然，对保密最需求的当然是军方，其次才是像那个人。为了应付现在天上飞来飞去的卫星，军事基地一般都会建造在地下。

某 K 国的军事基地是这样子的：地面上两排大天井共 $n_1$ 个作为出入口，内部是许多除可以共享出入口外互不连通的空腔，每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为 $1, 3, 5, \dots$ 和 $2, 4, 6, \dots$ 并且最大的编号为 $n_1$。

虽然上面扯了那么多关于保密的东西，但是其实解密也是一件很纠结的事情。但其实最简单直接暴力无脑的解密方法就是找个人去看看…

我们有很牛 X 的特种部队，只需要派出一支特种部队到 K 国基地的某个出入口，那么和这个出入口直接相连的所有空腔都可以被探索，但也只有这些空腔可以被这支部队探索。现在有足够多的特种部队可以供你调遣，你必须使用他们调查完所有的 K 国基地内的空腔。

当然，你的基地离 K 国基地不会太近，周边的地图将会给你，表示为 $n$ 个检查点和 $m$ 条连接这些点的道路，其中点 $1$ 到点 $n_1$ 就是 K 国基地的出入口，点 $n$ 是你的部队的出发点。对每条道路，有不同的通行时间 $t$ 和安全系数 $s$ 。因为情报部门只对单向的道路安全系数进行了评估，所以这些道路只允许单向通行，并且不会存在环。

一支特种部队从你的基地出发，通过某条路径，到达某个 K 国基地出入口，此时这支部队的危险性表示为总时间和这条路径经过的所有道路的安全系数和的比值。整个行动的危险性表示为你派出的所有部队的危险性之和。你需要使这个值最小的情况下探索整个 K 国基地。

快点完成这个任务，在 K 国的叫兽宣布你是 K 国人之前。

inputFormat:
第一行 2 个正整数 $n, m$ 表示整个地区地图上的检查点和道路数。

下面 $m$ 行，每行 4 个正整数 $a, b, t, s$ 表示一条从 $a$ 到 $b$ 的道路需时为 $t$，安全系数为 $s$。

接下来 1 行 2 个正整数 $m_1$ 和 $n_1$, $m_1$ 表示 K 国基地空腔的个数，$n_1$ 表示 K 国基地出入口的个数。

再接下来 $m_1$ 行，每行 2 个正整数 $u, v$，表示每个空腔的 $2$ 个出入口。

outputFormat: 一行，最小的危险性，保留一位小数。或者输出 `-1` 表示此任务不可能完成。


title: [SDOI2011] 消耗战

description:
在一场战争中，战场由 $n$ 个岛屿和 $n-1$ 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 $1$ 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 $k$ 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。

侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 $1$ 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 $m$ 次，所以我们只需要把每次任务完成即可。

inputFormat:
第一行一个整数 $n$，表示岛屿数量。

接下来 $n-1$ 行，每行三个整数 $u,v,w$ ，表示 $u$ 号岛屿和 $v$ 号岛屿由一条代价为 $w$ 的桥梁直接相连。

第 $n+1$ 行，一个整数 $m$ ，代表敌方机器能使用的次数。

接下来 $m$ 行，第 $i$ 行一个整数 $k_i$ ，代表第 $i$ 次后，有 $k_i$ 个岛屿资源丰富。接下来 $k_i$ 个整数 $h_1,h_2,..., h_{k_i}$ ，表示资源丰富岛屿的编号。

outputFormat: 输出共 $m$ 行，表示每次任务的最小代价。

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

- 对于 $10\%$ 的数据，$n\leq 10, m\leq 5$ 。
- 对于 $20\%$ 的数据，$n\leq 100, m\leq 100, 1\leq k_i\leq 10$ 。
- 对于 $40\%$ 的数据，$n\leq 1000, 1\leq k_i\leq 15$ 。
- 对于 $100\%$ 的数据，$2\leq n \leq 2.5\times 10^5, 1\leq m\leq 5\times 10^5, \sum k_i \leq 5\times 10^5, 1\leq k_i< n, h_i\neq 1, 1\leq u,v\leq n, 1\leq w\leq 10^5$ 。


title: [SDOI2012] 体育课

background: # 警告：滥用本题评测将被封号

description:
又是一节体育课的时间了，有 $n$ 个同学排成了一排。他们都很讨厌排在第一个位置的同学，于是后面的同学中比第一个高的都会产生一个高兴值，这个高兴值等于他的身高减去第一个同学的身高。当然比第一个同学矮的同学产生兴奋值为 $0$。

现在体育老师来了，他拥有神奇的魔法，现在他能做如下的三件事：

1. 询问某段区间高兴值最大的那个是多少。

2. 把某两个同学交换一下位置。

3. 选取一段区间的人，把第一个人身高加上 $t$，第二个加上 $2t$，第三个加上 $3t$ 以此类推。

但是体育老师不会数数，于是他找到你了，对于每一个询问，他要你帮他求出那个值。

inputFormat:
第一行两个整数 $n,m$，表示有 $n$ 个人，有 $m$ 个操作。

第二行 $n$ 个整数，顺序输入每个人的身高 $a_i$。

接下来 $m$ 行，每行第一个数位一个 $type$ 表示是做哪一件事情。

- 如果 $type=1$，那么接下来有两个整数 $l,r$，表示询问这段区间的最大的高兴值。
- 如果 $type=2$，接下来两个整数 $a,b$，表示交换这两个位置的人。
- 如果 $type=3$，接下来三个整数 $l,r,t$，表示把 $l$ 个人的升高增加 $t$,$l+1$ 个人增加 $2t$ ...第 $r$ 个人增加 $(r-l+1)t$。

outputFormat: 对于每个询问按照顺序输出每个操作 $1$ 的答案。

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

- 对于 $20\%$ 的数据，保证 $1 \le n,m \le 5 \times 10^3$。
- 另有 $10\%$ 的数据，没有第三种操作。
- 另有 $20\%$ 的数据，没有第二种操作。
- 对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$0 \le t \le 10^4$，$1 \leq a_i \leq 10^8$。


title: [SDOI2012] 基站建设

description:
up 主家终于买电脑了，但是接下来有各种问题要处理。首要解决的问题就是网络问题。他要从移动公司开始，通过一些基站来传递网络到他家。

为了简化问题，我们假设移动公司，所有的基站、up 主家位于同一条直线上，他们都位于这一条直线上的某一点 $x$，这些点**可能**会重合。每个基站发射和接收的范围都是一个切于地面的圆，发射的半径 $r$ 是固定的，接收半径 $r'$ 是可调的的。如下图：

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

一个点 $i$ 如果能从另一个点 $j$ 接收到信号（当且仅当 $x_j<x_i$），必须满足 $i$ 的接收范围与 $j$ 的发射范围相切，并且需要付 $\sqrt{r'_i}$ 的额外费用。同时启动每一个点 $i$ 都需要费用 $v_i$。

当然一个点如果能够发射的 up 主家只需要这个点的发射范围与 up 主家所在的竖线相切或相交即可，如下图：

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

当然费用越少就越好咯，于是 up 主想要请你帮他的忙。

inputFormat:
第一行两个整数 $n, m$。表示基站个数（包括移动公司），up 主家的坐标。（保证大于等于所有基站的坐标）

记下来 $n$ 行，每行三个整数 $x_i$，$r_i$，$v_i$，表示每个基站的坐标，发射范围以及费用。

$x_i$ 是按照坐标从小到大输入的，移动公司位于最小的那个坐标。

$r$ 为 $1\dots n$ 的排列。

outputFormat: 一个实数，保留小数点后三位。


title: [SDOI2012] 拯救小云公主

description:
英雄又即将踏上拯救公主的道路……

这次的拯救目标是——爱和正义的小云公主。

英雄来到boss的洞穴门口，他一下子就懵了，因为面前不只是一只boss，而是上千只boss。当英雄意识到自己还是等级1的时候，他明白这就是一个不可能完成的任务。

但他不死心，他在想，能不能避开boss去拯救公主呢，嘻嘻。

Boss的洞穴可以看成一个矩形，英雄在左下角（1,1），公主在右上角（row，line）。英雄为了避开boss，当然是离boss距离越远越好了，所以英雄决定找一条路径使到距离boss的最短距离最远。

Ps:英雄走的方向是任意的，但是不能走出矩形的范围。即英雄可以到达矩形范围内的任意一个点（没有必要是整点）

你可以帮帮他吗？

当英雄找到了美丽漂亮的小云公主，立刻就被boss包围了！！！英雄缓闭双眼，举手轻挥，白光一闪后使用了回城卷轴，回到了城堡，但只有小云公主回去了……因为英雄忘了进入回城的法阵了。

inputFormat:
第一行，输入三个整数，n表示boss的数目，row，line表示矩形的大小；

接下来n行，每行分别两个整数表示boss的位置坐标。

outputFormat: 输出一个小数，表示英雄的路径离boss的最远距离，精确到小数点后两位。

hint:
数据范围：

20%数据，boss坐标范围小于等于50；

60%数据，n<=1500；

100%数据，n<=3000；


title: [SDOI2012] 象棋

description:
小云和小南两姐妹从小喜欢下象棋，现在作为象棋高手的她们，已经不屑于玩平常的象棋了，于是她们便开始用棋盘和棋子玩各种各样的新游戏。

今天天气晴朗，阳光明媚，她们将在 $n\times m$ 的棋盘上进行游戏。

棋盘上有 $k$ 颗棋子和若干有障碍格子，令棋盘左上角格子坐标为 $(1,1)$，右下角格子坐标为 $(n,m)$，参数 $a,b$ 规定了所有棋子的走法：在 $(x, y)$ 的棋子下一步能走到 $(x + a, y + b), (x + a, y - b), (x  – a, y + b), (x – a, y – b), (x + b, y + a), (x + b, y - a), (x – b, y + a), (x – b, y – a)$ 这八个格子中的一个，棋子任何时候不能跃出棋盘或走到有障碍的格子上。

这k颗棋子是相同的，小云和小南的目标是用最少步数把所有棋子移动到特定格子，要求移动过程中不能出现多颗棋子同时在某一格的情况。

她们已经想出步数较少方案，但无法确定这是否为最少步数，所以向作为程序员的你求助。

inputFormat:
第一行五个空格隔开的整数 $n,m,k,a,b$；

接下来 $n$ 行，每行为长度 $m$ 的字符串，描述棋盘，`.` 表示没有障碍的格子，`*` 表示有障碍的格子；

接下来 $k$ 行，每行两个整数 $x$ 和 $y$，分别表示 $k$ 颗棋子的初始位置；

接下来 $k$ 行，每行两个整数 $x$ 和 $y$，分别表示 $k$ 颗棋子的目标位置。

outputFormat: 一个整数，为把所有棋子移动到目标位置的最少步数，数据保证有解。

hint:
【样例说明】

一可行方案如下：第二颗棋子向右跳两步，随后第一颗棋子向右跳两步，共 $4$ 步。值得注意的是，第一颗棋子向右跳三步，随后第二颗棋子向右跳一步的方案尽管能把棋子都移动到目标位置，但途中两颗棋子曾经同时在 $(1, 3)$，违反了规则，所以不能选用此方案。

数据范围

其中 $20\%$ 的数据，$n\times m\le 20$。

另外 $10\%$ 的数据，$n = 1$；

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


title: [SDOI2012] 集合

description:
小H在学习“集合与图论”的时候遇到了一个问题，他思考了很久依然无法很好完成这个问题。于是他只好来求助你了，给出n个点m条边的带权无向图（即每条无向边上都有一个权值），有3个集合A、B、C。一开始无向图中所有点都属于A集合，有如下9种操作：

MoveA x：表示将第x个点从所在集合中删除，并加入至A集合。

MoveB x：表示将第x个点从所在集合中删除，并加入至B集合。

MoveC x：表示将第x个点从所在集合中删除，并加入至C集合。

AskAA：询问两个端点都属于A集合的所有边中最小的权值是多少。

AskAB：询问两个端点分别属于A集合和B集合的所有边中最小的权值是多少。

AskAC：询问两个端点分别属于A集合和C集合的所有边中最小的权值是多少。

AskBB：询问两个端点都属于B集合的所有边中最小的权值是多少。

AskBC：询问两个端点分别属于B集合和C集合的所有边中最小的权值是多少。

AskCC：询问两个端点都属于C集合的所有边中最小的权值是多少。

你能帮助他解决这个问题吗？

inputFormat:
输入的第1行有两个正整数，分别表示n和m。

在第2行至第m+1行中，每行有三个正整数，分别为u、v、w。表示这条无向边的两个端点分别为u和v(u != v)，且这个边的权值为w(w<=10^9)。

第m+2行有一个正整数q，表示有q个询问。

在第m+3行至第m+q+2行中，每行的输入方式为题目描述里9种操作中的一种。

outputFormat: 对于所有的Ask操作输出最小的权值，如果不存在则输出“No Found!”。

samples:
4 3
1 2 1
2 3 2
3 1 3
5
AskAA
AskAB
MoveB 2
AskAA
AskAB


title: [HAOI2006] 数字序列

description: 现在我们有一个长度为 $n$ 的整数序列 $a$。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。

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

outputFormat:
第一行输出一个整数，表示最少需要改变多少个数。

第二行输出一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。

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

- 对于 $90\%$ 的数据，保证 $n \leq 6 \times 10^3$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 3.5 \times 10^4$，$1 \leq a_i \leq 10^5$。数据保证 $a_i$ 随机生成。


title: [HAOI2006] 旅行

description:
Z 小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z 小镇附近共有 $n$ 个景点（编号为 $1,2,3,\ldots,n$），这些景点被 $m$ 条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。

也许是为了保护该地的旅游资源，Z 小镇有个奇怪的规定，就是对于一条给定的公路 $r_i$，任何在该公路上行驶的车辆速度必须为 $v_i$。

速度变化太快使得游客们很不舒服，因此从一个景点前往另一个景点的时候，大家都希望选择行驶过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

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

接下来的 $m$ 行每行包含三个正整数 $x,y,v$。表示景点 $x$ 到景点 $y$ 之间有一条双向公路，车辆必须以速度 $v$ 在该公路上行驶。

最后一行包含两个正整数 $s,t$，表示想知道从景点 $s$ 到景点 $t$ 最大最小速度比最小的路径。$s$ 和 $t$ 不可能相同。

outputFormat: 如果景点 $s$ 到景点 $t$ 没有路径，输出` IMPOSSIBLE`。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。


title: [HAOI2006] 均分数据

description:
已知 $n$ 个正整数 $a_1,a_2 ... a_n$ 。今要将它们分成 $m$ 组，使得各组数据的数值和最平均，即各组数字之和的均方差最小。均方差公式如下：

$$\sigma = \sqrt{\frac 1m \sum\limits_{i=1}^m(\overline x - x_i)^2},\overline x = \frac 1m \sum\limits_{i=1}^m x_i$$

其中 $\sigma$ 为均方差，$\bar{x}$ 为各组数据和的平均值，$x_i$ 为第 $i$ 组数据的数值和。

inputFormat:
第一行是两个整数，表示 $n,m$ 的值（ $n$ 是整数个数，$m$ 是要分成的组数）

第二行有 $n$ 个整数，表示 $a_1,a_2 ... a_n$。整数的范围是 $[1,50]$。

（同一行的整数间用空格分开）

outputFormat: 输出一行一个实数，表示最小均方差的值(保留小数点后两位数字)。

hint:
样例解释：$1,6$、$2,5$、$3,4$ 分别为一组

【数据规模】

对于 $40\%$ 的数据，保证有 $m \le n \le 10$，$2 \le m \le 6$

对于 $100\%$ 的数据，保证有 $m \le n \le 20$，$2 \le m \le 6$


title: [HAOI2006] 聪明的猴子

description:
在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。

现在，在这个地区露出水面的有 $N$ 棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。

在这个地区住着的猴子有 $M$ 个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。

现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。

inputFormat:
输入包括：

第 $1$ 行为一个整数，表示猴子的个数 $M$ $(2 \le M \le 500)$；

第 $2$ 行为 $M$ 个整数，依次表示猴子的最大跳跃距离（每个整数值在 $1 \sim 1000$ 之间）；

第 $3$ 行为一个整数表示树的总棵数 $N$ $(2 \le N \le 1000)$ ；

第 $4$ 行至第 $N+3$ 行为 $N$ 棵树的坐标（横纵坐标均为整数，范围为：$-1000 \sim 1000$）。

（同一行的整数间用空格分开）

outputFormat: 输出包括一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。

hint:
对于 $40\%$ 的数据，保证有 $2 \le N \le 100$，$1 \le M \le 100$

对于全部的数据，保证有 $2 \le N \le 1000$，$1 \le M \le500$

感谢 @charlie003 修正数据


title: Uim的情人节礼物·其之壱

description:
情人节到了，Uim打算给他的后宫们准备情人节礼物。UIm 一共有$N$（$1\le N\le 9$）个后宫妹子（现充去死挫骨扬灰!）。

为了维护他的后宫的稳定。他通过编程，得出了一个送礼物的最佳顺序。这个我们管不着。

然而他认为，如果什么事情做得太圆满不是什么好事。于是他希望得到原定顺序的前一个字典序的序列。

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

第二行 $N$ 个整数，表示原定排列。

outputFormat: 输出 $N$ 个数，表示给定排列的前一个排列。特别地，若当前排列已经是第一个，则输出 `ERROR`。


title: [HAOI2012] 道路

description: C 国有 $n$ 座城市，城市之间通过 $m$ 条**单向**道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。

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

接下来 $m$ 行每行包含三个正整数 $u, v, w$，表示有一条从 $u$ 到 $v$ 长度为 $w$ 的道路

outputFormat: 输出应有 $m$ 行，第 $i$ 行包含一个数，代表经过第 $i$ 条道路的最短路的数目对 $10^9+7$ 取模后的结果。


title: [SCOI2008] 劣质编码

description:
一个编码方案把每个字符对应到一个01 串。例如{1,1010,01,10101}就是一个编码方案，它把四个字符（假设它们为a,b,c,d）分别对应到串1、1010，01，10101。字符串的编码为各字符编码的连接。例如，在刚才的编码方案中，字符串cac的编码为01101，dcb的编码为10101011010。

进一步分析发现，刚才的编码是相当劣质的，因为字符串ba, acc 和d 的编码都是10101。对于一个编码方案，你的任务是找出三个不同的字符串，使得它们的编码全相同。换句话说，找一个01 编码串，使得它至少有三种解码方式。如果有多组解，这个编码串应当尽量短。

inputFormat: 第一行包含一个整数n，即符号的个数。以下n 行每行为一个长度不超过50的01串（可能为空串），即各符号的编码。

outputFormat: 仅一行，包含一个整数，即最短编码的长度。如果无解，输出-1。


title: [SCOI2008] 配对

description: 你有 $n$ 个整数 $A_i$ 和 $n$ 个整数 $B_i$。你需要把它们配对，即每个 $A_i$ 恰好对应一个 $B_{p[i]}$。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对。例如 $A = \{5, 6, 8\}$，$B = \{5, 7, 8 \}$，则最优配对方案是 $5 \sim 8$、$6 \sim 5$、$8 \sim 7$，配对整数的差的绝对值分别为 $3, 1, 1$，和为 $5$。注意，$5 \sim 5$、$6 \sim 7$、$8 \sim 8$ 是不允许的，因为相同的数不许配对。

inputFormat: 第一行为一个正整数 $n$，接下来是 $n$ 行，每行两个整数 $A_i$ 和 $B_i$，保证所有 $A_i$ 各不相同，$B_i$ 也各不相同。

outputFormat: 输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输出 `-1`。


title: [HAOI2008] 圆上的整点

description: 求一个给定的圆$(x^2+y^2=r^2)$，在圆周上有多少个点的坐标是整数。

inputFormat: r

outputFormat: 整点个数


title: [SCOI2008] 警告

description:
有一个简单的脚本语言，只有赋值语句、条件语句和返回语句三种。变量名必须是单个大写字母，且变量都是 $32$ 位带符号整数。

该语言的每条语句必须单独占一行。程序中不含空行，且每行的行首行末均无空格。每行的不同 token 之间用单个空格隔开。该语言的 BNF 如下：

```cpp
<line> :: <head> | <assignment> | <if> | ELSE | END IF | <return>
<head> :: PARAM <paramlist> | PARAM
<assignment> :: <variable> = <rvalue>
<if> :: IF <variable> <relation> <value> THEN
<return> :: RETURN <value>
<paramlist> :: <variable> | <variable> <paramlist>
<rvalue> :: <value> | <value> <operator> <value>
<value> :: <variable> | <integer>
<operator> :: + | - | * | /
<relation> :: < | = | >
<variable> :: A | B | ... | Z
<integer> :: 不含前导 0 的 32 位带符号整数
```
程序的第一行是一条 `<head>` 语句，定义了函数的参数，而最后一行一定是 `<return>` 语句。`<head>` 语句不能在除了第一行之外的其他任何地方出现，但 `<return>` 语句可以在程序中多次出现。行号从 $1$ 开始编号。
每条 `IF` 语句一定有一个配套的 `END IF` 语句，还有一个可选的 `ELSE` 语句（注意没有 `ELSE IF` 语句）。`IF` 语句可以嵌套，它总是比较一个变量和一个整数或者另一个变量。

你应该分析一个给定的程序，并输出两类警告信息（格式见样例输出）：

- 第一类警告：无法到达的代码行。不管各条 `IF` 语句的布尔表达式是真还是假（假设每条 `IF` 语句的布尔表达式都是既可能为真也可能为假，不受其他 `IF` 语句结果影响）。

- 第二类警告：可能未初始化的变量。该语句用到了某个变量的值，但这个变量既不在第一行指定的参数列表里，也没有在此之前由赋值语句赋值过。如果这条语句无法到达，那么不应该给出这类警告。

注意，语句 `ELSE` 和 `END IF` 不是可执行语句，因此不应该收到任何警告信息。

inputFormat: 最多包含 $50$ 行，即你要处理的程序。保证该程序合法。

outputFormat: 警告按照行号从小到大排序。如果同一行内有多个可能未初始化的变量，按照字母顺序从小到大排列。如果没有任何警告信息，你的输出应该为空。

samples:
PARAM A B
IF A > 5 THEN
C = B * A
END IF
D = B - C
Z = Y + X
E = T
F = E + E
V = G + G
RETURN F

samples:
Line 5: variable C might not have been
initialized
Line 6: variable X might not have been
initialized
Line 6: variable Y might not have been
initialized
Line 7: variable T might not have been
initialized
Line 9: variable G might not have been
initialized

samples:
Line 3: unreachable code
Line 4: unreachable code

samples:
PARAM T C
B = T
A = 4
IF A < 4 THEN
IF B > 3 THEN
Q = 100 + F
ELSE
IF C = -1111111111 THEN
Q = T - A
IF Q = 0 THEN
V = V - 1
END IF
ELSE
RETURN I
E = A
END IF
END IF
ELSE
Q = 1
END IF
RETURN Q

samples:
Line 6: variable F might not have been
initialized
Line 11: variable V might not have
been initialized
Line 14: variable I might not have
been initialized
Line 15: unreachable code


title: [HAOI2008] 下落的圆盘

description:
有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求.

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

inputFormat: n ri xi y1 ... rn xn yn

outputFormat: 最后的周长，保留三位小数


title: [HAOI2008] 木棍分割

description: 有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果**mod 10007**。。。

inputFormat: 输入文件第一行有2个数n,m. 接下来n行每行一个正整数Li,表示第i根木棍的长度.

outputFormat: 输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.


title: [HAOI2008] 糖果传递

description: 有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$。

inputFormat: 小朋友个数 $n$，下面 $n$ 行 $a_i$。

outputFormat: 求使所有人获得均等糖果的最小代价。


title: [HAOI2009] 逆序对数列

description: 对于一个数列 $\{a_i\}$，如果有 $i<j$ 且 $a_i>a_j$，那么我们称 $a_i$ 与 $a_j$ 为一对逆序对数。若对于任意一个由 $1 \sim n$ 自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为 $k$ 的这样自然数数列到底有多少个？

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

outputFormat: 写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。

hint:
样例说明：

下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；

测试数据范围

30%的数据  $n\le 12$。

100%的数据  $n\le 1000$，$k\le 1000$。


title: [HAOI2010] 工厂选址

description:
某地区有 $m$ 座煤矿，其中第 $i$ 号矿每年产量为 $a_i$ 吨。现有一火力发电厂，每年需用煤恰好 $b$ 吨，每年运行的固定费用（不包括煤的运费）为 $h$ 元，每吨原煤从第 $i$ 号矿运到火力发电厂的运费为 $C_{i,0}$ 元。

现规划新建一个发电厂， $m$ 座煤矿每年开采的原煤将全部供给这两座发电厂。有 $n$ 个备选的新发电厂厂址，若在第 $j$ 号备选厂址建新厂，每年运行的固定费用为 $h_j$ 元；每吨原煤从第 $i$ 号矿运到第 $j$ 号备选厂址的运费为 $C_{i,j}$ 元。

试问：应如何选取新厂厂址并分配 $m$ 座煤矿开采的原煤，才能使每年的总费用（发电厂运行费用与原煤运费之和）最小。

inputFormat:
第一行四个整数 $m,b,h,n$。

接下来一行 $m$ 个整数 $a_1,a_2,...,a_m$ 表示每一处煤矿的年产量。

接下来一行 $n$ 个整数 $h_1,h_2,...,h_n$ 表示新厂建在每一个位置的固定费用。

接下来 $n+1$ 行每行 $m$ 个正整数，第 $i$ 行描述 $C_{1,i-1} , C_{2,i-1} , ... , C_{m , i-1}$的值。

outputFormat:
第一行一个整数表示选择的新发电厂的厂址编号，如有多个厂址满足条件，输出最小的一个；

第二行一个整数表示最小的年总费用。

hint: 对于$100 \%$的数据，$1 \leq m \leq 5 \times 10^4$，$1 \leq b \leq 10^4$，$1 \leq n \leq 50$，$0 \leq h , h_i \leq 100$，$0 \leq a_i \leq 500$，$\sum\limits_{i=1}^m a_i \geq b$，$0 \leq C_{i,j} \leq 50$。


title: [HAOI2010] 软件安装

description:
现在我们的手头有 $N$ 个软件，对于一个软件 $i$，它要占用 $W_i$ 的磁盘空间，它的价值为 $V_i$。我们希望从中选择一些软件安装到一台磁盘容量为 $M$ 计算机上，使得这些软件的价值尽可能大（即 $V_i$ 的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件 $i$ 只有在安装了软件 $j$（包括软件 $j$ 的直接或间接依赖）的情况下才能正确工作（软件 $i$ 依赖软件 $j$)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为 $0$。

我们现在知道了软件之间的依赖关系：软件 $i$ 依赖软件 $D_i$。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则 $D_i=0$，这时只要这个软件安装了，它就能正常工作。

outputFormat: 一个整数，代表最大价值。


title: [HAOI2010] 最长公共子序列

description: 字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列$X=\{x_0,x_1,\cdots ,x_{m-1}\}$，序列$Y=\{y_0,y_1,\cdots ,y_{k-1}\}$ 是 $X$ 的子序列，存在 $X$ 的一个严格递增下标序列 $\{i_0,i_1,\cdots,i_{k-1}\}$ ，使得对所有的$j=0,1,\cdots,k-1$ ，有 $x_{ij}=y_j$ 。例如，$X=\verb!"ABCBDAB"!$ ，$Y=\verb!"BCDB"!$ 是 $X$ 的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。

inputFormat:
第一行为第一个字符序列，都是大写字母组成，以 . 结束，大写字母个数不超过 $5000$。

第二行为第二个字符序列，都是大写字母组成，以 . 结束，大写字母个数不超过 $5000$。

outputFormat:
第一行输出上述两个最长公共子序列的长度。

第二行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对 $10^{8}$ 求余即可。


title: [HAOI2010] 订货

description: 某公司估计市场在第 $i$ 个月对某产品的需求量为 $U_i$，已知在第 $i$ 月该产品的订货单价为 $d_i$，上个月月底未销完的单位产品要付存贮费用 $m$，假定第一月月初的库存量为 $0$，第 $n$ 月月底的库存量也为 $0$，问如何安排这 $n$ 个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为 $S$。

outputFormat: 只有 $1$ 行，一个整数，代表最低成本。


title: [HAOI2010] 计数

description: 现在给定一个数，你可以删掉这个数中的任意多个数位 $0$（或不删）并将其他的数位任意重新排序。请求出能产生出多少个不同的这个数小的数（注意这个数不会有前导 0）。

inputFormat: 只有一行，为一个整数 $n$。

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


title: [HAOI2011] problem a

description:
一次考试共有 $n$ 个人参加，可能出现多个人成绩相同的情况。第 $i$ 个人说：“有 $a_i$ 个人成绩比我高，$b_i$ 个人成绩比我低。”

请求出最少有几个人没有说真话。

inputFormat:
输入的第一行是一个整数，代表参加考试的人数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个用空格隔开的整数，第 $(i + 1)$ 行的两个整数分别代表比第 $i$ 个人成绩高的人数 $a_i$ 和比第 $i$ 个人成绩低的人数 $b_i$。

outputFormat: 输出一行一个整数，代表最少有几个人没有说真话。

hint: 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$0 \leq a_i, b_i \leq n$。


title: [HAOI2011] 向量

description:
给你一对数 $(a,b)$，你可以任意使用 $(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)$ 这些向量，问你能不能拼出另一个向量 $(x,y)$。

说明：这里的拼就是使得你选出的向量之和为 $(x,y)$。

inputFormat:
第一行数组组数 $t(t\leq50000)$。

接下来 $t$ 行，每行四个整数 $a,b,x,y(-2\times10^9\leq a,b,x,y\leq2\times10^9)$。

outputFormat: $t$ 行，每行为 `Y` 或者为 `N`，分别表示可以拼出来，不能拼出来。


title: [HAOI2011] 防线修建

description:
近来A国和B国的矛盾激化，为了预防不测，A 国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。

可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于 A 国的经费有限，所以希望你能帮忙完成如下的一个任务：

1、给出你所有的 A 国城市坐标

2、A国上层经过讨论，考虑到经济问题，决定取消对 $u$ 城市的保护，也就是说 $u$ 城市不需要在防线内了

3、A国上层询问对于剩下要保护的城市，修建防线的总经费最少是多少

你需要对每次询问作出回答。注意单位长度的防线花费为 $1$。

A 国的地形是这样的，形如下图，$x$ 轴是一条河流，相当于一条天然防线，不需要你再修建。

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

A 国总是有两个城市在河边，一个点是 $(0,0)$，一个点是 $(n,0)$，其余所有点的横坐标均在 $(0,n)$ 范围内，纵坐标均大于0。
A国有一个不在 $(0,0)$ 和 $(n,0)$ 的首都。$(0,0),(n,0)$ 和首都这三个城市是一定需要保护的。

上图中，A,B,C,D,E 点为 A 国城市，且目前都要保护，那么修建的防线就会是 A-B-C-D，花费也就是线段 AB 的长度+线段 BC 的长度+线段 CD 的长度,如果，这个时候撤销 B 点的保护，那么防线变成下图

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

inputFormat:
第一行三个整数 $n,x,y$ 分别表示河边城市和首都是 $(0,0),(n,0),(x,y)$。

第二行一个整数 $m$。

接下来 $m$ 行，每行两个整数 $a,b$ 表示 A 国的一个非首都非河边城市的坐标为 $(a,b)$。

再接下来一个整数 $q$，表示修改和询问总数。

接下来 $q$ 行每行要么形如 `1 u`，要么形如 `2`，分别表示撤销第 $u$ 个城市的保护和询问。

outputFormat: 对于每个询问输出一行一个实数 $v$，表示修建防线的花费，保留两位小数。

hint:
【数据范围】
对于 $30\%$ 的数据，$1\le m,q \le 1000$；
对于 $100\%$ 的数据，$1\le m \le 10^5$，$1\le q \le 2 \times 10^5$，$1 < n \le 10^4$。

所有点的坐标范围均在 $10^4$ 以内, 数据保证没有重点。

---

~~$\text{upd 2022.7.21}$：新增加一组 Hack 数据。~~ 该数据有误，已经被移除。


title: [HAOI2011] Problem b

description: 对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$，满足 $a \le x \le b$，$c \le y \le d$，且 $\gcd(x,y) = k$，$\gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。

inputFormat: 第一行一个整数 $n$，接下来 $n$ 行每行五个整数，分别表示 $a,b,c,d,k$。

outputFormat: 共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数。

hint: 对于 $100\%$ 的数据满足：$1 \le n,k \le 5 \times 10^4$，$1 \le a \le b \le 5 \times 10^4$，$1 \le c \le d \le 5 \times 10^4$。


title: [HAOI2011] Problem c

description:
给 $n$ 个人安排座位，先给每个人一个 $1\thicksim n$ 的编号，设第 $i$ 个人的编号为 $a_i$（不同人的编号可以相同）。

接着从第一个人开始，大家依次入座，第 $i$ 个人来了以后尝试坐到 $a_i$，如果 $a_i$ 被占据了，就尝试 $a_i+1$，$a_i+1$ 也被占据了的话就尝试 $a_i+2$……，如果一直尝试到第 $n$ 个都不行，该安排方案就不合法。

然而有 $m$ 个人的编号已经确定（他们或许贿赂了你的上司...），你只能安排剩下的人的编号，求有多少种合法的安排方案。

由于答案可能很大，只需输出其除以 $M$ 后的余数即可。

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

对于每组数据，第一行有三个整数，分别表示 $n$、$m$、$M$。

若 $m$ 不为 $0$，则接下来一行有 $m$ 对整数，$p_1$、$q_1$，$p_2$、$q_2$，...， $p_m$、$q_m$，其中第 $i$ 对整数 $p_i$、$q_i$ 表示第 $p_i$ 个人的编号必须为 $q_i$。

outputFormat: 对于每组数据输出一行，若是有解则输出 `YES`，后跟一个整数表示方案数 $\bmod M$，注意，`YES` 和数之间只有一个空格，否则输出 `NO`。

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

对于 $100\%$ 的数据，保证
- $1 \leq T \leq 10$。
- $1 \leq n \leq 300$， $0 \leq m \leq n$， $2 \leq M \leq 10^9$。
- $1 \leq p_i$、$q_i \leq n$。
- $p_i$ 互不相同。


title: 斐波那契数列（升级版）

background:
大家都知道，斐波那契数列是满足如下性质的一个数列：

- $f(1) = 1$
- $f(2) = 1$
- $f(n) = f(n-1) + f(n-2)$（$n > 2$ 且 $n$ 为整数）。

description: 请你求出第 $n$ 个斐波那契数列的数 $\bmod\,2^{31}$ 之后的值，并把它分解质因数。

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

outputFormat: 把第 $n$ 个斐波那契数列的数分解质因数。


title: [SHOI2001] 小狗散步

description:
Grant 喜欢带着他的小狗 Pandog 散步。Grant 以一定的速度沿着固定路线走，该路线可能自交。Pandog 喜欢游览沿途的景点，不过会在给定的  $N$ 个点和主人相遇。小狗和主人同时从  $(X_1,Y_1)$ 点出发，并同时在  $(X_n,Y_n)$ 点汇合。小狗的速度最快是 Grant 的两倍。当主人从一个点以直线走向另一个点时，Pandog 跑向一个它感兴趣的景点。Pandog 每次与主人相遇之前最多只去一个景点。

你现在的任务是：为 Pandog 寻找一条路线（有可能与主人的路线部分相同），使它能够游览最多的景点，并能够准时与主人在给定地点相遇或者汇合。

inputFormat:
第一行是两个整数  $N$ 和  $M$。

第二行的  $N$ 个坐标给出了 Grant 的散步路线，即 Pandog 和主人相遇地点。

第三行的  $M$ 个坐标给出了所有 Pandog 感兴趣的景点。

outputFormat:
输出小狗的移动路线。

第一行是经过的点数，第二行依次为经过的点的二维坐标。

hint: 对于所有数据，有  $1\le N,M\le 100$，所有输入的坐标均不相同，且绝对值不超过  $10^3$。


title: [SHOI2001] Panda的烦恼

description:
panda 是个数学怪人，他非常喜欢研究跟别人相反的事情。最近他正在研究筛法，众所周知，对一个范围内的整数，经过筛法处理以后，剩下的全部都是质数，不过 panda 对这些不感兴趣，他只对被筛掉的数感兴趣，他觉得在这些被筛掉的数中一定隐藏着重要的宇宙秘密，只是人们还没有发现罢了。

panda 还觉得如果只是单纯地从小到大筛的话，还不足够发现其中的奥秘，于是他决定对至多只包含某些质因数的数进行研究（比如说至多只包含质因数  $2,3$ 的数有  $2,3,4,6,8,9,\ldots$），他需要得到这些数中第  $k$ 小的数（ $k$ 是 panda 认为的宇宙系数），请你编个程序，帮助他找到这个数。

inputFormat:
第一行有两个整数  $n,k$， $n$ 代表质因数的个数， $k$ 代表那个宇宙系数。

第二行有  $n$ 个整数，代表这  $n$ 个质因数，设这些质因数组成的序列为  $p$。

outputFormat: 仅一行，即至多只包含这  $n$ 个质因数的数中第  $k$ 小的正整数，设这个答案为  $ans$。

hint:
#### 样例解释

前六个数分别是  $3,5,9,15,25,27$。

#### 数据范围及限制

对于所有数据，有  $1\le n\le 100$， $1\le k\le 10^5$， $p_i\in\text{prime}$， $p_i\le 10^3$， $p_i\not=p_j(i\not=j)$， $1\le ans\le 2\times 10^9$。


title: [SHOI2001] 化工厂装箱员

description:
118 号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有 $3$ 种不同的纯度，$A$：$100\%$，$B$：$1\%$，$C$：$0.01\%$，为了出售方便，必须把不同纯度的成品分开装箱，装箱员 grant 第 $1$ 次顺序从流水线上取 $10$ 个成品（如果一共不足 $10$ 个，则全部取出），以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持 $10$ 个成品（如果把剩下的全部取出不足 $10$ 个，则全部取出），如果所有的成品都装进了箱子，那么 grant 的任务就完成了。

由于装箱是件非常累的事情，grant 希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。

inputFormat:
第 $1$ 行为 $n$（$1\le n\le 100$），为成品的数量。

以后 $n$ 行，每行为一个大写字母 $\texttt A$，$\texttt B$ 或 $\texttt C$，表示成品的纯度。

outputFormat: 仅一行，为 grant 需要的最少的装箱次数。


title: [SHOI2001] 击鼓传花

description:
HC(Happy Child)小朋友最近经常在教室里跟同学一起玩击鼓传花的游戏，规则是第 $n$ 个拿到花的小朋友必须说出 $n!$ 最后一位非 0 的数字，如此循环游戏，如果谁讲错了就得罚唱一支歌曲。

经过几次游戏，HC 小朋友认为只要把前一个小朋友说得数字去乘以 $n$，说出得到的数的最后一位非 $0$ 的数字就可以了，可惜 HC 小朋友这次轮到了第 $15$ 个，结果被罚了唱歌(应该是 $8$，但是HC小朋友却说了$3$)。

HC 小朋友不希望这样的事情再次发生，所以希望你能编写一个程序，能够计算出 $n!$ 的最后一位非 $0$ 的数字。

outputFormat:
输出有 $5$ 行。

第 $i$ 行对应输入中第 $i$ 行的 $n$ 的阶乘的最后一位非 $0$ 的数字。


title: [SHOI2001] 排序工作量之新任务

description:
假设我们将序列中第 $i$ 件物品的参数定义为 $A_i$，那么排序就是指将 $A_1, \cdots ,A_n$ 从小到大排序。若 $i<j$ 且 $A_i>A_j$ ，则 $(i,j)$ 就为一个“逆序对”。SORT 公司是一个专门为用户提供排序服务的公司，他们的收费标准就是被要求排序物品的“逆序对”的个数，简称“逆序数”。

Grant 是这家公司的排序员，他想知道对于 $n$ 个参数都不同的物品组成的序列集合中，逆序对数为 $t$ 的物品有多少个，并试给出其中一个最小的物品序列。所谓最小，即若有两个物品序列 $(A_1,A_2,\cdots ,A_n)$，$(B_1,B_2,\cdots ,B_n)$，存在 $1 \le i \le n$，使得 $(A_1,A_2,\cdots ,A_{i-1})=(B_1,B_2,\cdots,B_{i-1})$ 且$A_i<B_i$。

inputFormat: 即两个整数 $n$和 $t(1 \le n \le 20,0 \le t \le \dfrac{n\cdot (n-1)}{2})$。

outputFormat:
第一行表示 $n$ 个参数都不通的物品组成的序列集合中，逆序数为 $t$ 的序列个数；

第二行是所求物品参数序列。假设 $n$ 个物品分别为 $1$ 到 $n$。


title: [SHOI2001] 三国围棋对抗赛

background: 中国邀请韩国，日本围棋队来参加三国围棋对抗赛，韩国，日本应邀各派了5位超一流高手来参赛，中国围棋队希望能赢得这场比赛，但是这10位高手实力不俗。不过中国队作为东道主，可以在对方选手安排好出场顺序后再决定队员的组成以及出场顺序，以得到最大的获胜概率。

description: 比赛规则如下：先抽签决定第1轮轮空的队，由不轮空的2支队的1号队员进行比赛，失利的队员被淘汰，以后每次由前一轮获胜的队员与前一轮轮空的队剩下的队员中序号最小的队员进行比赛，直到只剩下一个国家的队员为止，这个国家就获得了比赛的胜利。

inputFormat:
第1行为一个数n（5<=n<=15），中国队的候选人数。

接下来是n行，每行有10个数

第I+1行的10个数依次表示第I位中国选手对韩国1~5号，日本1~5号的胜率，胜率k（0<=k<=1）。

再接下来是5行，每行有5个数

第I+n+1行的第j个数表示韩国I号选手对日本j号选手的胜率。

outputFormat: 仅1行，为中国队的最大的获胜概率，保留6位小数。


title: [AHOI2012] 树屋阶梯

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

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

inputFormat: 一个正整数 $N$，表示阶梯的高度。

outputFormat: 一个正整数，表示搭建方法的个数。**注**：搭建方法的个数可能很大。


title: [AHOI2012] 信号塔

description: 在野外训练中，为了确保每位参加集训的成员安全，实时的掌握和收集周边环境和队员信息非常重要，集训队采用的方式是在训练所在地散布 $N$ 个小型传感器来收集并传递信息，这些传感器只与设在集训地中的信号塔进行通信，信号塔接收信号的覆盖范围是圆形，可以接收到所有分布在该集训区域内所有 $N$ 个小型传感器（包括在该圆形的边上）发出的信号。信号塔的功率与信号塔接收范围半径的大小成正比，因为是野外训练，只能使用事先储备好的蓄电设备，因此在可以收集所有传感器信息的基础上，还应使得信号塔的功率最小。小龙帮助教官确定了一种信号塔设置的方案，既可以收集到所有 $N$ 个传感器的信号，又可以保证这个信号塔的功率是最小的。同学们，你们知道，这个信号塔的信号收集半径有多大，它应该设置在何处吗?

inputFormat: 共 $N+1$ 行，第一行为正整数 $N$，表示队员个数。接下来 $N$ 行，每行两个实数用空格分开，分别是第 $i$ 个队员的坐标 $x_i$ 和 $y_i$ （$x_i,y_i$ 不超过双精度范围）。

outputFormat: 一行，共三个实数（中间用空格隔开），分别是信号塔的坐标，和信号塔覆盖的半径。

hint:
队员是否在边界上的判断应该符合他到圆心的距离与信号塔接受半径的差的绝对值小于 $10^{-6}$，最终结果保留 $2$ 位小数。

对于 $30\%$ 的数据，满足 $1\le N \le 10^4$
对于 $70\%$ 的数据，满足 $1\le N \le 2\times10^4$
对于 $100\%$ 的数据，满足 $1\le N \le 10^6$

本题存在 hack 数据，计 0 分。


title: [AHOI2012] 铁盘整理

description:
在训练中，一些臂力训练器材是少不了的，小龙在练习的时候发现举重器械上的铁盘放置的非常混乱，并没有按照从轻到重的顺序摆放，这样非常不利于循序渐进的锻炼。他打算利用一个非常省力气的办法来整理这些铁盘，即每次都拿起最上面的若干个圆盘并利用器械的力量上下翻转，这样翻转若干次以后，铁盘将会按照从小到大的顺序排列好。那么你能不能帮小龙确定，最少翻转几次就可以使铁盘按从小到大排序呢？

例如：下面的铁盘经过如图所示的以下几个步骤的翻转后变为从小到大排列。

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

inputFormat: 共两行。第一行为铁盘个数 $N$（$1 \leq N \leq 16$），第二行为 $N$ 个不同的正整数，分别为从上到下的铁盘的半径 $R$（$1 \leq R \leq 100$）。

outputFormat: 一个正整数，表示使铁盘从小到大有序需要的最少翻转次数。

tags: 启发式迭代加深搜索,IDA*


title: [AHOI2012] 收集资源

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

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


title: [NOIP2015 提高组] 斗地主 加强版

description:
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的 $A$ 到 $K$ 加上大小王的共 $54$ 张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：$3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{小王}<\text{大王}$，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 $n$ 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

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

**在此题中认为两个王不能组成对子牌**。

inputFormat:
第一行包含用空格隔开的 $2$ 个正整数 $T,n$，表示手牌的组数以及每组手牌的张数。

接下来 $T$ 组数据，每组数据 $n$ 行，每行一个非负整数对 $a_i,b_i$，表示一张牌，其中 $a_i$ 表示牌的数码，$b_i$ 表示牌的花色，中间用空格隔开。特别的，我们用 $1$ 来表示数码 $A$，$11$ 表示数码 $J$，$12$ 表示数码 $Q$，$13$ 表示数码 $K$；黑桃、红心、梅花、方片分别用 $1-4$ 来表示；小王的表示方法为 `0 1`，大王的表示方法为 `0 2`。

outputFormat: 共 $T$ 行，每行一个整数，表示打光第 $i$ 手牌的最少次数。

hint:
#### 样例 1 说明

共有 $1$ 组手牌，包含 $8$ 张牌：方片 $7$，方片 $8$，黑桃 $9$，方片 $10$，黑桃 $J$，黑桃 $5$，方片 $A$ 以及黑桃 $A$。可以通过打单顺子（方片 $7$，方片 $8$，黑桃 $9$，方片 $10$，黑桃 $J$），单张牌（黑桃 $5$）以及对子牌（黑桃 $A$ 以及方片 $A$）在 $3$ 次内打光。

#### 数据范围与提示

对于前 $20$ 个测试点， 我们约定手牌组数 $T$ 与张数 $n$ 的规模如下：

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

数据不保证所有的手牌都是随机生成的。


title: [AHOI2005] 病毒检测

description:
科学家们在 Samuel 星球上的探险仍在继续。非常幸运的，在 Samuel 星球的南极附近，探险机器人发现了一个巨大的冰湖！机器人在这个冰湖中搜集到了许多 RNA 片段运回了实验基地。

科学家们经过几个昼夜的研究，发现这些 RNA 片段中有许多是未知的病毒！

每个 RNA 片段都是由 `A`、`C`、`T`、`G` 组成的序列。科学家们也总结出了 Samuel 星球上的“病毒模版片段”。一个模版片段是由 `A`、`C`、`T`、`G` 的序列加上通配符 `*` 和 `?` 来表示。其中 `*` 的意思是可以匹配上 $0$ 个或任意多个字符，而 `?` 的意思是匹配上任意一个字母。

如果一个 RNA 片段能够和“病毒模版片段”相匹配，那么这个 RNA 片段就是未知的病毒。

例如，假设 “病毒模版片段”为 `A*G?C`。RNA 片段：`AGTC`，`AGTGTC` 都是未知的病毒，而 RNA 片段 `AGTGC` 则不是病毒。

由于，机器人搜集的这些 RNA 片段中除去病毒的其他部分都具有非常高的研究价值。所以科学家们希望能够分辨出其中哪些 RNA 片段不是病毒，并将不是病毒的 RNA 片段运回宇宙空间站继续进行研究。

科学家将这项任务交给了小联。现在请你为小联编写程序统计哪些 RNA 片段不是病毒。

inputFormat:
共 $N+2$ 行输入。

第一行有一个字符串，由 `A`、`C`、`T`、`G`、`*`、`?` 组成，表示“病毒模版片段”。“病毒模版片段”的长度不超过 $1000$。

第二行有一个整数 $N$，表示机器人搜集到的 RNA 片段的数目。

随后的 $N$ 行，每一行有一个字符串，由 `A`、`C`、`T`、`G` 组成，表示一个 RNA 片段。

outputFormat: 只有一行输出，为整数 $M$，即不是病毒的 RNA 片段的数目。

hint:
输入中的 RNA 片段 `AGTGC` 不是病毒。

对于所有数据，$0 < N < 500$。

特别的：

- 每个 RNA 片段的长度不超过 $500$；
- “病毒模版片段”和 RNA 片段的长度都至少为 $1$。


title: [AHOI2005] 穿越磁场

description:
探险机器人在Samuel星球上寻找一块奇特的矿石，然而此时它陷入了一片神秘的磁场区域，动弹不得。

探险空间站立刻扫描了这片区域，绘制出该区域的磁场分布平面图。这片区域中分布了N个磁场，每个磁场呈正方形，且边与坐标轴平行。

例如下图中，存在3个磁场，白点表示机器人的位置，黑点表示矿石的位置：

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

科学家们分析平面图，进一步发现：这些磁场为大小不一的正方形，可能相交，甚至覆盖，但是它们的边缘不会重合，顶点也不会重合。

例如下面的两种情形是不会出现的：

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

科学家们给探险机器人启动了磁力罩，这样它就可以在磁场中自由穿越了。

初始时，探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制，在穿越过程中机器人只能够水平或垂直移动，且不能够沿着磁场的边缘行动。

由于磁力罩的能量有限，科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中，探险机器人最少需要穿越两次磁场边缘。

现在小联请你编写程序，帮助科学家们设计探险机器人的路线，统计探险机器人最少需要穿越多少次磁场边缘。

inputFormat: 第一行有一个整数N，表示有N个磁场（1 < N < 100）。随后有N行，每行有三个整数X、Y、C（0 < X ,Y ,C < 10000），表示一个磁场左下角坐标为（X,Y），边长为C。接下来有一行，共有四个整数SX, SY, TX, TY，表示机器人初始坐标为（SX, SY），矿石坐标为（TX，TY）（其中，1 < SX, SY, TX, TY < 10000）。

outputFormat: 单行输出一个整数，表示机器人最少需要穿越多少次磁场边缘。


title: 计算器写作文

description:
众所周知，计算器可以拿来干很多它本不应该干的事情，比如弹琴。

小A发现了一个计算器的隐藏功能——写英语作文。

他在计算器上按一些数字，这些然后旋转 $180$ 度就是作文。

每个数字对应一两个字母

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

小 A 准备了一个单词表，选择其中的一些单词，按照一个顺序组成作文。这个作文是可以用计算器按出来的。比如单词表给 `ODD`、`EGG`，作文写成 `ODDEGG` 的话，那么要在计算器上按出 `993000`，这篇作文的得分就是 $993000$。

单词表的单词不能重复使用。如果单词表出现了多个一样的单词，每个单词最多都可以各使用一次。单词不可以被截断。

小 A 希望自己写出的作文得分最高。当然这个计算器是有位数限制，作文长度不能超过显示位数。

计算器不能显示前导零，但是你可以添加小数点。比如作文写成 `EGGODD` 的话，就得按出 $0.00993$，这个就是作文的得分，当然这得分太小了。

inputFormat:
第一行 $D$ 表示计算器位数。

第二行 $N$ 表示单词数。

接下来 $N$ 行，一行一个单词，保证可以转换为数字。

outputFormat: 一行，表示最大的分值。


title: [POI2008] SZK - Mirror trap

description:
King Byteasar's palace is haunted by a ghost. The spiteful claim it is the ghost of the late Byteasar's wife (who died recently in suspicious circumstances), for it takes great pleasure in looking at itself in the mirror, just as she did. No wonder that Byteasar would gladly get rid of this ghost!

Byteasar has decided to plant a special mirror trap in one of the palace's chambers. It is a closed, well lit room whose every interior wall is covered with mirror. Furthermore, in its every corner a laser gun or a laser detector can be set up. As soon as the ghost crosses one of the laser beams an alarm will go off, summoning Byteasar's ghost vanquishers team (as a royal team, they prefer not to be colloquially called 'ghost busters'), who will surely dispose of the ghost in no time.

The chamber, in which the mirror trap is being installed, is in the shape of a polygon whose consecutive sides are perpendicular. Moreover, the length of every side (measured in metres) is integral. Should a laser gun be installed in some corner, its beam has to be pointed along the bisector of the angle formed by the walls meeting in this corner (in a plane parallel to the floor surface). Obviously, if the laser beam encounters a mirror, it is reflected, obeying the regular reflection law: the angle which the incident ray makes with the normal is equal to the angle which the reflected ray makes to the same normal. This angle, as you may notice, is always 45 degrees due to the chamber's architecture. A beam cast along the bisector into a corner where a detector is placed, is completely absorbed by it. On the other hand, a beam cast along the bisector into corner without a detector (though possibly with a laser gun) is reflected back (by 180 degrees). In all the remaining cases the beam does not change its direction at all.

A maximum number of laser guns complemented with laser detectors should be placed in the room in such a way that each laser beam is eventually absorbed by some detector, no two laser beams are absorbed by the same detector and each detector absorbs some laser beam. Also, a laser gun and a detector may not be placed in the same corner.

An example of a mirror trap with the laser beam going from corner 1 to corner 7:

Write a programme that:

reads from the standard input the the mirror trap's shape description,
determines the way of setting up the maximum possible number of laser guns and detectors satisfying the aforementioned conditions,
writes out the result to the standard output.

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

inputFormat: 第一行给出一个数字N,代表有多少个点. 下面N行,用来描述点的坐标.其值在[-1000000,1000000]

outputFormat: 最多可放置多少对发射器和接收器

translation:
多边形相邻边垂直，边长为整数，边平行坐标轴。要在多边形的点上放一些激光发射器和接收器。满足下列要求：
1. 发射器和接收器不能放置在同一点；
2. 发射器发出激光可以沿壁反射，最终到达一个接收器；
3. 发射器只能沿角平分线发射激光。求：最多可放置多少对发射器和接收器？点数4<=n<=100000


title: [SCOI2008] 城堡

description:
在一个国家里，有 $n$ 个城市（编号为 $0$ 到 $n-1$）。这些城市之间有 $n$ 条双向道路相连（编号为 $0$ 到 $n-1$），其中编号为 $i$ 的道路连接了城市 $i$ 和城市 $r_i$（一条道路可以连接一个城市和它自身），长度为 $d_i$。$n$ 个城市中有 $m$ 个拥有自己城堡，可以抵御敌人侵略。如果没有城堡的城市遭受攻击，则离它最近的城堡将派兵前往救援。

你的任务是在不超过 $k$ 个没有城堡的城市中建立城堡，使得所有城市中“离最近城堡的距离”的最大值尽量小。换句话说，若令 $dist(c)$ 表示城市 $c$ 的最近城堡离它的距离，则你的任务是让 $\max\{dist(c)\}$ 尽量小。

输入数据保证存在方案使得对于每个城市，至少有一个城堡能够到达。

inputFormat: 输入第一行为三个正整数 $n, m, k$。第二行包含 $n$ 个整数 $r_0,r_1,\ldots,r_{n-1}$。第三行包含 $n$ 个整数 $d_0,d_1,\ldots,d_{n-1}$。第四行包含 $m$ 个各不相同的 $0$ 到 $n-1$ 之间的整数，分别为 $m$ 个城堡所在的城市编号。

outputFormat: 输出仅一行，包含一个整数，即 $\max\{dist(c)\}$ 的最小值。

hint: $100\%$ 的数据满足: $2\leq n\leq 50$，$1\leq d_i\leq 10^6$，$0\leq m\leq n-k$。


title: [USACO16DEC] Robotic Cow Herd P

description:
Bessie is hoping to fool Farmer John by building a herd of $K$ realistic robotic cows ($1 \leq K \leq 100,000$).

It turns out that building a robotic cow is somewhat complicated. There are $N$ ($1 \leq n \leq 100,000$) individual locations on the robot into which microcontrollers must be connected (so a single microcontroller must be connected at each location). For each of these locations, Bessie can select from a number of different models of microcontroller, each varying in cost.

For the herd of robotic cows to look convincing to Farmer John, no two robots should behave identically. Therefore, no two robots should have exactly the same set of microcontrollers. For any pair of robots, there should be at least one location at which the two robots use a different microcontroller model. It is guaranteed that there will always be enough different microcontroller models to satisfy this constraint.

Bessie wants to make her robotic herd as cheaply as possible. Help her determine the minimum possible cost to do this!

奶牛 Besiie 想要得罪一下农夫 John，为此她想造一个由K个仿真机械牛组成的牛群来戏弄 John （$1\le K \le 10^5$）

然而她发现想要造出一只机械牛是一件很复杂的事。在一只机械牛身上有 $N$（$1\le N \le 10^5$）个位置必须装上微型控制器。Bessie 可以选择不同型号的微型控制器装在每个位置上，每种型号有不同的花费。

为了让这群机械牛看上去不那么假，牛群中里面不能有两头相同的牛。也就是说，不能有哪两头牛身上的微型控制器是完全相同的。对于任意两头机机械牛来说，至少要有一个位置，在这个位置上这两头牛装了不同的微型控制器。因为美国科技很发达，所以 Bessie 总能找到足够型号的控制器来满足这个需求。

现在 Bessie 希望她的机械牛群造价尽量的便宜，因为剩下的钱她还要用来卡 $4$ 分 $35$ 秒出两船兵，她请你帮她计算一下最小花费。

inputFormat:
The first line of input contains $N$ and $K$ separated by a space.

The following $N$ lines contain a description of the different microcontroller models available for each location. The $i$th such line starts with $M_i$ ($1 \leq M_i \leq 10$), giving the number of models available for location $i$. This is followed by $M_i$ space separated integers $P_{i,j}$ giving the costs of these different models ($1 \le P_{i,j} \le 100,000,000$).

第一行：$N$ 和 $K$，以一个空格分开。

接下来 $N$ 行：以一个整数 $M_i$ 开头，表示这个位置可以装 $M_i$ 种微型控制器，接下来 $M_i$ 个整数 $P_i$，表示第 $i$ 个控制器的花费 $P_i\le 10^8$。

outputFormat:
Output a single line, giving the minimum cost to construct $K$ robots.

一行一个整数，最小花费

hint: 感谢 @ SakuraDance  提供翻译


title: [AHOI2005] 航线规划

description:
对 Samuel 星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了 Samuel 星球所在的星系——一个巨大的由千百万星球构成的 Samuel 星系。

星际空间站的 Samuel II 巨型计算机经过长期探测，已经锁定了 Samuel 星系中 $n$ 个星球的空间坐标，并对这些星球以 $1$ 至 $n$ 依次编号。

一些先遣飞船已经出发，在星球之间开辟探险航线。

探险航线是双向的，例如从 $1$ 号星球到 $3$ 号星球开辟探险航线，那么从 $3$ 号星球到 $1$ 号星球也可以使用这条航线。

例如下图所示：

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

在 $5$ 个星球之间，有 $5$ 条探险航线。

$A,B$ 两星球之间，如果某条航线不存在，就无法从 $A$ 星球抵达 $B$ 星球，我们则称这条航线为关键航线。

显然上图中，$1$ 号与 $5$ 号星球之间的关键航线有 $1$ 条：即为 $4\leftrightarrow5$ 航线。

然而，在宇宙中一些未知的磁暴和行星的冲撞，使得已有的某些航线被破坏，随着越来越多的航线被破坏，探险飞船又不能及时恢复这些航线，可见两个星球之间的关键航线会越来越多。

假设在上图中，航线 $4\leftrightarrow2$（从 $4$ 号星球到 $2$ 号星球）被破坏。此时，$1$ 号与 $5$ 号星球之间的关键航线就有 $3$ 条：$1 \leftrightarrow 3$，$3 \leftrightarrow 4$，$4 \leftrightarrow 5$。

小联的任务是，不断关注航线被破坏的情况，并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

inputFormat:
第一行有两个整数，分别表示星球个数 $n$ 和初始时的航线条数 $m$。

接下来 $m$ 行，每行有两个不相同的整数 $u, v$，表示星球 $u$ 和星球 $v$ 之间存在一条航线。

接下来有若干行，每行首先给出一个整数 $op$，表示一次操作的类型。

- 若 $op = 1$，则后接两个整数 $u, v$，表示询问当前 $u, v$ 两星球之间有多少关键航线。
- 若 $op = 0$，则后接两个整数 $u, v$，表示 $u, v$ 之间的航线被破坏。
- 若 $op = -1$，则表示输入结束，后面不再存在操作。

outputFormat: 对每个 $op = 1$ 的询问，输出一行一个整数表示关键航线数目。

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

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

- $1 \leq n \leq 3 \times 10^4$，$1 \leq m \leq 10^5$。
- $-1 \leq op \leq 1$，$1 \leq u, v \leq n$。
- 无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。
- 对于 $op = 0$ 的操作，保证操作前航线 $u \leftrightarrow v$ 存在。
- 询问与破坏航线的总次数不超过 $4 \times 10^4$。


title: [AHOI2005] 矿藏编码

description:
探险机器人在 Samuel 星球发现了一片广阔的矿藏区。在这个矿藏区中，有高耸的山峰，也有平坦的平地。为了方便考察，整个矿藏区被划分 个格子区域。

例如下图，就是一个 $K=2$ 即 $4 \times 4$ 的矿藏区：

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

其中黑色表示山峰，白色表示平地。

探险空间站已经将这片矿藏区的详细信息扫描并记录下来。由于矿藏区的面积实在太大，所以科学家们采用了一种特殊的编码方式记录。

- 如果这片矿藏区全部是平地，则编码为 `0`。
- 如果这片矿藏区全部是山峰，则编码为 `1`。
- 否则，将矿藏区均匀划分成 $4$ 份，如下 所示：
     ![](https://cdn.luogu.com.cn/upload/pic/1647.png)

依次对每份进行编码，得 $S_1,S_2,S_3,S_4$。该矿藏区的编码 $S$ 为 $2S_1S_2S_3S_4$。
例如上图中，矿藏区的编码为：`2021010210001`。

小联希望你能根据给定的编码统计出这片矿藏区一共有多少格子区域是平地。

inputFormat:
第一行有一个整数K，表示有矿藏区的规模为 $K$（$1 < K < 50$）。

第二行有一串编码，由  `0`、`1` 组成，长度不超过 $200$，表示该矿藏区的编码。

outputFormat: 单行输出一个整数，表示矿藏区中一共有多少格子是平地。


title: [AHOI2004] 奇怪的字符串

inputFormat: 输入文件中包含两个字符串X和Y。当中两字符串非0即1。序列长度均小于9999。

outputFormat: X和Y的最长公共子序列长度。


title: [AHOI2004] 数字迷阵

inputFormat: 每行有三个正整数，分别是i,j,m，其中i,j<=10^9,2<=m<=10^4。

outputFormat: 每行输出对应的第i行，第j列的那个正整数对m取模的结果。


title: [AHOI2004] 实验基地

inputFormat: 第一行有一个整数N(3<N<2000)，表示登陆地带的大小是2×N。随后的两行每一行有N个整数（其绝对值不超过10^6），表示对应的矩形土地的适用度评估值，各个整数之间用一个空格隔开。

outputFormat: 只有一行输出，为整数M，即所确定的实验基地的适用度。


title: [AHOI2004] 智能探险车

description:
在 ***Sanuel*** 星球上的科学探险活动是由名为 ***Smart*** 的智能探险车完成的。因为 ***Sanuel*** 星球远离地球，信号往返传送一次要耗费数小时，而且存在很高的误码率。因此科学家们无法在地球上对 ***Smart*** 探险车进行实时控制，绝大部分探险活动都是由该探险车通过分析环境要素、自主决策、自主完成的。

科学家们的探险车设计方案相对简单：

首先，总结出影响探险车决策的各种**决策因素**，譬如：天气（weather）、地形（landform）、探险车供电情况（energy）和已采集矿石数目（mine）等。

随后，将每一种**决策因素**分成两种主要**情况**。譬如，将天气分成晴朗（sunny）和大风（windy）；将探险车供电情况分成饱满（full）和匮乏（lack），等等。

再后，科学家们针对各种**决策因素**，分别列出每一种行为的决策条件。譬如，若影响采集矿石的决策因素有 $N=4$ 种，而采集矿石的决策条件如下：

| 决策条件 | Weather | Landform | Energy | Mine |
| :------: | :-----: | :------: | :----: | :--: |
|    1     |  sunny  |  Plain   |  full  | Few  |
|    2     |  sunny  | mountain |  full  | Many |
|    3     |  sunny  | mountain |  full  | Many |

探险车的行为及其决策条件都很多，为了提高探险车的决策速度，最后需要探险车上的智能归纳模块将每一种行为的各种决策条件总结成一条“决策模板”。

如上述采集矿石的各条决策条件可以总结为：

| 决策模板 | sunny |  *   | full |  *   |
| :------: | :---: | :--: | :--: | :--: |

其中，“*”表示该因素不影响探险车的行为决策。

显然，决策模板要能够涵盖科学家们列出的该行为的所有决策条件。同时，决策模板中也含有一些科学家们未列出的决策条件，因而探险车能够在科学家们没有给出的决策条件下也能够自动进行某种行为，因而具有一定的“智能性”。如，上述决策模板会导致探险车在以下决策条件下也会进行矿石的采集。

|            | Weather | Landform | Energy | Mine |
| :--------: | :-----: | :------: | :----: | :--: |
| 新决策条件 |  sunny  |  Plain   |  full  | Many |

但是，任何事物都存在着两个方面。如果给出的决策模板过于笼统就失去了决策意义，相当于决策不精确。如，以下决策模板虽然涵盖了科学家们列出的各种采集矿石决策条件，但是因为决策过于笼统而意义不大。

| 过于笼统的决策模板 |  *   |  *   | full |  *   |
| :----------------: | :--: | :--: | :--: | :--: |

因此，要求探险车的决策模板所使用的”*“尽可能少。

小可可负责领导开发探险车的智能归纳模块。请你编写程序帮助小可可完成任务。

inputFormat:
第一行有两个用一个空格隔开的正整数 $N$ 和 $M$ ，分别表示决策因素（$N \leq 100$）和某种行为的决策条件数目（$M \leq 1000$）。

接下来的 $M$ 行每行是由 $N$ 个单词构成的字符串，每个单词依次对应一种决策因素的情况，每行就表示一种决策条件。每行内的单词之间用一个空格隔开。

注意：每行的行首与行末都不存在多余的空白字符，单词仅仅由小写英文字母构成，长度不超过 10。

outputFormat: 只有一行，表示决策模板，由 $N$ 个单词或“*”构成，彼此间用一个空格隔开。要求行首与行末都不存在多余的空白字符。

samples:
4 3
sunny plain full many
sunny mountain full many
sunny mountain full few


title: [AHOI2004] DNA变异

outputFormat: 只有一行数字，表示DNA序列中的血缘序列对的总数。


title: 数颜色

background: 大样例可在页面底部「附件」中下载。

description:
小 C 的兔子不是雪白的，而是五彩缤纷的。每只兔子都有一种颜色，不同的兔子可能有 相同的颜色。小 C 把她标号从 1 到 $n$ 的 $n$ 只兔子排成长长的一排，来给他们喂胡萝卜吃。 排列完成后，第 $i$ 只兔子的颜色是 $a_i$。

俗话说得好，“萝卜青菜，各有所爱”。小 C 发现，不同颜色的兔子可能有对胡萝卜的 不同偏好。比如，银色的兔子最喜欢吃金色的胡萝卜，金色的兔子更喜欢吃胡萝卜叶子，而 绿色的兔子却喜欢吃酸一点的胡萝卜……为了满足兔子们的要求，小 C 十分苦恼。所以，为 了使得胡萝卜喂得更加准确，小 C 想知道在区间 $[l_j,r_j]$ 里有多少只颜色为 $c_j$ 的兔子。

不过，因为小 C 的兔子们都十分地活跃，它们不是很愿意待在一个固定的位置；与此同 时，小 C 也在根据她知道的信息来给兔子们调整位置。所以，有时编号为 $x_j$ 和 $x_j+1$ 的两 只兔子会交换位置。  小 C 被这一系列麻烦事给难住了。你能帮帮她吗？

inputFormat:
从标准输入中读入数据。 输入第 1 行两个正整数 $n$,$m$。

输入第 2 行 $n$ 个正整数，第 $i$ 个数表示第 $i$ 只兔子的颜色 $a_i$。

输入接下来 $m$ 行，每行为以下两种中的一种：

- “$1\ l_j\ r_j\ c_j$” ：询问在区间 $[l_j,r_j]$ 里有多少只颜色为 $c_j$ 的兔子；

- “$2\ x_j$”： $x_j$ 和 $x_j+1$ 两只兔子交换了位置。

outputFormat:
输出到标准输出中。

对于每个 1 操作，输出一行一个正整数，表示你对于这个询问的答案。

hint:
【样例 1 说明】

前两个 1 操作和后两个 1 操作对应相同；在第三次的 2 操作后，3 号兔子和 4 号兔子

交换了位置，序列变为 1 2 2 3 3 3。

【数据范围与约定】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解 决一部分测试数据。 对于所有测试点，有 $1 \le l_j < r_j \le n,1 \le x_j < n$。 每个测试点的数据规模及特点如下表：

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

特殊性质 1：保证对于所有操作 1，有 $|r_j - l_j| \le 20$ 或 $|r_j - l_j| \le n - 20$。

特殊性质 2：保证不会有两只相同颜色的兔子。


title: 分组

background: 大样例可在页面底部「附件」中下载。

description:
小 C 在了解了她所需要的信息之后，让兔子们调整到了恰当的位置。小 C 准备给兔子 们分成若干个小组来喂恰当的胡萝卜给兔子们吃。

此时， $n$ 只兔子按一定顺序排成一排，第 $i$ 只兔子的颜色是 $a_i$ 。由于顺序已经是被 调整好了的，所以每个小组都应当是序列上连续的一段。

在分组前，小 C 发现了一个规律：有些兔子会两两发生矛盾。并且，两只兔子会发生矛 盾，当且仅当代表他们的颜色的数值之和为一个正整数的平方。比如，1 色兔子和 2 色兔子 不会发生矛盾，因为 3 不是任何一个正整数的平方；而 1 色兔子却会和 3 色兔子发生矛盾， 因为 $4 = 2^2$。

小 C 认为，只要一个小组内的矛盾不要过大就行。因此，小 C 定义了一个小组的矛盾 值 $k$ ，表示在这个小组里，至少需要将这个组再一次分成 $k$ 个小团体；每个小团体并不需 要是序列上连续的一段，但是需要使得每个小团体内任意两只兔子之间都不会发生矛盾。

小 C 要求，矛盾值最大的小组的矛盾值 $k$ 不超过 $K$ 就可以了。当然，这样的分组方 法可能会有很多个；为了使得分组变得更加和谐，小 C 想知道，在保证分组数量最少的情况 下，字典序最小的方案是什么。你能帮帮她吗？

字典序最小的方案是指，按顺序排列分组的间隔位置，即所有存在兔子 $i$ 和 $i + 1$ 在 不同组的位置 $i$，和其它所有相同分组组数相同的可行方案相比总有第一个不同的位置比其 它方案小的方案。

inputFormat:
从标准输入中读入数据。

输入第 1 行两个正整数 $n,K$。

输入第 2 行 $n$ 个正整数，第 $i$ 个数表示第 $i$ 只兔子的颜色 $a_i$。

outputFormat:
输出到标准输出中。

输出第 1 行一个正整数 $m$，为你至少需要将兔子分为多少个小组。

输出第 2 行$m-1$个从小到大的排列的正整数，第 $i$ 个数 $s_i$ 表示 $s_i$ 和 $s_i + 1$ 在 你的方案里被分到了两个小组。如果 $m = 1$，那么请输出一个空行。

hint:
【样例 1 解释】

如果将五只兔子全部分到同一个小组的话，那么 (1, 3) (3, 6) (6, 10) (10, 15) (1, 15) 均 不能分到同一个小团体；因为最多分成两个小团体，所以为了满足前 4 对限制，只能分为 {{1, 6, 15}, {3, 10}}，但此时不满足 (1, 15) ，所以不存在一种组数为 1 的方案满足全部限制。

如果将五只兔子分为两个小组的话，一种字典序最小的可行的分组方案是 {1}, {3, 15, 10, 6}，此时第二组内的小团体数量不超过 2 的一种分法是 {{3, 10}, {15, 6}}。

【数据范围】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解 决一部分测试数据。

每个测试点的数据规模及特点如下表：

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

特殊性质 1：保证最优分组方案唯一。

特殊性质 2：保证不会有两只相同颜色的兔子。


title: [AHOI2001] 质数和分解

description:
任何大于 $1$ 的自然数 $n$ 都可以写成若干个大于等于 $2$ 且小于等于 $n$ 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如，$9$ 的质数和表达式就有四种本质不同的形式：

$9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7$ 。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数 $n$ 可以写成多少种本质不同的质数和表达式。

inputFormat: 文件中的每一行存放一个自然数 $n(2 \leq n \leq 200)$ 。

outputFormat: 依次输出每一个自然数 $n$ 的本质不同的质数和表达式的数目。


title: [AHOI2001] 彩票摇奖

description:
为了丰富人民群众的生活、支持某些社会公益事业，北塔市设置了一项彩票。该彩票的规则是：

1. 每张彩票上印有 $7$ 个各不相同的号码，且这些号码的取值范围为 $1\sim33$。
2. 每次在兑奖前都会公布一个由七个各不相同的号码构成的中奖号码。
3. 共设置 $7$ 个奖项，特等奖和一等奖至六等奖。

兑奖规则如下：
- 特等奖：要求彩票上 $7$ 个号码都出现在中奖号码中。
- 一等奖：要求彩票上有 $6$ 个号码出现在中奖号码中。
- 二等奖：要求彩票上有 $5$ 个号码出现在中奖号码中。
- 三等奖：要求彩票上有 $4$ 个号码出现在中奖号码中。
- 四等奖：要求彩票上有 $3$ 个号码出现在中奖号码中。
- 五等奖：要求彩票上有 $2$ 个号码出现在中奖号码中。
- 六等奖：要求彩票上有 $1$ 个号码出现在中奖号码中。

注：兑奖时并不考虑彩票上的号码和中奖号码中的各个号码出现的位置。例如，中奖号码为 $23\ 31\ 1\ 14\ 19\ 17\ 18$，则彩票 $12\ 8\ 9\ 23\ 1\ 16\ 7$ 由于其中有两个号码（$23$ 和 $1$）出现在中奖号码中，所以该彩票中了五等奖。

现已知中奖号码和小明买的若干张彩票的号码，请你写一个程序帮助小明判断他买的彩票的中奖情况。

inputFormat:
输入的第一行只有一个自然数 $n$，表示小明买的彩票张数；

第二行存放了 $7$ 个介于 $1$ 和 $33$ 之间的自然数，表示中奖号码；

在随后的 $n$ 行中每行都有 $7$ 个介于 $1$ 和 $33$ 之间的自然数，分别表示小明所买的 $n$ 张彩票。

outputFormat: 依次输出小明所买的彩票的中奖情况（中奖的张数），首先输出特等奖的中奖张数，然后依次输出一等奖至六等奖的中奖张数。

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

对于 $100\%$ 的数据，保证 $1 \leq n\lt1000$。


title: [AHOI2001] 华夏60战斗机

description:
华夏 60 超音速战斗机是当今世界上机动性能最先进的战斗机。战斗过程中的一个关键问题是如何在最短的时间内使飞机从当前的飞行高度和速度爬升/俯冲到指定的高度并达到指定速度，以便占据有利的战斗位置。

现假定只允许华夏 60 执行以下三种基本飞行动作，并且只能在完成了一个基本动作的情况下再去执行另一个基本飞行动作。这样华夏 60 的飞行可以表示成由这三种基本飞行动作组成的动作序列。

(1) 维持原速做恒速爬升飞行，直至飞行高度提高 ∆h 英尺；

(2) 水平加速飞直至速度提高 1 马赫(1 马赫≈1200 公里/小时)；

(3) 垂直俯冲飞行 ∆h 英尺，飞行速度会提高 1 马赫。

同时假定飞机的初始飞行速度和执行每个基本飞行动作初始时刻的飞行速度都是 1 马赫的整数倍，且不超过 6 马赫；初始飞行高度和执行每个基本飞行动作初始时刻的飞行高度都为 ∆h 英尺( ∆h 是整数)的整数倍。

实验研究表明：在不同高度 H 和不同的初始速度V 完成上述的三种基本飞行动作所需的时间也是各不相同的。表 1~表 3 给出了 ∆ h = 15000英尺和最大飞行高度 = 75000

H m 英尺时完成这三种基本飞行动作所需的时间。

根据表 1~表 3 的数据，欲使华夏 60 战斗机从 H = 0 英尺、V = 1马赫的飞行状态达到 H = 75000 英尺、V = 6 马赫的飞行状态的最短飞行时间是79 秒，相应的飞行动作序列是：

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

(1) 恒速爬升飞行至 H = 15000英尺，V = 1马赫状态；

(2) 连续做两次水平加速飞行至 H = 15000英尺，V = 3马赫状态；

(3) 连续做四次恒速爬升飞行至 H = 75000 英尺，V = 3马赫状态；

(4) 水平加速飞行至 H = 75000 英尺，V = 4马赫状态；

(5) 连续做两次垂直俯冲飞行至 H = 45000 英尺，V = 6 马赫状态；

(6) 连续做两次恒速爬升飞行至 H = 75000 英尺，V = 6 马赫状态。

现在小明驾驶华夏 60 战斗机以V1马赫的速度飞行于 H1英尺高度，中队长发出了让他以V2 马赫的速度飞行于 H 2 英尺高度的指令。请你编写程序帮小明决策一下如何飞行才能花费最少的时间执行完中队长下达的命令。

outputFormat:
输出信息用两行来存放。第一行存放你求出的最优方案所需的时间。

第二行存放该最优方案的动作序列(以 R 表示恒速爬升飞行，A 表示

水平加速飞行，D 表示垂直俯冲飞行)。第二行中不允许出现多余的

字符(包括空白字符)。


title: [AHOI2001] 团体操队形

description:
有 $n$ 个团体操队员编号分别为 $1\sim n$ 。其队形(分连续队形和梅花桩队形)可以按行排列或者按列排列，按行(列)排列时每行(列)有 $r$ 个位置。

例1：$n=16$，$r=6$，连续队形按行排列。
|1|2|3|4|5|6|
|:-:|:-:|:-:|-|-|-|
|**7**|**8**|**9**|**10**|**11**|**12**|
|**13**|**14**|**15**|**16**|

例2：$n=16$，$r=3$，连续队形按列排列。
|  1  |  4  |  7  |  10  |  13  |16|
| :-: | :-: | :-: |  :-: |  :-: |- |
|**2**|**5**|**8**|**11**|**14**|
|**3**|**6**|**9**|**12**|**15**|

例3：$n=16$，$r=7$，梅花桩队形按行排列。
|  1   |      |  2   |      |  3   |      |  4   |
| :-:  | :-:  | :-:  | :-:  | :-:  | :-:  | :-:  |
|      |**5** |      |**6** |      |**7** |      |
|**8** |      | **9**|      |**10**|      |**11**|
|      |**12**|      |**13**|      |**14**|      |
|**15**|      |**16**|      |      |      |      |

例4：$n=16$，$r=5$，梅花桩队形按列排列。
|  1  |     |  6  |      |  11  |      |16 |
| :-: | :-: | :-: | :-:  | :-:  | :-:  |:-:|
|     |**4**|     |**9** |      |**14**|   |
|**2**|     |**7**|      |**12**|      |   |
|     |**5**|     |**10**|      |**15**|   |
|**3**|     |**8**|      |**13**|      |   |

现请你编写程序指出编号为 $m$ 的团体操队员所处位置的行号和列号。

inputFormat:
**本题有多组数据**
第一行只有一个自然数 $k$ ，表明随后的 $k$ 行每行都是一组数据。
接下来 $k$ 行，每行都有五个整数，分别表示队伍里的人数、队形代号（$1$表示连续队形，而$2$表示梅花桩队形）、排列方式（$1$表示按**行**排列，而$2$表示按**列**排列）、每行(列)的位置数、和询问位置的队员的编号

outputFormat: 输出 $2k$ 个整数，第 $i$ 对整数表示第 $i$ 组询问的行编号和列编号（不用换行）


title: [AHOI2001] 多项式乘法

description:
请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定：

1. 代数多项式表达式中只涉及一个代数符号 `a`；
2. 保证输入的「含乘法运算的代数多项式」有且仅有一个「代数多项式」与「代数多项式」的乘法。形式化地讲，每一个测试点的输入数据中，一定有且仅有一行 `(...)*(...)`，其中 `...` 为不含乘法运算的代数多项式。
3. 一个「不含乘法运算的代数多项式」会被写作 `XXXa^YYY+XXXa^YYY+XXXa^YYY+...+XXX`（代表 $\text{XXX}a ^ \text{YYY} + \text{XXX}a ^ \text{YYY} + \text{XXX}a ^ \text{YYY} + \cdots + \text{XXX}$），其中 `XXX`、`YYY` 均为正整数，且保证除第一项外每一项的 `YYY` 比上一项的 `YYY` 少 $1$。例如，一个合法的「不含乘法运算的代数多项式」为 `142a^4+9a^3+4a^2+1a^1+3`。

> 对于约定 3，原题目给予了这样一个表述：常数项以外的各项都是 $xa^y$ 的形式，写作 `xa^y`，其中 $x$ 为该项的系数，而 $y$ 是该项的指数。$x = 1$ 时，不得简写成 `a^y`，应写成 `1a^y`。而 $y = 1$ 时，不得简写成 `xa`，应写成 `xa^1`。

inputFormat:
输入仅有一行字符串，代表给定的「含乘法运算的代数多项式」。

其格式为：`(...)*(...)`，其中 `...` 为不含乘法运算的代数多项式。对于「不含乘法运算的代数多项式」的约束，请参考题目描述。

outputFormat:
输出一行一个字符串，代表答案。

答案要求指数大的项不能出现在指数小的项之后，指数相同的项必须合并同类项。**不允许出现不必要的空白字符**。输出中不允许有括号。

hint:
关于数据范围以及数据若干格式的说明：

* 系数范围和指数范围均为 $[0,30]$。


title: [AHOI2001] 有限自动机的测试

description:
在数字系统的诸多领域(如工业系统离散事件控制、数字电路、程序的

语法分析等实际应用)中，有限自动机是用来抽象地表示系统行为的一种工

具。实际上，有限自动机是把系统表示成若干种可能的状态。在一定的外

部条件(称作输入)下，系统的状态会发生变化，同时系统也有相应的输出。

为了直观地表示，可以把这些状态画成小圆圈，同时每个状态都有一个不含空白字符的

字符串名字。状态间的变化可以画成弧，同时把状态发生变化的条件和发生变化时的输出在

弧上标出(如下图所示)。

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

有限自动机在每个状态下的输入、输出都是一个固定长度的二进制数串。但是在弧上标出的输入条件除了 0 和 1之外还有一个符号 X 。符号 X 表明该位既可以是 0 也可以是 1。当外部输入满足弧上所标的输入条件，有限自动机就会从当前状态转变到该弧所指向的那个状态。例如当前状态是 S1，输入是“01”(或“11”)，这时有限自动机就会转变成状态 S2，同时输出“10” 。在一个输入序列的作用下，有限自动机就会从一个状态转移到另一个

状态，不断地变化所处的状态，与此同时会产生一个输出序列。对有限自动机进行测试就是要找出一种叫做UIO 的输入序列。状态 s 的UIO 序列可以使状态 s 在该输入序列作用下的输出序列不同于任何其他状态在该序列作用下的输出序列。作为黑箱测试(不涉及内部结构，即看不见内部结构)的一种方法，UIO 序列只考察输出序列，而不考虑其他因素。

例如，序列长度为 1 的输入序列“01”就同时是状态 S1、 S2和 S3的UIO 序列。因为状态 S1在输入“01”作用下的输出是“10” ， 状态 S2在输入“01”作用下的输出是“01”, 状态 S3在输入“01”作用下的输出是“00” 。一般而言，同一个有限自动机不同状态的UIO 序列可以各不相同。实践表明，并不是所有有限自动机的任何一个状态都存在着UIO 序列。同时任何一个状态的UIO 序列经过任意拓展(即延长序列长度)仍然是该状态

的UIO 序列。通常我们特指某状态的最短UIO 序列为该状态的UIO 序列。现在请你编写程序确定有限自动机中存在着UIO 序列的状态数，同时求出这些存在着UIO 序列的那些状态的最短UIO 序列的序列长度最大值。

outputFormat: 输出两个数据，中间用空白字符隔开。第一个数据表示该有限自动机中存在UIO 序列的状态数；第二个数据表示存在着UIO 序列的那些状态的最短UIO 序列的序列长度最大值。


title: [AHOI2002] 数的朗读

description:
春游时小可可结识了刚回国定居的 Sealock。但是 Sealock 在海外出生，

回国后才开始学习汉语。数的朗读成为 Sealock 的一个难题，小可可下决心

教会 Sealock 如何朗读绝对值小于 10 亿的数。

小可可知道汉语中有如下的读数规则：

⑴首先读符号位， 然后读整数部分， 整数部分之后可能出现小数点， 如果有

小数部分则小数点一定出现、并且读出小数点之后读小数部分；

⑵符号位的读法是：

(2.1)正数，不论正号“+”是否出现，都不必读出符号位；

(2.2)负数的最左边的符号是“-”， 读成“ 负” (以“ F” 来表示“负” )；

⑶整数部分的读法是：

蚌埠， 2002.4.20 AH02SGOI11A1.doc 第1页

2002 年安徽省青少年信息学(计算机)竞赛网上同步赛暨 SGOI 第十一次友谊赛 一试试题

(3.1)如果整数部分不存在或者整数部分全是零则直接读成“零” (以“ 0”

来表示“零” )；

(3.2)否则从整数部分中最左边的非零数字开始读起， 然后以十、 百、 千、

万、亿(分别以“ S”、“ B”、“ Q”、“ W”、“ Y”来表示)等数量单位来拼读整

数部分；

⑷整数部分中：

(4.1)每一个非零数字都必须结合各个相应的数量单位读出来；

(4.2)每一段连续的“零” 只能读成一个“零”， 但是某一段连续的“零”的左侧或者右侧不存在非零数字(这里只考虑整数部分)则这一段“零” 不应该读出来；

⑸如果有小数部分，则首先读“点”(以“ D”来表示“点”)，然后从左至右顺序地读出各个小数位。 在读小数部分的时候不可以使用十、 百、 千、 万、亿等数量单位； 但是小数部分的每一个数字都需要读出来， 连续的零不可以读成一个“零”，而应该分别读出；

⑹如果数中有小数点而没有小数部分，则不应该把小数点读出来。

例如， -0020030004.567 应该读成“ F2Q03W04D567”， 000.89 应该读成“ 0D89”。

请你编写程序帮助小可可把给定的数正确地读出来。

inputFormat:
文件中以一行的形式存放了一个数(不超过 50 个字符)，其绝对值

小于 10 亿。

outputFormat: 以一行的形式输出这个数的正确读法。


title: [AHOI2002] Kitty猫基因编码

description:
小可可选修了基础生物基因学。教授告诉大家 Super Samuel 星球上 Kitty猫的基因的长度都是 2 的正整数次幂 )， 全是由两种不同的基因单元组成的。 这两种不同的基因单元分别记成 0 和 1，于是 Kitty 猫基因可以写成一个 01 串表达式 。

为了便于分析和降低数据存储量，教授发明了 ABC 编码规则。该编码规则是不断地按照

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

对 Kitty 猫基因 01 串表达式 进行改写， 直至最终被改写成只含有字符 “ A”、“ B”、“ C”的符号串。

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

请你编写程序帮助小可可求出 Kitty 猫基因的 ABC 编码以协助教授开展科研工作。

inputFormat: 文件中以一行的形式存放了一个 Kitty 猫基因的 01 串表达式。

outputFormat: 以一行的形式输出这个 Kitty 猫基因的 ABC 编码。

hint: 给出的01字符串长度$Len\leq 256$


title: [AHOI2002] 黑白图像压缩

description:
选修基础生物基因学的时候， 小可可在家里做了一次图像学试验。 她知道：整个图像其实就是若干个图像点(称作像素)的序列，假定序列中像素的个数总是 8 的倍数， 于是每八个像素可以转换成一个叫做字节的数， 从而这个表示图像的像素序列就被转换成了字节的序列。

所谓的字节就是一个八位的二进制数(当然，为了便于书写，人们经常用它的十进制形式来表示)。这八个像素从前向后依次对应于字节从高位到低位的八个位， 用 0 来表示白色像素、 1 来表示黑色像素。 这种表示方法叫做位图法。 例如字节序列 210、 0、255 表示了 8\*3=24 个像素， 由于对应的二进制形式是 11010010、 00000000、11111111， 所以这 24 个像素的颜色依次是黑、 黑、 白、 黑、 白、 白、 黑、 白、白、白、白、白、白、白、白、白、黑、黑、黑、黑、黑、黑、黑、黑。

小可可想： 其实图像中存在着很多连续的同色像素段， 也许换一种方式表达图像能够减少图像的数据量。 她的思路是： 把像素按照颜色分成若干个片段， 同一个片段中各像素颜色相同， 且连续的同色像素都在同一个片段中。同时已知每个片段的最大长度小于 128。

每一个像素片段都是用一个二进制字节量来表示， 最高位表示片段中像素的颜色， 而低七位表示片段中像素的数目。注意：不存在长度为 0 的像素片段。这种表示法叫做像素片段法。

例如位图表示法的字节序列 210、 0、 255 对应的像素序列可以分成七个片段，分别是： 11、 0、 1、 00、 1、 000000000、 11111111。如果用像素片段法来表示的话，二进制字节序列应该写成 10000010、 00000001、 10000001、00000010、 10000001、 00001001、 10001000， 而其对应于十进制字节序列就是 130、 1、 129、 2、 129、 9、 136。

像素片段法是否能有效地减少图像的数据存储量呢？小可可不知道如何用数学的方法加以证明， 于是决心对手头上的图像做些试验， 看看该方法是否真的有效。 请你编写程序完成图像信息的转换， 以协助小可可完成这项试验。

inputFormat: 文件中以一行的形式存放了一个图像的信息。第一个数是正整数 $n$ ，表明该图像有 $n$ 个像素。随后有 $\frac{n}{8}$ 个十进制形式的字节量，表示该图像的位图信息。相邻数之间用一个空白字符隔开。

outputFormat:
以一行的形式输出以像素片段表示法表示的图像信息，各个数都以

十进制的形式出现，相邻数之间用一个空白字符隔开。

hint: $1\leq n\leq 8\times 10^4$。


title: [AHOI2002] 芝麻开门

description:
周末小可可参加智力大冲浪活动，经过努力终于来到最后一关“芝麻开门”。门上的电子显示屏写着这么一段话：如果你能把 $n^k$ 的所有正整数因子的和正确地写在门上，并念一声“芝麻开门”，门就能够自由打开。

例如：$n=2$，$k=3$，则 $n^k=8$，它的正因子有 $1,2,4,8$，如果小可可把它们的和 $15$ 写在门上，然后念一声“芝麻开门”，门就能够自动打开。

已知门上的 $n,k$ 都是每过一段时间就会变化一次，请你编写程序协助小可可在规定的时间内求出答案，从而获得智力大冲浪的最终大奖。

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

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


title: [AHOI2002] 网络传输

description:
在计算机网络中所有数据都是以二进制形式来传输的。但是在进行较大数据的传输时，直接使用该数的二进制形式加以传输则往往传输的位数过多。譬如要传输 $1024$ 就需要 $11$ 位二进制数。于是小可可提出了一种数据优化传输的设想，并打算对这一设想进行试验。

该设想是：正整数的所有方幂以及任意多个互不相等的 $k$ 的方幂之和排成一个递增数列 $\{a(k)n\}$，例如当 $k=3$ 时，$\{a(k)n\}$ 的前 $7$ 项为 $1(=3^0)$ 、 $3(=3^1)$ 、 $4(=3^0+3^1)$ 、 $9(=3^2)$ 、 $10(=3^0+3^2)$ 、 $12(=3^1+3^2)$ 、 $13(=3^0+3^1+3^2)$。

如果数 $d$ 是数列 $\{a(k)n\}$ 中的第 $p$ 项，则可以通过传送 $k$ 和 $p$ 这两个数来表示数 $d$。由于 $k$ 和 $p$ 这两个相对很小的数就可以表达出很大的数，因而理论上可以减少网络传输的位数。

小可可现在请你编写程序把接收到的数 $k$ 和 $p$ 所代表的数 $d$ 计算出来。

inputFormat:
文件中以一行的形式存放了两个正整数 $k$ 和 $p$，$1<k \le 1024$，
$1 \le p \le 1024$。

outputFormat: 以一行的形式输出问题的解（解的位数不超过 $50$ 位）。


title: [AHOI2002] 哈利·波特与魔法石

inputFormat:
文件中第一行有七个数，分别是 S1、 S2 、 …、 S7 ；第二行有两个数，依次分别是起点城市 i 和终点城市 j ；第三行有一个正整数 c ，c<=10000， 表示随后的 c 行中每行存放了一对能直接通达的城市的信息。 能直接通达的城市的信息由三个数组成， 依次分别是两个城市的编号和这两个城市之间的地形。城市的编号都是不超过 100 的正整

数， 但是各个城市的编号未必连续。 文件里同一行中相邻的两个数都是用一个空白字符隔开的。

outputFormat: 以一行的形式输出起点城市i 与终点城市 j 之间的最快路线所需要的时间。


title: [AHOI2002] Kitty猫基因突变

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

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

outputFormat: 以一行的形式输出评价效果最好的突变方案的评价指标。


title: [AHOI2002] 黑白瓷砖

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

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

inputFormat: 一行，一个正整数 $n$，$n \leq 20$ 。

outputFormat: 以一行的形式输出问题的解 $s$ (解的位数不超过 $200$ 位)。


title: [SCOI2009] 生日礼物

description:
小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。

小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。

inputFormat: 第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。接下来K行，每行第一个数为Ti，表示第i种彩珠的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的位置。

outputFormat: 输出应包含一行，为最短彩带长度。

hint:
【样例说明】

有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。

【数据规模】

对于50%的数据， N≤10000；

对于80%的数据， N≤800000；

对于100%的数据，1≤N≤1000000，1≤K≤60，$0≤$珠子位置$<2^{31}$。

$\sum T_i =n$


title: [SCOI2009] 骰子的学问

description:
小鱼儿是个数学天才。一天晚上他研究一个和字符串有关的penney-ante游戏。游戏的规则如下：

1．有两个玩家，开始时每人选择一个长度相同的字符串；

2．一个字符生成器不断的随机生成字母添加到字符串S的末尾，S初始为空串；

3．如果S包含了某个玩家选择的字符串则游戏结束，该玩家获胜。

假设玩家1和玩家2分别选择了两个字符串A和B，如果玩家1可以以较大概率战胜玩家2，我们记作A>B。 咋一看来，小鱼儿觉得如果A>B且B>C则A>C。可事实恰好相反，存在字符串A, B, C使得A>B, B>C, C>A。

小鱼儿被这种戏的一个反常现象所吸引，通过查阅资料，他了解到这种现象被称为“非传递性悖论”，在许多非完全信息游戏（比如军棋）中，经常会有这样的例子。可是它到底是如何产生的呢？小鱼儿决定设计一种游戏，从中可以容易的找到非传递的例子，以便更清楚的认识“非传递性”。当然，这样的游戏越简单道理越深刻，于是小鱼儿想起了最简单的掷骰子游戏……

这个游戏是这样的，假设有n个骰子D1~Dn，每个骰子有m个面。每个面上标有一个1~n×m的正整数，并且所有骰子的所有n×m个面上的数字各不相同。满足这条编号要求，并且每个面被随到的概率相等的，这样的n个骰子称为一组“好骰子”。游戏开始时，两个玩家分别选两个骰子Di和Dj，各掷一次来比较掷出来那一面的数值，数大的获胜。

小鱼儿请你帮忙设计一组“好骰子”，使得对任意一个骰子Di，它总能战胜Dai。此处战胜是指选择前者的玩家获胜的概率超过1/2；a1~an为输入的1~n的正整数。

inputFormat: 第一行为两个整数n, m。第二行有n个整数，为a1，a2, …, an。

outputFormat:
包含n行，每行m个1~n×m的正整数，各不相同，以空格分开。

如果有多解，输出任意一组解；如果无解，输出一个整数0。

hint:
30%的数据满足n, m≤10

100%的数据满足3≤n, m≤200

感谢 @cn：苏卿念 提供spj


title: [SCOI2009] 围豆豆

description:
是不是平时在手机里玩吃豆豆游戏玩腻了呢？最近MOKIA手机上推出了一种新的围豆豆游戏，大家一起来试一试吧。

游戏的规则非常简单，在一个N×M的矩阵方格内分布着D颗豆子，每颗豆有不同的分值Vi。游戏者可以选择任意一个方格作为起始格，每次移动可以随意的走到相邻的四个格子，直到最终又回到起始格。最终游戏者的得分为所有被路径围住的豆豆的分值总和减去游戏者移动的步数。矩阵中某些格子内设有障碍物，任何时刻游戏者不能进入包含障碍物或豆子的格子。游戏者可能的最低得分为0，即什么都不做。

注意路径包围的概念，即某一颗豆在路径所形成的多边形（可能是含自交的复杂多边形）的内部。下面有两个例子：

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

第一个例子中，豆在路径围成的矩形内部，所以豆被围住了。第二个例子中，虽然路径经过了豆的周围的8个格子，但是路径形成的多边形内部并不包含豆，所以没有围住豆子。

布布最近迷上了这款游戏，但是怎么玩都拿不了高分。聪明的你决定写一个程序来帮助他顺利通关。

inputFormat:
第一行两个整数N和M，为矩阵的边长。

第二行一个整数D，为豆子的总个数。

第三行包含D个整数V1到VD，分别为每颗豆子的分值。

接着N行有一个N×M的字符矩阵来描述游戏矩阵状态，0表示空格，#表示障碍物。而数字1到9分别表示对应编号的豆子。

outputFormat: 仅包含一个整数，为最高可能获得的分值。

hint:
50%的数据满足1≤D≤3。

100%的数据满足1≤D≤9，1≤N, M≤10，-10000≤Vi≤10000。


title: 地铁间谍

description:
特工玛利亚被送到 S 市执行一个特别危险的任务。她需要利用地铁完成他的任务，S 市的地铁只有一条线路运行，所以并不复杂。

玛利亚有一个任务，现在的时间为 $0$，她要从第一个站出发，并在最后一站的间谍碰头。玛利亚知道有一个强大的组织正在追踪她，她知道如果一直呆在一个车站，她会有很大的被抓的风险，躲在运行的列车中是比较安全的。所以，她决定尽可能地呆在运行的列车中，她只能往前或往后坐车。

玛利亚为了能准时且安全的到达最后一个车站与对方碰头，需要知道在在车站最小等待时间总和的计划。你必须写一个程序，得到玛丽亚最短的等待时间。当然，到了终点站之后如果时间还没有到规定的时刻，她可以在车站里等着对方，只不过这个等待的时刻也是要算进去的。

这个城市有 $n$ 个车站，编号是 $1-n$，火车是这么移动的：从第一个车站开到最后一个车站。或者从最后一站发车然后开会来。火车在每特定两站之间行驶的时间是固定的，我们也可以忽略停车的时间，玛利亚的速度极快，所以他可以迅速上下车即使两辆车同时到站。

inputFormat:
输入文件包含多组数据，每组数据都由 $7$ 行组成。

- 第 $1$ 行一个正整数 $N\ (2 \le N \le 50)$ 表示站的数量。
- 第 $2$ 行一个正整数 $T\ (0 \le T \le 2000)$ 表示需要的碰头时间。
- 第 $3$ 行 $1\sim n-1$ 个正整数 $t_i\ (0<t_i<70)$ 表示两站之间列车的通过时间。
- 第 $4$ 行一个整数 $M_1\ (1 \le M_1 \le 50)$ 表示离开第一个车站的火车的数量。
- 第 $5$ 行 $M_1$ 个正整数 $d_1,d_2,\cdots,d_n\ (0 \le d \le 250$，$d_i<d_i+1)$ 表示每一列火车离开第一站的时间。
- 第 $6$ 行一个正整数 $M_2\ (1 \le M_2 \le 50)$ 表示离开第 $N$ 站的火车的数量。
- 第 $7$ 行 $M_2$ 个正整数：$e_1,e_2\cdots e_{M_2}\ (0 \le e \le 250$，$e_i<e_i+1)$ 表示每一列火车离开第 $N$ 站的时间。

最后一行有一个整数 $0$。

outputFormat:
对于每组数据，打印一行 $\text{\texttt{Case Number }\textit{N}\texttt{:}}$（$N$ 从 $1$开始）和一个整数表示总等待的最短时间或者一个单词 $\verb!impossible!$ 如果玛丽亚不可能做到。

可参考样例输出。

samples:
Case Number 1: 5
Case Number 2: 0
Case Number 3: impossible

hint:
### 样例 1 解释

她 $0$ 分钟时上车，在 $3$ 号站下车，立刻坐上（$0$ 分始发）$15$ 分开的车回去，到 $2$ 号车站，立刻坐上（$20$ 分始发）$25$ 开的车到终点，$50$ 分到，还需要等待 $5$ 分钟。


title: [SCOI2010] 幸运数字

background: 四川 NOI 省选 2010。

description:
在中国，很多人都把 $6$ 和 $8$ 视为是幸运数字！lxhgww 也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字 $6$ 和 $8$ 的那些号码，比如 $68$，$666$，$888$ 都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在 $[1,100]$ 的区间内就只有 $6$ 个（$6$，$8$，$66$，$68$，$86$，$88$），于是他又定义了一种“近似幸运号码”。lxhgww 规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如 $12$，$16$，$666$ 都是“近似幸运号码”。

现在 lxhgww 想知道在一段闭区间 $[a, b]$ 内，“近似幸运号码”的个数。

inputFormat: 输入数据是一行，包括 $2$ 个数字 $a$ 和 $b$。

outputFormat: 输出数据是一行，包括 $1$ 个数字，表示在闭区间 $[a, b]$ 内“近似幸运号码”的个数。


title: GCD

description: 给定正整数 $n$，求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

inputFormat: 只有一行一个整数，代表$n$。

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

对于样例，满足条件的 $(x,y)$ 为 $(2,2)$，$(2,4)$，$(3,3)$，$(4,2)$。

---

#### 数据规模与约定

- 对于 $100\%$ 的数据，保证 $1\le n\le10^7$。

---

来源：bzoj2818。

本题数据为洛谷自造数据，使用 [CYaRon](https://github.com/luogu-dev/cyaron) 耗时 $5$ 分钟完成数据制作。


title: [SCOI2010] 股票交易

description:
最近 $\text{lxhgww}$ 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。

通过一段时间的观察，$\text{lxhgww}$ 预测到了未来 $T$ 天内某只股票的走势，第 $i$ 天的股票买入价为每股 $AP_i$，第 $i$ 天的股票卖出价为每股 $BP_i$（数据保证对于每个 $i$，都有 $AP_i \geq BP_i$），但是每天不能无限制地交易，于是股票交易所规定第 $i$ 天的一次买入至多只能购买 $AS_i$ 股，一次卖出至多只能卖出 $BS_i$ 股。

另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 $W$ 天，也就是说如果在第 $i$ 天发生了交易，那么从第 $i+1$ 天到第 $i+W$ 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 $\text{MaxP}$。

在第 $1$ 天之前，$\text{lxhgww}$ 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，$T$ 天以后，$\text{lxhgww}$ 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

inputFormat:
输入数据第一行包括 $3$ 个整数，分别是 $T$，$\text{MaxP}$，$W$。

接下来 $T$ 行，第 $i$ 行代表第 $i-1$ 天的股票走势，每行 $4$ 个整数，分别表示 $AP_i,\ BP_i,\ AS_i,\ BS_i$。

outputFormat: 输出数据为一行，包括 $1$ 个数字，表示 $\text{lxhgww}$ 能赚到的最多的钱数。

hint:
- 对于 $30\%$ 的数据，$0\leq W<T\leq 50,1\leq\text{MaxP}\leq50$；
- 对于 $50\%$ 的数据，$0\leq W<T\leq 2000,1\leq\text{MaxP}\leq50$；
- 对于 $100\%$ 的数据，$0\leq W<T\leq 2000,1\leq\text{MaxP}\leq2000$；
- 对于所有的数据，$1\leq BP_i\leq AP_i\leq 1000,1\leq AS_i,BS_i\leq\text{MaxP}$。


title: [ZJOI2010] 贪吃的老鼠

description:
奶酪店里最近出现了 $m$ 只老鼠！它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产 $n$ 块奶酪，其中第 $i$ 块的大小为 $p_i$，会在第 $r_i$ 秒被生产出来，并且必须在第 $d_i$ 秒之前将它吃掉。第 $j$ 只老鼠吃奶酪的速度为 $s_j$，因此如果它单独吃完第 $i$ 块奶酪所需的时间为 $p_i/s_j$。老鼠们吃奶酪的习惯很独特，具体来说：

1. 在任一时刻，一只老鼠最多可以吃一块奶酪；
2. 在任一时刻，一块奶酪最多被一只老鼠吃。

由于奶酪的保质期常常很短，为了将它们全部吃掉，老鼠们需要使用一种神奇的魔法来延长奶酪的保质期。将奶酪的保质期延长 $T$ 秒是指所有的奶酪的 $d_i$ 变成 $d_i+T$。同时，使用魔法的代价很高，因此老鼠们希望找到最小的 $T$ 使得可以吃掉所有的奶酪。

inputFormat:
输入文件的第一行包含一个整数 $K$，表示输入文件中数据的组数。

每组数据的第一行包含两个整数 $n$ 和 $m$，分别表示奶酪和老鼠的数量。接下来的 $n$ 行每行包含三个整数 $p_i,r_i,d_i$。最后 $m$ 行每行包含一个整数，表示 $s_j$。$p_i,r_i,d_i,s_j$ 的含义如上文所述。

outputFormat: 包含 $K$ 行，每行包含一个实数，表示你找到的最小的 $T$。你的答案和标准答案的绝对误差不应超过 $10^{-4}$。

hint:
### 样例说明

第一组数据中：

第 $0$ 到第 $1$ 秒：

第一只老鼠吃第一块奶酪；

第 $1$ 到第 $3.5$ 秒：

- 第一只老鼠吃第二块奶酪；
- 第二只老鼠吃第一块奶酪；

第 $3.5$ 到第 $4.5$ 秒：第一只老鼠吃第一块奶酪。

### 数据规模

$30\%$ 的数据中，$1 \le n,m \le 5$；

$100\%$ 的数据中，$1 \le K \le 5$，$1 \le n,m \le 30$，$1 \le p_i \le 10^5$，$0 \le r_i<d_i \le 10^7$，$1 \le s_j \le 10^5$。


title: [SCOI2010] 传送带

description: 在一个 $2$ 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 $\text{AB}$ 和线段 $\text{CD}$。lxhgww 在 $\text{AB}$ 上的移动速度为 $P$，在 $\text{CD}$ 上的移动速度为 $Q$，在平面上的移动速度 $R$。现在 lxhgww 想从 $\text A$ 点走到 $\text D$ 点，他想知道最少需要走多长时间。

inputFormat:
第一行 $4$ 个整数，表示 $\text A$ 和 $\text B$ 的坐标，分别为 $A_x$，$A_y$，$B_x$，$B_y$。

第二行 $4$ 个整数，表示 $\text C$ 和 $\text D$ 的坐标，分别为 $C_x$，$C_y$，$D_x$，$D_y$。

第三行 $3$ 个整数，分别是 $P$，$Q$，$R$。

outputFormat: 输出数据为一行，表示 lxhgww 从 $\text A$ 点走到 $\text D$ 点的最短时间，保留到小数点后 $2$ 位。


title: [SCOI2010] 序列操作

description:
lxhgww 最近收到了一个 $01$ 序列，序列里面包含了 $n$ 个数，下标从 $0$ 开始。这些数要么是 $0$，要么是 $1$，现在对于这个序列有五种变换操作和询问操作：

- `0 l r` 把 $[l, r]$ 区间内的所有数全变成 $0$；
- `1 l r` 把 $[l, r]$ 区间内的所有数全变成 $1$；
- `2 l r` 把 $[l,r]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$，把所有的 $1$ 变成 $0$；
- `3 l r` 询问 $[l, r]$ 区间内总共有多少个 $1$；
- `4 l r` 询问 $[l, r]$ 区间内最多有多少个连续的 $1$。

对于每一种询问操作，lxhgww 都需要给出回答，聪明的程序员们，你们能帮助他吗？

inputFormat:
第一行两个正整数 $n,m$，表示序列长度与操作个数。
第二行包括 $n$ 个数，表示序列的初始状态。
接下来 $m$ 行，每行三个整数，表示一次操作。

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


title: [SCOI2012] 滑雪

description:
a180285 非常喜欢滑雪。他来到一座雪山，这里分布着 $m$ 条供滑行的轨道和 $n$ 个轨道之间的交点（同时也是景点），而且每个景点都有一编号 $i\space (1 \le i \le n)$ 和一高度 $h_i$。

a180285 能从景点 $i$ 滑到景点 $j$ 当且仅当存在一条 $i$ 和 $j$ 之间的边，且 $i$ 的高度**不小于** $j$。与其他滑雪爱好者不同，a180285 喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。

于是 a18028 5拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是 a180285 滑行的距离）。

请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。 现在，a180285站在 $1$ 号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？

inputFormat:
输入的第一行是两个整数 $n,m$。
接下来一行有 $n$ 个整数 $h_i$，分别表示每个景点的高度。

接下来 $m$ 行，表示各个景点之间轨道分布的情况。每行三个整数 $u,v,k$，表示编号为 $u$ 的景点和编号为 $v$ 的景点之间有一条长度为 $k$ 的轨道。

outputFormat: 输出一行，表示 a180285 最多能到达多少个景点，以及此时最短的滑行距离总和。


title: [ZJOI2005] 梦幻折纸

background:
你是一个喜欢幻想的小女孩，特别喜欢追求一些完美的理想的东西——“理想的圆”，“理想的均等”，“理想的材料”，“理想的最优解”……

最近，偶然的机会，你迷恋上了折纸。你把自己的作业本扯下来折成了各种各样的小把戏——小花，小草，小鸟，小兔子，小老鼠……一张又一张，直到作业本的封面都被你折成了纸鹤。但是你还是觉得不过瘾。

终于……你克制不住自己心中压抑的想法，从可怜的同桌那儿拿了一张用过的草稿纸。正当你打算用同样的方法折掉它的时候，你十分惊奇的发现：这不是一张普通的草稿纸，而是一张非常特殊的草稿纸：它薄得厚度可以忽略不计，柔韧得怎么撕也撕不破，而且无论怎么折都行。

你如获至宝，这不就是你梦寐以求的“理想的材料”吗？真所谓“踏破铁鞋无觅处，得来全不费功夫。梦里寻它千百度，蓦然回首，它却在灯火阑珊处 ！”你决心要把它折成一个有难度一点的东西，才对得住一张这么好的纸。

description:
你仔细观察了一下纸的特点：

纸的大小为n(cm)×m(cm)，上面等距离的印好了格线，n-1条横线和m-1条竖线（线的宽度忽略不计）。这些格线将纸分成了n×m个大小完全相同的正方形小格。你的同桌已经在每一块小格(i,j)上写下了一个互不相同的正整数P[i,j]，1<=P[i,j]<=n×m。

“他干嘛在纸上写下这么些数字呢？”你看着这些数字，疑惑不解。

这时，你的同桌突然出现了，他发现你正拿着他的纸，看着上面的数字发呆。于是傻乎乎地对你说：

“我刚刚也想学你折纸，可是我很笨，只折出一个1(cm)×1(cm)的正方形，也就是一个n×m层纸的纸垛，每一层恰好是一个小格，所有的格线都恰好在正方形的边界上。”

“哦，折得不错，挺好的。”你口里说不错，心里却暗笑：没见过你这么笨的。居然把这么好的纸折成一个如此简单的正方形，简直是暴殄天物，罪过啊，罪过！

“是吗？你也觉得不错啊？我刚刚就在想，如果给这些小格编上号，最上面一层编为1，从上往下数的第i层编为i，那么能不能从这些编号复原出刚刚我折的那个图形呢？于是我就在这些格子上写下了它们的编号”

“这……”你一时语塞，确切的说，惊讶得说不出话来，原来一向傻乎乎的同桌脑子里也有这么深奥的想法。

“这样吧，如果你能根据我把我刚刚折的正方形折出来，那我就把这张纸送给你！” 同桌接着说，“不管你折法是否和我一样，只要折出来也是个1(cm)×1(cm)的正方形，从上往下数的第i层的编号恰好也是i，并且纸不能破，就算你折对了。”

“好啊，不过我先要检查检查你有没有骗我，要是你故意骗我或者自己粗心在编号的时候写错了数字而害得我折不出来，我可饶不了你！”

inputFormat:
第一行为整数t，代表输入数据的总数。

以下有t组数据，每组数据的结构如下：

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

以下n行，每行m个正整数，相邻两个整数之间用一个空格隔开，描述矩阵p[i,j]。

outputFormat:
输出t行，对应t个输入数据。

对于第i组数据，输出AllRight——如果可以折出来；输出Cheat——如果折不出来。

hint:
    t ≤ 10

    1 ≤ n，m ≤ 100


title: [ZJOI2004] 午餐

description:
上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。

THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。

现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

inputFormat:
第一行一个整数N，代表总共有N个人。

以下N行，每行两个整数 Ai，Bi。依次代表第i个人的打饭时间和吃饭时间。

outputFormat: 一个整数T，代表所有人吃完饭的最早时刻。

hint: 所有输入数据均为不超过200的正整数。


title: [ZJOI2005] 九数码游戏

inputFormat: 输入文件中包含三行三列九个数，同行的相邻两数用空格隔开，表示初始状态每个方格上的数字。初始状态不会是目标状态。

outputFormat:
如果目标状态无法达到，则输出“UNSOLVABLE”（引号不输出）。

否则，第一行是一个整数S，表示最少的操作次数。接下来4 × (S + 1)行，每四行表示一个状态：前三行每行三个整数，相邻两数用空格隔开，表示每个方格上的数字，第四行是一个空行，作为分隔。第一个状态必须是初始状态，最后一个状态必须是目标状态。


title: [ZJOI2005] 沼泽鳄鱼

description:
潘塔纳尔沼泽地号称世界上最大的一块湿地，它地位于巴西中部马托格罗索州的南部地区。每当雨季来临，这里碧波荡漾、生机盎然，引来不少游客。

为了让游玩更有情趣，人们在池塘的中央建设了几座石墩和石桥，每座石桥连接着两座石墩，且每两座石墩之间至多只有一座石桥。这个景点造好之后一直没敢对外开放，原因是池塘里有不少危险的食人鱼。

豆豆先生酷爱冒险，他一听说这个消息，立马赶到了池塘，想做第一个在桥上旅游的人。虽说豆豆爱冒险，但也不敢拿自己的性命开玩笑，于是他开始了仔细的实地勘察，并得到了一些惊人的结论：食人鱼的行进路线有周期性，这个周期只可能是 $2$、$3$ 或者 $4$ 个单位时间。每个单位时间里，食人鱼可以从一个石墩游到另一个石墩。每到一个石墩，如果上面有人它就会实施攻击，否则继续它的周期运动。如果没有到石墩，它是不会攻击人的。

借助先进的仪器，豆豆很快就摸清了所有食人鱼的运动规律，他要开始设计自己的行动路线了。每个单位时间里，他只可以沿着石桥从一个石墩走到另一个石墩，而不可以停在某座石墩上不动，因为站着不动还会有其它危险。如果豆豆和某条食人鱼在同一时刻到达了某座石墩，就会遭到食人鱼的袭击，他当然不希望发生这样的事情。

现在豆豆已经选好了两座石墩 $\mathrm{Start}$ 和 $\mathrm{End}$，他想从 $\mathrm{Start}$ 出发，经过 $K$ 个单位时间后恰好站在石墩 $\mathrm{End}$ 上。假设石墩可以重复经过（包括 $\mathrm{Start}$ 和 $\mathrm{End}$），他想请你帮忙算算，这样的路线共有多少种（当然不能遭到食人鱼的攻击）。

inputFormat:
输入文件共 $M + 2 + \mathrm{NFish}$ 行。

第一行包含五个正整数 $N,M,\mathrm{Start},\mathrm{End},K$，分别表示石墩数目、石桥数目、$\mathrm{Start}$ 石墩和 $\mathrm{End}$ 石墩的编号和一条路线所需的单位时间。石墩用 $0$ 到 $N-1$ 的整数编号。

第 $2$ 到 $M + 1$ 行，给出石桥的相关信息。每行两个整数 $x$ 和 $y$，$0 \leq x, y \leq N-1$，表示这座石桥连接着编号为 $x$ 和 $y$ 的两座石墩。

第 $M + 2$ 行是一个整数 $\mathrm{NFish}$，表示食人鱼的数目。

第 $M + 3$ 到 $M + 2 + \mathrm{NFish}$ 行，每行给出一条食人鱼的相关信息。每行的第一个整数是 $T$，$T = 2,3$ 或 $4$，表示食人鱼的运动周期。接下来有 $T$ 个数，表示一个周期内食人鱼的行进路线。

- 如果 $T=2$，接下来有 $2$ 个数 $P_0$ 和 $P_1$，食人鱼从 $P_0$ 到 $P_1$，从 $P_1$ 到 $P_0,\ldots$；

- 如果 $T=3$，接下来有 $3$ 个数 $P_0,P_1$ 和 $P_2$，食人鱼从 $P_0$ 到 $P_1$，从 $P_1$ 到 $P_2$，从 $P_2$ 到 $P_0,\ldots$；

- 如果 $T=4$，接下来有 $4$ 个数 $P_0,P_1,P_2$ 和 $P_3$，食人鱼从 $P_0$ 到 $P_1$，从 $P_1$ 到 $P_2$，从 $P_2$ 到 $P_3$，从 $P_3$ 到 $P_0,\ldots$。

豆豆出发的时候所有食人鱼都在自己路线上的 $P_0$ 位置，请放心，这个位置不会是 $\mathrm{Start}$ 石墩。

outputFormat: 输出路线的种数，因为这个数可能很大，你只要输出该数除以 $10000$ 的余数就行了。

hint: 对于 $100 \%$ 的数据，$1 \leq N \leq 50$，$1 \leq K \leq 2 \times 10^9$，$1 \leq \mathrm{NFish} \leq 20$。


title: [ZJOI2005] Genotype

background:
Genotype 是一个有限的基因序列。它是由大写的英文字母A-Z组成，不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的规则可以用三个大写字母A1A2A3表示，含义为基因A1可以分化成A2A3

我们用S代表特种基因，繁殖genotype是从特种基因序列开始。根据给定的规则，它由被选择控制规则对基因不断进行繁殖而成。

description:
读入一个定义的规则集和一个想生成的genotypes 单词序列

对每一个给定的 genotype，根据给定的分化规则，检查是否它能从某一个确定特种基因序列生成，如果能，找到最小的序列长度，

inputFormat:
第一行有一个整数n, 1 <= n <= 10000. 下面n 每一行为一个分化规则. 这些规则都由包含A – Z的三个大写字母组成.

接下来的10 行，每行有一个 genotype. Genotype由没有空格的单词组成，最多100 个英文大写字母.

outputFormat: 有10行,在第I行应写入: 一个正整数――需要生成第I个genotypes的最小长度；或者单词 NIE, 如果不能生成对应的genotype。


title: [NOIP2015 提高组] 信息传递

background: NOIP2015 Day1T2

description:
有 $n$ 个同学（编号为 $1$ 到 $n$）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 $i$ 的同学的信息传递对象是编号为 $T_i$ 的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

inputFormat:
输入共 $2$ 行。

第一行包含 $1$ 个正整数 $n$，表示 $n$ 个人。

第二行包含 $n$ 个用空格隔开的正整数 $T_1,T_2,\cdots,T_n$，其中第 $i$ 个整数 $T_i$ 表示编号为 $i$ 的同学的信息传递对象是编号为 $T_i$ 的同学，$T_i\leq n$ 且 $T_i\neq i$。

outputFormat: 共一行一个整数，表示游戏一共可以进行多少轮。

hint:
**样例 1 解释：**

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

游戏的流程如图所示。当进行完第 $3$ 轮游戏后，$4$ 号玩家会听到 $2$ 号玩家告诉他自己的生日，所以答案为 $3$。当然，第 $3$ 轮游戏后，$2$ 号玩家、 $3$ 号玩家都能从自己的消息来源得知自己的生日，同样符合游戏结束的条件。

- 对于 $30\%$ 的数据，$n\le 200$；
- 对于 $60\%$ 的数据，$n\le 2500$；
- 对于 $100\%$ 的数据，$n\le 2\times 10^5$。


title: [ZJOI2006] GameZ游戏排名系统

description:
GameZ为他们最新推出的游戏开通了一个网站。世界各地的玩家都可以将自己的游戏得分上传到网站上。这样就可以看到自己在世界上的排名。得分越高，排名就越靠前。当两个玩家的名次相同时，先上传记录者优先。由于新游戏的火爆，网站服务器已经难堪重负。为此GameZ雇用了你来帮他们重新开发一套新的核心。

排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回 $10$ 条记录。

inputFormat:
输入文件的第一行是一个整数 $n$ $( n \ge 10 )$ 表示请求总数目。接下来n行每行包含了一个请求。请求的具体格式如下：

``+Name Score`` 上传最新得分记录。``Name`` 表示玩家名字，由大写英文字母组成，不超过 $10$ 个字符。``Score`` 为最多 $10$ 位的正整数。

``?Name`` 查询玩家排名。该玩家的得分记录必定已经在前面上传。

``?Index`` 返回自第 ``Index`` 名开始的最多 $10$ 名玩家名字。``Index`` 必定合法，即不小于 $1$，也不大于当前有记录的玩家总数。

outputFormat:
对于每条查询请求，在文件中输出相应结果。

对于 ``?Name`` 格式的请求，应输出一个整数表示该玩家当前的排名。

对于 ``?Index`` 格式的请求，应在一行中依次输出从第 ``Index`` 名开始的最多 $10$ 名玩家姓名，用一个空格分隔。

samples:
2
CATHY TOM ADAM BOB
CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM
4

hint:
20
+ADAM 1000000     加入ADAM的得分记录

+BOB 1000000       加入BOB的得分记录

+TOM 2000000       加入TOM的得分记录

+CATHY 10000000    加入CATHY的得分记录

?TOM               输出TOM目前排名

?1                  目前有记录的玩家总数为4，因此应输出第1名到第4名。

+DAM 100000        加入DAM的得分记录

+BOB 1200000       更新BOB的得分记录

+ADAM 900000      更新ADAM的得分记录（即使比原来的差）

+FRANK 12340000   加入FRANK的得分记录

+LEO 9000000       加入LEO的得分记录

+KAINE 9000000     加入KAINE的得分记录

+GRACE 8000000    加入GRACE的得分记录

+WALT 9000000      加入WALT的得分记录

+SANDY 8000000    加入SANDY的得分记录

+MICK 9000000      加入MICK的得分记录

+JACK 7320000      加入JACK的得分记录

?2                  目前有记录的玩家总数为12，因此应输出第2名到第11名。

?5                  输出第5名到第13名。

?KAINE             输出KAINE的排名

输入文件总大小不超过 2M。

NOTE：用 C++ 的 fstream 读大规模数据的效率较低


title: [ZJOI2006] 三色二叉树

description:
一棵二叉树可以按照如下规则表示成一个由 $0$、$1$、$2$ 组成的字符序列，我们称之为“二叉树序列 $S$”：

$$S=
\begin{cases}
0& \text表示该树没有子节点\\
1S_1& 表示该树有一个节点，S_1 为其子树的二叉树序列\\
2S_1S_2& 表示该树由两个子节点，S_1 和 S_2 分别表示其两个子树的二叉树序列
\end{cases}$$

例如，下图所表示的二叉树可以用二叉树序列 $S=\texttt{21200110}$ 来表示。

![haha.png](https://i.loli.net/2020/04/27/Ijw8ZEWCKH2rtJG.png)

你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不同。给定一颗二叉树的二叉树序列，请求出这棵树中**最多和最少**有多少个点能够被染成绿色。

inputFormat: 输入只有一行一个字符串 $s$，表示二叉树序列。

outputFormat: 输出只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。

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

对于全部的测试点，保证 $1 \leq |s| \leq 5 \times 10^5$，$s$ 中只含字符 `0` `1` `2`。


title: [ZJOI2008] 杀蚂蚁

description:
最近，佳佳迷上了一款好玩的小游戏：antbuster。

游戏规则非常简单：在一张地图上，左上角是蚂蚁窝，右下角是蛋糕，蚂蚁会源源不断地从窝里爬出来，试图把蛋糕搬回蚂蚁窝。而你的任务，就是用原始资金以及杀蚂蚁获得的奖金造防御塔，杀掉这些试图跟你抢蛋糕的蚂蚁~

为了拿到尽可能高的分数，佳佳设计了很多种造塔的方案，但在尝试了其中的一小部分后，佳佳发现，这个游戏实在是太费时间了。为了节省时间，佳佳决定写个程序，对于每一种方案，模拟游戏进程，根据效果来判断方案的优劣。

根据自己在游戏中积累的一些经验，以及上网搜到的一些参数，佳佳猜了蚂蚁爬行的算法，并且假设游戏中的蚂蚁也是按这个规则选择路线：

1. 每一秒钟开始的时候，蚂蚁都在平面中的某个整点上。如果蚂蚁没有扛着蛋糕，它会在该点留下 $2$ 单位的信息素，否则它会留下 $5$ 单位的信息素。然后蚂蚁会在正北、正南、正东、正西四个方向中选择一个爬过去。

2. 选择方向的规则是：首先，爬完一个单位长度后到达的那个点上，不能有其他蚂蚁或是防御塔，并且那个点不能是蚂蚁上一秒所在的点（除非上一个时刻蚂蚁就被卡住，且这个时刻它仍无法动），当然，蚂蚁也不会爬出地图的边界（我们定义这些点为不可达点）。如果此时有多个选择，蚂蚁会选择信息素最多的那个点爬过去。

3. 如果此时仍有多种选择，蚂蚁先面向正东，如果正东不是可选择的某个方向，它会顺时针转 $90^\degree$，再次判断，如果还不是，再顺时针旋转 $90^\degree$，直到找到可以去的方向。

4. 如果将每只蚂蚁在洞口出现的时间作为它的活动时间的第 $1$ 秒，那么每当这只蚂蚁的活动时间秒数为 $5$ 的倍数的时候，它先按规则 $1\sim 3$ 确定一个方向，面对该方向后逆时针转 $90^\degree$，若它沿当前方向会走到一个不可达点，它会不停地每次逆时针转 $90^\degree$，直到它面对着一个可达的点，这样定下的方向才是蚂蚁最终要爬去的方向。

5. 如果蚂蚁的四周都是不可达点，那么蚂蚁在这一秒内会选择停留在当前点。下一秒判断移动方向时，它上一秒所在点为其当前停留的点。

6. 你可以认为蚂蚁在选定方向后，瞬间移动到它的目标点，这一秒钟剩下的时间里，它就停留在目标点。

7. 蚂蚁按出生的顺序移动，出生得比较早的蚂蚁先移动。

然后，是一些有关地图的信息：

1. 每一秒，地图所有点上的信息素会损失 $1$ 单位，如果那个点上有信息素的话。

2. 地图上某些地方是炮台。炮台的坐标在输入中给出。

3. 地图的长、宽在输入中给出，对于 $n\times m$ 的地图，它的左上角坐标为 $(0,0)$，右下角坐标为 $(n,m)$。蚂蚁洞的位置为 $(0,0)$，蛋糕的位置为 $(n,m)$。

4. 你可以把蚂蚁看做一个直径为 $1$ 单位的圆，圆心位于蚂蚁所在的整点。

5. 游戏开始时，地图上没有蚂蚁，每个点上的信息素含量均为 $0$。

一些有关炮塔的信息：

1. 炮塔被放置在地图上的整点处。

2. 为了简单一些，我们认为这些炮塔都是激光塔。激光塔的射速是 $1$ 秒每次，它的攻击伤害为 $d$ 单位每次，攻击范围为 $r$。你可以认为每秒蚂蚁移动完毕后，塔才开始攻击。并且，只有当代表蚂蚁的圆的圆心与塔的直线距离不超过 $r$ 时，塔才算打得到那只蚂蚁。

3. 如果一只蚂蚁扛着蛋糕，那么它会成为 target，也就是说，任何打得到它的塔的炮口都会对准它。如果蛋糕好好地呆在原位，那么每个塔都会挑离它最近的蚂蚁进行攻击，如果有多只蚂蚁，它会选出生较早的一只。如果有蚂蚁扛着蛋糕，但是不在某个塔的攻击范围内，这个塔会选择最近的蚂蚁进行攻击。

4. 激光塔有个比较奇怪的特性：它在选定了打击目标后，只要目标在其射程内，塔到目标蚂蚁圆心的连线上的所有蚂蚁（这里“被打到”的判定变成了表示激光的线段与表示蚂蚁的圆有公共点）都会被打到并损 $d$ 格血，但激光不会穿透它的打击目标打到后面的蚂蚁。

5. 尽管在真实游戏中，塔是可以升级的，但在这里我们认为塔的布局和等级就此定了下来，不再变动。

再介绍一下蚂蚁窝：

1. 如果地图上的蚂蚁不足 $6$ 只，并且洞口（即点 $(0,0)$）没有蚂蚁，那么窝中每秒会爬出一只蚂蚁，直到地图上的蚂蚁数为 $6$ 只。

2. 刚出生的蚂蚁站在洞口。

3. 每只蚂蚁有一个级别，级别决定了蚂蚁的血量，级别为 $k$ 的蚂蚁的血量为 $\lfloor 4\times 1.1^k\rfloor$（$\lfloor x\rfloor$ 表示对 $x$ 下取整）。每被塔打一次，蚂蚁的血减少 $d$。注意，血量为 $0$ 的蚂蚁仍能精力充沛地四处乱爬，只有一只蚂蚁的血被打成负数时，它才算挂了。

4. 蚂蚁的级别是这样算的：前 $6$ 只出生的蚂蚁是 $1$ 级，第 $7\sim 12$ 只是 $2$级，依此类推第 $6k+1\sim 6k+6$ 的等级是 $k+1(k\in \Bbb{N})$。

最后给出关于蛋糕的介绍：

1. 简单起见，你可以认为此时只剩最后一块蛋糕了。如果有蚂蚁走到蛋糕的位置，并且此时蛋糕没有被扛走，那么这只蚂蚁就扛上了蛋糕。蚂蚁被打死后蛋糕回到点 $(n,m)$。

2. 如果一只扛着蛋糕的蚂蚁走到蚂蚁窝的位置，我们就认为蚂蚁成功抢到了蛋糕，游戏结束。这个回合不会对蚂蚁的年龄产生贡献。

3. 蚂蚁扛上蛋糕时，血量会增加 $\left\lfloor\dfrac{x}{2}\right\rfloor$（$x$ 表示蚂蚁出生时的血量），但不会超过蚂蚁的血量上限。

整理一下 $1$ 秒钟内发生的事件：

1. $1$ 秒的最初，如果地图上蚂蚁数不足 $6$，一只蚂蚁就会在洞口出生。

2. 接着，蚂蚁们在自己所在点留下一些信息素后，考虑移动。先出生的蚂蚁先移动。

3. 移动完毕后，如果有蚂蚁在蛋糕的位置上并且蛋糕没被拿走，它把蛋糕扛上，血量增加，并在这时被所有塔设成 target。

4. 然后所有塔同时开始攻击。如果攻击结束后那只扛着蛋糕的蚂蚁挂了，蛋糕瞬间归位。扛着蛋糕的蚂蚁死后，蛋糕会在下一秒钟所有蚂蚁移动完之后再出现。下一秒钟出现在 $(n,m)$ 的蚂蚁才会获得蛋糕。

5. 攻击结束后，如果发现扛蛋糕的蚂蚁没死并在窝的位置，就认为蚂蚁抢到了蛋糕，游戏也在此时结束。

6. 最后，地图上所有点的信息素损失 $1$ 单位。所有蚂蚁的年龄加 $1$。漫长的 $1$ 秒到此结束。

inputFormat:
输入的第一行是两个用空格隔开的正整数，$n,m$，分别表示了地图的长和宽。

第二行是三个用空格隔开的整数，$s,d,r$，依次表示炮塔的个数、单次攻击伤害以及攻击范围。

接下来 $s$ 行，每行两个用空格隔开的整数 $x,y$，描述了一个炮塔的位置。当然，蚂蚁窝的洞口以及蛋糕所在的位置上一定没有炮塔。

最后一行是一个正整数 $t$，表示我们模拟游戏的前 $t$ 秒钟。

outputFormat:
如果在第 $t$ 秒或之前蚂蚁抢到了蛋糕，输出一行 `Game over after x seconds`，其中 $x$ 为游戏结束的时间，否则输出 `The game is going on`。

如果游戏在 $t$ 秒或之前结束，输出游戏结束时所有蚂蚁的信息，否则输出 $t$ 秒后所有蚂蚁的信息。格式如下：

第一行是一个整数 $s$，表示此时活着的蚂蚁的总数。

接下来 $s$ 行，每行五个整数，依次表示一只蚂蚁的年龄（单位为秒）、等级、当前血量，以及在地图上的位置 $(a,b)$。输出按蚂蚁的年龄递减排序。

hint:
### 样例说明：

$3\times 5$ 的地图，有一个单次伤害为 $1$、攻击范围为 $2$ 的激光炮塔，它的位置为 $(2,2)$，模拟游戏的前 $5$ 秒。

$5$ 秒内有 $5$ 只蚂蚁出生，都是向东爬行，其中第 $1\sim 4$ 只在路过 $(0,2)$ 点时被激光塔射伤了 $1$ 格血。在第 $5$ 秒的时候，最早出生的蚂蚁按移动规则 $1\sim 3$ 本来该向东移动，但由于规则 $4$ 的作用，它在发现向北和向西移动都会到达不可达点后，最终选择了向南移动。

### 数据范围说明：

对于 $100\%$ 的数据，满足 $1\leqslant n,m\leqslant 8,s\leqslant 20,t\leqslant 2\times 10^5,0\leqslant d\leqslant 10^4,0\leqslant r\leqslant 15$。（这里的 $s$ 指的是炮塔的总数）。


title: [ZJOI2008] 泡泡堂

description:
第 XXXX 届 NOI 期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由 $n$ 名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，$n$ 号选手捉对厮杀，共进行 $n$ 场比赛。每胜一场比赛得 $2$ 分，平一场得 $1$ 分，输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。

作为浙江队的领队，你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚，并将其用一个实力值来衡量。为简化问题，我们假定选手在游戏中完全不受任何外界因素干扰，即实力强的选手一定可以战胜实力弱的选手，而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序，所以所有的队伍都采取了这样一种策略，就是完全随机决定出场顺序。

当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下，浙江队最终分别能得到多少分。

inputFormat:
输入文件的第一行为一个整数 $n$，表示每支代表队的人数。

接下来 $n$ 行，每行一个整数，描述了 $n$ 位浙江队的选手的实力值。

接下来 $n$ 行，每行一个整数，描述了你的对手的 $n$ 位选手的实力值。

outputFormat: 输入文件中包括两个用空格隔开的整数，分别表示浙江队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。


title: [ZJOI2008] Risk

description:
经过连续若干年的推广，Risk这个游戏已经风靡全国，成为大众喜闻乐见的重要娱乐方式。Risk这个游戏可以理解为一种简易的策略游戏，游戏者的目的是占领所有的土地。由于游戏规则的规定，只要两个国家相邻，就认为两个国家有交战的可能性。我们现在希望知道在当前的局面下，哪些国家之间有交战的可能性。注意，我们认为只有当两个国家的国界线有公共边的时候才认为相邻，若两个国家的领土只有公共点，则认为两个国家不相邻。

每一个国家的边界由一系列线段组成，保证这个边界是一个简单多边形，即严格不自交。为了定位每个国家的位置，我们还给出每个国家最庞大的一支军队的位置，保证这个位置一定出现在某一个形内，而不是出现在某条边界上。

inputFormat:
输入文件的第一行中包括两个整数n,m。分别表示地图上的国家数和描述国家的边界的线段的数量。1<=n<=600，1<=m<=4000。接下来n行，每行用一对数描述了某个国家的主力军队的坐标。接下来m行，每行有4个数x1,y1,x2,y2，（x1,y1）-(x2,y2)描述了一条国界线。所有点的坐标都是0-10000之间的整数。

保证输入的所有线段至多只会在线段交点处相交。整张地图上有且仅有一块面积无限的空白区域不属于任何国家。每一条国界线两侧的区域或者隶属于两个不同的国家，或者分隔了一个国家与那块无穷大的空白区域。即保证一条国界线两侧的区域不同时属于同一个国家或是同时都是空白区域。所有封闭区域内部包含且仅包含一支主力军队，表示了该区域的归属。

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

例如上图中第一行的数据是合法的。而第二行中的数据都是不合法的。左边的那幅图包含线段两侧都是空白区域；中间的图包含线段两侧区域同时属于同一个国家；右边的图中军队被布置在了国界线上，因此非法；此外若最右侧的图中若没有军队也是非法的。保证输入文件提供的数据都是合法的，你的程序不需要进行数据合法性的判定。

outputFormat: 输出文件包括n行，每行第一个数字x表示有x个国家可能与这个国家交战，接着在同一行中升序输出x个整数，表示可能与这个国家交战的国家的编号。国家按输入中给出的顺序从1到n编号。注意数字间严格以一个空格隔开，并且不要在行末输出多余的空白字符。


title: [ZJOI2006] 碗的叠放

description:
小H有n个碗需要放进橱柜，她希望将他们叠起来放置。你知道每个碗都是规则的圆柱体，并且都是上宽下窄，你已经测量出了每个碗的两个半径及高，请你帮小H找出一种叠放顺序，使得叠放出来的碗堆的高度尽量小，比如：

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

inputFormat: 第一行一个整数n，表示碗的数目。以下n行，每行三个整数h，r1，r2。分别表示碗高及两个半径。其中r1<r2。

outputFormat: 仅一个数，表示最小的高度。答案四舍五入取整。

hint: 数据范围：100%数据满足n<=9。所有输入的数绝对值不超过1000。


title: [ZJOI2008] 树的统计

description:
一棵树上有 $n$ 个节点，编号分别为 $1$ 到 $n$，每个节点都有一个权值 $w$。

我们将以下面的形式来要求你对这棵树完成一些操作：

I. `CHANGE u t` : 把结点 $u$ 的权值改为 $t$。

II. `QMAX u v`: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值。

III. `QSUM u v`: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和。

注意：从点 $u$ 到点 $v$ 的路径上的节点包括 $u$ 和 $v$ 本身。

inputFormat:
输入文件的第一行为一个整数 $n$，表示节点的个数。

接下来 $n-1$ 行，每行 $2$ 个整数 $a$ 和 $b$，表示节点 $a$ 和节点 $b$ 之间有一条边相连。

接下来一行 $n$ 个整数，第 $i$ 个整数 $w_i$ 表示节点 $i$ 的权值。

接下来 $1$ 行，为一个整数 $q$，表示操作的总数。

接下来 $q$ 行，每行一个操作，以 `CHANGE u t` 或者 `QMAX u v` 或者 `QSUM u v` 的形式给出。

outputFormat: 对于每个 `QMAX` 或者 `QSUM` 的操作，每行输出一个整数表示要求输出的结果。

samples:
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

hint:
对于 $100 \%$ 的数据，保证 $1\le n \le 3\times 10^4$，$0\le q\le 2\times 10^5$。

中途操作中保证每个节点的权值 $w$ 在 $-3\times 10^4$ 到 $3\times 10^4$ 之间。


title: [ZJOI2009] 函数

description:
有 $N$ 个连续函数 $f_i(x)$，其中 $1\le i\le N$。如果对于任意不相等的 $i,j$ 满足 $1\le i,j\le N$，恰好存在一个 $x$ 使得 $f_i(x)=f_j(x)$，并且存在无穷多的 $x$ 使得 $f_i(x)<f_j(x)$，对于任意 $i,j,k$ 满足 $1\le i < j < k\le N$，不存在 $x$ 使得 $f_i(x)=f_j(x)=f_k(x)$，则称这 $N$ 个连续函数满足条件。

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

如上左图就是 $3$ 个满足条件的函数，最左边从下往上依次为 $f_1,f_2,f_3$。右图中红色部分是这整个函数图像的最低层，我们称它为第一层。同理绿色部分称为第二层，蓝色部分称为第三层。注意到，右图中第一层左边一段属于 $f_1$，中间属于 $f_2$，最后属于 $f_3$。而第二层左边属于 $f_2$，接下来一段属于 $f_1$，再接下来一段属于 $f_3$，最后属于 $f_2$。因此，我们称第一层分为了三段，第二层分为了四段。同理第三层只分为了两段。求满足前面条件的 $N$ 个函数，第 $K$ 层最少能由多少段组成。

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

outputFormat: 一行一个整数，表示 $N$ 个函数第 $K$ 层最少能由多少段组成。

hint: 对于 $100\%$ 的数据满足 $1\le K\le N\le 100$。


title: [ZJOI2008] 生日聚会

description:
今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：

对于任意连续的一段，男孩与女孩的数目之差不超过k。

很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考这个问题……

假设参加party的人中共有n个男孩与m个女孩，你是否能解答Susie和hidadz的疑问呢？由于这个数目可能很多，他们只想知道这个数目除以12345678的余数。

inputFormat: 输入文件party.in仅包含一行共3个整数，分别为男孩数目n, 女孩数目m,  常数k。

outputFormat: 输出文件party.out应包含一行，为题中要求的答案。

hint:
对于30%的数据，n , m ≤ 20；

对于100%的数据, n , m ≤ 150，k ≤ 20。


title: [ZJOI2006] 超级麻将

description:
很多人都知道玩麻将，当然也有人不知道，呵呵，不要紧，我在这里简要地介绍一下麻将规则：

普通麻将有砣、索、万三种类型的牌，每种牌有1~9个数字，其中相同的牌每个有四张，例如1砣~9砣，1索~9索，1万~9万各有4张，所以共36\*3=108张牌。胡牌时每人有14张牌，其中只要某人手里有若干句话（就是同种类型的牌连续三张或同种牌三张），另外再加上一对，即可胡牌。当然如果全是对，叫七小对，也可以胡牌。下图是连三张示例。

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

要判断某人是否胡牌，显然一个弱智的算法就行了，某中学信息学小组超级麻将迷想了想，决定将普通麻将改造成超级麻将。

所谓超级麻将没有了砣、索、万的区分，每种牌上的数字可以是1~100，而每种数字的牌各有100张。另外特别自由的是，玩牌的人手里想拿多少张牌都可以，好刺激哦！

刺激归刺激，但是拿多了怎么胡牌呢？

超级麻将规定只要一个人手里拿的牌是若干句话（三个连续数字的牌各一张组成一句话，三张或者四张同样数字的牌也算一句话），再加上一对相同的牌，就算胡了。

作为信息学竞赛选手的你，麻烦你给这位超级麻将迷编个程序，判断能否胡牌。

inputFormat:
输入文件第一行一个整数N（N<=100），表示玩了N次超级麻将。

接下来N行，每行100个数a1..a100，描述每次玩牌手中各种牌的数量。ai表示数字为i的牌有ai张。（0<=ai<=100）

outputFormat: 输出N行，若胡了则输出Yes，否则输出No，注意区分Yes，No的大小写！


title: [ZJOI2009] 染色游戏

description: 一共n × m 个硬币，摆成n × m 的长方形。dongdong 和xixi 玩一个游戏， 每次可以选择一个连通块，并把其中的硬币全部翻转，但是需要满足存在一个 硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正 上方)，并且这个硬币是从反面向上翻成正面向上。dongdong 和xixi 轮流操作。 如果某一方无法操作，那么他(她) 就输了。dongdong 先进行第一步操作，假 设双方都采用最优策略。问dongdong 是否有必胜策略。

inputFormat: 第一行一个数T，表示他们一共玩T 局游戏。接下来是T 组游戏描述。每 组游戏第一行两个数n;m，接下来n 行每行m 个字符，第i 行第j 个字符如 果是“H” 表示第i 行第j 列的硬币是正面向上，否则是反面向上。第i 行j 列 的左上方是指行不超过i 并且列不超过j 的区域。

outputFormat: 对于每局游戏，输出一行。如果dongdong 存在必胜策略则输出“-\_-”(不含 引号) 否则输出“=\_=”(不含引号)。(注意输出的都是半角符号，即三个符号 ASCII 码分别为45,61,95)

hint:
对于40% 的数据，满足1 ≤ n;m ≤ 5。

对于100% 的数据，满足1 ≤ n;m ≤ 100，1 ≤ T ≤ 50。


title: [ZJOI2009] 多米诺骨牌

description: 有一个 $n \times m$ 的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些 $1 \times 2$ 或者 $2 \times 1$ 的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意你并不需要放满所有没有障碍的格子。

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

接下来 $n$ 行，每行 $m$ 个字符，表示这个矩形表格。其中字符 `x` 表示这个位置有障碍，字符 `.` 表示没有障碍。

outputFormat: 一行一个整数，表示不同的放置方法数对 $19\,901\,013$ 取模的值。

hint:
### 样例解释

两种放置方法分别为：

```plain
112 411
4.2 4.2
433 332
```

注意这里的数字只用于区分骨牌，不同的排列并不代表不同的方案。

### 数据范围

- 对于 $40\%$ 的数据，满足 $n,m \leq 8$；
- 对于 $90\%$ 的数据，满足 $n,m \leq 14$。
- 对于 $100\%$ 的数据，满足 $1 \leq n,m \leq 15$。


title: [ZJOI2006] 书架

description:
小 T 有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用 $1$ 到 $n$ 的正整数给每本书都编了号。

小 T 在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小 T 的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有 $x$ 本书，那么放回去时这本书上面就只可能有 $x-1$、$x$ 或 $x+1$ 本书。

当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小 T 会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。

久而久之，小 T 的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：
- 编号为 $x$ 的书在书柜的什么位置。
- 从上到下第 $i$ 本书的编号是多少。

inputFormat:
第一行有两个整数，分别表示书的个数 $n$ 以及命令条数 $m$。

第二行有 $n$ 个整数，第 $i$ 个整数表示初始时从上向下书第 $i$ 本书的编号 $p_i$。

接下来 $m$ 行，每行表示一个操作。每行初始时有一个字符串  $op$。

- 若 $op$ 为 `Top`，则后有一个整数 $s$，表示把编号为 $s$ 的书放在最上面。
- 若 $op$ 为 `Bottom`，则后有一个整数 $s$，表示把编号为 $s$ 的书放在最下面。
- 若 $op$ 为 `Insert`，则后有两个整数 $s, t$，表示若编号为 $s$ 的书上面有 $x$ 本书，则放回这本书时他的上面有 $x + t$ 本书。
- 若 $op$ 为 `Ask`，则后面有一个整数 $s$，表示询问编号为 $s$ 的书上面有几本书。
- 若 $op$ 为 `Query`，则后面有一个整数 $s$，询问从上面起第 $s$ 本书的编号。

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

samples:
10 10
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2

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

对于 $100\%$ 的数据，保证：
- $3 \leq n, m \leq 8 \times 10^4$。
- $p_i$ 是一个 $1 \sim n$ 的排列。
- $1 \leq s \leq n$，$-1 \leq t \leq 1$，$op$ 只可能是输入的五种字符串之一。
- 当编号为 $s$ 的书上面没有书的时候，不会对它进行 `Insert s -1` 操作。
- 当编号为 $s$ 的书下面没有书的时候，不会对它进行 `Insert s 1` 操作。


title: [ZJOI2012] 灾难

background:
阿米巴是小强的好朋友。

阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。

学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。

description:
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：

- 一个食物网有 $n$ 个点，代表 $n$ 种生物，生物从 $1$ 到 $n$ 编号。
- 如果生物 $x$ 可以吃生物 $y$，那么从 $y$ 向 $x$ 连一个有向边。
- 这个图没有环。
- 图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存。
- 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
- 如果某个消费者的所有食物都灭绝了，它会跟着灭绝。

我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。

举个例子：在一个草场上，生物之间的关系如下

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

如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是 $1$。但是，如果草突然灭绝，那么整个草原上的 $5$ 种生物都无法幸免，所以，草的灾难值是 $4$。

给定一个食物网，你要求出每个生物的灾难值。

inputFormat:
第一行有一个整数，表示食物网的结点个数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行若干个互不相同的整数，第 $(i + 1)$ 行的整数 $a_{i, j}$ 表示编号为 $i$ 的生物可以吃编号为 $a_{i, j}$ 的生物。每行结尾有一个整数 $0$ 表示本行结束。

outputFormat: 输出 $n$ 行，每行一个整数，第 $i$ 行输出编号为 $i$ 的生物的灾难值。

hint:
### 样例 1 解释

样例输入描述了题目描述中举的例子。

### 数据规模与约定

- 对于 $50\%$ 的数据，保证 $n \leq 10^4$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 65534$，$1 \leq a_{i, j} \leq n$，输入的文件大小不超过 1 MB，且图上不存在环。


title: [ZJOI2009] 狼和羊的故事

description:
“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向……”Orez 听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！

Orez 的羊狼圈可以看作一个 $n\times m$ 的矩阵格子，这个矩阵的边缘已经装上了篱笆。可是 Drake 很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以 Orez 决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。

通过仔细观察，Orez 发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。

Orez 想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。

inputFormat: 文件的第一行包含两个整数 $n$ 和 $m$。接下来 $n$ 行每行 $m$ 个整数，$1$ 表示该格子属于狼的领地，$2$ 表示属于羊的领地，$0$ 表示该格子不是任何一只动物的领地。

outputFormat: 文件中仅包含一个整数 $\mathit{ans}$，代表篱笆的最短长度。


title: [ZJOI2009] 取石子游戏

description:
在研究过 Nim 游戏及各种变种之后，Orez 又发现了一种全新的取石子游戏，这个游戏是这样的：

有 $n$ 堆石子，将这 $n$ 堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。

Orez 问：对于任意给出一个初始一个局面，是否存在先手必胜策略。

inputFormat:
文件的第一行为一个整数 $T$，表示有 $T$ 组测试数据。对于每组测试数据：

第一行为一个整数 $n$，表示有 $n$ 堆石子。

第二行为 $n$ 个整数 $a_1, a_2, \ldots , a_n$，依次表示每堆石子的数目。

outputFormat: 对于每组测试数据仅输出一个整数 $0$ 或 $1$。其中 $1$ 表示有先手必胜策略，$0$ 表示没有。


title: [ZJOI2008] 瞭望塔

description:
致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。

我们将H村抽象为一维的轮廓。如下图所示

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

我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi村长希望建造的塔高度尽可能小。

请你写一个程序，帮助dadzhi村长计算塔的最小高度。

inputFormat: 输入文件tower.in第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1 ~ yn。

outputFormat: 输出文件tower.out仅包含一个实数，为塔的最小高度，精确到小数点后三位。

hint:
对于60%的数据， N ≤ 60；

对于100%的数据， N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。


title: [ZJOI2009] 对称的正方形

description: Orez 很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近，Orez 又得到了一些数据，并已经把它们排成了一个 $n$ 行 $m$ 列的矩阵。通过观察，Orez 发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。Orez 自然很想知道这个数是多少，可是矩阵太大，无法去数。只能请你编个程序来计算出这个数。

inputFormat: 文件的第一行为两个整数 $n$ 和 $m$。接下来 $n$ 行每行包含 $m$ 个正整数，表示 Orez 得到的矩阵。

outputFormat: 文件中仅包含一个整数 $ans$，表示矩阵中有 $ans$ 个上下左右对称的正方形子矩阵。


title: [ZJOI2010] 数字计数

description: 给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，每个数码(digit)各出现了多少次。

inputFormat: 仅包含一行两个整数 $a,b$，含义如上所述。

outputFormat: 包含一行十个整数，分别表示 $0\sim 9$ 在 $[a,b]$ 中出现了多少次。


title: [ZJOI2008] 无序运动

description:
D 博士对物理有着深入的研究，经典物理、天体物理、量子物理都有着以他的名字命名的定理。最近 D 博士着迷于研究粒子运动的无规则性。对圣经深信不疑的他相信，上帝创造的任何事物必然是有序的、有理可循的，而不是无规则的、混沌的。

经过长时间的研究，D 博士找到了很多出现相当频繁的轨迹片断，他把这些轨迹片断储存在一个很大的数据库内。他需要你帮助他写一个程序，对于一个给出的粒子运动轨迹，统计数据库中每个轨迹片断的出现的次数。

为清楚起见，我们定义一个粒子的轨迹为二维平面上的一个点列 $(P_1, P_2, \dots, P_N)$。点列 $P$ 的一个子列 $[i, j]$ 定义为 $P$ 中一段连续的子序列 $(P_i, P_{i + 1}, \dots, P_j)$。点列 $P$ 的一个子列 $[u, v]$ 被称为点列 $Q = (Q_1, Q_2, \dots, Q_{v - u + 1})$ 在 $P$ 中的一次出现，当且仅当 $Q$ 经过有限次的平移、旋转、翻转、放缩之后得到 $Q'$ 满足 $\forall 1 \le k \le u - v + 1$，$ Q'_k = P_{u + k - 1}$。

对点列进行四种操作的解释：
|操作名称|解释|
|:-:|:-:|
|平移|设平移向量为 $(d_x, d_y)$，则任意点 $(x, y)$ 平移后的结果为 $(x + d_x, y + d_y)$|
|旋转|设旋转角为 $t$，则任意点 $(x, y)$ 旋转后的结果为 $(x \cos t - y \sin t, x \sin t + y \cos t)$|
|翻转|任意点 $(x, y)$ 翻转后的结果为 $(x, -y)$
|放缩|设放缩比例为 $p(p \ne 0)$，则任意点 $(x, y)$ 放缩后的结果为 $(px, py)$|

inputFormat:
第一行两个整数 $N, M$，分别描述待处理的粒子运动轨迹的点列大小与数据库内的轨迹片断个数。

接下来 $M$ 行依次给出每个轨迹片断。每行先是一个正整数 $K$，表示该轨迹片断点列的长度。然后 $2K$ 个整数，依次描述点列中的 $K$ 个点的横坐标与纵坐标。

接下来一行 $2N$ 个整数，依次描述待处理的粒子运动轨迹的点列中 $N$ 个点的横坐标与纵坐标。

注：输入中的每条轨迹中任意相邻两点不会相同。

outputFormat: 应包含 $M$ 行，依次给出每个片段在待处理运动轨迹中的出现次数。

hint:
记片段总长度为 $L$。

对于 $30\%$ 的测试数据，满足 $N, M, K \le 100$，$L \le 500$;

对于 $50\%$ 的测试数据，满足 $N, M, K \le 1000$，$L \le 5000$;

对于 $100\%$ 的测试数据，满足 $N, K \le 2 \times 10 ^ 5$，$L \le 2 \times 10 ^ 6$，保证输入中给出所有点坐标绝对值均不大于 $10 ^ 4$。


title: [ZJOI2010] 网络扩容

description:
给定一张有向图，每条边都有一个容量 $c$ 和一个扩容费用 $w$。这里扩容费用是指将容量扩大 $1$ 所需的费用。求：

1. 在不扩容的情况下，$1$ 到 $n$ 的最大流；

2. 将 $1$ 到 $n$ 的最大流增加 $k$ 所需的最小扩容费用。

inputFormat:
第一行包含三个整数 $n,m,k$，表示有向图的点数、边数以及所需要增加的流量。

接下来的 $M$ 行每行包含四个整数 $u,v,c,w$，表示一条从$u$ 到 $v$，容量为 $c$，扩容费用为 $w$ 的边。

outputFormat: 输出文件一行包含两个整数，分别表示问题 $1$ 和问题 $2$ 的答案。

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

- 对于 $30\%$ 的数据，保证 $n\le 100$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 10^3$，$1\le m\le 5\times 10^3$，$1\le k\le 10$，$1 \leq u, v \leq n$。