title: [IOI2021] 分糖果

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

### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

description:
Khong 阿姨正在给附近一所学校的学生准备 $n$ 盒糖果。盒子的编号分别为 $0$ 到 $n - 1$，开始时盒子都为空。第 $i$ 个盒子 $(0 \leq i \leq n - 1)$ 至多可以容纳 $c[i]$ 块糖果（容量为 $c[i]$）。

Khong 阿姨花了 $q$ 天时间准备糖果盒。在第 $j$ 天 $(0 \leq j \leq q - 1)$，她根据三个整数 $l[j]$、 $r[j]$ 和 $v[j]$ 执行操作，其中 $0 \leq l[j] \leq r[j] \leq n - 1$ 且 $v[j] \neq 0$。对于每个编号满足 $l[j] \leq k \leq r[j]$ 的盒子 $k$：

- 如果 $v[j] > 0$，Khong 阿姨将糖果一块接一块地放入第 $k$ 个盒子，直到她正好放了 $v[j]$ 块糖果或者该盒子已满。也就是说，如果该盒子在这次操作之前已有 $p$ 块糖果，那么在这次操作之后盒子将有 $\min(c[k], p + v[j])$ 块糖果。

- 如果 $v[j] < 0$，Khong 阿姨将糖果一块接一块地从第 $k$ 个盒子取出，直到她正好从盒子中取出 $-v[j]$ 块糖果或者该盒子已空。也就是说，如果该盒子在这次操作之前已有 $p$ 块糖果，那么在这次操作之后盒子将有 $\max(0, p + v[j])$ 块糖果。

你的任务是求出 $q$ 天之后每个盒子中糖果的数量。

inputFormat:
**实现细节**

你要实现以下函数：

```cpp
std::vector<int> distribute_candies(
  	std::vector<int> c, std::vector<int> l,
  	std::vector<int> r, std::vector<int> v)
```

- $c$：一个长度为 $n$ 的数组。 对于 $0 \leq i \leq n - 1$, $c[i]$ 表示盒子 $i$ 的容量。

- $l$、 $r$ 和 $v$：三个长度为 $q$ 的数组。 在第 $j$ 天, 对于 $0 \leq j \leq q - 1$，Khong 阿姨执行由整数 $l[j]$、 $r[j]$ 和 $v[j]$ 决定的操作，如题面所述。

outputFormat: - 该函数应该返回一个长度为 $n$ 的数组。用 $s$ 表示这个数组。 对于 $0 \leq i \leq n - 1$， $s[i]$ 应为 $q$ 天以后盒子 $i$ 中的糖果数量。


title: 「Wdoi-1.5」魔理沙的计算器

type: P

background:
魔理沙是普通而平凡的魔法使。在解决了大大小小的异变后，她终于攒足了足够多的钱在香霖堂里购置了一台 $\verb!Carno!$ 计算器，用来计算魔女之汤各种配料的含量之比。

魔理沙早就听闻灵梦通过河童重工网络[入手了一部 $\verb!Casio!$ 计算器](https://www.luogu.com.cn/problem/P5515)，来计算神社的香火钱，却买到了假货，最多只能显示整数部分（下取整）。而魔理沙的这部可以精确到小数点后面若干位（下取整）的计算器。更高级的是，这部计算器还可以支持其他的进制，其强大的功能高出了灵梦一大截。因此作为灵梦真挚的朋友，魔理沙希望向灵梦表达真挚的遗憾之情。

正当魔理沙打算出发之时，她发现虽然 $\verb!Carno!$ 计算器不会导致一些特别大的误差，但是在计算除法时仍然会出现一定的问题。考虑将计算器的进制调整为 $10$ 进制，而计算器屏幕上最多可以显示 $5$ 位数字（小数点不计入显示位数）。比如，魔理沙希望计算 $1\div 3$ 的值，那么真正显示在屏幕上的则是：

$$
0.3333
$$

按照道理上来讲，$1\div(1\div 3)$ 结果应当等于 $3$。但出乎意料的是，当魔理沙输入 $1\div 0.3333$ 后，得到的结果却是：

$$
3.0003
$$

这当然只是一个个例。当魔理沙计算 $1\div(1\div 4)$ 时，屏幕上显示出了正确的数字。

为了防止在表达遗憾之情的时候自己的计算器也出了漏子，魔理沙希望找到有多少个数字使得计算出的结果是正确的，因此她向你求助了。

description:
魔理沙的计算器可以进行 $b$ 进制的运算，屏幕上可以显示 $k$ 个数字（不包含小数点）。进行计算后，若某个数字超出了屏幕，就会被**直接舍去**（例如 $b=10$ 时 $1\div 7=0.142857\cdots$，若屏幕大小为 $4$，那么最终显示为 $0.142$）。

魔理沙用计算器计算了 $1\div n=n'$，再计算 $1\div n'=n''$（$n'$ 和 $n''$ 均为显示在屏幕上的结果）。魔理沙希望知道，有多少个正整数 $n$ 使得 $n=n''$。你只需要输出这个答案对 $998,244,353$ 取模后的结果即可。

inputFormat:
- 第一行有一个正整数 $T$，表示数据组数。
- 接下来 $T$ 行，每行有两个正整数 $b,k$，分别表示计算器的进制、屏幕上能显示的数字个数。

outputFormat:
- 输出共 $T$ 行。
- 每行输出一个整数。第 $i$ 行的整数表示第 $i$ 组数据中合法的 $n$ 的总数对 $998,244,353$ 取模后的结果。

hint:
### 样例解释

- 对于第一组询问，符合条件的数（转换成十进制）为 $1,2,4$。
- 对于第二组询问，符合条件的数（转换成十进制）为 $1,5,25$。

### 数据范围及约定

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|c|c|}\hline
\textbf{subtask}&\textbf{分值} & \bm{b\le} & \bm {k\le } & \textbf{特殊性质} & \textbf{subtask 依赖} \cr\hline
1 & 20 & 10 & 7 & - &-\cr\hline
2 & 20 & 10^5 & 2 & k=2&-\cr\hline
3 & 10 & 10^5 & 3 & k=3&- \cr\hline
4 & 50& 10^5 & 500 & -&1,2,3\cr\hline
\end{array}
$$

对于 $100\%$ 的数据，满足 $1\le T\le 10$，$2\le b\le 10^5$，$1\le k\le 500$。


title: [JOI Open 2021] Financial Report

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

description:
有一个长度为 $N$ 的序列 $A_i$，定义函数 $f(m,p_1,p_2,\cdots,p_m)$ 的值为满足：

$$\max\limits_{j=1}^{i-1}\{A_{p_j}\} < A_{p_i}$$

的 $p_i$ 的个数，当 $i=1$ 时，我们假设上面这个不等式是恒成立的。

给定一个整数 $D$，求一个序列 $p_i$ 满足：

- $1 \le m \le N$；
- $p_m=N$；
- $p_i<p_{i+1}$；
- 如果 $m \ge 2$，那么有 $p_{j+1}-p_j \le D$；
- $f(m,p_1,p_2,\dots,p_m)$ 的值最大。

求 $f$ 函数的最大值。

inputFormat:
第一行两个整数 $N,D$，意义如题面所述。

第二行 $N$ 个整数 $A_i$ 代表给定的序列。

outputFormat: 一行一个整数代表 $f$ 函数的最大值。


title: 「Wdoi-3」夜雀 collecting

background:
巧妇难为无米之炊。在制作菜品之前，米斯蒂娅必然要四处收集食材了。

然而幻想乡实在是太大，四处散落着各种各样的食材。米斯蒂娅的背包却非常有限，以至于四处采集时不得不考虑取舍的问题了。米斯蒂娅的时间非常有限，因为她必须要在夜晚摆摊之前准备好所有的食材。

于是她来向你求助，希望精通计算的你帮助她收集食材。

description:
米斯蒂娅有一个容量为 $v$ 的背包，而食材有 $x$ 种。当背包被塞满后，米斯蒂娅就不能够采集更多的食材了。

为了尽可能地收集到更多食材，又要节省更多时间，她会**依次**经过 $n$ 个采集点。每个采集点都会有一定量的食材可供采集。

具体来说，对于第 $i$ 个采集点，每种食材的个数分别为 $C_{i,1},C_{i,2}\cdots C_{i,x}$ ，其中 $C_{i,j}$ 代表该采集点有多少个第 $j$ 种食材。保证对于所有 $i$ ，都有 $\displaystyle C_{i,1}+C_{i,2}+\cdots+C_{i,x}=\sum_{j=1}^{x}C_{i,j} \leq v$ 。

每到一个采集点，米斯蒂娅都会决定是否开始采集食材。因为她非常享受采集新食材带来的愉悦感，一旦开始采集，她会将这个采集点的食材**全部采集完**。因此，如果此时她背包不足以塞下这里所有的食物，她将**不能进行**采集。尽管如此，米斯蒂娅也可以选择在采集前丢弃背包里的一些食材。

不同的食材在烹饪中的泛用性是不同的，一些食材会经常使用，而一些食材则只会出现于少数菜品。因此，每种食材在米斯蒂亚心中有着不同的价值，第 $i$ 种的价值为 $A_i$。

为了菜品的多样性，米斯蒂娅会尽可能采集更多种类的食材。于是她想知道，在经过了这 $n$ 个采集点后，她的背包中至少有 $1$ 个的食材的价值和最大是多少（也就是说，如果一种食材有多个，那么只计算一次）。

inputFormat:
第一行三个整数 $n,v,x$。
第二行 $x$ 个整数，表示每种食材的价值。
接下来 $n$ 行，每行 $x$ 个整数，第 $i$ 行的第 $j$ 个整数表示 $C_{i,j}$。

outputFormat: 一行一个整数，表示价值和。

hint:
#### 样例 1 解释

在第一个和第三个采集点收集食材。要注意的是，在采集第三个采集点前，丢弃一个第一种食材。最终，四个食材的数量分别是 $\{1,1,0,1\}$，于是获得的价值和为 $7+11+11=29$。可以证明，没有更优的方案。

---

#### 数据范围及约定

$$
\def{\arraystretch}{2}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm x & \bm n & \textbf{分值}\cr \hline
1 & 1\le x \le 10 & 1\le n\le 2\times 10^3 & 20 \cr\hline
2 & 1\le x \le 14 & 1\le n\le 10^6 & 40 \cr\hline
3 & 1\le x \le 18 & 1\le n\le 1000 & 40 \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，有 $1 \le n \le 10^6$，$1 \le x \le 18$，$1 \le v \le 2000$，$0 \le C_{i,j}$，$\sum_{j=1}^x C_{i,j} \le v$，$0 \le A_i \le 1000$。

Subtask 4 为不计分的 Hack 数据， 保证满足 Subtask 2 或 Subtask 3 的限制。

特别感谢 chenxinyang2006 对本题解法的巨大贡献。


