title: [NOI2020] 制作菜品

description:
厨师准备给小朋友们制作 $m$ 道菜，每道菜均使用 $k$ 克原材料。为此，厨师购入了 $n$ 种原材料，原材料从 $1$ 到 $n$ 编号，第 $i$ 种原材料的质量为 $d_i$ 克。$n$ 种原材料的**质量之和恰好为 $m \times k$ 克**，其中 $d_i$ 与 $k$ 都是**正整数**。

制作菜品时，一种原材料可以被用于多道菜，但为了让菜品的味道更纯粹，厨师打算每道菜**至多使用 $2$ 种**原材料。现在请你判断是否存在一种满足要求的制作方案。更具体地，方案应满足下列要求：
- 共做出 $m$ 道菜。
- 每道菜至多使用 $2$ 种原材料。
- 每道菜恰好使用 $k$ 克原材料。
- 每道菜使用的每种原材料的质量都为正整数克。
- $n$ 种原材料都被恰好用完。

若存在满足要求的制作方案，你还应该给出一种具体的制作方案。

inputFormat:
**本题单个测试点包含多组测试数据**。

第一行一个整数 $T$ 表示数据组数。对于每组数据：
- 第一行三个正整数 $n, m, k$ 分别表示原材料种数、需要制作的菜品道数、每道菜品需使用的原材料的质量。
- 第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 种原材料的质量 $d_i$。

outputFormat:
对于每组测试数据：
- **若不存在满足要求的制作方案，则输出一行一个整数 $-1$**;
- 否则你需要输出 $m$ 行，每行表示一道菜品的制作方案，根据使用的原材料种数，格式为下列两种之一：
  - 依次输出一行两个整数 $i$ 和 $x$，表示该道菜使用 $x$ 克第 $i$ 种原材料制作。你应保证 $1 \leq i \leq n$，$x = k$。
  - 依次输出一行四个整数 $i$、$x$、$j$ 和 $y$，表示该道菜使用 $x$ 克第 $i$ 种原材料与 $y$ 克第 $j$ 种原材料制作。你应保证$1 \leq i, j \leq n$，$i \not= j$，$x + y = k$，$x, y > 0$。

本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。

你应保证方案输出的格式正确，且同一行中相邻的两个数使用单个空格分隔，除此之外你的输出中**不应包含其他多余字符**。


title: [NOI2020] 超现实树

type: P

background:
下课铃声响起，机房里的两位女生从座位上站起来。（下面用 $\mathbf{X1}$, $\mathbf{X2}$ 代指两人）

$\mathbf{X2}$：省选前的集训真难熬啊…… 听课、考试、讲评、补题 —— 对于现在的我来说，即使在梦里想到一道数据结构题，也会不由自主地开始思考吧。

$\mathbf{X1}$：重复训练对我来说似乎并不是什么负担，但我确实感觉到解决题目带来的愉悦感在最近逐渐减弱了。也许我们需要一些精神上的 “刺激”：一些不拘泥于繁复技术的智力游戏，来让我们找回对于数学和算法的兴趣。

$\mathbf{X2}$：咦，我好像收到了一封用英文写的短信，似乎是…… 数学书上的一些片段。

description:
$\mathbf{X1}$：我来翻译一下短信的内容。

> 定义：本文所述的树是归纳定义的：单独的结点构成一棵树，以一棵树作为左（或右）孩子可以构成一棵树，以两棵树分别作为左、右孩子也可以构成一棵树。仅由以上规则用有限步生成的所有结构被称为树。

$\mathbf{X2}$：也就是说，这里所说的树是指**非空、有根、区分左右孩子的二叉树**。

$\mathbf{X1}$：的确如此。接下来书上定义了两棵树的同构。

> 定义：称两棵树 $T$, $T^{\prime}$ 同构，记做 $T \equiv T^{\prime}$，由以下四条规则定义：
> 1. 由单独结点构成的树是彼此同构的；
> 2. 如果两棵树的根结点均只有左子树，并且它们的左子树同构，那么这两棵树是同构的；
> 3. 如果两棵树的根结点均只有右子树，并且它们的右子树同构，那么这两棵树是同构的；
> 4. 如果两棵树的根结点均有左、右子树，并且它们的左、右子树分别对应同构，那么这两棵树是同构的。
>
> 很明显，同构关系构成了所有树上的一个等价关系。为了方便，我们将同构的树看作相同的树。

$\mathbf{X2}$：将同构的树看成相同的树就是说树的结点是彼此相同的。简单地说，两棵树同构当且仅当**他们在结点无标号、区分左右孩子的意义下相同**；我们说两棵树不同，当且仅当它们不同构。

$\mathbf{X1}$：书里还定义了树的**叶子**：和通常的定义一样，叶子指**没有任何孩子的结点**。

$\mathbf{X2}$：这和我们熟悉的定义完全一致。嘛，数学家真是有点啰嗦…… 恐怕只有 $\mathbf{X3}$ 那种家伙会喜欢这种做派吧。

$\mathbf{X1}$：我倒是对此不太反感 —— 比起基于经验的 “直觉”，准确的定义和严谨的证明还是更加让人安心。你看，下一个定义就没有那么直观了。

> 定义：称一棵树 $T$ **单步替换**成为 $T^{\prime}$，如果将 $T$ 的某一**叶子结点**替换为另一棵树 $T^{\prime \prime}$ 得到的树与 $T^{\prime}$ 同构，记做 $T \rightarrow T^{\prime}$；称一棵树 $T$ **替换**成为 $T^{\prime}$，记做 $T \rightarrow^{\star} T^{\prime}$，如果存在自然数 $n \geq 1$ 和树 $T_{1}, T_{2}, \ldots, T_{n}$，使得 $T \equiv T_{1} \rightarrow T_{2} \rightarrow \cdots \rightarrow T_{n} \equiv T^{\prime}$。

$\mathbf{X2}$：我来想想…… 所谓替换，就是删掉某个叶子结点并在对应的位置放入另一棵树，就像那个叶子结点 “长出了” 一个更大的子树一样；一棵树替换成为另一棵树，说明它可以经由**零次、一次或多次**单步替换得到那棵树。哦…… 我明白了！举例来说，任何一棵树都可以替换成它本身，换言之对于树 $T$，都有 $T \rightarrow^{\star} T^{\prime}$。下面这个图片可以帮助理解单步替换和替换的含义。

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

$\mathbf{X1}$：你说得对。特别地，任何一棵树都可以替换得到无穷多棵不同的树，并且仅有一个结点构成的树可以替换得到任意其他的树。书上也有定义这样的东西。

> 定义：对于一棵树 $T$，定义 $\operatorname{grow}(T)$ 表示 T 所能替换构成的树的集合，即 $\operatorname{grow}(T)=\left\{T^{\prime} \mid T \rightarrow^{\star} T^{\prime}\right\}$。更近一步，如果 $\mathscr{T}=\left\{T_{1}, T_{2}, \ldots, T_{n}\right\}$ 是一个树的有限集合，定义 $\operatorname{grow}(\mathscr{T})$ 为所有 $\operatorname{grow}\left(T_{i}\right)$ 的并集，其中 $i=1,2, \ldots, n$。即
> $$\operatorname{grow}(\mathscr{T})=\bigcup_{T_{i} \in \mathscr{T}} \operatorname{grow}\left(T_{i}\right)$$

$\mathbf{X2}$：我们把 $\operatorname{grow}(\mathscr{T})$ 称作树的集合 $\mathscr{T}$ **所生长得到的集合**吧 —— 也就是说，树的集合 $\mathscr{T}$ 所生长得到的集合包含所有可以被某个 $T \in \mathscr{T}$ 替换得到的树。不妨把树的集合叫做**树林**。不太严谨地说，一个树林所生长得到的新树林就是其中所有树、以所有可能的方式生长得到的树林。显而易见，一个非空树林所生长得到的树林都是无穷树林。但这个无穷树林，或者说 $\operatorname{grow}(\mathscr{T})$，并不一定包含所有的树 —— 更进一步，它甚至不一定包含 “几乎所有” 的树。

$\mathbf{X1}$：让我来补充一下：我们称一个树林是**几乎完备**的（或称**几乎包含了所有的树**），如果仅有有限多的树不在其中。对于一个有限树林 $\mathscr{T}$，$\operatorname{grow}(\mathscr{T})$ 要么包含了所有的树，要么包含了几乎所有的树，要么存在无穷多棵树不在其中。如果这是一道 OI 题，出题人一定会**在样例中给出三种情况的例子**吧。书上的关键定理也用了和我们相同的定义。

> **定理**（**几乎完备的可判定性**）：一个树的集合是**几乎完备**的，如果仅有有限棵树不在其中。那么，对于一个给定的树的有限集合 $\mathscr{T}$，存在高效的算法判定 $\operatorname{grow}(\mathscr{T})$ 是否是几乎完备的。

$\mathbf{X2}$：这个问题变成一个纯粹的 OI 题目了！让我用我们的语言来重述一下题意：**给定一个有限大小的树林 $\mathscr{T}$，判定 $\operatorname{grow}(\mathscr{T})$ 是否是几乎完备的，即是否仅有有限棵树不能被树林中所包含的树生长得到**。

$\mathbf{X1}$：也就是说，给定一个有限的树的集合 $\mathscr{T}$，判定是否仅有有限个树 $T$，满足 $T \notin \operatorname{grow}(\mathscr{T})$。所谓 $T \notin \operatorname{grow}(\mathscr{T})$，就是说不存在 $T^{\prime} \in \mathscr{T}$，使得 $T^{\prime} \rightarrow^{\star} T$。这和通常的 OI 题目的确非常不同：我甚至没有想到这个问题的一个算法。

$\mathbf{X2}$：我也一样，不过我很久没有感受到这种解决未知问题的冲动了。

inputFormat:
本题有多组测试数据，输入文件的第一行包含一个正整数 $N$，表示测试数据的组数。接下来包含恰好 $N$ 组测试数据，每组测试数据具有以下的格式：

第一行是一个正整数 $m$，表示树的集合中树的个数。接下来按照以下格式输入 $m$ 棵树：
- 首先是一个正整数 $n$，表示树中的结点个数，结点编号为 $1,2, \ldots, n$；
- 接下来 $n$ 行每行两个非负整数，其中第 $i$ 行从左到右包含用空格隔开的 $l_i$ 和 $r_i$，分别表示 $i$ 号结点左、右孩子结点的编号。如果左（或右）孩子不存在，那么 $l_i$（或 $r_i$）为 $0$。当然，叶结点一定满足 $l_i = r_i = 0$。
- 输入数据保证构成一棵以 $1$ 号结点作为根结点的树。**请注意**：结点的编号只是为了方便输入，任何同构的树都被视为是相同的。

所输入的 $m$ 棵树中可能存在彼此同构的树；如果去除这些重复的树（即每种同构的树只留下一个），它们可以构成一个树的集合 $\mathscr{T}$。你需要判定这一树的集合所生长得到的集合 $\operatorname{grow}(\mathscr{T})$ 是否是几乎完备的。

outputFormat: 输出包含 $N$ 行，分别表示 $N$ 组测试数据的答案。其中，第 $i$ 行输出一个字符串：如果第 $i$ 组测试数据所输入的树的集合所生长得到的集合是几乎完备的（换言之，仅有有限棵树不能被其生长得到），那么输出 `Almost Complete`；否则输出 `No`。**请注意输出字符串的拼写和大小写**。

hint:
#### 样例 2 解释
这一样例仅包含一组测试数据，其中树的集合 $\mathscr{T}$ 包含三棵树，如下图所示。容易发现，仅有单个结点构成的树不在 $\operatorname{grow}(\mathscr{T})$ 中，其包含了几乎所有树，因而是几乎完备的。

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

#### 样例 3 解释
这一样例仅包含一组测试数据，其中树的集合 $\mathscr{T}$ 包含两棵树。容易发现，对于所有的 $n \geq 2$，包含 $n$ 个结点，每个非叶结点仅有右孩子的链状树都不在 $\operatorname{grow}(\mathscr{T})$ 中，因而存在无穷多棵树不在 $\operatorname{grow}(\mathscr{T})$ 中，$\mathscr{T}$ 不是几乎完备的。

#### 样例 4
见选手目录下的 surreal/surreal4.in 与 surreal/surreal4.ans。

---

### 测试点约束

**全部数据满足**：$\sum n \leq 2 \times 10^{6}$， $\sum m \leq 2 \times 10^{6}$， $\max h \leq 2 \times 10^{6}$， $N \leq 10^{2}$。其中，$\sum n$ 表示这一测试点所有测试数据中所出现的所有树的结点个数之和；$\sum m$ 表示这一测试点中所有测试数据中所出现的树的个数；$\max h$ 表示这一测试点中所出现的所有树的最高高度（仅包含一个结点的树高度为 $1$）。下表中的表项 $\sum n$，$\sum m$ 和 $\max h$ 含义与上面相同，描述了每一组测试点的数据范围。

**特殊性质**：下面是下表中会涉及的四种特殊性质的解释。
- 特殊性质 $1$：对于这一测试点中的每一组测试数据，都有 $m \leq 4$，即树的集合中包括不超过 $4$ 棵树；
- 特殊性质 $2$：对于这一测试点中的每一组测试数据，树的集合中所有的树具有相同的高度；
- 特殊性质 $3$：对于这一测试点中的每一组测试数据，树的集合仅包含链（换言之，每个非叶结点仅包含一个孩子）；
- 特殊性质 $4$：对于这一测试点中的每一组测试数据，树的集合仅包含满足以下两个条件之一的树：
  - 每个非叶结点仅包含一个孩子；
  - 恰好有两个叶结点，它们具有相同的父结点，并且除这三个结点外，其余结点均有且仅有一个孩子。

每个测试点的具体限制见下表：

| 测试点编号 |  $N$ |  $\sum n$ |  $\sum m$ |  $\max h$ | 特殊性质 |
| :-: | :-: | :-: | :-: | :-: |:-:  |
|  $1$ |  $100$ |  $\le 10^3$ |  $\le 10^3$ |  $\le 1$ | 无 |
|  $2\sim 3$ |  $100$ |  $\le 10^3$ |  $\le 10^3$ |  $\le 2$ | 性质  $1$ |
|  $4$ |  $100$ |  $\le 10^6$ |  $\le 10^6$ |  $\le 4$ | 无 |
|  $5$ |  $100$ |  $\le 10^6$ |  $\le 10^6$ |  $\le 5$ | 性质  $2$ |
|  $6$ |  $100$ |  $\le 10^6$ |  $\le 10^6$ |  $\le 8$ | 无 |
|  $7$ |  $100$ |  $\le 10^6$ |  $\le 10^6$ |  $\le 9$ | 性质  $2$ |
|  $8$ |  $100$ |  $\le 10^6$ |  $\le 10^6$ |  $\le 10$ | 无 |
|  $9$ |  $100$ |  $\le 10^6$ |  $\le 10^6$ |  $\le 10^6$ | 性质  $3$ |
|  $10$ |  $20$ |  $\le 10^3$ |  $\le 100$ |  $\le 10^3$ | 性质  $4$ |
|  $11$ |  $20$ |  $\le 2\times 10^3$ |  $\le 2\times 10^3$ |  $\le 2\times 10^3$ | 性质  $4$ |
|  $12$ |  $20$ |  $\le 10^5$ |  $\le 10^5$ |  $\le 10^5$ | 性质  $4$ |
|  $13$ |  $20$ |  $\le 2\times 10^5$ |  $\le 2\times 10^5$ |  $\le 2\times 10^5$ | 性质  $4$ |
|  $14$ |  $20$ |  $\le 800$ |  $\le 200$ |  $\le 800$ | 无 |
|  $15$ |  $20$ |  $\le 10^3$ |  $\le 100$ |  $\le 10^3$ | 无 |
|  $16$ |  $20$ |  $\le 2\times 10^3$ |  $\le 2\times 10^3$ |  $\le 2\times 10^3$ | 无 |
|  $17$ |  $40$ |  $\le 3\times 10^5$ |  $\le 3\times 10^5$ |  $\le 3\times 10^5$ | 无 |
|  $18$ |  $40$ |  $\le 6\times 10^5$ |  $\le 6\times 10^5$ |  $\le 6\times 10^5$ | 无 |
|  $19$ |  $40$ |  $\le 9\times 10^5$ |  $\le 9\times 10^5$ |  $\le 9\times 10^5$ | 无 |
|  $20$ |  $40$ |  $\le 1.2\times 10^6$ |  $\le 1.2\times 10^6$ |  $\le 1.2\times 10^6$ | 无 |
|  $21$ |  $40$ |  $\le 1.5\times 10^6$ |  $\le 1.5\times 10^6$ |  $\le 1.5\times 10^6$ | 无 |
|  $22\sim 25$ |  $40$ |  $\le 2\times 10^6$ |  $\le 2\times 10^6$ |  $\le 2\times 10^6$ | 无 |


title: [NOI2020] 翻修道路

description:
C 国中包含 $n$ 座城市，这些城市通过 $m$ 条双向道路连接。城市从 $1$ 到 $n$ 编号，道路从 $1$ 到 $m$ 编号，$i$ 号道路两端连接着城市 $u_i$ 与城市 $v_i$，它的长度为 $w_i$ 米。经由这些道路，从 C 国中任意一个城市出发，均能到达其他所有城市。

C 国人民喜欢环路旅程，但又不喜欢经过太多条道路，为此 C 国的道路被建造得非常特殊。更具体地，对于一条经过 $l$ 条道路的简单环路（即除起点城市外**不经过重复城市**的环路），它可以表示为 $c_{1} \rightarrow c_{2} \rightarrow \cdots \rightarrow c_{l} \rightarrow c_{1}$（其中对于所有 $1 \leq i<l$，城市 $c_i$ 与城市 $c_{i+1}$ 有道路相连；城市 $c_l$ 与城市 $c_1$ 有道路相连；对于所有 $1 \leq i<j \leq l$，有 $c_{i} \neq c_{j}$），若 $l > 3$，则 C 国的道路将满足下列条件：
  - 存在两个在该环路上**不相邻**的城市 $u$, $v$，满足两个城市间有道路直接相连。即：存在 $1 \leq u<v \leq l$，使得 $v-u \geq 2$，$u$ 和 $v$ 不同时为 $1$ 和 $l$，并且城市 $c_u$ 与城市 $c_v$ 间有道路直接相连。

现在 C 国有了新的翻修计划，需要在城市 $s$ 与城市 $t$ 间寻找一条路径进行翻修。翻修时路径中包含的所有道路将无法通行，为了保障人民的日常生活，C 国希望在翻修这条路径时，经由**剩余**的道路（即没被包含在翻修路径内的道路）依然能满足：**从 C 国中任意一个城市出发，均能到达其他所有城市**。

C 国找到了身为工程大师的你，请你帮助 C 国找出一条满足上述要求的翻修路径，并使得这条路径的总长**尽量小**。

inputFormat:
第一行两个整数 $n$, $m$ 分别表示城市个数与道路条数。

接下来 $m$ 行每行三个整数 $u_i$, $v_i$, $w_i$，依次表示每条道路的两个端点与它的长度。

数据保证每条道路都一定连接两个不同城市，即 $u_i \not= v_i$。

最后一行两个整数 $s$, $t$，分别表示需要翻修的路径的两个端点。

outputFormat:
仅一行一个整数，表示满足题目要求的情况下，翻修路径的总长的最小值。

**如果不存在满足题目要求的路径，输出一行一个整数$-1$。**

hint:
#### 样例 1 解释

路径 $(1,2,1),(2,3,1),(3,4,1)$ 是城市 $1$ 和城市 $4$ 间总长最小的路径，但不符合要求。

路径 $(1,3,5),(3,4,1)$ 符合要求，长度为 $6$。

路径 $(1,2,1),(2,4,6)$ 符合要求，长度为 $7$。

除上述两条路径外，没有其他满足要求的路径。

#### 样例 3

见选手目录下的 road/road3.in 与 road/road3.ans。该样例与测试点 $1 \sim 6$ 限制相同。

#### 样例 4

见选手目录下的 road/road4.in 与 road/road4.ans。该样例与测试点 $7 \sim 10$ 限制相同。

#### 样例 5

见选手目录下的 road/road5.in 与 road/road5.ans。该样例与测试点 $11 \sim 15$ 限制相同。

#### 样例 6

见选手目录下的 road/road6.in 与 road/road6.ans。该样例与测试点 $16 \sim 20$ 限制相同。

*然而，后面三个样例太大了，传不上来。。。*

---

### 测试点约束

对于所有测试点：$2 \leq n \leq 5 \times 10^{5}$，$2 \leq m \leq 10^{6}$，$s \neq t$。

$1 \leq u_{i}, v_{i} \leq n$，$u_{i} \neq v_{i}$，$1 \leq w_{i} \leq 10^{9}$，保证任意两条道路它们的端点不全相同。

保证给出的道路满足题面描述第二段中的性质。

每个测试点的具体限制见下表：

| 测试点编号 |  $n\le $ |  $m\le $ | 特殊限制 |
| :-: | :-: | :-:| :-: |
|  $1\sim 6$ |  $2\times 10^3$ |  $4\times 10^3$ | 无 |
|  $7\sim 10$ |  $5\times 10^5$ |  $10^6$ |  $\text{A}$ |
|  $11\sim 15$ |  $5\times 10^5$ |  $10^6$ |  $\text{B}$ |
|  $16\sim 20$ |  $5\times 10^5$ |  $10^6$ | 无 |

特殊限制 A：所有道路的长度均相等。

特殊限制 B：所有 $w_i = 1$ 的道路恰好构成 $s$ 到 $t$ 的一条路径，且其他 $w_i \not= 1$ 的道路的两条端点在这条路径上距离为 $2$。


title: [JOISC2020] 収穫

background: JOI 君是 IOI 庄园的庄园主。

description:
现在 IOI 庄园有 $N$ 名员工，在周长为 $L$ 的湖的湖岸边有 $M$ 棵苹果树。

第 $i$ 名员工从湖的最北点顺时针走了 $A_i$ 米，第 $i$ 棵苹果树长在从湖的最北点顺时针的 $B_i$ 米。

因为特殊原因，每棵苹果树上最多长一个苹果，初始时刻每棵苹果树上都有 $1$ 个苹果，如果一棵树上的苹果被摘掉了，在恰好 $C$ s 后会长出一个苹果。

每名员工在初始时刻都在自己原本的位置，每过一个时刻就会顺时针走 $1$ 米，遇到有成熟苹果的苹果树就会把苹果摘下来。

现在 JOI 君给定了 $Q$ 个询问，第 $i$ 个询问为：

- 询问第 $V_i$ 个员工在时刻 $T_i$ 结束后收获到几个苹果。

