title: [COCI2006-2007#5] IVANA

description:
给定 $n$ 个整数排成一圈，两位玩家进行如下的取数规则：

- 第一次取数的玩家可以取任意一个数；
- 第二次取数的玩家只能从上一次取得数的左右两边相邻的两个数中取一个；
- 第三次取数的玩家可以从之前所有取过的任意一个数的左右两边相邻的两个数中取一个；

其中，与第一个数和第 $n$ 个数相邻的只有一个数。

两位玩家轮流取数。在所有的数都被取完之后，取得奇数多的玩家胜利。

请你找出，先手玩家有多少种不同的开局方法，使得自己能够赢得比赛。

inputFormat:
输入第一行一个整数 $n$ ,表示数字的数量。

第二行 $n$ 个数，表示具体的数字。

outputFormat: 输出一行一个整数，表示先手玩家赢得比赛的开局种类数。

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

对于 $100\%$ 的数据，保证 $1\le n\le 100$，读入的数字都在 $1\sim 1000$ 之间。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #5](https://hsin.hr/coci/archive/2006_2007/contest5_tasks.pdf) *T5 IVANA***。


title: [COCI2006-2007#5] DVAPUT

type: P

description: 给定一个长度为 $L$ 的字符串，你需要找出一个最长的子串，**并且使得这个子串在字符串中出现了至少两次**（在不同的位置）。输出它的长度。

inputFormat:
输入第一行一个整数 $L$，表示字符串的长度。

第二行为一个长度为 $L$ 的字符串。

outputFormat: 输出一行一个整数，表示这个最长串的长度。

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

对于 $100\%$ 的数据，保证 $1\le L\le 2\times 10^5$，输入的字符串都为小写字母。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #5](https://hsin.hr/coci/archive/2006_2007/contest5_tasks.pdf) *T6 DVAPUT***。


title: 「EZEC-2」数轴

description:
小 X 画了一条数轴，他将进行 $n$ 次操作，每次操作他会先在数轴上的 $x_i$ 位置上增添 $a_i$ 个标记。

然后他需要选择二元组 $(l,r)$，满足 $l,r$ 为整数， $0\le l\le r \le m$，且在数轴上的区间 $[l,r]$ 上的标记的个数**小于等于** $k$。

对于每次操作，你需要求出满足条件的二元组 $(l,r)$ 中 $r-l$ 的最大值。

inputFormat:
第一行，三个整数，$n,m$ 和 $k$。

下面 $n$ 行，每行两个整数 $x_i$ 和 $a_i$。

outputFormat:
共 $n$ 行，表示每次操作后的答案。

若找不到符合条件的二元组 $(l,r)$，输出 `-1`。


title: 「Wdoi-1」完美冻结

background: 琪露诺是一个喜欢研究数表的女孩子。

description:
琪露诺有 $n$ 个正整数 $a_1,a_2,...,a_n$，她会按照如下方式构造一个大小为 $n\times n$ 的数字表格：

- 定义数表的左下角为 $(1,1)$，右上角为 $(n,n)$，从左向右数第 $x$ 列，从下向上数第 $y$ 行的位置为 $(x,y)$。在数表的每个位置填入数字 $0$，然后在每个 $(i,i) (1\le i\le n)$ 处填入 $a_i$

- 枚举数表中的每一个 $2\times 2$ 大小的子矩阵，当子矩阵左下角和右上角的数字**都不为 $0$** 时，记该子矩阵中从左到右，从上到下的数字分别为 $a,b,c,d$，进行以下操作：

	- 若 $a=0$，$d=0$，则在数表中 $a,d$ 所处的位置填入 $b+c$
    - 若 $a=0$，$d\neq 0$，则在数表中 $a$ 所处的位置填入 $b+c-d$
    - 若 $a\neq 0$，$d=0$，则在数表中 $d$ 所处的位置填入 $b+c-a$

- 重复第二步操作直至数表中的每一个位置都填有**正整数**  。

- 最后，将数表中的每个数 $a_{ij}$ 变为 $\lfloor \frac{a_{ij}}{k} \rfloor $，其中 $k$ 是一给定常数，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

构造完 $n\times n$ 的巨大数表后，琪露诺会进行 $q$ 次查询，每次询问数表中以  $(x_1,y_1)$ 为左下角，$(x_2,y_2)$ 为右上角的子矩阵中所有数字的和。

头脑简单的琪露诺想了一天又一天，却始终没有头绪，因此她找到了聪明的你帮她解决这个问题。

当然，由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果即可。

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

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

之后 $q$ 行，每行四个正整数 $x_1,y_1,x_2,y_2$，表示询问子矩阵的左下角和右上角坐标。

outputFormat: 共 $q$ 行，每行一个整数，表示每一个询问的答案对 $998244353$ 取模后的结果。


title: [COCI2016-2017#2] Go

description:
在游戏《进化！宝可梦》中，Mirko 拥有 $n$ 只宝可梦。为了完成对它们的进化，Mirko 为第 $i$ 只宝可梦准备了 $m_i$ 颗糖果。

每次进化第 $i$ 只宝可梦，都需要消耗 $k_i$ 颗为其准备的糖果。进化完成后，Mirko 将获得 $2$ 颗相应的糖果作为奖励。需要注意，所有宝可梦都只能使用相应的糖果进行进化。

Mirko 想知道他总共能完成多少次对宝可梦的进化，并找出进化次数最多的一只宝可梦。如果进化次数最多的宝可梦不唯一，请选择更早在输入中出现的那一只。

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

接下来 $2\times n$ 行：

- 第 $2\times i$ 行一个字符串，表示 Mirko 的第 $i$ 只宝可梦的名字。

- 第 $2\times i+1$ 行两个整数 $k_i,m_i$。

outputFormat:
第一行一个整数，表示 Mirko 能完成对宝可梦进化的总次数。

第二行一个字符串，表示进化次数最多的宝可梦的名字。

samples:
4
Caterpie
12 33
Weedle
12 42
Pidgey
12 47
Rattata
25 71

samples:
7
Bulbasaur
25 74
Ivysaur
100 83
Charmander
25 116
Charmeleon
100 32
Squirtle
25 1
Wartortle
100 173
Pikachu
50 154

hint:
#### 样例 1 解释

对于 Weedle 的第一次进化，Mirko 消耗了 $12$ 颗糖果，然后获得 $2$ 颗糖果作为奖励。此时，还剩下 $42-12+2=32$ 颗糖果供 Weedle 进化。这样，Mirko 共能完成 $4$ 次对 Weedle 的进化。

类似地，Mirko 能进化 $3$ 次 Caterpies，$4$ 次 Pidgeys 和 $3$ 次 Rattatas。累计能完成 $14$ 次进化，即为答案的第一部分。

其中，Weedle 和 Pidgeys 的进化次数最多，均为 $4$ 次。由于 Weedle 比 Pidgeys 更早在输入中出现，故将 `Weedle` 作为答案的第二部分。

------------

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 70$，$12\le k_i\le 400$，$1\le m_i\le 10^4$。

所有字符串的长度不超过 $20$，且都仅包含大小写字母。

------------

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T1 Go_**。


title: 座位调查

background: ION 2048 结束了，但 ℲƆƆ 发现，一个机房里发生了性质恶劣的作弊事件。

description:
Youyou 奉命来到该机房进行调查。已知该机房是一个 $n \times m$ 的矩阵，每个位置是 `O` 或 `X`，其中 `O` 表示该位置是座位，`X` 表示该位置是空地。**每个座位上都必须坐有学生**，当然，至少有一个座位。

要想查明作弊的学生，Youyou 必须知道这个机房中的考生有多少种座位的可能。ION 2048 有来自 $k$ 个学校的考生参加，且座位满足以下要求：

* 考场中的座位是由若干长条形组成的，这样方便管理；
* 任意考生不可能和来自同学校的考生座位相邻，可以避免交流。

两个座位是相邻的当且仅当它们有一条**公共边**。

条形定义为除了两个端点只有一个相邻的座位外，每个座位都恰好有两个相邻座位，当然，一个座位也属于条形的。

例如，下面的都**是**「条形的座位」。

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

下面的都**不是**「条形的座位」。

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

注：方格中的数字表示与其相邻的座位的个数。

试求出合法的座位方案总数，由于结果可能很大，请输出结果对质数 $998244353$ 取模的结果。如果这个机房本身就不可能是 ION 2048 的考试机房，答案应当是 $0$。

inputFormat:
第一行三个正整数，$n,m$ 和 $k$。

接下来 $n$ 行，每行 $m$ 个字符，表示机房的情况。保证只有 `O`，`X` 两种字符，且 `O` 至少出现一次。

outputFormat: 一行一个整数，表示结果对质数 $998244353$ 取模的结果。

hint:
**样例 1 解释**

可能有以下 $4$ 种情况，红色代表学校 $1$ 的学生，蓝色代表学校 $2$ 的学生：

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

**样例 2 解释**

可能有以下 $12$ 种情况，红色代表学校 $1$ 的学生，蓝色代表学校 $2$ 的学生，黄色代表学校 $3$ 的学生：

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

**样例 3 解释**

机房不是条形安排的，所以答案为 $0$。

**数据规模与约定**

* Subtask 1（10 分）：$n = 1$，$k = 2$；
* Subtask 2（15 分）：$n = 1$，$2 \le m,k \le 8$；
* Subtask 3（15 分）：$n = 1$；
* Subtask 4（20 分）：保证座位设置是条形的，$k = 2$；
* Subtask 5（20 分）：保证座位设置是条形的；
* Subtask 6（20 分）：无特殊限制。

对于全部的数据，$1 \le n, m \le 10^3$，$2 \le k \le 10^9$。


title: Promises I Can't Keep

background:
>I had so much certainty
Til that moment I lost control
And I've tried but it never was up to me
I've got no worse enemy
Than the fear of what's still unknown
And the time's come to realize there will be
Promises I can't keep

description:
RFMC 给了你一个电路，一个电源，他希望你能把电源接在电路的某一个节点上，让电流流通，并答应给你电路显示屏上的数那么多钱。

这个电路有 $n$ 个节点，每个节点有一个权值 $val_i$，以 $n-1$ 条导线互相连通。你可以把电源接在任意一个起点上。接着，电流从这个节点开始流。若当前电源接到了一个节点 $u$，则接下来电流会**等概率**且**不重复经过一个点地**流向**一个叶子节点**，电流流过的所有节点的权值即为电路显示屏上的数（叶子节点即为 **除了 $u$** 的度数为 1 的节点）。

现在你有 $n$ 种接电源的选择，你希望接上电源以后期望得分越高越好，所以你现在就要在规定的时间内求出这 $n$ 种期望值中最大的的一个。

inputFormat:
第一行一个整数 $n$ 意义如题目所述。

接下来 $n-1$ 行每行两个整数 $u,\ v$，表示有一条联通编号为 $u,\ v$ 节点的导线。

接下来一行 $n$ 个整数，第 $i$ 个整数为 $val_i$，表示第 $i$ 个节点的权值。

outputFormat:
输出一行一个浮点数，表示最大期望值。

**本题使用 special judge，你的答案和正确答案误差不超过 $10^{-2}$ 即可通过。标准答案保留 4 位小数。**

hint:
样例一的解释：

电源接在 5 号节点时有两种情况：$5\rightarrow 1\rightarrow 2\rightarrow 3$ 或 $5\rightarrow 1\rightarrow 2\rightarrow 4$，两种情况得分分别为 8 和 6，期望值即为 7，可以证明没有其他节点接通电源的期望值比 7 大。

---

**本题采用捆绑测试，每一档部分分对应一个 subtask。**

对于 $30\%$ 的数据，保证 $2<n\le 10^3$。
对于另外 $20\%$ 的数据，保证是一条链。
对于所有的数据，保证 $2<n\le 5\times10^5,\  |val_i|\le10^4$。

本题的 special judge 代码已经在附件中给出。

附：本题数据量较大，可以采用更快的读入方法。（标程在用 ```scanf``` 的情况下可以通过）

~~后记：按照题目名称，RFMC 是不会遵守诺言的（大雾~~

题目名其实是一首歌名啦。


title: [COCI2013-2014#1] TRENER

background:
有一些字符串，需要你按特定要求统计。

## 请不要只输出 `PREDAJA`，浪费洛谷评测资源！

description:
给出 $n$ 个字符串，每个字符串都有其对应首字母。

输出首字母对应字符串数量不低于 $5$ 的首字母个数。

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

接下来 $n$ 行每行包含一个仅由小写字母组成的字符串，长度不超过 $30$ 个字符。

outputFormat:
若不存在符合题目要求的首字母，输出 `PREDAJA`。

否则按字典序输出所有首字母，其中无空格。

samples:
18
babic
keksic
boric
bukic
sarmic
balic
kruzic
hrenovkic
beslic
boksic
krafnic
pecivic
klavirkovic
kukumaric
sunkic
kolacic
kovacic
prijestolonasljednikovic

samples:
6
michael
jordan
lebron
james
kobe
bryant

hint:
#### 【数据规模与约定】
对于 $100 \% $ 的数据，$1\le n \le150$。

#### 样例 1 解释

符合条件的首字母是 `k` 和 `b`。

------
#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf)  T1 _TRENER_。**

------------
$\mathtt{Subtask \ 0}$ 为样例数据。（注意：仅用于调试程序）

$\mathtt{Subtask \ 1\sim Subtask\ 2}$无特殊限制。


title: 分散层叠算法(Fractional Cascading)

background:
`Fractional Cascading` 算法，国内多译为“分散层叠”。

本题仅提供一个简单而经典的方式给算法验证正确性，原则上会尽量卡掉比较暴力的做法，但不保证乱搞一定无法通过。

description:
给出 $k$ 个长度为 $n$ 的**有序数组**。

现在有 $q$ 个查询 : 给出数 $x$，分别求出每个数组中大于等于 $x$ 的最小的数(非严格后继)。

若后继不存在，则定义为 $0$。

每个查询的答案定义为 $k$ 个后继的**异或和**。

你需要**在线地**回答这些询问。

由于输出太多不好，给出参数 $d$，你只需要输出编号为 $d$ 的倍数的询问的答案。询问从 $1$ 开始编号。

inputFormat:
第一行四个整数 $n,k,q,d$，意义如题面所述。

后 $k$ 行，每行 $n$ 个整数，描述一个数组。**所有数组中出现过的数不重复**，保证每个数组严格递增。

后 $q$ 行，每行一个整数 $x$，描述一个询问。

输入中所得的 $x$ 需要与上一个询问的答案(**无论是否输出**)异或解密，如果这是第一个询问，则无需操作。

outputFormat: 对于编号为 $d$ 的倍数的每个询问，输出一行一个整数，表示  $k$ 个后继的异或和。


title: [COCI2013-2014#1] KUŠAČ

background: 顿顿邀请你来均分香肠啦。

description:
共有 $n$ 个香肠，需将其平均分给 $m$ 个品尝者。

每刀可将香肠分为两份，要求用尽可能少的刀数切出符合要求的香肠，问至少要切几刀。

inputFormat: 输入仅一行，两个正整数 $n$ 和 $m$。

outputFormat: 输出一行，表示最少要切的刀数。

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

#### 样例 1 解释
有 $2$ 个香肠和 $6$ 个品尝者，将每个香肠三等分，共 $4$ 刀。
#### 样例 2 解释
有 $3$ 个香肠，$4$ 个品尝者。将香肠切成 $\tfrac{3}{4}$。前三人拿到 $\tfrac{3}{4}$，最后一人拿到 $3\times \tfrac{1}{4}$。

---

#### 【数据规模与约定】
对于全部的测试点，保证 $1\le n,m\le 100$。

---

#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf)  _T2 KUŠAČ_。**


title: [COCI2013-2014#1] LOPOV

background: 有一些物品和一个小偷。

description:
有 $N$ 件物品，每件物品有质量 $M_i$ 和价值 $V_i$。

Mirko 有 $K$ 个袋子，每袋可容纳的最大质量为 $C_i$。

每袋仅能放一个物品，问最多可以带走多少价值的物品？

inputFormat:
第一行包含两个正整数 $N$ 和 $K$。

接下来 $N$ 行中的每行包含两个正整数 $M_i$ 和 $V_i$。

接下来 $K$ 行中的每行包含一个正整数 $C_i$。

outputFormat: 输出一行，能拿走的最大物品总价值。

hint:
#### 【数据规模与约定】
- $1\le N,K\le 3\times 10^5$。
- $1\le M_i,V_i\le 10^6$。
- $1\le C_i\le 10^8$。

#### 样例 2 解释
Mirko 将第一件物品放在第二袋中，将第三件物品放在第一袋中。

-------
#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf)  _T4 LOPOV_。**


title: [COCI2013-2014#1] RATAR

description:
给出一个 $n\times n$ 的矩阵，问有多少对子矩阵有且仅有一个公共顶点，并且元素和相等。

请注意，这里的**公共顶点**是指**顶点相交**，而不是**存在一个公共格子**。请参考样例 1 来理解“**公共顶点**”的含义。

inputFormat:
输入的第一行包含正整数 $n$。

接下来 $n$ 行每行 $n$ 个整数，表示为 $a_{i,j}$，**可能有负数**。

outputFormat: 输出仅一行，符合条件的方案数。


title: [COCI2013-2014#1] SLASTIČAR

background: 你需要比较一些序列号。

description:
现有 $M$ 个由数字 $0$ 到 $9$ 组成的短序列号和一个长度为 $N$ 的长序列号。

检查序列号 $A$ 是否包含长度为 $L$ 的序列号 $B$ 的过程如下：

- 将 $A$ 从位置 $1$ 到 $L$ 逐位与 $B$ 比较，一找到不同就将搜索段整体向后移，如果确定相等则停止比较。

- 将搜索段后移意为把 $x$ 到 $y$ 的搜索区域后移为 $x+1$ 和 $y+1$。

- 若剩下用于比较的位数不够，则在字符串末尾填充 `#`。如字符串为 `563232`，从位置 $4$ 到 $10$ 的填充为 `232####`。

- 若尝试了所有段均不匹配则停止比较。

对于每个短序列号，输出停止比较前比较的次数。

inputFormat:
输入的第一行是正整数 $N$。

输入的第二行是一个长度为 $N$ 的长序列号。

输入的第三行包含正整数 $M$。

接下来 $M$ 行每行包含一个长度不超过 $10^5$ 的短序列号。

短序列号总长度不超过 $3\times 10^6$。

outputFormat: 输出 $M$ 个整数，即对于第 $i$ 个短序列号所需的比较次数。

hint:
#### 【数据规模与约定】
- 对于 $20\%$ 的数据，$1\le N\le 10^3$，$1\le M\le 500$，任意短序列号长度均不超过 $10^3$。
- 对于 $100\%$ 的数据，满足 $1\le N\le 10^5$，$1\le M\le 5\times 10^4$。
- 对于任意序列号中的一位字符 $c$，满足 $c\in\{0,1,2,3,4,5,6,7,8,9 \}$。

#### 【样例解释】

#### 样例 1 解释

第一个序列号：
- 机器人为每个段查找不同的第一位数字，总共进行 $7$ 次比较。

第二个序列号：
- 尝试第一个位置，立即发现差异，$1$ 次比较。
- 尝试第二个位置，找到第四个数字的差异，$4$ 次比较。
- 尝试第三个位置，立即找到差异，$1$ 次比较。
- 尝试第四个位置，找到匹配，$4$个比较。
- 总计 $10$ 次比较。

第三序列号：
- 立即找到匹配项，总计 $3$ 个比较。

第四个序列号：
- 在第二个位置找到匹配项，总计 $1+3=4$ 个比较。

#### 样例 3 解释
按顺序将序列号 `11` 与段 `00`，$1$ 次比较，`01`，$1$ 次比较，和`1#`，$2$ 次比较，总计 $4$ 次比较。

--------
#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf)  _T6 SLASTIČAR_。**


title: [COCI2013-2014#1] ORGANIZATOR

background: 有一场比赛，要求你算出参加决赛的人数。

description:
参加决赛的人数满足以下描述：

现有 $n$ 个整数，分别为 $A_1,A_2,\cdots,A_n$。

需要找到一个正整数 $x$，假设有 $m(m \geq 2)$ 个 $A_i$ 是 $x$ 的倍数，则参加决赛的人数是 $s$，他的值为 $m\cdot x$。

请注意，对于一个正整数 $x$，如果其对应的 $m$ 值为 $1$，则该方案不合法。

请找出令 $s$ 尽可能大的 $x$，并输出 $s$。

inputFormat:
输入的第一行包含正整数 $n$。

输入的第二行包含 $n$ 个用空格隔开的整数 $A_i$。

outputFormat: 输出一个整数 $s$。

hint:
#### 样例 1 解释
令 $x=2$，此时 $A_{2,3}$ 满足条件，答案为 $2\times 2=4$。

#### 【数据规模与约定】
- 对于 $30\%$ 的数据，$n<1000$。
- 对于 $100\%$ 的数据，满足 $2\le n\le 2\times 10^5$，$1\le A_i\le 2\times 10^6$。

-----
#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf)  _T5 ORGANIZATOR_。**


title: 「StOI-2」不朽的逃亡者

description:
巴尔博亚要逃遁到不朽的事业——发现太平洋。

现在巴尔博亚在一个矩阵的 $(1,1)$ 位置，太平洋在 $(n,m)$ ， $(i,j)$ 位置的危险值为 $d_i$$_j$ 。他现在抓到了 $k$ 个印第安人，第 $i$ 个人对 $[ax_i,ay_i]  [bx_i,by_i]$ 的**范围**（ 以 $(ax_i,ay_i)$ 为左上角坐标，以 $(bx_i,by_i)$ 为右下角坐标的矩形 ）有了解，如果带上这个人，这一范围不会有危险。

由于时间紧迫，巴尔博亚必须只走 $n+m-1$ 个位置到达太平洋。

现在巴尔博亚希望最多带上的人数不超过 $w$ ，同时使危险值之和最小，求最小值。

inputFormat:
第一行 $4$ 个正整数，$n$ , $m$ , $k$ , $w$ , 含义如题。

接下来是一个 $n$ 行 $m$ 列的矩阵，含义如题。

接下来 $k$ 行，每行 $4$ 个正整数，分别是 $ax_i$ ，$bx_i$ ， $ay_i$ , $by_i$ ，含义如题。

outputFormat: 一个正整数，表示最小值。

hint:
## 样例解释

选择第二人。

路径：`(1,1)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(4,4)`

危险值: 没有受到保护的 `(4,3)`与`(4,4)` ，为 $2+1=3$。

## 数据范围

#### 本题采用捆绑测试。
子任务 $1$（$10$ 分）：$1 \leq n,m,k,w \leq 4$。
子任务 $2$（$20$ 分） : $1 \leq n,m,k,w \leq 20$。
子任务 $3$（$20$ 分）：$1 \leq n,m,k,w \leq 50$。
子任务 $4$（$20$ 分）：所有 $d_{i,j}$ 均相同。
子任务 $5$（$30$ 分） : 无特殊性质。

对于所有数据：$1\leq n,m,k \leq 200$，$1 \leq w \leq 100$，$0 \leq d_{i,j} \leq 10^8$，$1 \leq ax_i \leq bx_i \leq n$ ，$1\leq ay_i \leq by_i \leq m$ 。

注意：输入顺序与题目略有不同


title: [COCI2008-2009#6] BUKA

description: 给定两个位数不超过 $100$，且为 $10$ 的幂次方的整数，你需要计算出他们相乘或者相加后的结果。

inputFormat:
输入共三行。

第一行和第三行分别有一个整数，表示准备计算的数。第二行一个字符，为 `*`（乘）或 `+`（加），表示需要进行哪种运算。数据为 `Windows` 下生成，请注意后缀含有的 `\r`。

outputFormat: 输出一行一个整数，表示运算的结果。

hint:
#### 说明

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T1 BUKA***。


title: [COCI2008-2009#6] BAZEN

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

有一个直角边长为 $250$ 的等腰直角三角形在平面直角坐标系中位于如图所示的位置。你需要画一条线段来把这个三角形的面积分成相等的两部分，且线段的两端点都必须要在三角形的边上。

给出这条线段的起点坐标，请你找出终点应在的坐标。

inputFormat: 输入一行两个整数，表示线段的起点坐标。

outputFormat:
输出一行两个实数，表示线段的终点坐标。

由于答案可能不是整数，所以请四舍五入保留两位小数。**本题使用 SPJ**。

hint:
#### 说明

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T2 BAZEN***。


title: [COCI2008-2009#6] DOSTAVA

description:
在一个 $r\times c$ 的方格矩阵中，一个快递员从公司 $(1,1)$ 出发，要前往 $d$ 个格子送披萨。在临走的时候，他就已经带上了所有的披萨，这样就不会因为来回奔波而浪费时间了。

快递员任何时刻都只能左右移动，但如果他在第 $1$ 或 $c$ 列时，就可以上下运动。每到一个格子，都有在此处要花费的时间。（多次到达多次计入总时间）

为了能更高效，他想知道，这 $d$ 个送餐点共需要花费多长时间？

inputFormat:
输入第一行两个整数 $r,c$，表示矩阵的行和列。

接下来的 $r$ 行，每行 $c$ 个整数，为走到这个格子需要的时长。

接下来一行一个整数 $d$ ，表示总共需要到达的送餐点。

接下来的 $d$ 行，每行两个整数 $a,b$，表示需要送餐到位于第 $a$ 行第 $b$ 列的那一个格子。

虽然快递员要尽量减少用时，但是他**必须按照输入的顺序送餐**，否则会引起顾客的不满。

outputFormat: 输出一行一个整数，表示最少的送餐时间。


title: [COCI2008-2009#6] SLICICE

background: 在一个城市里，有群孩子热衷于收集卡片。

description:
由于他们的零花钱不够，所以想出了一个办法：两人一组，每人出一半的钱，到商店购买两张卡片。紧接着，他们比赛谁先跑到市中心的喷泉，获胜者将得到这两张卡片。如果两人同时到达，那么每人将拿走一张。

有一天，所有的孩子聚集在了一起。他们想统计出所有的购买记录。但是孩子们的记忆有些模糊了，只记得一部分购买记录（且不知道谁得到了多少），并且数出了自己有多少张卡片。你需要编写一个程序，帮助孩子们还原一种可能的购买记录。

inputFormat:
输入第一行两个整数 $n,m$，表示孩子的数量和孩子们记忆中的购买记录。孩子从 $1\sim n$ 编号。

第二行 $n$ 个整数，表示每个孩子所拥有的卡片的数量。

接下来的 $m$ 行，每行两个整数 $a,b$，表示编号分别为 $a,b$ 的两个孩子一起去买了一次卡片。

outputFormat:
输出第一行一个整数 $k$，表示购买总数。

接下来的 $k$ 行，每行三个整数。前两个整数为一次购买中两个孩子的编号。第三个整数为前一个孩子在这次比赛中获得的卡片数（$0/1/2$）。

**题目保证有解。购买的总数最多为 $1000$。如果有多种购买的方案，输出任意一种，本题使用 SPJ。**

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

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

#### 说明

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T6 SLICICE***。


title: [COCI2013-2014#6] VJEKO

background: Vjeko 在业余时间喜欢浏览目录中的文件。

description:
模式串是由英文字母的小写字母和一个星号组成的字符串。

星号可以替换为由小写字母组成的字符串，如果通过替换能使模式字符串等于文件名，则文件名与模式串匹配。

举个例子，字符串 `abcd`，`ad`和`anestonestod` 都与模式 `a*d` 匹配，而字符串 `bcd` 则不匹配。

编写一个程序，该程序将给出一个模式和一些文件名，输出是否与该模式匹配。

inputFormat:
输入的第一行包含整数 $N$，即文件数。

输入的第二行包含一个字符串，该字符串仅由英文字母的小写字母和一个星号组成。

字符串的长度将不超过 $100$，并且星号不会位于字符串的开头或结尾。

接下来的 $N$ 行中的每一行都包含文件名。

文件名仅由英文字母的小写字母组成，且长度不超过  $100$。

outputFormat:
输出共 $N$ 行。

对于每一个文件名，匹配输出 `DA`，反之输出 `NE`。

samples:
6
h*n
huhovdjestvarnomozedocisvastan
honijezakon
atila
je
bio
hun

hint:
#### 【数据规模与约定】
$1\le N\le 100$。

#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #6](https://hsin.hr/coci/archive/2013_2014/contest6_tasks.pdf)  _T1 VJEKO_。**


title: [COCI2013-2014#6] KOCKICE

background: 堆积木！

description:
Mirko 和 Slavko 在玩积木。他们俩都有自己的一堆砖头。一共有 $N$ 列砖头（其中 $N$ 为奇数）。

Mirko 桩的第 $i$ 列中有 $m_i$ 块砖，而 Slavko 每列有 $s_i$ 个。

他们决定创建两堆一样的砖头，这几堆的高度首先是严格下降，然后是严格上升（参见下方右图），相邻列的高度恰好相差 $1$（见图）。最低的列的左右两侧的砖头数量必须相同。

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

允许两种操作：

- 从某一列的顶部移除一块砖。
- 在某一列的顶部加上一块砖。

问在满足上述要求的情况下，最少要几次操作？

inputFormat:
输入的第一行包含一个奇数 $N$，即两个人砖头的堆数。

输入的第二行包含 $N$ 个整数 $m_i$，即 Mirko 堆中的列高。

输入的第三行包含 $N$ 个整数 $s_i$，即 Slavko 堆中的列高。

outputFormat: 输出所需的最少操作次数。

hint:
#### 样例 1 解释
Mirko 在其桩的第一列的顶部放置了两块砖，而 Slavko 在他桩的第三列的顶部放置了一块砖。

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

- 对于 $40\%$ 的数据，满足 $1\le N\le 1000$，$0\le m_i,s_i\le 1000$。
- 对于 $100\%$ 的数据，满足 $1\le N\le 3\times 10^5$，$0\le m_i,s_i\le 10^{12}$。

#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #6](https://hsin.hr/coci/archive/2013_2014/contest6_tasks.pdf)  _T3 KOCKICE_。**


title: [COCI2013-2014#6] HASH

background: Mirko 正在研究一个哈希函数。

description:
此哈希函数如此定义：

- $f(\rm{NULL})=0$
- $f(a_i+s_i)=((f(s_i)\times33)\operatorname{xor}\ \operatorname{ord}(a_i))\bmod MOD$

其中 $a_i$ 代表一个字符，$s_i$ 代表一个字符串，均由小写字母组成。

- $\operatorname{xor}$ 代表按位异或算符。
- $\operatorname{ord(letter)}$ 代表字母中字母的序数（如：$\operatorname{ord(a)=1}$，$\operatorname{ord(z)= 26}$）。

$MOD$ 是 $2^m$ 形式的整数。

当 $m=10$ 时，哈希函数的一些值如下：

- $f(\texttt{a})=1$
- $f(\texttt{aa})=32$
- $f(\texttt{kit})=438$

请问有多少个单词的哈希值为 $k$ 且长度为 $n$？

inputFormat: 输入一行，包含三个整数 $n$，$k$ 和 $m$。

outputFormat: 输出一行，哈希值为 $k$ 且长度为 $n$ 的单词个数。

hint:
#### 【样例解释】
#### 样例 1 解释
字母表中的所有字符的 $\text{ord}$ 值均不为 $0$。
#### 样例 2 解释
单词`b`。
#### 样例 3 解释
词语为`dxl`，`hph`，`lxd` 和 `xpx`。

#### 【数据规模与约定】
$1\le n\le 10$，$0\le k<2^m$，$6\le m\le 25$。

#### 【说明】
**题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #6](https://hsin.hr/coci/archive/2013_2014/contest6_tasks.pdf)  _T5 HASH_。**


title: [COCI2019-2020#5] Matching

description:
给你二维平面上的 $n$ 个整点。保证 $\forall a$，有至多两个形如 $(a,x)$ 的点；$\forall b$，有至多两个形如 $(x,b)$ 的点。

请你用 $n\over 2$ 条线段连接这 $n$ 个点。要求每个点都是一条线段的端点。要求这些线段都是水平的或竖直的。要求这些线段都不相交。

请你求出这是否可能。如果可能，请你输出任意一种方法。

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

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

outputFormat:
如果不可能，请在一行输出 `NE`。

如果可能，请在第一行输出 `DA`。在接下来的 $n\over 2$ 行中各输出两个整数，表示一条线段（整数是端点的编号，从 $1$ 开始）。

hint:
### 数据范围

**本题捆绑测试。**

- 对于 $5 pts$ 的数据：$2\leq n\leq 20$，且 $\forall a$ ，有偶数个形如 $(a,x)$ 的点和偶数个形如 $(x,a)$ 的点。
- 对于另外 $6 pts$ 的数据：$2\leq n\leq 20$。
- 对于另外 $7 pts$ 的数据：$2\leq n\leq 40$。
- 对于另外 $40 pts$ 的数据：$2\leq n\leq 2000$。
- 对于所有的数据：$2\leq n\leq 100000$ 且 $1\leq x_i,y_i\leq 100000$。对于任何整数 $a$ ，有至多 $2$ 个点 $(a,x)$ 和 至多 $2$ 个点 $(x,a)$。

### 说明

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf)  _T3 Matching_** ，译者 [90693](/user/90693)。

spj by [90693](/user/90693)，有任何问题请直接私信或@。


title: [NOI Online #2 提高组] 子序列问题

background: 2s 512M

description:
给定一个长度为 $n$ 的正整数序列 $A_1$, $A_2$, $\cdots$, $A_n$。定义一个函数 $f(l,r)$ 表示：序列中下标在 $[l,r]$ 范围内的子区间中，不同的整数个数。换句话说，$f(l,r)$ 就是集合 $\{A_l,A_{l+1},\cdots,A_r\}$ 的大小，这里的集合是不可重集，即集合中的元素互不相等。

现在，请你求出 $\sum_{l=1}^n\sum_{r=l}^n (f(l,r))^2$。由于答案可能很大，请输出答案对 $10^9 +7$ 取模的结果。

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

第二行 $n$ 个正整数，相邻两个正整数用空格隔开，表示序列 $A_1$, $A_2$, $\cdots$, $A_n$。

outputFormat: 仅一行一个非负整数，表示答案对 $10^9+7$ 取模的结果。

hint:
对于 $10\%$ 的数据，满足 $1 \leq n \leq 10$；

对于 $30\%$ 的数据，满足 $1 \leq n \leq 100$；

对于 $50\%$ 的数据，满足 $1\leq n \leq 10^3$；

对于 $70\%$ 的数据，满足 $1 \leq n \leq 10^5$；

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^6$，集合中每个数的范围是 $[1,10^9]$。


title: [NOI Online #2 提高组] 游戏

background: 1s 512M

description:
小 A 和小 B 正在玩一个游戏：有一棵包含 $n=2m$ 个点的有根树（点从 $1\sim n$ 编号），它的根是 $1$ 号点，初始时两人各拥有 $m$ 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点，若对手的点在自己的点的子树内，则该回合自己获胜；若自己的点在对方的点的子树内，该回合自己失败；其他情况视为平局。游戏共进行 $m$ 回合。

作为旁观者的你只想知道，在他们随机选点的情况下，第一次非平局回合出现时的回合数的期望值。

为了计算这个期望，你决定对于 $k=0,1,2,\cdots,m$，计算出非平局回合数为 $k$ 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 $x$，小 B 在 $x$ 被小 A 选择的那个回合所选择的点不同。

由于情况总数可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

inputFormat:
第一行一个正整偶数 $n$ 表示树的结点数。

第二行一个长度为 $n$ 的 01 字符串，第 $i$ 个字符为 $0$ 表示 $i$ 号点被小 A 拥有，否则被小 B 拥有。保证 $0$、$1$ 的个数相同。

接下来 $n-1$ 行每行两个正整数 $u$, $v$，表示树中的一条边。

outputFormat: 共 $\frac{n}{2}+1$ 行每行一个整数，第 $i$ 行的整数表示 $k=i-1$ 时的答案。


title: [NOI Online #2 提高组] 涂色游戏

background: 1s 256M

description:
你有 $10^{20}$ 个格子，它们从 $0$ 开始编号，初始时所有格子都还未染色，现在你按如下规则对它们染色：

1. 编号是 $p_1$ 倍数的格子（包括 $0$ 号格子，下同）染成红色。
2. 编号是 $p_2$ 倍数的格子染成蓝色。
3. 编号既是 $p_1$ 倍数又是 $p_2$ 倍数的格子，你可以选择染成红色或者蓝色。

其中 $p_1$ 和 $p_2$ 是给定的整数，若格子编号是 $p_1$ 或 $p_2$ 的倍数则它必须要被染色。在忽略掉所有未染色格子后，你不希望存在 $k$ 个连续的格子颜色相同，因为你认为这种染色方案是无聊的。现在给定 $p_1$, $p_2$, $k$，你想知道是否有一种染色方案不是无聊的。

inputFormat:
本题包含多组数据。

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

每组数据一行三个正整数 $p_1$, $p_2$, $k$，变量意义见题目描述。

outputFormat:
对于每组数据，输出一行一个字符串，若存在一种染色方案不是无聊的，则输出 `YES`，否则输出 `NO`。

选手程序输出结果与样例或题面中的一种格式相符即可，即不区分大小写。例如，如果标准答案为 `YES` ，则输出结果 `YES/Yes/yes` 都视为正确。


title: [NOI Online #2 入门组] 建设城市

description:
球球是一位建筑师。一天，他收到市长的任务：建设城市。球球打算建造 $2n$ 座高楼。为了保证城市美观，球球做出了如下计划：

- 球球喜欢整齐的事物。他希望高楼从左向右排成一行，编号依次为 $1\sim 2n$。

- 球球喜欢整数，他要求每座高楼的高度都是正整数。

- 由于材料限制，高楼的高度无法超过 $m$。

- 球球喜欢中间高，两边低的造型。他要求前 $n$ 座高楼的高度不下降，后 $n$ 座高楼的高度不上升。

- 球球打算选两座编号为 $x,y$ 的高楼作为这座城市的地标。他认为只有当这两座高楼高度相等时，才会让城市变得美观。

球球把自己的想法告诉了市长。市长希望得知所有建设城市的方案数。两种方案不同，当且仅当某座高楼的高度在两个方案中不同。这个问题可难倒了球球。球球找到了你，希望你能帮他算出答案。由于答案可能很大，你只需要给出答案对 $998244353$ 取模后的结果。

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

仅一行四个整数 $m,n,x,y$，变量意义见题目描述。

outputFormat:
输出到标准输出。

仅一行一个整数表示答案。


title: [NOI Online #2 入门组] 荆轲刺秦王

background:
本测试数据为脚造，欢迎提供 hack。

第 18 组数据卡了很多人，放于附件中供检查。

description:
时隔数年，刺客荆轲再次来到咸阳宫，试图刺杀嬴政。

咸阳宫的地图可以描述为一个 $n$ 行 $m$ 列的矩形。在这里，我们规定每一行中从左到右为 $x$ 轴正方向，每一列中从下到上为 $y$ 轴正方向，左下角的点坐标为 $(1,1)$。矩形中的点可以分为 $4$ 种：

1. 起点，也就是荆轲的所在点，在地图中用字符 `S` 代表。
2. 终点，也就是嬴政的所在点，在地图中用字符 `T` 代表。
3. 卫兵，在地图中用一个正整数 $a_{i,j}$ 代表。在这里，一个卫兵 $(i,j)$ 可以观察到与他曼哈顿距离小于 $a_{i,j}$ 的点。也就是卫兵 $(i,j)$ 可以观察到所有满足 $|x-i|+|y-j|<a_{i,j}$ 的点 $(x,y)$。
4. 空地，在地图中用字符 `.` 代表。

荆轲的正常移动方式为每秒向八连通的任意方向前进一格。如下图，中间的点为荆轲当前所在点，每一秒，他可以走向其余的八个点。

![img](https://s1.ax1x.com/2020/04/25/Js5XL9.png)

需要注意的是，正常移动时，荆轲不能踏进任何一个有卫兵或者卫兵能观察到的格子。当然，他也不能走出咸阳宫，也就是说，无论何时，荆轲的坐标 $(x,y)$ 都必须满足 $1\le x\le m$ 且 $1\le y\le n$。

荆轲还有两种技能：隐身和瞬移。

1. 隐身：下一秒荆轲进入隐身状态，卫兵观察不到荆轲，荆轲可以进入卫兵的观察范围内，但仍然不能进入卫兵所在的格子。注意这个状态只能维持一秒。
2. 瞬移：荆轲下一秒移动的距离改为 $d$，但这时只能向上下左右四个方向移动。即可以移动到
$(x+d,y)$，$(x-d,y)$，$(x,y+d)$，$(x,y-d)$。
在本题中，两种技能可以同时使用，而且不考虑冷却时间，即一次用完可以立即用下一次，两种技能都分别有使用次数限制，你也可以不用完所有次数。

现在给出咸阳城的地图，请计算荆轲到达秦王所在点所需的最短时间。此外，在所用时间相同情况下，荆轲希望使用的两种技能总次数尽可能少；在所用时间与技能次数相同情况下，荆轲希望使用的隐身次数尽可能少。

inputFormat:
第一行五个整数 $n$, $m$, $c_1$, $c_2$, $d$，代表地图的大小为 $n\times m$，隐身的使用限制次数为 $c_1$，瞬移的使用限制次数为 $c_2$ 和一次瞬移的距离为 $d$。

接下来 $n$ 行，每行 $m$ 个元素。每个元素为字符 `S`、`T`、`.` 或者一个正整数 $a_{i,j}$，代表一个格点，具体含义详见题目描述。

outputFormat:
若荆轲无法到达秦王所在点，则输出一行一个 $-1$。

否则输出一行三个整数 $t$, $u_1$, $u_2$，依次代表所需的最短时间，隐身的使用次数与瞬移的使用次数。

hint:
#### 样例 1 解释

起点为 $(1,2)$，荆轲可以依次走到 $(1,3)$, $(2,4)$, $(3,5)$ 到达终点。

#### 样例 2 解释

起点为 $(2,8)$，荆轲可以依次走到 $(2,5)$, $(2,2)$, $(5,2)$，需要注意的是，即使最后一步到达终点，但因为终点在卫兵的观察范围之内，所以仍然需要隐身进入。

#### 数据范围与提示

对于测试点 $1\sim 6$：$n$, $m\le 10$，$c_1=c_2=0$，保证所需的最短时间不超过 $5$ 或者无解。

对于测试点 $7\sim 10$：$n$, $m\le 20$，$c_1=c_2=0$，保证 `T` 的位置不在任何一个卫兵的观察范围之中。

对于测试点 $11\sim 12$：$n$, $m\le 20$，$c_1=0$

对于测试点 $13\sim 14$：$n$, $m\le 20$，$c_1$, $c_2 \le 5$。

对于测试点 $15\sim 16$：卫兵个数不超过 $350$。

对于所有测试点：$2\le n$, $m\le 350$，$1\le a_{i,j}\le 350$，$0\le c_1$, $c_2\le 15$，$1\le d\le 350$。

保证 `S` 的位置不在任何卫兵的观察范围中。


title: [NOI Online #2 入门组] 未了

description:
由于触犯天神，Sisyphus 将要接受惩罚。

宙斯命 Sisyphus 推一块巨石上长度为 $L$ 的山坡。Sisyphus 匀速向上推的速度为每年 $v$ 的长度（由于是匀速，故经过 $\frac{1}{2}$ 年将能向上推 $\frac{v}{2}$ 的长度）。然而，宙斯并不希望 Sisyphus 太快到达山顶。宙斯可以施展 $n$ 个魔法，若宙斯施展第 $i$ 个魔法 $(1\leq i \leq n)$，则当 Sisyphus 第一次到达位置  $a_i$ 时，他将会同巨石一起滚落下山底，并从头推起。（滚落的时间忽略不计，即可看作第一次到达位置 $a_i$ 后 Sisyphus 立即从山底重新出发）

例如宙斯施用了 $a_i=3$ 和 $a_i=5$ 的两个魔法。Sisyphus 的速度 $v=1$ ，山坡的长度 $L = 6$，则他推石上山过程如下：

- 用 $3$ 年走到位置 $3$。

- 受 $a_i=3$ 的魔法影响，回到了山底出发。

- 再用 $3$ 年走到位置 $3$，然而因为是第二次到达，$a_i=3$ 的魔法不起作用。

- 用 $2$ 年走到位置 $5$。

- 受 $a_i=5$ 的魔法影响，回到了山底出发。

- 用 $6$ 年从山底走到了山顶。花费的总时间为 $14$ 年。

现在，宙斯有 $q$ 个询问。对于第 $i$ 个询问 $t_i$，宙斯想知道，他最少需要施展多少个魔法才能使 Sisyphus 到达山顶所用的年数大于 $t_i$

inputFormat:
第一行三个整数 $n,L,v$ 分别表示魔法的种类数，山坡的长度，Sisyphus 的速度。

第二行 $n$ 个整数。第 $i$ 个整数 $a_i$ 表示第 $i$ 个魔法作用的位置。$(1<i<n)$

第三行一个整数 $q$ 表示宙斯的询问个数。

接下来 $q$ 行每行一个整数，第 $i$ 行的整数 $t_i$ 表示宙斯的第 $i$ 个询问。$(1<i<n)$

outputFormat:
输出 $q$ 行，每行恰好一个整数，第 $i$ 行的整数对应第 $i$ 个询问的答案。$(1 \leq i\leq q)$

如果宙斯无论如何都不能使 Sisyphus 使用的年数大于 $t_i$，请输出 $-1$。

hint:
1. 不使用任何魔法，Sisyphus 需要 $2$ 年走上山顶。
2. 使用魔法 $2$ ，Sisyphus 需要 $\frac{11}{3}$ 年走上山顶。（用时 $\frac{5}{3}$ 年走到魔法 $2$ 的位置并滚落下山，再用时 $\frac{6}{3}=2$ 年走到山顶）
3. 使用魔法 $1,2$ ，Sisyphus 需要 $\frac{14}{3}$ 年走上山顶。
4. 宙斯不能使 Sisyphus 用大于 $5$ 年的时间走上山顶。

对于测试点 $1\sim 8:n=1$。

对于测试点 $9\sim 12:n=2$。

对于测试点 $13\sim 17:n,q\le 1000$。

对于所有测试点：$1 \leq n,q \leq 2 \times 10^5$，$1\leq v\leq L\leq 10^{9}$，$1\leq a_i < L$，$1 \leq t_i\leq 10^9$。

数据保证 $a_i$ 两两不同。


title: [COCI2010-2011#2] NAPOR

description:
Little Mirko 对数学课不在意，所以老师决定在周末让他做一个乏味的作业。

老师给了他一个包含 $n$ 行的文本，仅包含数字和小写字母。 Mirko 必须在文本中找到所有数字，并以不降序的顺序输出。 他还必须省略文本中数字可能包含的任何前导零。

可以通过扫描文本并始终使用可能的最大数来确定这些数，即仅以字母或行首/尾定界。 例如，`01a2b3456cde478` 的最终输出结果是 `1, 2, 478, 3456`。

由于 Mirko 解决问题的速度像蜗牛一样慢，因此他要求您为他编写一个程序以快速解决任务，以便他可以尽快与 Slavko 一起玩。

inputFormat:
第一行一个整数 $n$，表示文本的行数。

接下来 $n$ 行，每行一个字符串。

outputFormat: 每行一个整数，表示文本中的数（从小到大）。

samples:
4
01bond
02james007
03bond
04austinpowers000

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

对于 $100\%$ 的数据，保证 $1 \leq  n \leq 100$，每个字符串长度不超过 $100$，文本中包含数的个数不超过 $500$，输入中仅包含小写字母与数字。

#### 说明

- 本题满分 $60$ 分。
- 题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) NAPOR，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2010-2011#2] PUŽ

description: 蜗牛爬井问题：一只蜗牛要爬上 $v$ 米高的树桩，它每天白天向上爬 $a$ 米，晚上向下掉 $b$ 米。几天之后它可以爬到树桩顶？

inputFormat: 一行三个整数 $a$、$b$、$v$，用空格隔开。

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

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

对于 $100\%$ 的数据，保证 $1 \leq  b < a \leq v \leq 1 \times 10^9$。

#### 说明

- 本题满分 $30$ 分。
- 题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) PUŽ，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。

#### 提示

请推导结果公式，单纯的模拟可能导致 `TLE`。


title: [COCI2010-2011#4] ASTRO

description:
有两颗星星，他们各自每隔一段时间都会闪烁一次。

现在，知道了两个星星第一次闪烁的时间和每颗星星两次闪烁的间隔。你需要求出何日何时两颗星星首次同时闪烁。

**注意：刚开始闪烁的那一天为星期六，`00:00` 为一天的第一分钟。**

inputFormat:
输入共四行。

每行一个形如 `HH:MM` 的时间（小时：分钟），依次表示第一颗星星闪烁的初始时间；第二颗星星闪烁的初始时间；第一颗星星闪烁的时间间隔；第二颗星星闪烁的时间间隔。

保证前两行的时间不同，且均在星期六；时间间隔不会是 `00:00`。

outputFormat:
如果两颗星星永远不会同时闪烁，则输出 `Never`。

否则输出两行，第一行一个字符串，表示第一次同时闪烁是星期几。第二行一个格式与输入相同的时刻，表示这一天的具体同时闪烁为什么时候。

单词的正确拼写：（依次为星期日到星期六）

`Sunday` `Monday` `Tuesday` `Wednesday` `Thursday` `Friday` `Saturday`。

如果 $HH<10$，需要输出前导 $0$。

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

- 对于 $40\%$ 的数据，保证时间间隔为整小时数，即 $MM=0$；例如 `13:00`。
- 对于 $100\%$ 的数据，保证 $0\le HH\le 23$，$0\le MM\le 59$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #4](https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf) *T3 ASTRO***。


title: 不灭「不死鸟之尾」

background:
不死鸟之尾，一种量产型的羽毛。可用作药品。

虽说是量产型，可是从哪里可以得到这种万能之药呢？

description:
有一个包含 $n$ 个停车位的停车场，里面的停车位排成了一排，最左边和最右边都是墙壁。

有 $n$ 辆车要按顺序依次停入这个停车场，在停入第 $i$ 辆车时，这辆车要停入的位置左右两边的空位越多，停进去需要的时间也就会越少，具体地，如果其左边连续的空位数量为 $l$，其右边连续的空位数量为 $r$，那么停入该辆车所需时间为 $W_i-L_i\cdot l-R_i\cdot r$，其中 $W_i,L_i,R_i$ 会给出（特别的，停车所需要的时间不会是负数，所以我们保证 $W_i\ge L_i\cdot n+R_i\cdot n$）。

对于连续空位的解释：例如，下图中箭头所指位置左边连续空位为 $1$，右边连续空位为 $2$。

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

请依次确定每一辆车停入的位置，使得停入所有车所需时间最小。

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

接下来三行，每行 $n$ 个整数：第一行第 $i$ 个数给出 $W_i$，第二行第 $i$ 个数给出 $L_i$，第三行第 $i$ 个数给出 $R_i$。保证 $W_i\ge L_i\cdot n+R_i\cdot n$，$L_i,R_i\ge 0$。

outputFormat: 输出一个数表示所需要的最少时间。

hint:
#### 样例解释 1

第 $1$ 辆车停入从左往右数第 $3$ 个停车位，此时该停车位左边有 $2$ 个连续空位，右边没有连续空位，所需时间 $18-1\times 2-1\times 0=16$。

第 $2$ 辆车停入从左往右数第 $1$ 个停车位，此时该停车位左边没有连续空位，右边有 $1$ 个连续空位，所需时间 $20-2\times 0-4\times 1=16$。

第 $3$ 辆车停入从左往右数第 $2$ 个停车位，此时该停车位左右都没有连续空位，所需时间 $22-3\times 0-3\times 0=22$。

停入所有车需要时间 $16+16+22=54$。

#### 数据范围

对于所有数据，保证 $1\le n\le 10^5$，$0\le L_i,R_i\le 10^5$，$nL_i+nR_i\le W_i\le 2\times 10^{10}$。


title: [COCI2010-2011#4] PROSJEK

description:
你有 $5$ 种数字： $1,2,3,4,5$。

你需要从中选取尽量少的数字，使得这些数之和的平均数为 $P$。

**需要注意的是，这 $5$ 种数字每种有任意多个。**

inputFormat:
输入一行一个实数 $P$。

$P$ 为一个 $1\sim 9$ 位的小数。

outputFormat:
输出一行五个数，分别表示 $1,2,3,4,5$ 取用的数量。

**如果有多种最优的方案，输出任意一种即可。本题使用 SPJ。**

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

对于 $100\%$ 的数据，保证 $1\le P\le 5$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #4](https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf) *T4 PROSJEK***。


title: [COCI2010-2011#4] DUGOVI

description:
在一个小镇上有 $n$ 位居民，每位居民都**恰好从其他一位**居民那里借了一些钱。

现在到了还债的时间。但问题是每个人都把自己的钱用完了；也就是说任何人都无力偿还债务。这样以来产生了很多冲突。

市长决定解决这个问题。他预想要给一部分居民一些钱，以便于他们用来还债。不过当一部分居民拿到了钱，一系列的连锁反应就开始了。

例如， $A$ 从市长那里得到了钱。$A$ 赶忙用这些钱偿还 $B$ 的债务。$B$ 也正好偿还 $C$ 的债务，以此类推。

其中，如果 $B$ 没有足够的钱来一次还清，那么他会把钱暂时留在自己手里等到钱够了；如果还完债后还有剩余， $B$ 也会自己留着。（$B$ 的行为对于任意一个人适用）

另一个例子：如果两个镇上的居民**互欠**对方 $100$ 美元，那么市长只需要给其中一个人 $100$ 美元，这两个债务就都解决了。

你需要通过程序来计算出：市长至少要支出多少元给一部分居民才能平息一切债务？

inputFormat:
输入一行一个整数 $n$，表示镇上居民的数量。

接下来的 $n$ 行，每行两个整数 $A_i,B_i$，表示第 $i$ 个人欠第 $A_i$ 个人 $B_i$ 美元。

居民从 $1\sim n$ 编号。

outputFormat: 输出一行一个整数，表示市长最少支出的金额。

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

对于 $100\%$ 的数据，保证 $2\le n\le 2\times 10^5$，$1\le A_i\le n$ 且 $A_i\neq i$，$1\le B_i\le 10^4$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #4](https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf) *T5 DUGOVI***。


title: [COCI2010-2011#2] IGRA

description:
解决了繁琐的任务后，Mirko 决定与他的好朋友 Slavko 一起玩游戏。

他们在一张纸上写了一个含有 $n$ 个字母的序列。每个人轮流使用序列中的字母拼写一个单词，即从序列中删除单个字母并将其附加到单词的末尾。Mirko 开始了第一回合。当序列中没有剩余字母时，游戏结束。

一个比另一个单词更美丽的单词指这个单词按照字典序排在另一个单词前面。在游戏结束时拥有更美丽单词的玩家将获胜。 如果两个玩家的单词都一样，他们就都输了这一轮。

Mirko 玩得比 Slavko 更好，因此他决定通过始终选择序列中最右边的字母来使 Slavko 玩得更容易一些。 知道了这一点，Slavko 想知道他是否有可能获胜，以及他可能得到的最美丽的单词是什么。

inputFormat:
第一行一个整数 $n$，具体含义请见题目描述。

第二行一个长度为 $n$ 的字符串，表示初始序列。

outputFormat:
第一行一个大写字符串 `NE` 或 `DA`，`DA` 表示 Slavko 可能获胜，`NE` 表示 Slavko 不可能获胜。

第二行一个字符串，表示 Slavko 可能得到的最美丽的单词。

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

- 对于 $50\%$ 的数据，保证 $n = 2\times k(1 \leq k \leq 500)$ 且 $k$ 为整数。
- 对于 $100\%$ 的数据，保证 $n = 2\times k(1 \leq k \leq 10^5)$ 且 $k$ 为整数，所有读入的、输出的第二行的字符均为小写字母。

#### 说明

- 本题满分 $80$ 分。
- 题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) IGRA，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2010-2011#4] HRPA

description:
有 $n$ 枚石子。两位玩家定了如下规则进行游戏：

- Mirko 先取一次，Slavko 再取一次，然后 Mirko 再取一次，两人轮流取石子，以此类推；
- Mirko 在第一次取石子时可以取走任意多个；
- 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
- 取走最后一块石子的玩家获胜。

双方都以最优策略取石子。Mirko 想知道，自己第一次至少要取走几颗石子最终才能够获胜。

inputFormat: 输入一行一个整数 $n$，表示石子的数量。

outputFormat: 输出一行一个整数，表示 Mirko 最少取多少石子可以保证获胜。

hint:
#### 样例 1 解释

对于这个样例，Mirko 第一次可以取 $1/2/3/4$ 个。虽然他取 $4$ 个会直接赢得比赛，但这并不是最少的。最少的方案是取走 $1$ 个。这样 Slavko 只能取走 $1$ 个或者 $2$ 个。无论选择哪种，Mirko 下一步都能取走所有的石子并获胜。

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 10^{15}$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #4](https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf) *T6 HRPA***。


title: [COCI2010-2011#2] KNJIGE

description:
Mirko 有一个由 $n$ 本书组成的家庭图书馆，$n$ 本书在一个狭窄的橱柜中一个接一个地排列。由于在上一任务中对字母进行了很好的训练，他现在希望按字母顺序排列书籍，以使书名字典序排第一的书排在最后，而字典序排最后的书在书橱的底部。

Mirko 可以轻松地将书从书橱中拉出，但是很难将其推回书橱中，因此只能将书放回到书橱的顶部。因此，将书排序籍的唯一可用方法是反复将书籍从书橱中拉出并将其放在书橱的顶部。

这些书按字母顺序用从 $1$ 到 $n$ 的整数标记。因此，Mirko 希望从顶部开始将它们排序为 $(1,2, \cdots ,n)$。例如，如果 $n = 3$ 且开始顺序为 $(3,2,1)$，则两步就足够了。首先，他拉出编号为 $2$ 的书并将其放在最上面，这样书的顺序便变成 $(2,3,1)$。之后，他对编号为 $1$ 的书执行相同操作，因此书的顺序变成 $(1,2,3)$。

计算给定起始顺序，排序完毕所需的最少移动次数。

inputFormat:
第一行一个整数 $n$，具体含义请见题目描述。

接下来 $n$ 行，每行一个正整数，表示书籍的初始摆放顺序。

outputFormat: 一行一个整数，表示使书籍按照自然数顺序排列所需的最小移动步数。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 3 \times 10^5$，书籍的初始摆放顺序为 $1\ldots n$ 的一个排列。

#### 说明

- 本题满分 $80$ 分。

- 题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) KNJIGE，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2010-2011#6] USPON

background: Tomislav 去爬山。

description:
他所走的山路可以看做一个长度为 $n$ 的数字序列 $P_i$，$P_i$ 表示位置 $i$ 的高度为 $P_i$。

从低处往高处走一段**连续的高度严格递增的**山路称为一次爬升。

为了锻炼身体，他想走一段落差尽量大的爬升。

一段山路的落差定义为这段山路的结束点与起始点的差。

你需要求出他走一段山路所能达到最大的落差是多少。

inputFormat:
输入第一行一个整数 $n$，表示山路的长度。

第二行 $n$ 个整数 $P_i$，表示位置 $i$ 的高度为 $P_i$。

outputFormat:
输出一行一个整数，表示最大的落差。

如果整条山路不包含任何的爬升，则输出 `0`。

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

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

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #6](https://hsin.hr/coci/archive/2010_2011/contest6_tasks.pdf) *T2 USPON***。


title: [COCI2010-2011#6] RAZINE

description:
给定一个长度为 $n$ 的序列，你可以将某些各减去一个数，使得整个序列**严格递增**。

你需要求出所有减去的数的总和的最小值。

例如：有一个长度为 $3$ 的序列 $5,5,5$；最优方案是 $5-2,5-1,5$ 即 $3,4,5$。这样所有减去的数的总和是 $2+1=3$，为最小值。

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

第二行 $n$ 个整数，描述这个序列。

outputFormat: 输出一行一个整数，表示总和的最小值。

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

对于 $100\%$ 的数据，保证 $1\le n\le 100$，序列中的数字皆为不大于 $20000$ 的正整数。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #6](https://hsin.hr/coci/archive/2010_2011/contest6_tasks.pdf) *T3 RAZINE***。


title: [COCI2010-2011#6] ABECEDA

description:
人们发现一份字典序未知的单词表。其中共包含 $n$ 个单词。

虽然不知道具体的字典序，但大家已知这些单词在单词表上是按照字典序排列的。

你需要求出这份单词表所依照哪种字典序。

inputFormat:
输入第一行一个整数 $n$，表示单词数。

接下来的 $n$ 行，每行一个字符串，描述一个单词。

outputFormat:
输出一行：

- 如果有唯一的字典序，则按照你求出的字典序依次输出字母；
- 如果答案不存在，则输出 `!`；
- 如果存在多种可能的字典序，则输出 `?`。

hint:
#### 样例 1 解释

根据第一列的字母可知，`a` `k` `u` 这三个字母的字典序是 `u` `k` `a`。再观察第二列可知，`l` 排在 `u` 之前。所以最终的字典序为 `luka`，且是唯一解。

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 100$，所有的单词仅包含小写字母且最多包含 $10$ 个。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #6](https://hsin.hr/coci/archive/2010_2011/contest6_tasks.pdf) *T4 ABECEDA***。


title: [COCI2010-2011#6] VODA

description:
在一个 $r\times s$ 的网格城市里，你承担着水资源运输的设计工作。

具体来说，你需要把水资源从左上角 $(1,1)$ 的上方运输到右下角 $(r,s)$ 的下方，通过铺设水管来实现。

有些格子为 `#`，表示有障碍物，无法铺设水管；其他的格子为 `.`，表示可以铺设水管。每一个为 `.` 的格子都可以铺设如下六种水管之一（也可以不铺设水管）：

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

你需要求出共有多少种可能的设计方案（$\bmod\ 10007$）。使得水资源在运输的过程中不漏出水管且所有铺设在城市中的水管都被使用。

inputFormat:
输入第一行两个整数 $r,c$，表示城市的行数和列数。

接下来的 $r$ 行，每行 $c$ 个字符，其中 `#` 表示无法铺设水管，`.` 表示可以铺设水管。

outputFormat: 输出一行一个整数，表示总方案数（$\bmod\ 10007$）。

hint:
#### 样例 1 解释

对于第一个样例，只有如下图这一种铺设方案：

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

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $2\le r,s\le 10$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #6](https://hsin.hr/coci/archive/2010_2011/contest6_tasks.pdf) *T6 VODA***。


title: [COCI2016-2017#2] Tavan

description:
Željko 正在读奶奶的一封信。由于年代久远，信中的一些单词已经无法辨认。他选出了一个长度为 $n$ 的单词，将其中 $m$ 个无法辨认的字母替换为 `#`。

对于每一处 `#`，奶奶都给出了 $k$ 个字母，该处原先的字母是这 $k$ 个字母之一。所有可能的单词中**按字典序排列**的第 $x$ 个，即为原先的单词。

请你帮助他们找出原先的单词。

inputFormat:
第一行四个整数 $n,m,k,x$。

第二行一个长度为 $n$ 的字符串，表示 Željko 选出的单词。

接下来 $m$ 行，每行一个长度为 $k$ 的字符串，表示奶奶给出的字母。

outputFormat: 一行，一个字符串，表示原先的单词。

hint:
#### 样例 1 解释

所有可能的单词按字典序排列如下：

- `pololjeni`
- `pololjeui`
- `pololjezi`
- `poooljeni`
- `poooljeui`
- `poooljezi`
- `posoljeni`
- `posoljeui`
- `posoljezi`

第 $7$ 个单词为 `posoljeni`。

------------

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 500$，$1\le m\le n$，$1\le k\le 26$，$1\le x\le 10^9$。

所有字符串中仅包含小写字母和 `#`。

------------

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T2 Tavan_**。


title: [COCI2016-2017#2] Nizin

description:
设 $A$ 是一个含有 $n$ 个元素的数组，其中各元素的编号为 $1\dots n$。若对于任意整数 $i\in [1,n]$ 都有 $A_i=A_{n-i+1}$，则称 $A$ 是一个「回文数组」。

Mislav 可以通过以下方式修改一个数组：

1. 选择两个**相邻**的元素。
2. 将这两个元素**替换**为一个新的元素，值为它们的和。

现在，给出一个数组。请你计算在至少多少次修改后，Mislav 可以将其修改为一个「回文数组」。

inputFormat:
第一行一个整数 $n$，表示数组中元素的个数。

接下来一行 $n$ 个整数 $a_i$，表示数组中的元素。

outputFormat: 一行，一个整数，表示 Mislav 至少需要修改数组的次数。


title: [NOI2004] 沙丘

background:
### 特别提示

**在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：**

1. 提交时请在程序开头加入如下函数声明语句：

```cpp
void init();
void look(int&, bool&);
void put_sign();
void take_sign();
void walk(int);
void report(int, int);
```

2. 本题仅支持 C++ 语言（包括 `C++`，`C++11`，`C++14`，`C++17`）提交。

description:
根据新出土的一批史料记载，在塔克拉玛干沙漠中的一座沙丘下面，埋藏着一个神秘的地下迷宫。由著名探险家阿强率领的探险队经过不懈的挖掘，终于发现了通往地下迷宫的入口！队员们兴奋不已，急忙钻下去，去寻找那个埋藏已久的秘密。

他们刚钻进迷宫，只听“轰隆”一声巨响，回头一看，入口已与石墙融为一体，无法辨认。他们意识到自己被困在迷宫里了！环顾周围，似乎是一个洞穴。

这座迷宫由很多洞穴组成，某些洞穴之间有道路连接。每个洞穴都有一盏灯，凭借着微弱的灯光，可以看清有多少条道路与这个洞穴相连。每个洞穴的内部是完全相同的，且无法做标记。每条道路也是完全相同的，也无法做标记。

阿强凭借着微弱的灯光，发现了墙壁上的一段文字（事实上，每个洞穴的墙壁上都有这段文字），翻译成现代汉语就是：“陌生人，请把这个迷宫的洞穴数和道路数告诉我，我就会指引你走出迷宫。”

阿强很快镇定了下来，他拿出一个路标，对队员们说：“这个迷宫的危险程度远超出我们的想象，为了安全起见，大家一定要集体行动。我这儿有一个路标，有了它，我们一定能探明迷宫的结构。大家跟我走！”

现在，轮到你扮演阿强了。路标只有一个，可以随身携带，也可以暂时放在某个洞穴中（把路标放在道路上是毫无意义的，因为那里一片漆黑，什么都看不见）。你的任务很简单：用尽量少的步数探明这个迷宫共有多少个洞穴和多少条道路。“一步”是指从一个洞穴走到另一个相邻的洞穴。

### 交互方法

本题是一道交互式题目，你的程序应当和测试库进行交互，而不得访问任何文件（包括临时文件）。测试库提供了若干函数，它们的用法和作用如下：

- `init` 必须先调用，但只能调用一次，用作初始化测试库；
- `look(d,sign)` 的作用是查看当前洞穴的情况，测试库将从整型变量 $d$ 中返回与该洞穴相连的道路的数目，从布尔变量 `sign` 中返回该洞穴内是否有路标，`sign` 为 `true` 表示有路标，为 `false` 表示无路标。
- `put_sign` 的作用是在当前洞穴放上路标。只有当路标随身携带着的时候，才可以调用这个函数。
- `take_sign` 的作用是把当前洞穴的路标拿走。只有当路标在当前洞穴时，才可以调用这个函数。
- `walk(i)` 的作用是沿着编号为 $i$ 的道路走到相邻的洞穴中。这里的编号是相对于当前所在洞穴而言的，并且是暂时的。假设与某洞穴相连的道路有 $d$ 条，这些道路按照逆时针顺序依次编号为 $0$，$1$，$2$，$\ldots$，$d-1$。走第一步时，编号为 $0$ 的道路由库确定。以后的过程，阿强会将他走进这个洞穴的道路编号为 $0$。
- `report(n,m)` 的作用是向测试库报告结果。$n$ 表示洞穴的数目，$m$ 表示道路的数目。当这个函数被调用后，测试库会自动中止你的程序。

**注意与其他交互题不同的是，您需要直接在 `main()` 函数内实现你的程序。**

在 C/C++ 中，布尔型变量用整型变量代替，$0$ 表示 `false`，$1$ 表示 `true`。

hint:
### 样例解释

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

探险队初始时站在编号为 $1$ 的洞穴内，编号为 $0$ 的道路通向洞穴 $2$，编号为 $1$ 的道路通向洞穴 $3$，编号为 $2$ 的道路通向洞穴 $4$。

一种可能得满分的调用方案如下：

|C/C++ 选手的调用方法|说明|
|:-:|:-:|
|`init();`|初始化程序|
|`look(d, sign);`|返回 $d=3$，$sign=false$|
|`put_sign();`|放下路标|
|`walk(0);`|选择编号为 $0$ 的道路|
|`look(d, sign);`|返回 $d=2$，$sign=false$|
|`walk(1);`|选择编号为 $1$ 的道路|
|`look(d, sign);`|返回 $d=2$，$sign=false$|
|`walk(1);`|选择编号为 $1$ 的道路|
|`look(d, sign);`|返回 $d=3$，$sign=true$|
|`take_sign();`|拿起路标|
|`walk(1);`|选择编号为 $1$ 的道路|
|`look(d, sign);`|返回 $d=2$，$sign=false$|
|`walk(1);`|选择编号为 $1$ 的道路|
|`look(d, sign);`|返回 $d=1$，$sign=false$|
|`report(5, 5);`|返回洞穴数为 $5$，道路数为 $5$|

注意，该例子只是对库函数的使用说明，并没有算法上的意义。

### 约定

- 洞穴数不超过 $100$，道路数不超过 $4000$。
- 迷宫是连通的，即任意两个洞穴都相互可达。
- 两个洞穴之间最多只有一条道路。
- 没有哪条道路连接两个相同的洞穴。

### 评分方法

如果你的程序有下列情况之一，该测试点 $0$ 分：

- 访问了任何文件(包括临时文件)或者自行终止；
- 非法调用库函数；
- 让测试库异常退出。

否则你每个测试点的得分按这样来计算：

如果你所报告的洞穴数与通道数都不正确，得 $0$ 分；如果只有其中一个正确，得 $2$ 分；如果两个都正确，则根据 $walk$ 函数的调用次数评分，公式如下：

$$
your\_score=\left\{
\begin{aligned}
&10&,your\_ans\le our\_ans\\
&5+\left\lfloor\frac{our\_ans}{your\_ans}\times 5+0.5\right\rfloor&,your\_ans>our\_ans
\end{aligned}
\right.
$$

其中 $your\_ans$ 表示你的程序调用 $walk$ 函数的次数，$our\_ans$ 表示我们的程序的结果。

### 如何进行本地测试

- 在工作目录下建立一个文件叫做 `dune.in`，文件的第一行包括一个整数 $n$ 为洞穴的数目，洞穴用1到n的整数编号，以下 $n$ 行描述迷宫的结构。文件的第 $i+1$ 行描述编号为 $i$ 的洞穴的情况，第一个数 $d_i$ 表示与该洞穴相连的道路的数目，其后的 $d_i$ 个数按照逆时针顺序给出了这些道路另一端的洞穴编号。
- 调用 $init$ 函数之后，库将编号为 $1$ 的洞穴作为探险队的起始洞穴，并暂定编号为 $0$ 的道路通向的洞穴编号为文件中第二行的第二个数。比如样例中，初始时，库暂定编号为 $0$ 的道路通向洞穴 $4$。
- 把你的源文件（命名为 `dune.cpp`）和 `dune_lib.hpp` 放在同一目录下，用命令 `g++ -o dune dune_lib.cpp dune.cpp` 来编译你的程序。
- 执行你的程序，此时测试库会产生输出文件 `dune.log`，该文件中包括了你程序和库交互的记录和最后的结果。
- 如果程序正常结束，`dune.log` 的最后一行包含一个整数，为你走的步数。
- 如果程序非法退出，则我们不保证 `dune.log` 中的内容有意义。

样例交互库请在题目附件中下载。


title: [COCI2019-2020#5] Putovanje

description:
给你一棵有 $n$ 个点的树，节点编号从 $1$ 到 $n$。

你会按编号从小到大顺序访问每个节点。

经过树上的边需要收费。第 $i$ 条边有单程票（只能用一次）价格 $c_{i1}$ 和多程票（珂以用无限次）价格 $c_{i2}$。你在访问途中可能会重复走一条边，所以多程票有时更划算。

请你求出从 $1$ 访问到 $n$ 最少需要多少费用。

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

- 接下来的 $n-1$ 行描述 $n-1$ 条边：有 $4$ 个正整数 $a_i,b_i,c_{i1},c_{i2}$，表示有一条连接 $a_i$ 和 $b_i$ 的单程票价格为 $c_{i1}$、多程票价格为 $c_{i2}$ 的边。

outputFormat: 一行一个正整数：你的答案。

hint:
### 样例#1 解释

- $1\to 2$：多程票，费用 $5$。
- $2\to 1\to 3$：$2\to 1$ 使用买过的多程票，无费用；$1\to 3$ 单程票，费用 $2$。
- $3\to 1\to 2\to 4$：$3\to 1$ 单程票，费用 $2$；$1\to 2$ 使用买过的多程票，无费用；$2\to 4$ 单程票，费用 $1$。
- 费用共 $5+2+2+1=10$。

### 数据范围

**本题捆绑测试。**

- 对于 $20 pts$ 的数据，$2\leq n\leq 2000$。

- 对于另外 $25 pts$ 的数据，每个城镇最多与另外两个城镇直接相连。

- 对于所有的数据，$2\leq n\leq 200000$，$1\leq a_i,b_i\leq n$，$1\leq c_{i1}\leq c_{i2}\leq 100000$。

### 说明

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


title: [COCI2016-2017#2]  Prosječni

description:
Slavko 想在一个 $n\times n$ 的矩阵内填入 $n^2$ 个互不相等的正整数，使其满足：

- 每行 $n$ 个数的平均数是该行内的一个整数。
- 每列 $n$ 个数的平均数是该列内的一个整数。
- 对于矩阵中的任意一个元素 $a_{i,j}$，都有 $1\le a_{i,j}\le 10^9$。

请你帮助他找出任意一种可行的方案。

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

outputFormat:
**本题使用 Special Judge**。

若无解，输出 `-1`。

否则，输出 $n$ 行，每行 $n$ 个整数，表示任意一个符合要求的矩阵。

hint:
#### 样例 1 解释

各行的平均数分别为 $2,5,8$，均为相应行内的一个整数。

各列的平均数分别为 $4,5,6$，均为相应列内的一个整数。

------------

#### 数据规模与约定

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

------------

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T4 Prosječni_**。


title: [COCI2016-2017#2] Zamjene

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

description:
Dominik 构造了一个含有 $n$ 个元素的数组 $p_1,p_2,\dots,p_n$，和对其排序得到的数组 $q_1,q_2,\dots,q_n$。

此外，他还定义了「可交换集」。若无序数对 $(a,b)$ 属于「可交换集」，则他可以交换 $p_a,p_b$ 的位置。『通过「可交换集」』，即为**通过若干次这样的交换**。

现有四种操作：

- 操作 $1$：

	格式：`1 a b`。

    交换 $p_a,p_b$ 的位置（不受「可交换集」限制）。

- 操作 $2$：

	格式：`2 a b`。

    将无序数对 $(a,b)$ 加入「可交换集」。

- 操作 $3$：

    格式：`3`。

    判断能否通过「可交换集」完成对数组 $p$ 的排序。

- 操作 $4$：

	格式：`4`。

    若数组 $p$ 中的第 $x$ 个元素能通过「可交换集」移至第 $y$ 位，则称 $x,y$ 是相连的。其中 $x$ 可能等于 $y$。

    将所有与 $x$ 相连的 $y$ 构成的集合称作 $x$ 的「云」。若一朵「云」能通过「可交换集」使得「云」中任意的 $i$ 满足 $p_i=q_i$，则称这朵「云」是「祥云」。

    计算有多少组无序数对 $(a,b)$ 满足：

    - $1\le a,b\le n$ 且 $a\not=b$。
	- $a,b$ 不是相连的。
	- $a$ 的「云」与 $b$ 的「云」均不是「祥云」。
    - 将无序数对 $(a,b)$ 加入「可交换集」后，$a$ 的「云」变为「祥云」。

请你帮助 Dominik 完成这些操作。

inputFormat:
第一行两个整数 $n,q$，表示数组 $p$ 中元素的个数和操作次数。

第二行 $n$ 个整数 $p_i$。

接下来 $q$ 行按以下格式给出：

1. 一个整数 $t$，表示操作的类型。

2. 若 $t$ 为 $1$ 或 $2$，接下来给出两个不同的整数 $a,b$。

outputFormat:
- 对于每一次操作 $3$：

	若能通过「可交换集」完成对数组 $p$ 的排序，输出一行 `DA`。

	否则，输出一行 `NE`。

- 对于每一次操作 $4$：

	输出一行，一个整数，表示满足条件的无序数对 $(a,b)$ 组数。

hint:
#### 样例 1 解释

- 第一次操作：仅有无序数对 $(2,3)$ 满足要求。
- 第二次操作：不能通过「可交换集」完成对数组 $p$ 的排序。
- 第三次操作：将无序数对 $(2,3)$ 加入「可交换集」。
- 第四次操作：不存在满足要求的无序数对。
- 第五次操作：交换 $p_2,p_3$，即可通过「可交换集」完成对数组 $p$ 的排序。

------------

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n,q\le 10^6$，$1\le p_i\le 10^6$，$1\le t\le 4$，$1\le a,b\le n$ 且 $a\not=b$。

------------

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T5 Zamjene_**。


title: 「EZEC-2」甜梦

background:
> 昨是今非望无尽，生死相隔两茫茫。
解愁肠，度思量，人间如梦，倚笑乘风凉。

description:
有 $n$ 个梦境场景，编号 $\in [1,n]$ 且互不相同。PF 有精神分裂症，他在同一时间会处于两个梦境。**这两个梦境所在的场景编号差别的绝对值不能大于 $l$**。场景之间有 $m$ 种**单向**关系，其中第 $i$ 个关系连接场景 $u_i$ 和 $v_i$。不存在不可能到达的场景。

每个场景都有一个快乐值，其中第 $j$ 个场景的快乐值为 $a_j$，在梦境**第一次**经过时增加。

一开始两个梦境均在场景 $1$，当两个梦境都移动到场景 $n$ 时，PF会醒来。

如果某次移动时，PF 目前梦境所在的两个场景 $A,B$ 都与某个场景 $C$ **直接相连**，那么 PF 可以**同时移动** 两个梦境到达场景 $C$ 。否则，PF **一次只能移动一个梦境**。

请你编一个程序，来计算醒来时可能得到的最大快乐值。

inputFormat:
第一行三个整数 $n,m,l$，分别表示场景的数量，场景之间的关系数量，以及 PF 两个场景距离的最大值。

接下来一行 $n$ 个整数，第 $i$ 个数表示编号为 $i$ 的场景的快乐值为 $a_i$，场景 $1$ 和场景 $n$ 的快乐值为 $0$。

接下来 $m$ 行，每行两个整数 $u,v(1\le u<v \le n)$，表示场景之间存在的一条单向关系。

outputFormat:
如果有解，一行一个整数 $q$，表示能获得的最大快乐值。

如果无解，只需输出 `-1`。


title: [COCI2016-2017#2] Burza

description:
Daniel 和 Stjepan 在一棵含有 $n$ 个节点的树上做游戏，树上各节点的编号为 $1,2,\dots,n$。游戏开始时，$1$ 号节点上有一枚硬币。

游戏规则如下：

1. Daniel 选择一个节点，将其标记。
2. Stjepan 标记当前硬币所在的节点。
3. Stjepan 将硬币移至一个**尚未标记**且**与当前所在的节点相邻**的节点。

重复以上操作。当 Stjepan 无法移动硬币时，游戏结束。

Daniel 想知道是否存在某种**既定**的操作策略，使得**无论 Stjepan 如何操作**，都能在 $k$ 轮操作内结束游戏。即 Stjepan 能移动硬币的次数**小于** $k$。

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

接下来 $n-1$ 行，每行两个整数 $a,b$，表示编号为 $a,b$ 的结点间存在一条边。

outputFormat:
若存在满足条件的操作策略，输出一行 `DA`。

否则，输出一行 `NE`。

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

**样例 2 解释**

- 若 Daniel 标记结点 $1$，Stjepan 可以将硬币移至结点 $2$ 或结点 $3$。
- 若 Daniel 标记结点 $2$，Stjepan 可以将硬币移至结点 $3$。
- 若 Daniel 标记结点 $3$，Stjepan 可以将硬币移至结点 $2$。

均不能在 $1$ 轮操作内结束游戏。

即不存在满足条件的操作策略。

**样例 3 解释**

- 第一轮操作，Daniel 标记结点 $2$。
- 第二轮操作，Daniel 标记结点 $6$。

无论 Stjepan 如何操作，都无法第二次移动硬币。

即存在满足条件的操作策略。

------------

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

对于 $100\%$ 的数据，$1\le k\le n\le 400$，$1\le a,b\le n$。

------------

#### 【说明】

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T6 Burza_**。


title: [COCI2010-2011#3] EKIPA

description:
有一支队伍共 $n$ 个人准备参加 $m$ 类比赛。对于每一类比赛，每个人都有对这类比赛知识的积累程度（用一个一位小数表示）。作为教练，你需要派出 $k$ 名选手参赛。

已知一个人最多只能参加一类比赛，多个人可以同时参加同一类比赛，可以有选手不参赛。请你安排 $k$ 名选手参加比赛，使得所有这 $k$ 名选手知识积累程度之和最大。

inputFormat:
输入第一行三个整数 $n,m,k$，分别表示总人数，比赛种类数，实际派出选手数。

接下来的 $m$ 行，描述 $m$ 类比赛。每行 $n$ 个数对 $(i,s)$，表示编号为 $i$ 的选手对这类比赛的知识积累程度为 $s$。按照 $s$ 递减的顺序给出这 $n$ 个数对，每名选手会且仅会出现一次。

outputFormat: 输出一行一个实数，表示最大的知识积累程度总和。保留一位小数。

hint:
#### 样例 1 解释

对于这个样例，我们分别派 $2$ 号选手参加第一类竞赛，$3$ 好选手参加第二类竞赛，这样使得总和最大为 $3.0+1.0=4.0$。

#### 数据规模与约定

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

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #3](https://hsin.hr/coci/archive/2010_2011/contest3_tasks.pdf) *T3 EKIPA***。


title: [COCI2010-2011#3] ZNANSTVENIK

description:
给定一个 $r\times c$ 的字母矩阵。你需要从这个矩阵的第一行开始，删除尽量多的行， 且保证矩阵任意两列都不相等。输出最多可以删除的行数。

- 两列相等定义为在这两列中同一行的字母都相等。
- 初始的矩阵中任意两列都是不相等的。

inputFormat:
输入第一行两个整数 $r,c$。

接下来的 $r$ 行，每行 $c$ 个字母，描述这个字母矩阵。

保证矩阵中的字母皆为小写字母。

outputFormat: 输出一行一个整数，表示最多可以删除的行数。

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

对于 $100\%$ 的数据，保证 $2\le r,c\le 1000$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #3](https://hsin.hr/coci/archive/2010_2011/contest3_tasks.pdf) *T4 ZNANSTVENIK***。


title: [COCI2010-2011#3] DIFERENCIJA

description:
给出一个长度为 $n$ 的序列 $a_i$，求出下列式子的值：

$$\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)$$

即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。

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

接下来的 $n$ 行，每行一个整数 $a_i$，描述这个序列。

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

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

对于 $100\%$ 的数据，保证 $2\le n\le 3\times 10^5$，$1\le a_i\le 10^8$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #3](https://hsin.hr/coci/archive/2010_2011/contest3_tasks.pdf) *T5 DIFERENCIJA***。


title: [COCI2010-2011#3] MONO

description:
给定一个 $r\times c$ 的由小写字母组成的矩阵。每一个方格内有一个字母。其中：

- 左上角的坐标为 $(0,0)$；
- 右上角的坐标为 $(c,0)$；
- 左下角的坐标为 $(0,r)$；
- 右下角的坐标为 $(c,r)$。

**注意这里的坐标是点，而字母放置在方格内。**

给定一个顶点在一些方格的顶点上的多边形，且每条边平行于矩阵的边。请你求出，这个多边形经过上、下、左、右的平移，最多存在多少种情况，使得其内部的字母全部相等？

inputFormat:
输入第一行两个整数 $r,c$，为矩形的长和宽。

接下来的 $r$ 行，每行 $c$ 个字母，描述这个矩阵。

接下来一行一个整数 $V$，为多边形的顶点数。

接下来的 $V$ 行，每行两个整数 $x,y$，表示这个多边形一个顶点的坐标。顶点坐标按顺时针顺序给出。

outputFormat: 输出一行一个整数，表示通过平移可以得到的内部字母全部相等的多边形数量。

samples:
5 4
xyyx
xyyy
xxyy
xxxx
xxxx
8
1 3
1 2
0 2
0 0
2 0
2 1
3 1
3 3

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

- 对于 $40\%$ 的数据，保证 $r,c,V\le 20$；
- 对于 $70\%$ 的数据，保证 $V\le 20$；
- 对于 $100\%$ 的数据，保证 $1\le r,c\le 500$，$4\le v\le 500$，$0\le x\le c$，$0\le y\le r$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #3](https://hsin.hr/coci/archive/2010_2011/contest3_tasks.pdf) *T6 MONO***。


title: [YsOI2020] 义已失吾亦死

background:
> 义已失吾亦死！亦久亦旧罢以龄。

本题添加了 HACK 数据。并且愿意接受更多的 HACK 数据。

description:
Ysuperman 的幼儿园不仅注重文化课、竞赛课的教学，还教授大家德智体美全面发展。这一天是周末，德智体美全面发展的 Ysuperman 爬上了 Y 山。

Ysuperman 爬山并不走行车的大路，而是走旁边的泥土山路。走了很远，他猛然发现回头的路已变得模糊，挡在他面前的是巨大的石壁。他震惊地发现，石壁上竟然写有上个世纪的文字！“义已失吾亦死”他看着这些文字，仿佛有一种特殊的魅力。

回到幼儿园，兴奋的 Ysuperman 立即创造了其他的句子，但他却发现这些句子大部分都失去了魅力。经过两年半的钻研，TA 终于发现，“义已失吾亦死”，对应的其实是 $114514$ 这串数字！研究方向变得更加明确，他决定研究把一个句子映射到一个数字里，一个有魅力的数字满足如下条件：

- 十进制，是自然数；

- 数位(digit)仅仅包含 $1,4,5$ 三种数字；

- 在模一个给定常数 $p$ 意义下为 $0$。

现在 Ysuperman 已经有了很多的数字 $1,4,5$，分别有 $a_1,a_4,a_5$ 个。

Ysuperman 希望组成一个长度为 $n$ 的有魅力的数字，使得它尽可能大。

Ysuperman 知道，如果 TA 还是学生，一定能凭借这次发现入围羟基计划。为了 TA 儿时的梦想，你能帮帮他吗？

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

数据共 $T$ 组。第一行读入 $T$，此后每一组数据：

第一行两个正整数 $n,p$，分别表示 Ysuperman 想组成的有魅力的数字的长度，给定的常数 $p$。

第二行三个自然数 $a_1,a_4,a_5$，表示 Ysuperman 最初拥有的数字个数。

outputFormat:
如果 Ysuperman 无法获得有魅力的数字，输出 `-1`。

否则输出 Ysuperman 能组成的最大有魅力的数字。

两组数据之间需要换行。


title: [COCI2010-2011#2] LUNAPARK

description:
Mirko 对所有书籍都感到了厌倦，因此尽管他不喜欢玩过山车，他还是决定和朋友一起去游乐园。 当他的朋友们度过美好的时光时，Mirko 则坐在长椅上，等待着并思考过山车的可能路线。

游乐园可以用 $r$ 行 $c$ 列的表格来表示。 过山车必须从表格的左上角开始，到表格的右下角结束。 每个单元格最多可以访问一次，但并非所有单元格都需要访问。 它可以继续从当前单元格到其上方，下方，左侧或右侧的相邻单元的路径。

每个单元格都有一个与之相关的正整数值，表示该单元格可以为游客增加的娱乐程度。过山车的总娱乐程度是过山车所访问的所有单元格的娱乐程度的总和。 帮助 Mirko 确定最有趣（总娱乐程度最大）的过山车路线之一。

inputFormat:
第一行两个整数 $r$ 和 $c$，具体含义请见题目描述。

接下来 $r$ 行，每行 $c$ 个整数（用空格隔开），表示相对应的单元格可以为游客增加的娱乐程度。

outputFormat: 一行一个大写字符串，由 `U`、`D`、`L`、`R` 组成（`U` 表示过山车接下来向上走，`D` 表示向下走，`L` 表示向左走，`R` 表示向右走），表示过山车为获得最大娱乐程度应该走的路线。

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

- 对于 $70\%$ 的数据，保证 $2 \leq r,c \leq 30$。
- 对于 $100\%$ 的数据，保证 $2 \leq r,c \leq 1 \times 10^3$，输出字符串的每一位只可能是 `U`、`D`、`L`、`R`。

#### 说明

- 本题满分 $120$ 分。
- 题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) LUNAPARK，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。

#### 鸣谢

感谢 @[Silence_water](https://www.luogu.com.cn/user/338630) 提供的 Special Judge。

#### 提示

输出结果可能不唯一。


title: [COCI2010-2011#2] CRNI

description:
尽管 Mirko 找到了所有最有趣的游乐设施，但他的热情仍然没有消失。 他打开方格纸笔记本，开始给方块上色，一个新的甚至更难的问题浮现在他身上。

您将得到一个 $n \times n$ 的表格。 每个单元格的颜色是黑色或白色。

如果表格内的某一个矩形图形的所有单元格均为黑色并且此矩形由至少两个单元格组成，则此矩形称为黑色矩形。

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

上左图举了两个不是黑色矩形的例子。 标为 $1$ 的矩形不是黑色矩形，因为它包含一个白色单元格；标为 $2$ 的矩形不是黑色矩形，因为它仅包含一个单元格。 上右图则举了三个黑色矩形的例子。

计算选择两个没有公共单元格的黑色矩形的方法数。 由于所求的结果可能非常大，因此您应该输出该数除以 $10^4 + 7$ 后的余数。

inputFormat:
第一行一个整数 $n$，具体含义请见题目描述。

接下来 $n$ 行，每行一个长度为 $n$ 的大写字符串（由 `C`（表示该单元格颜色为黑）和 `B`（表示该单元格颜色为白）两种字符组成），表示表格。

outputFormat: 一行一个整数，表示所求方法数除以 $10^4 + 7$ 后的余数。

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

对于 $100\%$ 的数据，保证 $2 \leq n \leq 1 \times 10^3$，输入字符串的每一位只可能是 `C` 或 `B`，令 $|s|$ 为每个字符串长度，则 $|s| = n$。

#### 说明

- 本题满分 $130$ 分。
- 题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) CRNI，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2006-2007] FIREFLY

background: 一只日本萤火虫飞进了一个充满障碍的山洞。

description:
山洞中有两种障碍物：石笋（从地面向上生长）和钟乳石（从洞顶垂挂下来）。山洞长 $n$ 个单位，高 $h$ 个单位。从左到右第一个障碍物是石笋；紧接着钟乳石与石笋依次交替出现。

下图是一个长 $14$ 个单位，高 $5$ 个单位的山洞示例：

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

这只日本萤火虫并不会绕开障碍物，而只会沿着同一高度飞行。凭借着自己精湛的功夫，他会从山洞的一端，以某一高度撞开所有障碍物而达到另一端。

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

例如在上图中，如果萤火虫选择高度 $4$ 来飞行，那么它总共会撞到 $8$ 个障碍物。

但这并不是最好的选择。因为如果它选择高度 $1$ 或高度 $5$ 飞行的话，只需要撞开 $7$ 个障碍物就行了。

为了减轻疼痛，你需要帮助萤火虫找出最少需要摧毁的障碍的数量和摧毁最少障碍物的高度种类数。

inputFormat:
输入第一行两个整数 $n,h$，表示山洞的长度和高度。数据保证 $n$ 是偶数。

接下来的 $n$ 行，每行一个整数，表示障碍物的长度。保证所有障碍物的长度都小于 $h$。

outputFormat: 输出一行两个整数，分别为最少需要摧毁的障碍物数量和摧毁最少的障碍物有多少种高度的选择。

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

对于 $100\%$ 的数据，保证 $2\le n\le 2\times 10^5$，$2\le h\le 5\times 10^5$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [Regional Competition](https://hsin.hr/coci/archive/2006_2007/regional_tasks.pdf) *T3 FIREFLY***。


title: [CRCI2006-2007] CIRCLE

description:
给定一串环形排列的鹅卵石。这串鹅卵石共有 $n$ 个，每个鹅卵石可能是黑色或者白色。

Mirko 要对这串鹅卵石进行 $k$ 次操作。这串鹅卵石为**初始石串**。一次操作的描述如下：

- 如果相邻的鹅卵石颜色相同，则把它们之间放入一个黑色鹅卵石；

- 如果相邻的鹅卵石颜色不同，则把它们之间再放入一个白色鹅卵石；

- 重复上述步骤 $k$ 次。

- **这里的相邻只计算原有的鹅卵石。后放入的不计。**

- 最终，原来的一串鹅卵石将会增加到 $2\times n$ 个。把**初始石串**拿走，剩下的鹅卵石（也就是后加入的 $n$ 个）即为一次操作后的结果。

给定一个初始石串，经过 $k$ 次操作后会得到一个结果。你需要求出：有多少种不同的初始石串同样可以经过 $k$ 次操作得到同样的结果？

inputFormat:
输入第一行有两个整数 $n,k$。

第二行一行 $n$ 个字符，描述这串石头的颜色。`W` 表示白色，`B` 表示黑色。

outputFormat: 输出一行一个整数，表示不同的初始石串的种类数。（输入的那一种计入答案）

hint:
#### 样例 1 解释

石串 `BBW` 和 `WBW` 在经过 $1$ 次操作后同样得到石串 `BWW`。故有 $2$ 种初始石串。

#### 数据规模与约定

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

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [Regional Competition](https://hsin.hr/coci/archive/2006_2007/regional_tasks.pdf) *T4 CIRCLE***。


title: [CRCI2006-2007] BARD

description:
有一个小村子，村子里共有 $n$ 个人，不妨将这 $n$ 个人从 $1$ 至 $n$ 编号，编号为 $1$ 的人是诗人。

每天晚上都会有一些村民围在篝火旁唱歌。

如果某天晚上诗人来了，那么诗人会编一首所有人都没有听过的新歌曲并教给大家唱。在这天晚上**不会唱其他任何歌曲**。

如果某天晚上诗人没来，那么与会者就会唱他们之中**至少有一个人**会唱的**所有歌曲**，并把这些歌曲教给那些来了但不会唱的人。

给定 $m$ 天晚上参与唱歌的村民的编号，初始时村民们什么都不会唱，诗人一首歌也没有写。请输出最终有多少村民会唱诗人写的所有歌。

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

第二行有一个整数，表示夜晚的数量 $m$。

第 $3$ 到第 $(m + 2)$ 行，每行描述一个夜晚，第 $(i + 2)$ 行描述第 $i$ 个晚上的情况：
该行首先有一个整数 $k_i$，表示该晚上来了 $k_i$ 个村民，然后有 $k_i$ 个互不相同的整数 $a_{i, j}$，分别表示来了的村民的编号。

outputFormat: 输出若干行，每行一个整数，以**升序**输出每一个会所有歌的村民的编号。

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

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

- $ 1 \leq n \leq 100$，$1 \leq m \leq 50$。
- $2 \leq k_i \leq n$，$1 \leq a_{i, j} \leq n$。$1$ 在 $a_{i, j}$ 中至少出现了一次。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [Regional Competition](https://hsin.hr/coci/archive/2006_2007/regional_tasks.pdf) *T1 BARD***，翻译来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: [CRCI2006-2007] TETRIS

description:
有如下七种俄罗斯方块的图形：

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

在使用时可以将它们旋转 $90$，$180$，$270$ 度或不进行旋转。

现在有一个有 $n$ 列，高度不限的方格阵，第 $i$ 列的底部 $a_i$ 行已经有了图形（即最下方 $a_i$ 行在之前已经被放上了方块），每一列只有底部的连续若干行有方块。

下一次要落下的方块是 $m$ 号方块，请求出下落后有多少种布局满足不存在任何一个格子，它本身不被方块占据但是上方的格子被方块占据。也即求出多少种布局满足任何一列只有底部连续若干行有方块。

两种布局不同当且仅当存在一个格子，在其中一种布局中该格子被方块占据，在另一种布局中不被占据。

inputFormat:
第一行有两个整数，分别表示方格阵的行数 $n$ 和下一次下落的方块编号 $m$。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 列的只有底部连续 $a_i$ 行有方块。

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

hint:
#### 样例 1 解释

下面六张图中，左上角的图是方格阵的初始布局，另外五张图是五种情况。

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

#### 数据规模与约定

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

- $1 \leq n \leq 100$，$1 \leq m \leq 7$。
- $0 \leq a_i \leq 100$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [Regional Competition](https://hsin.hr/coci/archive/2006_2007/regional_tasks.pdf) *T2 TETRIS***，翻译来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: [COCI2010-2011#6] STEP

description:
给定一个长度为 $n$ 的字符序列 $a$，初始时序列中全部都是字符 `L`。

有 $q$ 次修改，每次给定一个 $x$，若 $a_x$ 为 `L`，则将 $a_x$ 修改成 `R`，否则将 $a_x$ 修改成 `L`。

对于一个只含字符 `L`，`R` 的字符串 $s$，若其中不存在连续的 `L` 和 `R`，则称 $s$ 满足要求。

每次修改后，请输出当前序列 $a$ 中最长的满足要求的连续子串的长度。

inputFormat:
第一行有两个整数，分别表示序列的长度 $n$ 和修改操作的次数 $q$。

接下来 $q$ 行，每行一个整数，表示本次修改的位置 $x$。

outputFormat: 对于每次修改操作，输出一行一个整数表示修改 $a$ 中最长的满足要求的子串的长度。

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

对于全部的测试点，保证 $1 \leq n, q \leq 2 \times 10^5$，$1 \leq x \leq n$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #6](https://hsin.hr/coci/archive/2010_2011/contest6_tasks.pdf) *T5 STEP***，翻译来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: [COCI2010-2011#6] OKUPLJANJE

description:
一场巨大的派对结束以后，有五家报纸刊登了参加这场派对的人数，然而这些报纸上的数字可能是错误的。

现在你知道整个会场的面积是 $L$ 平方米，并且平均每平方米上有 $p$ 个人。现在请分别求出这五家报纸刊登的参加人数与实际参加人数之差。

inputFormat:
输入的第一行有两个整数，分别表示会场面积 $L$ 和平均每平方米的人数 $p$。

第二行有五个整数 $a_1 \dots a_5$，分别表示五家报纸刊登的人数。

outputFormat: 输出一行五个整数，依次表示每家报纸刊登人数与实际人数之差。

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

对于全部的测试点，保证 $1 \leq L, p \leq 10^9$，$1 \leq a_i \leq 10^{18}$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #6](https://hsin.hr/coci/archive/2010_2011/contest6_tasks.pdf) *T1 OKUPLJANJE***，翻译来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)，数据范围略有修改。


title: 『JROI-1』 蒟蒻火锅的盛宴

background:
点击展开阅读更佳，**题目背景与解题无关。**

----------
传说专门服务神仙们的蒟蒻火锅店前面有一首诗：

灶前无用煮青山，不识神炉自往还。

玉碗琼浆谁乞赐，瑶琴银箭可容攀。

风生夜气通云汉，雨歇秋光上碧湾。

却笑老奴真倦眼，此心空处一团闲。

----
Qiuly 是洛谷著名餐厅“蒟蒻火锅店”的主厨，当中的伙计很多，比如呆呆的 Aw 顿顿，机智的 Cocoly1990 还有珂爱的 45dino。Qiuly 喜欢让顿顿为他准备丰富多样的食材，制作火锅的必需品包括但不限于七星章鱼和芥末鱼子酱，当然，还有各种各样珍稀而奇怪的食材：

- 蒟蒻果冻制成的蒟蒻团子。
- 糯米（雾）制成的糯米青团。
- Aw 顿顿制成的菜鸡糕。
- Bamboo（45dino）。

这些食材难以收集，但是神仙 Qiuly 还是全部弄到手了。接下来她要让顿顿**分类这些食材**。但是顿顿是菜鸡，根本不会分类，他崩溃了。于是他请你，IOI 的 AKer，帮助他分类这些食材，因为这个问题事关 Qiuly 的成绩（IOI 第一名还是第二名），所以你必须尽快。

每一个食材都有各种各样的奇怪特性，根据这些特性，Aw 顿顿咨询了全世界的专家们，评价出了**一个食材的美味程度**，根据这个程度可以**有效的分类食材**。如果你不能**在 $\bf 400$ 毫秒内**给出答案，你就会成为一个食材，光荣的沉没在 Qiuly 精心调制的汤底中。

description:
有 $n$ 个互不相同的整数，现有 $m$ 个整数属于集合 $G$ 中。

Aw顿顿规定这个集合有如下规定：

- 若 $x\in G$，则 $x+a\in G$。
- 若 $x+a$ 不在 $n$ 个整数中就不做处理。
- 若对于一个集合 $G$ 不存在需要加入的元素，那么它是完善的。

若集合是完善的，输出 `Great Set!`，反之输出至少还要按规定加入几个食材才能完善该级别。

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

接下来一行存在 $n$ 个用空格隔开的整数 $A_i$，**互不相同**。

下一行一个正整数 $m$，表示集合 $G$ 当中有 $m$ 个整数，均属于 $n$ 个整数当中。

接下来一行是 $m$ 个用空格隔开的整数。

最后是一个正整数 $a$。

outputFormat:
如果这个集合已经完善，输出 `Great Set!`。

反之输出需要完善该集合所需的整数数量。


title: 「PMOI-2」简单构造题

description:
某次模拟赛中，NaCly\_Fish 遇见这样一道题：
****
定义一个长度为 $n$ 的序列 $A$ 的权值为：

$$\sum_{l=1}^n\sum_{r=l}^n f_A(l,r)$$
其中 $f_A(l,r)$ 就是在 $A$ 的区间 $[l,r]$ 中，「所有**在该区间内出现过的**元素出现次数的乘积」再乘上「区间内所有元素的乘积」。

要求构造一个长为 $n$ 的序列，其中每个元素都是 $[1,m]$ 中的整数，最大化其权值。
****
她并不会，只好均匀随机 $n$ 个 $[1,m]$ 中的整数组成一个数列，然后输出其权值。

当然，她的这份程序一分都没拿到；但她想知道，生成出的序列期望权值是多少。

为了防止精度问题，答案需要对 $998244353$ 取模。

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

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


title: 远大目标

background:
众所周知，一个 OIer 的最远大的目标，就是要 AK IOI。

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

（图片来自[《深入浅出 程序设计竞赛 基础册》](https://class.luogu.com.cn/course/lgbook1)）

做为一名 OIer，小 Z 也想 AK IOI。但他还是太菜了，连说一句 `I AK IOI` 都会遭到大神的鄙视。

所以，小 Z 只好说 `|A|<|O|` 来勉励自己。

但是，Youyou 大佬看到了，很不屑，说：就你这水平还想 AK IOI？算了，你说了 `|A|<|O|`，就给你一道题目做做吧。

可怜的小 Z 实在是太菜了，连这题都不会，所以只好求助于你——未来的 IOI AKer。

description:
给你 $O$，求出满足 $|A|<O$ 且 $A$ 为整数的 $A$ 的个数。

由于小 Z 太菜了，于是连 `|A|<|O|` 都不敢说了，只好来研究这 `|A|<O` 的问题。

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

outputFormat: 一行一个整数，满足条件的整数 $A$ 的个数。

hint:
**样例 1 解释**

$A$ 的取值可以是 $-1, 0$ 和 $1$。

**数据规模和约定**

* Subtask 1（30 分）：$0 \le |O| \le 2^{10}-1$；
* Subtask 2（60 分）：$0 \le |O| \le 2^{31}-1$；
* Subtask 3（10 分）：$0 \le |O| \le 2^{63}-1$。

$|O|$ 表示 $O$ 的绝对值。

**提示**

如果您不了解绝对值是什么，可以理解为：

$$|x| = \begin{cases} x & (x > 0) \\ 0 & (x = 0) \\ -x & (x < 0)\end{cases}$$

原idea: [Meatherm](https://www.luogu.com.cn/user/108949)


title: [COCI2010-2011#3] ZBROJ

description:
老师给了 Perica 两个数 $a, b$，Perica 将他们抄在了笔记本上，并要算出他们的和。

在抄写过程中，Perica 可能会将 $a, b$ 中的数字 $6$ 错抄成数字 $5$，也可能将数字 $5$ 错抄成数字 $6$，当然也可能不抄错。

给定 $a, b$，请求出 Perica 算出的和最小和最大分别是多少。

inputFormat: 输入只有一行两个整数，分别表示 $a$ 和 $b$。

outputFormat: 输出一行两个整数，表示最小可能的和以及最大可能的和。

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

对于全部的测试点，保证 $1 \leq a, b \leq 10^6$。

#### 说明

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #3](https://hsin.hr/coci/archive/2010_2011/contest3_tasks.pdf) *T2 ZBROJ***。


title: Run Away

description:
平面直角坐标系内有一个矩形，左下角坐标为 $(0, 0)$，右上角为 $(w, h)$，边平行于坐标轴。

矩形内有 $n$ 个已知点，第 $i$ 个点坐标为 $(x_i, y_i)$。

请找到矩形内一点，使得这个点到最近的已知点距离最远。输出这个距离的值即可。

inputFormat:
第一行输入三个整数 $w, h, n$。

接下来 $n$ 行，每行输入两个整数 $x_i, y_i$。

outputFormat:
输出一行一个实数，表示最近距离的最大值。

当你的答案与标准输出的绝对误差或相对误差在 $10^{-6}$ 内时，就会被视为正确。

hint:
#### 样例解释 1

所求点坐标为 $(50, 50)$，到已知最近点的距离为 $40 \sqrt{2} \approx 56.568542494923802$。

---

#### 数据范围

- 对于 $50\%$ 的数据，$n \le 50$。
- 对于 $100\%$ 的数据，$1 \le w, h \le 10\ 000$，$3 \le n \le 1000$，$0 \le x_i \le w$，$0 \le y_i \le h$。

输入数据中可能有重点。

---

来源：IOI 2006 国家集训队论文「王栋 —— 浅析平面 voronoi 图的构造及应用」。


title: [CRCI2007-2008] NIKOLA

description:
有一行 $n$ 个格子，编号为 $1\sim n$，Nikola 从 $1$ 号格子出发，想要前往 $n$ 号格子。

他的行程包含若干次跳跃，第一次只能跳到 $2$ 号格子，接下来的跳跃必须满足以下条件：

- 如果他向 $n$ 号格子的方向跳跃，那么每次必须比前一次多跳一个距离的格子；

- 如果他向 $1$ 号格子的方向跳跃，那么每次必须与上一次的跳跃距离完全相同。

例如，在第一次跳跃之后（位于 $2$ 号格），Nikola 可以选择跳到 $4$ 或者 $1$。

每进入一个格子，Nikola 都要支付相应的入场费。第 $i$ 个格子需要付费 $a_i$。他希望在能到达 $n$ 号格的前提下尽可能少的花钱。你需要求出这个最小值。

inputFormat:
输入第一行一个整数 $n$，表示格子的数量。

接下来的 $n$ 行，每行一个整数 $a_i$，依次表示 $1\sim n$ 号格子的入场费。

outputFormat:
输出一行一个整数，表示最小的花费。

**注意：刚开始所在的 $1$ 号格子不计费，但多次经过同一个格子需要计费。**

hint:
#### 样例 1 解释

在第一个样例中，Nikola 的路线为 $1-2-1-3-6$。共花费 $2+1+3+6=12$ 。

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 1000$，$1\le a_i\le 500$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [Regional Competition](https://hsin.hr/coci/archive/2007_2008/regional_tasks.pdf) *T2 NIKOLA***。


title: [CEOI2010 day1] alliances

description:
在一个幻想世界里，有块矩形岛屿。这座岛屿被划分成了 $R$ 行 $C$ 列的方格。

有些方格无人居住，而有些方格被以下某一种生物占据：精灵，人类，矮人或者霍比特人。占据同一格子的生物在这一格子组成了一个村庄。

为了防止恶魔的袭击，他们需要结成联盟。定义**每个村庄相邻四个方向（上下左右）的村庄**为这个村庄的邻居。

每种生物分别要满足以下条件：

- 精灵：只需要与一个邻居结盟；
- 人类：需要与两个邻居结盟，且这两个邻居不能在上下或者左右方向；
- 矮人：需要与三个邻居结盟；
- 霍比特：需要与四个邻居结盟（即所有邻居）。

你的任务是确定岛上的所有村庄是否都能与相应数量的邻居结盟（即可能会出现一些邻居并没有结盟）。如果能，则输出联盟的结构。否则输出 `Impossible!`。

**注意：结盟的关系是双向的。**

inputFormat:
输入第一行两个整数 $r,c$。

接下来的 $r$ 行，每行 $c$ 个 $0\sim 4$ 之间的数字，描述岛屿的人口分布状态。

- 0：此地无村庄；
- 1：此地为精灵村庄；
- 2：此地为人类村庄；
- 3：此地为矮人村庄；
- 4：此地为霍比特村庄。

**可以注意的技巧：输入的数字对应该地所需的联盟数量。**

outputFormat:
如果无法全部结盟则输出 `Impossible!`。

否则，输出以下格式的地图：

每块地都作为一个 $3\times 3$ 的矩阵输出。如果该地无人居住，则输出全部输出为 `.`。如果该地有村庄，则在中心输出一个 `O`。如果这个村庄与一些村庄结盟，那么在 `O` 上下左右四个方格输出 `X` 来表示结盟。

对于每种生物，所有可能的输出格式如下：

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

(elves 表示精灵，humans 表示人类，dwarves 表示矮人，hobbits 表示霍比特人）

**如果有多种方案，输出其中任意一种，本题使用 SPJ。**

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

- 对于 $55\%$ 的数据，保证 $\min(r,c)\le 10$；
- 对于另 $15\%$ 的数据，保证 $r\times c\le 20$；
- 对于另 $10\%$ 的数据，保证地图中只有无人区和人类；
- 对于 $100\%$ 的数据，保证 $1\le r,c\le 70$。

#### 说明

**题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 1 *[T1 alliances](https://people.ksp.sk/~misof/ceoi2010/all-eng.pdf)***。

翻译版权为题目提供者 @[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。


title: [CEOI2010 day1] arithmetic

description:
给定一个 $R\times C$ 的矩阵，有些格子已经填有了数字；而有些格子为空，用 `.` 表示。

你需要找到一种填数的方案，使得每行每列的数字依次排列构成的数列为等差数列。

inputFormat:
输入第一行两个整数 $R,C$，表示矩阵的长和宽。

接下来的 $R$ 行，每行 $C$ 个数字或者字符：`.` 或者一个数字。

outputFormat:
输出共 $R$ 行，每行 $C$ 个整数或者分数，表示完善后的矩阵。

分数的格式为 `N/D` ，其中 $N,D$ 为整数且互质，如果 $D=1$ 则省略。

如果答案不存在，输出 `No solution.`

输出中的所有数都不超过 $20$ 位。

**注意：数据保证输入一定是整数，但输出可能为实数，需要用分数表示。可能有多种方案，输出任意一种即可，本题使用 SPJ。**

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

#### 样例 1 解释

我们可以先把第二行第五列的 $6$ 填入，然后再填写第一行、第二行，最后填写第一列、第四列。

#### 样例 4 提示

输出为多种可能的解决方案中的一种。

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

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

数据共分为以下 $10$ 个子任务，每个子任务 $10$ 分。

|子任务编号|限制|
|:-:|:-:|
|$1$|数字已经全部填好|
|$2$|$R=1$ 或 $C=1$|
|$3$|$R=C=2$|
|$4$|保证方案唯一且可使用样例 $1$ 的解决方法|
|$5$|保证方案唯一且答案中仅包含整数|
|$6$|保证方案唯一|
|$7$|每组数据仅可能有唯一的只包含整数的解决方案或者无解|}
|$8$|每组数据仅有唯一的解决方案或者无解|
|$9$|无特殊限制|
|$10$|无特殊限制|

- 在子任务 $1\sim 9$ 中，保证 $1\le R,C\le 6$。
- 对于全部的测试点，保证 $1 \leq R, C \leq 50$，矩阵中给出的所有数字在 $-100\sim 100$ 之间。

#### 【说明】

**题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 1 *[T2 arithmetic](https://people.ksp.sk/~misof/ceoi2010/ari-eng.pdf)***。

翻译版权为题目提供者 @[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。

SPJ 由 @[一扶苏一](https://www.luogu.com.cn/user/65363) 提供，特别鸣谢。


title: [CEOI2010 day1] bodyguards

description: 在一个矩阵中，需要在一些行和列上安排目标数量的保镖。每个位置可以放置一名保镖。你需要求出能否安排出一种方案，使得一些行、列上恰好有目标数量的保镖？

inputFormat:
输入第一行一个整数 $R$，表示共有 $R$ 条行上的约束。

接下来的 $R$ 行，每行两个整数 $a,b$，表示有 $b$ 行需要恰好包含 $a$ 名保镖。

接下来的一行一个整数 $C$，表示共有 $C$ 条列上的约束。

接下来的 $C$ 行，每行两个整数 $x,y$，表示有 $y$ 列需要恰好包含 $x$ 名保镖。

outputFormat: 输出一行一个数字。如果存在这样的方案，输出 `1`；否则输出 `0`。

hint:
#### 样例 1 解释

有一行需要包含两名保镖，两行需要包含一名保镖；两列需要包含两名保镖，一种方案如下：

```
XX
X.
.X
```

其中 `X` 表示保镖，`.` 表示空位。

#### 样例 2 解释

有两行必须全部是保镖，但是有一列却要仅有一名保镖，无法实现，故无解。

#### 数据规模与约定

- 对于 $50\%$ 的数据，保证 $R,C\le 2000$，最多有 $10^6$ 名保镖；
- 对于 $100\%$ 的数据，保证保镖总数最多为 $10^{18}$，所有数字均为不超过 $10^9$ 的正整数，$1\le R,C\le 2\times 10^5$。

#### 说明

**题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 1 *[T3 bodyguards](https://people.ksp.sk/~misof/ceoi2010/bod-eng.pdf)***。

翻译版权为题目提供者@[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。


title: [CEOI2010 day2] mp3player

description:
有一个 MP3 播放器，这个播放器如果连续 $t$ 秒没有任何操作就会自动休眠。在休眠期间，任何按键都不会起到按键本身的作用，而只会终止休眠。

例如，假设 $t=5$ 且播放器当前处于锁定状态。然后进行如下 $4$ 步操作：

- 按下 `A`，停顿 $3$ 秒；
- 按下 `B`，停顿 $5$ 秒；
- 按下 `C`，停顿 $6$ 秒；
- 按下 `D`。

这些操作过后，实际执行的只有 `B` `C`。注意，在按 `C` 和按 `D` 之间播放器已经休眠了。

这个 MP3 还有两个音量控制键 `+` `-`，分别为将音量调高一个单位或降低一个单位。音量只能为介于 $0\sim V_{\max}$ 之间的整数，即如果音量为 $0$ 时按 `-` 或音量为 $V_{\max}$ 时按 `+`，音量均不发生改变。

刚开始你并不知道 $t$ 的值，便想通过实验来得出。

播放器刚开始是休眠的。你会从某一个音量 $V_1$ 开始，经过 $n$ 次操作得到音量 $V_2$，操作的具体步骤已经给出，每次操作形如 `+/-` $C_i$，表示在距离实验开始 $C_i$ 秒时按下 `+` 或 `-`。

不幸的是，你也不知道 $V_1$ 的值，现在，你需要找出符合实验操作的 $t$ 的最大值，并输出相应的 $V_1$ 。

inputFormat:
输入第一行三个整数 $n,V_{\max},V_2$。

接下来的 $n$ 行，每行为一个字符 $x_i$ 和一个整数 $C_i$（有空格隔开）。$x_i$ 为 `+` 或 `-`，表示调高音量或者降低音量。

$C_i$ 表示距离实验开始 $C_i$ 秒后进行该操作，保证 $C_i$ 在输入中严格递增。

outputFormat:
输出一行两个整数，为 $t,V_1$ 的值。

如果有多种可能的方案，输出 $t$ 的最大的那一组；如果 $t$ 最大时同样有多种方案，输出 $V_1$ 最大的一组。

如果 $t$ 可以任意大，则输出 `infinity`。

请注意，不存在无解的情况。因为有一个方案：$t=0$ 一定存在。在这种情况下所有的按键都无法发挥作用，所以 $V_1=V_2$。

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

#### 样例 1 解释

当 $t=5$ 时，按键的情况为；`解锁,解锁,+,+,解锁,-`。

此时对于 $V_1\in \{2,3,4\}$，可以得到 $V_2=3$。但是要输出最大的 $V_1$。

当 $t\geq 6$ 时，最后两个按键都会发挥正常的作用，也就是连续下调两个音量。此时结果无法为 $V_2=3$，故 $t_{\max}=5$。

#### 样例 2 解释

当 $V_1=10$ 时，任意的 $t$ 都能满足条件。

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

- 对于 $40\%$ 的数据，保证 $n\le 4000$；
- 对于 $70\%$ 的数据，保证 $n\times V_{\max}\le 4\times 10^5$；
- 对于 $100\%$ 的数据，保证 $2\le n\le 10^5$，$2\le V_{\max}\le 5000$，$0<C_i<2\times 10^9$，$0\le V_2\le V_{\max}$，$x_i\in\{\texttt{+}, \texttt{-}
\}$。

#### 【说明】

**题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 2 *[T1 mp3player](https://people.ksp.sk/~misof/ceoi2010/mp3-eng.pdf)***。

翻译版权为题目提供者@[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。


title: [CEOI2010 day2] pin

description: 给定 $n$ 个长度为 $4$ 的字符串，你需要找出有多少对字符串满足**恰好** $D$ 个对应位置的字符不同。

inputFormat:
输入第一行两个整数 $n,D$。

接下来的 $n$ 行，每行一个长度为 $4$ 的字符串。

outputFormat: 输出一行一个整数，表示满足条件的字符串的对数。

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

#### 样例 1 解释

任意两个字符串都有多于一个位置不相同。

#### 样例 2 解释

共有三对字符串：`0000,a010` `a010,a0e2` `0000,0202`。

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

- 对于 $15\%$ 的数据，保证 $n\le 2000$；
- 对于 $30\%$ 的数据，保证 $D=1$；
- 对于 $60\%$ 的数据，保证 $D\le 2$；
- 对于 $75\%$ 的数据，保证字符串中只包含小写字母 $a\sim f$ 以及数字。因此可以视为 $16$ 进制数；
- 对于 $100\%$ 的数据，保证 $2\le n\le 5\times 10^4$，$1\le D\le 4$，所有输入的字符串没有重复，串中的字符仅可能为 $a\sim z$ 或者数字字符。

#### 【说明】

**题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 2 *[T2 pin](https://people.ksp.sk/~misof/ceoi2010/pin-eng.pdf)***。

翻译版权为题目提供者@[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。


title: [CEOI2010 day2] tower

background: 古巴比伦人决定建造一座塔。

description:
这座塔共有 $n$ 层，每层由一个边长为 $a_i$ 的立方体石块构成。一个石块 $i$ 能够直接放在石块 $j$ 上当且仅当 $a_i  \leq a_j+D$，其中 $D$ 为一个给定的常数。

你需要求出如果使用全部的石块，有多少种不同的搭建方案。输出答案 $\bmod\ 10^9+9$ 的结果。

**注意：即使两个石块的边长相同，也看做不同的石块。**

inputFormat:
输入第一行两个整数 $n,D$。

第二行 $n$ 个整数 $a_1,\dots,a_n$，表示每个立方体石块的边长。

outputFormat: 输出一行一个整数，表示方案总数 $\bmod\ 10^9+9$ 的结果。

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

#### 样例 1 解释

首先把边长为 $100$ 的石块放在底部，其余的石块可以任意顺序放置，除了以下两种情况：`2,1,3` `1,3,2`。

#### 样例 2 解释

首先不允许在 $10$ 上面放 $20$。

所以就把 $20$ 一堆放在底下，$10$ 一堆放在上面。

即 $(3!)\times (3!)=36$。

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

- 对于 $10\%$ 的数据，保证 $n\le 10$；
- 对于 $30\%$ 的数据，保证方案数不超过 $10^6$；
- 对于 $45\%$ 的数据，保证 $n\le 20$；
- 对于 $70\%$ 的数据，保证 $n\le 70$；
- 对于 $100\%$ 的数据，保证 $2\le n\le 6.2\times 10^5$，输入中所有数字为不超过 $10^9$ 的正整数。

#### 【说明】

**题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 2 *[T3 tower](https://people.ksp.sk/~misof/ceoi2010/tow-eng.pdf)***。

翻译版权为题目提供者 @[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。


title: [CRCI2007-2008] KUHAR

description:
做某种菜需要 $n$ 种食材，对于第 $i$ 种食材，做一道该菜品需要 $a_i$ 份该食材，目前厨房已经有 $b_i$ 份该食材。对于每种食材都可以去超市再买一些，超市里有**大包**和**小包**两种类型，第 $i$ 种食材的小包每包有 $sm_i$ 份该食材，价格为每包 $pm_i$ 元，大包有 $sv_i$ 份该食材，价格为每包 $pv_i$ 元。对于每种食材，你都可以买任意多包（可以不买）的大包与小包。

你手里有 $m$ 元钱，现在请求出用你手中的钱，最多能做出几道该菜品。

inputFormat:
输入的第一行有两个整数，分别表示食材数 $n$ 和你的钱数 $m$。

第 $2$ 到第 $(n + 1)$ 行，每行六个整数，第 $(i + 1)$ 行的整数分别为 $a_i, b_i, sm_i, pm_i, sv_i, pv_i$，其含义见【题目描述】。

outputFormat: 输出一行一个整数，表示你最多能做出几道该菜品。

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

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

- $1 \leq n \leq 100$，$1 \leq m \leq 10^5$。
- $10 \leq a_i \leq 100$，$1 \leq b_i \leq 100$。
- $1 \leq sm_i \lt sv_i \leq 100$，$1 \leq pm_i \lt pv_i \leq 100$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [Regional Competition](https://hsin.hr/coci/archive/2007_2008/regional_tasks.pdf) *T3 KUHAR***。


title: [CRCI2007-2008] JEDNAKOST

description:
给定一个形如 `A=B` 的字符串，其中 $A$ 和 $B$ 都是不含前导零的正整数。请给 $A$ 的一些相邻数位之间加上加号，要求添加的加号数量最少，使得等式成立。

在 $A$ 加上加号后，每个加数允许有多个前导 $0$。包括 $0$ 在内。也即允许形如 $000 \ldots$ 的数作为加数。

数据保证有解。

inputFormat: 输入只有一行一个形如 `A=B` 字符串，表示给定的等式。

outputFormat:
**本题存在 Special Judge**。

输出一行一个字符串，表示加上加号以后的成立的等式。

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

对于全部的测试点，保证 $1 \leq A \lt 10^{1000}$，$1 \leq B \leq 5 \times 10^3$，$A \neq B$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [Regional Competition](https://hsin.hr/coci/archive/2007_2008/regional_tasks.pdf) *T4 JEDNAKOST***。


title: 奶牛排队

description:
奶牛在熊大妈的带领下排成了一条直队。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 $A$ 是最矮的，最右边的 $B$ 是最高的，且 $B$ 高于 $A$ 奶牛。中间如果存在奶牛，则身高不能和 $A,B$ 奶牛相同。问这样的奶牛最多会有多少头？

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 $0,2$，但不会是 $1$）。

inputFormat:
第一行一个正整数 $N$，表示奶牛的头数。

接下来 $N$ 行，每行一个正整数，从上到下表示从左到右奶牛的身高 $h_i$。

outputFormat: 一行一个整数，表示最多奶牛数。

hint:
#### 样例解释

取第 $1$ 头到第 $4$ 头奶牛，满足条件且为最多。

#### 数据范围

对于全部的数据，满足 $2 \le N \le 10^5$，$1 \le h_i <2^{31}$。


title: [COCI2016-2017#3] Imena

description:
单词是由大写或小写字母组成的字符串。特别的，末尾也可以是标点符号（`.`,`?`,`!`）。名字是 **有且仅有首字母为大写字母** 的单词。

句子是由一些单词组成的字符串，并且最后一个字符是标点符号（`.`,`?`,`!`）
。

给定 $N$ 个句子，Mirko 想让你统计每个句子中分别有多少个名字。

inputFormat:
第一行包含一个正整数 $N$，表示句子的个数。

第二行包含这 $N$ 个句子。这些句子的字符总数不会超过 $10^3$。

outputFormat: 包含 $N$ 行，每行一个正整数。第 $i$ 行表示第 $i$ 个句子的名字总数。

samples:
1
Spavas li Mirno del Potro Juan martine?

samples:
2
An4 voli Milovana. Ana nabra par Banana.

hint:
### 样例解释

#### 样例 2 解释

第一个句子中的名字有 `Milovana`，共 $1$ 个；第二个句子中的名字有 `Ana`,`Banana`，共 $2$ 个。注意第一个句子中，尽管 `An4` 的开头是一个大写字母，但它包含了一个数字，所以不是一个名字。

### 数据规模与约定

对于 $40\%$ 的数据，满足 $N=1$。

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

### 说明
**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T1 Imena_**。


title: [COCI2016-2017#3] Kroničan

description:
Mislav 有 $N$ 个玻璃杯，从 $1\sim N$  编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子），使这些杯子中只有 $K$ 个有水。

已知将第 $i$ 号玻璃杯中的水倒入第 $j$ 号，需要消耗 $C_{i,j}$ 的代价。Mislav 想知道，经过倒水后满足只有 $K$ 个（或更少）玻璃杯中有水时，消耗的代价总和的最小值。

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

接下来 $N$ 行，每行包含 $N$ 个非负整数 $C_{i,j}$。第 $i$ 行 $j$ 列的数表示从玻璃杯 $i$ 倒水到玻璃杯 $j$ 需要付出的代价。保证 $C_{i,i}$ 一定是 $0$。

outputFormat: 输出 Mislav 达成目标需要付出的最小代价和。

hint:
#### 样例 1 解释

Mislav 不需要倒水。代价和是 $0$。

#### 样例 2 解释

Mislav 需要将任意一个玻璃杯中的水倒入任何其他玻璃杯中，使其满足只有两个玻璃杯中有水。代价和为 $1$。

#### 样例 3 解释

Mislav 可以将水从玻璃杯 $4$ 倒入玻璃杯 $3$，然后将玻璃杯 $3$ 中的水倒入玻璃杯 $5$，最后将玻璃杯 $1$ 中的水倒入玻璃杯 $5$。总共付出代价和为 $1+2+2=5$。

### 数据规模与约定

对于 $40\%$ 的数据，满足 $N\le 10$。

对于 $100\%$ 的数据，满足 $1\le K\le N\le 20,C_{i,j}\le10^5$

### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T3 Kroničan_**。


title: [COCI2016-2017#3] Kvalitetni

description:
定义一个算术表达式是有质量的，当且仅当这个算术表达式只由括号，数字，乘法符号和加法符号组成。

一个有质量的算术表达式由下列方式递归定义：

- 仅包含一个正实数**小于等于** $Z_1$。这种表达形式如下：

 $$(x)$$

 例如当 $Z_1=5$，那么 $(4)$ 就是有质量的算术表达式。

- 如果 $A_1,A_2,\cdots,A_k(2\le k\le K)$ 都是有质量的算术表达式，并且这些有质量的算术表达式的和**小于等于** $Z_k$，那么

$$(A_1+A_2+\cdots+A_k)$$

$$(A_1*A_2*\cdots*A_k)$$

也是有质量的算术表达式。

你会得到一条**所有数字都被问号代替**的算术表达式，求满足这个表达式是有质量的算术表达式的前提下，这个表达式可能的最大值。

inputFormat:
第一行包含一个正整数 $K$。

第二行包含 $K$ 个被空格隔开的正整数，表示 $Z_1,Z_2,\cdots,Z_K$。

第三行包含了一个所有数字被 `?` 代替的算术质量表达式。这个表达式只包含 `?`,`+`,`*`,`(`,`)`。

outputFormat:
**本题采用 Special Judge**。

你需要输出这个表达式的最大值。

你的解被接受当且仅当你的输出和标准答案的绝对值 $\le 10^{-3}$。

hint:
#### 样例 1 解释

表达式 $((3)+(3))$ 满足条件，因此它是一个算术表达式。容易证明，$6$ 是这个表达式的最大值。

#### 样例 2 解释

对于表达式 $(((1)+(2))*(2))$ 可以达到最大值。

#### 样例 3 解释

对于表达式 $((2)*(2)*(2))$ 可以得到最大值。

### 数据规模与约定

对于 $100\%$ 的数据，满足 $2\le K\le 50,1\le Z_i\le 50$，表达式的长度 $\le 10^6$。

### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T4 Kvalitetni_**。


title: [COCI2016-2017#3] Zoltan

description:
Marton 的朋友 Cero 有一个由 $N$ 个正整数组成的数组。

首先 Cero 会在黑板上写下这个数组中的第一个数字。接下来他会在之前写下的所有数的左边或者右边写下一个数字。重复以上操作得到一个序列。

请注意，根据上述方法构造出的两个序列相同**当且仅当每一个数字写下的顺序完全相同**。例如，$1,1$ 可能和 $1,1$ 不同，前者的第二个数在第一个数的左边，后者的第二个数在第一个数的右边。

求这些数组成的所有序列中，最长严格递增子序列长度的最大值 $M$，以及所有最长严格递增子序列长度等于 $M$ 的序列中，最长严格递增子序列个数的总和。考虑到答案可能很大，Marton 只想知道这个数对 $10^9+7$ 取模的值。

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

接下来的一行包含 $N$ 个正整数，表示按顺序给出的这个数组的各个元素。

outputFormat: 仅一行，输出这个最长的子序列长度以及总个数模上 $10^9+7$ 的值。

hint:
### 样例解释

#### 样例 1 解释

Cero 可以构造 $2$ 个不同的序列，$1,1$ 和 $1,1$。

显然最长的严格上升子序列长度为 $1$，有 $4$ 个子序列满足。

#### 样例 2 解释

最长的严格上升子序列长度为 $4$，只有 $1,2,3,4$ 满足。

### 数据规模与约定

对于 $30\%$ 的数据，满足 $N\le 20$。

对于 $50\%$ 的数据，满足 $N\le 10^3$。

对于 $100\%$ 的数据，满足 $N\le 2\times10^5$，数组中的每个元素 $\le10^9$。

### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T5 Zoltan_**。

样例 1,2 的解释非官方。


title: [COCI2016-2017#3] Meksikanac

description:
Norman 有一个给定的 $K$ 边形的苍蝇拍。他想知道有多少种放置苍蝇拍的方法，使得这个苍蝇拍的顶点在顶点为 $(0,0)$ 和 $(X_p,Y_p)$ 的矩形中，并且各个顶点是整点，满足没有一个苍蝇被伤害。

其中，整点的定义是横坐标和纵坐标都是整数的点。

这个矩形中有 $N$ 个苍蝇，每一个苍蝇可以看成一个点 $(X,Y)$。一个苍蝇会被伤害，当且仅当这个苍蝇在这个苍蝇拍的顶点，边或内部。

苍蝇拍不能旋转或翻折。

inputFormat:
第一行包含三个正整数 $X_p,Y_p,N$，意义同上。

以下 $N$ 行，每行包含两个正整数 $(X,Y)$，表示第 $i$ 个苍蝇的坐标。

接下来一行有一个正整数 $K$ 表示多边形的点数。

以下 $K$ 行，每行两个正整数 $(X_i,Y_i)$，表示当苍蝇拍的第一个顶点的坐标为 $(X_1,Y_1)$ 的时候，其他顶点的坐标。各个顶点是顺次给出的。

outputFormat: 你需要输出有多少可行的放置苍蝇拍的方案。

hint:
### 样例解释

#### 样例 1 解释

可以放置的苍蝇拍的位置如下：

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

共 $4$ 种。

#### 样例 2 解释

可以放置的苍蝇拍的位置如下：

![](https://cdn.luogu.com.cn/upload/image_hosting/6mcgzh88.png?x-oss-process=image/resize,m_lfit,h_340,w_450)

共 $3$ 种。

#### 样例 3 解释

可以放置的苍蝇拍的位置如下：

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

共 $1$ 种。

### 数据规模与约定

对于 $63\%$ 的数据，满足 $1\le X_p,Y_p\le100$。

对于 $100\%$ 的数据，满足 $1\le X_p,Y_p\le500,1\le N\le X_p\times Y_p,3\le K\le10^4,0<X<X_p,0<Y<Y_p,-10^9\le X_i,Y_i\le10^9$。

### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T6 Meksikanac_**。

样例 1,2 的解释非官方。


title: [COCI2015-2016#1] KARTE

description:
这里有一堆牌，可惜它们似乎不全。

您需要找出每种花色缺失的张数。

如果有相同的扑克牌，请输出 `GRESKA`。

inputFormat:
您要读取的是一个字符串 $s$，每三个字符为一张扑克牌。

对于每一张扑克牌：

- 第一位为花色，用 `P`，`K`，`H`，`T` 表示，且输出也是这个顺序。
- 接下来两位，为这张牌的点数，个位数会在十位补零。

outputFormat:
如果有相同的扑克牌，请输出 `GRESKA`。

否则按  `P`，`K`，`H`，`T` 的顺序，输出该花色缺的牌数。

hint:
#### 【样例解释】
#### 样例 1 解释
有一张花色为 `P` 的牌，一张花色为 `K` 的牌，两张花色为 `H` 的牌。
#### 样例 2 解释
这里有两张 `H02` ，所以输出 `GRESKA`。

#### 【数据范围及限制】
对于 $100\%$ 的数据，保证 $1\le \lvert s\rvert\le 10^3$ 且 $s$ 中仅含有数字与 `P`，`K`，`H`，`T`，每张牌的点数 $\in [1,13]$ 。

#### 【说明】
**本题满分 $50$ 分。**

本题译自 [Croatian Open Competition in Informatics 2015/2016](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T1 KARTE。


title: 灯光效果

background:
  「为了你唱下去——直到荒芜」

  「为了你唱下去——直到……」

  舞台上，享受地阖上眼眸，双手交叠扣在话筒，后脚踮起，在随着节奏闪烁变换的灯光下轻摇……

  嘴角轻扬，绫珍惜着步入瞳孔的每一粒光，那些从天依的发丝、脸颊划过的，带着属于她的旖旎，轰击着明明做好防备的绫的心尖。

  收尾的音调扬起，灯光，也是那样应景呢。

description:
对于舞台效果，灯光是重要的角色。背景屏幕是一个 $n \times n$ 的矩形，行从左到右，列从上到下编号为 $1\sim n$，并用 $(x,y)$ 表示第 $x$ 行第 $y$ 列的灯光单元。

作为御用灯光师的阿绫设计了一个控制背景灯光效果的程序。她设定了两个长度为 $m$ 的**递增**整数序列 $\{x_m\}$ 和 $\{y_m\}$，且满足 $0\le x_1,y_1$，$x_m,y_m\le n$。每次灯光变换，程序会均匀地随机生成两对整数 $(i_1,i_2),(j_1,j_2)$，满足 $1\le i_1<i_2\le m$，$1\le j_1<j_2\le m$，转换满足 $x_{i_1}<r\le x_{i_2}$，$y_{j_1}<c\le y_{j_2}$ 的所有灯光单元 $(r,c)$ 的状态（亮变为熄，熄变为亮）。

表演开始时，所有灯光单元处于熄灭状态；经计算，到表演结束时，一共会发生 $k$ 次灯光变换。而表演落幕时的灯光效果极为关键，所以阿绫想知道，表演落幕时，期望有多少个灯光单元是亮着的？

**由于答案可能是一个小数，为了避免损失精度，请输出答案在 $998244353$ 模意义下的值。**

------------

#### 简化题意

有一个 $n\times n$ 的矩阵，初始所有元素的值为 $0$。给出递增序列 $\{x_m\}$ 和 $\{y_m\}$，其中 $0\le x_1,y_1$，$x_m,y_m\le n$，一次操作定义为：

- 随机选出四个整数 $i_1,i_2,j_1,j_2$，满足 $1\le i_1<i_2\le m$，$1\le j_1<j_2\le m$。
- 把以 $(x_{i_1}+1,y_{j_1}+1)$ 为左上角，$(x_{i_2},y_{j_2})$ 为右下角的子矩阵的每个元素异或 $1$。

求 $k$ 次操作后矩阵内元素之和的期望值。答案对 $998244353$ 取模。

inputFormat:
第一行三个整数，分别为 $n,m,k$ 。

第二行 $m$ 个整数，其中第 $i$ 个数表示 $x_i$ 。

第三行 $m$ 个整数，其中第 $i$ 个数表示 $y_i$ 。

outputFormat: 一行一个整数，表示答案在 $998244353$ 模意义下的值。


title: 皇室战争

description:
训练场可以看作成一个 $n \times m$ 的字符矩阵，每个单元为`S`，`K`或`.`。

`S`为神箭游侠，`K`为骷髅。众所周知，神箭游侠的箭是可以穿透的。（我们把他的箭的射程看作是一条射线，且无限长）。由于骷髅很脆，所以打一下就死。已知骷髅都不会动，问你他最少射几箭才能使所有的骷髅都死亡？

假设所有的人物都站在点上，且无限小。

inputFormat:
第 1 行 2 个数，$n$ 和 $m$。

第 2 至第 $n+1$ 行，每行 $m$ 个字符，代表骷髅`K`，空地`.`和神箭游侠`S`，神箭游侠只会有一个。

outputFormat: 一个数，即最少射的箭数。

hint:
* Subtask 1（15 分）：$1 \le n,m \le 10$；
* Subtask 2（20 分）：$1 \le n,m \le 400$；
* Subtask 3（35 分）：$1 \le n,m \le 10^3$；
* Subtask 4（30 分）：$1 \le n\times m \le 10^6$。

$n,m$ 均为正整数。

样例 $1$ 解释：

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


title: 超超的序列 加强

background:
孙1超总是喜欢疯言疯语，有一天，他随口说出了一串序列，又想对某几个特定位置的值进行修改和求和。由于孙1超十分菜，所以他来找你帮助。

## 请不要抄题解。

description:
给定序列 $a$，并且给出两种操作：
- `1 x y v`：将所有 $a_i$ 的值加上 $v$，其中 $i\equiv y\pmod {2^x}$。
- `2 x y`：询问所有 $a_i$ 的和，其中 $i\equiv y\pmod {2^ x}$。

**本题强制在线。**

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

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

接下来若干行，每行给出若干个整数：

当 $op=1$ 时，$op'$ 的后三个整数依次为该操作的 $x,y,v$；

当 $op=2$ 时，$op'$ 的后两个个整数依次为该操作的 $x,y$。

其中保证没有多余的数输入。

每次操作的 $op=(\operatorname{lastans}+op')\bmod 2+1$。

其中 $\rm lastans$ 表示上一个输出的答案，若之前没有询问，则 $\rm lastans=0$。

outputFormat: 输出每次询问的结果。

hint:
#### 样例解释
对于样例 1：

- 第一个操作 $op=2$，需要计算贡献的 $i$ 为 $1,5$，答案为 $7$。
- 第二个操作 $op=1$， 需要加上 $3$ 的 $i$ 为 $1,3,5$，将 $a_1,a_3,a_5$ 加上 $3$。
- 第三个操作 $op=2$， 需要计算贡献的 $i$ 为 $1,2,3,4,5$，答案为 $25$。

#### 数据范围
- 对于 $10\%$ 的数据，$1\le n,m \leq 10^3$。
- 对于 $70\%$ 的数据，每一个操作后面有一个换行。
- 对于 $100\%$ 的数据，$1\le n,m \leq 2\times10^5$，$0 \leq a_i,y,v,op'<10^7$。
- 对于操作 1 和 2，$0\leq x \leq 20$ 且 $0 \le y < 2^x$。


title: [COCI2015-2016#1]  AKCIJA

description:
书店搞活动了！

现在，您可以一次性购买 $3$ 本书，而三本书中，您只需要付较贵的两本书的钱。

注意，这种优惠在一次性购买 $1$ 或 $2$ 本书时，不存在。

现在，您希望花最少的钱买下 $n$ 本书。

请求出买下 $n$ 本书需花的最少钱数。

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

接下来 $n$ 行，一行一个整数 $c_i$，第 $i$ 行表示第 $i$ 本书的价格。

outputFormat: 仅一行一个整数，表示买下 $n$ 本书需花的最少钱数。

hint:
#### 【样例解释】
#### 样例 1 解释
一起买价格为 $3,2,2$ 的三本书，剩下的一本书单独买即可。
#### 样例 2 解释
一起买价格为 $6,4,5$ 的三本书，而后一起买价格为 $5,5,5$ 的三本书。
#### 【数据范围及限制】
- 对于 $50\%$ 的数据，保证 $n\le 2\times 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le c_i\le 10^5$。

#### 【说明】
**本题满分 $80$ 分。**

本题译自 [Croatian Open Competition in Informatics 2015/2016](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T2 AKCIJA。


title: 「EZEC-2」字母

background: 给你一个 $01$ 矩阵，我们希望你从中找到由连续的 $1$ 组成的「字母 T」。

description:
「字母 T」由一横和一竖组成，竖一定在横的下方（您可以借助英文字母 `T` 辅助理解）。

在本题中，我们定义「横」为组成「字母 T」的水平线段，「竖」为组成「字母 T」的竖直线段。

注意「横」与「竖」的公共部分同时计入横长和竖长。

**合法的「字母 T」的「横」长必须为奇数且「竖」与「横」交于「横」的中点，「横」长最小为 $3$ ，「竖」长最小为 $2$。**

如：

$$
    \begin{array}{ccc}
       0\color{Red}111\color{black}1\\
       00\color{Red}1\color{black}01
    \end{array}
$$

**只含有**一个合法的「字母 T」（即标红部分）。

现在给你一个 $n \times m$ 的 $01$ 矩阵，请你求出在这个矩阵中**合法**的「字母 T」中，一共有多少个**满足以下条件**的「字母 T」。

设某个合法的「字母 T」的「横」长为 $w$，「竖」长为 $h$，有：

- $w\ge a$
- $h\ge b$
- $w\times h \ge s$
- $w+h\ge x$

两个「字母 T」不相同即两个「字母 T」的 **「横」长** 或 **「竖」长** 或 **最左上角的坐标** 不同。

inputFormat:
第一行，两个整数 $n,m$，表示给定的 $01$ 矩阵共有 $n$ 行 $m$ 列。

第二行，四个整数 $a,b,s,x$。

接下来 $n$ 行，每行 $m$ 个数，只可能是 $0$ / $1$，为给定的矩阵。

outputFormat: 输出一个整数，表示有多少个**满足条件且合法**的「字母 T」。


title: [COCI2015-2016#1] BALONI

background: 神箭手射气球！

description:
神箭手要射掉 $n$ 个气球，且每个气球有高度，设为 $h_i$。

箭会因为气球的弹性而下坠，当射中一个气球后箭的高度会下降 $1$。

神箭手可以射任意高度的箭。

求出神箭手最少需射几箭。

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

接下来一行 $n$ 个整数 $h_i$。

outputFormat: 仅一行一个整数，表示神箭手最少需射几箭。

hint:
#### 样例 1 解释
先射击高度为 $5$ 的气球，再射击高度为 $2$ 的气球。
#### 数据范围及限制
- 对于 $40\%$ 的数据，保证 $n\le 5\times 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le n,h_i\le 10^6$。
#### 说明
**本题满分 $100$ 分。**

本题译自 [Croatian Open Competition in Informatics 2015/2016](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T3 BALONI。


title: [COCI2015-2016#1] TOPOVI

description:
这里有一个 $n\times n$ 的棋盘，棋盘上有 $k$ 个棋子，每个棋子有一个武力值 $w_i$。

我们做出如下规定：
- 一个棋子的攻击范围是它所在的这一行与这一列，不包括它自己。
- 一个棋盘上的单元格可以被攻击，当且仅当能攻击到它的所有棋子的武力值的异或和大于 $0$。

现在我们会进行 $p$ 次操作，请求出每次操作后会被攻击到的格子总数。

inputFormat:
第一行三个整数 $n,k,p$。

接下来 $k$ 行，一行三个整数 $x_i,y_i,w_i$，第 $i$ 行表示有一个棋子在 $(x_i,y_i)$ 的位置，武力值为 $w_i$。

接下来 $p$ 行，一行四个整数 $r_1,c_1,r_2,c_2$，表示将位于 $(r_1,c_1)$ 的棋子移至 $(r_2,c_2)$。

outputFormat: 共 $p$ 行，一行一个整数，第 $i$ 行表示第 $i$ 次操作后会被攻击到的格子总数。

hint:
#### 数据范围及限制
- 对于 $25\%$ 的数据，保证 $n,k\le 100$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 10^9$，$1\le k\le 10^5$，$1\le p\le 10^5$，$1\le x_i,y_i,r_1,c_1,r_2,c_2\le n$，$1\le w_i\le 10^9$，在移动过程中棋子不会重叠。

#### 说明
**本题满分 $120$ 分。**

本题译自 [Croatian Open Competition in Informatics 2015/2016](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T4 TOPOVI。


title: [COCI2015-2016#1] RELATIVNOST

description:
您是一位计数大师，有一天您的朋友 Luka 出了一道问题来刁难您。

Luka 是一位勤劳的画家，他的画很好，所以会有 $n$ 个人来买他的画。

画分两种，黑白画与彩色画。

Luka 十分勤劳，所以他有无穷多的画。

Luka 讨厌出售黑白画，所以他希望至少有 $c$ 个人会买走一张彩色画。

第 $i$ 个人会至多购买 $a_i$ 张彩色画，$b_i$ 张黑白画，且它们会至少购买一幅画。

但是，客户们只能单独购买彩色画或黑白画。

客户们会不断改变 $a_i$ 与 $b_i$，这种改变会持续 $q$ 次。

客户以 $1\sim n$ 编号。

您需要求出在每次改变之后，Luka 会有几种方案满足所有需求。

为了防止输出太大，Luka 只需要您告诉他方案数 $\bmod\ 10^4+7$ 的值。

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

第二行为 $n$ 个整数 $a_i$。

第三行为 $n$ 个整数 $b_i$。

第四行为一个整数 $q$。

接下来 $q$ 行，一行三个整数 $p_i,a_{p_i},b_{p_i}$，第 $i$ 行表示标号 $p_i$ 的顾客将 $a_i$ 和 $b_i$ 更换成 $a_{p_i}$ 和 $b_{p_i}$。

outputFormat: 共 $q$ 行，一行一个整数，第 $i$ 行的值表示进行了第 $i$ 次改变后，满足条件的方案数 $\bmod\ 10^4+7$ 的值。

hint:
#### 样例 1 说明
第一次改变后，我们只有唯一的一种方案，就是向两位用户都出售一张彩色画。

#### 数据范围及限制
- 对于 $30\%$ 的数据，保证 $n,q\le 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le n,q\le 10^5$，$1\le c\le 20$，$1\le a_i,b_i,a_{p_i},b_{p_i}\le 10^9$，$1\le p_i\le n$。

#### 说明
**本题满分 $140$ 分。**

本题译自 [Croatian Open Competition in Informatics 2015/2016](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T5 RELATIVNOST。


title: [COCI2015-2016#1] UZASTOPNI

description:
这里有一棵有 $n$ 个点的树，每一个树上的节点有一个权值，即为 $v_i$，以 $1$ 为根，点以 $1\sim n$ 编号。

现在，我们想从选出一些点，并满足以下条件：

1. 一个点的父亲点若未被选择则其不能被选择。
1. 所选点的集合内不能有相同的权值。
1. 对于每一个选择的点，其子树中所有被选择点的权值必须可以构成公差为 $1$ 的等差数列。

您只需要输出满足上述条件的方案个数。

**注意：这里的方案指所选的数的集合不同的方案。**

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

接下来一行 $n$ 个整数 $v_i$。

接下来 $n-1$ 行，一行两个整数 $a_i,b_i$，第 $i$ 行描述树上有一条以 $a_i$ 为父亲，$b_i$ 为儿子的边。

outputFormat: 仅一行一个整数，表示满足上述条件的方案个数。

hint:
#### 【样例解释】
#### 样例 1 解释
如下为选点的权值的六种情况：

$\{2\},\{2,3\},\{2,3,4\},\{1,2,3,4\},\{1,2\},\{1,2,3\}$。

#### 样例 2 解释
如下为选点的权值的三种情况：

$\{3\},\{3,4\},\{3,4,5\}$。

注意到不能选权值为 $6$ 的点，因为其父亲点与其构成的子树 $\{4,6\}$ 不符条件。
#### 【数据范围及限制】
- 对于 $50\%$ 的数据，保证 $n\le 100$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 10^4$，$1\le v_i\le 100$，$1\le a_i,b_i\le n$。
#### 【说明】
**本题满分 $160$ 分。**

本题译自 [Croatian Open Competition in Informatics 2015/2016](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T6 UZASTOPNI。


title: [COCI2019-2020#5] Zapina

description:
有 $n$ 个**不同的**人和 $n$ 道**不同的**题。

第 $i$ 个人开心当且仅当他被分配到 $i$ 道题。

求让至少一个人开心的分配方案数。

inputFormat: 一个正整数：$n$。

outputFormat: 一个数字：你的答案$\bmod 10^9+7$。

hint:
### 数据范围

**本题捆绑测试。**

- 对于 $22 pts$ 的数据，$2\leq n\leq 7$。
- 对于另外 $33 pts$ 的数据，$1\leq n\leq 20$。
- 对于所有的数据，$1\leq n\leq 350$。

### 样例#2解释

有以下 $3$ 种方案：

- 第一题給第一个人，第二题給第二个人。

- 第二题給第一个人，第一题給第二个人。

- 两题都给第二个人。

### 说明

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf)  _T5 Zapina_** ，译者 [90693](/user/90693)。


title: 「EZEC-2」异或

description:
有 $T$ 组询问，每次给定两个正整数 $n,l$，

你需要构造一个长度为 $l$ 的正整数序列 $a$（编号从 $1$ 至 $l$），

且满足 $\forall i\in[1,l]$，都有 $a_i\in[1,n]$。

求：

$$\sum_{i=1}^l\sum_{j=1}^{i-1}a_i\oplus a_j$$

的最大值。

为了避免答案过大，对于每组询问，只需要输出这个最大值对 $10^9+7$ 取模的结果。

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

接下来第 $2$ 行到第 $T+1$ 行，每行两个整数 $n,l$ ，分别代表 $a_i$ 的最大取值与 $a$ 的长度。

outputFormat: 共 $T$ 行，每行一个整数，对应每组询问的答案对 $10^9+7$ 取模的结果。


title: [WC2018] 即时战略

background:
### 特别提示

**在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：**

1. 提交时请在程序里加入以下函数声明语句：

```cpp
int explore(int,int);
```

2. 程序开头不用，也不应该包含 `rts.h` 头文件。
3. 仅支持 `C++`（含 `C++`，`C++11`，`C++14`，`C++17`）提交。

description:
小 M 在玩一个即时战略 (Real Time Strategy) 游戏。不同于大多数同类游戏，这个游戏的地图是树形的。也就是说，地图可以用一个由 $n$ 个结点，$n - 1$ 条边构成的连通图来表示。这些结点被编号为 $1 \sim n$。

每个结点有两种可能的状态：「已知的」或「未知的」。游戏开始时，只有 $1$ 号结点是已知的。
在游戏的过程中，小 M 可以尝试探索更多的结点。具体来说，小 M 每次操作时需要选择一个已知的结点 $x$，和一个不同于 $x$ 的任意结点 $y$（结点 $y$ 可以是未知的）。然后游戏的自动寻路系统会给出 $x$ 到 $y$ 的最短路径上的第二个结点 $z$，也就是从 $x$ 走到 $y$ 的最短路径上与 $x$ 相邻的结点。此时，如果结点 $z$ 是未知的，小 M 会将它标记为已知的。

这个游戏的目标是：利用至多 $T$ 次探索操作，让所有结点的状态都成为已知的。然而小 M 还是这个游戏的新手，她希望得到你的帮助。

**为了让游戏过程更加容易，小 M 给你提供了这个游戏的交互库，具体见「任务描述」和「实现细节」。**
**另外，小 M 也提供了一些游戏的提示，具体见题目的最后一节「提示」。**

### 任务介绍
你需要实现一个函数 `play`，以帮助小 M 完成游戏的目标。

* `play(n, T, dataType)`
	* `n` 为树的结点个数；
	* `T` 为探索操作的次数限制；
	* `dataType` 为该测试点的数据类型，具体见「数据规模和约定」。

在每个测试点中，交互库都会调用恰好一次 `play` 函数。该函数被调用之前，游戏处于刚开始的状态。

你可以调用函数 `explore` 来帮助你在游戏中探索更多结点，但是这个函数的调用次数不能超过 $T$ 次。

* `explore(x, y)`
	* `x` 为一个已知的结点；
	* `y` 为一个不同于 $x$ 的任意结点（可以不是已知的结点）；
	* 这个函数会返回结点 $x$ 到 $y$ 的最短路径上的第二个结点的编号。

在函数 `play` 返回之后，交互库会检查游戏的状态：只有当每个结点都是已知的，才算游戏的目标完成。

### 实现方法
你需要且只能提交一个源文件 `rts.cpp/c/pas` 实现上述函数，且遵循下面的命名和接口。

**对 C/C++ 语言的选手：**

源代码中需要包含头文件 `rts.h`（**请注意在洛谷提交时不用包含该头文件**）。

你需要实现的函数 `play`：
```
void play(int n, int T, int dataType);
```

函数 `explore` 的接口信息如下：
```
int explore(int x, int y);
```

**对 Pascal 语言的选手：**

你需要使用单元 `graderhelperlib`。

你需要实现的函数 `play`：
```
procedure play(n, T, dataType : longint);
```

函数 `explore` 的接口信息如下：
```
function explore(x, y : longint) : longint;
```

inputFormat:
第一行包含三个整数 $n$, $T$, $\texttt{dataType}$，需要保证 $2 \leqslant n \leqslant 3 \times 10^5, $ $1 \leqslant T \leqslant 5 \times 10^6,$ $\texttt{dataType} = 1$ 或 $2$ 或 $3$。

接下来 $n - 1$ 行，每行两个整数 $u$, $v$，需要保证 $1 \leqslant u, v \leqslant n$ 且 $u \ne v$，表示一条 $u$ 和 $v$ 之间的边。

你的输入需要保证这 $n - 1$ 条边构成一棵树。

outputFormat: 交互库会判断游戏目标是否完成。如果完成，则会输出 $\texttt{Correct}$，否则会输出相应的错误信息。

hint:
### 样例解释

这是使用试题目录的 grader 和正确的源程序得到的输出文件。

对于此样例，一种可能的 `explore` 函数的调用顺序为：

* `explore(1, 2)`，返回 3
* `explore(3, 2)`，返回 2
* `explore(2, 4)`，返回 3
* `explore(3, 4)`，返回 4

### 如何测试你的程序

**对 C/C++ 语言的选手：**

你需要在本题目录下使用如下命令编译得到可执行程序：

`g++ grader.cpp rts.cpp -o rts -O2`

可执行文件将从**标准输入**读入数据。

读入完成之后，交互库将调用 `play` 函数。如果此时你调用 `explore` 的次数超过 $T$ 次，则交互库会输出详细的错误信息，并退出。

接下来交互库会判断游戏目标是否完成。如果完成，则会输出 "$\texttt{Correct}$"，否则会输出相应的错误信息。

如果传入 `explore` 函数的参数非法（$x,y$ 不在 $1$ 到 $n$ 的范围内，或 $x$ 不是已知结点，或 $x=y$），那么交互库会输出详细的错误信息，并退出。

如果要使用自己的输入文件进行测试，请保证输入文件符合以上格式要求，否则不保证程序能正确运行。

### 如何使用样例源代码

本题目录下，有针对每种语言的样例源代码 `rts_sample.cpp/c/pas`。选择你所需的语言，将其复制为 `rts.cpp/c/pas`，按照上文中提到的方式进行编译，即能通过编译得到可执行程序。

对于非正式选手，你只能选择一种语言进行作答，即你本题的试题目录下不能同时存在多个语言的 `rts.cpp/c/pas`，否则系统将任选一份源代码进行评测并作为最终结果。

接下来你需要修改这个文件的实现，以达到题目的要求。

### 子任务

一共有 20 个测试点，每个测试点 5 分。

对于所有测试点，以及对于所有样例，$2 \leqslant n \leqslant 3 \times 10^5, $ $1 \leqslant T \leqslant 5 \times 10^6,$ $\texttt{dataType} = 1$ 或 $2$ 或 $3$。
不同 $\texttt{dataType}$ 对应的数据类型如下：

* 对于 $\texttt{dataType} = 1$ 的测试点，没有特殊限制。
* 对于 $\texttt{dataType} = 2$ 的测试点，游戏的地图是一棵以结点 $1$ 为根的完全二叉树，
即，存在一个 $1$ ~ $n$ 的排列 $a$，满足 $a_1 = 1$，且结点 $a_i ~ (1 < i \leqslant n)$ 与结点 $a_{\lfloor i/2 \rfloor}$ 之间有一条边相连。
* 对于 $\texttt{dataType} = 3$ 的测试点，游戏的地图是一条链，
即，存在一个 $1$ ~ $n$ 的排列 $a$，满足结点 $a_i ~ (1 < i \leqslant n)$ 与结点 $a_{i-1}$ 之间有一条边相连。

对于每个测试点，$n, T, \texttt{dataType}$ 的取值如下表：

| 测试点编号 | $n =$ | $T =$ | $\texttt{dataType} =$ |
|-|-|-|-|
| 1 | $2$ | $10000$ | 1 |
| 2 | $3$ | $10000$ | 1 |
| 3 | $10$ | $10000$ | 1 |
| 4 | $100$ | $10000$ | 1 |
| 5 | $1000$ | $10000$ | 2 |
| 6 | $20000$ | $300000$ | 2 |
| 7 | $250000$ | $5000000$ | 2 |
| 8 | $1000$ | $20000$ | 3 |
| 9 | $5000$ | $15500$ | 3 |
| 10 | $30000$ | $63000$ | 3 |
| 11 | $150000$ | $165000$ | 3 |
| 12 | $250000$ | $250100$ | 3 |
| 13 | $300000$ | $300020$ | 3 |
| 14 | $1000$ | $50000$ | 1 |
| 15 | $5000$ | $200000$ | 1 |
| 16 | $30000$ | $900000$ | 1 |
| 17 | $150000$ | $3750000$ | 1 |
| 18 | $200000$ | $4400000$ | 1 |
| 19 | $250000$ | $5000000$ | 1 |
| 20 | $300000$ | $5000000$ | 1 |

### 提示

这里是小 M 给你的一些贴心的提示：

* 图（无向图）由结点和边构成，边是结点的无序对，用来描述结点之间的相互关系；
* 路径是一个结点的非空序列，使得序列中相邻两个结点之间都有边相连；
* 两个结点是连通的，当且仅当存在一条以其中一个结点开始、另一个结点结束的路径；
* 一个图是连通的，当且仅当这个图上的每对结点都是连通的；
* 一棵 $n$ 个结点的树，是一个由 $n$ 个结点，$n - 1$ 条边构成的连通图；
* 两个结点的最短路径，是指连接两个结点的所有可能的路径中，序列长度最小的；
* 在一棵树中，连接任意两个结点的最短路径，都是唯一的；
* 通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。


title: 中子衰变

background:
这是一道**交互题**。

可能会用到的前置知识：

质子带一个单位的正电荷。

电子带一个单位的负电荷。

中子不带电。

description:
Youyou 和小 Z 面前有 $n$ 个中子，从左往右排成一行，这些中子被强作用力固定在编号为 $1 \sim n$ 的位置上。

小 Z 拥有一台弱作用衰变机 Wadm（Weak Action Decay Machine）。Wadm 每次可以使一个中子发生弱作用衰变，放出一个电子和一个质子（本题中不考虑中微子），然后 Wadm 会根据 Youyou 或小 Z 的指令，留下其中一个粒子，然后将另一个粒子移出体系。

简而言之，Wadm 可以将一个中子变为一个电子或一个质子。

现在小 Z 想和 Youyou 玩一个游戏：两个人轮流使用 Wadm 操作一个中子，将其变为一个电子或一个质子。然而，如果一个电子和质子相邻，那么由于强大的库仑引力的作用，它们会脱离强作用力的束缚，所以这种情况是不被允许的。如果轮到某人操作时，所有位置都不能操作了，那么他就输了。

Youyou 快乐地答应了小 Z 的游戏请求，但是面对聪明的小 Z，Youyou 只好来求助你了。

特别地，**如果全部中子最后变成了同种粒子，那么后手获胜**。

如果你帮助 Youyou 打败了小 Z，那么 Youyou 就会送你一台 Wadm 作为奖励！

## 交互方式

你的程序应从标准输入中读入，向标准输出中输出。

输入中将包含两个整数 `n task_id` ，分别代表题目中的 $n$ 和子任务编号。

然后你需要输出一个整数 `order`，$\text{order}$ 只能是 $0$ 或 $1$。$0$ 代表你选择先手，$1$ 代表你选择后手。

接下来，你应该根据你选择的先后手情况通过标准输入输出与交互库进行交互。

- 若轮到你操作，那么你应该接着输出两个整数 `place type`，代表你将位置在 $\text{place}$ 的中子变为了电子（$\text{type}=-1$）或质子（$\text{type}=1$）。其中，你需要保证：
  - $\text{place} \in [1,n]$ 且该位置可以操作；
  - $\text{type} \in \{-1,1\}$；
  - **你已经清空缓冲区**。在 C 或 C++ 中，可使用 `fflush(stdout)` 函数。在 C++ 中，还可使用 `cout << flush`，`cout.flush()`，或使用 `endl` 而不是 `'\n'` 来输出一个换行。

- 若轮到小 Z 操作，那么你应该接着读入两个整数 `place type`，代表小 Z 将位置在 $\text{place}$ 的中子变为了电子（$\text{type}=-1$）或质子（$\text{type}=1$）。其中，保证：
  - $\text{place} \in [1,n]$ 且该位置可以操作；
  - $\text{type} \in \{-1,1\}$。

例如，如果你选择先手，那么你应该按照「输出，输入，输出，输入……」的顺序进行交互。如果你选择后手，那么你应该按照「输入，输出，输入，输出……」的顺序进行交互。

请注意，如果游戏结束，你应当立即终止程序。游戏结束后多余的输出可能会导致 RE 。

inputFormat: 见「交互方式」。

outputFormat: 见「交互方式」。

hint:
* Subtask 1（5 分）：$n \leq 4$；
* Subtask 2（8 分）：$n \leq 8$；
* Subtask 3（12 分）：$n$ 为偶数，交互库特殊策略*；
* Subtask 4（15 分）：交互库特殊策略*；
* Subtask 5（20 分）：$n$ 为偶数；
* Subtask 6（40 分）：无特殊限制。

*交互库特殊策略：每次轮到交互库操作时，交互库会找到最左侧的能操作的位置，然后如果该位置能操作为质子，则操作为质子，否则操作为电子。

对于全部的数据，保证 $1 \leq n \leq 2^{10}$ 。


title: [RC-04] 走迷宫

background:
**这是一道交互题。**

请确保您提交前认真阅读过 <https://www.luogu.com.cn/blog/luogu/interactive-problems>，并且熟知 P1947 的写法。

您可以直接在以下样例程序中编辑：

```cpp
#include<bits/stdc++.h>
using namespace std;
extern "C" bool move_to(char position);
extern "C" string find_out_map(int X,int Y,int N){
	return "233";
}
```

同时本题不支持 Pascal，祝愿 Pascal 党早日转 C++。

description:
### 题目描述

**这是一道交互题。**

你被困在一个迷宫内，你需要求出这个迷宫的地图。

迷宫是 $n\times n$ 的网格，每个位置上要么是障碍，要么是路。障碍用 `1` 表示，路用 `0` 表示。坐标按照从上到下，从左到右编号，第 $i$ 行第 $j$ 列坐标为 $(i,j)$。

定义两个格子连通当且仅当他们有公共边（四连通）。保证恰好存在一个 `0` 构成的连通块，并且你的出生点在这个连通块中。

### 实现细节

你需实现一个函数：

`string find_out_map(int x,int y,int n)`

参数为三个整数 $x,y,n$，返回值为一个字符串。其中 $x,y$ 表示你的坐标为 $(x,y)$（$1<x,y<n$），$n$ 为地图大小。

你返回的字符串的第 $i$ 位（$0\le i<n\times n$）为 `1` 表示地图的第 $\lfloor\dfrac{i}{n}\rfloor+1$ 行，第 $i+1-n\lfloor \dfrac{i}{n}\rfloor$ 列是障碍；反之为路。

你可以调用以下函数以找出答案：

`bool move_to(char position)`

其中 `position` 为 `WASD` 中任一个，分别表示试图向上，左，下，右（分别为横坐标减一，纵坐标减一，横坐标加一，纵坐标加一）移动。若这个函数返回 `1`，说明你成功向这个方向移动一格；否则说明这个方向上有障碍物，移动失败。注意除了最开始，你都不能从交互器获得当前坐标。假如 `position` 不合法，交互器的行为是未定义的。

保证地图开始时已确定，不会动态构造。保证第一列，第一行，第 $n$ 列，第 $n$ 行都是障碍。

**你的函数可能会被调用多次，请注意初始化。**

inputFormat: 这部分你无法读取，其中包含 $n$ 与地图。输入文件以加密形式给出，并且交互器中也不会解密存储。

outputFormat: 没有输出。

hint:
### 交互过程范例

假设地图为

```
1111
1011
1001
1111
```

最初传进来的参数为 $(2,2,4)$。

下面是一种合法的交互过程：

| 选手调用 | 交互器返回 |
| :----------: | :----------: |
| `move_to('S')` | 1 |
| `move_to('D')` | 1 |
| `move_to('W')` | 0 |
| 返回 `1111101110011111` | Accepted |

### 数据范围与限制

**本题时间限制 $2$ 秒，空间限制 $512\text{MB}$，且保证交互库最坏情况下所用时间小于 $0.5$ 秒、空间小于 $15\text{MB}$。**

首先交互题会受到和常规题相同的限制，如超时/超空间会导致整个测试点得零分。

在此基础上，当且仅当你报告的迷宫地图完全正确时你得分。设你调用函数最多的一次次数为 $W$，则你得到该测试点的满分，当且仅当 $W\le 5\times 10^5$。

对于 $100\%$ 的数据，$5\le n\le 500$。设调用你的函数的次数为 $x$（相当于有多组数据，你需要初始化），则 $1\le x\le 50$。详细数据范围如下，$(T)$ 表示这个测试点分数为 $T$ 分。

- 测试点 $1\ (8)$：$n=5,x\le 50$。
- 测试点 $2\ (8)$：$n=7,x\le 50$。
- 测试点 $3\ (20)$：$n\le 10,x\le 50$。
- 测试点 $4\ (10)$：$n\le 500,x\le 7$。保证仅存在恰好一个 `1` 构成的连通块。
- 测试点 $5\ (10)$：$n\le 20,x\le 20$。
- 测试点 $6\ (10)$：$n\le 50,x\le 20$。
- 测试点 $7\ (9)$：$n\le 100,x\le 10$。
- 测试点 $8\ (10)$：$n\le 200,x\le 7$。
- 测试点 $9\ (15)$：$n\le 500,x\le 7$。

### 交互题怎么调试

本题交互过程太过简单，因此本题不提供交互器。请选手自行编写。

假如你不知道怎么做：只需编写一个程序，读入地图，并且实现 `move_to` 函数，然后把你的答案函数放于其中即可运行。


title: [CEOI2014] 007

background: CEOI2014 Day2 T1，译者：小粉兔

description:
007 特工发现了她最大的敌人 De Referenced Nullpointer 博士（简称 Dr. Null）的一个阴谋：Dr. Null 将要摧毁洛谷的两台服务器中的某一台！Dr. Null 正准备去实施他的方案，并且他也正在去服务器的路上。很遗憾，这意味着 007 必须告别她正在泡着帅哥吃早餐的生活。

007 和 Dr. Null 都入侵了一个卫星系统，所以他们总是知道对方的位置。卫星系统把地图表示为一个**连通**的无向图，007 和 Dr. Null 以及两台服务器都位于节点上。**特别地，保证两台服务器位于相邻的两个节点上**。007 和 Dr. Null 都可以在一个单位时间内移动一条边，不过也可以不移动。Dr. Null 摧毁服务器也需要一个单位时间。Dr. Null 和 007 轮流行动，Dr. Null 先手。

如果 007 抓住了 Dr. Null（他们位于同一个节点上）或者可以保证 Dr. Null 在无限长的时间内无法摧毁服务器，就算 007 获胜。

007 想要知道她现在能吃着早餐泡帅哥最迟到什么时候，以确保无论 Dr. Null 采取什么策略依然可以取得胜利。

请你帮助 007 编写一个程序，计算她为了确保胜利，最迟停下吃早餐的时间。注意：当 007 还在吃早餐的时候她是没有办法抓住 Dr. Null 的，即使他们位于同一个节点上也不行。

inputFormat:
第一行两个正整数 $n, m$，分别表示图中节点数和边数。
第二行四个互不相同的正整数 $s, d, a, b$，分别表示 007 的初始位置，Dr. Null 的初始位置，以及两台服务器的位置。
接下来 $m$ 行，每行两个正整数 $u, v$，表示一条连接节点 $u$ 和 $v$ 之间的边。

outputFormat:
输出一行一个数，表示为了确保胜利，007 最多还能吃多久的早餐。具体地说，如果 007 在一开始就必须行动则输出 $0$。
如果 007 无论如何都无法胜利，输出 $-1$。

hint:
对于所有数据，保证 $4 \le n \le 2 \times {10}^5$，$3 \le m \le 6 \times {10}^5$，$1 \le s, d, a, b \le n$ 且互不相同，保证图连通。

| 子任务编号 | 分值 | 特殊限制 |
| :-: | :-: | :-: |
| $1$ | $30$ | $n \le 300$，$m \le 1600$ |
| $2$ | $70$ | 无特殊限制 |

**部分分设置**：对于每个子任务，如果你的程序的输出在其中至少一组测试点中比非负的正确答案少 $1$ 并且在其它测试点中完全正确，则你将获得该子任务的 $30 \%$ 的分数。注意如果正确答案是 $0$ 时你的程序输出 $-1$ 也算作这种情况。


title: [CEOI2014] Cake

background: CEOI2014 Day2 T2，译者：小粉兔

description:
Leopold 和 Molly 都喜欢蛋糕：Leopold 喜欢吃蛋糕，Molly 喜欢看 Leopold 吃蛋糕。

现在有 $n$ 块蛋糕排成一排，从左到右数的第 $i$ 块蛋糕编号为 $i$，每块蛋糕有一个美味度 $d_i$。

Leopold 会先吃掉编号为 $a$ 的蛋糕，这样位置 $a$ 就空了。接下来每次他会选择一个与空出的位置相邻的蛋糕中美味度最小的蛋糕吃掉（要把好吃的留到最后）。你可以发现空出的位置一定是一个连续的区间。

为了让事情更加有趣，Molly 有时会给某一块蛋糕上加一点装饰，以增加它的美味度。她保证做完此操作后，这块蛋糕的美味度会变成所有蛋糕中前 $10$ 大的。而且在任何时候任意两块蛋糕的美味度都不同。

有时 Molly 好奇在 Leopold 吃掉某块特定的编号为 $b$ 的蛋糕之前，他会吃掉多少块蛋糕。

请你帮助 Molly 编写一个程序，给出操作序列，回答 Molly 的询问。

inputFormat:
第一行两个正整数 $n, a$，分别表示蛋糕总块数以及 Leopold 第一次会吃掉哪一块蛋糕。
第二行 $n$ 个互不相同的正整数 $d_1, d_2, \ldots , d_n$，表示蛋糕的初始美丽度。
第三行一个正整数 $q$，表示操作的个数。
接下来 $q$ 行，每行形如 `E i e` 或 `F b` 表示一次操作：

- `E i e`：将编号为 $i$ 的蛋糕的美味度提升至第 $e$ 美味的。保证在操作之前比编号为 $i$ 的蛋糕美味的蛋糕的数量至少为 $e$。
- `F b`：询问 Leopold 在吃掉编号为 $b$ 的蛋糕之前会吃掉多少块蛋糕。

outputFormat: 对于每个 `F` 操作，输出一行一个数表示答案。

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

在第一次增加美味度之前，编号为 $3, 2, 4, 5, 1$ 的蛋糕会依次被吃掉。但接下来编号为 $1$ 的蛋糕太好吃了以至于它不会先被吃掉，编号为 $4$ 和 $5$ 的蛋糕先被吃掉了。注意最后一次对编号为 $5$ 的蛋糕的美味度的增加不会改变吃蛋糕的顺序。

**【数据范围与提示】**

对于所有数据，保证 $1 \le n \le 2.5 \times {10}^5$，$1 \le q \le 5 \times {10}^5$，$1 \le d_i, a, i, b \le n$，$1 \le e \le 10$。

| 子任务编号 | 分值 | 特殊限制 |
| :-: | :-: | :-: |
| $1$ | $15$ | $n, q \le {10}^4$ |
| $2$ | $15$ | $n \le 2.5 \times {10}^4$ 且 `F` 操作的数量不超过 $500$ |
| $3$ | $20$ | $q \le {10}^5$ 且 `E` 操作的数量不超过 $100$ |
| $4$ | $50$ | 无特殊限制 |


title: [CEOI2014] The Wall

background: CEOI2014 Day2 T3，译者：小粉兔

description:
Rectos 岛经常遭受洪水的泛滥和海盗的侵扰，所以 Rectos 的国王想要建造一堵城墙以保护岛上所有的村庄。

Rectos 是一个矩形岛屿，所以城墙的设计师将岛屿看作一个正方形网格。每个村庄都位于其中的某个方格中，并且首都村庄位于整座岛的西北角，也就是最左上角的方格中。

必须保证从外部（也就是整个网格的外部）在不越过城墙的条件下，是到达不了任何一个村庄的。

设计师计划城墙将只沿着网格线建造，更具体地说是按照如下方法：他将第一段城墙置于最左上角延伸出的两条网格线之一上，并且下一段城墙总是和上一段城墙首尾相连，不断重复这一过程直到又一次回到最左上角为止。这一过程可能会导致一段网格线上放置了大于一段的城墙，总而言之，城墙是沿着网格线上的一条连续闭曲线建造的。

地势测量表明，在每一段网格线上建造一段城墙都需要一定的花费。建造城墙的总花费就是建造每一段城墙的花费之和。如果在某一段网格线上建造了 $t$ 段城墙，则花费也要重复计算 $t$ 次。

国王想要花费尽量少的钱建好城墙。请你帮助国王，编写一个程序，给出村庄的位置以及每一段网格线上的建造花费，计算建造城墙所需最小的花费。

inputFormat:
第一行两个正整数 $n, m$，分别表示网格的行数和列数。
接下来 $n$ 行，每行 $m$ 个数，每个数为 $0$ 或 $1$，若为 $0$ 则表示该格没有村庄，若为 $1$ 则表示该格有村庄，保证第 $1$ 行的第 $1$ 个数一定为 $1$。
接下来 $n$ 行，每行 $m + 1$ 个非负整数，依次表示每一段竖直的网格线上的建造花费。
接下来 $n + 1$ 行，每行 $m$ 个非负整数，依次表示每一段水平的网格线上的建造花费。

outputFormat: 输出一行一个数表示建造城墙的最小花费。

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

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

**【样例 #2 解释】**

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

**【数据范围与提示】**

对于所有数据，保证 $1 \le n, m \le 400$，对于所有的建造花费 $v$，有 $1 \le v \le {10}^9$。

| 子任务编号 | 分值 | 特殊限制 |
| :-: | :-: | :-: |
| $1$ | $30$ | $n, m \le 40$ 且村庄的数量不超过 $10$ |
| $2$ | $30$ | $n, m \le 40$ |
| $3$ | $40$ | 无特殊限制 |