title: [COCI2013-2014#5] LOZINKA

description:
给出一些长度为奇数的字符串，请你找出一个字符串，且它反转后的字符串也在给出的字符串中。

例如：字符串 `abcca`，如果满足条件，则字符串 `accba` 也必须出现在输入的字符串中。

输出这个字符串的长度和它处于最中间的字符。

inputFormat:
输入共 $n+1$ 行：

第 $1$ 行，一个整数 $n$，表示给出的字符串的个数；

第 $2$ 至 $n+1$ 行，每行一个字符串。

outputFormat: 输出共 $1$ 行，一个整数和一个字符，用空格隔开，分别表示符合要求的字符串的长度和它处于字符串中间的字符。

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

`las` 和 `sal` 是符合要求的字符串对，长度为 $3$，中间的字符为 `a`。

**【样例解释 #2】**

`kisik` 是回文串，翻转后的字符串仍是 `kisik`，满足要求。

**【数据范围】**

对于 $100\%$ 的数据，$1\le n\le 100$，$3\le $ 字符串长度 $\le 13$，所有字符串均由小写字母组成，保证答案是唯一的。

**【说明】**

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

题目译自[COCI2013_2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #5](https://hsin.hr/coci/archive/2013_2014/contest5_tasks.pdf) _**T1 LOZINKA**_


title: [JOI2018] Stove

description:
JOI 君的房间里有一个炉子。因为 JOI 君已经习惯了寒冷的温度，所以当他一个人在房间里时，他不需要打开炉子。但是，有客人时，他需要打开炉子。有一天，$N$ 位客人将拜访 JOI 君。第 $i$ 个客人 ($1 \leq i \leq N$) 将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。任何时间最多有一个客人访问  JOI 君。JOI 君可以随时开火或关火。JOI 君用火柴打开炉子。JOI 君只有 $K$ 根火柴。 因此他最多可以打开炉子 $K$ 次。在一天的开始，炉子是关闭的。当炉子打开时，它需要燃料。因此，JOI 君控制着他何时打开或关闭炉子，他想尽量减少炉子的总运行时间。
现给定访问 JOI 君的客人数据和 JOI 君拥有的火柴数，请编写一个程序来计算炉子总运行时间的最小值。

inputFormat: 第一行包含两个空格分隔的整数 $N$，$K$。 这意味着 $N$ 位客人将访问 JOI 君，而 JOI 君 有 $K$ 根火柴。接下来的下 $N$ 行的第 $i$ 行包含整数 $T_i$。这意味着第 $i$ 个客人将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。

outputFormat: 唯一的一行应包含一个整数为炉子总运行时间的最小值。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq K \leq N$，$1 \leq T_i \leq 10^9$（$1 \leq i \leq N$），$T_i < T_{i+1}$（$1 \leq i \leq N-1$）。
- Subtask $1$（$20$ points）：$N \leq 20$。
- Subtask $2$（$30$ points）：$N \leq 5000$。
- Subtask $3$（$50$ points）：没有额外的限制。
#### 样例说明
**对于样例 $1$**：三位客人将访问 JOI 君。如果他按以下方式打开和关闭炉子，那么当客人来访时打开炉子，他打开炉子两次，炉子的总运行时间为 $(4-1)+(7-6)=4$。
- 当第一位客人到来时，他在时间 1 打开炉子。
- 当第二位客人离开时，他在时间 4 关掉炉子。
- 当第三位客人到来时，他在时间 6 打开炉子。
- 当第三位客人离开时，他在时间 7 关掉炉子。

由于炉子的总运行时间不能小于 $4$，输出 $4$。
**对于样例 $2$**：JOI 君只能打开一次炉子。因此，他在第一个客人来的时间 $1$ 打开炉子，当第三位客人离开时他在时间 $7$ 关掉炉子。
请注意，客人离开的时间可以与下一位客人到来的时间相同。
**对于样例 $3$**：JOI 君在每位客人到来时打开炉子，并在每位客人离开时关掉炉子。
#### 题目说明：
来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T1：Stove](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t1-en.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [JOI2018] Art Exhibition

background: JOI 共和国将举行一个艺术展。许多来自全国各地的艺术作品将在艺术展中展出。

description:
有 $N$ 件艺术品是展览的候选作品。艺术品编号从 $1$ 到  $N$。每件艺术品都定义了两个整数：尺寸和价值。艺术品 $i$（$1 \leq i \leq N$）的尺寸为 $A_i$，艺术品 $i$ 的价值为 $B_i$。
在艺术展中，至少会选择并展示一件艺术品。由于展厅足够大，可以将 $N$ 件作品全部展示。但是，由于 JOI 共和国人的审美意识，我们希望展览选择的艺术品，使展出的艺术品尺寸之间的差异不会太大。另一方面，我们想展示许多具有高价值的艺术品。我们决定按照以下规则选择展览的艺术品：
- 在选择的展览作品中，$A_{max}$ 为所选作品中最大的尺寸，$A_{min}$ 为所选作品中最小的尺寸。设 $S$ 为所选艺术品的总价值。
- 然后，我们想要最大化 $S−(A_{max}−A_{min})$。
现给定展览的艺术品候选数量，以及每件艺术品的尺寸和价值，请编写一个程序来计算 $S−(A_{max}−A_{min})$ 的最大值。

inputFormat: 第一行包含一个整数 $N$，即展览艺术品的候选数量。接下来的 $N$ 行的第 $i$ 行包含两个空格分隔的整数 $A_i$、$B_i$，这意味着艺术品 $i$ 的尺寸是 $A_i$，价值是 $B_i$。

outputFormat: 唯一的一行包含一个整数为 $S−(A_{max}−A_{min})$ 的最大值。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$2 \leq N \leq 5×10^5$，$1 \leq A_i \leq 10^{15}$（$1 \leq i \leq N$），$1 \leq B_i \leq 10^9$（$1 \leq i \leq N$）。
- Subtask $1$（$10$ points）：$N \leq 16$。
- Subtask $1$（$20$ points）：$N \leq 300$。
- Subtask $2$（$20$ points）：$N \leq 5000$。
- Subtask $3$（$50$ points）：没有额外的限制。
#### 样例说明
**对于样例 $1$**：本次展览共有 $3$ 幅作品候选。每件艺术品的尺寸和价值如下：
- 艺术品 $1$ 的尺寸为 $2$，价值为 $3$。
- 艺术品 $2$ 的尺寸为 $11$，价值为 $2$。
- 艺术品 $3$ 的尺寸为 $4$，价值为 $5$。

在这种情况下，如果我们为展览选择艺术品 $1$ 和艺术品 $3$，我们有 $S−(A_{max}−A_{min})$  如下：
- 在选择的艺术品中，艺术品 $3$ 的尺寸最大。因此，$A_{max} = 4$。
- 在所选的艺术品中，艺术品 $1$ 的尺寸最小。因此，$A_{min} = 2$。
- 所选艺术品的总价值为 $3+5=8$。因此，$S=8$。
由于 $S−(A_{max}−A_{min})$ 不能大于 $7$，因此输出 $6$。
#### 题目说明：
来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T2：Art Exhibition](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t2-en.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [JOI2018] Dango Maker

background: 你是一名专业的糕点师，制作团子，日本甜饺子。现在，你要串饺子了。

description:
饺子被放置在具有 $N$ 行和 $M$ 列的单元格网格上。每个单元格包含一个饺子。每个饺子的颜色是红色（$\texttt{R}$）、绿色（$\texttt{G}$）或 白色（$\texttt{W}$）。
您将从单元格中选择三个连续的饺子，并将它们串成一根棍子。所选的三个连续饺子的方向必须是从左到右，或从上到下。
现在，您要按此顺序制作颜色为红色、绿色、白色的饺子串。你想做尽可能多的饺子串。串到棍子上的饺子的顺序必须与从单元格中选择的饺子的顺序相同。一个饺子上不能串多根棍子。
你能做多少串饺子？
现给定放置在单元格上的饺子的颜色，请编写一个程序来计算您可以制作的饺子的最大数量。颜色必须按此顺序为红色、绿色、白色。

inputFormat: 输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。接下来的 $N$ 行的第 $i$ 行包含大小为 $M$ 的字符串，由 $\texttt{R}$、$\texttt{G}$ 或 $\texttt{W}$ 组成。该字符串的第 $j$ 个字符是从上数第 $i$ 行、从左数第 $j$ 列的饺子的颜色。

outputFormat: 输出一个整数饺子串的最大数量。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq N \leq 3000$，$1 \leq M \leq 3000$，$1 \leq i \leq N$，$1 \leq j \leq M$。
- Subtask $1$（$13$ points）：$N \leq 4$，$M \leq 4$。
- Subtask $2$（$20$ points）：$N \leq 10$，$M \leq 10$。
- Subtask $3$（$67$ points）：没有额外的限制。
#### 样例说明
**对于样例 $1$**：你能制作 $3$ 串饺子。
- 您从顶部的第一行和左侧的第一列中选择三个连续的饺子。方向是从左到右。然后，你按照这个顺序把它们串成一串。
- 您从上数第一行和左数第 $4$ 列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。
- 您从上数第三行和左数第一列中选择三个连续的饺子。方向是从左到右。然后，你按照这个顺序把它们串成一串。

因为你不能做 $4$ 串，所以输出 $3$。
**对于样例 $2$**：你能制作 $4$ 串饺子。
- 您从顶部的第一行和左侧的第一列中选择三个连续的饺子。方向是从左到右。然后，你按照这个顺序把它们串成一串。
- 您从顶部的第一行和左侧的第 4 列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。
- 您从上数第二行和左数第二列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。
- 您从上数第二行和左数第三列中选择三个连续的饺子。方向是从上到下。然后，你按照这个顺序把它们串成一串。

因为你不能做 $5$ 串，所以输出 $4$。
#### 题目说明：
来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T3：Dango Maker](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t3-en.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [JOI2018] Commuter Pass

description:
JOI 君住在一个有 $N$ 个车站的城市。车站编号为 $1$ 至$N$。编号为 $1$ 至 $M$ 的有 $M$ 条铁路。铁路 $i$（$1 \leq i \leq M$）双向连接 $A_i$ 站和 $B_i$ 站，票价为 $C_i$ 日元。
JOI 君住在 $S$ 站附近，去 $T$ 站附近的 IOI 高中。他打算买一张连接这两个站的通勤票。当他购买通勤票时，他需要选择一条成本最低的 $S$ 站和 $T$ 站之间的路线。使用此通勤票，他可以沿任何方向乘坐所选路线中包含的任何铁路，而无需额外费用。
JOI 君经常去 $U$ 站和 $V$ 站附近的书店。因此，他想买一张通勤票，这样从 $U$ 站到 $V$ 站的费用可以降到最低。
当他从 $U$ 站移动到 $V$ 站时，他首先选择了一条从 $U$ 站到 $V$ 站的路线，那么他需要支付的车费是：
- $0$ 日元：如果铁路 $i$ 包含在他购买的通勤票时选择的路线中，或者，
- $C_i$ 日元：如果铁路 $i$ 不包含在他购买通勤票时选择的路线中。

上述票价的总和就是从 $U$ 站到 $V$ 站的成本。
他想知道如果他在购买通勤票时选择合适的路线，从 $U$ 站到 $V$ 站的最低成本。

inputFormat: 第一行包含两个空格分隔的整数 $N$，$M$。这意味着 JOI 君居住的城市有 $N$ 个车站和 $M$ 条铁路。第二行包含两个空格分隔的整数 $S$，$T$。这意味着 JOI 君计划购买从 $S$ 站到 $T$ 站的通勤票。第三行包含两个空格分隔的整数 $U$，$V$。这意味着 JOI 君想要最小化从站 $U$ 到站 $V$ 的成本。接下来的 $M$ 行的第 $i$ 行包含三个空格分隔的整数 $A_i$，$B_i$，$C_i$。铁路 $i$ 双向连接 $A_i$ 站和 $B_i$ 站，票价为 $C_i$ 日元。

outputFormat: 如果他在购买通勤票时选择了适当的路线，则输出应包含一个整数为从站 $U$ 到站 $V$ 的最小成本。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，
$2 \leq N \leq 10^5$，$1 \leq M \leq 2×10^5$，$1 \leq S \leq N$，$1 \leq T \leq N$，$1 \leq U \leq N$，$1 \leq V \leq N$，$S {=}\mathllap{/\,} T$，$U {=}\mathllap{/\,} V$，$ S{=}\mathllap{/\,} U$ 或 $T {=}\mathllap{/\,} V$，$1 \leq A_i \leq B_i \leq N$（$1 \leq i \leq M$）。对于每 $1 \leq i < j \leq M$，$A_i {=}\mathllap{/\,} A_j$ 或 $B_i {=}\mathllap{/\,} B_j$，$1 \leq C_i \leq 10^9$（$1 \leq i \leq M$）。JOI 君可以从任何车站移动到任何其他车站乘坐铁路。
- Subtask $1$（$16$ points）：$S=U$。
- Subtask $2$（$15$ points）：从 $S$ 站到 $T$ 站有一条成本最低的唯一路线。
- Subtask $3$（$24$ points）：$N \leq 300$。
- Subtask $4$（$45$ points）：没有额外的限制。
#### 样例说明
**对于样例 $1$**：JOI 君在购买通勤票时只能选择一条路线：$1$ 号站 → $2$ 号站 →$3$ 号站 → $5$ 号站 → $6$ 号站。为了尽量减少从 $1$ 号站到 $4$ 号站的成本 ，他选择以下路线：$1$ 站 → $2$ 站 → $3$ 站 → $5$ 站 → $4$ 站。选择这条路线时，他需要支付的车费为。
- $2$ 日元用于车站 $4$ 和车站 $5$ 的铁路 $5$，以及，
- $0$ 日元：其他铁路。

**对于样例 $2$**：JOI 君从 $3$ 号站移动到 $6$ 号站时，不使用通勤票。
#### 题目说明：
来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T4：Commuter Pass](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t4-en.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。
#### Hack 说明
[@gaojunqing](https://www.luogu.com.cn/user/536005) 于 2021 年 11 月 6 日向供题人提供一组 hack 数据，经过多次检验后于 2021 年 11 月 7 日加入到本题测试数据中。
出于对该 JOI 原题的尊重与体验考虑，一律所加入的 hack 数据均不做分值改变，即满分依然为 100 分，新增 hack 数据单独放置在 Subtask #5 ，且分数为 0 分。即如通过原所有测试数据而未通过 hack 数据，将获得 100 分但不能 AC，当且仅当通过全部测试数据方可 AC。


title: [JOI2018] Snake Escaping

description:
JOI 实验室有 $2^L$ 条毒蛇。蛇的编号为  $0,1,\cdots,2^L−1$。每条蛇从头到尾分为  $L$ 个部分。每个部分的颜色是蓝色或红色。 对于毒蛇 $i$，令 $i = \sum_{k=1}^{L} c_k2^{L-k}$（$0 \leq c_k \leq 1$）为 $i$ 的二进制表达式。那么，
- 如果 $c_k=0$，毒蛇 $i$ 从头开始的第 $k$ 部分的颜色是蓝色，
- 如果 $c_k=1$，毒蛇 $i$ 从头开始的第 $k$ 部分的颜色是红色。

每条毒蛇都有一个 $0$ 到 $9$ 之间的整数，包括 $0$ 和 $9$，为毒性。给出一个由 $\texttt{0,1,2,3,4,5,6,7,8,9}$ 组成的长度为  $2^L$ 的字符串 $S$。第 $i$ 个字符（$1 \leq i \leq 2^L$）是毒蛇 $i−1$ 的毒性。由于毒蛇行动迅速，所以经常从 JOI 实验室逃走。住在实验室附近的人向 JOI 实验室投诉，他们看到毒蛇从实验室逃逸。您将收到 $Q$ 天的投诉清单。 第 $d$ 天的投诉（$1 \leq d \leq Q$）是一个长度为 $L$ 的字符串 $T_d$，由 $\texttt{0,1,?}$ 组成。
- 如果 $T_d$ 的第 $j$ 个字符（$1 \leq j ≤ L$）为 $\texttt{0}$，这意味着第 $d$ 天从实验室逃出的每条毒蛇的第 $j$ 个部分是蓝色的，
- 如果 $T_d$ 的第 $j$ 个字符（$1 \leq j \leq L$）为 $\texttt{1}$，这意味着第 $d$ 天从实验室逃出的每条毒蛇的第 $j$ 部分是红色的，并且
- 如果 $T_d$ 的第 $j$ 个字符（$1 \leq j \leq L$）为 $\texttt{?}$，这意味着人们没有提供关于第 $d$ 天从实验室逃逸的毒蛇的第 $j$ 部分的信息。

所有的投诉都是准确的信息。所有从实验室逃逸的毒蛇都在同一天被 JOI 实验室的工作人员收留。可能发生同一条蛇在不同的日子逃脱。
JOI 实验室执行主任 K 教授为了估计毒蛇逃逸的风险，想知道可能逃出实验室的毒蛇的毒性总和。 你的任务是编写一个程序，根据 $Q$ 天的投诉列表，计算每天可能从实验室逃逸的蛇的毒性总和。
现给定描述毒蛇毒性的字符串 $S$ 和 $Q$ 天的投诉列表，请编写一个程序来计算每天可能从实验室逃逸的蛇的毒性总和。
请注意，此任务的内存限制很小。

inputFormat: 第一行包含两个空格分隔的整数 $L$，$Q$，分别是每条毒蛇的部位数和投诉天数。第二行包含长度为 $2^L$ 的字符串 $S$，描述了毒蛇的毒性。后面 $Q$ 行的第 $d$ 行包含一个长度为 $L$ 的字符串 $T_d$，为第 $d$ 天的投诉。

outputFormat: 共 $Q$ 行，第 $d$ 行应包含一个整数，即第 $d$ 天可能从实验室逃逸的蛇的毒性总和。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq L \leq 20$，$1 \leq Q \leq 10^6$，$S$ 是长度为 $2^L$ 的字符串，字符串 $S$ 由 $\texttt{0,1,2,3,4,5,6,7,8,9}$ 组成，$T_d$ 是长度为 $L$（$1 \leq d \leq Q$）的字符串，字符串 $T_d$ 由 $\texttt{0,1,?}$（$1 \leq d \leq Q$）组成。
- Subtask $1$（$5$ points）：$L \leq 10$，$Q \leq 1000$。
- Subtask $2$（$7$ points）：$L \leq 10$。
- Subtask $3$（$10$ points）：$L \leq 13$。
- Subtask $4$（$53$ points）：$Q \leq 5000$。
- Subtask $5$（$25$ points）：没有额外的限制。

#### 样例说明
**对于样例 $1$**：$L=3$，共 $2^3=8$条毒蛇，它们中的每一条都分为 $3$ 个部分。 投诉时间为 $5$ 天。
- 第一天，可能逃出实验室的毒蛇只有毒蛇 $0$。毒性总和为 $1$。
- 第二天，可能从实验室逃逸的毒蛇是毒蛇 $0,1,2,3$。毒性总和为 $10$。
- 第三天，可能从实验室逃逸的毒蛇是毒蛇  $4,6$。毒性总和为 $12$。
- 第四天，可能从实验室逃逸的毒蛇是毒蛇 $3,7$。毒性总和是 $12$。
- 第五天，可能从实验室逃逸的毒蛇是毒蛇 $0,1,2,3,4,5,6,7$。毒性总和为 $36$。
#### 题目说明：
来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T5：Snake Escaping](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t5-en.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: 与圆相关的计算

type: B

description: 给出圆的半径，求圆的直径、周长和面积。输入圆的半径实数 $r$，输出圆的直径、周长、面积，每个数保留小数点后 $4$ 位。圆周率取值为 $3.14159$。

inputFormat: 输入包含一个实数 $r$（$0<r \le 10000$），表示圆的半径。

outputFormat: 输出一行，包含三个数，分别表示圆的直径、周长、面积，数与数之间以一个空格分开，每个数保留小数点后 $4$ 位。


title: 计算并联电阻的阻值

description:
对于阻值为 $r_1$ 和 $r_2$ 的电阻，其并联电阻阻值公式计算如下：
$$R=\dfrac{1}{\dfrac{1}{r_1}+\dfrac{1}{r_2}}$$

输入实数 $r_1,r_2$。输出并联之后的阻抗大小，结果保留小数点后 $2$ 位。

inputFormat: 两个实数 $r_1,r_2$，以一个空格分开。

outputFormat: 并联之后的阻抗大小，保留小数点后 $2$ 位。


title: 浮点数向零舍入

description: 输入一个双精度浮点数，将其向零舍入到整数。说明：向零舍入的含义是，正数向下舍入，负数向上舍入。

inputFormat: 一个双精度浮点数 $x$。

outputFormat: 一个整数，即向零舍入到整数的结果。


title: 打印 ASCII 码

description: 输入一个除空格以外的可见字符，输出其 ASCII 码。

inputFormat: 一个除空格以外的可见字符。

outputFormat: 一个十进制整数，即该字符的 ASCII 码。


title: 打印字符

description: 输入一个 ASCII 码，输出对应的字符。

inputFormat: 一个整数，即字符的 ASCII 码，保证存在对应的可见字符。

outputFormat: 一行，包含相应的字符。


title: 整型与布尔型的转换

description: 将一个整型变量的值赋给一个布尔型变量，再将这个布尔型变量的值赋给一个整型变量，得到的值是多少？

inputFormat: 一个整型范围内的整数，即初始时整型变量的值。

outputFormat: 一个整数，经过上述过程后得到的结果。


title: 分糖果

description: 某个幼儿园里，有 $5$ 位小朋友编号依次为 $1,2,3,4,5$ 他们按照自己的编号顺序围坐在一张圆桌旁。他们身上有若干糖果，现在他们玩一个分糖果游戏。从 $1$ 号小朋友开始，将自己的糖果均分成 $3$ 份（如果有多余的糖果，就自己立即吃掉），自己留一份，其余两份分给和他相邻的两个小朋友。接着 $2,3,4,5$ 号小朋友也这样做。问一轮结束后，每个小朋友手上分别有多少糖果。

inputFormat: 一行，$5$ 个用空格隔开的 `int` 范围内的正整数，分别是游戏开始时  $1,2,3,4,5$ 号小朋友手里糖果的数量。

outputFormat: $2$ 行，第 $1$ 行是用一个空格隔开的 $5$ 个整数，表示一轮游戏结束后  $1,2,3,4,5$ 号小朋友手里糖果的数量。第 $2$ 行是一个整数，表示一轮游戏过程中吃掉的糖果的总数。


title: 输出保留 3 位小数的浮点数

description:
读入一个单精度浮点数，保留 $3$ 位小数输出这个浮点数。

**提示：就这题来说，请使用 `float` 类型的单精度浮点数。**

inputFormat: 只有一行，一个单精度浮点数。

outputFormat: 也只有一行，读入的单精度浮点数。


title: 输出保留 12 位小数的浮点数

description: 读入一个双精度浮点数，保留 $12$ 位小数，输出这个浮点数。

inputFormat: 只有一行，一个双精度浮点数。

outputFormat: 也只有一行，保留 $12$ 位小数的浮点数。


title: 空格分隔输出

description: 读入一个字符，一个整数，一个单精度浮点数，一个双精度浮点数，然后按顺序输出它们，并且要求在他们之间用一个空格分隔。输出浮点数时保留 $6$ 位小数。

inputFormat:
第一行是一个字符；

第二行是一个整数；

第三行是一个单精度浮点数；

第四行是一个双精度浮点数。

outputFormat: 输出字符、整数、单精度浮点数和双精度浮点数，之间用空格分隔。


title: 输出浮点数

description: 读入一个双精度浮点数，分别按输出格式 `%f` ，`%f` 保留 $5$ 位小数，`%e` 和 `%g` 的形式输出这个数，每次在单独一行上输出。

inputFormat: 一个双精度浮点数。

outputFormat:
第一行是按 `%f` 输出的双精度浮点数；

第二行是按 `%f` 保留 $5$ 位小数输出的双精度浮点数；

第三行是按 `%e` 输出的双精度浮点数；

第四行是按 `%g` 输出的双精度浮点数。


title: 输出字符菱形

description: 用 `*` 构造一个对角线长 $5$ 个字符，倾斜放置的菱形。

inputFormat: 没有输入要求。

outputFormat: 如样例所示。用 `*` 构成的菱形。


title: 计算浮点数相除的余

description: 计算两个双精度浮点数 $a$ 和 $b$ 的相除的余数，$a$ 和 $b$ 都是双精度浮点数。这里余数（$r$）的定义是：$a=k \times b+r$，其中 $k$ 是整数，$0 \le r<b$。

inputFormat: 输入仅一行，包括两个双精度浮点数 $a$ 和 $b$。

outputFormat:
输出也仅一行，$a/b$ 的余数。

选手输出与标准答案的绝对误差或相对误差不超过 $10^{-5}$ 即视为正确。

hint:
### 「暂时的」数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq a \leq 10 ^ 6$，$1 \leq b \leq 10 ^ 3$，$a > b$。

> **为什么是「暂时的」？**
> 原题没有标注数据范围，并且由于涉及到浮点数取模，一些情况想要进行处理是很费劲的。所以暂时设置一个较为宽松的数据规模约定。后续数据可能会进行加强。


title: 计算球的体积

description:
已知球半径为 $r$ 时，球的体积为 $V=\frac{4}{3}\pi r^3$。

小理手里有个半径为 $r$ 的球体，他现在想知道这个球的体积为多少？

**计算时，取 $\pi = 3.14$**。

inputFormat: 输入共一行，其中包括一个正整数 $r$ 表示球体的半径。

outputFormat: 输出共一行，其中包括球体的体积。**要求保留小数点后$5$ 位**。

hint: $1\leq r\leq 100$。


title: 反向输出一个三位数

description: 将一个三位数反向输出，例如输入 $358$，反向输出 $853$。

inputFormat: 一个三位数 $n$。

outputFormat: 反向输出 $n$。


title: 大象喝水

description:
一只大象口渴了，要喝 $20$ 升水才能解渴，但现在只有一个深 $h$ 厘米，底面半径为 $r$ 厘米的小圆桶 （$h$ 和 $r$ 都是整数）。问大象至少要喝多少桶水才会解渴。

**Update：数据更新，这里我们近似地取圆周率 $\pi = 3.14$。**

inputFormat: 输入有一行：包行两个整数，以一个空格分开，分别表示小圆桶的深 $h$ 和底面半径 $r$，单位都是厘米。

outputFormat: 输出一行，包含一个整数，表示大象至少要喝水的桶数。

hint:
### 数据规模与约定
对于全部的测试点，保证 $1 \leq h \leq 500$，$1 \leq r \leq 100$。


title: 计算线段长度

description:
已知线段的两个端点的坐标 `A(Xa,Ya)`，`B(Xb
,Yb)` ，求线段 AB 的长度。

inputFormat:
输入。

共两行。

第一行是两个实数 $Xa，Ya$，即 $A$ 的坐标。

第二行是两个实数 $Xb，Yb$，即 $B$ 的坐标。

输入中所有实数的绝对值均不超过 $10000$。

outputFormat:
输出。

一个实数，即线段 $AB$ 的长度，保留到小数点后 $3$ 位。


title: 计算三角形面积

description: 平面上有一个三角形，它的三个顶点坐标分别为 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，那么请问这个三角形的面积是多少。

inputFormat: 输入仅一行，包括 $6$ 个双精度浮点数，分别对应 $x_1,y_1,x_2,y_2,x_3,y_3$。

outputFormat: 输出也是一行，输出三角形的面积，精确到小数点后两位。


title: 等差数列末项计算

description:
等差数列是一个很有趣的数列，它的任何相邻两项的差相等。

现在给出一个等差数列的前两项 $a_1,a_2$ 的值，求第 $n$ 项是多少。

outputFormat: 一个整数，即第 $n$ 项的值。


title: A*B 问题

description: 输入两个正整数 $A$ 和 $B$，求 $A \times B$ 的值。注意乘积的范围和数据类型的选择。

inputFormat: 一行，包含两个正整数 $A$ 和 $B$，中间用单个空格隔开。$1 \le A,B \le 50000$。

outputFormat: 一个整数，即 $A \times B$ 的值。


title: 计算 2 的幂

description: 给定非负整数 $n$，求 $2^n$ 的值。

inputFormat: 一个整数 $n$。$0\le n<31$。

outputFormat:
一个整数，即 $2$ 的 $n$ 次方。

请注意，如果您正在使用 `cout` 进行输出，您需要关注被输出的数据的类型。输出格式不符合预期可能会造成答案错误。

常用函数的返回值类型可以在 [cppreference.com](https://en.cppreference.com/w/) 和 [cplusplus.com](https://cplusplus.com/) 查询到。例如，您可以在这两个网站中查到 `pow` 函数的返回值是 `float` 或 `double`。

您可以使用显式或隐式的类型转换，来变换数据类型。


title: 判断数正负

description: 给定一个整数 $N$，判断其正负。如果 $N>0$, 输出 `positive` ; 如果 $N=0$, 输出 `zero` ; 如果 $N<0,$ 输出 `negative`。

outputFormat:
如果 $N>0$， 输出 `positive`;

如果 $N=0$, 输出 `zero`；

如果 $N<0$， 输出 `negative`。


title: 输出绝对值

description: 输入一个浮点数 $n$，输出这个浮点数的绝对值。

inputFormat: 输入一个浮点数 $n$，其绝对值不超过 $10000$。

outputFormat: 输出 $n$ 的绝对值，保留到小数点后两位。


title: 奇偶数判断

description: 给定一个整数，判断该数是奇数还是偶数。如果 $n$ 是奇数，输出 `odd`；如果 $n$ 是偶数，输出 `even`。

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

outputFormat: 输出仅一行，如果 $n$ 是奇数，输出 `odd`；如果 $n$ 是偶数，输出 `even`。


title: 奇偶 ASCII 值判断

description:
任意输入一个字符，判断其 ASCII 是否是奇数，若是，输出 `YES`，否则，输出 `NO` 。

例如，字符 `A` 的 ASCII 值是 `65`，则输出 `YES`，若输入字符 `B`(ASCII 值是 $66$)，则输出 `NO`。

inputFormat: 输入一个字符。

outputFormat: 如果其 ASCII 值为奇数，则输出 `YES`，否则，输出 `NO`。

samples: A YES

samples: B NO


title: 整数大小比较

description: 输入两个整数，比较它们的大小。若 $x>y$ ，输出 `>` ；若 $x=y$ ，输出 `=` ；若 $x<y$，输出 `<` 。

outputFormat: 一个字符。若 $x>y$，输出 `>` ；若 $x=y$ ，输出 `=` ；若 $x<y$ ，输出 `<` ；


title: 判断是否为两位数

description: 判断一个正整数是否是两位数（即大于等于 $10$ 且小于等于 $99$）。

inputFormat: 一个正整数，不超过 $1000$。

outputFormat: 一行。若该正整数是两位数，输出 $1$，否则输出 $0$。


title: 收集瓶盖赢大奖

description: 某饮料公司最近推出了一个“收集瓶盖赢大奖”的活动：如果你拥有 $10$ 个印有“幸运”、或 $20$ 个印有“鼓励”的瓶盖，就可以兑换一个神秘大奖。现分别给出你拥有的印有“幸运”和“鼓励”的瓶盖数，判断是否可以去兑换大奖。若可以兑换大奖，输出 `1` ，否则输出 `0` 。

inputFormat: 一行，包含两个整数，分别是印有“幸运”和“鼓励”的瓶盖数，用一个空格隔开。

outputFormat: 一行。若可以兑换大奖，输出 $1$ ，否则输出 $0$。


title: 判断一个数能否同时被 3 和 5 整除

description: 判断一个数 $n$ 能否同时被 $3$ 和 $5$ 整除。

inputFormat: 输入一行，包含一个整数 $n$。

outputFormat: 输出一行，如果能同时被 $3$ 和 $5$ 整除输出 `YES`，否则输出 `NO`。


title: 判断能否被 3，5，7 整除

description:
给定一个整数 $x$，判断它能否被 $3$，$5$，$7$ 整除，并输出以下信息：

1、能同时被 $3,5,7$ 整除（直接输出 `3 5 7`，每个数中间一个空格）；

2、只能被其中两个数整除（按从小到大的顺序输出两个数，例如：`3 5` 或者 `3 7` 或者 `5 7`，中间用空格分隔）；

3、只能被其中一个数整除（输出这个除数）；

4、不能被任何数整除，输出小写字符 `n`。

inputFormat: 输入一行，包括一个整数 $x$。

outputFormat: 输出一行，按照描述要求给出整数被 $3$，$5$，$7$ 整除的情况。

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

对于全部的测试点，保证 $1 \leq x \leq 200$。


title: 有一门课不及格的学生

description: 给出一名学生的语文、数学、英语成绩，判断他是否恰好有一门课不及格（成绩小于 $60$ 分）。若该学生恰好有一门成绩不及格输出 $1$，否则输出 $0$。

inputFormat: 一行包含三个 $0 \sim 100$ 之间的整数，分别表示该生的语文、数学、英语成绩。

outputFormat: 该学生恰好有一门成绩不及格输出 $1$，否则输出 $0$。


title: 晶晶赴约会

description: 晶晶的朋友贝贝约晶晶下周一起去看展览，但晶晶每周的 $1,3,5$ 有课必须上课，请帮晶晶判断她能否接受贝贝的邀请，如果能输出 `YES`；如果不能则输出 `NO`。

inputFormat: 输入有一行，贝贝邀请晶晶去看展览的日期，用数字 $1$ 到 $7$ 表示从星期一到星期日。

outputFormat: 输出有一行，如果晶晶可以接受贝贝的邀请，输出 `YES`，否则，输出 `NO`。注意 `YES` 和 `NO` 都是大写字母！


title: 骑车与走路

description: 在清华校园里，没有自行车，上课办事会很不方便。但实际上。并非去办任何事情都是骑车快，因为骑车总要找车、开锁、停车、锁车等，这要耽误一些时间。假设找到自行车，开锁，上车起步的时间为 $27$ 秒；停车锁车的时间为 $23$ 秒；步行每秒行走 $1.2$ 米，骑车每秒行走 $3.0$ 米。请判断走不同的距离去办事，是骑车快还是走路快。

inputFormat: 输入一行，包含一个整数，表示一次办事要行走的距离，单位为米。

outputFormat:
- 如果骑车快，输出一行 `Bike`；

- 如果走路快，输出一行 `Walk`；

- 如果一样快，输出一行 `All`。


title: 分段函数

description:
编写程序，计算下列分段函数 $y=f(x)$ 的值。

当 $0 \le x<5$ 时，$y=-x+2.5$。

当 $5 \le x<10$ 时，$y=2-1.5(x-3)(x-3)$。

当 $10 \le x<20$ 时，$y=x/2-1.5$。

inputFormat: 一个浮点数 $x$。

outputFormat: 输出 $x$ 对应的分段函数值：$f(x)$。结果保留到小数点后三位。


title: 计算邮资

description:
请根据邮件的重量和用户选择是否加急计算邮费。计算规则：

- 重量在 $1000$ 以内（包括），基本费 $8$ 元；

- 超过 $1000$ 克的部分，每 $500$ 克加收超重费 $4$ 元，不足 $500$ 克部分按 $500$ 克计算；

- 如果用户选择加急，多收 $5$ 元。

inputFormat:
一行，包含一个正整数 $x$ 和一个字符 c(`y` 或 `n`)，之间用一个空格隔开，分别表示重量和是否加急。

如果字符是 `y`，说明选择加急；如果字符是 `n`，说明不加急。

outputFormat: 输出一行一个正整数，表示邮费。


title: 最大数输出

description: 输入三个整数，输出最大的数。

inputFormat: 输入为一行，包含三个整数，数与数之间以一个空格分开。

outputFormat: 输出一行，包含一个整数，即最大的整数。

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

对于全部的测试点，保证输入的整数均在 32 位有符号整型 (`int`/`long int`) 范围内。


title: 三角形判断

description: 给定三个正整数，分别表示三条线段的长度，判断这三条线段能否构成一个三角形。

inputFormat: 输入共一行，包含三个正整数，分别表示三条线段的长度，数与数之间以一个空格分开。（三条边的长度均不超过 $10000$）

outputFormat: 如果能构成三角形，则输出 `1` ，否则输出 `0`。

hint:
构成三角形的条件：

任意两边长度之和大于第三条边的长度。


title: 点和正方形的关系

description: 有一个正方形，四个角的坐标 $(x,y)$ 分别是 $(1,-1)$、$(1,1)$、$(-1,-1)$、$(-1,1)$，$x$ 是横轴，$y$ 是纵轴。写一个程序，判断一个给定的点是否在这个正方形内（包括正方形边界）。

inputFormat: 输入一行，包括两个整数 $x,y$，以一个空格分开，表示坐标 $(x,y)$。

outputFormat: 输出一行，如果点在正方形内，则输出 `yes`，否则输出 `no`。

samples:
1 1
yes


title: 简单计算器

description:
一个最简单的计算器，支持 `+,-,*,/` 四种运算。仅需考虑输入输出为整数的情况，数据和运算结果不会超过 `int` 表示的范围。然而：

1. 如果出现除数为 $0$ 的情况，则输出：`Divided by zero!`。

2. 如果出现无效的操作符（即不为 `+,-,*,/` 之一），则输出：`Invalid operator!`。

3. 除号表示整除，结果向 0 取整。

inputFormat: 输入只有一行，共有三个参数，其中第 $1,2$ 个参数为整数，第 $3$ 个参数为操作符`（+,-,*,/）`。

outputFormat:
输出只有一行，一个整数，为运算结果。然而：

1. 如果出现除数为 $0$ 的情况，则输出：`Divided by zero!`。

2. 如果出现无效的操作符（即不为 `+,-,*,/` 之一），则输出：`Invalid operator!`。

samples:
5 0 /
Divided by zero!


title: 求一元二次方程

description:
利用公式 :

$$x_1=\frac{-b+\sqrt{b^2-4ac}}{2a} , x_2=\frac{-b-\sqrt{b^2-4ac}}{2a}$$

求一元二次方程 $ax^2+bx+c=0$ 的根，其中 $a$ 不等于 $0$。结果要求精确到小数点后 $5$ 位。

inputFormat: 输入一行，包含三个浮点数 $a,b,c$（它们之间以一个空格分开），分别表示方程 $ax^2+bx+c=0$ 的系数。

outputFormat:
输出一行，表示方程的解。

若两个实根相等，则输出形式为：`x1=x2=aaaa`；

若两个实根不等，在满足根小者在前的原则，则输出形式为：`x1=aaaa;x2=bbbb`；

若无实根输出 `No answer!`。

所有输出部分要求精确到小数点后 $5$ 位，数字、符号之间没有空格。


title: 求平均年龄

description: 班上有学生若干名，给出每名学生的年龄（整数），求班上所有学生的平均年龄，保留到小数点后两位。

inputFormat: 第一行有一个整数 $n$（$1 \le n \le 100$），表示学生的人数。其后 $n$ 行每行有 $1$ 个整数，表示每个学生的年龄，取值为 $15$ 到 $25$。

outputFormat: 输出一行，该行包含一个浮点数，为要求的平均年龄，保留到小数点后两位。


title: 均值

description: 给出一组样本数据，计算其均值。

inputFormat:
输入有两行，第一行包含一个整数，表示样本容量 $n$。
第二行包含 $n$ 个浮点数 $a_i$，代表各个样本数据。

outputFormat:
输出一行，包含一个浮点数，表示均值。

选手输出与标准输出的相对误差或绝对误差不超过 $10^{-3}$ 即视为正确。

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

对于全部的测试点，保证 $1 \leq n \leq 100$，$|a_i| \leq 10^4$。


title: 求整数的和与均值

description: 读入 $n(1 \le n \le 10000)$ 个整数，求它们的和与均值。

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

第 $2 \sim n+1$ 行每行包含 $1$ 个整数。每个整数的绝对值均不超过 $10000$。

outputFormat: 输出一行，先输出和，再输出平均值（保留到小数点后 $5$ 位），两个数间用单个空格分隔。


title: 最高的分数

description: 孙老师讲授的《计算概论》这门课期中考试刚刚结束，他想知道考试中取得的最高分数。因为人数比较多，他觉得这件事情交给计算机来做比较方便。你能帮孙老师解决这个问题吗？

inputFormat: 输入两行，第一行为整数 $n$（$1 \le n<100$），表示参加这次考试的人数。第二行是这 $n$ 个学生的成绩，相邻两个数之间用单个空格隔开。所有成绩均为 $0$ 到 $100$ 之间的整数。

outputFormat: 输出一个整数，即最高的成绩。


title: 奥运奖牌计数

description: $2008$ 年北京奥运会，A 国的运动员参与了 $n$ 天的决赛项目 $(1 \le n \le 100)$。现在要统计一下 A 国所获得的金、银、铜牌数目及总奖牌数。输入第 $1$ 行是 A 国参与决赛项目的天数 $n$，其后 $n$ 行，每一行是该国某一天获得的金、银、铜牌数目（不超过 $100)$。输出 $4$ 个整数，为 A 国所获得的金、银、铜牌总数及总奖牌数。

inputFormat: 第 $1$ 行是 A 国参与决赛项目的天数 $n$，其后 $n$ 行，每一行是该国某一天获得的金、银、铜牌数目，以一个空格分开。

outputFormat: 输出 $1$ 行，包括 $4$ 个整数，为 A 国所获得的金、银、铜牌总数及总奖牌数，以一个空格分开。


title: 奇数求和

description: 计算非负整数 $m$ 到 $n$（包括 $m$ 和 $n$）之间的所有奇数的和，其中，$m$ 不大于 $n$，且 $n$ 不大于 $300$。例如 $m=3,n=12,$ 其和则为：$3+5+7+9+11=35$。

inputFormat: 两个数 $m$ 和 $n$，两个数以一个空格分开，其中 $0 \le m \le n \le 300$。

outputFormat: 输出一行，包含一个整数，表示 $m$ 到 $n$（包括 $m$ 和 $n$）之间的所有奇数的和。


title: 满足条件的数累加

description: 将正整数 $m$ 和 $n$ 之间（包括 $m$ 和 $n)$ 能被 $17$ 整除的数累加，其中，$0<m<n<1000$。

inputFormat: 一行，包含两个整数 $m$ 和 $n$，其间，以一个空格间隔。

outputFormat: 输出一行，包行一个整数，表示累加的结果。


title: 整数的个数

description: 给定 $k$（$1<k<100$）个正整数，其中每个数都是大于等于 $1$，小于等于 $10$ 的数。写程序计算给定的 $k$ 个正整数中，$1$，$5$ 和 $10$ 出现的次数。

inputFormat: 输入有两行：第一行包含一个正整数 $k$，第二行包含 $k$ 个正整数，每两个正整数用一个空格分开。

outputFormat: 输出有三行，第一行为 $1$ 出现的次数，，第二行为 $5$ 出现的次数，第三行为 $10$ 出现的次数。


title: 乘方计算

description: 给出一个整数 $a$ 和一个正整数 $n$，求乘方 $a^n$。

outputFormat: 一个整数，即乘方结果。题目保证最终结果的绝对值不超过 $1000000$。


title: 人口增长问题

description: 假设目前的世界人口有 $x$ 亿，按照每年 $0.1\%$ 的增长速度，$n$ 年后将有多少人？

inputFormat: 一行两个正整数 $x$ 和 $n$，之间有一个空格。其中，$1 \leq x\leq 100, 1\leq n\leq 100$。

outputFormat: 一行一个数，表示答案。以亿为单位，保留到小数点后 $4$ 位。


title: 斐波那契数列

description:
斐波那契数列是指这样的数列：数列的第一个和第二个数都为 $1$，接下来每个数都等于前面 $2$ 个数之和。

给出一个正整数 $a$，要求斐波那契数列中第 $a$ 个数是多少。

inputFormat: 第 $1$ 行是测试数据的组数 $n$，后面跟着 $n$ 行输入。每组测试数据占 $1$ 行，包括一个正整数 $a$（$1 \le a \le 30$）。

outputFormat: 输出有 $n$ 行，每行输出对应一个输入。输出应是一个正整数，为斐波那契数列中第 $a$ 个数的大小。


title: 鸡尾酒疗法

description:
鸡尾酒疗法，原指“高效抗逆转录病毒治疗”（HAART），由美籍华裔科学家何大一于 $1996$ 年提出，是通过三种或三种以上的抗病毒药物联合使用来治疗艾滋病。该疗法的应用可以减少单一用药产生的抗药性，最大限度地抑制病毒的复制，使被破坏的机体免疫功能部分甚至全部恢复，从而延缓病程进展，延长患者生命，提高生活质量。

人们在鸡尾酒疗法的基础上又提出了很多种改进的疗法。为了验证这些治疗方法是否在疗效上比鸡尾酒疗法更好，可用通过临床对照实验的方式进行。

假设鸡尾酒疗法的有效率为 $x$，新疗法的有效率为 $y$，如果 $y-x$ 大于 $5\%$，则效果更好，如果 $x-y$ 大于 $5\%$，则效果更差，否则称为效果差不多。

下面给出 $n$ 组临床对照实验，其中第一组采用鸡尾酒疗法，其他 $n-1$ 组为各种不同的改进疗法。请写程序判定各种改进疗法效果如何。

inputFormat:
第一行为整数 $n$（$1<n \le 20$）；

其余 $n$ 行每行两个整数，第一个整数是临床实验的总病例数（小于等于 $10000)$，第二个疗效有效的病例数。

这 $n$ 行数据中，第一行为鸡尾酒疗法的数据，其余各行为各种改进疗法的数据。

outputFormat:
有 $n-1$ 行输出，分别表示对应改进疗法的效果：

如果效果更好，输出 `better`；如果效果更差，输出 `worse`；否则输出 `same`。


title: 救援

description:
救生船从大本营出发，营救若干屋顶上的人回到大本营，屋顶数目以及每个屋顶的坐标。

和人数都将由输入决定，求出所有人都到达大本营并登陆所用的时间。

在直角坐标系的原点是大本营，救生船每次从大本营出发，救了人之后将人送回大本营。坐标系中的点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。救生船每次从大本营出发，以速度 $50$ 米 / 分钟驶向下一个屋顶，达到一个屋顶后，救下其上的所有人，每人上船 $1$ 分钟，船原路返回，达到大本营，每人下船 $0.5$ 分钟。假设原点与任意一个屋顶的连线不穿过其它屋顶。

inputFormat:
第一行，一个整数，表示屋顶数 $n$。

接下来依次有 $n$ 行输入，每一行上包含两个表示屋顶相对于大本营的平面坐标位置的实数（单位是米）、一个表示人数的整数，数之间以一个空格分开。

outputFormat: 一行，救援需要的总时间，精确到分钟（向上取整）。


title: 药房管理

description: 对药品的管理是其中的一项重要内容。现在药房的管理员希望使用计算机来帮助他管理。假设对于任意一种药品，每天开始工作时的库存总量已知，并且一天之内不会通过进货的方式增加。每天会有很多病人前来取药，每个病人希望取走不同数量的药品。如果病人需要的数量超过了当时的库存量，药房会拒绝该病人的请求。管理员希望知道每天会有多少病人没有取上药。

inputFormat:
共 $3$ 行，第一行是每天开始时的药品总量 $m$。

第二行是这一天取药的人数 $n(0<n \le 100)$。

第三行共有 $n$ 个数，分别记录了每个病人希望取走的药品数量（按照时间先后的顺序）。

outputFormat: 只有 $1$ 行，为这一天没有取上药品的人数。


title: 统计满足条件的 4 位数

description: 给定若干个四位数，求出其中满足以下条件的数的个数：个位数上的数字减去千位数上的数字，再减去百位数上的数字，再减去十位数上的数字的结果大于零。

inputFormat: 输入为两行，第一行为四位数的个数 $n$，第二行为 $n$ 个的四位数。$(n \le 100)$。

outputFormat: 输出为一行，包含一个整数，表示满足条件的四位数的个数。


title: 求分数序列和

description: 有一个分数序列 $\dfrac{q_{1}}{p_{1}},\dfrac{q_{2}}{p_{2}},\dfrac{q_{3}}{p_{3}},\dfrac{q_{4}}{p_{4}},\dfrac{q_{5}}{p_{5}},...$，其中 $q_{i+1}=q_{i}+p_{i}, p_{i+1}=q_{i},p_{1}=1,q_{1}=2$。比如这个序列前  $6$ 项分别是 $\dfrac{2}{1},\dfrac{3}{2},\dfrac{5}{3},\dfrac{8}{5},\dfrac{13}{8},\dfrac{21}{13}$。求这个分数序列的前 $n$ 项之和。

inputFormat: 输入一行一个正整数 $n(n\leq 30)$。

outputFormat: 输出一行一个浮点数，表示分数序列前 $n$ 项的和，精确到小数点后 $4$ 位。


title: 计算分数加减表达式的值

description:
$S_n=\frac{1}{1}-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\frac{1}{6}+...+(-1)^{n-1}\times\frac{1}{n}$。

输入一个整数 $n$，求 $S_n$。

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

outputFormat: 输出为一行，为 $S_n$ 的值，结果保留小数点后 $4$ 位小数。


title: 余数相同问题

description:
已知三个正整数 $a$，$b$，$c$。现有一个大于 $1$ 的整数 $x$，将其作为除数分别除 $a$，$b$，$c$，得到的余数相同。

请问满足上述条件的 $x$ 的最小值是多少？数据保证 $x$ 有解。

inputFormat: 一行，三个不大于 $1000000$ 的正整数 $a$，$b$，$c$，两个整数之间用一个空格隔开。

outputFormat: 一个整数，即满足条件的 $x$ 的最小值。


title: 分苹果

description: 把一堆苹果分给 $n$ 个小朋友，要使每个人都能拿到苹果，而且每个人拿到的苹果数都不同的话，这堆苹果至少应该有多少个？

inputFormat: 一个不大于 $1000$ 的正整数 $n$，代表小朋友人数。

outputFormat: 一个整数，表示满足条件的最少苹果个数。


title: 求小数的某一位

description: 分数 $\dfrac{a}{b}$ 化为小数后，小数点后第 $n$ 位的数字是多少？

inputFormat: 三个正整数 $a$，$b$，$n$，相邻两个数之间用单个空格隔开。$0<a\le b\le100$，$1 \le n \le 10000$。

outputFormat: 一个数字。


title: 计算星期几

description: 假设今天是星期日，那么过 $a$ 的 $b$ 次方天之后是星期几？

inputFormat: 两个正整数 $a, b$，中间用单个空格隔开。$1 \le a \le 100$，$1 \le b \le 10000$。

outputFormat:
一个字符串，代表过 $a$ 的 $b$ 次方天之后是星期几。

其中，`Monday` 是星期一，`Tuesday` 是星期二，`Wednesday` 是星期三，`Thursday` 是星期四，`Friday` 是星期五，`Saturday` 是星期六，`Sunday` 是星期日。

samples:
3 2000
Tuesday


title: 幂的末尾

description: 幂 $a^b$ 的末 $3$ 位数是多少？

outputFormat: 从高位到低位输出幂的末三位数字，中间无分隔符。若幂本身不足三位，在前面补零。


title: 球弹跳高度的计算

description:
一球从某一高度落下（整数，单位米），每次落地后反跳回原来高度的一半，再落下。

编程计算气球在第 $10$ 次落地时，共经过多少米？第 $10$ 次反弹多高？

inputFormat: 输入一个整数 $h$，表示球的初始高度。

outputFormat:
输出包含两行：

第 $1$ 行：到球第 $10$ 次落地时，一共经过的米数。

第 $2$ 行：第 $10$ 次弹跳的高度。

注意：结果可能是实数，结果用 double 类型保存。

提示：输出时不需要对精度特殊控制，用 `cout<<ANSWER`，或者 `printf("%g",ANSWER)` 即可。


title: 角谷猜想

description:
所谓角谷猜想，是指对于任意一个正整数，如果是奇数，则乘 $3$ 加 $1$，如果是偶数，则除以 $2$，得到的结果再按照上述规则重复处理，最终总能够得到 $1$。如，假定初始整数为 $5$，计算过程分别为 $16$ 、 $8$ 、 $4$ 、 $2$ 、 $1$。

程序要求输入一个整数，将经过处理得到 $1$ 的过程输出来。

outputFormat: 从输入整数到 $1$ 的步骤，每一步为一行，每一部中描述计算过程。最后一行输出 `End`。如果输入为 $1$，直接输出 `End`。


title: 含 k 个 3 的数

description: 输入两个正整数 $m$ 和 $k$，其中 $1 \lt m \leq 10^{15}$，$1 \lt k \leq 15$ ，判断 $m$ 是否恰好含有 $k$ 个 $3$，如果满足条件，则输出 `YES`，否则，输出 `NO`。

inputFormat: 输入一行，为两个整数 $m,k$，中间用单个空格间隔。

outputFormat: 满足条件，则输出 `YES`，否则，输出 `NO`。


title: 求出 e 的值

description: 利用公式 $e=1+1/1!+1/2!+1/3!+ \cdots +1/n!$，求 $e$ 的值，要求保留小数点后 $10$ 位。

inputFormat: 输入只有一行，该行包含一个整数 $n$，表示计算 $e$ 时累加到 $1/n!$。

outputFormat: 输出只有一行，该行包含计算出来的 $e$ 的值，要求打印小数点后 $10$ 位。


title: 计算多项式的值

description: 假定多项式的形式为 $x^n+x^{(n-1)}+$ … $+x^2+x+1$，请计算给定单精度浮点数 $x$ 和正整数 $n$ 值的情况下这个多项式的值。多项式的值精确到小数点后两位，保证最终结果在 double 范围内。

inputFormat: 输入仅一行，包括 $x$ 和 $n$，用单个空格隔开。

outputFormat: 输出一个实数，即多项式的值，精确到小数点后两位。保证最终结果在 double 范围内。

hint: $x$ 在 double 范围内，$n \le 1000000$。


title: 与 7 无关的数

description: 一个正整数，如果它能被 $7$ 整除，或者它的十进制表示法中某一位上的数字为 $7$，则称其为与 $7$ 相关的数。现求所有小于等于 $n(n<100)$ 与 $7$ 无关的正整数的平方和。

inputFormat: 输入为一行，正整数 $n(n<100)$。

outputFormat: 输出一行，包含一个整数，即小于等于 $n$ 的所有与 $7$ 无关的正整数的平方和。


title: 数字统计

description:
请统计某个给定范围 $[L,R]$ 的所有整数中，数字 $2$ 出现的次数。

比如给定范围 $[2,22]$，数字 $2$ 在数 $2$ 中出现了 $1$ 次，在数 $12$ 中出现 $1$ 次，在数 $20$ 中出现 $1$ 次，在数 $21$ 中出现 $1$ 次，在数 $22$ 中出现 $2$ 次，所以数字 $2$ 在该范围内一共出现了 $6$ 次。

inputFormat: 输入共 $1$ 行，为两个正整数 $L$ 和 $R$，之间用一个空格隔开。

outputFormat: 输出共 $1$ 行，表示数字 $2$ 出现的次数。


title: 画矩形

description:
根据输入的四个参数：$a,b,c,f$ 参数，画出对应的矩形。

前两个参数 $a,b$ 为整数，依次代表矩形的高和宽；

第三个参数 $c$ 是一个字符，表示用来填充的矩形符号；

第四个参数 $f$ 为整数，$0$ 代表空心，否则代表实心。

具体例子请见样例。

inputFormat: 第一行：a,b,c,f。

outputFormat: 一个矩形。

hint:
数据范围：

$3 \le a \le 100$。

$5 \le b \le 100$。

保证 $c$ 是一个可见的字符（ASCII 码在 $[33,126]$ 内）。

$0 \le f \le 1$。


title: 质因数分解

description: 已知正整数 $n$ 是两个不同的质数的乘积，试求出较大的那个质数。

inputFormat: 输入只有一行，包含一个正整数 $n$（$6<n<10^9$）。

outputFormat: 输出只有一行，包含一个正整数 $p$，即较大的那个质数。


title: 第 n 小的质数

description: 输入一个正整数 $n$，求正整数范围中第 $n$ 小的质数。

inputFormat: 一个不超过 $30000$ 的正整数 $n$。

outputFormat: 第 $n$ 小的质数。


title: 不定方程求解

description: 给定正整数 $a$，$b$，$c$。求不定方程 $ax+by=c$ 关于未知数 $x$ 和 $y$ 的所有非负整数解组数。

inputFormat: 一行，包含三个正整数 $a$，$b$，$c$，两个整数之间用单个空格隔开。每个数均不大于 $1000$。

outputFormat: 一个整数，即不定方程的非负整数解组数。


title: 与指定数字相同的数的个数

description: 输出一个整数序列中与指定数字相同的数的个数。

inputFormat:
输入包含三行：

第一行为 $n$，表示整数序列的长度（$n\le100$）；

第二行为 $n$ 个整数，整数之间以一个空格分开；

第三行包含一个整数，为指定的整数 $m$。

outputFormat: 输出为 $n$ 个数中与 $m$ 相同的数的个数。


title: 计算书费

description:
下面是一个图书的单价表：
1. 计算概论 28.9 元/本
2. 数据结构与算法 32.7 元/本
3. 数字逻辑 45.6元/本
4. C++程序设计教程 78 元/本
5. 人工智能 35 元/本
6. 计算机体系结构 86.2 元/本
7. 编译原理 27.8元/本
8. 操作系统 43 元/本
9. 计算机网络 56 元/本
10. JAVA程序设计 65 元/本

依次给定每种图书购买的数量，编程计算应付的总费用。

inputFormat:
输入一行，含 $10$ 个非负整数，每两个整数之间有一个空格。

第 $i$ 个整数表示要购买上述第 $i$ 种图书的数量（数量不超过 $100$，以本为单位，$i$ 分别为 $1,2,3, \cdots ,10$）。

outputFormat: 输出一行，包含一个实数，表示应付的总费用。精确到小数点后一位。


title: 数组逆序重存放

description: 将一个数组中的值按逆序重新存放。例如，原来的顺序为 $8,6,5,4,1$。要求改为 $1,4,5,6,8$。

inputFormat: 输入为两行：第一行数组中元素的个数 $n$（$1 \lt n \le 100$)，第二行是 $n$ 个整数，每两个整数之间用空格分隔。