inputFormat:
第一行四个整数 $N,M,L,C$ 代表员工数，苹果树数，湖的周长，苹果每隔一定时间成熟。
第二行 $N$ 个整数 $A_i$ 如题目所示。
第三行 $M$ 个整数 $B_i$ 去题目所示。
第四行一个整数 $Q$ 代表询问次数。
接下来 $Q$ 行每行两个整数 $V_i,T_i$ 代表一个询问。

outputFormat: $Q$ 行每行一个整数代表答案。

hint:
#### 样例 1 解释

- 在时刻 $1$：
	- 员工 $2$ 到达第 $2$ 棵苹果树，并采摘了成熟的苹果
    - 员工 $3$ 到达第 $1$ 棵苹果树，并采摘了成熟的苹果
- 在时刻 $3$：
	- 员工 $2$ 到达第 $1$ 棵苹果树，但没有成熟的苹果

到时刻 $3$ 结束后，员工 $2$ 共采摘了 $1$ 个苹果，对应样例 $1$ 的第 $2$ 个询问。

- 在时刻 $4$：
	- 员工 $1$ 到达第 $2$ 棵苹果树，并采摘了成熟的苹果
- 在时刻 $6$：
	 - 员工 $1$ 到达第 $1$ 棵苹果树，并采摘了成熟的苹果
     - 员工 $3$ 到达第 $2$ 棵苹果树，但没有成熟的苹果

到时刻 $7$ 结束后，员工 $1$ 共采摘了 $2$ 个苹果，对应样例 $1$ 的第 $1$ 个询问。

- 在时刻 $8$：
	- 员工 $2$ 到达第 $2$ 棵苹果树，并采摘了成熟的苹果
    - 员工 $3$ 到达第 $1$ 棵苹果树，但没有成熟的苹果

到时刻 $8$ 结束后，员工 $3$ 共采摘了 $1$ 个苹果，对应样例 $1$ 的第 $3$ 个询问。

#### 子任务

|子任务|特殊性质|分数|
|:-:|:-:|:-:|
|$1$|$N,M,Q \le 3000$|$5$|
|$2$|$T_i \ge 10^{15}$|$20$|
|$3$|无|$75$|

对于 $100\%$ 的数据，$1 \le N,M,Q \le 2 \times 10^5$，$N+M \le L$，$1 \le C,L \le 10^9$，$0 \le A_i,B_i < L$，$A_i<A_{i+1}$，$B_i<B_{i+1}$，$A_i \ne B_i$，$1 \le V_i \le N$，$1 \le T_i \le 10^{18}$。

#### 说明

翻译自 [第１９回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day3 B 収穫](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day3/harvest.pdf)。


title: [Ynoi2009] rpdq

description:
给定一棵 $n$ 个节点的无根，有边权的树，每个点有个编号，编号为一个 $1 \sim n$ 的排列。

共 $m$ 组询问，每次询问给出 $l,r$，求所有点编号的二元组 $(i,j)$ 满足 $l \le i<j \le r$ 在树上的距离的和，两个点的距离定义为连接其的简单路径上的所有边的边权和。

inputFormat:
第一行两个空格隔开的数 $n$ $m$。

之后 $n-1$ 行，每行三个空格隔开的数 $u$ $v$ $d$ 表示一条 $u$ 和 $v$ 之间边权为 $d$ 的边。

之后 $m$ 行，每行两个空格隔开的数 $l$ $r$ 表示一次询问。

outputFormat: 共 $m$ 行，表示每个询问对应的答案，答案对 $2^{32}$ 取模。

hint:
Idea：nzhtl1477，Solution：nzhtl1477，Code：zx2003，Data：nzhtl1477

对于 $100\%$ 的数据，$1\le n,m,d\le 2\cdot 10^5$，所有数值均为整数。


title: [Ynoi2009] rla1rmdq

description:
给定一棵 $n$ 个节点的树，树有边权，与一个长为 $n$ 的序列 $a$。

定义节点 $x$ 的父亲为 $fa(x)$，根 $rt$ 满足 $fa(rt)=rt$。

定义节点 $x$ 的深度 $dep(x)$ 为其到根简单路径上所有边权和。

有 $m$ 次操作：

`1 l r`：对于 $l \le i \le r$， $a_i := fa(a_i)$ 。

`2 l r `：查询对于 $l \le i \le r$，最小的 $dep(a_i)$。

inputFormat:
第一行三个空格隔开的数 $n$ $m$ $rt$，其中 $rt$ 表示根节点的编号。

之后 $n-1$ 行，每行三个空格隔开的数 $u,v,w$ 表示一条 $u$ 与 $v$ 之间，边权为 $w$ 的边。

之后一行 $n$ 个空格隔开的数表示这个序列。

之后 $m$ 行，每行三个用空格隔开的数，表示一次操作。

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

hint:
Idea：yummy，Solution：nzhtl1477&memset0，Code：nzhtl1477，Data：nzhtl1477

对于 $100\%$ 的数据，$1\le n,m\le 2\cdot 10^5$，$1\le a_i\le n$，边权在 $[0,10^9]$ 之间。


title: [Ynoi2008] rsmemq

description:
给定一个长为 $n$ 的序列 $a$，定义 $x$ 为区间 $[l, r]$ 的众数当且仅当不存在 $y$ 使得 $y$ 在区间 $[l, r]$ 中的出现次数**大于** $x$ 在区间 $[l,r]$ 中的出现次数。

有 $m$ 次询问，每次询问给出 $l, r$，求有多少二元组 $(l',r')$ 满足 $l\le l'\le r'\le r$，且 $[l', r']$ 的区间长度为奇数，且 $(l' + r') / 2$**（注意这里是下标而不是下标对应的值）**是区间 $[l', r']$ 中的众数。

inputFormat:
输入的第一行包含两个数 $n$，$m$。

之后一行 $n$ 个数表示这个序列。

之后 $m$ 行，每行两个数 $l$，$r$ 表示一次询问。

outputFormat: 输出共 $m$ 行，表示每个询问对应的答案。


title: [COCI2019-2020#1] Trol

description:
Stjepan 最近在萨格勒布大学获得了数学学士学位。他的父母自然而然地为他感到骄傲，并决定给他所有不超过 $2^{60}$ 的正整数作为礼物。为了保证它们的安全，他迅速地将所有数存入了一个序列 $A$，使得 $A_i=i$。

一个妒忌他的朋友 Marin 决定做一个恶作剧：**不断地把 $A$ 中的每个元素替换为其所有数位之和，直到最终只剩下一位数。**

例如，第 $197$ 个元素的初始值为 $197$。Marin 先将这个值变为 $1+9+7=17$，然后再一次改变了它，使其变为 $1+7=8$。

Stjepan 对此极为震惊，并请求 Marin 把序列变回初始状态。不幸的是，在他正确回答 $Q$ 个询问之前，Marin 并不会如此。对于每一个询问，Stjepan 需要回答 $A$ 序列中第 $l$ 项至第 $r$ 项元素的总和。

来帮 Stjepan 回答这些询问吧！

inputFormat:
第一行包含一个整数 $Q$，表示询问次数。

接下来的 $Q$ 行，每行包含两个正整数 $l_i,r_i$，表示 Marin 第 $i$ 次询问的区间范围。

outputFormat: 输出 $Q$ 个询问的答案。答案之间应当用换行符两两分开，并且应当符合询问的顺序。

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

对于 $20\%$ 的数据，所有询问满足 $1 \le l_i \le r_i \le 9$。

对于 $60\%$ 的数据，所有询问满足 $r_i-l_i \le 1000$。

对于 $100\%$ 的数据，$1 \le Q \le 100$，所有询问满足 $1 \le l_i \le r_i \le 2^{60}$。

#### 说明

**本题分值按 COCI 原题设置，满分 $50$。**

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf)  _T1 Trol_ 。**


title: Tram

background:
电车开了，他的声音在我的脑海中萦绕不散：

「留下来，跟我来。」

我回头去看车站，他不见了。

我在德辅道寻找他的身影。

路人不多，但他却消失了。

我把窗拉下来，微风轻拂我的脸。

他到哪儿去了？

路人、街道、高楼大厦。

在我身边轻轻地流走。

description:
你就要出道了！

你的教练和同学为你联系了摄影师，你们来到德辅道边拍宣传照。

街上一共有 $n$ 幢楼房，从左到右排成一列，从 $1$ 到 $n$ 编号，编号为 $i$ 的楼房的高度是 $a_i$。

一张照片可以用二元组 $(l,r)$ 描述，其中 $1\le l\le r\le n$，这张照片中包含了编号在 $[l,r]$ 之间的所有楼房。

摄影师认为，一张照片是美丽的，当且仅当其同时满足下面的两个条件：

- 对于任意的 $i<j<k$，如果高度为 $i$ 和 $k$ 的楼房都在照片中出现过，那么高度为 $j$ 的楼房也在照片中出现过。
- 对于任意的 $i$，高度为 $i$ 的楼房要么不出现在照片中，要么在照片中出现恰好 $i$ 次。

摄像师问你，一共能拍出多少不同的美丽的照片呢？

两张照片 $(l_1,r_1)$ 和 $(l_2,r_2)$ 不同，当且仅当 $l_1\ne l_2$ 或 $r_1\ne r_2$。

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

随后一行 $n$ 个正整数，第 $i$ 个为编号为 $i$ 的楼房的高度。

outputFormat: 输出一行一个整数表示能拍出的不同的美丽的照片数量。

hint:
**本题采用捆绑测试**。你只有通过 subtask 中的所有测试点才能获得该 subtask 的分数。

- Subtask 1(10 points)：$n\le 200$；
- Subtask 2(5 points)：$n\le 1000$；
- Subtask 3(10 points)：$n\le 6000$；
- Subtask 4(20 points)：$n\le 3\times 10^4$；
- Subtask 5(30 points)：$n\le 10^5$；
- Subtask 6(25 points)：$n\le 10^6$。

对于所有数据满足：$1\le n,a_i\le 10^6$。

注意答案的大小可能超过 $32$ 位有符号整数的范围。

本题输入数据量较大，请使用较快的读入方式。


title: Mex

background: 忘掉种过的花/重新的出发/放弃理想吧。

description:
小 G 曾经有一个 $0$ 到 $n$ 的排列（下标从 $0$ 开始），但他忘记了这个排列。

现在他想把这个排列找回来，他努力地回想，只能回想起关于这个排列的 $m$ 条信息，每条信息形如 $(l,r,val)$，表示区间 $[l,r]$ 的 ${\rm mex}$ 值为 $val$。一个区间的 ${\rm mex}$ 值是最小的没有在这个区间中出现的自然数。

小 G 把 $n$ 和这 $m$ 条信息告诉了你，希望你能帮他还原出一个排列，或者告诉他他的回忆出现了问题。

inputFormat:
第一行两个整数 $n$ 和 $m$，含义见上。

随后 $m$ 行每行三个整数 $l,r,val$ 描述一条信息，表示区间 $[l,r]$ 的 ${\rm mex}$ 值为 $val$。

outputFormat:
如果不存在满足所有条件的排列，输出 $-1$。

否则输出一行 $n+1$ 个正整数，表示一个 $0$ 到 $n$ 的排列。

**本题采用 Special Judge**。如果满足条件的排列有多个，你可以输出任意一个。

hint:
**本题采用捆绑测试**。你只有通过 subtask 中的所有测试点才能获得该 subtask 的分数。

- Subtask 1(15 points)：$n,m\le 10$；
- Subtask 2(20 points)：$n,m\le 20$；
- Subtask 3(10 points)：$val=0$；
- Subtask 4(15 points)：数据随机生成；
- Subtask 5(10 points)：$n\le 10^5$；
- Subtask 6(30 points)：无特殊限制。

对于所有的数据满足：$1 \le n,m\le 5\times 10^5$，$ 0\le l,r\le n$，$0\le val\le n+1$。

Subtask4 的数据生成方式为：随机生成一个排列，再随机 $m$ 个区间求出它们的 ${\rm mex}$ 值作为条件。

本题输入输出量较大，请注意使用效率较高的 IO 方式。