outputFormat: 输出为一行：输出逆序后数组的整数，每两个整数之间用空格分隔。


title: 年龄与疾病

description: 某医院进行一项研究，想知道某项疾病是否与年龄有关。因此对以往的诊断记录进行整理，统计 0-18 、 19-35 、 36-60、 61 及以上这四个年龄段的患者人数占总患者人数的比例。

inputFormat:
输入共 $2$ 行。

第一行包含一个整数 $N$（$0<n \le 100$），表示总患者人数。

第二行包含 $N$ 个整数，代表这 $N$ 个患者就诊时的年龄。

outputFormat:
输出共 $4$ 行。

第 $1$ 行包含一个百分数，这个百分数保留小数点后 $2$ 位，代表 $0-18$ 岁这个年龄段的患者人数占总患者人数的比例。

第 $2$ 行包含一个百分数，这个百分数保留小数点后 $2$ 位，代表 $19-35$ 岁这个年龄段的患者人数占总患者人数的比例。

第 $3$ 行包含一个百分数，这个百分数保留小数点后 $2$ 位，代表 $36-60$ 岁这个年龄段的患者人数占总患者人数的比例。

第 $4$ 行包含一个百分数，这个百分数保留小数点后 $2$ 位，代表 $61$ 岁及以上这个年龄段的患者人数占总患者人数的比例。


title: 向量点积计算

description:
在线性代数、计算几何中，向量点积是一种十分重要的运算。

给定两个 $n$ 维向量 $a=(a_1,a_2, \cdots ,a_n)$ 和 $b=(b_1,b_2, \cdots ,b_n)$，求点积 $a$ · $b=a_1b_1+a_2b_2+ \cdots +a_nb_n$。

inputFormat:
第一行是一个整数 $n$。$1 \le n \le 1000$。

第二行包含 $n$ 个整数 $a_1,a_2, \cdots ,a_n$。

第三行包含 $n$ 个整数 $b_1,b_2, \cdots ,b_n$。

相邻整数之间用单个空格隔开。每个整数的绝对值都不超过 $1000$。

outputFormat: 一个整数，即两个向量的点积结果。


title: 开关灯

description: 假设有 $N$ 盏灯（$N$ 为不大于 $5000$ 的正整数），从 $1$ 到 $N$ 按顺序依次编号，初始时全部处于开启状态；第一个人（$1$ 号）将灯全部关闭，第二个人（$2$ 号）将编号为 $2$ 的倍数的灯打开，第三个人（$3$ 号）将编号为 $3$ 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和 $3$ 号一样，将凡是自己编号倍数的灯做相反处理。问当第 $N$ 个人操作完之后，有哪些灯是关闭着的？

inputFormat: 输入为一行，一个整数 $N$，为灯的数量。

outputFormat: 输出为一行，按顺序输出关着的灯的编号。编号与编号之间间隔一个空格。


title: 查找特定的值

description: 在一个序列（下标从 $0$ 开始）中查找一个给定的值，输出第一次出现的位置。

inputFormat:
第一行包含一个正整数 $n$，表示序列中元素个数。$1 \le n \le 10000$。

第二行包含 $n$ 个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。元素的绝对值不超过 $10000$。

第三行包含一个整数 $x$，为需要查找的特定值。$x$ 的绝对值不超过 $10000$。

outputFormat: 若序列中存在 $x$，输出 $x$ 第一次出现的下标；  否则输出 `-1`。


title: 不与最大数相同的数字之和

description: 输出一个整数数列中不与最大数相同的数字之和。

inputFormat:
输入分为两行：

第一行为 $N(N$ 为接下来数的个数，$N \le 100)$；

第二行为 $N$ 个整数，数与数之间以一个空格分开，每个整数的范围是 $-1000,000$ 到 $1000,000$。

outputFormat: 输出为 $N$ 个数中除去最大数其余数字之和。


title: 白细胞计数

description:
医院采样了某临床病例治疗期间的白细胞数量样本 $n$ 份，用于分析某种新抗生素对该病例的治疗效果。为了降低分析误差，要先从这 $n$ 份样本中去除一个数值最大的样本和一个数值最小的样本，然后将剩余 $n-2$ 个有效样本的平均值作为分析指标。同时，为了观察该抗生素的疗效是否稳定，还要给出该平均值的误差，即所有有效样本（即不包括已扣除的两个样本）与该平均值之差的绝对值的最大值。

现在请你编写程序，根据提供的 $n$ 个样本值，计算出该病例的平均白细胞数量和对应的误差。

inputFormat:
输入的第一行是一个正整数 $n$（$2<n \le 300$），表明共有 $n$ 个样本。

以下共有 $n$ 行，每行为一个浮点数，为对应的白细胞数量，其单位为 $10^9/L$。数与数之间以一个空格分开。

outputFormat: 输出为两个浮点数，中间以一个空格分开。分别为平均白细胞数量和对应的误差，单位也是 $10^9/L$。计算结果需保留到小数点后 $2$ 位。


title: 直方图

description:
给定一个非负整数数组，统计里面每一个数的出现次数。我们只统计到数组里最大的数。

假设 $Fmax（Fmax \le 100000）$是数组里最大的数，那么我们只统计 $\{0,1,2 \ldots Fmax \}$ 里每个数出现的次数。

inputFormat:
第一行 $n$ 是数组的大小。$1 \le n \le 100000$。

紧接着一行是数组的 $n$ 个元素。

outputFormat:
按顺序输出每个数的出现次数，一行一个数。如果没有出现过，则输出 $0$。

对于例子中的数组，最大的数是 $3$，因此我们只统计 $\{0,1,2,3\}$ 的出现频数。


title: 最长平台

description:
对于一个数组，其连续的相同段叫做一个平台，例如，在 $1$，$2$，$2$，$3$，$3$，$3$，$4$，$5$，$5$，$6$ 中 $1$，$2-2$，$3-3-3$，$4$，$5-5$，$6$ 都是平台。

编写一个程序，接收一个数组，找出最长的平台。在上面的例子中 $3-3-3$ 就是最长的平台。

inputFormat:
第一行有一个整数 $n$，为数组元素的个数。（$1 \le n \le 100$）

第二行有 $n$ 个整数，整数之间以一个空格分开，整数 $k$ 范围（$0<k<2000$）。

outputFormat: 输出最长平台的长度。


title: 整数去重

description: 给定含有 $n$ 个整数的序列，要求对这个序列进行去重操作。所谓去重，是指对这个序列中每个重复出现的数，只保留该数第一次出现的位置，删除其余位置。

inputFormat:
输入包含两行：

第一行包含一个正整数 $n$（$1 \le n \le 20000$），表示第二行序列中数字的个数；

第二行包含 $n$ 个整数，整数之间以一个空格分开。每个整数大于等于 $10$ 、小于等于 $100$。

outputFormat: 输出只有一行，按照输入的顺序输出其中不重复的数字，整数之间用一个空格分开。


title: 矩阵交换行

description: 给定一个 $5 \times 5$ 的矩阵(数学上，一个 $r \times c$ 的矩阵是一个由 $r$ 行 $c$ 列元素排列成的矩形阵列)，将第 $n$ 行和第 $m$ 行交换，输出交换后的结果。

inputFormat:
输入共 $6$ 行，前 $5$ 行为矩阵的每一行元素,元素与元素之间以一个空格分开。

第 $6$ 行包含两个整数 $m$、$n$，以一个空格分开（$1 \le m,n \le 5$）。

outputFormat: 输出交换之后的矩阵，矩阵的每一行元素占一行，元素之间以一个空格分开。


title: 同行列对角线的格

description:
输入三个自然数 $N$，$i$，$j$（$1 \le i \le n$，$1 \le j \le n$），输出在一个 $N \times N$ 格的棋盘中（行列均从 $1$ 开始编号），与格子 $(i$，$j)$ 同行、同列、同一对角线的所有格子的位置。

如：$n=4$，$i=2$，$j=3$ 表示了棋盘中的第二行第三列的格子，

当 $n=4$，$i=2$，$j=3$ 时，输出的结果是：

$(2,1)(2,2)(2,3)(2,4)$ 同一行上格子的位置。

$(1,3)(2,3)(3,3)(4,3)$ 同一列上格子的位置。

$(1,2)(2,3)(3,4)$ 左上到右下对角线上的格子的位置。

$(4,1)(3,2)(2,3)(1,4)$ 左下到右上对角线上的格子的位置。

inputFormat: 一行，三个自然数 $N$，$i$，$j$，相邻两个数之间用单个空格隔开 $(1 \le N \le 10)$。

outputFormat:
第一行：从左到右输出同一行格子位置；

第二行：从上到下输出同一列格子位置；

第三行：从左上到右下输出同一对角线格子位置；

第四行：从左下到右上输出同一对角线格子位置。

其中每个格子位置用如下格式输出：$(x,y)$，$x$ 为行号，$y$ 为列号，采用英文标点，中间无空格。相邻两个格子位置之间用单个空格隔开。


title: 计算矩阵边缘元素之和

description:
输入一个整数矩阵，计算位于矩阵边缘的元素之和。

所谓矩阵边缘的元素，就是第一行和最后一行的元素以及第一列和最后一列的元素。

inputFormat:
第 $1$ 行包含两个整数，分别为行数 $m$ 和列数 $n$，两个整数之间空格隔开。

第 $2$ 行开始有 $m$ 行数据，每行包含 $n$ 个整数，整数之间空格隔开。

outputFormat: 对应矩阵的边缘元素和。

hint: $1 \le m,n \le 100$。保证答案在 int 范围内。


title: 计算鞍点

description:
给定一个 $5 \times 5$ 的矩阵，每行只有一个最大值，每列只有一个最小值，寻找这个矩阵的鞍点。鞍点指的是矩阵中的一个元素，它是所在行的最大值，并且是所在列的最小值。

例如：在下面的例子中，第 $4$ 行第 $1$ 列的元素就是鞍点，值为 $8$。

```
11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8  6 4 7 2
15 10 11 20 25
```

inputFormat: 输入包含一个 $5$ 行 $5$ 列的矩阵。

outputFormat: 如果存在鞍点，输出鞍点所在的行、列及其值，如果不存在，输出 `not found`。


title: 图像相似度

description:
给出两幅相同大小的黑白图像（用 $0-1$ 矩阵）表示，求它们的相似度。

说明：若两幅图像在相同位置上的像素点颜色相同，则称它们在该位置具有相同的像素点。两幅图像的相似度定义为相同像素点数占总像素点数的百分比。

inputFormat:
第一行包含两个整数 $m$ 和 $n$，表示图像的行数和列数，中间用单个空格隔开。$1 \le m \le 100,1 \le n \le 100$。

之后 $m$ 行，每行 $n$ 个整数 $0$ 或 $1$，表示第一幅黑白图像上各像素点的颜色。相邻两个数之间用单个空格隔开。

之后 $m$ 行，每行 $n$ 个整数 $0$ 或 $1$，表示第二幅黑白图像上各像素点的颜色。相邻两个数之间用单个空格隔开。

outputFormat: 一个实数，表示相似度（以百分比的形式给出），精确到小数点后两位。


title: 矩阵加法

description: 输入两个 $n$ 行 $m$ 列的矩阵 $A$ 和 $B$，输出它们的和 $A+B$，矩阵加法的规则是两个矩阵中对应位置的值进行加和，具体参照样例。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，表示矩阵的行数和列数 $(1 \le n \le 100$，$1 \le m \le 100)$。

接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $A$ 的元素。

接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $B$ 的元素。

相邻两个整数之间用单个空格隔开，每个元素均在 $1 \sim 1000$ 之间。

outputFormat: $n$ 行，每行 $m$ 个整数，表示矩阵加法的结果。相邻两个整数之间用单个空格隔开。


title: 矩阵乘法