title: [COCI2019-2020#1] Lutrija

background:
Vedran 在赌输彩票之后，无意之间打开了 COCI 的频道。只要完成 COCI 给出的任务，他就能够免除前往新加坡 IOI2020 现场的费用。

不幸的是，Vedran 已经老了，于是你决定帮帮他。

description: 给定两个素数 $A,B$。你需要给出一个开头和结尾分别为 $A$ 和 $B$ 的序列，使得其所有元素均为素数，并且相邻两个元素之间的差值也为素数。

inputFormat: 输入两个素数 $A,B$。

outputFormat:
如果任务不可能完成，即没有满足条件的序列（以下称为有解），则只输出 `-1`。

否则，在第一行输出序列的元素个数，并在第二行输出所有元素。

如果有解，则你的构造必须满足下列二者之一：

- 序列元素个数不超过 $30$
- 任何一个元素都不超过 $10^{15}$。

如果有多组解，则输出任意一种。

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

对于 $20\%$ 的数据，如果有解，则必定有一种解，满足元素的个数不超过 $3$，且其中的所有元素都不超过 $1000$。

对于另外 $40\%$ 的数据，$2 \le A,B \le 1000$。

对于 $100\%$ 的数据，$2 \le A,B \le 10^{14},A \neq B$。

#### 说明

**本题分值按 COCI 原题设置，满分 $70$。**

由于平均下来每个测试点为 $2.5$ 分，因而将其中一半的测试点设置为 $2$ 分，另一半设置为 $3$ 分。

本题使用非官方的 [Special Judge](https://www.luogu.com.cn/paste/hrj05be5)，欢迎大家 hack（可私信或直接发帖）。

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf)  _T2 Lutrija_ 。**


title: [COCI2019-2020#1] Džumbus

background:
Marin 是一个心地善良的人，因此他将为他的 $N$ 个朋友组织 $Q$ 次宴会。宴会上唯一的饮料被称为 _džumbus_。

每位朋友对这种饮料的需求量是已知的。在这些朋友中，有 $M$ 组朋友。每一组中的两位在同时满足他们各自的需求量后，将开始互相核对自己对往届 COCI 题目的答案。

当朋友 $A$ 把自己的答案分享给朋友 $B$ 时，朋友 $B$ 可以决定是否要以相同的方式进行分享。然而，这 $M$ 组朋友不可能将 $A$ 分享给别人的答案重新分享给 $A$。

description:
Marin 为每一次宴会准备了不同单位量的 džumbus。在每次宴会的过程中，他想要使分享给别人答案至少一次的朋友数量最多。

你的任务是找到会与别人分享答案的朋友的最大数量。

inputFormat:
第一行包含题中所提到的两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，其中第 $i$ 个整数为 $D_i$，表示第 $i$ 个朋友对这种饮料的需求量。

接下来的 $M$ 行，每行包含两个整数 $A_i,B_i$（$A_i \neq B_i$），表示第 $i$ 对朋友。

接下来的一行，包含整数 $Q$。

接下来的 $Q$ 行，每行包含一个整数 $S_i$ 表示第 $i$ 次宴会的饮料总量。

outputFormat:
分别输出每次宴会的答案，即会与别人分享答案的朋友的最大数量。

每两次宴会的答案之间用换行符分开。

hint:
#### 样例解释

在第三个样例中的第一个宴会过程中，Marin 决定让编号为 $1,2,3,7,9,10,12,13$ 的朋友达到各自的需求量。他们总共饮用了 $45$ 个单位的饮料。

如下图，建立一个无向图，用点来表示朋友，用边表示二者是否为一组。其中 exchange 表示两个朋友之间交换答案。

![](https://cdn.luogu.com.cn/upload/image_hosting/37y5ctim.png?x-oss-process=image/resize,m_lfit,h_377,w_438)

#### 数据范围及约定

| Subtask | 分值 | 数据范围及约定 | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $20$ | $M = N - 1, 1 \le S_i \le 1000$ | 每位朋友最多只与两位其他朋友分享答案 |
| $2$ | $30$ | $M = N - 1$ | 每位朋友最多只与两位其他朋友分享答案 |
| $3$ | $30$ | $N \le 100$ | 无 |
| $4$ | $30$ | 无 | 无 |

对于 $100\%$ 的数据，$0 \le M \lt N \le 1000, 1 \le Q \le 2 \times 10^5, 1 \le D_i \le 10^9, 1 \le S_i \le 10^9$。

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf)  _T3 Džumbus_ 。**


title: [Ynoi2008] rupq

description:
给定一个长为 $n$ 的括号序列，每个位置有一个括号 $a_i$，其中 $a_i=1$ 代表是左括号 $'('$，$a_i=0$ 代表是右括号 $')'$。 $a_i$ 位置的括号有一个权值 $b_i$。

对任意括号序列，通过不断删除形如 $'()'$ 的子段直到无法操作，最终可以得到一个唯一的序列，这个序列称为不匹配括号，如 $a_1=')',a_2='(',a_3='(',a_4=')',a_5='('$，这个括号序列的不匹配括号序列为 $')(('$，其不匹配括号对应位置为 $1,2,5$，其不匹配括号对应位置的 $b$ 为 $b_1,b_2,b_5$。

有 $m$ 次操作，操作有以下三类：

`1 x y`：进行单点修改，即 $a_x:=1-a_x; b_x:=y$。

`2 l r`：求 $a[l..r]$ 中不匹配括号对应位置的 $b$ 从左到右的 $\texttt {NAND}$ （$32$ 位的按位与非，可以见 https://en.wikipedia.org/wiki/NAND_logic ）， $\texttt {max}$（最大值） ，将二者 $\texttt {xor}$ 后输出。如果不匹配括号为空序列，则 $\texttt {NAND}$ 的答案为 $2^{32}-1$， $\texttt {max}$ 的答案为 $0$。

$\texttt {NAND}$ 即以 $c_0=2^{32}-1$ 为初值，然后依次 $c_i=\texttt {NAND}(c_{i-1},b_i)$，对于一个 $n$ 个值的序列 $b$，最后答案为 $c_n$。

`3 l r`：将 $a[l..r]$ 和 $a[r+1..n]$ 交换位置，$b$ 也做同样的操作。

inputFormat:
第一行用空格隔开的两个数 $n,m$。

之后 $n$ 行每行用空格隔开的两个数，第 $i$ 行为 $a_i,b_i$。

之后 $m$ 行，每行表示一个操作。

outputFormat: 对每个操作 $2$ 输出一行表示答案。

hint:
Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：nzhtl1477

对于 $100\%$ 的数据，

$0 \le a[i] \le 1$。

$0 \le b[i] \le 10^9$。

$1 \le n \le 2\times10^6,1 \le m \le 2\times10^5$。


title: [Ynoi2008] rplexq

description:
给定一棵 $n$ 个节点的有根树，第 $i$ 个点的编号是 $i$。

有 $m$ 次询问，每次询问给出 $l,r,x$，求有多少点编号的二元组 $(i,j)$ 满足 $l \le i < j \le r$ 且 $i$ 和 $j$ 的最近公共祖先是节点 $x$。

inputFormat:
第一行三个数 $n$ $m$ $rt$，其中 $rt$ 表示根节点的编号。

之后 $n-1$ 行，每行两个数 $u$ $v$ 表示一条边。

之后 $m$ 行，每行三个数 $l$ $r$ $x$ 表示一次询问。

outputFormat: 共 $m$ 行，表示每个询问对应的答案


title: [Ynoi2008] rrusq

description:
给定一个二维平面，有 $n$ 个关键点，$m$ 个矩形，以及 $q$ 个询问，每个关键点有一个权值 $a_i$。

定义一个左下角为 $(x_i,y_i)$，右上角为 $(x'_i,y'_i)$ 的矩形包含一个点 $a,b$，当且仅当 $x_i\le a\le x'_i$ 且 $y_i\le b\le y'_i$。

每次询问给定 $[l,r]$，对于一个关键点 $i$ ，如果点 $i$ 在编号在 $[l,r]$ 内的任意一个矩形中，则认为 $i$ 被区间 $[l,r]$ 的矩形并包含，输出区间 $[l,r]$ 的矩形并包含的所有关键点的权值和。

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

之后 $n$ 行每行两个元素 $p_i,a_i$，表示第 $i$ 个关键点 $(i,p_i)$，权值为 $a_i$，保证 $p$ 为一个 $1$ 到 $n$ 的排列。

之后一行一个数 $m$。

之后 $m$ 行每行四个元素 $x_i,x'_i,y_i,y'_i$，表示第 $i$ 个矩形左下角为 $(x_i,y_i)$，右上角为 $(x'_i,y'_i)$。

之后一行一个数 $q$。

之后 $q$ 行每行两个元素 $l,r$，表示一次对区间 $[l,r]$ 的询问。

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

hint:
Idea：nzhtl1477&ccz181078，Solution：zx2003，Code：ccz181078，Data：nzhtl1477

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $5\%$ 的数据，为样例 1。

对于另外 $14\%$ 的数据，$q=1$。

对于另外 $19\%$ 的数据，$n,m,q\leq 500$。

对于另外 $19\%$ 的数据，$n,m\leq 500$。

对于另外 $19\%$ 的数据，$n,m,q\leq 2000$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$1\leq q \leq 10^6$。

$1\leq a_i \leq 10000$，$1\leq x_i\leq x_i'\leq n$，$1\leq y_i\leq y_i'\leq n$，$1\leq l\leq r\leq m$。


title: 「MCOI-03」正方

background:
MC 中没有圆。

所以小 S 和小 Q 和小 U 和小 A 和小 R 和小 E 喜欢 Square。

description:
给定一个正方形，求有多少个正方形内的点满足与正方形四个顶点划分出来的四块面积的比为 $a:b:c:d$。四个数不分顺序。

比如如下图所示假设一个点 E 使得分成的四个三角形的面积之比为 $a:b:c:d$，那么这个点 E 就符合要求。因为不分顺序，所以分出来的比是 $d:b:a:c$ 也可以。但是点 E 不是唯一解，你要输出的是解的个数。

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

因为小 S 和小 Q 和小 U 和小 A 和小 R 和小 E 很喜欢询问，所以本题给定了 $q$ 组询问。

inputFormat:
第一行一个整数 $q$ 代表询问个数。
接下来 $q$ 行每行四个整数 $a,b,c,d$。

outputFormat: $q$ 行每行一个整数代表答案。

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

对于 $20\%$ 的数据，$a=b=c=d$。
对于 $100\%$ 的数据，$1 \le a,b,c,d \le 9 \times 10^{18}$，$1 \le q \le 100$，不保证 $a:b:c:d$ 为最简比，不保证 $a,b,c,d$ 为升序。


title: [COCI2019-2020#1] Trobojnica

description:
> "Everything will be in flames once red, white, and blue start running through your veins." - Slaven Bilić

在该任务中，我们将会研究一些多边形，它们具有 $N$ 条被涂成颜色的边（总共有三种颜色），而顶点的编号沿顺时针依次为 $1$ 至 $N$。

你的任务是找到一个多边形的三角形分割方式，即将一个多边形沿对角线分成 $N-2$ 个三角形，使得多边形的每个三角形的三条邻边都各分别为三种不同的颜色。

inputFormat:
第一行包含一个题中所提的整数 $N$。

第二行是一个共有 $N$ 个数位的整数，表示该多边形各边的颜色。其第一位表示边 $(1,2)$ 的颜色，第二位表示边 $(2,3)$ 的颜色，以此类推，第 $N$ 位表示边 $(N,1)$ 的颜色。所有数位都将会是 $1,2,3$ 中的其中一个。

outputFormat:
如果没有符合条件的分法，输出 `NE` 并结束整个程序。

否则，在第一行输出 `DA` 并在接下来的 $N-3$ 行中输出每一条被分割的对角线及其颜色。

每行输出格式为 `X Y C`。其中 $X,Y$ 为对角线的两个顶点，而 $C$ 为其颜色编号（$1 \le X,Y \le N, 1 \le C \le 3$），不必考虑对角线顶点顺序。

如果有多种符合条件的分法，输出任意一种。

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

| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $20$ | $4 \le N \le 11$ |
| $2$ | $40$ | $4 \le N \le 10^3$ |
| $3$ | $50$ | $4 \le N \le 2 \times 10^5$ |

#### 说明

**本题分值按 COCI 原题设置，满分 $110$。**

本题使用非官方的 [Special Judge](https://www.luogu.com.cn/paste/wxx1bxs2)，欢迎大家 hack（可私信或直接发帖）。

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf)  _T4 Trobojnica_ 。**


title: 「MCOI-03」括号

background:
MCOI q 群的日常 ……

> 一只书虫仔：挖不到钻石，我要哭了（笑）
> WAPER420：我们分明次次挖到钻石啊（疑惑）
> 一只书虫仔：（友善的笑容）
> 7KByte：为什么你们都喜欢加括号啊（呆呆地望着）
> 一只书虫仔：（笑）
> WAPER420：（笑）
> 鏡音リン：（笑）
> 7KByte：（笑）

---

本题中 **合法括号串** 的定义如下：

1. 空串是合法括号串。
2. 如果 ```A``` 是合法括号串，则 ```(A)``` 是合法括号串。
3. 如果 ```A```，```B``` 是合法括号串，则 ```AB``` 是合法括号串。

本题中 **子串** 的定义如下：

字符串 $S$ 的子串是 $S$ 中连续的任意个字符组成的字符串。$S$ 的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S(l,r)$（$1 \leq l \leq r \leq |S|$，$|S |$ 表示 ```S``` 的长度）。

description:
定义一个括号串的 $0$ 级偏值为将该括号串修改为 **合法括号串** 需要的最小操作数。一次操作你可以在一个位置 **添加** 一个括号或者 **删除** 一个位置的括号。

定义一个括号串的 $i\ (i>0)$ 级偏值为该串 **所有子串** 的 $i-1$ 级偏值之和。

现在你需要求出一个长度为 $N$ 的括号串 $S$ 的 $K$ 级偏值。答案可能很大，输出对 $998244353$ 取模后的结果。

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

第二行一个字符串代表括号序列 $S$。

outputFormat: 一行一个整数代表答案对 $998244353$ 取模的结果。


title: [BalticOI 2002 Day1] Triangles

description:
给定 $n$ 个等腰直角三角形，每个三角形由一个点 $(x_i,y_i)$ 向上向右延伸出长为 $m_i$ 的两条直角边生成。

求这些三角形覆盖的面积。

inputFormat:
第一行一个整数 $n$ 代表三角形的个数。
接下来 $n$ 行每行三个整数 $x_i,y_i,m_i$ 描述一个三角形。

outputFormat:
一行一个实数代表答案。
只需要保留一位小数。

hint:
#### 样例说明

对于样例 $1$，$5$ 个三角形如下：

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

#### 数据规模与约定

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

#### 说明

翻译自 [BalticOI 2002 Day1 C Triangles](https://boi.cses.fi/files/boi2002_day1.pdf)。


title: [BalticOI 2002 Day1] Tennis Club

description:
有 $N$ 个人想互相交朋友，第 $i$ 个人想和 $G_i$ 个人交朋友。

求一种交朋友的分配方式。

inputFormat:
第一行一个整数 $N$ 代表人数。
接下来 $N$ 行每行一个整数 $G_i$ 代表第 $i$ 个人想和 $G_i$ 个人交朋友。

outputFormat:
如果无解，一行输出 `NO SOLUTION`。
如果有解，首先一行输出 `SOLUTION`。
接下来 $N$ 行每行 $G_i$ 个整数代表第 $i$ 个人与哪几个人交朋友。

注意如果有方案第 $i$ 行的 $G_i$ 个整数请升序输出。
如果有多种方案，任意输出一种即可。

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

对于 $100\%$ 的数据，$2 \le N \le 1000$，$1 \le G_i < N$。

**本题使用 Special
Judge。**

#### 说明

翻译自 [BalticOI 2002 Day1 B Tennis Club](https://boi.cses.fi/files/boi2002_day1.pdf)。


title: [BalticOI 2002 Day1] Speed Limits

description:
您现在在一张 $N$ 点 $M$ 边的无向图的点 $0$ 处，这 $N$ 个点编号为 $0$ 到 $N-1$。

每条边从 $A$ 连向 $B$，速度限制为 $V$，长度为 $L$，经过这条边的时间的算法如下：

$$T=\begin{cases}\dfrac{L}{V}\ (V\ne 0)\\\dfrac{L}{V_\text{old}}\ (V=0)\end{cases}$$

其中 $V_\text{old}$ 为您经过的上一条边的 $V$ 的值，最开始 $V_\text{old}=70$。

如果 $V=0$，这条边的 $V$ 的值在计算完 $T$ 后更新为 $V_\text{old}$，$V_\text{old}$ 更新为 $V$。

您先在要从点 $0$ 到点 $D$，求一条从 $0$ 到 $D$ 的路径使得花的时间最少。

inputFormat:
第一行三个整数 $N,M,D$ 代表点数，边数和终点。
接下来 $M$ 行每行四个整数 $A,B,V,L$ 代表一条边。

outputFormat: 一行若干个整数代表花的时间最少的路径。

hint:
#### 样例说明

对于样例 $1$，输出这条路径花的时间最少，为 $2628$。

#### 数据规模与约定

对于 $100\%$ 的数据，$2 \le M \le N \le 150$，$0 \le V,L \le 500$。

#### 说明

翻译自 [BalticOI 2002 Day1 A Speed Limits](https://boi.cses.fi/files/boi2002_day1.pdf)。


title: [COCI2019-2020#3] Preokret

background:
圣诞节后的一天——圣史蒂芬日，将要到来了。在非宗教领域，它在英国被称为节礼日。在克罗地亚人通过享用大餐来庆祝的同时，我们的英国朋友却有着踢足球的传统。

今年圣诞节，Pep 吃了太多的烤牛肉，因此他决定这次不踢足球，而是在家中分析球赛。

description:
已知有 $N$ 次进球得分以及它们的顺序。他想要得到下列问题的答案：

1. 最终的得分是多少，即 City 队及其对手的得分。

2. 球赛过程中有几次打平，即两队进球数目相同。初始比分 `0:0` 也算作一次打平。

3. 球赛中最大的「翻盘」。「翻盘」指其中一队在比分落后的情况之下，通过**连续**进球若干次，在比分上领先于对方。他想知道该队的进球数是多少。数据保证至少有一次「翻盘」。

inputFormat:
第一行包含题中所提的整数 $N$。

接下来的 $N$ 行，每行有一个整数 $1$ 或 $2$。$1$ 代表 City 队得分，$2$ 则代表其对手得分。

outputFormat:
第一行，输出两个用空格分开的整数，表示 City 及其对手的进球数量。

第二行，输出双方打平的次数。

第三行，输出最大的「翻盘」。

hint:
#### 样例解释

第一个样例的解释：

$6$ 次比分分别为：`0:0`、`1:0`、`2:0`、`2:1`、`2:2`、`2:3`。其中，有 $2$ 次平局—— `0:0` 和 `2:2`。最大的「翻盘」指 City 对手以 `2:0` 落后，但后续进球 $3$ 次，比分变为 `2:3`，得分超过 City。

第二个样例的解释：

$10$ 次比分分别为：`0:0`、`1:0`、`1:1`、`1:2`、`2:2`、`3:2`、`4:2`、`4:3`、`5:3`、`6:3`。其中，有 $3$ 次平局—— `0:0`、`1:1` 以及 `2:2`。最大的「翻盘」指 City 以 `1:2` 落后，但后续进球 $3$ 次，比分变为 `4:3`，得分超过对手。

#### 数据规模及约定

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

#### 评分方式

本题中，每个测试点按行给分。第一行和第二行分值均为 $1$ 分，第三行分值为 $3$ 分，因而启用 Special Judge。

#### 说明

**本题分值按 COCI 原题设置，满分 $50$。**

本题使用非官方的 [Special Judge](https://www.luogu.com.cn/paste/zfwv9rik)，欢迎大家 hack（可私信或直接发帖）。

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #3](https://hsin.hr/coci/archive/2019_2020/contest3_tasks.pdf)  _T1 Preokret_ 。**


title: [COCI2019-2020#3] Grudanje

background:
Patrik 热爱研究英语单词。他尤其喜欢正好包含 $N$ 个字母的单词。他看到满足这种条件的单词时，便立即开始分析这个单词的 $Q$ 个子单词。如果这 $Q$ 个子单词的字母各不相同，那么他称原单词为「完美单词」。

Krešimir 则不然，他则更喜欢朝 Patrik 扔雪球。在一个寒冷的冬天早晨，正当他在城中拿着 $N$ 个雪球游荡时，却突然撞到正在研究一个包含 $N$ 个字母的单词的 Patrik。

Krešimir 向 Patrik 扔出了他的 $N$ 个雪球，其中第 $i$ 个雪球正好不偏不倚地砸在单词的第 $p_i$ 个字母上。

description:
Patrik 决定重新对「完美单词」作出定义：对于一个长度为 $N$ 的单词的 $Q$ 个子单词，如果所有的子单词的未被雪覆盖的字母部分没有重复，那么原单词被称为「完美单词」。

他想知道 Krešimir 在砸了几个雪球之后，原单词就成为了「完美单词」。

inputFormat:
第一行包含一个只有小写英文字母的单词，其长度为 $N$。

第二行包含一个整数 $Q$。

接下来的 $Q$ 行，第 $i$ 行包含两个整数 $a_i,b_i$。这表示第 $i$ 个子单词是从原单词的第 $a_i$ 个字母至第 $b_i$ 个字母连续截取而来。

接下来的一行，包含 $N$ 个互不相同的整数 $p_i$。

outputFormat: 输出 Patrik 想要知道的答案，即输出在砸了几个（可能为 $0$）雪球之后，原单词才能成为「完美单词」。

hint:
#### 样例解释

第二个样例中的单词在分别被雪球砸掉之后的情况：

```plain
abbab*ab
ab*ab*ab
ab*a**ab
*b*a**ab
*b****ab
******ab
*******b
********
```

#### 数据规模及约定

对于 $20\%$ 的数据，$1 \le N,Q \le 500$。

对于另外 $30\%$ 的数据，$1 \le N,Q \le 3000$。

对于另外 $20\%$ 的数据，原单词只包含字母 `a`。

对于 $100\%$ 的数据，$1 \le N,Q \le 10^5$，$1 \le a_i \le b_i \le N$，$1 \le p_i \le N$。

#### 说明

**本题分值按 COCI 原题设置，满分 $70$。**

由于平均下来每个测试点为 $2.5$ 分，因而将其中一半的测试点设置为 $2$ 分，另一半设置为 $3$ 分。

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #3](https://hsin.hr/coci/archive/2019_2020/contest3_tasks.pdf)  _T2 Grudanje_ 。**


title: [PA2013] Filary

description:
给定长度为 $n$ 的数列 $a$，从中选取 $k$ 个数使得这 $k$ 个数模 $m$ 相等，其中 $m\geq 2$。

求出 $k$ 的最大值，并在 $k$ 最大的前提下最大化 $m$。

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

第二行 $n$ 个正整数，表示数列 $a$。

outputFormat: 一行两个数 $k,m$。

hint: $2\leq n\leq 10^5$，$1\leq a_i\leq 10^7$，保证有解，且不存在所有 $a_i$ 都相等的情况。


title: [PA2013] Działka

description: 给定 $k\times k$ 平面中的 $n$ 个点，$m$ 次询问，每次询问一个边平行于坐标轴的矩形内部（包含边界）的点构成的凸包面积。

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

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$ 表示第 $i$ 个点的坐标。

之后一行一个数 $m$。

之后 $m$ 行，第 $i$ 行包含四个数 $a_i,b_i,c_i,d_i)$，表示询问左下角为 $(a_i,c_i)$，右上角为 $(b_i,d_i)$ 的矩形。

outputFormat: 对于每个询问输出一行表示面积。保留小数点后一位。

hint: $1\leq k\leq 10^6$，$3\leq n\leq 3\times 10^3$，$1\leq m\leq 10^6$，$0\leq x_i,y_i,a_i,b_i,c_i,d_i\leq k，a_i<c_i,b_i<d_i$。


title: [COCI2019-2020#3] Drvca

description:
为了迎接圣诞老人，市政厅已经准备了 $N$ 棵圣诞树。相关人员想要将这些树排成两排，使得每一排中：

- 相邻两树之间高度之差相等
- 圣诞树按照高度从小到大的顺序排列。

请你帮助大家找到一个合适的排列方式。

inputFormat:
第一行，输入一个整数 $N$，表示圣诞树的总数。

第二行，输入 $N$ 个整数，第 $i$ 个为 $h_i$，表示第 $i$ 棵圣诞树的高度。

outputFormat:
第一行，输出一个整数 $A$，表示第一排圣诞树的数量。

第二行，输出 $A$ 个整数，依次表示第一排各个圣诞树的高度。

第三行，输出一个整数 $B$，表示第二排圣诞树的数量。

第四行，输出 $B$ 个整数，依次表示第二排各个圣诞树的高度。

给出的方案中，每排都必须有树，即 $A \gt 0, B \gt 0$，并且每一棵树都应该放在其中一排，即 $A+B=N$。并且，每一排的圣诞树都必须按照高度从小到大排列。如果有多种方案，请输出任意一种。否则，只输出一个整数 `-1`。


title: [COCI2019-2020#3] Lampice

description:
Mirko 用 $N$ 个 LED 灯来装饰圣诞树，它们的颜色是已知的，并且通过 $(N-1)$ 条电线连接。

Mirko 在大功告成后，仔细地品味自己的作品。他被一种叫作「回文段」的特殊图案所吸引。「回文段」指一条从 $u$ 至 $v$ 的路径，它满足从 $u$ 到 $v$ 的路径所包含灯的颜色等于从 $v$ 到 $u$ 的路径所包含灯的颜色。

求出圣诞树中最长的「回文段」。

inputFormat:
第一行，输入一个整数 $N$，表示 LED 灯的数量。

第二行，输入一个由 $N$ 个英文小写字母组成的字符串，其中第 $i$ 个字母代表第 $i$ 个灯的颜色。

接下来的 $(N-1)$ 行，每行输入两个整数 $A,B$，表示 $A,B$ 之间用一条电线连接。

outputFormat: 输出圣诞树中最长的「回文段」。


title: [COCI2019-2020#3] Sob

background: 在漆黑的平安夜晚上，一个巨大的驯鹿闯入，对我们的英雄说：「在你解决这个问题之前，我将不会离开。」

description:
给定两个正整数 $N,M$。

现要将集合 $A=\{0,1,2,\cdots,N-1\}$ 和 $B=\{M,\cdots,M+N-1\}$ 中的数进行组合，选出 $N$ 个有序数对 $(x_i,y_i)$。要求：

- $x_i \in A$，$y_i \in B$，$x_i \& y_i = x_i$（$\&$ 表示按位与运算）。
- 所有的 $x_i$ 互不相同，所有的 $y_i$ 互不相同。

inputFormat: 输入两个整数 $N,M$。

outputFormat:
输出共有 $N$ 行。

第 $i$ 行输出两个整数 $x_i,y_i$，其中 $x_i \in A, y_i \in B$。

可以证明，符合条件的方案一定存在。

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

| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $N$ 是 $2$ 的整数次幂 |
| $2$ | $29$ | $N+M$ 是 $2$ 的整数次幂 |
| $3$ | $39$ | $N+M \le 1000$ |
| $4$ | $32$ | 无 |

对于 $100\%$ 的数据，$1 \le N \le M, N+M \le 10^6$。

#### 说明

本题使用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/462bmlh1)，欢迎大家 hack（可私信或直接发帖）。

**本题分值按 COCI 原题设置，满分 $110$。**

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #3](https://hsin.hr/coci/archive/2019_2020/contest3_tasks.pdf)  _T5 Sob_ 。**


title: [PA2012] Binary Dodgeball

description:
有 $n$ 个盒子，开始时每个盒子中有一个棋子。

两位选手轮流操作，每次可以选择一个 $i$ 号盒子中的棋子和一个正整数 $p$，将棋子移到编号为 $2^p\times i$ 的盒子中。若编号为 $2^p\times i$ 的盒子中已有棋子了，则这两个棋子都会被移出盒子。不能移动者输。

求第 $k$ 小的 $n$，使得**后**手能赢得游戏。

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

outputFormat: 仅一行，包含一个正整数 $n$。


title: [PA2012] Two Cakes

description: 你有两个 $1\sim n$ 的排列。你用左手和右手分别从左到右写两个排列，每只手每写一个数需要 $1$ 单位时间，两只手可以同时工作。若你两只手不能同时写同一个数，那你至少需要多久写完这两个排列呢？

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

接下来一行 $n$ 个整数，为一个 $1\sim n$ 的排列。

接下来一行 $n$ 个整数，为另一个 $1\sim n$ 的排列。

outputFormat: 仅一个整数，为最短时间。

hint:
**样例解释**

第一单位时间：左手写 $1$，右手写 $3$。

第二单位时间：左手写 $2$。

第三单位时间：右手写 $2$。

第四单位时间：左手写 $3$，右手写 $1$。

**数据范围**

对于 $100\%$ 的数据，$1\le n\le 10^6$。


title: [PA2012] Tanie linie

description: 给定含 $n$ 个数的序列，求至多 $k$ 个不相交子段的和的最大值。

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

接下来一行 $n$ 个整数，为这个序列。

outputFormat: 输出一个整数，为答案。


title: [PA2012] Tax

description: 给出一个 $n$ 个点 $m$ 条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点 $1$ 到点 $n$ 的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。

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

接下来 $m$ 行，每行三个数 $a,b,c$，表示 $a,b$ 之间存在一条长度为 $c$ 的边。

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

hint: $1\leq n\leq 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq c\leq 10^6$。


title: 『JROI-2』Shelter

background:
And it's a long way forward
So trust in me
I'll give them shelter like you've done for me
And I know, I'm not alone
You'll be watching over us
Until ...

一个小女孩斜躺在一个驾驶舱的椅子上，长发从肩膀上飘落到地上。
她的嘴角绽放出微笑，身旁的显示屏写着 “返回 第三行星”。
她怀里的泰迪熊身上写着她的名字，Rin。

—— [Shelter](https://www.bilibili.com/video/BV1ys41147Gv)

---

description:
Rin 和爸爸还在地球上时，他们经常玩一个石子游戏。

爸爸摆出了 $n$ 堆石子，这 $n$ 堆石子编号为 $1$ 到 $n$。

游戏规则是这样的，每次 Rin 可以抓取石子，有两种抓取方式：

- 选择一个数 $i$，把第 $i$ 堆石子抓取走，代价为 $i \times p$。
- 选择两个数 $i,j$，把第 $i$ 堆和第 $j$ 堆石子抓走，代价为 $|i-j| \times q$。

其中 $p,q$ 为爸爸提前定好的常数。

Rin 想知道，抓取完所有石子至少需要多少代价。

还剩 1919810114514 秒第三行星的灾难就要降临了，爸爸还需要 1919810114513.7 秒的时间把 Rin 安放到驾驶舱里，并启动机器让 Rin 进入 “Shelter” 里，因此，你只有 0.3 秒的时间帮助 Rin 算出这个结果哦！

inputFormat:
**本题多测**，第一行一个整数 $T$ 代表数据组数。
接下来 $t$ 行，每行三个整数 $n,p,q$ 代表石子堆数，和两个常数。

outputFormat: $T$ 行每行一个整数代表答案。

hint:
#### 样例 1 解释

第一组数据：

1. 利用第一个操作，拿走第 $1$ 堆石子，代价为 $1 \times 2=2$。
2. 利用第二个操作，拿走第 $2,3$ 堆石子，代价为 $|2-3| \times 3=3$。
3. 利用第二个操作，拿走第 $4,5$ 堆石子，代价为 $|4-5| \times 3=3$。

最小代价为 $2+3+3=8$。

第二组数据：

1. 利用第一个操作，拿走第 $1$ 堆石子，代价为 $1 \times 1=1$。
2. 利用第一个操作，拿走第 $2$ 堆石子，代价为 $2 \times 1=2$。
3. 利用第二个操作，拿走第 $3,4$ 堆石子，代价为 $|3-4| \times 5=5$。

最小代价为 $1+2+5=8$。

#### 数据规模与约定

**本题采用捆绑测试。**

- Subtask 1（1 pts）：$p,q =0$。
- Subtask 2（1 pts）：$n=1$。
- Subtask 3（30 pts）：$T \le 5 \times 10^4$，$n \le 5 \times 10^5$。
- Subtask 4（33 pts）：$T \le 10^6$，$n \le 5 \times 10^5$。
- Subtask 5（35 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^9$，$0 \le p,q \le 100$，$1 \le T \le 10^6$。

附件中的 Extra Example 满足 $T=10^4$，可供调试使用。

-----
Source：[JROI-2 Summer Fun Round](https://www.luogu.com.cn/contest/30241) - T1

Idea&Sol：[一只书虫仔](/user/114914)

Std&Data：[Tony2](/user/171288)

Retest：[Cocoly1990](/user/183026)


title: [CEOI2006] Queue

description:
If you are an average football fan, you probably know that obtaining tickets for this year's World Cup in
Germany was an almost impossible task. Greedy organizers and football federations grabbed the majority of
available tickets and divided them among sponsors, friends and family members. As a result, jet setters have
flooded the venues, while die-hard fans sit at home enjoying the games between advertisements featuring crappy
beer and sugar-free chewing gum.

A couple of tickets are left for the final game and a huge queue has formed in front of the ticket office. As fans
were arriving, they were labeled with successive integers. The first person in queue was labeled with number one,
the second with number two, etc.

Since the fans arrived the night before, they had to wait for a long time before the ticket counter was open and,
naturally, some of them had to use the restroom. Each time a person needs to use the restroom, he/she steps
out of the queue and, after completing the task, steps back into the queue, though not necessarily at the same
position as before. Since there is only one restroom available, no person leaves the queue before the previous
person has returned (hence, at any moment there is at most one person missing from the queue).

During the course of the night, a total of N restroom visits have occurred. Each visit is described by two positive
integers A and B, denoting that the person labeled **A stepped out of the queue** and then stepped back into the
queue **immediately in front of the person labeled B**. Now that all the visits have completed, the officials have
to answer a series of questions. Each question is either of the form 'P X', asking for **the position of the person
labeled X**, or of the form 'L X', asking for **the label of the person at position X**.

The first person in queue is considered to be at position one, the second at position two, etc.

Write a program that, given the description of the visits and a number of questions, **answers all of the
questions**.

inputFormat:
The first line of input contains an integer N (2 ≤ N ≤ 50 000) – the total number of restroom visits.

Each of the following N lines contains two different integers A and B (1 ≤ A, B ≤ 109), describing one restroom
visit. The next line contains an integer Q (1 ≤ Q ≤ 50 000) – the total number of questions.

Each of the following Q lines contains a single character (either the uppercase letter 'P' or the uppercase letter
'L') and an integer X (1 ≤ X ≤ 109), describing one question.

outputFormat:
The output should consist of a total of Q lines.

The ith line of output should contain a single integer R – the answer to the ith question.

If the corresponding question is of the form 'P Xi' then R should be the final position of the person labeled Xi.

If the corresponding question is of the form 'L Xi' then R should be the label of the person at position Xi.

translation:
翻译经过简化，但不是结论。

一开始将一列人按编号从 $1$ 开始顺序排列，然后进行 $N$ 次操作，每次将编号为 $A$ 的人拿出，放在编号为 $B$ 的人前面，所有操作进行完后有 $Q$ 个问题，询问编号为 $X$ 的人的位置，或者询问在 $X$ 号位置上的人的编号。

hint:
Partial credit is awarded for incorrect solutions that correctly answer all questions of one type. If all questions of
the form 'P X' are answered correctly or if all questions of the form 'L X' are answered correctly, you will receive
50% of the points for the corresponding test case.

In order to receive partial credit, the output should be formatted according to the specifications. Therefore, even
if you choose to answer only one type of questions, you should still produce output for all questions of the other
type.


title: [CEOI2006] CONNECT

description:
Back in the day when the famous sixteen-bit three-letter operating system most often used on an 25x80 terminal dominated the PC market, "Nibbles" was everyone's favorite computer game. This problem, however, is not related to Nibbles – it is related to a game called "Connect" which is almost, but not quite, entirely unlike
Nibbles.

Connect is played on a board composed of squares organized into R rows and $C$ columns, where both $R$ and $C$ are **odd numbers**. Rows and columns are numbered $1$ to $R$ and $1$ to $C$, respectively. Each position on the board
is either free or blocked by a wall. Additionally, each board satisfies the following constraints:

- Squares with **both coordinates even** are called rooms. They are **never blocked**.
- Squares with **both coordinates odd** are called barriers. They are **always blocked**
- All other squares are called corridors. They may or may not be blocked.
- Corridors **along the edge** of the board are **always blocked**.

Barriers are represented by the '+' (plus) character, blocked horizontal corridors by the '|' (pipe) character, while blocked vertical corridors are represented by the '–' (minus) character. Rooms and free corridors are represented by the blank character.

  At the beginning of the game an **even number** of figures (represented by the uppercase letter 'X') are placed on the board – each in a separate **room**. $A$ path between figures $A$ and $B$ is a sequence of **free** squares starting from $A$, ending with $B$ and moving in one of the **four possible directions** in each step (the path includes both endpoint squares, $A$ and $B$). The length of the path is the total number of steps needed to get from $A$ to $B$  (which is equal to the number of squares contained in the path minus one).

  The goal of the player is to first **divide all the figures into pairs**, and then, for each pair, **connect** the two figures with a path. The pairs should be connected in such a way that **no two paths share a common square**.

  For a completed game, the score is defined as **the sum of the lengths** of all paths.

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

Write a program that, given the starting position of the Connect game, plays the game in such a way that the **minimum possible score** is achieved.
The test data will guarantee that a solution, although not necessarily unique, will always exist.

inputFormat:
第一行输入为两个整数： $R$ 与 $C$ ,其中 $R$ 为行数，$C$ 为列数，$R$ ，$C$ 均为奇数。

接下来的 $R$ 行每行包括 $C$ 个字符，每个字符都是`+`、`|`、`- `、空格或`X`中的一个，分别表示障碍及两种墙壁、空格表示房间或可通过的走廊，`X`表示房间中的物品。

outputFormat:
输出的第一行是一个整数，即最小分值。

本题**不要求**输出合法方案

translation:
给定一个 $R*C$ 大小的迷宫，其中 $R,C$ 均为奇数。

迷宫中**两个- 坐标值均为奇数**的点不能通过，称为障碍；迷宫中其他不能通过的点统称为墙壁；坐标为两个偶数的点可以通过，称为房间；迷宫中其他可通过的点称为走廊。

迷宫有边界，迷宫中放置有**偶数**个物品，物品一定放置在房间中，问如何将这些物品配对可以使得所有物品对之间路径的总和最小，任两条路径不能相交，并输出这个总和的最小值。

hint: $5 \leqslant R \leqslant 25$，$5 \leqslant C \leqslant 80$


title: [CEOI2006] Link

description:
Webmaster Kirk is reorganizing his school's website. There are a number of pages on the website and the
content is fine, but he noticed that the pages are not properly linked. In fact, every page contains exactly one link, pointing to some other page in the website. This is a poor design – starting from the homepage, a visitor will usually have to follow many links before reaching the page of his interest, and some pages might not be reachable from the homepage at all. As a first step, he wants to add a few links so that every page can be quickly accessed from the homepage. New links can be added anywhere in the website.

The website contains N pages marked with integers 1 to N and the homepage is marked with the number 1.

There are also N links; **each page contains exactly one link** pointing to some **different** page. For an integer
K, a website is said to be **K-reachable** if every page on the website other than the homepage can be reached from the homepage by following **at most K** links.

Write a program that, given the description of the website and an integer K, finds the **minimum number of links that need to be added** in order to make the website K-reachable.

inputFormat:
第一行是两个整数用空格隔开 $N$ 和 $K$。

接下来 $N$ 行：

其中第 $i+1$ 行 $(1\leqslant i\leqslant N)$ 输入两个整数 $x$ 和 $y$ , 表示存在一条从 $x$ 到 $y$ 的单向边。

outputFormat: 输出仅一个整数：表示最少需要添加的边数。

translation: 给定一个 $N$ 个点 $N$ 条边的有向图（内向基环树）， 要求在图上添加最上的边，使得点 $1$ 到达所有其他点的最短路长度不超过 $K$。


title: [CEOI2006] Walk

description:
Finding your destination in a big unknown city can be challenging, especially if you are a computer scientist like
Kirk, always trying to use the shortest possible path. Planning can help – given the map of the city Kirk wants to
find the shortest path between his current position and his destination.

The map of the city can be represented in the plane as an infinite grid composed of unit squares.

Kirk is currently located at the square (0, 0) and his destination is the square (X, Y).

There are N buildings in the city. Each building is a rectangle fully occupying a number of unit squares. **No two
buildings touch or overlap**, i.e. Kirk can walk freely around every building. A building is defined by specifying
the coordinates of two diagonally opposite squares occupied by the building.

In each step, Kirk can walk to one of the four neighboring squares, but he is not allowed to step onto a square
occupied by a building. His current position is at the west entrance to the city and the x coordinate of every
square occupied by a building is **strictly greater than zero**.

Write a program that, given the locations of the buildings, finds **one shortest possible path** from Kirk's current
position to his destination. A path should be reported as a sequence of vertical and horizontal segments, with no
two consecutive segments parallel. The length of a path is the number of squares contained in the path,
excluding the initial square.

inputFormat:
The first line of input contains two integers X, Y (1 ≤ X ≤ 106, -106 ≤ Y ≤ 106) – the coordinates of the
destination square. The second line of input contains a single integer N (0 ≤ N ≤ 100 000) – the number of
buildings in the city. Each of the following N lines contains four integers X1, Y1, X2, Y2 (1 ≤ X1, X2 ≤ 106,
-106 ≤ Y1, Y2 ≤ 106) – the coordinates of two diagonally opposite squares occupied by the building.

outputFormat:
The first line of output should contain an integer L – the length of the shortest path to the destination.
The second line of output should contain an integer M – the number of segments in the shortest path. The
number of segments M must not exceed 1,000,000.

Each of the following M lines should contain two integers, DX and DY, describing Kirk's relative movement in
one segment. For each segment, **exactly one** of the values DX, DY should be zero, and no two consecutive
segments should be parallel.

Note: if there are multiple solutions, you should output any one of them.

translation:
在一个陌生的城市中寻找目的地确实是一项颇具挑战性的任务，特别是对于像 Kirk 这样的计算机科学家而言——他总是试图去寻找一条可能的最短路径。在这种情况下，事先做好规划是有帮助的。Kirk 希望借助这个城市的地图找出他当前所在位置与目标位置之间的最短路径。

用一个平面来表示城市地图，它由很多个单位边长的正方形网格组成。
Kirk当前所处位置为方格 $(0,0)$，而他的目标是方格 $(X,Y)$。

城市中有 $N$ 个建筑，而且每个建筑是一个完全覆盖了若干个方格的长方形。注意，任意两个建筑之间彼此均互不重叠或互不相交，Kirk 可以随意地围绕任一个建筑走上一圈。建筑用一对坐标来表示，它们是长方形对角线的两个端点。

在每一步中，Kirk 可以朝着四个方向的任意一个方向前进，但是他不能进入被建筑占据的方格。他现在的位置是城市西边的入口，而每个建筑所占据的方格的 $x$ 坐标均大于 $0$。

试编写一个程序，当给出所有建筑位置时，找出一个从 Kirk 当前位置到目标位置的可能的最短路径。一条路径应该由一系列水平和竖直的线段构成，任意两个相邻线段都不应该平行。路径的长度是路径占据的方格数，初始的那个方格除外。

终点位置 $1 \le X \le 10^6$，$-10^6 \le Y \le 10^6$，建筑个数 $0 \le N \le 10^5$，建筑物的两点坐标 $1 \le X_1,X_2 \le 10^6$，$ -10^6 \le Y_1,Y_2 \le 10^6$

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

**Note**: each of the figures depicts the respective input, along with the supplied solution.

**注意：原题还要求输出方案，本题略去。**


title: [PA2009] Quasi-template

description:
定义一个串 $s$ 能匹配 $S$ 当且仅当 $s$ 能可超出头尾地覆盖
$S$ 且长度不超过 $S$，且 $s$ 必须是 $S$ 的子串。

如下图。

![](https://cdn.luogu.com.cn/upload/image_hosting/gpq807qg.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

给定 $S$ ，求不同的 $s$ 的个数以及长度最短的 $s$，如有多解，输出字典序最小的。

inputFormat: 一行一个字符串 $S$。

outputFormat:
第一行一个整数表示方案数。

第二行一个字符串，表示长度最短的 $s$，如有多解，输出字典序最小的。

hint:
符合条件的串：
aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, abaabaaa.

$S$ 的长度 $\leq 2\times 10^5$


title: [PA2009] Circular Game

description:
一个大小为 $m$ 的轮盘，上面有 $a$ 个白棋子，$b$ 个黑棋子。

白棋先行，每次可以走到一个中间没有任何棋子的位。

例如下图中，$8$ 号棋子可以走到 $1、7、9$ 中任意一个位置。

![](https://cdn.luogu.com.cn/upload/image_hosting/u9d5ifjt.png?x-oss-process=image/resize,m_lfit,h_300,w_300)

inputFormat:
输入的第一行包含一个整数 $t$，表示数据组数。

对于每组数据的第一行有三个整数 $m$，$a$ 和 $b$ ，表示棋盘的长度、白色棋子的数量和黑色棋子的数量。

对于每组数据的第二行，有一个递增的整数序列，代表白色棋子的位置。

对于每组数据的第三行有一个递增的整数序列，代表黑子的位置。

outputFormat:
对于每组数据输出一个单一的字符：$B$ 、$C$ 或 $R$。

若白棋胜输出 $B$，若黑棋胜输出 $C$，
若永不结束，输出 $R$。


title: [PA2009] Cakes

description:
一个有 $n$ 个点 $m$ 条边的无向图，每个点有一个点权 $a$。

对于任意一个三元环 $(i,j,k)（i<j<k）$，它的贡献为 $\max (a_i,a_j,a_k)$。

求所有三元环的贡献和。

inputFormat:
第 $1$ 行 $2$ 个整数 $n,m$，表示点数和边数。

第 $2$ 行 $n$ 个整数 $a_i$，表示每个点的点权。

第 $3$ 至 $m$ 行，每行 $2$ 个整数 $x,y$ 表示一条边。

outputFormat: 一行一个整数 $ans$ ，表示所有三元环的贡献和。


title: [CEOI2020] 花式围栏

description:
众所周知，Balázs 拥有整个城镇中最漂亮的围栏。围栏由 $N$ 个部分组成，每个部分均为矩形，且相邻的两个部分间均紧密相连。第 $i$ 部分矩形的高度为 $h_i$，宽度为 $w_i$，我们需要找到满足如下条件的花式矩形：

- 矩形的每条边均是水平的或竖直的，且每条边的长度为整数。
- 矩形与地面的距离为整数。
- 矩形与围栏第一部分的左侧边的距离为整数。
- 矩形完整包含在围栏中。

现在你需要求出花式矩形的总数。因为这个数字可能很大，请输出其对 $10^9+7$ 取模后的结果。

inputFormat:
输入第一行包含一个整数 $N$，代表围栏由 $N$ 部分组成。

第二行 $N$ 个整数，第 $i$ 个整数为第 $i$ 个矩形的高度 $h_i$。

第三行 $N$ 个整数，第 $i$ 个整数为第 $i$ 个矩形的宽度 $w_i$。

outputFormat: 输出花式矩形数对 $10^9+7$ 取模后的结果。

hint:
### 样例解释 1

围栏形状如下所示：

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

形状如下的矩形有 $5$ 个：

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

形状如下的矩形有 $3$ 个：

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

形状如下的矩形有 $1$ 个：

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

形状如下的矩形有 $2$ 个：

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

形状如下的矩形有 $1$ 个：

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

### 样例 2

见附加文件。

### 子任务

所有测试点均满足：$1 \leq N \leq 10^5$，$1 \leq h_i,w_i \leq 10^9$。

各子任务的约束条件如下：

| 子任务编号 | 分值 | 约束                                                         |
| ---------- | ---- | ------------------------------------------------------------ |
| $1$        | $0$  | 样例                                                         |
| $2$        | $12$ | $N \leq 50$，且 $\forall i \in [1,N]$，$h_i \leq 50$ 且 $w_i=1$ |
| $3$        | $13$ | $\forall i \in [1,N]$，$h_i=1$ 或 $h_i=2$                    |
| $4$        | $15$ | 所有的 $h_i$ 均相等                                          |
| $5$        | $15$ | $\forall i \in [1,N-1]$，$h_i \leq h_{i+1}$                  |
| $6$        | $18$ | $N \leq 1000$                                                |
| $7$        | $27$ | 无特殊约束                                                   |


title: [CEOI2019] Building Skyscrapers

description:
在 2D 平面上，有 $n$ 个计划建摩天楼的格子，第 $i$ 座计划建的摩天楼的格子位于 $(r_i,c_i)$。

您可以选择任意一种建摩天楼的顺序，但是要满足如下设定：

- 设建摩天楼的顺序为 $s$。
- 对于任意 $2\le i\le n$，都要保证，第 $s_i$ 座至少和前面任意一座摩天楼有公共边或公共角。
- 对于任意 $1\le i\le n$，都要保证，从第 $s_i$ 座计划建摩天楼的格子到 2D 平面的边界，有路径相连（从一个格子只能走到与其有公共边的格子），且路径上除第 $s_i$ 座摩天楼无其他摩天楼。

同时会输入一个 $t$，表示输出的类别：

- 若 $t=1$，您需要构造任意一种建造的顺序。
- 若 $t=2$，您需要构造 $(s_n, s_{n - 1}, \dots, s_1)$ 字典序最大的建造顺序。

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

第二行一个整数 $t$。

接下来 $n$ 行，每行两个整数 $r_i,c_i$，第 $i$ 行表示第 $i$ 座计划建的摩天楼的坐标为 $(r_i,c_i)$。

outputFormat:
第一行为一个字符串 `YES` 或者 `NO`，表示是否有一种可行的方案。

若有一种可行的方案，接下来输出 $n$ 行，一行一个整数表示您构造的方案。

- 若 $t=1$，您需要构造任意一种建造的顺序。
- 若 $t=2$，您需要构造 $(s_n, s_{n - 1}, \dots, s_1)$ 字典序最大的建造顺序。

hint:
#### 样例解释

#### 样例 1 解释

这是三个摩天楼连成一行，自然有如下几种解：

- $1,2,3$
- $2,1,3$
- $2,3,1$
- $3,2,1$

因为 $t=2$，所以输出第一种。

#### 样例 2 解释

和样例 1 的区别只是三个摩天楼连成一条对角线，与样例 1 的解一致，又因为 $t=1$，随便输出一组即可。

#### 样例 3 解释

两个摩天楼无相交部分，自然无法建立。
#### 数据范围
对于 $100\%$ 的数据，保证 $1\le n\le 1.5\times 10^5$，$1\le t\le 2$，$\lvert r_i \rvert,\lvert c_i \rvert\le 10^9$。

详细子任务限制及分值如下表：

| 子任务编号 | 限制 | 分值 |
| :-: |:-:|:-:|
| 1 | $t=1$ 且 $n\le 10$ | $8$ |
| 2 | $t=1$ 且 $n\le 200$ | $14$ |
| 3 | $t=1$ 且 $n\le 2\times 10^3$ | $12$ |
| 4 | $t=2$ 且 $n\le 2\times 10^3$ | $17$ |
| 5 | $t=1$ | $20$ |
| 6 | $t=2$，$n\le 7\times 10^4$ 且 $\lvert r_i \rvert,\lvert c_i \rvert\le 900$ | $10$ |
| 7 | $t=2$ | $19$ |
#### 说明
本题译自 [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 1](https://ceoi.sk/tasks/) [T1 Building Skyscrapers](https://ceoi.sk/static/statements/skyscrapers-ENG.pdf)。


title: [蓝桥杯 2013 省 AB] 错误票据

background: 某涉密单位下发了某种票据，并要在年终全部收回。

description:
每张票据有唯一的 ID 号，全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。

你的任务是通过编程，找出断号的 ID 和重号的 ID。

数据保证断号不可能发生在最大和最小号。

inputFormat: 一个整数 $N(N<100)$ 表示后面数据行数，接着读入 $N$ 行数据，每行数据长度不等，是用空格分开的若干个（不大于 $100$ 个）正整数（不大于 $10^5$），每个整数代表一个 ID 号。

outputFormat: 要求程序首先输入要求程序输出 $1$ 行，含两个整数 $m$，$n$，用空格分隔，其中，$m$ 表示断号 ID，$n$ 表示重号 ID。


title: [蓝桥杯 2013 省 B] 翻硬币

background: 小明正在玩一个“翻硬币”的游戏。

description: 桌上放着排成一排的若干硬币。我们用 `*` 表示正面，用 `o` 表示反面（是小写字母，不是零），比如可能情形是 `**oo***oooo`，如果同时翻转左边的两个硬币，则变为 `oooo***oooo`。现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？

inputFormat:
两行等长字符串，分别表示初始状态和要达到的目标状态，每行长度小于 $1000$。

数据保证一定存在至少一种方案可以从初始状态和要达到的目标状态。

outputFormat: 一个整数，表示最小操作步数。

hint: source：蓝桥杯 2013 省 B 组 H 题


title: [蓝桥杯 2013 省 B] 带分数

description:
$100$ 可以表示为带分数的形式：$100 = 3 + \frac{69258}{714}$。

还可以表示为：$100 = 82 + \frac{3546}{197}$。

注意特征：带分数中，数字 $1$ ~ $9$ 分别出现且只出现一次（不包含 $0$）。

类似这样的带分数，$100$ 有 $11$ 种表示法。

inputFormat: 从标准输入读入一个正整数 $N(N<10^6)$。

outputFormat:
程序输出数字 $N$ 用数码 $1$ ~ $9$ 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

hint: 原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛


title: [CEOI2019] Dynamic Diameter

description:
有一棵树，含 $n$ 个节点，边带权。

会有 $q$ 次修改，每次会将树上的一条边的边权进行修改，在每次修改后，您需要求出每次修改后，这棵树的直径上的边权和。

**本题强制在线。**

inputFormat:
第一行为三个整数 $n,q,w$，分别表示点的个数，询问的个数和边权的上限。

接下来 $n-1$ 行，每一行为三个整数 $a_i,b_i,c_i$，表示 $a_i$ 到 $b_i$ 有一条边权为 $c_i$ 的边。

接下来 $q$ 行，每行两个经过加密的整数 $d_j,e_j$。

解密方式如下：
- $d_j'=(d_j+\text{last})\bmod(n-1)$
- $e_j'=(e_j+\text{last})\bmod w$

其中 $\text{last}$ 表示上一个询问的答案，初值为 $0$。

表示将第 $d_j'+1$ 条边的边权改为 $e_j'$。

outputFormat: 共输出 $q$ 行，一行一个整数，第 $i$ 行的整数表示在第 $i$ 次修改后的直径上的权值总和。

hint:
#### 样例 1 解释

解密后的修改如下：
```
2 1030
0 1050
2 970
```
如图为树的边权变化过程，红边代表树的直径：
![](https://cdn.luogu.com.cn/upload/image_hosting/sswn0icz.png)
#### 数据范围
对于 $100\%$ 的数据，保证 $2\le n\le 10^5$，$1\le q\le 10^5$，$1\le w\le 2\times 10^{13}$，$1\le a_i,b_i\le n$，$0\le c_i,e_j<w$，$0\le d_j<n-1$。

详细子任务限制及分值如下表：

| 子任务编号 | 限制 | 分值 |
| :-: |:-:|:-:|
| 1 | $n,q\le 100$ 且 $w\le 10^4$ | $11$ |
| 2 | $n,q\le 5\times 10^3$ 且 $w\le 10^4$ | $13$ |
| 3 | $w\le 10^4$ 且边的形式均为 $(1,i)$ | $7$ |
| 4 | $w\le 10^4$ 且边的形式均为 $(i,2\times i)$ 或 $(i,2\times i+1)$ | $18$ |
| 5 | 保证有一条直径经过 $1$ 号节点 | $24$ |
| 6 | 无特殊限制 | $27$ |
#### 说明
本题译自 [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 1](https://ceoi.sk/tasks/) [T2 Dynamic Diameter](https://ceoi.sk/static/statements/diameter-ENG.pdf)。


title: [CEOI2019] Amusement Park

description:
有一个含 $n$ 个点，$m$ 条边的有向图，图无重边，无自环，两点之间不成环。

现在我们想改变一些边的方向，使得该有向图无环。

您需要求出，每一种改变方向后使得该有向图无环的方案的需改变边的数量之和 $\bmod\ 998244353$ 之后的答案。

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

接下来 $m$ 行，一行两个整数 $a_i,b_i$，表示有一条起点为 $a_i$，终点为 $b_i$ 的有向边。

outputFormat: 仅一行一个整数，表示每一种改变方向后使得该有向图无环的方案的需改变边的数量之和 $\bmod\ 998244353$ 之后的答案。

hint:
#### 样例解释
#### 样例 1 解释
有如下两种方案：
- 改变方向。
- 不改变方向。

所以输出 $1+0=1$。
#### 样例 2 解释
共有六种可行的方案：
- $1\to2,2\to3,1\to3$
- $1\to2,3\to2,1\to3$
- $1\to2,3\to2,3\to1$
- $2\to1,2\to3,1\to3$
- $2\to1,2\to3,3\to1$
- $2\to1,3\to2,3\to1$

所以输出 $0+1+2+1+2+3=9$。
#### 数据范围
对于 $100\%$ 的数据，保证 $1\le n\le 18$，$0\le m\le \frac{n\times (n-1)}{2}$，$1\le a_i,b_i\le n$，$a_i\not=b_i$，对于 $i\not=j$，均有 $a_i\not=a_j$ 或者 $b_i\not=b_j$，无序数对 $\{a_i,b_i\}$ 互不相同。

详细子任务限制及分值如下表：

| 子任务编号 | 限制 | 分值 |
| :-: |:-:|:-:|
| 1 | $n\le 3$ | $7$ |
| 2 | $n\le 6$ | $12$ |
| 3 | $n\le 10$ | $23$ |
| 4 | $n\le 15$ | $21$ |
| 5 | 无特殊限制 | $37$ |
#### 说明
本题译自 [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 2](https://ceoi.sk/tasks/) [T1 Amusement Park](https://ceoi.sk/static/statements/amusementpark-ENG.pdf)。


title: 「MCOI-03」数据

background:
Rin 正在给 MCOI Round 998244353 的题目出数据。

但是她太菜了，把数据生成器写出锅了，于是数据只生成了一半然后生成器就 RE 了。

现在她想请你用这一半的数据恢复出完整的数据。

description:
以下是一些常见的定义，如果你很熟悉它们你也可以不看。

01 串是指仅包含 ```0``` 和 ```1``` 两种字符的字符串，仅包含其中一种也是可以的。

一个字符串取出其连续的一段称为子串。容易发现一个长度为 $2n$ 的字符串有 $n+1$ 个长度为 $n$ 的子串。

一组实数 $A$ 的平均值 $\overline{A}=\frac{\sum_{x\in A}x}{|A|}$，即所有元素的和除以元素的个数。

在此基础上，$A$ 的方差 $S^2=\frac{\sum_{x\in A}(x-\overline{A})^2}{|A|}$，即所有元素与平均值的差的平方和除以元素的个数。

一个长度为 $n$ 的 01 串 $S$ 的二进制值等于 $\sum_{i=1}^nS_i2^{n-i}$，其中 $S_i$ 是 $S$ 从左向右第 $i$ 个字符上的数字。

在本题中，给出如下定义：

一组数据是一个长度为 $2n$ 的 01 串。

一组数据的毒瘤度定义为，其所有长度为 $n$ 的子串的二进制值的方差。

现在，给定一组数据的前 $n$ 个字符。你需要找到使得这组数据的毒瘤度 **最小** 的后 $n$ 个字符。如果有多解，请按照这后 $n$ 个字符构成的子串的二进制值从小到大排序输出。

inputFormat: 输入数据共一行，包含一个长度为 $n$ 的 01 串，表示一组数据的前 $n$ 个字符。

outputFormat: 输出若干行，每一行一个长度为 $n$ 的 01 串，表示一组毒瘤度最小的数据的后 $n$ 个字符，按照其二进制值从小到大排序输出。


title: [CEOI2020] 道路

description:
Treeland 政府准备建立一个全新的道路网。Treeland 共有 $2N$ 个城市，目前已经修建了 $N$ 条道路，每条道路都是一条连接两个城市的线段。这 $N$ 条道路两两没有交点（包括端点处）。你现在需要再修建 $N-1$ 条道路，要求：

1. 每条道路都是一条连接两个城市的线段。
2. 道路只能在端点处相交。
3. 对于任意两个城市，均能通过该路网相互抵达。

inputFormat:
输入第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示 $(x_1,y_1)$ 和 $(x_2,y_2)$ 两座城市间存在一条道路直接相连。

outputFormat:
输出 $N-1$ 行。

每行包含四个整数 $x_1,y_1,x_2,y_2$，代表新修一条连接 $(x_1,y_1)$ 和 $(x_2,y_2)$ 两座城市间的道路。

如果存在多种方案，任意输出一种即可。

hint:
### 样例解释

下图中，实线表示已经修建的道路，虚线代表新修道路。

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

### 子任务

所有数据均满足：$2 \leq N \leq 10^5$，$-10^7 \leq x_1,y_1,x_2,y_2 \leq 10^7$。

各子任务的约束条件如下：

| 子任务编号 | 分值 | 约束                                 |
| ---------- | ---- | ------------------------------------ |
| $1$        | $0$  | 样例                                 |
| $2$        | $15$ | 输入的所有线段均为竖直线段           |
| $3$        | $15$ | 任意两条输入线段互相平行             |
| $4$        | $15$ | 输入的所有线段均为水平线段或竖直线段 |
| $5$        | $15$ | $N \leq 10^4$                        |
| $6$        | $40$ | 无特殊约束                           |

注意实际评测分值分配与上述约定不同。


title: [CEOI2020] 星际迷航

background: 原时空限制：0.2s，32m

description:
星际联邦由 $N$ 颗行星组成，分别编号为 $1 \sim N$。一些行星间由星际通道相连。通过这些星际通道，飞船可以在短时间内往返于各星球之间。整个星际联邦中恰好有 $N-1$ 条星际通道，并且通过这些星际通道，任意两颗行星之间均能相互抵达。

除了我们所处的宇宙之外，还有 $D$ 个平行宇宙，这些平行宇宙是我们的宇宙的完全复刻，它们的行星，星际通道都和我们的完全相同。我们将这些平行宇宙编号为 $1 \sim D$（我们的宇宙编号为 $0$），记第 $i$ 个宇宙的第 $x$ 颗行星为 $P_{x}^i$。通过星门，我们可以在这些平行宇宙间穿梭。$\forall i \in [0,D)$，我们将选择一个 $A_i$ 和一个 $B_i$（要求 $1 \leq A_i,B_i \leq N$），在 $P_{A_i}^i$ 和 $P_{B_i}^{i+1}$ 之间搭建一个**单向**（只能从 $P_{A_i}^i$ 前往 $P_{B_i}^{i+1}$）星门。

当所有的星门都准备就绪后，联邦星舰 Batthyány 号将会开始它的处女航，它目前正环绕着 $P_1^0$ 行星。Ágnes 舰长准备和 Gábor 中尉玩这样一个游戏：两个人交替选择星舰接下来前往的目的地，要求该目的地可以通过星际通道或星门直接抵达。他们希望每次前往的星球都是之前未抵达过的。即，如果星舰抵达了 $P_{x}^i$，他们将不再经过这个星球（但是可以抵达 $x$ 在其他平行宇宙中的相应星球）。由 Ágnes 舰长作为先手开始游戏，Gábor 中尉作为后手，当一位玩家在他的回合中，不能选择一个合法的目的地时，他就输掉了游戏。

舰长和中尉都是绝对聪明的，他们知道所有星际通道和星门的排布方案，并且他们每次都按照最优方案行动。你需要求出，有多少种布置星门的方案，使得作为先手的 Ágnes 舰长必胜？两种布置星门的方案是不同的，当且仅当存在一个整数 $i$，使得 $A_i$ 或 $B_i$ 不同。

inputFormat:
第一行两个整数 $N,D$，分别代表星际联邦拥有的行星数和平行宇宙的数量。

接下来 $N-1$ 行，每行两个整数 $u,v$，表示 $\forall i \in [0,D]$，$P_u^i,P_v^i$ 之间有星际通道相连。

outputFormat: 输出能使舰长必胜的星门布置方案数对 $10^9+7$ 取模的结果。


title: [CEOI2020] 权力药水

description:
很久以前，在萨满之岛上，所有人都住在一个如天一样高的豆茎上。每位萨满都有一个独一无二的编号，编号的范围在 $0$ 和 $N-1$ 之间。第 $i$ 位萨满居住的高度用 $H_i$ 表示。定义两位萨满间的距离为其高度差的绝对值。

所有的萨满之间本来和谐共处，直到一天权力药水的配方被盗。为了掩盖他的行径，那位小偷给整座岛施加了诅咒，大多数居民不再彼此信任了。

虽然情况非常复杂，但是经过调查，某组织还是获得了如下信息：

- 诅咒刚生效时，所有的萨满停止彼此信任。
- 诅咒本身是不稳定的，在每天将要结束时（准确来说是午夜），某一对萨满将会建立信任或是停止信任。
- 不幸地是，一位萨满在任意时刻最多信任 $D$ 位萨满。

该组织还重建了萨满间的信任变化日志，该日志记录了在每个半夜，哪对萨满的信任关系发生了变化（从不信任到信任，或是从信任到不信任）。

该组织的成员相信，小偷还向一位邪恶的萨满通过隔空传话的方式泄露了配方。为了避免被发现，他们俩都各自拜访了一位信任的萨满的家，在拜访的过程中，小偷透过窗户向邪恶的萨满泄露配方。需要注意的是，那位信任的朋友当时不必在家中，事实上，两位萨满可能互相前往对方的家。毕竟萨满都很奇怪。

幸运的是，因为萨满们的听力有限，声音并不能传出太远，这意味着两位朋友（小偷的朋友和邪恶的萨满的朋友）之间的距离必须尽可能近。

现在该组织决定让你来协助调查。他们想要验证自己的猜想：当小偷为 $x$，邪恶的萨满为 $y$，泄露配方的日子为 $v$ 时，隔空传话的声音需要行进的最小值是多少？也即，你需要在第 $v$ 天时，在 $x$ 信任的所有萨满中找到一位萨满 $x'$，在 $y$ 信任的所有萨满中找到一位萨满 $y'$，使 $x'$ 和 $y'$ 间的距离最小。

你已经获得了求出答案所需的所有信息，但你需要**实时**回答每一组询问。

inputFormat:
**仅提供 IO 交互**。

输入第一行包含四个整数 $N,D,U,Q$，分别代表萨满的数量，一位萨满最多信任的朋友数，日志包含的天数，以及需要回答的询问数。

下一行包含 $N$ 个整数，两两间以一个空格隔开。其中第 $i$ 个整数代表第 $i-1$ 只萨满居住的高度 $H_{i-1}$。

接下来 $U$ 行，第 $i$ 行包含两个整数 $A_i,B_i$，代表编号为 $A_i$ 和 $B_i$ 的萨满在第 $i-1$ 天结束的时候，他们之间的信任状态发生了变化。即，如果 $A_i$ 和 $B_i$ 在第 $i-1$ 天互相信任，则他们自第 $i$ 天起不再互相信任，反之同理。

接下来你需要回答 $Q$ 组询问。询问必须实时回答，即你必须回答完一组询问后才能读入下一组询问。

每组询问包含三个整数 $x,y,v$，代表小偷为 $x$，邪恶的萨满为 $y$，泄露配方的日子为第 $v$ 天。

outputFormat:
对于每组询问，你需要在第 $v$ 天时，在 $x$ 信任的所有萨满中找到一位萨满 $x'$，在 $y$ 信任的所有萨满中找到一位萨满 $y'$，使 $x'$ 和 $y'$ 间的距离最小，并输出这个最小值。

特别地，

- 若存在一位萨满同时被 $x$ 和 $y$ 信任，输出 $0$。
- 若 $x$ 或 $y$ 在第 $v$ 天无信任的朋友，输出 $1000000000$（$10^9$）。

在回答完一组询问后，你需要立刻刷新缓冲区。

对于 C++ 选手，可以通过 `fflush(stdout);` 或 `cout.flush()` 来刷新缓冲区。


title: [CEOI2020] 春季大扫除

description:
春季大扫除也许是我们一生中最无聊的事情之一。当然，对于 Flóra 和她的母亲而言，今年的春季大扫除要有意思得多。因为她们在地毯下发现了一张已被灰尘覆盖的树形地图。

这棵树有 $N$ 个节点，节点从 $1$ 到 $N$ 进行编号，这 $N$ 个点通过 $N-1$ 条边相连。这些边上都积累了过多的灰尘，因此 Flóra 的母亲准备对这棵树进行清理。

清理这棵树的过程是这样的：Flóra 的母亲每次在这棵树上选择两个叶子节点（定义一棵树的叶子节点为只与恰好一个点直接相连的点），并对这两个叶子点路径上的所有边进行清理。如果这条路径上有 $d$ 条边，则清理的费用为 $d$。当这棵树上的所有边都被清理后，这棵树的清理过程就完成了。清理这棵树的总费用即为各次清理的费用之和。

因为她想保护这棵树的叶子节点，因此对于每个叶子节点，她最多只会选择一次。

Flóra 认为原来的树过于简单，她决定对原始的树进行一些改造。在第 $i$ 次改造中，她在原始的树的基础上添加了 $D_i$ 个叶子节点。具体来说，她会在原始的树上选择一个节点，并在该点与新的叶子节点之间连接一条边。需要注意的是，在添加新的叶子节点的过程中，原来的一些节点将不再是叶子节点。

现在你需要帮助 Flóra 求出清理改造后的树的最小费用。

inputFormat:
输入第一行包含两个数 $N,Q$，分别代表原始的树上的节点数，以及 Flóra 准备对原始的树进行的改造次数。

接下来 $N-1$ 行，每行两个整数 $u,v$，表示在原始的树上 $u,v$ 两个节点间有一条边相连。

接下来 $Q$ 行，每行第一个整数 $D_i$，表示 Flóra 准备在第 $i$ 次改造中添加 $D_i$ 个叶子节点。接下来 $D_i$ 个整数，第 $j$ 个整数 $a_j$ 表示 Flóra 准备在 $a_j$ 号点上添加一个叶子节点。同一个点上可能会添加多个叶子节点。

每次改造过程是独立的，即在一轮改造后，Flóra 会在原始的树上重新开始改造过程。

outputFormat:
对于每次改造，你需要输出一个整数，表示清理这棵改造后的树的最小费用。

特别地，若这棵树不能被完全清理，输出 $-1$。

hint:
### 样例解释

下面展示的是第二次改造后的树：

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

一种最优的清理方案是清理 $1-6$，$A-7$，$B-3$ 这三条路径上的所有边。

### 子任务

所有测试点均满足：$3 \leq N \leq 10^5$，$1 \leq Q \leq 10^5$，$\sum D_i \leq 10^5$，$1 \leq u,v \leq N$，$1 \leq a_j \leq N$。

各子任务的约束条件如下：

| 子任务编号 | 分值 | 约束                                                         |
| ---------- | ---- | ------------------------------------------------------------ |
| $1$        | $0$  | 样例                                                         |
| $2$        | $9$  | $Q=1$，$\forall i \in [2,N]$，都存在一条连接 $1$ 和 $i$ 的边，且 Flóra 不会在 $1$ 号点上添加叶子节点 |
| $3$        | $9$  | $Q=1$，$\forall i \in [1,N)$，$i$ 和 $i+1$ 之间有边相连，且 Flóra 不会在 $1$ 号点或 $N$ 号点上添加叶子节点 |
| $4$        | $16$ | $N \leq 2 \times 10^4$，$Q \leq 300$                         |
| $5$        | $19$ | 原始的树是一棵以 $1$ 号点为根的满二叉树，即每个非叶子节点均有恰好两个子节点，且各叶子节点到根节点间的距离相等 |
| $6$        | $17$ | $\forall i \in [1,Q]$，$D_i=1$                               |
| $7$        | $30$ | 无特殊约束                                                   |


title: [CEOI2020] 象棋世界

description:
象棋世界是一个 $R$ 行 $C$ 列的棋盘，其中 $R \geq C$。所有的行依此编号为 $1$ 到 $R$，所有的列依此编号为 $1$ 到 $C$。

在象棋世界里，共有五种棋子：兵，车，象，后，王。与现实世界不同的是，骑士精神在象棋世界中已经死亡，因此象棋世界里找不到马。

象棋世界里，每种棋子可以按如下规则进行一步移动：

- 兵只能向行号增大的方向走一步（从第 $r$ 行到第 $r+1$ 行），且其所处的列不变。
- 车只能沿水平方向或竖直方向移动。
- 象只能沿对角线方向移动。
- 后可以沿水平方向，竖直方向，或对角线方向移动。
- 王可以向与之相邻的八个格子移动。

为了方便你理解，我们在下图给出了每种棋子的合法移动范围。其中 X 代表该棋子能移动到的位置。

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

最近一段时间，象棋世界发生了不少诡异的事情：某些棋子可能会被不明来源的力量所劫持，随后从象棋世界中消失。在这种情况下，所有棋子都希望能尽快前往他们想要到达的目的地，他们还想知道，在走的步数最少的前提下，到达目的地的方案数有多少。两种方案是不同的，当且仅当这两种方案中有一步经过的格子不同。

在本题中，你需要解决下面这个问题：某个棋子将从第 $1$ 行的第 $c_1$ 列出发，到达第 $R$ 行的第 $c_R$ 列。现在给出这个棋子的类型，以及 $c_1,c_R$ 的值，你需要求出，这个棋子最少需要走多少步，以及在步数最少的前提下，行走方案有多少种。

inputFormat:
第一行包含三个整数 $R,C,Q$，表示象棋世界中棋盘的行数，列数，以及需要回答的询问数。

接下来 $Q$ 行，包含一个字母 $T$，代表棋子种类，以及两个整数 $c_1,c_R$，代表起点为第 $1$ 行的第 $c_1$ 列，终点为第 $R$ 行的第 $c_R$ 列。

各字母与棋子种类对应关系如下所示：

| 字母         | 棋子种类 |
| ------------ | -------- |
| $\texttt{P}$ | 兵       |
| $\texttt{R}$ | 车       |
| $\texttt{B}$ | 象       |
| $\texttt{Q}$ | 后       |
| $\texttt{K}$ | 王       |

outputFormat:
对于每个询问，输出两个整数，第一个整数代表从起点到终点需要走的最少步数，第二个整数代表在步数最少的前提下，从起点到终点的方案数。

因为方案数可能很大，请输出其对 $10^9+7$ 取模后的结果。

特别地，若无法从起点到达终点，请输出一行 `0 0`。


title: [CEOI2019] Magic Tree

description:
有一棵以 $1$ 为根，节点从 $1$ 到 $n$ 编号的树。

在这棵树上有许多果实，第 $j$ 个果实会于第 $d_j$ 天在节点 $v_j$ 成熟，并且在收获后可获得 $w_j$ 的果汁。

第 $j$ 个果实仅能在第 $d_j$ 天收获。

收获的方式是断掉这棵树的一条边，这会获得在这条边上作为儿子的那个点的子树上的当天成熟的果实的果汁。

您要求出最多可以获得多少果汁。

inputFormat:
第一行为三个整数 $n,m,k$，分别表示节点的个数，果实的个数和果实可能成熟天数的最大值。

接下来 $n-1$ 行，一行一个整数 $p_i$，表示 $i+1$ 号节点的父亲是 $p_i$。

接下来 $m$ 行一行三个整数 $v_j,d_j,w_j$。

outputFormat: 一行一个数，表示最多可以获得多少果汁。

hint:
#### 样例解释
最优方案如下：
- 在第四天，断掉 $(4,5)$ 和 $(1,2)$，获得第一个和第三个果实，获得的果汁数量累计为 $6$。
- 在第七天，虽然我们有一个果实成熟，但是我们最好什么都不干。
- 在第九天，断掉 $(1,4)$，获得最后一个果实，获得的果汁数量累计为 $9$。
#### 数据范围
对于 $100\%$ 的数据，保证 $2\le n\le 10^5$，$1\le m\le n-1$，$1\le k\le 10^5$，$1\le p_i\le i-1$，$2\le v_j\le n$，$1\le d_j\le k$，$1\le w_j\le 10^9$，$v_j$ 互不相同。

详细子任务限制及分值如下表：

| 子任务编号 | 限制 | 分值 |
| :-: |:-:|:-:|
| 1 | $n,k\le 20$ 且 $w_j=1$ | $6$ |
| 2 | $v_j\in $ 叶子节点 | $3$ |
| 3 | 图是一条链且 $w_j=1$ | $11$ |
| 4 | $k\le 2$ | $12$ |
| 5 | $k\le 20$ 且 $w_j=1$ | $16$ |
| 6 | $m\le 10^3$ | $13$ |
| 7 | $w_j=1$ | $22$ |
| 8 | 无特殊性质 | $17$ |
#### 说明
本题译自 [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 2](https://ceoi.sk/tasks/) [T2 Magic Tree](https://ceoi.sk/static/statements/magictree-ENG.pdf)。


title: 「EZEC-4.5」走方格

description:
有 $n\times m$ 的方格矩阵，小 A 从 $(1,1)$ 出发到 $(n,m)$ ，只能向下或向右走，获得的分数为他经过方格的权值之和。

已知每个方格 $(i,j) $的权值 $a_{i,j}$，你可以将其中任意一个方格上的权值变为 $0$，求变化后小 A 最多能获得分数的**最小值**。

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

下面 $n$ 行每行 $m$ 个整数 $a_{i,j}$

outputFormat: 一个整数表示变化后小 A 最多能获得分数的**最小值**。


title: onu

background: 小 C 和小 D 是好朋友。他们正在尝试一种全新的牌类游戏——onu！

description:
为了增加一点趣味性，小 C 和小 D 每人买了 $v$ 颗糖用来当作筹码。

onu 的规则是这样的：

游戏共 $m$ 轮，由两人进行，一位先手，一位后手。在这里，我们默认先手的玩家是小 C，而后手的玩家是小 D。

在最开始时，小 C 会得到 $m$ 张牌，每张牌有其对应的花色、点数。而小 D 会得到 $n$ 张牌。

每一轮开始时，小 C 会打出一张牌，放在桌面上展示给小 D 看。

在此之后，小 D 需要跟牌，即打出他手上的一张牌，且该张牌必须满足其花色与小 C 打出的牌相同。若小 D 没有满足条件的牌或者是他**选择弃权（也就是说，可以选择当前回合是否打出牌）**，弃掉小 C 打出的牌后跳过该轮，视为小 D 败。

在小 D 打出满足要求的牌后，进行一次拼点，也即比较小 C 和小 D 打出的牌的点数：如果小 D 出的牌的点数**大于等于**小 C 的牌的点数，则小 D 胜，否则小 D 败。容易知道，这样不会出现平局的情况。

最后，胜的一方会从败的一方拿走 $c$ 颗糖，且双方均需弃掉打出的牌，并会**再从商店买等于自己打出的牌的点数颗糖**。例如小 C 和小 D 打的点数分别是 $3$ 和 $5$，那么小 C 会去购买 $3$ 颗糖，小 D 购买 $5$ 颗。

为了不破坏两人间的友好关系，不出现一方被另一方完全赢光的情况，他们在最开始买糖时，已经约定好了 $v \ge c \times m$。

现在，小 D 通过一些神秘手段，知道了小 C 在这 $m$ 轮中打出的所有牌，他希望在 $m$ 轮游戏进行之后，让自己的糖数尽量多。你可以帮他找到最优的方案吗？

inputFormat:
第一行四个正整数表示 $n, m, c, v$，含义如题目描述所示。

接下来 $n$ 行中，第 $i$ 行每行两个正整数 $a _i, b _i$，表示了小 D 一开始拥有的第 $i$ 张牌的花色、点数。

接下来 $m$ 行中，第 $i$ 行每行两个正整数 $a _i, b _i$，表示小 C 第 $i$ 轮会打出的牌的花色、点数。

注意可能会有花色点数均相同的牌。

outputFormat:
输出共 $m + 1$ 行。

第一行输出一个正整数，表示在最优方案中，小 D 最多能剩余的糖数。

接下来 $m$ 行中，第 $i$ 行输出一行一个正整数，表示小 D 在第 $i$ 轮打出的牌的编号。如果小 D 跳过了该轮，输出 `-1`。

**本题采用 Special Judge，如果有多种最优方案，输出任意一个即可。**

hint:
#### 「样例 1 解释」

以 $(a, b)$ 来表示一张花色为 $a$，点数为 $b$ 的牌。

一开始，小 D 有 $4$ 颗糖。小 C 会依次打出 $(1, 6), (3, 5), (1, 4)$ 三张牌。

一种最优的方案是：

第一轮，小 C 打出第一张牌 $(1, 6)$，小 D 打出第二张牌 $(1, 2)$，小 D 负，被拿走 $1$ 颗糖，购买 $2$ 颗糖。此时其有 $5$ 颗糖。

第二轮，小 C 打出 $(3, 5)$，小 D 打出 $(3, 5)$，由于点数**大于等于**小 C 的牌，所以小 D 胜，拿到 $1$ 颗糖，购买 $5$ 颗糖。此时其有 $11$ 颗糖。

第三轮，小 C 打出 $(1, 4)$。由于小 D 在第一轮已经打出过第二张牌 $(1, 2)$ 了，所以没有牌能打，输出 $-1$ 并判小 D 负，被拿走 $1$ 颗糖，此时其有 $10$ 颗糖。

#### 「样例 2 解释」

最开始有 $5$ 颗糖。

第一轮时小 C 打出 $(1, 8)$，小 D 选择弃权，败，于是剩下了 $5 - 1 = 4$ 颗糖；

第二轮时小 C 打出 $(1, 4)$，小 D 打出 $(1, 5)$，胜，得到 $5 + 1$ 颗糖，故最终小 D 有 $10$ 颗糖。

----

#### 「Special Judge 说明」

**请认真阅读输出格式**。

每个测试点仅有 $0$ 分和满分的区别。如果你的输出出现了以下情况，将会被判为 $0$ 分：

- 输出格式不符，如没有正确换行，输出了一些奇奇怪怪的字符等。
- 输出的最优糖果数与标准答案不同。
- 打牌的方案不合法，即不能打出已经弃掉的牌，也不能打出花色与小 C 打出的牌不相同的牌。
- 按照你所输出的方案打完牌后，小 D 的剩余糖果数与你第一行所输出的数字不同。

---

#### 「数据范围」

**本题采用捆绑测试**。

- Subtask 1(10 points)：$n, m \le 5$；
- Subtask 2(30 points)：$n, m \le 1000$；
- Subtask 3(20 points)：$c = 0$；
- Subtask 4(20 points)：$a _i = 1$；
- Subtask 5(20 points)：无特殊限制。

所有数据保证 $1 \le n, m, a _i, b _i\le 10 ^5$，$0 \le c \le 10 ^5$，$c \times m \le v \le 10 ^{12}$。


title: 「EZEC-5」魔法

description:
小明是一个魔法师。

他有一个可以被施魔法的数列 $A$ 。

他有两种魔法：

1. 花费 $a$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$ ，将 $A_{l},A_{l+1}...A_{r}$ 全部 $+1$ 。
2. 花费 $b$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$ ，将 $A_{l},A_{l+1}...A_{r}$ 全部 $\times 2$ 。

现在小明想对 $A$ 序列施若干次魔法，使其存在一个子区间元素之和不小于 $s$ 。请求出小明需要花费的最小魔法值。

inputFormat:
第一行四个整数 $n,a,b,s$，表示序列长度，两种魔法的代价，以及元素之和的要求。

接下来一行 $n$ 个整数，表示初始序列。

outputFormat: 一个整数，表示最小花费。


title: [CEOI2019] Scissors and Tape

description:
您有一个简单多边形 $S$，现在您想将其变成与其面积相等的简单多边形 $T$。

您可以使用两种工具：剪刀和胶带。剪刀可将任何多边形切割成较小的多边形。胶带可将较小的多边形组合成较大的多边形。您可以按任何顺序多次使用每个工具。

输入中的多边形的顶点坐标均为整数，但您的方案允许产生顶点坐标不为整数的多边形。

任务的形式化定义如下：

一个形状 $Q=(Q_0,\ldots Q_{n-1})$ 是平面中三个点及以上的序列，满足：

- 闭合折线 $Q_0,Q_1,Q_2,\ldots Q_{n-1},Q_0$ 不相交。
- 这段折线以逆时针围绕多边形的边界。

以形状 $Q$ 为边界的多边形为 $P(Q)$。

两个形状等效当且仅当一个形状经过平移或旋转之后与另一个形状相同。

不允许对形状进行对称，且点的顺序与形状有关：$(Q_0,Q_1\ldots Q_{n-1})$ 不一定等价于 $(Q_1\ldots Q_{n-1},Q_0)$。

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

在上图中，形状 $U$ 和 $V$ 是等价的，但形状 $W$ 与他们不等价，原因是给出的点的顺序不同，无论如何，第四个形状都不与前三个形状相同，因为不允许对称形状。

每一个形状的表示由 $2\times n+1$ 个数组成，第一个数为 $n$，表示形状的点数，接下来 $2\times n$ 个数 $Q_{0,x},Q_{0,y},Q_{1,x},\ldots,Q_{n-1,x},Q_{n-1,y}$，每两个数均表示形状里一个点的坐标，如 $(Q_{0,x},Q_{0,y})$ 为 $Q_0$ 的坐标。

形状 $B_1,B_2,\ldots B_k$ 被称为形状 $A$ 的划分，当且仅当：

- 所有 $P(B_i)$ 的并集为 $P(A)$。
- 对于所有的 $i\not=j$，$P(B_i)$ 与 $P(B_j)$ 无交。

形状是有 ID 的，$S$ 的 ID 为 $0$，您在解决方案中生成的 ID 为 $1,2,3,\ldots$。

剪刀将会剪开一个现有的形状 $A$，并产生 $A$ 的一个划分 $B_1,B_2,\ldots B_k$。

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

在上图中，形状 $A$ 被划分成了 $B_1,B_2,B_3$ 三个三角形。其中描述红色三角形的一种方式为 `3 3 1 6 1 5.1 4`。

胶带可以粘合存在的形状 $A_1,\ldots A_k$ 并使其变成形状 $B$，要执行这个操作，需要给定 $C_1,\ldots,C_k$ 和最终形状 $B$ 并满足如下要求：

- $C_i$ 等价于 $A_i$。
- $C_1,\ldots,C_k$ 是 $B$ 的划分。

通俗地说，你选择了形状 $B$，然后展示如何把每个存在的 $A_i$ 移动到构成 $B$ 的正确的位置 $C_I$。注意形状 $B$ 需要分配一个新 ID，但 $C_i$ 不需要。

inputFormat:
第一行为形状 $S$。

第二行为形状 $T$。

outputFormat:
每当使用剪刀时，按如下格式输出：
```
scissors
id(A) k
B_1
B_2
...
B_k
```
每当使用胶布时，按如下格式输出：
```
tape
k id(A_1) ... id(A_k)
C_1
C_2
...
C_k
B
```
您的输出需要保证以下限制：
- 输出的所有点坐标在 $[-10^7,10^7]$ 之内。
- 输出的每个形状最多能有 $100$ 个点。
- 每次操作中，$1\le k\le 100$。
- 操作数不多于 $2\times 10^3$。
- 输出中所有形状的总点数不超过 $2\times 10^4$。
- 最后必须只剩下一个形状，且这个形状等价于 $T$。

hint:
#### 样例解释
#### 样例 1 解释
![](https://cdn.luogu.com.cn/upload/image_hosting/nn0psa1v.png)

上左图是使用剪刀操作后的原始图形，右侧是使用胶带后对应 $C_i$。
#### 样例 2 解释
请注意，目标和您的最后达成的多边形只需等价即可，不需完全相同。
#### 样例 3 解释
下图显示了这个样例输出的三个阶段：

![](https://cdn.luogu.com.cn/upload/image_hosting/bk5bbncz.png)
#### 数据范围及限制
对于 $100\%$ 的数据，保证 $S$ 与 $T$ 的点数 $\le 10$ 且 $\ge 3$，输入的所有点坐标在 $[-10^6,10^6]$ 之内，无三点共线的情况，$P(S)$ 与 $P(T)$ 的面积相等。

如果一个形状的顶点分别为 $(0,0),(x,0),(0,y),(x,y)$ 且 $x,y$ 为正整数，则称它为好矩形。

如果一个形状是好矩形且 $x=y$，则称它为好正方形。

如果多边形 $P(A)$ 的每个内角都小于 $180$ 度，则称形状 $A$ 为严格凸多边形。

详细子任务限制如下：
| 子任务编号 | 限制 | 分数 |
| :-: | :-: | :-: |
| 1 | $S$ 和 $T$ 是好矩形且输入的所有点坐标在 $[1,10]$ 之内 | $5$ |
| 2 | $S$ 是好矩形且 $x>y$，$T$ 是好正方形 | $13$ |
| 3 | $S,T$ 是好矩形 | $12$ |
| 4 | $S$ 是三角形，$T$ 是好正方形 | $14$ |
| 5 | $S,T$ 均是三角形 | $10$ |
| 6 | $S$ 是严格凸多边形，$T$ 是好矩形 | $16$ |
| 7 | $T$ 是好矩形 | $11$ |
| 8 | 无特殊限制 | $19$ |
#### 说明
本题译自 [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 2](https://ceoi.sk/tasks/) [T3 Scissors and Tape](https://ceoi.sk/static/statements/scissors-ENG.pdf)。


title: [蓝桥杯 2013 省 B] 连号区间数

description:
小明这些天一直在思考这样一个奇怪而有趣的问题：

在 $1$ ~ $N$ 的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：

如果区间 $[L, R]$ 里的所有元素（即此排列的第 $L$个到第 $R$ 个元素）递增排序后能得到一个长度为 $R-L+1$ 的“连续”数列，则称这个区间连号区间。

当 $N$ 很小的时候，小明可以很快地算出答案，但是当 $N$ 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

inputFormat:
第一行是一个正整数 $N (1 \le N \le 50000)$， 表示全排列的规模。

第二行是 $N$ 个不同的数字 $P_i(1 \le P_i \le N)$， 表示这 $N$ 个数字的某一全排列。

outputFormat: 输出一个整数，表示不同连号区间的数目。


title: [蓝桥杯 2013 省 A] 剪格子

description:
**管理备注：此题当前数据仍不强，故评灰**

如图 $1$ 所示，$3\times 3$ 的格子中填写了一些整数。

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

我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是 $60$。

本题的要求就是请你编程判定：对给定的 $m\times n$ 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 $0$。

inputFormat:
程序先读入两个整数 $m$，$n$ 用空格分割 $(m,n<10)$
表示表格的宽度和高度。

接下来是 $n$ 行，每行 $m$ 个正整数，用空格分开。每个整数不大于 $10000$。

outputFormat: 程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。

hint:
第二个用例中：

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

时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛


title: [蓝桥杯 2013 省 A] 大臣的旅费

description:
很久以前，T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的 J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 $x - 1$ 千米到第 $x$ 千米这一千米中（$x$ 是整数），他花费的路费是 $x+10$ 这么多。也就是说走 $1$ 千米花费 $11$，走 $2$ 千米要花费 $23$。

J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

inputFormat:
输入的第一行包含一个整数 $n(n \le 10^5)$，表示包括首都在内的 $T$ 王国的城市数。

城市从 $1$ 开始依次编号，$1$ 号城市为首都。

接下来 $n-1$ 行，描述 $T$ 国的高速路（$T$ 国的高速路一定是 $n-1$ 条）。

每行三个整数 $P_i,Q,D_i$，表示城市 $P_i$ 和城市 $Q_i$ 之间有一条高速路，长度为 $D_i(D_i \le 1000)$ 千米。

outputFormat: 输出一个整数，表示大臣J最多花费的路费是多少。

hint:
样例解释：大臣 J 从城市 $4$ 到城市 $5$ 要花费 $135$ 的路费。

时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛


title: 「MCOI-03」村国

background:
$\texttt{What did this player dream?}$

他梦见了什么？

$\texttt{This player dreamed of sunlight and trees.Of fire and water.}$

他梦见了阳光与树木。梦见了火与水。

$\texttt{It dreamed it created. And it dreamed it destroyed. It dreamed it hunted,}$
$\texttt{and was hunted. It dreamed of shelter.}$

他梦见他的创造，亦梦见他毁灭。它梦见他在狩猎，亦梦见被猎捕。他梦见温馨的居所。

$\texttt{Hah, the original interface. A million years old, and it still works.But}$
$\texttt{ what true structure did this player create, in the reality behind the screen?}$

哎，那原始的界面。经历百万年的岁月，它依然在工作。只是他在屏幕后的真实里，到底创造了什么真实的世界呢？

description:
C 国一共有 $N$ 个村庄，$N-1$ 条道路。这些道路都可以双向通行。保证小 S 可以从一座村庄到其他任何一座村庄。这 $N$ 个村庄编号为 $1$ 到 $N$。

刚开始小 S 对第 $i$ 个村庄的好感值为 $A_i$。小 S 的假期一共有 $M$ 天，他会在 C 国旅行一共 $M$ 天。每一天他会选择来到当前好感值最高的村庄。如果有好感值相同的村庄，他会选择编号最小的村庄。假设这一天他来到村庄 $X$，那么这一天结束后，与村庄 $X$ 直接相邻所有村庄的好感值都会增加 $1$。即能从 $X$ 出发仅经过一条道路到达的村庄好感值会增加 $1$。因为小 S 已经在村庄 $X$ 待过一天了，所以这一天结束后村庄 $X$ 的好感值并不会增加。

现在小 S 想要知道经过 $M$ 天的旅行后好感值最高的村庄。

如果有多个好感值最高的村庄，输出编号最小的。

inputFormat:
**本题单个测试点包含多组测试数据**。
第一行一个正整数 $T$ 表示数据组数。
对于每组数据：
第一行包括两个正整数 $N,M$，表示村庄个数和旅行天数。
接下来一行 $N$ 个整数，第 $i$ 个整数表示第 $i$ 座村庄的好感值 $A_i$。
接下来 $N-1$ 行。每行两个整数 $x,y$ 表示村庄 $x$ 和村庄 $y$ 之间有一条双向通行的道路。

outputFormat: 一个整数表示 $M$ 天结束后好感值最高的村庄的编号。如果有多个好感值最高的村庄，输出编号最小的。


title: [蓝桥杯 2013 国 C] 横向打印二叉树

background: 二叉树可以用于排序。

description:
其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，`10 8 5 7 12 4` 的输入顺序，应该建成二叉树如图 $1$ 所示。

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

inputFormat:
输入数据为一行空格分开的 $N$ 个整数。$N<100$，每个数字不超过 $10000$。

$N$ 并没有在输入中给出。

输入数据中没有重复的数字。

outputFormat: 输出该排序二叉树的横向表示,为了便于评卷程序比对空格的数目，请把空格用句点代替。

hint:
样例解释 1：

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

时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛


title: [蓝桥杯 2013 国 C] 危险系数

background: 抗日战争时期，冀中平原的地道战曾发挥重要作用。

description:
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数 $DF(x,y)$：

对于两个站点 $x$ 和 $y(x\neq y),$ 如果能找到一个站点 $z$，当 $z$ 被敌人破坏后，$x$ 和 $y$ 不连通，那么我们称 $z$ 为关于 $x,y$ 的关键点。相应的，对于任意一对站点 $x$ 和 $y$，危险系数 $DF(x,y)$ 就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

inputFormat:
输入数据第一行包含 $2$ 个整数 $n(2 \le n \le 1000)$，$m(0 \le m \le 2000)$，分别代表站点数，通道数。

接下来 $m$ 行，每行两个整数 $u,v(1 \le u,v \le n,u\neq v)$ 代表一条通道。

最后 $1$ 行，两个数 $u,v$，代表询问两点之间的危险系数 $DF(u,v)$。

outputFormat: 一个整数，如果询问的两点不连通则输出 $-1$。

hint: 时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛


title: [蓝桥杯 2013 国 AC] 网络寻路

description:
$X$ 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。

源地址和目标地址可以相同，但中间节点必须不同。

如图 $1$ 所示的网络。

$1 \to 2 \to 3 \to 1$ 是允许的。

$1 \to 2 \to 1 \to 2$ 或者 $1 \to 2 \to 3 \to 2$ 都是非法的。

inputFormat:
输入数据的第一行为两个整数 $N,M$，分别表示节点个数和连接线路的条数 $(1 \le N \le 10000,0 \le M \le 100000)$。

接下去有 $M$ 行，每行为两个整数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 联通 $(1 \le u,v \le N,u \neq v)$。

输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。

outputFormat: 输出一个整数，表示满足要求的路径条数。

hint:
时限 1 秒，空间限制 64M。蓝桥杯 2013 年第四届国赛

------------
2024/1/28 添加一组 hack 数据


title: [蓝桥杯 2013 国 B] 高僧斗法

description:
古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有“高僧斗法”的趣味节目，以舒缓压抑的气氛。

节目大略步骤为：先用粮食（一般是稻米）在地上“画”出若干级台阶（表示 $N$ 级浮屠）。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人，其它任意。（如图 $1$ 所示 )。

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

两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。

两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。

对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。

inputFormat: 输入数据为一行用空格分开的 $N$ 个整数，表示小和尚的位置。台阶序号从 $1$ 算起，所以最后一个小和尚的位置即是台阶的总数。（$N<100,$ 台阶总数 $<1000$）

outputFormat: 输出为一行用空格分开的两个整数 ：$A,B$， 表示把 $A$ 位置的小和尚移动到 $B$ 位置。若有多个解，输出 $A$ 值较小的解，若无解则输出 $-1$。

hint: 时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛


title: [蓝桥杯 2013 国 B] 格子刷油漆

description:
X 国的一段古城墙的顶端可以看成 $2 \times N$ 个格子组成的矩形（如图 $1$ 所示），现需要把这些格子刷上保护漆。

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

你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）

比如：`adbcef` 就是合格的刷漆顺序。

`cefdab` 是另一种合适的方案。

当已知 $N$ 时，求总的方案数。当 $N$ 较大时，结果会迅速增大，请把结果对 $1000000007(10^9+7)$ 取模。

inputFormat: 输入数据为一个正整数 $N$（不大于 $1000$）。

outputFormat: 输出数据为一个正整数。

hint: 时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛


title: [蓝桥杯 2013 国 B] 农场阳光

description:
X 星球十分特殊，它的自转速度与公转速度相同，所以阳光总是以固定的角度照射。

最近，X 星球为发展星际旅游业，把空间位置出租给 Y 国游客来晒太阳。每个租位是漂浮在空中的圆盘形彩云（圆盘与地面平行）。当然，这会遮挡住部分阳光，被遮挡的土地植物无法生长。

本题的任务是计算某个农场宜于作物生长的土地面积有多大。

inputFormat:
输入数据的第一行包含两个整数 $a,b$，表示某农场的长和宽分别是 $a$ 和 $b$，此时，该农场的范围是由坐标 $(0,0,0),(a,0,0),(a,b,0),(0,b,0)$ 围成的矩形区域。

第二行包含一个实数 $g$，表示阳光照射的角度。简单起见，我们假设阳光光线是垂直于农场的宽的，此时正好和农场的长的夹角是 $g$ 度，此时，空间中的一点 $(x,y,z)$ 在地面的投影点应该是 $(x+z \times \ctg(g),y,0)$，其中 $\ctg(g)$ 表示 $g$ 度对应的余切值。

第三行包含一个非负整数 $n$，表示空中租位个数。

接下来 $n$ 行，描述每个租位。其中第 $i$ 行包含 $4$ 个整数 $x_i,y_i,z_i,r_i$，表示第 $i$ 个租位彩云的圆心在 $(x_i,y_i,z_i)$ 位置，圆半径为 $r_i$。

outputFormat: 要求输出一个实数，四舍五入保留两位有效数字，表示农场里能长庄稼的土地的面积。

hint: 时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛


title: [蓝桥杯 2013 国 A] 约数倍数选卡片

description:
闲暇时，福尔摩斯和华生玩一个游戏：

在 $N$ 张卡片上写有 $N$ 个整数。两人轮流拿走一张卡片。要求下一个人拿的数字一定是前一个人拿的数字的约数或倍数。例如，某次福尔摩斯拿走的卡片上写着数字“ $6$ ”，则接下来华生可以拿的数字包括：

$1$，$2$，$3$，$6$，$12$，$18$，$24 \cdots $。

当轮到某一方拿卡片时，没有满足要求的卡片可选，则该方为输方。

请你利用计算机的优势计算一下，在已知所有卡片上的数字和可选哪些数字的条件下，怎样选择才能保证必胜！

当选多个数字都可以必胜时，输出其中最小的数字。如果无论如何都会输，则输出 $-1$。

inputFormat:
输入数据为 $2$ 行。第一行是若干空格分开的整数（每个整数介于 $1 \sim 100$ 间），表示当前剩余的所有卡片。

第二行也是若干空格分开的整数，表示可以选的数字。当然，第二行的数字必须完全包含在第一行的数字中。

outputFormat: 程序则输出必胜的招法！！

hint: 时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛


title: [蓝桥杯 2013 国 A] 车轮轴迹

description:
栋栋每天骑自行车回家需要经过一条狭长的林荫道。道路由于年久失修，变得非常不平整。虽然栋栋每次都很颠簸，但他仍把骑车经过林荫道当成一种乐趣。

由于颠簸，栋栋骑车回家的路径是一条上下起伏的曲线，栋栋想知道，他回家的这条曲线的长度究竟是多长呢？更准确的，栋栋想知道从林荫道的起点到林荫道的终点，他的车前轮的轴（圆心）经过的路径的长度。

栋栋对路面进行了测量。他把道路简化成一条条长短不等的直线段，这些直线段首尾相连，且位于同一平面内。并在该平面内建立了一个直角坐标系，把所有线段的端点坐标都计算好。

假设栋栋的自行车在行进的过程中前轮一直是贴着路面前进的。

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

图 $1$ 给出了一个简单的路面的例子，其中蓝色实线为路面，红色虚线为车轮轴经过的路径。在这个例子中，栋栋的前轮轴从 $A$ 点出发，水平走到 $B$ 点，然后绕着地面的 $F$ 点到 $C$ 点（绕出一个圆弧），再沿直线下坡到 $D$ 点，最后水平走到 $E$ 点，在这个图中地面的坐标依次为：$(0,0),(2,0),(4,-1),(6,-1)$，前轮半径为 $1.50$，前轮轴前进的距离依次为：

$AB=2.0000$；弧长 $BC=0.6955$；$CD=1.8820$；$DE=1.6459$。

总长度为 $6.2233$。

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

图 $2$ 给出了一个较为复杂的路面的例子，在这个例子中，车轮在第一个下坡还没下完时（$D$ 点）就开始上坡了，之后在坡的顶点要从 $E$ 绕一个较大的圆弧到 $F$ 点。这个图中前轮的半径为 $1$，每一段的长度依次为：

$AB=3.0000$；弧长 $BC=0.9828$；$CD=1.1913$；$DE=2.6848$；弧长 $EF=2.6224$；$FG=2.4415$；$GH=2.2792$。

总长度为 $15.2021$。

现在给出了车轮的半径和路面的描述，请求出车轮轴轨迹的总长度。

inputFormat:
输入的第一行包含一个整数 $n$ 和一个实数 $r$，用一个空格分隔，表示描述路面的坐标点数和车轮的半径。

接下来 $n$ 行，每个包含两个实数，其中第 $i$ 行的两个实数 $x_i,y_i$ 表示描述路面的第 $i$ 个点的坐标。

路面定义为所有路面坐标点顺次连接起来的折线。给定的路面的一定满足以下性质：

* 第一个坐标点一定是 $(0,0)$；
* 第一个点和第二个点的纵坐标相同；
* 倒数第一个点和倒数第二个点的纵坐标相同；
* 第一个点和第二个点的距离不少于车轮半径；
* 倒数第一个点和倒数第二个点的的距离不少于车轮半径；
* 后一个坐标点的横坐标大于前一个坐标点的横坐标，即对于所有的 $i$，$x_{i+1}>x_i$。

outputFormat:
输出一个实数，四舍五入保留两个小数，表示车轮轴经过的总长度。

你的结果必须和参考答案一模一样才能得分。数据保证答案精确值的小数点后第三位不是 $4$ 或 $5$。


title: [蓝桥杯 2014 省 AB] 蚂蚁感冒

description:
长 $100$ 厘米的细长直杆子上有 $n$ 只蚂蚁。它们的头有的朝左，有的朝右。

每只蚂蚁都只能沿着杆子向前爬，速度是 $1$ 厘米 / 秒。

当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。

这些蚂蚁中，有 $1$ 只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

inputFormat:
第一行输入一个整数 $n(1<n<50)$ 表示蚂蚁的总数。

接着的一行是 $n$ 个用空格分开的整数 $X_i(-100<X_i<100)$，$X_i$ 的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现 $0$ 值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。

outputFormat: 要求输出 $1$ 个整数，表示最后感冒蚂蚁的数目。


title: [蓝桥杯 2014 省 AB] 地宫取宝

description:
X 国王有一个地宫宝库。是 $n \times m$ 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 $k$ 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 $k$ 件宝贝。

inputFormat:
输入一行 $3$ 个整数，用空格分开：$n$，$m$，$k(1 \le n,m \le 50,1 \le k \le 12)$。

接下来有 $n$ 行数据，每行有 $m$ 个整数 $C_i(0 \le C_i \le 12)$ 代表这个格子上的宝物的价值。

outputFormat: 要求输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。该数字可能很大，输出它对 $1000000007(10^9+7)$ 取模的结果。

hint: 时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛


title: [蓝桥杯 2014 省 B] 小朋友排队

description:
$n$ 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是 $0$。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加 $1$，如果第二次要求他交换，则他的不高兴程度增加 $2$（即不高兴程度为 $3$），依次类推。当要求某个小朋友第 $k$ 次交换时，他的不高兴程度增加 $k$。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

inputFormat:
输入的第一行包含一个整数 $n$，表示小朋友的个数。

第二行包含 $n$ 个整数 $H_1,H_2 \cdots H_n$，分别表示每个小朋友的身高。

outputFormat: 输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

hint:
【样例说明】

首先交换身高为 $3$ 和 $2$ 的小朋友，再交换身高为 $3$ 和 $1$ 的小朋友，再交换身高为 $2$ 和 $1$ 的小朋友，每个小朋友的不高兴程度都是 $3$，总和为 $9$。

【数据规模与约定】

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

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

对于 $50\%$ 的数据，$1 \le n \le 10000$；

对于 $100\%$ 的数据，$1 \le n \le 100000$，$0 \le H_i \le 1000000$。

时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛


title: [蓝桥杯 2014 省 A] 波动数列

description:
观察这个数列：

$1,3,0,2,-1,1,-2, \cdots $。

这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$。

栋栋对这种数列很好奇，他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢？

inputFormat: 输入的第一行包含四个整数 $n,s,a,b$，含义如前面说述。

outputFormat: 输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以 $100000007$ 的余数。


title: [蓝桥杯 2014 国 C] 拼接平方数

description:
小明发现 $49$ 很有趣，首先，它是个平方数。它可以拆分为 $4$ 和 $9$，拆分出来的部分也是平方数。$169$ 也有这个性质，我们权且称它们为：拼接平方数。

$100$ 可拆分 $1,00$，这有点勉强，我们规定，$0,00,000$ 等都不算平方数。

小明想：还有哪些数字是这样的呢？

你的任务出现了：找到某个区间的所有拼接平方数。

outputFormat: 若干行，每行一个正整数。表示所有的区间 $[a,b]$ 中的拼接平方数，从小到大输出。

hint: 时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛


title: [蓝桥杯 2014 国 C] 套娃

description:
作为 drd 送的生日礼物，atm 最近得到了一个俄罗斯娃娃。他对这个俄罗斯娃娃的构造很感兴趣。

俄罗斯娃娃是一层一层套起来的。假设：一个大小为 $x$ 的俄罗斯娃娃里面可能会放任意多个大小小于 $x$ 的俄罗斯娃娃（而市场上的套娃一般大娃里只能放一个小娃）。

drd 告诉 atm，这个俄罗斯娃娃是由 $n$ 个小娃娃组成的，它们的大小各不相同。我们把这些小娃娃的大小从小到大依次记为 $1$ 到 $n$。

如果 atm 想观赏大小为 $k$ 的小娃娃，他会先看这个小娃娃是否已经在桌子上了。如果已经在桌子上，那么他就可以观赏了。否则他就打开桌子上某一个俄罗斯娃娃，将它套住的所有的小娃娃拿出来，摆在桌子上。

一开始桌子上只有 drd 送的大小为 $n$ 的娃娃。注意，他只会将其中所有小娃娃拿出来，如果小娃娃里面还套着另外的小娃娃，他是不会将这些更里层的这些小娃娃拿出来的。

而且 atm 天生具有最优化的强迫症。他会最小化他所需要打开的娃娃的数目。

atm 是一个怪人。有时候他只想知道观看大小为 $x$ 的娃娃时需要打开多少个娃娃（但并不去打开）；有时候听 drd 说某个娃娃特别漂亮，于是他会打开看。现在请你输出他每次需要打开多少个娃娃。

inputFormat:
第一行两个数 $n_m$，表示娃娃的数目以及 atm 想看的娃娃的数目。

接下来 $n-1$ 行，每行两个数 $u,v$，表示大小为 $u$ 的娃娃里面套着一个大小为 $v$ 的娃娃。保证 $u>v$。

接下来 $m$ 行，每行形如：

- `P x`：表示 atm 一定要看到大小为 $x$ 的娃娃；

- `Q x`：表示 atm 只想知道为了看大小为 $x$ 的娃娃，他需要打开多少个娃娃，但实际上并不打开他们。

outputFormat: 输出 $m$ 行。对应输入中 $P$ 操作或 $Q$ 操作需要打开（或假想打开）多少个俄罗斯娃娃。


title: [蓝桥杯 2014 国 AC] 重复模式

description:
作为 drd 的好朋友，技术男 atm 在 drd 生日时送给他一个超长字符串 $S$。atm 要 drd 在其中找出一个最长的字符串 $T$，使得 $T$ 在 $S$ 中至少出现了两次，而他想说的秘密就藏在 $T$ 中。

由于字符串实在是太长了，drd 总是找不到合适的 $T$。于是 drd 请你帮他找到这个 $T$ 的长度。

inputFormat: 一行。一个字符串，即题目中说的 $S$。

outputFormat: 一行。一个整数，表示最长的 $T$ 的长度。


title: [蓝桥杯 2014 国 B] Log 大侠

description:
atm 参加了速算训练班，经过刻苦修炼，对以 $2$ 为底的对数算得飞快，人称 Log 大侠。

一天，Log 大侠的好友 drd 有一些整数序列需要变换，Log 大侠正好施展法力。

变换的规则是：对其某个子序列的每个整数变为 $[\log_2(x)+1]$ 其中 [] 表示向下取整，就是对每个数字求以 $2$ 为底的对数，然后取下整。

例如对序列 $3,4,2$ 操作一次后，这个序列会变成 $2,3,2$。

drd 需要知道，每次这样操作后，序列的和是多少。

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

第二行 $n$ 个数，表示整数序列，都是正数。

接下来 $m$ 行，每行两个数 $L$，$R$ 表示 atm 这次操作的是区间 $[L,R]$，数列序号从 $1$ 开始。

outputFormat: 输出 $m$ 行，依次表示 atm 每做完一个操作后，整个序列的和。

hint:
对于 $30\%$ 的数据，$n,m \le 10^3$。

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

时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛

官方数据似乎有错。重造数据按照 $1 \leq a_i \leq 10^9$ 设计。


title: [蓝桥杯 2014 国 B] 殖民地

description:
带着殖民扩张的野心，Pear 和他的星际舰队登上 X 星球的某平原。为了评估这块土地的潜在价值，Pear 把它划分成了 $M \times N$ 格，每个格子上用一个整数（可正可负）表示它的价值。

Pear 要做的事很简单——选择一些格子，占领这些土地，通过建立围栏把它们和其它土地隔开。对于 $M \times N$ 的格子，一共有 $(M+1) \times N+M \times (N+1)$ 条围栏，即每个格子都有上下左右四个围栏；不在边界上的围栏被相邻的两个格子公用。大概如下图 $1$ 所示。

图中，蓝色的一段是围栏，属于格子 $1$ 和 $2$；红色的一段是围栏，属于格子 $3$ 和 $4$。

每个格子有一个可正可负的收益，而建围栏的代价则一定是正的。

你需要选择一些格子，然后选择一些围栏把它们围起来，使得所有选择的格子和所有没被选的格子严格的被隔开。选择的格子可以不连通，也可以有“洞”，即一个连通块中间有一些格子没选。注意，若中间有“洞”，那么根据定义，“洞”和连通块也必须被隔开。

Pear 的目标很明确，花最小的代价，获得最大的收益。

inputFormat:
输入第一行两个正整数 $M,N$，表示行数和列数。

接下来 $M$ 行，每行 $N$ 个整数，构成矩阵 $A$，$A_{i,j}$ 表示第 $i$ 行第 $j$ 列格子的价值。

接下来 $M+1$ 行，每行 $N$ 个整数，构成矩阵 $B$，$B_{i,j}$ 表示第 $i$ 行第 $j$ 列上方的围栏建立代价。

特别的，$B_{M+1,j}$ 表示第 $M$ 行第 $j$ 列下方的围栏建立代价。

接下来 $M$ 行，每行 $N+1$ 个整数，构成矩阵 $C$，$C_{i,j}$ 表示第 $i$ 行第 $j$ 列左方的围栏建立代价。

特别的，$C_{i,N+1}$ 表示第 $i$ 行第 $N$ 列右方的围栏建立代价。

outputFormat: 一行。只有一个正整数，表示最大收益。

hint:
对于 $20\%$ 的数据，$M,N \le 4$。

对于 $50\%$ 的数据，$M,N \le 15$。

对于 $100\%$ 的数据，$M,N \le 200$。

$A,B,C$ 数组（所有的涉及到的格子、围栏输入数据）绝对值均不超过 $1000$。根据题意，$A$ 数组可正可负，$B,C$ 数组均为正整数。

时限 3 秒, 256M。蓝桥杯 2014 年第五届国赛


title: [蓝桥杯 2014 国 A] 排列序数

description:
如果用 a b c d 这 $4$ 个字母组成一个串，有 $4!=24$ 种，如果把它们排个序，每个串都对应一个序号：

```text
  abcd  0
  abdc  1
  acbd  2
  acdb  3
  adbc  4
  adcb  5
  bacd  6
  badc  7
  bcad  8
  bcda  9
  bdac  10
  bdca  11
  cabd  12
  cadb  13
  cbad  14
  cbda  15
  cdab  16
  cdba  17
  ...
```

现在有不多于10个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？

inputFormat: 一行，一个串。

outputFormat: 一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 $0$。

hint: 时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛


title: [蓝桥杯 2014 国 A] 供水设施

description:
X 星球的居民点很多。Pear 决定修建一个浩大的水利工程，以解决他管辖的 $N$ 个居民点的供水问题。现在一共有 $N$ 个水塔，同时也有 $N$ 个居民点，居民点在北侧从 $1$ 号到 $N$ 号自西向东排成一排；水塔在南侧也从 $1$ 号到 $N$ 号自西向东排成一排。

$N$ 条单向输水线（有水泵动力），将水从南侧的水塔引到北侧对应的居民点。

我们不妨将居民点和水塔都看做平面上的点，居民点坐标为 $(1,K) \sim (N,K)$，水塔为 $(1,0) \sim (N,0)$。

除了 $N$ 条纵向输水线以外，还有 $M$ 条单向的横向输水线，连接 $(X_i,Y_i)$ 和 $((X_i)+1,Y_i)$ 或者 $(X_i,Y_i)$ 和 $((X_i)-1,Y_i)$。前者被称为向右的水路，而后者是向左的。不会有两条水路重叠，即便它们方向不同。

布局的示意图如所示。

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

显然，每个水塔的水都可以到达若干个居民点（而不仅仅是对应的那个）。例如上图中，$4$ 号水塔可以到达 $3$ 、 $4$ 、 $5$ 、 $6$ 四个居民点。

现在 Pear 决定在此基础上，再修建一条横向单向输水线。为了方便考虑，Pear 认为这条水路应当是自左向右的，也就是连接了一个点和它右侧的点（例如上图中连接 $5$ 和 $6$ 两个纵线的横向水路）。

Pear 的目标是，修建了这条水路之后，能有尽可能多对水塔和居民点之间能到达。换句话说，设修建之后第 $i$ 个水塔能到达 $A_i$ 个点，你要最大化 $A_1+A_2+ \cdots +A_n$。

根据定义，这条路必须和 X 轴平行，但 Y 坐标不一定要是整数。注意：虽然输入中没有重叠的水路，但是你的方案可以将新修的输水线路与已有的水路重叠。

inputFormat:
输入第一行包含三个正整数 $N$，$M$，$K$，含义如题面所述：$N$ 是纵向线数，$M$ 横向线数，$K$ 是居民点纵坐标。

接下来 $M$ 行，每行三个整数。前两个正整数 $X_i,Y_i$ 表示水路的起点坐标；

$1 \le X_i \le N,0<Y_i<K$。

接下来一个数 $0$ 或者 $1$，如果是 $0$ 表示这条水路向左，否则向右。

保证水路都是合法的，也就是不会流向没有定义的地方。

outputFormat: 输出一行。是一个正整数，即：题目中要求的最大化的 $A_1+A_2+ \cdots +A_n$。


title: [蓝桥杯 2015 省 B] 移动距离

description:
X 星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为 $1,2,3, \cdots $ 。

当排满一行时，从下一行相邻的楼往反方向排号。

比如：当小区排号宽度为 $6$ 时，开始情形如下：

```
1  2  3  4  5  6
12 11 10 9  8  7
13 14 15 .....
```

我们的问题是：已知了两个楼号 $m$ 和 $n$，需要求出它们之间的最短移动距离。（不能斜线方向移动）

inputFormat:
输入为 $3$ 个整数 $w,m,n$，空格分开，都在 $1$ 到 $10000$ 范围内。

$w$ 为排号宽度，$m,n$ 为待计算的楼号。

outputFormat: 要求输出一个整数，表示 $m$ 与 $n$ 两楼间最短移动距离。

hint:
时限 1 秒, 256M。

蓝桥杯 2015 年省赛 B 组 H 题。


title: [蓝桥杯 2015 省 AB] 垒骰子

description:
赌圣 atm 晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。

经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！

我们先来规范一下骰子：$1$ 的对面是 $4$，$2$ 的对面是 $5$，$3$ 的对面是 $6$。

假设有 $m$ 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。

atm 想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。

由于方案数可能过多，请输出模 $10^9+7$ 的结果。

不要小看了 atm 的骰子数量哦～。

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

$n$ 表示骰子数目。

接下来 $m$ 行，每行两个整数 $a$，$b$，表示 $a$ 和 $b$ 数字不能紧贴在一起。

outputFormat: 一行一个数，表示答案模 $10^9+7$ 的结果。


title: [蓝桥杯 2015 省 B] 生命之树

description:
在 X 森林里，上帝创建了生命之树。

他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。

上帝要在这棵树内选出一个节点集合 $S$（允许为空集），使得对于 $S$ 中的任意两个点 $a,b$，都存在一个点列 ${a,v_1,v_2, \cdots ,v_k,b}$ 使得这个点列中的每个点都是 $S$ 里面的元素，且序列中相邻两个点间有一条边相连。

在这个前提下，上帝要使得 $S$ 中的点所对应的整数的和尽量大。

这个最大的和就是上帝给生命之树的评分。

经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算，他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。

inputFormat:
第一行一个整数 $n$ 表示这棵树有 $n$ 个节点。

第二行 $n$ 个整数，依次表示每个节点的评分。

接下来 $n-1$ 行，每行 $2$ 个整数 $u,v$，表示存在一条 $u$ 到 $v$ 的边。由于这是一棵树，所以是不存在环的。

outputFormat: 输出一行一个数，表示上帝给这棵树的分数。

hint:
对于 $30\%$ 的数据，$n \le 10$。

对于 $100\%$ 的数据，$0<n \le 10^5,$ 每个节点的评分的绝对值不超过 $10^6$。

时限 3 秒, 256M。

蓝桥杯 2015 省赛 B 组 J 题。


title: [蓝桥杯 2015 省 A] 灾后重建

description:
Pear 市一共有 $N$（$ \le 50000$）个居民点，居民点之间有 $M$（$ \le 2\times 10^5$）条双向道路相连。这些居民点两两之间都可以通过双向道路到达。这种情况一直持续到最近，一次严重的地震毁坏了全部 $M$ 条道路。

震后，Pear 打算修复其中一些道路，修理第 $i$ 条道路需要 $P_i$ 的时间。不过，Pear 并不打算让全部的点连通，而是选择一些标号特殊的点让他们连通。

Pear 有 $Q$（$ \le 50000$）次询问，每次询问，他会选择所有编号在 $[l,r]$ 之间，并且编号 $\bmod{K}=C$ 的点，修理一些路使得它们连通。由于所有道路的修理可以同时开工，所以完成修理的时间取决于花费时间最长的一条路，即涉及到的道路中 $P_i$ 的最大值。

你能帮助 Pear 计算出每次询问时需要花费的最少时间么？这里询问是独立的，也就是上一个询问里的修理计划并没有付诸行动。

inputFormat:
第一行三个正整数 $N$、$M$、$Q$，含义如题面所述。

接下来 $M$ 行，每行三个正整数 $X_i$、$Y_i$、$P_i$，表示一条连接 $X_i$ 和 $Y_i$ 的双向道路，修复需要 $P_i$ 的时间。可能有自环，可能有重边。$1 \le P_i \le 10^6$。

接下来 $Q$ 行，每行四个正整数 $L_i$、$R_i$、$K_i$、$C_i$，表示这次询问的点是 $[L_i,R_i]$ 区间中所有编号 $\bmod{K_i}=C_i$ 的点。保证参与询问的点至少有两个。

outputFormat: 输出 $Q$ 行，每行一个正整数表示对应询问的答案。


title: [蓝桥杯 2015 国 AC] 穿越雷区

description:
$X$ 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。

某坦克需要从 $A$ 区到 $B$ 区去（$A$，$B$ 区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了 $A$，$B$ 区，其它区都标了正号或负号分别表示正负能量辐射区。

例如：

```
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
```

坦克车只能水平或垂直方向上移动到相邻的区。

inputFormat:
输入第一行是一个整数 $n$，表示方阵的大小，$4 \le n<100$。

接下来是 $n$ 行，每行有 $n$ 个数据，可能是 `A`，`B`，`+`，`-` 中的某一个，中间用空格分开。

outputFormat:
要求输出一个整数，表示坦克从 $A$ 区到 $B$ 区的最少移动步数。

如果没有方案，则输出 $-1$。

hint: 时限 1 秒, 512M。蓝桥杯 2015 年第六届国赛


title: [蓝桥杯 2015 国 C] 机器人繁殖

description:
X 星系的机器人可以自动复制自己。它们用 $1$ 年的时间可以复制出 $2$ 个自己，然后就失去复制能力。
每年X星系都会选出 $1$ 个新出生的机器人发往太空。也就是说，如果X星系原有机器人 $5$ 个，
$1$ 年后总数是：$5 + 9 = 14$
$2$ 年后总数是：$5 + 9 + 17 = 31$

如果已经探测经过 $n$ 年后的机器人总数 $s$，你能算出最初有多少机器人吗？

inputFormat: 输入一行两个数字 $n$ 和 $s$，用空格分开，含义如上。$n$ 不大于 $100$，$s$ 位数不超过 $50$ 位。

outputFormat: 要求输出一行，一个整数，表示最初有机器人多少个。

hint: 时限 1 秒, 512M。蓝桥杯 2015 年第六届国赛


title: [蓝桥杯 2015 国 B] 密文搜索

description:
福尔摩斯从 X 星收到一份资料，全部是小写字母组成。

他的助手提供了另一份资料：许多长度为 $8$ 的密码列表。

福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。

请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。

inputFormat:
输入第一行：一个字符串 $s$，全部由小写字母组成，长度小于 $1024 \times 1024$。

紧接着一行是一个整数 $n,$ 表示以下有 $n$ 行密码，$1 \le n \le 1000$。

紧接着是 $n$ 行字符串，都是小写字母组成，长度都为 $8$。

outputFormat: 一个整数，表示每行密码的所有排列在 $s$ 中匹配次数的总和。

hint:
第一个密码匹配了 $3$ 次，第二个密码匹配了 $1$ 次，一共 $4$ 次。

时限 3 秒, 512M。蓝桥杯 2015 年第六届国赛


title: [蓝桥杯 2015 国 AC] 切开字符串

description:
Pear 有一个字符串，不过他希望把它切成两段。

这是一个长度为 $N$（$ \le 10^5$）的字符串。

Pear 希望选择一个位置，把字符串不重复不遗漏地切成两段，长度分别是 $t$ 和 $N-t$（这两段都必须非空）。

Pear 用如下方式评估切割的方案：

定义“正回文子串”为：长度为奇数的回文子串。

设切成的两段字符串中，前一段中有 $A$ 个不相同的正回文子串，后一段中有 $B$ 个不相同的非正回文子串，则该方案的得分为 $A \times B$。

注意，后一段中的 $B$ 表示的是：“ ... 非正回文 ... ”，而不是：“ ... 正回文 ... ”。

那么所有的切割方案中，$A \times B$ 的最大值是多少呢？

inputFormat:
输入第一行一个正整数 $N$（$ \le 10^5$）

接下来一行一个字符串，长度为 $N$。该字符串仅包含小写英文字母。

outputFormat: 一行一个正整数，表示所求的 $A \times B$ 的最大值。


title: [蓝桥杯 2015 国 B] 居民集会

description:
蓝桥村的居民都生活在一条公路的边上，公路的长度为 $L$，每户家庭的位置都用这户家庭到公路的起点的距离来计算，第 $i$ 户家庭距起点的距离为 $d_i$。

每年，蓝桥村都要举行一次集会。今年，由于村里的人口太多，村委会决定要在 $4$ 个地方举行集会，其中 $3$ 个位于公路中间，$1$ 个位最公路的终点。

已知每户家庭都会向着远离公路起点的方向去参加集会，参加集会的路程开销为家庭内的人数 $t_i$ 与距离的乘积。

给定每户家庭的位置 $d_i$ 和人数 $t_i$，请为村委会寻找最好的集会举办地：$p_1,p_2,p_3,p_4(p_1 \le p_2 \le p_3 \le p_4=L),$ 使得村内所有人的路程开销和最小。

inputFormat:
输入的第一行包含两个整数 $n,L$，分别表示蓝桥村的家庭数和公路长度。

接下来 $n$ 行，每行两个整数 $d_i,t_i$，分别表示第 $i$ 户家庭距离公路起点的距离和家庭中的人数。

outputFormat: 输出一行，包含一个整数，表示村内所有人路程的开销和。

hint:
【样例说明】

在距起点 $2,5,8,10$ 这 $4$ 个地方集会，$6$ 个家庭需要的走的距离分别为 $1,0,1,0,2,0$，总的路程开销为 $1 \times 3+0 \times 2+1 \times 5+0 \times 20+2 \times 5+0 \times 7=18$。

【数据规模与约定】

对于 $10\%$ 的评测数据，$1 \le n \le 300$。

对于 $30\%$ 的评测数据，$1 \le n \le 2000$，$1 \le L \le 10000$，$0 \le d_i \le L$，$d_i \le d_i+1$，$0 \le t_i \le 20$。

对于 $100\%$ 的评测数据，$1 \le n \le 10^5$，$1 \le L \le 10^6$，$0 \le d_i \le L$，$d_i \le d_i+1$，$0 \le t_i \le 10^6$。


title: [蓝桥杯 2015 国 B] 模型染色

description:
在电影《超能陆战队》中，小宏可以使用他的微型机器人组合成各种各样的形状。

现在他用他的微型机器人拼成了一个大玩具给小朋友们玩。为了更加美观，他决定给玩具染色。

小宏的玩具由 $n$ 个球型的端点和 $m$ 段连接这些端点之间的边组成。下图给出了一个由 $5$ 个球型端点和 $4$ 条边组成的玩具，看上去很像一个分子的球棍模型。

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

由于小宏的微型机器人很灵活，这些球型端点可以在空间中任意移动，同时连接相邻两个球型端点的边可以任意的伸缩，这样一个玩具可以变换出不同的形状。在变换的过程中，边不会增加，也不会减少。

小宏想给他的玩具染上不超过 $k$ 种颜色，这样玩具看上去会不一样。如果通过变换可以使得玩具变成完全相同的颜色模式，则认为是本质相同的染色。现在小宏想知道，可能有多少种本质不同的染色。

inputFormat:
输入的第一行包含三个整数 $n,m,k$，

分别表示小宏的玩具上的端点数、边数和小宏可能使用的颜色数。端点从 $1$ 到 $n$ 编号。

接下来 $m$ 行每行两个整数 $a,b$，表示第 $a$ 个端点和第 $b$ 个端点之间有一条边。输入保证不会出现两条相同的边。

outputFormat: 输出一行，表示本质不同的染色的方案数。由于方案数可能很多，请输入方案数除 $10007$ 的余数。


title: [蓝桥杯 2015 国 A] 铺瓷砖

description:
为了让蓝桥杯竞赛更顺利的进行，主办方决定给竞赛的机房重新铺放瓷砖。机房可以看成一个 $n \times m$ 的矩形，而这次使用的瓷砖比较特别，有两种形状，如【图1】所示。在铺放瓷砖时，可以旋转。

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

主办方想知道，如果使用这两种瓷砖把机房铺满，有多少种方案。

inputFormat: 输入的第一行包含两个整数，分别表示机房两个方向的长度。

outputFormat: 输出一个整数，表示可行的方案数。这个数可能很大，请输出这个数除以 $65521$ 的余数。

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

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

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

对于 $20\%$ 的数据，$1 \le n,m \le 5$。

对于 $50\%$ 的数据，$1 \le n \le 100$，$1 \le m \le 5$。

对于 $100\%$ 的数据，$1 \le n \le 10^{15}$，$1 \le m \le 6$。

时限 5 秒, 512M。蓝桥杯 2015 年第六届国赛


title: [蓝桥杯 2016 省 AB] 四平方和

description:
四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 $4$ 个正整数的平方和。

如果把 $0$ 包括进去，就正好可以表示为 $4$ 个数的平方和。

比如：

$5=0^2+0^2+1^2+2^2$。

$7=1^2+1^2+1^2+2^2$。

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 $4$ 个数排序使得 $0 \le a \le b \le c \le d$。

并对所有的可能表示法按 $a,b,c,d$ 为联合主键升序排列，最后输出第一个表示法。

inputFormat: 程序输入为一个正整数 $N(N<5\times10^6)$。

outputFormat: 要求输出 $4$ 个非负整数，按从小到大排序，中间用空格分开。

hint:
时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 A 组 H 题（B 组 H 题）。


title: [蓝桥杯 2016 省 AB] 最大比例

description:
X 星球的某个大奖赛设了 $M$ 级奖励。每个级别的奖金是一个正整数。

并且，相邻的两个级别间的比例是个固定值。

也就是说：所有级别的奖金数构成了一个等比数列。比如：

$$16,24,36,54$$

其等比值为：$3/2$。

现在，我们随机调查了一些获奖者的奖金数。

请你据此推算可能的最大的等比值。

inputFormat:
第一行为数字 $N(0<N<100)$，表示接下的一行包含 $N$ 个正整数。

第二行 $N$ 个正整数 $X_i(X_i<10^{12})$，用空格分开。每个整数表示调查到的某人的奖金数额。

outputFormat:
一个形如 $A/B$ 的分数，要求 $A$、$B$ 互质。表示可能的最大比例系数。

测试数据保证了输入格式正确，并且最大比例是存在的。

hint:
时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 A 组 J 题（B 组 J 题）。


title: [蓝桥杯 2016 省 B] 交换瓶子

description:
有 $N$ 个瓶子，编号 $1 \sim N$，放在架子上。

比如有 $5$ 个瓶子：

$$2,1,3,5,4$$

要求每次拿起 $2$ 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

$$1,2,3,4,5$$

对于这么简单的情况，显然，至少需要交换 $2$ 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

inputFormat:
第一行：一个正整数 $N$（$N<10000$），表示瓶子的数目。

第二行：$N$ 个正整数，用空格分开，表示瓶子目前的排列情况。

outputFormat: 输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

hint:
时限 1 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 B 组 I 题。


title: [蓝桥杯 2016 国 C] 赢球票

description:
某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。

主持人拿出 $N$ 张卡片（上面写着 $1 \sim N$ 的数字），打乱顺序，排成一个圆圈。

你可以从任意一张卡片开始顺时针数数 $:1,2,3 \cdots $。

如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。

直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。

比如：

卡片排列是：$1,2,3$。

我们从 $1$ 号卡开始数，就把 $1$ 号卡拿走。再从 $2$ 号卡开始，但数的数字无法与卡片对上，

很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了 $1$ 张球票。

还不算太坏！如果我们开始就傻傻地从 $2$ 或 $3$ 号卡片数起，那就一张卡片都拿不到了。

如果运气好，卡片排列是 $2,1,3$。

那我们可以顺利拿到所有的卡片！

本题的目标就是：已知顺时针卡片序列。

随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）

inputFormat:
第一行一个整数 $N(N<100)$，表示卡片数目。

第二行 $N$ 个整数，表示顺时针排列的卡片。

outputFormat: 一行，一个整数，表示最好情况下能赢得多少张球票。

hint: 时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛


title: [蓝桥杯 2016 国 AC] 路径之谜

description:
小明冒充 $X$ 星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 $n\times n$ 个方格。如图所示。

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

按习俗，骑士要从西北角走到东南角。

可以横向或纵向移动，但不能斜着走，也不能跳跃。

每走到一个新方格，就要向正北方和正西方各射一箭。

（城堡的西墙和北墙内各有 $n$ 个靶子）

同一个方格只允许经过一次。但不必做完所有的方格。

如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？

有时是可以的，比如如图中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

inputFormat:
第一行一个整数 $N(0<N<20)$，表示地面有 $N \times N$ 个方格。

第二行 $N$ 个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行 $N$ 个整数，空格分开，表示西边的箭靶上的数字（自北向南）

outputFormat:
一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号 $:0,1,2,3 \cdots $。

比如，图中的方块编号为：

```
0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15
```

hint: 时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛


title: [蓝桥杯 2016 国 AC] 碱基

description:
生物学家正在对 $n$ 个物种进行研究。

其中第 $i$ 个物种的 DNA 序列为 $s[i]$，其中的第 $j$ 个碱基为 $s[i][j],$ 碱基一定是 `A`,`G`,`C`,`T` 之一。

生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在 $m$ 个生物中出现的长度为 $k$ 的连续碱基序列。准确的说，科学家关心的序列用 $2m$ 元组 $(i_1,p_1,i_2,p_2 \cdots ,i_m,p_m)$ 表示，

满足：

$$1 \le i_1<i_2< \cdots <i_m \le n$$

且对于所有 $q(0 \le q<k)$，

$$s[i_1][p_1+q]=s[i_2][p_2+q]= \cdots =s[i_m][p_m+q]$$

现在给定所有生物的 DNA 序列，请告诉科学家有多少的 $2m$ 元组是需要关注的。如果两个 $2m$ 元组有任何一个位置不同，则认为是不同的元组。

inputFormat:
输入的第一行包含三个整数 $n$，$m$，$k$，两个整数之间用一个空格分隔，意义如题目所述。

接下来 $n$ 行，每行一个字符串表示一种生物的 DNA 序列。

DNA 序列从 $1$ 至 $n$ 编号，每个序列中的碱基从 $1$ 开始依次编号，不同的生物的 DNA 序列长度可能不同。

outputFormat:
输出一个整数，表示关注的元组个数。

答案可能很大，你需要输出答案除以 $1000000007(10^9+7)$ 的余数。

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

对于 $20\%$ 的数据，$k \le 5,$ 所有字符串总长 $L$ 满足 $L \le 100$。

对于 $30\%$ 的数据，$L \le 10000$。

对于 $60\%$ 的数据，$L \le 30000$。

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

保证所有 DNA 序列不为空且只会包含`A`,`G`,`C`,`T` 四种字母。

时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛


title: [蓝桥杯 2016 国 B] 机器人塔

description:
X 星球的机器人表演拉拉队有两种服装，A 和 B。

他们这次表演的是搭机器人塔。

类似：

```
     A
    B B
   A B A
  A A B B
 B B B A B
A B A B B A
```

队内的组塔规则是：

A 只能站在 AA 或 BB 的肩上。

B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下，在给定 A 与 B 的人数时，可以组成多少种花样的塔。

inputFormat: 输入一行两个整数 $M$ 和 $N$，空格分开（$0<M,N<N+M<231$，保证存在 $k\in \mathbb{N}$，$N+M=\frac{k(k-1)}{2}$），分别表示 A、B 的人数。

outputFormat: 要求输出一个整数，表示可以产生的花样种数。

hint: 时限 1 秒, 256M。蓝桥杯 2016 年第七届


title: [蓝桥杯 2016 国 B] 广场舞

description:
LQ 市的市民广场是一个多边形，广场上铺满了大理石的地板砖。

地板砖铺得方方正正，就像坐标轴纸一样。

以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。

广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。

舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。

（广场形状的例子参考图）

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

现在，告诉你广场的形状，请帮 LQ 市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。

inputFormat:
输入的第一行包含一个整数 $n$，表示广场是 $n$ 边形的（因此有 $n$ 个顶点）。

接下来 $n$ 行，每行两个整数，依次表示 $n$ 边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。

outputFormat: 输出一个整数，表示最多有多少市民可以在广场跳舞。

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

广场如图所示，一共有 $7$ 块完整的地板砖，因此最多能有 $7$ 位市民一起跳舞。

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

对于 $30\%$ 的数据，$n$ 不超过 $100$，横纵坐标的绝对值均不超过 $100$。

对于 $50\%$ 的数据，$n$ 不超过 $1000$，横纵坐标的绝对值均不超过 $1000$。

对于 $100\%$ 的数据，$n$ 不超过 $1000$，横纵坐标的绝对值均不超过 $10^8$。

时限 1 秒, 256M。蓝桥杯 2016 年第七届


title: 「EZEC-5」人赢 加强版

background:
> “我们在 小 Z 面前秀个恩爱吧。”\
>“好的。”

小 Z 发现他身边都是人赢，这使他非常自闭。

小 Z 又看着身边的潇，不禁陷入了沉思……

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

description:
潇有一个数组 $k$，下标为 $1$ 到 $n$ 。

潇定义 $f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}$ 。

潇想知道对于任意的 $1 \le x,y \le n$，$f(x,y)$ 的最大值是多少。但是她不会做，于是就问了善良的 小 Z，然而非常想在妹子面前表现的 小 Z 发现他也不会做，就只能够求助善良的你了。

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

第二行 $n$ 个整数 $k$，第 $i$ 个整数为 $k_i$。含义如上文。

outputFormat: 一行一个整数，表示对于任意的 $1 \le x,y \le n$，$f(x,y)$ 的最大值。

hint:
### 数据范围

**本题采用捆绑测试。**

- Subtask 1（10 points）：$1 \le n \le 50$。

- Subtask 2（20 points）：$1 \le n \le 5000$。

- Subtask 3（20 points）：$1 \le n \le 10^6$。

- Subtask 4（10 points）：保证所有 $k_{i}$ 都相等。

- Subtask 5（40 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^7$，$1 \le k_{i} \le 10^9$。

**本题建议使用较快的读入方式。**

std 使用的快读：

```cpp
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
```


title: station

description:
你需要规划一个城市的公交路线。

总共有 $n$ 条路线和 $m$ 个车站，编号均从 $1$ 开始。

你的主要任务是，规划每一条路线应该经过哪些车站。换言之，你要任意选择一个车站的子集，让这条路线经过这个子集中的所有车站。

定义两条路线是**关联**的，当且仅当它们经过了同一个车站，也就是它们的经过车站集合有交。

一个路线方案必须满足如下限制：

1. 一条线路不可能只通过一个车站，所以**每条线路至少要经过两个车站**；

2. 一个车站的运载能力是有限的，所以**一个车站最多只能被三条线路经过**。

3. 为了保证交通顺畅，对于任意两条不同线路 $i, j(i \not = j)$，都存在第三条线路 $k (k \not = i, k \not = j)$，使得 $k$ 与 $i, j$ 均**关联**。

现给定 $n$，请求出一个最小的 $m$ 和具体规划方案。

inputFormat: 一行一个正整数 $n$，含义如题目所示。

outputFormat:
第一行输出一个正整数 $m$，表示在你的规划方案中所用车站的数量。

接下来 $n$ 行中，第 $i$ 行输出一个正整数 $c$ 和若干个正整数 $a _1, a _2, \cdots, a _c$，表示在你的方案中第 $i$ 条路线经过的车站数目以及经过车站的编号。

hint:
#### 「样例 1 解释」

如图所示。

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

首先易知其满足题目描述中所给定的一、二条件。下面考虑三条件。

先考虑 $1, 2, 4$ 号线，可以发现这三条线路构成了一个三角形，任意两个线路均有剩下的一条线路与它们**关联**；

再对 $3$ 号线与 $1, 2, 4$ 号线分别考虑，容易验证满足对于任意 $x \in \{1, 2, 4\}$，均有另一条线路 $y \in \{1, 2, 4\}, y \not = x$ 与 $3, x$ 同时**关联**，满足题目条件。

---

#### 「Special Judge 说明与评分细则」

**请认真阅读输出格式**。

如果你的输出出现了如下情况，将会被判为 $0$ 分：

- 输出格式不符。如没有正确换行，输出了一些奇奇怪怪的字符，未输出车站个数等。
- 某一条线路经过了相同的车站，或者有某一个车站的编号不在 $[1, m]$ 内。
- 没有满足题目描述中所给定的三条限制。
- 输出文件大小过大或者是 $m$ 过大。如果你的 $m$ 大于 $10 ^6$ 将直接判为 $0$ 分。输出文件过大将导致 TLE 或 OLE，建议将输出文件大小控制在 25Mb 以内。

在没有被判为 $0$ 分的基础上，将会根据你输出的 $m$ 的大小进行判分。

每个测试点评测时会有 $10$ 个评测参数 $w _1, w _2, \cdots, w _{10}$，若你输出的 $m$ 小于等于其中 $k$ 个参数，那么你将得到该测试点 $k \times 10\%$ 的分数。

这 $10$ 个参数是对外不可见的，也即你的程序在运行时无法获知这些评测参数。

---

#### 「数据范围」

**本题采用捆绑测试**。你在某个 subtask 的得分为在**该 subtask 的所有测试点中的最小得分**。

- Subtask 1(20 points)：$n \le 10$。此处我们保证 $10$ 个评分参数均为 $10 ^6$。
- Subtask 2(40 points)：$n \le 200$。
- Subtask 3(40 points)：无特殊限制。

对于所有数据，均满足 $3 \le n \le 4 \times 10 ^3$，且 $ans + 5 \le w _1 \le w _2 \le \cdots \le w _{10} = 10 ^6$，其中 $ans$ 表示标准答案。

请注意此处的 $w _{10} = 10^6$ 的条件。


title: [蓝桥杯 2017 省 AB] 包子凑数

description:
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 $N$ 种蒸笼，其中第 $i$ 种蒸笼恰好能放 $A_i$ 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 $X$ 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 $X$ 个包子。比如一共有 $3$ 种蒸笼，分别能放 $3$ 、 $4$ 和 $5$ 个包子。当顾客想买 $11$ 个包子时，大叔就会选 $2$ 笼 $3$ 个的再加 $1$ 笼 $5$ 个的（也可能选出 $1$ 笼 $3$ 个的再加 $2$ 笼 $4$ 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 $3$ 种蒸笼，分别能放 $4$ 、 $5$ 和 $6$ 个包子。而顾客想买 $7$ 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

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

以下 $N$ 行每行包含一个整数 $A_i$。$(1 \le A_i \le 100)$。

outputFormat: 一个整数代表答案。如果凑不出的数目有无限多个，输出 `INF`。

hint:
对于样例 $1$，凑不出的数目包括：$1,2,3,6,7,11$。

对于样例 $2$，所有奇数都凑不出来，所以有无限多个。

蓝桥杯 2017 省赛 A 组 H 题。


title: [蓝桥杯 2017 省 AB] 分巧克力

description:
儿童节那天有 $K$ 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i \times W_i$ 的方格组成的长方形。

为了公平起见，小明需要从这 $N$ 块巧克力中切出 $K$ 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数。

2. 大小相同。

例如一块 $6 \times 5$ 的巧克力可以切出 $6$ 块 $2 \times 2$ 的巧克力或者 $2$ 块 $3 \times 3$ 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小 $H_i$ 计算出最大的边长是多少么？

inputFormat:
第一行包含两个整数 $N$ 和 $K$。$(1 \le N,K \le 10^5)$。

以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。$(1 \le H_i,W_i \le 10^5)$。

输入保证每位小朋友至少能获得一块 $1 \times 1$ 的巧克力。

outputFormat: 输出切出的正方形巧克力最大可能的边长。

hint: 蓝桥杯 2022 省赛 A 组 I 题。