description: 计算两个矩阵的乘法。$n \times m$ 阶的矩阵 $A$ 乘以 $m \times k$ 阶的矩阵 $B$ 得到的矩阵 $C$ 是 $n \times k$ 阶的，且 $C[i][j]=A[i][0] \times B[0][j]+A[i][1] \times B[1][j]+$ …… $+A[i][m-1] \times B[m-1][j](C[i][j]$ 表示 $C$ 矩阵中第 $i$ 行第 $j$ 列元素）。

inputFormat:
第一行为 $n,m,k$，表示 $A$ 矩阵是 $n$ 行 $m$ 列，$B$ 矩阵是 $m$ 行 $k$ 列，$n,m,k$ 均小于 $100$。

然后先后输入 $A$ 和 $B$ 两个矩阵，$A$ 矩阵 $n$ 行 $m$ 列，$B$ 矩阵 $m$ 行 $k$ 列，矩阵中每个元素的绝对值不会大于 $1000$。

outputFormat: 输出矩阵 $C$，一共 $n$ 行，每行 $k$ 个整数，整数之间以一个空格分开。


title: 矩阵转置

description: 输入一个 $n$ 行 $m$ 列的矩阵 $A$，输出它的转置 $A^T$。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，表示矩阵 $A$ 的行数和列数。$1 \le n \le 100$，$1 \le m \le 100$。

接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $A$ 的元素。相邻两个整数之间用单个空格隔开，每个元素均在 $1 \sim 1000$ 之间。

outputFormat: $m$ 行，每行 $n$ 个整数，为矩阵 $A$ 的转置。相邻两个整数之间用单个空格隔开。


title: 图像旋转

description: 输入一个 $n$ 行 $m$ 列的黑白图像，将它顺时针旋转 $90$ 度后输出。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，表示图像包含像素点的行数和列数。$1 \le n \le 100$，$1 \le m \le 100$。

接下来 $n$ 行，每行 $m$ 个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在 $0 \sim 255$ 之间。

outputFormat: $m$ 行，每行 $n$ 个整数，为顺时针旋转 $90$ 度后的图像。相邻两个整数之间用单个空格隔开。


title: 图像模糊处理

description:
给定 $n$ 行 $m$ 列的图像各像素点的灰度值，要求用如下方法对其进行模糊化处理：

$1.$ 四周最外侧的像素点灰度值不变；

$2.$ 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均（舍入到最接近的整数）。

inputFormat:
第一行包含两个整数 $n$ 和 $m$，表示图像包含像素点的行数和列数。$1 \le n \le 100$，$1 \le m \le 100$。

接下来 $n$ 行，每行 $m$ 个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在 $0$ ∼ $255$ 之间。

outputFormat: $n$ 行，每行 $m$ 个整数，为模糊处理后的图像。相邻两个整数之间用单个空格隔开。


title: 统计数字字符个数

description: 输入一行字符，统计出其中数字字符的个数。

inputFormat: 一行字符串，总长度不超过 $255$。

outputFormat: 输出为 $1$ 行，输出字符串里面数字字符的个数。


title: 找第一个只出现一次的字符

description: 给定一个只包含小写字母的字符串，请你找到第一个仅出现一次的字符。如果没有，输出 `no`。

inputFormat: 一个字符串，长度小于 $1100$。

outputFormat: 输出第一个仅出现一次的字符，若没有则输出 `no`。

samples: abcabd c

samples: aabbcc no


title: 基因相关性

description:
为了获知基因序列在功能和结构上的相似性，经常需要将几条不同序列的 DNA 进行比对，以判断该比对的 DNA 是否具有相关性。

现比对两条长度相同的 DNA 序列。首先定义两条 DNA 序列相同位置的碱基为一个碱基对，如果一个碱基对中的两个碱基相同的话，则称为相同碱基对。接着计算相同碱基对占总碱基对数量的比例，如果该比例大于等于给定阈值时则判定该两条 DNA 序列是相关的，否则不相关。

inputFormat: 有三行，第一行是用来判定出两条 DNA 序列是否相关的阈值，随后 $2$ 行是两条 DNA 序列（长度不大于 $500$）。

outputFormat: 若两条 DNA 序列相关，则输出 `yes`，否则输出`no`。


title: 石头剪子布

description:
石头剪子布，是一种猜拳游戏。起源于中国，然后传到日本、朝鲜等地，随着亚欧贸易的不断发展它传到了欧洲，到了近现代逐渐风靡世界。简单明了的规则，使得石头剪子布没有任何规则漏洞可钻，单次玩法比拼运气，多回合玩法比拼心理博弈，使得石头剪子布这个古老的游戏同时用于“意外”与“技术”两种特性，深受世界人民喜爱。

游戏规则：石头打剪刀，布包石头，剪刀剪布。

现在，需要你写一个程序来判断石头剪子布游戏的结果。

inputFormat:
第一行是一个整数 $N$，表示一共进行了 $N$ 次游戏。$1 \le N \le 100$。

接下来 $N$ 行的每一行包括两个字符串，表示游戏参与者 Player1，Player2 的选择（石头、剪子或者是布）：
S1,S2

字符串之间以空格隔开 S1 S2 只可能取值在 `Rock`,`Scissors`,`Paper` (大小写敏感）中。

outputFormat: 输出包括 $N$ 行，每一行对应一个胜利者（Player1 或者 Player2），或者游戏出现平局，则输出 `Tie`。


title: 输出亲朋字符串

description: 亲朋字符串定义如下：给定字符串 $s$ 的第一个字符的 ASCII 值加第二个字符的 ASCII 值，得到第一个亲朋字符；$s$ 的第二个字符加第三个字符得到第二个亲朋字符；依此类推。注意：亲朋字符串的最后一个字符由 $s$ 的最后一个字符 ASCII 值加 $s$ 的第一个字符的 ASCII 值。

inputFormat: 输入一行，一个长度大于等于 $2$，小于等于 $100$ 的字符串。

outputFormat: 输出一行，为变换后的亲朋字符串。输入保证变换后的字符串只有一行。


title: 配对碱基链

description:
脱氧核糖核酸（DNA）由两条互补的碱基链以双螺旋的方式结合而成。

而构成 DNA 的碱基共有 $4$ 种：

- 分别为腺嘌呤（$A$）

- 鸟嘌呤（$G$）

- 胸腺嘧啶（$T$）

- 胞嘧啶（$C$）

我们知道，在两条互补碱基链的对应位置上，腺嘌呤总是和胸腺嘧啶配对，鸟嘌呤总是和胞嘧啶配对。

你的任务就是根据一条单链上的碱基序列，给出对应的互补链上的碱基序列。

inputFormat:
一个字符串，表示一条碱基链。

这个字符串只含有大写字母 $A$ 、 $T$ 、 $G$ 、 $C$，分别表示腺嘌呤、胸腺嘧啶、鸟嘌呤和胞嘧啶。

字符串长度不超过 $255$。

outputFormat: 一个只含有大写字母 $A$ 、 $T$ 、 $G$ 、 $C$ 的字符串，为与输入的碱基链互补的碱基链。


title: 密码翻译

background: $\text{Update on 2023.01.21 11:33:00}$：目前数据已经修复，对于题解中提到的 `@` 应视作 `A` 的问题经调查发现为一个错误，现在已经修复。

description:
在情报传递过程中，为了防止情报被截获，往往需要对情报用一定的方式加密。我们给出一种最简单的加密方法，对给定的一个字符串，把其中从 $\texttt{a} \sim \texttt{y}$，$\texttt{A} \sim \texttt{Y}$ 的字母用其后继字母替代，把 $\texttt{z}$ 和 $\texttt{Z}$ 用 $\texttt{a}$ 和 $\texttt{A}$ 替代，其他非字母字符不变。请根据该加密规则将输入的密码进行解密。

提示：这里需要进行**解密**操作，而不是**加密**。

inputFormat: 一行，加密后的字符串，长度不多于 $10000$ 个字符。

outputFormat: 一行，将密码解密后的字符串。

samples:
Ifmmp !  Ipx  bsf  zpv!
Hello !  How  are  you!


title: 加密的病历单

description:
小英是药学专业大三的学生，暑假期间获得了去医院药房实习的机会。

在药房实习期间，小英扎实的专业基础获得了医生的一致好评，得知小英在计算概论中取得过好成绩后，主任又额外交给她一项任务，解密抗战时期被加密过的一些伤员的名单。

经过研究，小英发现了如下加密规律（括号中是一个“**原文 → 密文**”的例子）

1. 原文中所有的字符都在字母表中被循环左移了三个位置（$\text{bcd} \to \text{yza}$）

2. 逆序存储（$\text{abcd} \to \text{dcba}$）

3. 大小写反转（$\text{abXY} \to \text{ABxy}$）

现在给出一个**加密**的字符串，请你将其**解密**。

inputFormat: 一个加密的字符串。（长度小于 $50$ 且只包含大小写字母）

outputFormat: 输出解密后的字符串。

samples: GSOOWFASOq Trvdizrrvj


title: 整理药名

description:
医生在书写药品名的时候经常不注意大小写，格式比较混乱。现要求你写一个程序将医生书写混乱的药品名整理成统一规范的格式，即药品名的第一个字符如果是字母要大写，其他字母小写。

如将 ASPIRIN 、 aspirin 整理成 Aspirin。

inputFormat:
第一行一个数字 $n$，表示有 $n$ 个药品名要整理，$n$ 不超过 $100$。

接下来 $n$ 行，每行一个单词，长度不超过 $20$，表示医生手书的药品名。

药品名由字母、数字和 - 组成。

outputFormat: $n$ 行，每行一个单词，对应输入的药品名的规范写法。

samples:
4
AspiRin
cisapride
2-PENICILLIN
Cefradine-6

samples:
Aspirin
Cisapride
2-penicillin
Cefradine-6


title: 验证子串

description: 输入两个字符串，验证其中一个串是否为另一个串的子串。

inputFormat: 两行，每行一个字符串。

outputFormat:
若第一个串 $s_1$ 是第二个串 $s_2$ 的子串，则输出`(s1) is substring of (s2)`；

否则，若第二个串 $s_2$ 是第一个串 $s_1$ 的子串，输出`(s2) is substring of (s1)`；

否则，输出 `No substring`。

hint: 对于 $100 \%$ 的数据，字符串长度在 $20$ 以内。


title: 删除单词后缀

description: 给定一个单词，如果该单词以 `er` 、 `ly` 或者 `ing` 后缀结尾，则删除该后缀（题目保证删除后缀后的单词长度不为 $0$），否则不进行任何操作。

inputFormat: 输入一行，包含一个单词（单词中间没有空格，每个单词最大长度为 $32$）。

outputFormat: 输出按照题目要求处理后的单词。

samples: referer refer


title: 单词的长度

description:
输入一行单词序列，相邻单词之间由 $1$ 个或多个空格间隔，请对应地计算各个单词的长度。

注意：如果有标点符号（如连字符，逗号），标点符号算作与之相连的词的一部分。没有被空格间开的符号串，都算作单词。

inputFormat: 一行单词序列，最少 $1$ 个单词，最多 $300$ 个单词，单词之间用至少 $1$ 个空格间隔。单词序列总长度不超过 $1000$。

outputFormat: 依次输出对应单词的长度，之间以逗号间隔。

samples: She was born in 1990-01-02  and  from Beijing city.


title: 最长最短单词

description:
输入 $1$ 行句子（不多于 $200$ 个单词，每个单词长度不超过 $100)$，只包含字母、空格、逗号和句号。单词由至少一个连续的字母构成，空格、逗号和句号都是单词间的间隔。

输出第 $1$ 个最长的单词和第 $1$ 个最短单词。

inputFormat: 输入数据：一行句子。

outputFormat:
输出数据：

第 $1$ 行，第一个最长的单词。

第 $2$ 行，第一个最短的单词。

samples: I am a student,i am studying Programming language C in Peking University.


title: 单词翻转

description: 小明同学写单词的时候喜欢反着写，比如 `hello` 他会写成 `olleh`。给出小明同学写的一个句子，请你将所有的单词复原。

inputFormat: 共一行，一个字符串表示句子，单词之间以空格分隔。

outputFormat: 每个单词一行。

hint: 句子长度不超过 $100$，仅包含小写字母和空格，不存在多余的空格。


title: 字符串 p 型编码

description: 给定一个完全由数字字符（'0','1','2',…,'9'）构成的字符串 str ，请写出 str 的 p 型编码串。例如：字符串 `122344111` 可被描述为 `1个1、2个2、1个3、2个4、3个1` ，因此我们说`122344111` 的 p 型编码串为 `1122132431` ；类似的道理，编码串 `101` 可以用来描述 `1111111111` ；`00000000000` 可描述为 `11个0`，因此它的p型编码串即为 `110` ；`100200300` 可描述为 `1个1、2个 0、1个2、2个0、1个3、2个0`，因此它的 p 型编码串为 `112012201320`。

inputFormat: 输入仅一行，包含字符串 str。每一行字符串最多包含 $1000$ 个数字字符。

outputFormat: 输出该字符串对应的 $p$ 型编码串。


title: 判断字符串是否为回文

description: 输入一个字符串，输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。

inputFormat: 输入一行字符串，长度小于 $100$。

outputFormat: 如果字符串是回文，输出 `yes`；否则，输出 `no`。

samples: abcdedcba yes


title: 最高分数的学生姓名

description: 输入学生的人数，然后再输入每位学生的分数和姓名，求获得最高分数的学生的姓名。

inputFormat:
第一行输入一个正整数 $N$（$N \le 100$），表示学生人数。

接着输入 $N$ 行，每行包括两个整数，代表分数姓名。

分数是一个非负整数，且小于等于 $100$；

姓名为一个连续的字符串，中间没有空格，长度不超过 $20$。

数据保证所有同学的姓名都不同，而且最高分只有一位同学。

outputFormat: 获得最高分数同学的姓名。

samples:
5
87 lilei
99 hanmeimei
97 lily
96 lucy
77 jim

hint: hanmeimei 的分数最高 $99$ 分。


title: 连续出现的字符

description: 给定一个字符串，在字符串中寻找第一个连续出现次数不低于 $k$ 次的字符。

inputFormat: $2$ 行。第 $1$ 行是 $k$；第 $2$ 行是仅包含大小写字母的字符串。

outputFormat: 字符串中第一个连续出现次数不低于 `k` 次的字符。如果没有符合条件的字符，输出 `No`。

hint: $1\leq k\leq1000$，字符串长度不超过 $1000$。


title: 求正整数 2 和 n 之间的完全数

description:
求正整数 $2$ 和 $n$ 之间的完全数（一行一个数）。

完全数：对于一个自然数，所有比它小的所有因数之和，等于它本身，它就是个完全数。如 $6=1+2+3$。

outputFormat: 一行一个数，按由小到大的顺序。


title: 素数个数

description: 编程求 $2$ ～ $n(n$ 为大于 $2$ 的正整数）中有多少个素数。

outputFormat: 素数个数。


title: 最大数 max(x,y,z)

description:
已知：

$m=\dfrac{\max(a,b,c)}{\max(a+b,b,c) \times \max(a,b,b+c)}$

输入三个整数 $a$，$b$，$c$，求 $m$。

把求三个数的最大数 $\max(x,y,z)$ 分别定义成函数和过程来做。

inputFormat: 输入只有一个行三个整数，分别为 $a, b, c$。

outputFormat: 输出一行一个小数，为答案，保留三位小数。

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

对于全部的测试点，保证 $|a|,|b|,|c| \leq 50$。换句话说，$a,b,c$ 都在 $-50$ 到 $50$ 之间。

测试数据保证，分式的分母不为 $0$。


title: 简单算术表达式求值

description:
两位正整数的简单算术运算（只考虑整数运算），算术运算为：

`+`，加法运算；

`-`，减法运算；

`*`，乘法运算；

`/`，整除运算；

`%`，取余运算。

算术表达式的格式为（运算符前后可能有空格）：

运算数运算符运算数。

请输出相应的结果。

inputFormat: 一行算术表达式。

outputFormat: 整型算数运算的结果（结果值不一定为 $2$ 位数，可能多于 $2$ 位或少于 $2$ 位）。


title: 甲流病人初筛

description: 目前正是甲流盛行时期，为了更好地进行分流治疗，医院在挂号时要求对病人的体温和咳嗽情况进行检查，对于体温超过 $37.5$ 度（含等于 $37.5$ 度）并且咳嗽的病人初步判定为甲流病人（初筛）。现需要统计某天前来挂号就诊的病人中有多少人被初筛为甲流病人。

inputFormat:
第一行是某天前来挂号就诊的病人数 $n$。$(n<200)$。

其后有 $n$ 行，每行是病人的信息，包括三个信息：姓名（字符串，不含空格，最多 $8$ 个字符）、体温（float）、是否咳嗽（整数，$1$ 表示咳嗽，$0$ 表示不咳嗽）。每行三个信息之间以一个空格分开。

outputFormat: 按输入顺序依次输出所有被筛选为甲流的病人的姓名，每个名字占一行。之后在输出一行，表示被筛选为甲流的病人数量。


title: 素数对

description: 定义两个相差为 $2$ 的素数称为素数对，如 $5$ 和 $7,17$ 和 $19$ 等，要求找出所有两个数均不大于 $n$ 的素数对。

inputFormat: 一个正整数 $n$。$1 \le n \le 10000$。

outputFormat: 所有小于等于 $n$ 的素数对。每对素数对输出一行，中间用单个空格隔开。若没有找到任何素数对，输出 `empty`。


title: 我家的门牌号

description:
我家住在一条短胡同里，这条胡同的门牌号从 $1$ 开始顺序编号。

若其余各家的门牌号之和减去我家门牌号的两倍，恰好等于 $n$，求我家的门牌号及总共有多少家。数据保证有唯一解。

outputFormat: 一行，包含两个正整数，分别是我家的门牌号及总共有多少家，中间用单个空格隔开。


title: 质数的和与积

description: 两个质数的和是 $S$，它们的积最大是多少？

inputFormat: 一个不大于 $10000$ 的正整数 $S$，为两个质数的和。

outputFormat: 一个整数，为两个质数的最大乘积。数据保证有解。


title: 单词替换

description: 输入一个字符串，以回车结束（字符串长度 $ \le 200$）。该字符串由若干个单词组成，单词之间用一个空格隔开，所有单词区分大小写。现需要将其中的某个单词替换成另一个单词，并输出替换之后的字符串。

inputFormat:
第 $1$ 行是包含多个单词的字符串 $s$；

第 $2$ 行是待替换的单词 $a($ 长度 $ \le 100)$；

第 $3$ 行是 $a$ 将被替换的单词 $b($ 长度 $ \le 100)$。

$s,a,b$ 最前面和最后面都没有空格。

outputFormat: 输出只有 $1$ 行，将 $s$ 中所有单词 $a$ 替换成 $b$ 之后的字符串。


title: 素数回文数的个数

description: 求 $11$ 到 $n$ 之间（包括 $n$），既是素数又是回文数的整数有多少个。

outputFormat: $11$ 到 $n$ 之间的素数回文数个数。

hint: 回文数指左右对称的数，如：$11$，$12121$。


title: 判决素数个数

description: 求 $X$，$Y$ 之间的素数个数（包括 $X$ 和 $Y$）。

inputFormat: 两个整数 $X$ 和 $Y$（$1 \le X,Y \le 1.1 \times 10^6$）。

outputFormat: 输出一个整数，表示 $X, Y$ 之间的素数个数（包括 $X$ 和 $Y$）。


title: 最大质因子序列

description: 任意输入两个正整数 $m,n$（$2\le m\le n\le5000$），依次输出 $m$ 到 $n$ 之间每个数的最大质因子（包括 $m$ 和 $n$；如果某个数本身是质数，则输出这个数自身）。

inputFormat: 一行，包含两个正整数 $m$ 和 $n$，其间以单个空格间隔。

outputFormat: 一行，每个整数的最大质因子，以逗号间隔。


title: 区间内的真素数

description:
找出正整数 $M$ 和 $N$ 之间（$N$ 不小于 $M$）的所有真素数。

真素数的定义：如果一个正整数 $P$ 为素数，且其反序也为素数，那么 $P$ 就为真素数。

例如，$11$，$13$ 均为真素数，因为 $11$ 的反序还是为 $11$，$13$ 的反序为 $31$ 也为素数。

inputFormat: 输入两个数 $M$ 和 $N$，空格间隔。

outputFormat: 按从小到大输出 $M$ 和 $N$ 之间（包括 $M$ 和 $N$）的真素数，逗号间隔。如果之间没有真素数，则输出 `No`。


title: 二进制分类

description:
若将一个正整数化为二进制数，在此二进制数中，我们将数字 $1$ 的个数多于数字 $0$ 的个数的这类二进制数称为 $A$ 类数，否则就称其为 $B$ 类数。

例如：

$(13)_{10}=(1101)_2$，其中 $1$ 的个数为 $3$，$0$ 的个数为 $1$，则称此数为 $A$ 类数；

$(10)_{10}=(1010)_2$，其中 $1$ 的个数为 $2$，$0$ 的个数也为 $2$，称此数为 $B$ 类数；

$(24)_{10}=(11000)_2$，其中 $1$ 的个数为 $2$，$0$ 的个数为 $3$，则称此数为 $B$ 类数；

程序要求：求出 1~n 之中（$1 \le n \le 1000$），全部 $A,B$ 两类数的个数。

inputFormat: 输入 $n$。

outputFormat: 一行，包含两个整数，分别是 $A$ 类数和 $B$ 类数的个数，中间用单个空格隔开。


title: 确定进制

description:
$6\ \times 9=42$ 对于十进制来说是错误的，但是对于 $13$ 进制来说是正确的。即 $6_{(13)}\ \times 9_{(13)}=42_{(13)}$，而 $42_{(13)}=4\ \times 13^1+2\ \times 13^0=54_{(10)}$。

你的任务是写一段程序读入三个整数 $p,q$ 和 $r$，然后确定一个进制 $B(2 \le B \le 16)$ 使得 $p\ \times q=r$。如果 $B$ 有很多选择，则输出最小的一个。

例如：$p=11,q=11,r=121$，则有 $11_{(3)}\ \times 11_{(3)}=121_{(3)}$，因为 $11_{(3)}=1\ \times 3^1+1\ \times 3^0=4_{(10)}$ 和 $121_{(3)}=1\ \times 3^2+2\ \times 3^1+1\ \times 3^0=16_{(10)}$。对于进制 $10,$ 有 $11_{(10)}\ \times 11_{(10)}=121_{(10)}$。这种情况下，应该输出 $3$。如果没有合适的进制，则输出 $0$。

inputFormat: 一行，包含三个整数 $p,q,r$，相邻两个整数之间用单个空格隔开。

outputFormat: 一个整数：即使得 $p \times q=r$ 成立的最小的 $B$。如果没有合适的 $B$，则输出 $0$。

hint: $p,q,r$ 的所有位都是数字，并且 $1 \le p,q,r \le 10^6$。


title: 求 1+2+3+...+N 的值

description: 用递归的方法求 $1+2+3+$ …… $+N$ 的值。

inputFormat: 输入 $N$。

outputFormat: 输出和。


title: 进制转换

description: 用递归算法将一个十进制整数 $X$（$1 \le X \le 10^9$）转换成任意进制数 $M$（$2\le M\le16$，$M$ 为整数）。

inputFormat: 一行两个数，第一个十进制整数 $X$，第二个为进制 $M$。

outputFormat: 输出结果。

hint:
**样例解释**。

将十进制 $31$ 转化为十六进制数。


title: 阿克曼（Ackermann）函数

description:
阿克曼（Ackermann）函数 $A(m,n)$ 中，$m, n$ 定义域是非负整数（$m \le 3$，$n \le 10$），函数值定义为：

$\mathit{akm}(m,n)=n+1$；（$m=0$ 时）。

$\mathit{akm}(m,n)=\mathit{akm}(m-1,1)$；（$m>0$、$n=0$ 时）。

$\mathit{akm}(m,n)=\mathit{akm}(m-1,\mathit{akm}(m,n-1))$；（$m,n>0$ 时）。

inputFormat: $m$ 和 $n$。

outputFormat: 函数值。


title: digit 函数

description: 在程序中定义一函数 $digit(n,k)$，它能分离出整数 $n$ 从右边数第 $k$ 个数字。

inputFormat: 正整数 $n$ 和 $k$。

outputFormat: 一个数字。


title: Hermite 多项式

description:
求 Hermite 多项式的值。

$$
h_n(x)=\left\{
\begin{aligned}
1&，&n=0\\
2x&，&n=1\\
2xh_{n-1}(x)-2(n-1)h_{n-2}(x)&，& n>1
\end{aligned}
\right.
$$

对给定的 $x$ 和正整数 $n$，求多项式的值。

inputFormat: 输入 $n$ 和 $x$ 。

outputFormat: 求多项式的值。


title: 求 f(x,n)

description:
已知 $f(x,n)=\sqrt{n+\sqrt{(n-1)+\sqrt{(n-2)+\sqrt{...+2+\sqrt{1+x}}}}}$。

计算 $f$ 的值。

inputFormat: 输入 $x$ 和 $n$。

outputFormat: 函数值，保留两位小数。


title: 再求 f(x,n)

description:
已知

$f(x,n)=\dfrac{x}{n+\dfrac{x}{(n-1)+\dfrac{x}{(n-2)+\dfrac{\vdots}{\cdots+\dfrac{x}{1+x}}}}}$。

用递归函数求解。

inputFormat: 第一个数是 $x$ 的值，第二个数是 $n$ 的值。（$x$ 为**实数**，$n$ 为整数）


title: An Extra Requirement

background: 由于 Codeforces [[1]](https://codeforces.com/contest/1610/problem/I) [[2]](https://codeforces.com/contest/1591/problem/F) 能从 Atcoder [[1]](https://atcoder.jp/contests/agc017/tasks/agc017_d) [[2]](https://atcoder.jp/contests/arc115/tasks/arc115_e) 搬题，于是出（搬）题人也从 Atcoder [[3]](https://atcoder.jp/contests/agc054/tasks/agc054_e) 搬了一道。

description:
对于一个长度为 $N$ 的排列 $P$，你可以进行若干次如下操作：选三个位置 $x,y,z(x<y<z)$，若 $P_y<\min\{P_x,P_z\}$ 或 $P_y>\max\{P_x,P_z\}$，那么可以删除 $P_y$。

统计存在一种删除方式，使得最后只剩下不超过两个数且 $P_1=A$ 的排列 $P$ 的个数。由于答案可能很大，你只需要输出个数模 $998244353$ 的结果即可。

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

接下来 $T$ 行，每行两个正整数 $N,A$，分别表示排列 $P$ 的长度和排列 $P$ 的第一个数。

outputFormat: 输出 $T$ 行，每行一个整数表示答案，对 $998244353$ 取模。


title: 【深进1.例1】求区间和

description: 给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和。

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

第二行，为 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$

第三行，为一个正整数 $m$ 。

接下来 $m$ 行，每行为两个正整数 $l_i,r_i$ ，满足 $1\le l_i\le r_i\le n$

outputFormat:
共 $m$ 行。

第 $i$ 行为第 $i$ 组答案的询问。

hint:
样例解释：第 1 到第 4 个数加起来和为 10。第 2 个数到第 3 个数加起来和为 5。

对于 $50\%$ 的数据：$n,m\le 1000$ ；

对于 $100\%$ 的数据：$1 \leq n,m\le 10^5$，$1 \leq a_i\le 10^4$。


title: [COCI2013-2014#5] OBILAZAK

description:
给出一棵有 $2^K-1$ 个节点的完全二叉树，遍历这棵树的规律如下：

- 起点是二叉树第一层的唯一一个节点。

- 如果当前节点的左孩子还没有记录到，那么就记录左孩子的编号并移动到左孩子处。

- 如果当前节点没有左孩子或者左孩子已经记录过，就记录当前节点的编号。

- 如果当前节点已经记录过，那么就记录右孩子的编号并移动到右孩子处。

- 如果当前节点及此节点的左右孩子都已经记录过，那么就移动到当前节点的父节点处。

现在给出从第一层的节点出发记录下的编号顺序，请你求出原本的完全二叉树。

inputFormat:
第一行，一个整数 $K$，表示这个完全二叉树有 $2^K-1$ 个节点；

第二行，$2^K-1$ 个整数，表示从第一层的节点出发记录下的编号顺序。

outputFormat: 输出共 $K$ 行，为原本的完全二叉树。

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

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

先移动到节点 $1$，发现左孩子没有记录，移动到节点 $2$ 并记录节点 $2$；发现节点 $2$ 没有孩子，返回节点 $1$ ，发现此节点没有记录，记录节点 $1$；发现右孩子没有记录，移动到节点 $3$ 并记录节点 $3$。

**【样例解释 #2】**

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

**【数据范围】**

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

**【说明】**

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

题目译自[COCI2013_2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #5](https://hsin.hr/coci/archive/2013_2014/contest5_tasks.pdf) _**T2 OBILAZAK**_


title: [COCI2013-2014#5]  EKSPLOZIJA

description:
给出一个字符串和一个目标字符串，在给出的字符串中找到所有的目标字符串并删除。

将剩下的小字符串按照原来的顺序拼接，再继续在剩下的字符串中持续这种操作，直到没有更多的目标字符串出现为止。

请打印出剩下的字符串。如果没有剩下的字符串，输出 `FRULA`。

inputFormat:
第一行，一个字符串，表示原字符串；

第二行，一个字符串，表示目标字符串。

outputFormat: 一行，一个字符串，表示剩下的字符串。

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

第一次删除，原字符串变为 `mirkov**nizC**4` （`*` 表示被删除的字符），即 `mirkovnizC4`。

第二次删除，字符串变为 `mirkovniz**`，即 `mirkovniz`。

**【样例解释 #2】**

第一次删除，原字符串变为 `****1****2ab` （`*` 表示被删除的字符），即 `12ab`。

第二次删除，字符串变为 `****`。故输出 `FRULA`。

**【数据范围】**

对于 $50\%$ 的数据，$1\le $ 原字符串长度 $\le 3000$；

对于 $100\%$ 的数据，$1\le $ 原字符串长度 $\le 10^6$，$1\le $ 目标字符串长度 $\le 36$，所有字符串均由大写字母、小写字母和数字 $0,1...9$ 组成，保证目标字符串中没有重复的字符。

**【说明】**

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

题目译自[COCI2013_2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #5](https://hsin.hr/coci/archive/2013_2014/contest5_tasks.pdf) _**T3 EKSPLOZIJA**_


title: 「Wdoi-3」夜雀 dreaming

background:
作为幻想乡食物链顶端的幽幽子，一直都是老板娘米斯蒂娅的噩梦！

尽管幽幽子一般而言是不会选择吃她的，但奈何日有所思夜有所梦，米斯蒂娅做了一个梦，一个交杂着幻想与现实的梦，或者说，那就是幻想中的现实……

尽管米斯蒂娅不知道这天什么时候会到来，但她不敢放松警惕，于是老板娘向你求助了……

description:
作为一道签到题，为了能让选手更好的发挥手速，米斯蒂娅决定提供这题的题意简述：[隙间传送](https://www.luogu.com.cn/paste/2dwm3f7z)。

---

在梦中，幽幽子来到了夜雀餐厅。似乎是由于异变的影响，本来就贪吃的幽幽子此刻变得更加可怕。

米斯蒂娅一共会做 $n$ 道菜，用来满足所有顾客的需求，并试图增加自己存活的概率。这些菜的编号为 $0,1,2$ 直到 $n-1$。同时，幽幽子会进行 $k$ 次点餐。

- 本题中，我们记**点菜事件**为 $\operatorname{order}(t,x)$ ，表示顾客向米斯蒂娅发起一份请求，希望她在 $t$ 时刻制作并端上菜品 $x$ 。
- 我们用一个三元组 $(t_i,x_i,y_i)$ 描述幽幽子发起第 $i$ 次点餐。在每次点餐中，幽幽子会发起 $\operatorname{order}(t_i,x_i)$ 。然而幽幽子的欲望是不能被满足的。因此，当幽幽子在 $t_i$ 时刻收到菜品时，会再次发起 $\operatorname{order}(2\cdot t_i,(x_i+y_i)\bmod n)$ ！更加不幸地，此过程会不断累加，接着她会发起 $\operatorname{order}(3\cdot t_i,(x_i+2\cdot y_i)\bmod n)$ 乃至更多……
- 总而言之，幽幽子的第 $i$ 次点餐 $(t_i,x_i,y_i)$ 会执行这样的操作：

$$\operatorname{order}(j\cdot t_i,(x_i+(j-1)\cdot y_i)\bmod n)(j=1,2,3,\cdots)$$

由于幽幽子会发起无数次点餐请求，所以米斯蒂娅是不可能使她满足的。但为了不辜负大家的期望，米斯蒂娅决定竭尽全力拖延时间。作为老板娘，她有着超凡的厨艺：

- 每一个时刻，米斯蒂娅都能做出**无限**份菜，**但菜只能是同一种类**。

如果一个时刻幽幽子点的菜没能被立即做好（幽幽子并不愿意吃上一个时刻做好的菜哦），那么她就会大发雷霆，在这一时刻**立即**摧毁夜雀餐厅。米斯蒂娅想知道她能坚持多久（坚持多久指的是最多能坚持多少个时刻使得这些时刻内幽幽子不会摧毁餐厅，时刻**从 $1$ 开始计数**）。如果她能坚持 $9961^{9961}$ 时刻或以上的话（在此题中，你可以认为 $9961^{9961}$ 是无穷大），请输出 `Mystia will cook forever...`。

inputFormat:
第一行有两个整数 $n,k$ ，含义如题面所示。

接下来 $k$ 行，每行给定三个整数 $(t_i,x_i,y_i)$ ，描述一组询问。

outputFormat: 共一行。输出米斯蒂娅最多能支撑多久，或者输出 `Mystia will cook forever...`。

hint:
#### 样例 1 解释

在时刻 $4$，幽幽子同时点了菜品 $3$ 和菜品 $2$，于是夜雀餐厅会被摧毁，答案为 $4-1=3$。

---

#### 数据范围及约定

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \bm{k} & \bm{\max\{t_i\}} & \textbf{特殊性质} & \textbf{分值}\cr\hline
\textsf1 & =1 & \text{无特殊限制} & \text{无} & 10 \cr\hline
\textsf2 & \leq 10 & \leq 10 & \text{无} & 20 \cr\hline
\textsf3 & \text{无特殊限制} & \text{无特殊限制} & \text{A} & 30\cr\hline
\textsf4 & \text{无特殊限制} & \text{无特殊限制}& \text{无}& 40 \cr\hline
\end{array}$$

特殊性质 $\text{A}$ ：保证对于所有的 $i$ ，满足 $y_i = 0$ 。

对于 $100\%$ 的数据，满足：
- $1 \le t_i,n \leq 10 ^ 9$。
- $0 \le x_i,y_i  \leq 10 ^ 9$。
- $1 \le k \leq 1000 $。


title: [COCI2013-2014#5] DOMINE

description: 给出一个 $N\times 3$ 的棋盘，上面写有数字。给你 $K$ 块 $1\times 2$ 的多米诺骨牌，请你求出用这 $K$ 块骨牌能覆盖的棋盘上的数字之和的最大值。

inputFormat:
第一行，两个整数 $N$ 和 $K$，分别表示棋盘的行数和骨牌块数；

接下来 $N$ 行，每行 $3$ 个整数，表示棋盘上的数字。

outputFormat: 输出一个整数，表示这 $K$ 块骨牌能覆盖的棋盘上的数字之和的最大值。

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

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

如图，总和为 $3+2+2+3+3+3=16$，可以证明这是最大的。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N,K\le 1000$。

**【说明】**

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

题目译自[COCI2013_2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #5](https://hsin.hr/coci/archive/2013_2014/contest5_tasks.pdf) _**T4  DOMINE**_


title: [COCI2013-2014#5] TROKUTI

description:
给定 $N$ 条在平面直角坐标系内的直线，这些直线上的点满足 $A_ix+B_iy+C_i=0$。

请你求出这些直线围出的三角形个数，答案对 $10^9+7$ 取模。

保证没有三线共点。

inputFormat:
第一行，一个整数 $N$，表示直线条数；

接下来 $N$ 行，每行 $3$ 个 $A_i,B_i,C_i$，表示直线 $i$ 满足的条件。

outputFormat: 一个整数，表示这些直线围出的三角形对 $10^9+7$ 取模后的个数。

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

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

上图即为所有直线在平面直角坐标系上的位置，共围出了 $10$ 个三角形。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N\le 3\times 10^5$，$|A_i|,|B_i|,|C_i|\le 10^9$。

**【说明】**

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

题目译自[COCI2013_2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #5](https://hsin.hr/coci/archive/2013_2014/contest5_tasks.pdf) _**T5 TROKUTI*_


title: [COCI2013-2014#5] LADICE

description:
有 $N$ 个物品，$L$ 个抽屉，没个抽屉只能放 $1$ 个物品，每个物品都能被放进抽屉 $A_i$ 或 $B_i$ 中。

放物品的规则如下（按照顺序执行，即满足条件 $1$ 时就立刻执行，不会执行条件 $2$；不满足条件 $1$ 时就判断条件 $2$）：

- $1.$ 如果抽屉 $A_i$ 是空的，就把这个物品放进抽屉 $A_i$ 中；

- $2$ 如果抽屉 $B_i$ 是空的，就把这个物品放进抽屉 $B_i$ 中；

- $3.$ 把抽屉 $A_i$ 中的物品移到它的另一个抽屉里；如果这个抽屉也满了，就把这个抽屉里的物品放到它的另一个抽屉里，知道你成功或回到之前遇到过的抽屉为止。如果成功了，就把这个物品放进这个抽屉中；

- $4.$ 把抽屉 $B_i$ 中的物品移到它的另一个抽屉里；如果这个抽屉也满了，就把这个抽屉里的物品放到它的另一个抽屉里，知道你成功或回到之前遇到过的抽屉为止。如果成功了，就把这个物品放进这个抽屉中；

- $5.$ 扔掉此物品。

对于给定的每件物品，请你求出哪些物品将被保存，哪些将被扔掉。

inputFormat:
第一行，两个整数 $N$ 和 $L$，分别表示物品个数和抽屉个数；

接下来的 $N$ 行，每行两个整数 $A_i$ 和 $B_i$，表示物品 $i$ 能被储存的两个抽屉。

outputFormat:
输出共 $N$ 行，每行一个字符串：

如果该物品成功被保存，输出 `LADICA`；

如果该物品被扔掉，输出 `SMECE`。

samples:
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA

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

物品 $1$ 放入抽屉 $1$，物品 $2$ 放入抽屉 $3$，物品 $3$ 放入抽屉 $3$，物品 $1$ 和物品 $1$ 没有地方放。

**【样例解释 #2】**

物品 $1$ 放入抽屉 $1$，物品 $2$ 放入抽屉 $3$，物品 $3$ 放入抽屉 $5$，物品 $4$ 放入抽屉 $7$，物品 $5$ 放入抽屉 $9$，物品 $6$ 放入抽屉 $2$，物品 $8$ 放入抽屉 $8$。

物品 $7$ 的两个抽屉都满了，将抽屉 $1$ 里的物品 $1$ 移到抽屉 $2$ 里，将抽屉 $2$ 里的物品 $6$ 移到抽屉 $3$ 里，将抽屉 $3$ 里的物品 $2$ 移到抽屉 $4$ 里，抽屉 $4$ 是空的，成功放入。

物品 $9$ 的两个抽屉都满了，将抽屉 $7$ 里的物品 $4$ 移到抽屉 $8$ 里，将抽屉 $8$ 里的物品 $8$ 移到抽屉 $2$ 里，将抽屉 $2$ 里的物品 $1$ 移到抽屉 $1$ 里，将抽屉 $1$ 里的物品 $7$ 移到抽屉 $5$ 里，将抽屉 $5$ 里的物品 $3$ 移到抽屉 $6$ 里，抽屉 $6$ 是空的，成功放入。

**【数据范围】**

对于 $50\%$ 的数据，$1\le N,L\le 2000$；

对于 $100\%$ 的数据，$1\le N,L\le 3\times 10^5$，$1\le A_i,B_i\le L$。

**【说明】**

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

题目译自[COCI2013_2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #5](https://hsin.hr/coci/archive/2013_2014/contest5_tasks.pdf) _**T6  LADICE**_


title: [COCI2008-2009#5] LJESNJAK

description:
不久以前，在操作系统还未像今天如此发达的时候，计算机无法处理克罗地亚字母表中的某些字母，于是程序员被允许用二到三个计算机能够显示的字符替换这个不能显示的字母，如下表：

| 不能显示的字母 | 用来替换的字符 |
| :----------: | :----------: |
| `č` | `c=` |
| `ć` | `c-` |
| `dž` | `dz=` |
| `ñ` | `d-` |
| `lj` | `lj` |
| `nj` | `nj` |
| `š` | `s=` |
| `ž` | `z=` |

例如说，`ljes=njak` 这一个字符串可以用来表示克罗地亚字母表中的六个字母：`lj`、`e`、`š`、`nj`、`a`、`k`。

现在给出一个字符串，请你求出解码后这一个字符串里面包含多少个克罗地亚字母表中的字母。字母的匹配是贪心的，尽可能长的匹配当前字母，例如 `lj` 不应该被认为是两个英文字母 `l` 和 `j`。

克罗地亚字母表中的字母除了有上表中的几个字母外，还有英语中的 `a`~`z` 这 26 个字母。

inputFormat: 输入仅一行，一个字符串，表示一个按上述方式编码的字符串。

outputFormat: 输出仅一行，表示解码之后的字符串包含的克罗地亚字母表中的字母个数。

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

对于所有数据，满足字符串的长度不超过 $100$，且仅包含小写字母和 `-`、`=` 字符。

**【题目来源】**

本题来源自 **_[COCI 2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T1 LJESNJAK_**，按照原题数据配置，满分 $30$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2008-2009#5] JABUKA

description:
Mirko 拥有 $R$ 个红苹果和 $G$ 个绿苹果，他想把他分给若干个朋友，使得所有朋友分得的红苹果个数和绿苹果个数都一样。由于 Mirko 自己不喜欢苹果，所以他不会给自己留苹果。

例如，假设 Mirko 有 $4$ 个红苹果和 $8$ 个绿苹果，则以下是分配苹果的所有方案：

- 分给一个朋友，即将 $4$ 个红苹果和 $8$ 个绿苹果全部分给这个朋友。
- 分给两个朋友，每个朋友分得 $2$ 个红苹果和 $4$ 个绿苹果。
- 分给四个朋友，每个朋友分得 $1$ 个红苹果和 $2$ 个绿苹果。

现给定 $R,G$，请你帮助 Mirko 找到所有的分配苹果的方案。可以证明一定存在分配苹果的方案。

inputFormat: 输入仅一行，两个整数 $R,G$，分别表示红苹果的个数和绿苹果的个数。

outputFormat:
输出若干行，每行三个整数，分别表示分给的朋友数，每个朋友分得的红苹果个数和绿苹果个数。

如果有多种方案，请按照**朋友的个数升序排列**输出。

数据保证不会超出输出限制。

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

对于所有数据，$1\leqslant R,G\leqslant 10^9$。

**【题目来源】**

本题来源自 **_[COCI 2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T2 JABUKA_**，按照原题数据配置，满分 $50$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2008-2009#5] JAGODA

description:
Slavko 养了 $n$ 只兔子，他每天用各种水果和蔬菜喂兔子。然而，兔子最喜欢草莓。草莓在隆冬时节很难找到，而且很贵，所以 Slavko 只给部分兔子吃草莓。Slavko 把兔子编号为 $1\sim n$。为了帮助追踪每只兔子得到多少草莓，他决定采用以下草莓分配程序。

Slavko 每天都会买 $S$ 个草莓，然后选一个兔子 $A$ ，然后给它第一个草莓。之后，兔子 $A+1$ 会得到第二个草莓，兔子 $A+2$ 会得到第三个，以此类推。

给每只兔子分配一个最初为空的火柴盒，然后把这 $n$ 个火柴盒排成一排。设 $k$ 为使得 $k^2\leqslant n$ 的最大整数。这样就可以把兔子分成 $\left\lceil\dfrac{n}{k}\right\rceil$组，每组 $k$ 个火柴盒（从第一个开始，最后一组有可能不足 $k$ 个），每组火柴盒旁边也会有一个杯子。我们说 $k$ 个连续的火柴盒和它们的杯子形成一组。

在给兔子草莓之后，Slavko 会把一根火柴放进每个得到草莓的兔子的火柴盒里，**除非**他把火柴放进一组里所有的火柴盒里。此时他不会把火柴放在一组的所有火柴盒里，而是把一根火柴放在这一组所在的杯子里。通过这种方式，兔子收到的草莓总数可以用火柴盒里的火柴数加上杯子里的火柴数来计算。例如，假设 Slavko 有 $11$ 只兔子，即 $n=11$。数字 $3$ 是使得 $k^2\leqslant n$ 的最大整数 $k$，因此 $k=3$。因此这些兔子将会被分成四组（最后一组只有两只兔子和两个火柴盒），自然就会有四个杯子，如下图所示：

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

如果 Slavko 买了 $6$ 个草莓，把第一个送给兔子 $5$，杯子和火柴盒里的状态将变为如下图所示：

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

现在，请你编写一个程序，给定兔子的数量 $n$、天数 $m$ 以及 $m$ 天中的每一天购买的草莓数量 $S$ 和得到第一个草莓的兔子编号 $A$。对于每一天，输出 Slavko 当天使用的所有火柴盒和杯子中的火柴总数。

inputFormat:
输入共 $m+1$ 行。

第一行两个整数 $n,m$，分别表示兔子的总数（也是火柴盒数）和天数。
随后 $m$ 行，第 $i$ 行两个整数 $S,A$，分别表示第 $i$ 天购买的草莓数量和得到第一个草莓的兔子编号。

outputFormat: 输出共 $m$ 行，第 $i$ 行一个整数，表示 Slavko 第 $i$ 天使用的所有火柴盒和杯子中的火柴总数。

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

对于样例 $1$，兔子、火柴盒和杯子摆放的情况即为题面中所给出的例子。

第一天即为题面中所给出的例子，因此 Slavko 第一天放入 $4$ 根火柴。

第二天 Slavko 买了 $3$ 个草莓，并将第一个草莓给了 $1$ 号兔子，这样的话，$1$、$2$、$3$ 号兔子都得到草莓，由于它们三个兔子都在一组里面，所以 Slavko 只需要在第 $1$ 个杯子里面放入一根火柴。因此 Slavko 第一天放入 $1$ 根火柴。

第三天，Slavko 可以给他所有的兔子送草莓，所以需要在每个杯子里放一根火柴。总共是把 $4$ 根火柴放到杯子里，他在这天使用的杯子里（就是所有杯子）在他放置后一共有 $6$ 根火柴，所以输出 $6$。

**【数据范围】**

对于所有数据。$1\leqslant n,m\leqslant 10^5$，$1\leqslant A\leqslant n$，$1\leqslant A+S-1\leqslant n$。

**【题目来源】**

本题来源自 **_[COCI 2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T3 JAGODA_**，按照原题数据配置，满分 $70$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [CEOI2005] Depot Rearrangement

description:
一家公司经营着 $N$ 个店铺，每个店铺都销售 $M$ 种不同的产品。该公司有一个大型仓库，产品在运送到商店之前在都会那里进行包装。每家商店将会收到相同数量的每种产品。因此，该公司将一定数量的相应产品分别包装到一个集装箱中，并用产品标识符标记该集装箱。产品由 $1$ 到 $M$ 的数字标识。因此，在包装结束后，仓库中将会有 $N×M$ 个集装箱，并且正好 $N$ 个集装箱贴有每个产品的对应标签。由于该仓库位于一个狭窄的建筑物内，所以集装箱排成了一排。但为了加快配送速度，仓库经理想要重新排列集装箱。由于将产品配送到商店是通过向每个商店发出一辆卡车来实现的，并且每辆卡车运载每种产品的一个集装箱，其合适的安排如下。该行最前部分 $M$ 个集装箱必须贴有不同的产品标签，该行的第二部分 $M$ 个集装箱必须贴有不同的产品标签，依此类推。不幸的是，在这一行的尽头只有一个空闲的地方可以放置一个集装箱。因此，必须通过依次拿起集装箱并将其移动到空闲位置来进行重新排列。重新排列后，空闲位置也必须在行的末尾。
目标是通过最少的移动以实现所需的重新排列。
现请您编写一个程序来计算需要最少移动多少次使得达成目标重排。

inputFormat: 第一行包含两个整数 $N$ 和 $M$。$N$ 是商店的数量，$M$ 是产品的数量。第二行包含 $N×M$ 个整数，即按初始顺序排列的集装箱标签。每个产品标识符 $x$ 在行中恰好出现 $N$ 次。

outputFormat: 第一行包含一个整数 $S$，这是达成集装箱所需排列所需的最小移动次数。以下 $S$ 行描述了重新排列。每行包含一对整数 $x$，$y$。一对 $x$，$y$ 描述了一个移动：位于 $x$ 位置的集装箱将移动到位置 $y$。位置由从 $1$ 到 $N×M+1$ 的数字标识；最初位置 $N×M+1$ 是空闲的（没有集装箱）。只有在移动之前位置 $y$ 是空闲的，从 $x$ 到 $y$ 的移动才是合法的。从 $x$ 移动到 $y$ 后，位置 $x$ 将是空闲的。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq N \leq 400$，$1 \leq M \leq 400$，$1 \leq x \leq M$。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Depot Rearrangement。
由 @[求学的企鹅](/user/271784) 翻译整理。
Special Judge 感谢 @[abruce](/user/104324)。


title: [COCI2008-2009#5] LUBENICA

description:
一个班有 $n$ 个孩子，他们上课时并没有认真听课，而是在玩 Facebook 社交网页上的扔西瓜游戏。

第一节课上，Goran 向他的每个朋友扔了一个西瓜，**随后几节课**，孩子们都会按照以下方式采取行动：

- 如果上节课一个人被奇数个西瓜扔中，那么这节课他会向所有他的朋友各扔一个西瓜。
- 如果上节课一个人被偶数（**包括 $0$**）个西瓜扔中，那么这节课他会向所有他的朋友各扔两个西瓜。

孩子们按照 $1\sim n$ 编号，其中 Goran 的编号为 $1$。

现在，给定孩子的个数 $n$ 和他们所有人的朋友关系，请求出 $h$ 节课之后，孩子们一共扔了多少个西瓜。

inputFormat:
输入共 $n+1$ 行。

第一行，两个整数 $n,h$，分别表示孩子的个数和课程的节数。
随后 $n$ 行，每行 $n$ 个整数（**不用空格隔开**），形成一个矩阵。第 $i$ 行描述第 $i$ 个孩子的朋友关系，具体地，如果第 $i$ 行第 $j$ 个元素是 $1$，则表示第 $i$ 个孩子和第 $j$ 个孩子是朋友，否则不是。

输入矩阵是对称的（即 $A$ 如果是 $B$ 的朋友，那么 $B$ 也会是 $A$ 的朋友），并且保证不会出现一个孩子和自己成为朋友的情况。

outputFormat: 输出仅一行，一个整数，表示 $h$ 节课之后孩子们扔出的西瓜总数。

hint:
**【样例 1/2 解释】**

对于样例 $1/2$，首先，Goran 在第一节课上向第 $2$、$3$ 号孩子扔出一个西瓜，并且没有其他孩子扔出西瓜。因此，样例 $1$ 的答案为 $2$。
第二节课上，第 $2$、$3$ 号孩子都向第 $1$、$4$ 号孩子各扔出一个西瓜，同时第 $1$、$4$ 号孩子由于在上一节课没有被西瓜扔中，因此他们都向第 $2$、$3$ 号孩子各扔出 $2$ 个西瓜。因此第二节课上一共扔出了 $2\times 2\times 1+2\times 2\times 2=12$ 个西瓜。

因此，前两节课一共扔出了 $2+12=14$ 个西瓜，而这就是样例 $2$ 的答案。

**【数据范围】**

对于 $50\%$ 的数据，满足 $h\leqslant 1000$。
对于所有数据，$1\leqslant n\leqslant 20$，$1\leqslant h\leqslant 10^9$。

**【题目来源】**

本题来源自 **_[COCI 2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T4 LUBENICA_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2008-2009#5] TRESNJA

description:
Lana 住在一个快乐的小村庄里。主街旁边有一排樱桃树。Lana 注意到每棵树用从 $1$ 开始的连续整数编号。经过大量研究，Lana 注意到树的编号唯一地决定了树的樱桃数量。对于一棵树，考虑将树编号中的连续数字组拆分出来。对于每组数字，将这一组中唯一的数字乘以该组数字长度的平方。把这些数字加在一起就得到了树上的樱桃总数。例如，在编号为 $77744007$ 的树中，我们将编号中的连续数字组拆分出来，得到 $4$ 组数：$777$、$44$、$00$ 和 $7$。所以编号为 $77744007$ 的树中樱桃的数量为 $7\times 3^2+4\times 2^2+0\times2^2+7\times1^2=86$ 个。

到了摘樱桃的时候了，村民们同意把编号在区间 $[a,b]$ 中的树上的樱桃都摘下来。现在请你编写一个程序来计算采摘樱桃的总量。

inputFormat: 输入仅一行，两个整数 $a,b$，代表能够采摘樱桃的树的起始点和终止点。

outputFormat: 输出仅一行，一个整数，代表能够采摘的樱桃总量。

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

对于所有数据，$1\leqslant a\leqslant b\leqslant 10^{15}$。

**【题目来源】**

本题来源自 **_[COCI 2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T5 TRESNJA_**，按照原题数据配置，满分 $120$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2008-2009#5] KRUSKA

background: Aladdin 已经厌倦了宫殿里的生活。他有一份稳定的工作，他的妻子 Jasmine 和孩子们都在路上，生活变得单调。在这一切的驱使下，他决定在安顿下来之前再进行一次冒险。他决定找到 Golden Pear，这是一件极为珍贵的传奇文物，至今无人能找到。

description:
Aladdin 正在寻找的沙漠可以被看作是一个 $n×n$ 的网格。行和列从上到下、从左到右编号为 $1$ 到 $n$。沙漠中的网格里一共有 $m$ 个巫师，他们以一种不同寻常的方式帮助 Aladdin 完成任务。

Aladdin 星期一在沙漠的左上角 $(1,1)$ 开始他的任务并面朝右。他的动作包括重复这些步骤：

1. 如果当前的网格里有一个醒着的巫师，那么 Aladdin 会根据巫师说的话向左或向右转 $90$ 度。
2. 如果向前走会把 Aladdin 带出沙漠，他会转过 $180$ 度。
3. Aladdin 向前移动了一格，这将花费他一天的时间。

对于每个巫师，我们都知道他的位置和一周中每一天的活动计划。每个巫师的日程表是一个由七个字母（仅包含`L`、`R` 或 `S`）组成的字符串，每个字符告诉我们巫师在一周中的某一天（从**星期一**开始）做什么。字母 `L` 表示 Aladdin 将在这一天被告知向左转，`R` 表示 Aladdin 将在这一天被告知向右转，而 `S` 表示巫师那天正在睡觉。

一个古老的预言说，在改变 $k$ 次方向（通过**步骤 $1$ 和步骤 $2$**）后，Aladdin 会找到 Golden Pear。根据古老的预言，写一个程序来计算冒险将持续多少天。

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

第一行，两个整数 $n,k$，分别表示沙漠的边长和古老的预言中所说的要改变方向的次数。
第二行，一个整数 $m$，表示巫师的个数。
随后 $m$ 行，第 $i$ 行两个整数和一个字符串，分别表示巫师所在的横坐标，纵坐标和一个星期内的行动（从**星期一**开始）。

数据保证不存在在 $(1,1)$ 处的巫师、两个在同一网格的巫师或者在沙漠外的巫师。

outputFormat: 输出仅一行，一个整数，代表冒险持续的天数。

samples:
5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS

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

对于样例 $1$，Aladdin 移动了两格之后到达沙漠的边缘，随后他转过 $180$ 度，找到了 Golden Pear。所以冒险将持续 $2$ 天。

**【样例 2 解释】**

对于样例 $2$，Aladdin 在走了两天之后找到了第一个巫师，但是这个巫师此时正在睡觉，所以 Aladdin 继续走了两天，然后他在第 $4$ 天找到了第二个巫师，这个巫师告诉他要向左转，Aladdin 这么做了，然后他来到了沙漠的边缘，转过 $180$ 度，找到了 Golden Pear。所以冒险将持续 $4$ 天。

**【数据范围】**

对于 $50\%$ 的数据，保证 $k\leqslant 1000$。
对于所有数据，$2\leqslant n\leqslant 200$，$1\leqslant k\leqslant 10^9$，$0\leqslant m\leqslant 10^4$。

**【题目来源】**

本题来源自 **_[COCI 2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T6 KRUSKA_**，按照原题数据配置，满分 $130$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [CEOI2005] Mobile Service

description:
一家公司为其位于不同城镇的合作伙伴提供服务。公司现有流动服务人员 $3$ 名。如果服务请求发生在某个位置，服务人员必须从他当前的位置移动到请求的位置（如果没有员工在那里）以满足请求。任何时候只有一名员工可以移动。他们只能应要求移动，并且不允许多名员工在同一位置。将员工从位置 $p$ 移动到位置 $q$ 会产生一定的成本 $C(p,q)$。成本计算不一定是对等的，但不动代价为 $0$，即 $C(p,p)=0$。公司必须以严格按照先请求先得服务的原则满足收到的要求。
请您编写一个程序，该程序决定服务人员中的哪位员工要为每个请求移动，以便为给定的请求列表提供服务的总成本尽可能小。

inputFormat: 第一行包含两个整数 $L$ 和 $N$。$L$ 是表示位置的数，$N$ 是请求数。位置由从 $1$ 到 $L$ 的整数表示。接下来的 $L$ 行中的每一行都包含 $L$ 个非负整数。第 $i+1$ 行第 $j$ 个数字是成本 $C(i,j)$。最后一行包含 $N$ 个整数，为请求列表。请求由发生请求的位置的标识符标识。起初，三名服务人员分别位于位置 $1,2$ 和 $3$，并以此为三名服务人员进行标识。

outputFormat: 第一行包含一个整数 $M$，它是为请求的列表提供服务的最小总成本。第二行正好包含 $N$ 个整数。第 $i$ 个编号是将为第 $i$ 个请求提供服务的服务人员的标识符（$1,2 $ 或 $3$）。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$3 \leq L \leq 200$，$1 \leq N \leq 1000$，$C(i,j) <2000$。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Mobile  Service。
由 @[求学的企鹅](/user/271784) 翻译整理。
Special Judge 感谢 @[Cat_shao](/user/234011)。


title: [CEOI2005] Multi-key Sorting

description:
考虑一个包含行和列的表。列从 $1$ 到 $C$ 编号。为简单起见，表中的项目是由小写字母组成的字符串。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/z70sexo1.png)
您将获得对此类表的 Sort($k$) 操作：Sort($k$) 按照列 $k$ 中的值的顺序对表的行进行排序（而列的顺序不会改变）。排序是稳定的，即在第 $k$ 列中具有相等值的行保持其原始顺序。例如，将 Sort($2$) 应用于表 $1$ 会产生表 $2$。
我们对此类排序操作的序列感兴趣。这些操作依次应用于同一个表。例如，应用序列 Sort($2$)；Sort($1$) 到表 $1$ 产生表 $3$。
如果两个排序操作序列对于任何表具有相同的效果，则它们被称为等效。例如，Sort($2$)；Sort($2$)；Sort($1$) 等效于 Sort($2$)；Sort($1$)。但是，它不等效于 Sort($1$)；Sort($2$)，因为对表 $1$ 的影响不同。

inputFormat: 第一行包含两个整数，$C$ 和 $N$。$C$ 是列数，$N$ 是排序操作数。第二行包含 $N$ 个整数，$k_i$。它定义了排序操作的顺序 Sort($k_1$)；$\cdots$； Sort($k_N$)。

outputFormat: 第一行包含一个整数 $M$，为输入的操作序列的最短等效排序操作序列的长度。第二行包含 $M$ 个整数，表示其最短操作序列。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq C \leq 10^6$，$1 \leq N \leq 3×10^6$，$1 \leq k_i \leq C$。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Multi-key Sorting。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [CEOI2005] Critical Network Lines

description:
一个通信网络包含若干个节点，以及若干条直接连接这些节点的双向**通信线路**。已知所研究的通信网络是连通的，即：任意一对节点之间都存在（若干条**通信线路**首尾相接而成的）**通信路径**。

一些节点会向所有节点（包括它自己）提供 $A$ 类型服务，还有一些节点会向所有节点（包括它自己）提供 $B$ 类型服务。一个节点可能会同时提供两种类型的服务。每个节点都必须要访问这两种服务。

当一条**通信线路**断开时，可能会出现某个节点不能访问某种服务的情况。（即：存在某个节点以及某种服务，使得不存在任何提供该类型服务，且与该节点连通的节点）我们称会造成这种情况的**通信线路**为**关键通信线路**。

你的任务是，写一个程序计算有多少条**关键通信线路**，并求出每条**关键通信线路**所连接的两个端点。

inputFormat:
输入第一行包含四个整数 $N,M,K,L$。其中，$N \; (1 \le N \le 10^5)$ 表示通信网络的节点数，$M \; (1 \le M \le 10^6)$ 表示通信网络的**通信线路**数，$K \; (1 \le K \le N)$ 表示提供 $A$ 类型服务的节点数，$L \; (1 \le L \le N)$ 表示提供 $B$ 类型服务的节点数。节点编号为 $1$ 到 $N$。

第二行包含 $K$ 个整数，表示提供 $A$ 类型服务的节点编号。

第三行包含 $L$ 个整数，表示提供 $B$ 类型服务的节点编号。

接下来 $M$ 行，每行包含两个整数 $p,q \; (1 \le p,q \le N,p \neq q)$，表示一条**通信线路**的两个端点的编号。保证任意两个节点之间至多只有一条**通信线路**。

outputFormat:
输出第一行包含一个整数 $S$，表示**关键通信线路**的数量。

接下来 $S$ 行，每行包含两个整数 $p,q$，表示一条**关键通信线路**所连接的两个端点的编号。

**关键通信线路**的顺序任意，每一条**关键通信线路**所连接的两个端点的顺序也任意。

hint:
本题为 CEOI2005 D2T2，原题面请见：[Critical Network Lines](http://ceoi.inf.elte.hu/ceoi2005/download/tasks/day2/net.htm)。

感谢 @[wsyhb](https://www.luogu.com.cn/user/145355) 提供的 Special Judge！


title: [CEOI2005] Ticket Office

description:
售票处在出售音乐会门票，但它不销售单个座位的门票，而是销售固定数量的连续座位的成组门票。该售票处办公室已收到大量采购订单。一组座位的采购订单指定该组座位中最低的座位号。而办公室可能无法完成所有采购订单。此外，如果它只完全按照采购订单中的要求分配座位，那么大量作位可能会保持空置。因此，办公室采用以下分配和定价策略。如果采购订单被接受并且分配的座位正是所要求的座位，那么购买者支付全价（$2$ petaks）。如果采购订单被接受，但分配的座位与请求的座位不同（至少在一个位置上），则购买者支付半价（$1$ petak）。目标是使总收入最大化。
请您编写一个程序来计算可以实现的最大收入，并将座位分配给选定的订单以实现该收入。

inputFormat: 第一行包含两个整数，$M$ 和 $L$。$M$ 是座位数，$L$ 是每组中连续的座位号。座位号从 $1$ 到 $M$。第二行包含一个整数 $N$，即采购订单的数量。第三行包含 $N$ 个整数，定义采购订单，其行中的第 $i$ 个数字 $z$ 表示第 $i$ 个购买者要求从座位 $z$ 开始到座位 $z+L-1$ 结束的一组座位。

outputFormat: 第一行包含一个整数 $S$，即最大收入。第二行包含一个整数 $Q$，即已接受订单的数量。 接下来的 $Q$ 行描述了座位分配。每行包含一对整数 $x$ $y$。一对 $x$ $y$ 表示购买者 $x$ 从座位号 $y$ 开始获得座位。这些行必须按座位号的升序排列。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据， $1 \leq M \leq 3×10^4$，$1 \leq L \leq 100$，$1 \leq N \leq 10^5$，$1 \leq z \leq M-L+1$。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Ticket Office。
由 @[求学的企鹅](/user/271784) 翻译整理。
Special Judge 感谢 @[Azazеl](/user/160701)。


title: [CEOI2002] Bugs Integrated,Inc.

description:
Bugs Integrated,Inc. 是高级存储芯片的主要制造商。他们正在开始生产新的 $6$ TB Q-RAM 芯片。每个芯片由以 $2×3$ 的矩形排列的六个方形硅片块组成。Q-RAM 芯片的制造方式是将一块长方形的大硅片分成 $N×M$ 个方形硅片块。然后仔细测试所有方形硅片块，坏的用黑色标记。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/qqjfauh0.png)
最后，将硅片切割成存储芯片。每个芯片由 $2×3$（或
 $3×2$）单位方形硅片块组成。当然，任何芯片都不能包含任何坏的（标记的）方形硅片块。它可能不能将硅片切割成每一个好的方形硅片块都成为某些存储芯片的一部分。该公司希望尽可能少地浪费好方形硅片块。因此他们想知道如何切割硅片以尽可能多地切出芯片。
现您将获得几个硅片的尺寸和其每个硅片所有坏方形硅片块的列表。你的任务是编写一个程序，计算每个硅片最多可以从其切下的芯片数量。

inputFormat: 第一行由一个整数 $D$ 组成，表示硅片的数量。接下来 $D$ 个部分，每个部分描述一个硅片。每个部分的第一行包含三个整数 $N$，$M$，$K$，其间由单个空格分隔。$N$ 是硅片的长度，$M$ 是它的高度，$K$ 是硅片中坏方硅片块的数量。以下 $K$ 行包含一个坏方硅片块列表。每行包含两个整数 $x$ 和 $y$，表示一个坏方硅片块的坐标（左上角的坐标为（$1,1$），左下角是 （$N,M$））。

outputFormat: 每行输出每个硅片最多可以从其切下的芯片数量。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq D \leq 5$，$1 \leq N \leq 150$，$1 \leq M \leq 10$，$0 \leq K \leq M×N$，$1 \leq x \leq N$，$1 \leq y \leq M$。
#### 样例说明
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/v4ugwh72.png)
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2002 的 [Bugs Integrated,Inc.](https://web.ics.upjs.sk/ceoi/documents/tasks/bugs-tsk.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [CEOI2002] A decorative fence

description:
理查德刚刚盖完他的新房子。现在房子唯一缺少的是一个可爱的小木栅栏。他不知道如何制作木栅栏，所以他决定订购一个。不知何故，他拿到了 $\texttt{ACME Fence Catalog 2002}$――可爱的小木栅栏的旗舰版资源（注：ACME 是一家什么都造的公司）。看完它的前言，他已经知道，什么使小木栅栏变得可爱。
一个木栅栏由 $N$ 块木板组成，每块木板垂直排成一排。除此之外，当且仅当满足以下条件时，围栏看起来很可爱：
- 木板有不同的长度，即 $1,2,\cdots,N$ 为木板长度单位。
- 每块有两个相邻的木板，它要么比它的相邻的都大，要么比它相邻的都小。（即，这会使得围栏顶部交替上升和下降（高低起伏））。

因此，我们可以将每个用 $N$ 块木板的可爱的栅栏唯一地描述为一个排列 $a_1,\cdots,a_N$（$\forall i$，$1 < i < N$）$(a_i - a_{i−1}) × (a_i - a_{i+1}) > 0$。反之亦然，每个这样的排列都描述了一个可爱的围栏。
很明显，可能有许多不同的可爱木栅栏由 $N$ 块木板制成。ACME 的销售经理决定以下列方式排列可爱围栏并放入清单：栅栏 A（由排列 $a_1,\cdots,a_N$ 表示）在栅栏 B 之前（由 $b_1,\cdots,b_N$ 表示），当且仅当存在这样的 $i$，使得（$\forall j < i$）$a_j = b_j$ 和 （$a_i < b_i$）。（也就是说，比较两个围栏中哪个在清单中更早相当于取它们对应的排列，找出它们第一个不同的地方，并比较这个地方的值。）所有 $N$ 块木板的可爱围栏都被按照它们在清单中出现的顺序编号（从 $1$ 开始）。这个号码被称为他们的清单号。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/9kopwi5p.png)
仔细检查所有的可爱的小木栅栏后，理查德决定要它们中的一些。他记下木板的数量 $N$ 和清单号 $C$。后来，他遇到了他的朋友，他想向他们展示他围栏，但他失去了清单。他得到的唯一的事情是他的笔记。请帮助他查明，他的围栏将为何等样子。

inputFormat: 第一行包含一个整数 $K$。接下来 $K$ 行，每行描述一个输入数据集，每一行都包含两个以空格分割的整数 $N$ 和 $C$，$N$ 是围栏上木板的数量，$C$ 是围栏的栅栏的清单号。

outputFormat: 每个数据集输出一行，描述列表带有 $N$ 个木板的第 $C$ 个栅栏。更准确地说，如果栅栏排列 $a_1,\cdots,a_N$，则输出的相应行应包含数字 $a_i$（按正确顺序），由单个空格分隔。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq K \leq 100$，$1 \leq N \leq 20$。你可以认为，$20$ 块木板的可爱小木栅栏的总数适合转换为 $64$ 位有符号整数变量（C/C++ 中的 `long long`，FreePascal 中的 `int64`）。你也可以认为输入是正确的，特别是 $C$ 最小是 $1$ 并且它不超过有 $N$ 块木板的可爱围栏的数量。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2002 的 [A decorative fence](https://web.ics.upjs.sk/ceoi/documents/tasks/fence-tsk.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [蓝桥杯 2019 省 B] 特别数的和

description:
小明对数位中含有 $2$、$0$、$1$、$9$ 的数字很感兴趣（不包括前导 $0$），在 $1$ 到 $40$ 中这样的数包括 $1$、$2$、$9$、$10$ 至 $32$、$39$ 和 $40$，共 $28$ 个，他们的和是 $574$。

请问，在 $1$ 到 $n$ 中，所有这样的数的和是多少？

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

outputFormat: 输出一行，包含一个整数，表示满足条件的数的和。

hint:
对于 $20\%$ 的评测用例，$1 \le n \le 10$。

对于 $50\%$ 的评测用例，$1 \le n \le 100$。

对于 $80\%$ 的评测用例，$1 \le n \le 1000$。

对于所有评测用例，$1 \le n \le 10000$。

蓝桥杯 2019 省赛 B 组 F 题。


title: [蓝桥杯 2019 省 AB] 完全二叉树的权值

description:
给定一棵包含 $N$ 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 $A_1,A_2, \cdots A_N$，如下图所示：

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

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 $1$。

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

第二行包含 $N$ 个整数 $A_1,A_2, \cdots, A_N$。

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

hint:
对于所有评测用例，$1 \le N \le 10^5$，$0 \le |A_i| \le 10^5$。

蓝桥杯 2019 省赛 A 组 F 题（B 组 G 题）。


title: [蓝桥杯 2019 省 B] 等差数列

description:
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 $N$ 个整数。

现在给出这 $N$ 个整数，小明想知道包含这 $N$ 个整数的最短的等差数列有几项？

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

第二行包含 $N$ 个整数 $A_1,A_2,\cdots,A_N$。（注意 $A_1 ∼ A_N$ 并不一定是按等差数列中的顺序给出 )。

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


title: [蓝桥杯 2019 省 B] 后缀表达式

description:
给定 $N$ 个加号、 $M$ 个减号以及 $N+M+1$ 个整数 $A_1,A_2,\cdots,A_{N+M+1}$，小明想知道在所有由这 $N$ 个加号、 $M$ 个减号以及 $N+M+1$ 个整数凑出的合法的后缀表达式中，结果最大的是哪一个。

请你输出这个最大的结果。

例如使用 `1 2 3 + -`，则 `2 3 + 1 -` 这个后缀表达式结果是 $4$，是最大的。

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

第二行包含 $N+M+1$ 个整数 $A_1,A_2,\cdots,A_{N+M+1}$。

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

hint:
对于所有评测用例，$0 \le N,M \le 10^5$，$-10^9 \le A_i \le 10^9$。

蓝桥杯 2019 年省赛 B 组 I 题。


title: [蓝桥杯 2019 省 B] 灵能传输

background: 在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在游戏的中后期发挥着重要的作用，其技能“灵能风暴”可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位

description:
你控制着 $n$ 名高阶圣堂武士，方便起见标为 $1,2, \cdots,n$。每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 $a_i$ 表示其拥有的灵能的多少（$a_i$ 非负表示这名高阶圣堂武士比在最佳状态下多余了 $a_i$ 点灵能，$a_i$ 为负则表示这名高阶圣堂武士还需要 $-a_i$ 点灵能才能到达最佳战斗状态）。现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 $i \in[2,n-1]$，若 $a_i \ge 0$ 则其两旁的高阶圣堂武士，也就是 $i-1$ 、 $i+1$ 这两名高阶圣堂武士会从 $i$ 这名高阶圣堂武士这里各抽取 $a_i$ 点灵能；若 $a_i<0$ 则其两旁的高阶圣堂武士，也就是 $i-1,i+1$ 这两名高阶圣堂武士会给 $i$ 这名高阶圣堂武士 $-a_i$ 点灵能。形式化来讲就是 $(a_{i-1},a_i,a_{i+1})\leftarrow (a_{i-1}+a_i,-a_i,a_{i+1}+a_i)$。

灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 $\max\limits_{i=1}^n\{|a_i|\}$，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。

inputFormat:
本题包含多组询问。输入的第一行包含一个正整数 $T$ 表示询问组数。

接下来依次输入每一组询问。

每组询问的第一行包含一个正整数 $n$，表示高阶圣堂武士的数量。

接下来一行包含 $n$ 个数 $a_1,a_2, \cdots,a_n$。

outputFormat: 输出 $T$ 行。每行一个整数依次表示每组询问的答案。

hint:
**【样例说明】**

对于第一组询问：

对 $2$ 号高阶圣堂武士进行传输操作后 $a_1=3$，$a_2=2$，$a_3=1$。答案为 $3$。

对于第二组询问：

这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。

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

对于所有评测用例，$T \le 3$，$3 \le n \le 3\times10^5$，$|a_i| \le 10^9$。

评测时将使用 $25$ 个评测用例测试你的程序，每个评测用例的限制如下：

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

蓝桥杯 2019 年省赛 B 组 J 题。


title: [蓝桥杯 2019 省 A] 外卖店优先级

description:
“饱了么”外卖系统中维护着 $N$ 家外卖店，编号 $1$ ∼ $N$。每家外卖店都有一个优先级，初始时 $(0$ 时刻）优先级都为 $0$。

每经过 $1$ 个时间单位，如果外卖店没有订单，则优先级会减少 $1$，最低减到 $0$；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 $2$。

如果某家外卖店某时刻优先级大于 $5$，则会被系统加入优先缓存中；如果优先级小于等于 $3$，则会被清除出优先缓存。

给定 $T$ 时刻以内的 $M$ 条订单信息，请你计算 $T$ 时刻时有多少外卖店在优先缓存中。

inputFormat:
第一行包含 $3$ 个整数 $N$ 、 $M$ 和 $T$。

以下 $M$ 行每行包含两个整数 $ts$ 和 $id$，表示 $ts$ 时刻编号 $id$ 的外卖店收到。

一个订单。

hint:
**样例解释**

$6$ 时刻时，$1$ 号店优先级降到 $3$，被移除出优先缓存；$2$ 号店优先级升到 $6$，

加入优先缓存。所以是有 $1$ 家店 $(2$ 号）在优先缓存中。

**评测用例规模与约定**

对于 $80\%$ 的评测用例，$1 \le N,M,T \le 10000$。

对于所有评测用例，$1 \le N,M,T \le 10^5$，$1 \le ts \le T$，$1 \le id \le N$。

蓝桥杯 2019 年省赛 A 组 G 题。


title: [蓝桥杯 2019 省 A] 修改数组

description:
给定一个长度为 $N$ 的数组 $A=[A_1,A_2, \cdots A_N]$，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 $A_2,A_3, \cdots ,A_N$。

当修改 $A_i$ 时，小明会检查 $A_i$ 是否在 $A_1$ ∼ $A_{i-1}$ 中出现过。如果出现过，则小明会给 $A_i$ 加上 $1$；如果新的 $A_i$ 仍在之前出现过，小明会持续给 $A_i$ 加 $1$，直到 $A_i$ 没有在 $A_1$ ∼ $A_{i-1}$ 中出现过。

当 $A_N$ 也经过上述修改之后，显然 $A$ 数组中就没有重复的整数了。

现在给定初始的 $A$ 数组，请你计算出最终的 $A$ 数组。

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

第二行包含 $N$ 个整数 $A_1,A_2, \cdots ,A_N$。

outputFormat: 输出 $N$ 个整数，依次是最终的 $A_1,A_2, \cdots ,A_N$。

hint:
对于 $80\%$ 的评测用例，$1 \le N \le 10000$。

对于所有评测用例，$1 \le N \le 10^5$，$1 \le A_i \le 10^6$。

蓝桥杯 2019 年省赛 A 组 H 题。


title: [CEOI2003] The Race

description:
在一年一度的调谐宇宙飞船星际竞赛中，$N$ 艘宇宙飞船将参赛。每艘宇宙飞船 $i$ 的调谐方式都是这样的，它可以在零时间内加速到它的最大速度 $V_i$ 并继续以那个速度巡航。由于过去的成就，每艘宇宙飞船都从一个起始位置出发，给定其飞船离起跑线的距离。
赛程无限长。因为宇宙飞船速度很快，比赛的路线一直都是笔直的。在直线赛道上，飞船可以很容易地相互通过，而没有互相干扰。
很多观众还没有意识到，比赛的胜负是可以提前预测的。你的任务是向他们展示这一点，告诉他们宇宙飞船将相互经过多少次，并通过按时间顺序预测宇宙飞船经过的前 $10000$ 次。
您可以假设每艘宇宙飞船都从不同的位置开始。此外，任何时候在赛道的同一位置上永远不会有超过两艘飞船。
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/437urrvu.png)

inputFormat: 第一行包含一个整数 $N$ 指定了正在竞争的飞船的数量。接下来的 $N$ 行中的每一行都描述了一艘宇宙飞船的特性。第 $i+1$ 行用两个整数 $X_i$ 和 $V_i$ 描述第 $i$ 艘飞船，表示第 $i$ 艘飞船的起始位置和速度。飞船按照起始位置排序，即 $X_1 < X_2 < \cdots < X_N$。 起始位置是飞船开始的起点线后的公里数，速度以千米每秒为单位。

outputFormat: 第一行应该包含一个整数为飞船在比赛中相互通过的次数，并对 $1000000$ 取模。接下来的每一行都应该按时间顺序表示一个经过。如果要通过 $10000$ 次以上，只输出前 $10000$ 次。如果小于 $10000$ 次，输出所有的次。每一行应该由两个整数 $i$ 和 $j$ 组成，指定飞船 $i$ 经过飞船 $j$。如果多次相互通过同时发生，它们必须按此次赛道位置排序。这意味着发生在起跑线附近的相互通过必须首先列出。路过的时间是两艘宇宙飞船在同一位置的时间

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$0 < N \leq 250 000$，$0 \leq X_i \leq 1 000 000$，$0 < V_i < 100$。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2003 的 [The Race](https://www.ceoi2003.de/www/downloads/therace-en.pdf)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: [蓝桥杯 2019 省 A] 糖果

description:
糖果店的老板一共有 $M$ 种口味的糖果出售。为了方便描述，我们将 $M$ 种口味编号 $1$ ∼ $M$。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 $K$ 颗一包整包出售。

幸好糖果包装上注明了其中 $K$ 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 $N$ 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

inputFormat:
第一行包含三个整数 $N$、$M$ 和 $K$。

接下来 $N$ 行每行 $K$ 这整数 $T_1,T_2, \cdots ,T_K$，代表一包糖果的口味。

outputFormat: 一个整数表示答案。如果小明无法品尝所有口味，输出 $-1$。

hint:
对于 $30\%$ 的评测用例，$1 \le N \le 20$。

对于所有评测样例，$1 \le N \le 100$，$1 \le M \le 20$，$1 \le K \le 20$，$1 \le T_i \le M$。

蓝桥杯 2019 年省赛 A 组 I 题。


title: [蓝桥杯 2019 省 A] 组合数问题

description: 给 $n,m,k$，求有多少对 $(i,j)$ 满足 $1 \le i \le n,0 \le j \le \min(i,m)$ 且 ${i\choose j} \equiv 0\pmod{k}$，$k$ 是质数。其中 ${i\choose j}$ 是组合数，表示从 $i$ 个不同的数中选出 $j$ 个组成一个集合的方案数。

inputFormat:
第一行两个数 $t,k$，其中 $t$ 代表该测试点包含 $t$ 组询问，$k$ 的意思与上文中相同。

接下来 $t$ 行每行两个整数 $n,m$，表示一组询问。

outputFormat: 输出 $t$ 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 $10^9+7$ 的余数。

hint:
**【样例说明】**

在所有可能的情况中，只有 ${2 \choose 1}=2$ 是 $2$ 的倍数。

**【数据规模和约定】**

对于所有评测用例，$1 \le k \le 10^8,1 \le t \le 10^5,1 \le n,m \le 10^{18}$，且 $k$ 是质数。

评测时将使用 $10$ 个评测用例测试你的程序，每个评测用例的限制如下：

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

蓝桥杯 2019 年省赛 A 组 J 题。


title: [CEOI2003] Shift Register

description:
计算机的寄存器存储 $N$ 位用于计算。移位寄存器是一种特殊的寄存器，其位值可以很容易地移位一位。
使用反馈移位寄存器，可以通过以下方式生成二进制伪随机数：大小为 $N$ 的移位寄存器最初填充位值 $a_1,a_2,\cdots,a_N$。每次，寄存器输出其最右边位的值 $a_N$。其他位值向右移动一个位置。第一个位置被分配一个新值 $a_1^{\prime}$，如下所示：
寄存器的每一位都通过一个开关连接到一个异或门（见下图）。对于每个位 $i$，有一个开关 $s_i$（可以是 $1$ 或 $0$），用于确定位值 $a_i$ 是否被转发到 XOR 门。令 $k_i = s_i×a_i$。新值 $a_1^{\prime}$ 被设置为 XOR 门的输出值 XOR（$k_1,\cdots, k_N$）。注：如果 $k_1,\cdots,k_N$ 中 $1$ 的个数为奇数，则 XOR（$k_1,\cdots,k_N$）的值为 $1$，否则为 $0$）。以下是正式定义：
$$a_1^{\prime} = XOR(k1,\cdots,k_N)$$
$$a_i^{\prime} = a_{i−1} \text{ for }2 ≤ i ≤ N$$
$$\text{output} = a_N$$
![TuLi](https://cdn.luogu.com.cn/upload/image_hosting/3fqp3iwp.png)
在上面的例子中，第一次的值 $a_1$ 计算如下：$\text{XOR}(1 \cdot 1,0 \cdot 0,1 \cdot 1,1 \cdot 1,0 \cdot 0,1 \cdot 0,1 \cdot 1) = 0$。
您将获得此类反馈移位寄存器的前 $2N$ 个输出值。从这些值中，您将尝试确定开关值 $s_i$。

inputFormat: 第一行包含一个整数 $N$ 为移位寄存器的大小 。第二行包含 $2N$ 个数字 $0$ 或 $1$，它们是移位的前 $2N$ 个输出位值。

outputFormat: 输出只包含一行。如果有一个开关设置产生给定的寄存器输出值，输出任何此类开关设置的开关值 $s_i$，从 $s_1$ 开始。如果没有这样的开关设置，只输出数字 $-1$。

hint:
#### 数据规模与约定
对于 $100 \%$ 的数据，$1 \leq N \leq 750$。
#### 题目说明
来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2002 的 [Shift Register](https://www.ceoi2003.de/www/downloads/register-en.ps)。
由 @[求学的企鹅](/user/271784) 翻译整理。


title: 交通运输（Wormhole Transportaion）

background:
**本题数据点较多，请勿恶意提交。如发现恶意提交的，可能面临封号的处罚。**

天体风暴过后，永恒大陆的交通急需重建。

description:
永恒大陆上有 $n$ 个基地，基地编号为 $1, 2, \ldots , n$。

现在有 $m$ 条运输任务，第 $i$ 条形如：将货物从基地 $u_i$ 运输到基地 $v_i$。

然而灾后交通并不发达，因此你决定使用虫洞：可以在任意两个不同基地 $x,y$ 之间建立一个虫洞：货物从虫洞的一端传输到虫洞的另一端只需要花费 $1$ 单位的时间。

而且，**运输的方向是双向的**，也就是说，假设建立了一个连接了基地 $a, b$ 的虫洞，那么货物既可以从基地 $a$ 运输到基地 $b$，也可以从基地 $b$ 运输到基地 $a$。

但建立虫洞的代价是昂贵的，你决定只建立**恰好** $\boldsymbol{m - 1}$ 个虫洞，且不能有两个虫洞连接的两个基地完全相同。

你想要知道，在所有的建造方案中， $m$ 条运输任务所花费的时间之和最小能是多少，此外，在花费的时间之和最小的情况下，有多少种建造虫洞的方案。

由于第二个问题的答案可能很大，你只需要输出方案数对 ${10}^9 + 7$ 取模的结果。

inputFormat:
第一行：三个整数 $n,m,t$，其中 $t$ 为子任务编号，对于样例来说 $t=0$。

接下来 $m$ 行：每行两个整数 $u_i,v_i$。

outputFormat:
第一行，一个整数，表示 $m$ 条运输任务所花费的时间之和的最小值。

第二行，一个整数，表示建造虫洞的方案数对 ${10}^9 + 7$ 取模的结果。

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

有三种建造方案。

其中一种是在城市 $1, 2$ 之间建立虫洞，在城市 $2, 3$ 之间建立虫洞，这样，前两条任务的时间都为 $1$，最后一条的时间为 $2$。

另外两种方案是：在城市 $1, 2$ 和 $1, 3$ 之间建立虫洞，或在城市 $1, 3$ 和 $2, 3$ 之间建立虫洞。

---

**【数据范围】**

对于所有数据，$2 \le n \le 2000$，$2 \le n \cdot m \le 2 \times {10}^7$，$1 \le u_i, v_i \le n$，$u_i\ne v_i$。

保证所有无序对 $(u_i, v_i)$ 两两不同，且至少存在一种合法的建造虫洞的方案。

| 子任务编号 | 分值 | $n \le$ | 特殊限制 | 部分分 |
|:-:|:-:|:-:|:-:|:-:|
| $1$ | $10$ | $6$ | 无 | $0$ |
| $2$ | $12$ | $2000$ | $m=n$，且 $u_i=i,\ v_i=i\bmod n+1$ | $3$ |
| $3$ | $12$ | $2000$ | 由所有 $(u_i,v_i)$ 为无向边构成的图为仙人掌森林 | $3$ |
| $4$ | $25$ | $2000$ | 由所有 $(u_i,v_i)$ 为无向边构成的图为杏仁 | $8$ |
| $5$ | $27$ | $300$ | $m\leq 1000$ | $8$ |
| $6$ | $14$ | $2000$ | 无 | $3$ |

仙人掌森林：每条边在至多一个简单环中的无向图。

杏仁：恰好存在两个度数大于 $2$ 的结点，其他结点度数都等于 $2$，且所有环都经过两个度数大于 $2$ 的结点的连通无向图。

当你对于某个子任务的所有测试点，**第一问都回答正确，但第二问没有都回答正确**，你将获得这个子任务的部分分。


title: [COCI2009-2010#4] AUTORI

background: 伟大的科学发现一般是以科学家的姓氏命名，比如说，最流行的非对称密码系统 RSA 是由三位叫做 Rivest、Shamir 和 Adleman 的科学家发现的，而更为熟知的则是 Knuth-Morris-Pratt 算法，这个算法是由三位叫做 Knuth、Morris 和 Pratt 的科学家命名的。

description:
科学论文会大量引用一些早期的著作，因此在一个论文中出现两种不同的命名约定并不少见。这两种不同的命名约定分别是：

- 长变体，由每个作者姓氏的完整单词由连字符连接而成，例如 `Knuth-Morris-Pratt`。
- 短变体，仅由每个作者姓氏的第一个字符拼接而成，例如 `KMP`。

现在，你发现了一篇论文中同时使用了长变体和短变体这两种命名约定，这让你感到很不愉快，因此你想编写一个程序，将所有的长变体变为短变体。

inputFormat:
输入仅一行，一个字符串，代表在论文中出现的长变体。

每一个长变体中的单词开头**一定是大写字母**。

outputFormat: 输出仅一行，一个字符串，代表长变体经过变换以后的短变体。

samples: Knuth-Morris-Pratt KMP

samples: Mirko-Slavko MS

samples: Pasko-Patak PP

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

对于所有数据，满足字符串的长度不超过 $100$，且仅包含大小写英文字母和连字符 `-`。

**【题目来源】**

本题来源自 **_[COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST 4](https://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf) T1 AUTORI_**，按照原题数据配置，满分 $30$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2009-2010#4] PLANINA

background: Mirko 和 Slavko 正在拍摄一部改编自科幻小说 _Chicks in space 13_ 的电影。剧本要求他们呈现出不同的世界，所以他们决定在绿屏幕前拍摄整部电影，之后再添加 CGI 背景。Mirko 听说生成人工地形最好的办法是使用**中点位移算法**。

description:
为了执行这个算法，Mirko 选择了 $4$ 个点组成了一个完美正方形。然后他开始执行以下步骤：

- 在每个正方形的每一条边上，Mirko 都在正中间添加一个新点。这个新点上的地形高度是他所在这条边两个点上的平均高度。
- 在每个正方形的正中间，Mirko 也添加了一个新点。这个新点上的地形高度是所有 $4$ 个正方形定点的平均高度加上一个小的随机值。

Mirko 在执行完一次上面的所有操作后拥有了 $4$ 个新的方块。于是他不断地新建正方形，直到他对结果满意为止。下图说明了算法的初始状态、$1$ 次迭代和 $2$ 次迭代。
![](https://cdn.luogu.com.cn/upload/image_hosting/p16l99h1.png)

Mirko 发现到有些点属于不止一个正方形，为了减少内存消耗，他只存储这些点一次，但是**一旦这个点存储进去了，它就会永远储存在内存中**。现在他想请你编写一个程序，告诉他经过 $n$ 次迭代之后，总共需要在内存中存储多少点。

inputFormat: 输入仅一个整数 $n$，表示迭代的次数。

outputFormat: 输出仅一个整数，表示 $n$ 次迭代后内存内需要存储的点数。

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

对于所有数据，$1\leqslant n\leqslant 15$。

**【题目来源】**

本题来源自 **_[COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST 4](https://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf) T2 PLANINA_**，按照原题数据配置，满分 $50$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2009-2010#4] IKS

background: Mirko 的伟大的曾祖母 Katica 是一位狂热的数学家，她喜欢用数学游戏折磨她的曾孙。

description:
这一天，她在一张纸上写下了一个 $n$ 个数字的序列，并告知 Mirko 可以做如下操作若干次：

- 选取序列中的两个数字（我们不妨称之为 $A,B$），然后选取能整除 $A$ 的质数 $X$。之后，Mirko 把 $A$ 擦去并在原来的位置上写下 $\frac AX$，然后他把 $B$ 擦去并在原来的位置上写下 $B\times X$。

Mirko 希望得到最大分数，因为这样他可以从他的曾祖母那里得到糖果。一个包含 $n$ 个数字的序列的分数是**这 $n$ 个数字的最大公因数**。

Mirko 并不擅长这个，但又很想希望得到糖果，因此找到了你，希望你能编写一个程序计算最大的可能分数，同时他也希望你能够得出在得到最大可能的分数的前提下最少应当执行的操作数。

inputFormat:
输入共两行。

第一行一个整数 $n$，代表序列中的元素个数。
第二行包含 $n$ 个整数，描述 Katica 给 Mirko 的序列。

outputFormat: 输出仅一行两个整数，第一个整数表示 Mirko 最大能够得到的分数，第二个整数表示 Mirko 在能够获得最大的分数的前提下最少应当执行的操作数。

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

对于样例 $1$，Mirko 可以选择序列中的 $4$ 和 $1$ 两个数，并选择 $4$ 的唯一质因子 $2$。之后 Mirko 将 $4$ 和 $1$ 擦去，并在它们原来所在的位置上都写下了 $2$，这样这个序列的分数是 $2$。可以证明这样的方案可以获得最大的分数并且在此前提下操作数最少。

**【数据范围】**

对于所有数据，$1\leqslant n\leqslant 100$，序列中的元素不超过 $10^6$。

**【题目来源】**

本题来源自 **_[COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST 4](https://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf) T3 IKS_**，按照原题数据配置，满分 $70$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: [COCI2009-2010#4] OGRADA

background: Matjia 需要粉刷他的旧篱笆。

description:
篱笆是由 $n$ 块木板做成的，每块木板宽 $1$ 厘米，高度不一。为了方便快捷，他给自己买了一个宽 $x$ 厘米的超级油漆辊。然而超级油漆辊来了一个陷阱——Matija 必须始终使辊子紧密地整个接触木板，否则油漆会滴到四周并污渍所有东西。此外，辊子必须始终与地面平行，以防泄漏。这意味着为了让 Matija 安全地使用压路机，他需要选择 $x$ 块木板，并从最下面的木板的底部到顶部一次涂上油漆。然后，他选择一些其他的木板，油漆它们，以此类推。

这使得一些木板的部分没有上漆。Matija 必须用牙刷刷这些部分。这显然是相当乏味的，所以他请你帮他编写一个程序，求出他需要手动刷漆的最小面积。因为有不止一种方法可以做到这一点，他也想知道需要使用超级油漆辊的最少次数。

inputFormat:
输入共两行。

第一行两个整数 $n,x$，分别代表木板的个数和超级油漆辊的宽度。
第二行 $n$ 个正整数 $h_1,h_2,\dots,h_n$，表示每个木板的高度。

outputFormat:
输出共两行。

第一行一个整数，表示 Matjia 需要手动刷漆的最小面积。
第二行一个整数，表示在手动刷漆的面积最小的前提下，需要使用超级油漆辊的最少次数。

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

对于样例 $1$，Matjia 需要使用两次超级油漆辊。

- 第一次，用超级油漆辊粉刷第 $1,2,3$ 个木板，粉刷高度为 $3\text{ cm}$，因此粉刷面积为 $9\text{ cm}^2$。
- 第二次，用超级油漆辊粉刷第 $3,4,5$ 个木板，粉刷高度为 $4\text{ cm}$，因此粉刷面积为 $12\text{ cm}^2$。

因为两次粉刷有 $3\text{ cm}^2$ 的面积重叠，因此剩下的需要手动粉刷的面积为 $5+3+4+4+5-9-12+3=3\text{ cm}^2$。可以证明这样的方案需要手动粉刷的面积是最小的并且使用超级油漆辊的次数也是最少的。

具体可以结合下图理解：

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

**【数据范围】**

对于所有数据，$1\leqslant n\leqslant 10^6$，$1\leqslant x\leqslant 10^5$，$1\leqslant h_i<10^6$。

**【题目来源】**

本题来源自 **_[COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST 4](https://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf) T4 OGRADA_**，按照原题数据配置，满分 $100$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。


title: 「Wdcfr-1」Yet Another Cirno Game (hard version)

description:
**The only difference between the two versions is whether you have to find a way to get the maximum points.**

Cirno drew a graph. This graph consists of $4\cdot n$ nodes, which are numbered $0$ through $4\cdot n - 1$. Also:

- For $0\le i\le 3$ and $0 \le j, k \lt n$, node $(n\cdot i + j)$ and node $(n\cdot i + k)$ are connected.
- For $0 \le i \le n$ and $0 \le j, k \le 3$, node $(i + n\cdot j)$ and node $(i + n\cdot k)$ are connected.

Cirno called Daiyousei to come and play with her.

The rules for this game are as follows:

- Firstly, Cirno chooses $2\cdot n$ (i.e. half) of the nodes, and she colors them blue. The rest are left red.
- Then there are $2\cdot n$ turns: for each turn Cirno first chooses a blue node, and Daiyousei chooses a red node. If those two nodes are connected, Daiyousei gets a point.

Try to maximize the number of points Daiyousei gets.

inputFormat:
In the first line, $n$ is provided.

In the second line, $n$ numbers follow: they are the nodes that Cirno chose.

outputFormat:
In the first line output $x$, which is the maximum number of points Daiyousei can get.

Then output $2\cdot n$ integers. For each node that Cirno chooses, output the corresponding node that Daiyousei responds with. Obviously the order of the chosen nodes doesn't matter. The solution must get the maximum number of points possible.

translation:
**两个难度之间的唯一区别为是否需要输出对应的匹配方案**

给定 $4n$ 个点，点的编号从 $0$ 到 $4n-1$。每个点有两种属性 $x$ 和 $y$，编号为 $i$ 的点的属性为 $x_i=\left\lfloor\frac{i}{n}\right\rfloor,y_i=i-n\left\lfloor\frac{i}{n}\right\rfloor$。对于每两个点 $i,j(0\le i <j < 4n)$ 之间，若 $x_i=x_j$ 或 $y_i= y_j$，则这两点有一条无向边相连。现有其中 $2n$ 个不同的点被选择，试给每个被选择的点都匹配上另一个点，使得：

- 被匹配到的点未被选择；
- 每个点都只被匹配一次；
- 若每个点与其匹配的点之间有连边，那么记为一分，需要最大化分值。

请输出最大的分值**和对应的匹配方案**。

hint:
### Explanation

In the following picture, nodes in matrices are connected to each other. Cirno chose nodes $0,1,2,3,4,5$.

Arrows below show a possible way for Daiyousei to get the maximum number of points she can get.

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

### Constraints

$1\le n\le 2\times 10^6$.


title: 「MCOI-09」Greedy Deletion

description:
小于等于 $n$ 的正整数形成集合 $S_n=\{1,2,\dots,n\}$。

删除值为 $i$ 的元素代价为 $i^k$，其中每一个元素至多被删一次。

给定正整数 $n$ 和 $k$，求：最小代价使 $S_n$ 乘积变为完全平方数是什么？答案对 $998244353$ 取模。

**注意你需要求最小代价，模 $998244353$，而不是模 $998244353$ 后的代价的最小值。**

你需要回答 $T$ 组询问，其中所有 $k$ 相同。

inputFormat:
第一行三个正整数 $T$，$k$，$\max n$，分别表示询问数量，给定 $k$，以及最大 $n$。

接下来 $T$ 行，每行一个正整数 $n$。

outputFormat: 输出 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案。

hint:
#### 样例 1 解释

对于 $n=1$，$S_1$ 乘积为完全平方数，不需要删除。

对于 $n=6$，可以删除 $5$ 使得 $S_6$ 乘积变为完全平方数。

#### 数据规模与约定

 - Subtask 1（7 pts）：$\max n\le 20$。
 - Subtask 2（37 pts）：$\max n\le 1000$。
 - Subtask 3（11 pts）：$T\le 1000$。
 - Subtask 4（45 pts）：无额外限制。

对于 $100\%$ 的数据，$1\le \max n\le 5\times 10^6$，$1\le T\le 5\times 10^5$，$1\le k< 998244353$。

**保证** $1\le n\le \max n$。


title: [CCC2014] 燃料搜集

description:
英勇的狐狸星小队正在执行任务。他们的任务是从莱拉星系的不同的星球上搜集尽可能多的燃料。莱拉星系里有 $n$ 个星球，第 $i$ 个星球有 $a_i$ 单位燃料，但是从任何星球去那里都要花费 $b_i$ 单位燃料。不幸的是，燃料不是一种可再生资源，所以如果你第二次到访一个星球，你在那里将搜集不到新的燃料。

狐狸星小队在星球 $P$，所以他们可以立马搜集这个星球的燃料，然后他们就可以去执行任务了。只要他们的燃料足够，即完成飞行后他们剩余的燃料量是非负的，他们就可以以任意顺序访问星球。最后，他们可能会在任何星球选择停下来，甚至可能连星球 $P$ 都没离开过就停下来。他们的目标是使搜集到的燃料量最大化，如果有很多种方法可以达到这个目标，他们还想使他们访问过的不同星球的个数最大化，你能帮助他们吗？

inputFormat:
第一行两个整数 $n,P$，以空格分隔，分别表示星球数和起始星球编号。

接下来 $n$ 行每行两个整数 $a_i,b_i$。

outputFormat:
输出包含两行，每行一个正整数。

第一行表示当他们停下来时狐狸星小队能搜集到的燃料的最大值。

第二行表示在搜集到第一行所述燃料量的前提下能访问到的最大的不同星球数。

hint:
一个最优的方案是，狐狸星小队搜集完星球 $2$ 即起点的燃料后从该出发，依次访问并搜集星球 $3,1,5$ 上的燃料，途中花费分别为 $3,12,15$，从起点开始各个星球上完成搜集后剩余燃料分别为 $10,15,15,25$。他们此时不应该选择去星球 $4$ 而是应该选择停下来以使结束时搜集到的燃料量最大化。

对于 $20\%$ 的测试数据，$1\le n\le10$；

对于 $100\%$ 的测试数据，$1\le P\le n\le10^5$，$a_i,b_i\le10^5$ 。


title: [CCC2014] 提前交卷

description:
你正在一个狭窄而又长的礼堂里考试，礼堂一共有 $n$ 排，标号从前到后分别为 $1$ 到 $n$。每排有 $6$ 个座位，左边 $3$ 个，右边 $3$ 个，中间是过道。每个座位都有一个从 A 到 F 的字母标识，其中最左的座位的标识是 A，最右的座位的标识是 F，过道在座位标识为 C 和 D 的座位之间，礼堂同时还有两个保密室，一个在最前面（第一排前面），一个在最后面（第 $n$ 排后面）。

礼堂里的每个座位一开始被刚好一个考生占用。然而，在考试过程中，$m$ 个不同的考生决定完成所有他们会做的题后依次离开礼堂。第 $i$ 个考生在座位 $r_ic_i$，其中 $c_i$ 是 A 到 F 的字母之一。当考生离开礼堂时，他们必须在任意一个保密室等待到考试结束。幸运的是，保密室能容下任意多的考生。

考生不仅关心试题本身，他们还关心怎么样可以最舒服的考试。因此，他们协作以最小化他们的不满度之和。一个考生的不满度的计算方式是 $Ax+By$，其中 $A,B$ 为常数，$x$ 为去往保密室时经过的考生人数，具体将在下面详述，$y$ 是在考生进入保密室之前保密室内的人数。注意如果一个考生不离开他的考位，那么他的不满度为 $0$。

当一个考生从一个考位走往保密室时，他在去往过道时必须先经过同排的考生，然后走过从这行到第一行或第 $n$ 行（取决于所选的保密室）的邻近过道的考生。注意走过空的座位不影响 $x$ 值。

你能帮助他们最小化他们的不满度之和吗？

inputFormat:
第一行四个整数 $n,m,A,B$，以空格分隔，分别表示礼堂内的排数、提前离开的考生数、不满度计算参数。

接下来 $m$ 行每行一个整数 $r_i$ 和一个字母 $c_i$，其中 $1\le i\le n$。

outputFormat: 输出一个整数，表示最小的不满度之和。

hint:
其中一个最优策略是，第一个提前离开的考生去最前面的保密室，经过 $6$ 个考生（分别是 `3D`、`3C`、`2D`、`2C`、`1D`、`1C`），不满度为 $3\times6+4\times0=18$。第二个提前离开的考生也去最前面的保密室，只经过 $1$ 个考生，即 `1C`，然后他发现保密室里有 $1$ 个考生，不满度为 $7$。第三个提前离开的考生去最后面的保密室，经过 $1$ 个考生，不满度为 $3$。第四个提前离开的考生去最前面的保密室，经过 $1$ 个考生（因为座位 `1D` 是空的），不满度为 $11$。最后，第五个提前离开的考生去最后面的保密室，经过 $4$ 个考生，发现保密室里有 $1$ 个人，不满度为 $16$。所有考生总的不满度为 $55$。

对于 $60\%$ 的数据，$1\le m\le5000$；

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le6n$，$1\le A,B\le 10^9$。


title: [CCC2014] 登机口

description:
你现在正在一个有 $G$ 个登机口的机场里，登机口由 $1$ 到 $G$ 编号。第 $i$ 个登机口离机场入口有 $100i$ 米远。

同时机场里还有 $N$ 个水平自动扶梯，第 $i$ 个水平自动扶梯单向地以每分钟 $S_i$ 米从登机口 $A_i$ 到另外一个登机口 $B_i$。在走道的任意一个点，相同方向（朝着机场入口或者远离机场入口）的水平自动扶梯至多只有一条在移动。然而，可能有两条水平自动扶梯从同一登机口出发且同向同终点。

你可以以 $W$ 米每分钟的速度沿着走道走，当你在一个水平自动扶梯的起点时，你可以选择走上去，如果你选择了，它就会把你送到它的终点。即使该自动扶梯经过某个非起点或终点的位置，你不能在该位置离开或开始乘坐该水平自动扶梯。当你在水平自动扶梯 $i$ 上时，你的速度为 $W+S_i$ 米每分钟。

当你在等你晚点的飞机时，为了找乐子，你问了自己 $Q$ 个问题，第 $i$ 个问题为寻找从登机口 $X$ 到登机口 $Y$ 的最短时间。为了使问题更加有趣，你决定不正确回答问题不登机，因此你最好不要把事情搞砸了！

inputFormat:
第一行四个整数 $G,W,N,Q$，分别表示登机口数量、走路速度、水平自动扶梯数量、询问数量。

接下来 $N$ 行每行三个整数 $A_i,B_i,S_i$，表示水平自动扶梯 $i$ 的起点和终点以及水平自动扶梯的速度。其中 $A_i\ne B_i$。

接下来 $Q$ 行每行两个整数 $X,Y$，表示起始登机口和目标登机口。

outputFormat:
输出 $Q$ 行，每行一个实数，表示从登机口 $X$ 到登机口 $Y$ 最少要多少分钟。

你的结果的正确性将以如下方式进行判断：如果 $D$ 是标准答案，那么在范围 $[D\times (1-10^{-4}),D\times (1+10^{-4})]$ 内的结果都被认为是正确的。

hint:
对于第一个询问，你只需要从登机口 $3$ 走到登机口 $2$ 即可，两登机口间距离为 $100$ 米，你的速度为 $10$ 米每分钟。

对于第二个询问，你应该乘坐从登机口 $2$ 到登机口 $3$ 的水平自动扶梯，距离为 $100$ 米，你的速度为 $25$ 米每分钟。

对于第三个询问，你应该花费 $10$ 分钟走去登机口 $2$，然后花费 $4$ 分钟乘坐询问 $2$ 所述水平自动扶梯，接着花费 $10$ 分钟走去登机口 $4$。

对于第四个询问，你应该花费 $1.25$ 分钟乘坐从登机口 $4$ 到登机口 $2$ 的水平自动扶梯，然后花费 $4$ 分钟坐登机口  到登机口 $2$ 的水平自动扶梯，最后花费 $3$ 分钟坐从登机口 $1$ 到登机口 $6$ 的飞机。

对于某些数据，$G,N,Q$ 中至少一个值是较小的。这个信息也许有用，也许没用。

对于 $100\%$ 的数据，$1\le A_i,B_i,X,Y\le G\le 10^9$，$1\le N,Q\le10^5$。


title: 「Wdoi-2」灵山之上神风起

background:
在天狗记者射命丸文的指（放）引（水）之下，灵梦一行人找到了山中的神社。

“在妖怪之山上还真的存在其他的神社啊。”灵梦感慨道。她们看到了由树木建造的神社正殿，以及正殿前的参拜道上的一排御柱，而更远处则是一片湖——风神之湖。湖面非常开阔，波光粼粼，一碧万顷，远处似乎有群山环抱，让人心旷神怡。

到达神社之时已经是傍晚了。正当灵梦和魔理沙感慨之时，见到在她们面前有一位白衣蓝裙的少女，东风谷早苗，拥有着引发奇迹程度的能力。为了找到守矢神社中的两位神灵，灵梦与魔理沙，向东风谷早苗产生了激烈的交战。

“那就在现人神的力量洗礼中思索吧！这召唤奇迹的神明之力！”

description:
### 简要题意

给定一个长度为 $n$ 的正整数序列 $a$ 满足对于所有 $i\in [1,n]$ 有 $a_i \in \{1,2,3\}$。

现在通过该序列构造一张含 $n$ 个节点，节点编号为 $1$ 到 $n$ 的图：对于数 $i$，如果 $a_i=1$，那么什么都不做；如果 $a_i=2$，那么向所有比 $i$ 小的数的节点连无向边；如果 $a_i=3$，那么向所有比 $i$ 大的数的节点连无向边。求出该图的最大独立集的大小。

最大独立集，指的是原图中一个点数尽量多的点集，这些点在原图中两两之间没有边**直接**相连。

### 原始题意

然而，东风谷早苗（后称早苗）的弹幕密度相当之高，使人应接不暇，灵梦只得想个方法去减少她需要关注的弹幕数量。

数个回合过后，她发现，早苗每次释放弹幕只会释放出 $n$ 个弹幕，分别编号为 $1,2,\dots,n$，而她每释放一个弹幕，都会对应着产生一次神力波动。因而她的神力波动可以抽象为一个长度为 $n$ 的正整数数列 $\{a_n\}$。由于她的资历尚浅，只会使用三种神力，分别用 $1,2,3$ 表示，即 $\forall i \in [1,n]$，$a_i \in \{1,2,3\}$。

她发现，早苗的三种神力作用各不相同，具体而言如下：

- 当 $a_i=1$ 时，她不会做任何事情。
- 当 $a_i=2$ 时，早苗会让第 $i$ 个弹幕向所有弹幕编号**小于** $i$ 的弹幕建立神力输送通道。
- 当 $a_i=3$ 时，早苗会让第 $i$ 个弹幕向所有弹幕编号**大于** $i$ 的弹幕建立神力输送通道。

接着，在各种神力的交互配合之下，密集的弹幕将展开于灵梦的眼前。而一旁的魔理沙发现，若是从这些弹幕中挑选出**尽可能多的**一群弹幕，使得每个弹幕之间不存在直接相连的神力输送通道，那么这群弹幕会产生【引发奇迹程度的能力】，是不必关注的。

由于【引发奇迹程度的能力】只能被触发**一次**，灵梦和魔理沙想要知道，**最多**有多少个弹幕是不必关注的。她们找到了你，希望你能帮她解答。

inputFormat:
- 第一行，输入一个正整数 $n$，表示弹幕总数。
- 第二行，输入 $n$ 个正整数表示 $a_i$，具体含义见题目描述。

outputFormat: - 共一行，输出一个正整数，表示**最多**有多少个弹幕是不必关注的。

hint:
### 样例解释

根据题意显然可以构造出如下的图。其中 $a_i=2$ 的用蓝色边表示，$a_i=3$ 的用红色边表示。

显然选取第 $2,3$ 个弹幕（已用绿色填图）是最多的情况。实际上对于这个样例，选取弹幕的方案不止一种，但是不存在更多的情况了。

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

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值}\\\hline
1 & 10 & - & 20\\\hline
2 & 10^5 & \text{A} & 10\\\hline
3 & 10^5 & \text{B} & 30 \\\hline
4 & 10^5 & - & 40 \\\hline
\end{array}$$

- 特殊性质 $\text{A}$：所有的 $a_i=1$；
- 特殊性质 $\text{B}$：所有的 $a_i$ 不是 $1$ 就是 $2$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$a_i \in \{1,2,3\}$。


title: [COCI 2011-2012#5] KRIŽALJKA

description:
有两个单词 $A,B$，将 $A$ 水平摆放，$B$ 竖直摆放，两个单词重叠部分必须为**同一字母**，且这一字母须在 $A,B$ 中第一次出现。

例如，当 `A="ABBA",B="CCBB"` 时，输出如下所示：

```
.C..
.C..
ABBA
.B..
```

inputFormat: 一行，两个字符串，由大写字母组成，分别表示 $A$ 和 $B$。

outputFormat:
一个矩阵，表示摆放结果。

其中无字符用 `.` 表示。

hint:
数据保证有解。

字符串由大写字母构成。

题目译自 [COCI 2011/2012 #5 T1](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。


title: [COCI 2011/2012 #5] DNA

description:
有一个由 $A,B$ 组成的 $N$ 个字母的序列。

每次操作可以有两种情况：

1. 改变序列中的一个字符 （$A\to B$ 或 $B\to A$）；

2. 改变序列的前缀，即对 $1$ 到 $K(1\le K\le N)$ 的字符进行操作 1。

求最少进行多少次操作可以使序列全部为 $A$。

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

第二行 $N$ 个字符，表示该序列。

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

hint:
$1\le N\le 10^{6}$。

序列仅由 `'A','B'` 构成。

题目译自 [COCI 2011/2012 #5 T3](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。


title: [COCI2011-2012#3] DIGITALNA

background: 由于答案不唯一，**本题使用 SPJ 评测**。

description:
不久前，Mirko 的祖父母不得不从模拟电视接收器切换到数字电视接收器。在他们的旧模拟电视接收器上，他们只能观看两个频道——BLJTV1 和 BLJTV2。换成数字接收器后，他们获得了几十个新的频道，但他们仍然想只看以前的两个频道。他们要求 Mirko 调整频道菜单，使 BLJTV1 在第一个频道，BLJTV2 在第二个频道上。开机后，数字接收器会创建一个可用频道的列表。所有的频道都是不同的，列表中总是包含 BLJTV1 和 BLJTV2。Mirko 找到了遥控器后开始调整菜单。菜单中包含了频道列表和一个标着当前选择频道的箭头。进入菜单后，箭头标志着列表中的第一个频道。菜单中有四种操作，每种操作在操作序列中用其前面的编号表示：

1. 将箭头向下移动一个位置（从频道 $i$ 到频道 $i+1$）；
2. 将箭头向上移动一个位置（从频道 $i$ 到频道 $i-1$）；
3. 将箭头和选定的频道向下移动一个位置（频道 $i$ 和频道 $i+1$ 交换位置，箭头在频道 $i+1$ 的位置结束）；
4. 将箭头和选定的通道向上移动一个位置（频道 $i$ 和频道 $i-1$ 交换位置，箭头在频道 $i-1$ 的位置结束）。

菜单是稳定的，所以无效的命令（如将箭头移到频道列表之外的命令）都将被忽略。

编写一个程序，给定一个频道列表，输出一个任何操作的序列，使其在执行后，BLJTV1 在频道列表的第一个位置，BLJTV2 在第二个位置。此外，该序列的长度应小于 $500$。所有其他频道的排序是**任意的**。

inputFormat:
输入共 $n+1$ 行。

第一行一个整数 $n$，表示频道个数。
随后 $n$ 行，每行一个字符串 $s$，表示频道的名字。

输入数据保证所有频道中一定有 BLJTV1 和 BLJTV2 这两个频道，并且**一定存在至少一种**可行的操作序列。

outputFormat: 输出仅一行，一个字符串，表示能够达到要求的操作序列。

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

对于所有数据，$2\leqslant n\leqslant 100$，频道名字长度不超过 $10$，且仅包括大写英文字母和数字。

**【题目来源】**

本题来源自 **_[COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST 3](https://hsin.hr/coci/archive/2011_2012/contest3_tasks.pdf) T1 DIGITALNA_**，按照原题数据配置，满分 $50$ 分。

由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。

感谢 [yzy1](https://www.luogu.com.cn/user/207996) 提供本题的 SPJ。