title: [COCI2006-2007#4] SIBICE

background: 年轻的 Mirko 把火柴扔的到处都是。他的母亲希望他将火柴放入盒子中。

description:
Mirko 现在要放置 $n$ 根火柴，他有一个 $w\times h$ 的矩形盒子。

他现在想请你进行判断这 $n$ 根火柴每一个是否能够放入这个盒子。

我们可以把盒子看成一个平面，只需要判断火柴是否能够在这个平面内放下即可。

inputFormat:
输入第一行为三个整数 $n,w,h$。

接下来的 $n$ 行，每行一个 $[1,1000]$ 区间内的整数，表示一根火柴的长度。

outputFormat: 输出共 $n$ 行，对于每根火柴，输出 `DA` 表示能放下，否则输出 `NE` 表示放不下。

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

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

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T1 SIBICE***


title: [COCI2006-2007#4]  SKENER

type: P

background: Mirko 在拿放大镜看杂志。

description:
他正在看一面 $r$ 行 $c$ 列的杂志。放大镜有两个参数 $zr,zc$，表示把每个字符都转换成一个 $zr$ 行 $zc$ 列的矩阵。

给出原始杂志，请你帮他找出杂志在放大镜下的影像。

inputFormat:
输入第一行四个整数 $r,c,zr,zc$。

接下来的 $r$ 行，每行 $c$ 个字符。字符可能为数字，字母或 `.`。

outputFormat: 输出一个 $r\times zr$ 行，$c\times zc$ 列的矩阵，表示放大镜下的影像。

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

对于 $100\%$ 的数据，保证 $1\le r,c\le 50$，$1\le zr,zc\le 5$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T2 SKENER***


title: 「Wdoi-1」四重存在

background:
芙兰朵露·斯卡蕾特的符卡禁忌「四重存在」可以产生 $4$ 个芙兰的幻影。

但是芙兰并不满足于此。

description:
芙兰所处的地下室可以被抽象为一个巨大的平面直角坐标系。芙兰朵露会进行 $q$ 次行动，每次行动的形式如下：

- `1 x y v` 表示芙兰在坐标 $(x,y)$ 处召唤出一个新的幻影，这个幻影拥有 $v$ 个单位的力量。

- `2` 表示查询现有的幻影中，"**芙兰距离**"的最大值是多少。

- `3 a` 表示查询如果忽略掉第 $a$ 个被召唤出的幻影，则剩余的幻影中"芙兰距离"的最大值是多少 。

注：

记第 $i$ 个被召唤出的幻影编号为 $i$，坐标为 $(x_i,y_i)$，力量为 $v_i$。

两个编号为 $u,v$ 的幻影间的"芙兰距离"等于 $|x_u-x_v|+|y_u-y_v|+v_{\max(u,v)}$。

**特殊地，编号为 $i$ 的幻影与自己的"芙兰距离"为 $v_i$。**

$3$ 操作中第 $a$ 个召唤的幻影只是在本次询问中不参与运算，而不是被去除。

inputFormat:
第一行一个整数 $q$，表示操作个数。

之后 $q$ 行，每行若干个整数，输入格式与题目描述一致。

**注意**：由于芙兰朵露的情绪并不稳定，因此在 $1$ 操作中，实际输入的

$$x'=x \operatorname{ xor } (\text{lastans} \bmod 3)$$

$$y'=y \operatorname{ xor } (\text{lastans} \bmod 3)$$

$$v'=v \operatorname{ xor } (\text{lastans} \bmod 3)$$

其中的运算含义如下：

- $\operatorname{xor}$ 表示异或运算。

- $\text{lastans}$ 表示上一次 $2$ 或 $3$ 操作的答案，初始时 $\text{lastans}=0$

outputFormat: 输出一共若干行，每行一个整数，为每个 $2$ 操作或 $3$ 操作的答案。


title: [COCI2006-2007#4] PRSTENI

description:
有 $n$ 个半径不同的圆环，把它们依次放在地上摆成一行，使得除了第一个和最后一个环，其他的圆环都能接触到相邻两个环。

请你求出当第一个环转动了 $1$ 圈时，其他每个环都转动了多少圈。

由于答案可能不是整数，所以请用最简分数的形式表示，格式见样例。

inputFormat:
输入第一行为一个整数 $n$，为圆环的个数。

第二行为 $n$ 个整数，依次表示每个圆环的半径。

outputFormat: 输出共 $n-1$ 行，表示除第一个圆环外，其他圆环所转动的圈数。

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

对于 $100\%$ 的数据，保证 $3\le n\le 100$，半径长度在 $1\sim 1000$ 之间（含端点） 。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T3 PRSTENI***


title: [COCI2006-2007#4] ZBRKA

description: 在一个长度为 $n$ 的排列中找出逆序对数量恰好为 $c$ 的排列总数。（$\bmod \ 10^9+7$）

inputFormat: 输入共一行为两个整数 $n,c$。

outputFormat: 输出逆序对数量恰好为 $c$ 的排列总数。（$\bmod \ 10^9+7$）

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

对于 $100\%$ 的数据，保证 $1\le n\le 10^3$，$1\le c\le 10^4$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T4 ZBRKA***


title: [COCI2006-2007#4]  JOGURT

description:
给定一棵完全二叉树，共 $n$ 层。

我们将根节点记为在第 $0$ 层，根节点的两个子节点记为在第 $1$ 层，以此类推。

现在，我们要把 $1\sim 2^n-1$ 这 $2^n-1$ 个数字不重复无遗漏的分别填入每个节点，使得对于任意的 $d$，以第 $d$ 层的一个节点为根，它的左右子树分别的数字之和的差的绝对值等于 $2^d$。

请你给出一个可行的方案，只需输出这个方案的[先序遍历](https://baike.baidu.com/item/%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86/6442839?fr=aladdin)即可。

inputFormat: 输入一行一个整数 $n$，表示树的层数。

outputFormat:
输出一行 $2^n-1$ 个 $1\sim 2^n-1$ 的整数，用空格隔开，为一个可能的先序遍历。

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

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

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

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T5 JOGURT***

感谢 @[一扶苏一](https://www.luogu.com.cn/user/65363) 提供SPJ！


title: [PA2011] Hard Choice

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

有 $q$ 次询问，每次询问包含一个字符 $opt$ 和两个整数 $x,y$。

若 $opt$ 为 $Z$，表示一次删除操作，删去边 $x,y$，保证 $x,y$ 这条边之前没有被删除，但不保证图上存在边（也就是说，可能会删去所有的边）。

若 $opt$ 为 $P$，表示一次询问，询问 $x,y$ 之间是否有两条完全不同的路径，这里的完全不同指没有经过相同的边，但可以经过相同的点。

inputFormat:
第一行三个整数 $n,m,q$，意义同题面。

接下来 $m$ 行，每行两个数 $x,y$，表示 $x,y$ 之间存在一条无向边。

接下来 $q$ 行，每行包含一个字符 $opt$ 和两个整数 $x,y$，意义同题面。

outputFormat: 对于每一次 $opt$ 为 $P$ 的询问，如果存在两条完全不同的路径，输出一行一个字符串 TAK，否则输出一行一个字符串 NIE。

hint: $2\leq n\leq 10^5$，$1\leq m,q\leq 10^5$，保证输入数据合法且不存在重边和自环。


title: [PA2011] Kangaroos

description:
给出长为 $n$ 的序列 $a$，第 $i$ 个元素是一个区间 $[l_i,r_i]$。

$m$ 次询问，给出 $A,B$，求出 $a$ 中最长的区间（即这个序列中的一段），使得这个区间内每个区间都与 $[A,B]$ 有交集。输出这个最长区间的长度。

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

接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$。

接下来 $m$ 行，每行两个整数 $A,B$，为一次询问。

outputFormat: 输出 $m$ 行，每行一个整数，为询问的答案。


title: [COCI2006-2007#4]  ISPITI

background: Mirko 的村子要进行一场考试。

description:
考试在即，学生们赶快加紧了复习的进度。每个学生都有两个能力系数 $A\ B$。

我们认为一个学生会向另一个学生求助，当且仅当另一个学生的 $A$ 和 $B$ 都不小于这个学生。

现在给出 $n$ 条指令，有以下两种类型：

- `D A B` 来了一个学生，他的两个能力系数为 $A$ 和 $B$。

- `P i` 第 $i$ 个学生想知道找谁帮忙。为了不大材小用，如果有多人可以求助，他会首先选择系数 $B$ 相差最小的。如果 $B$ 相同，则首选 $A$ 相差最小的。

其中学生的编号由入场的顺序从 $1$ 开始依次编排。

inputFormat:
输入第一行为一个整数 $n$ ，表示指令的总数。

接下来的 $n$ 行，每行一个指令，具体格式参照题目描述。

保证不会存在任意两个学生的两个指数都相同。

outputFormat: 对于每一个 `P i`，输出一个整数，为第 $i$ 个学生想向哪个编号的学生求助。如果这个学生没有可以求助的对象，则输出 `NE`。

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

对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$1\le A,B\le 2\times 10^9$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T6  ISPITI***


title: [PA2011] Laser Pool

description:
在一个 $n\times m$ 的网格（左下角为 $(1,1)$，右上角为 $(m,n)$）里有一个小球（可以视为一个点），其中横向和纵向都有一些光线，$q$ 次询问，每次给出小球的初始位置，方向，速度和运动时间（具体方式见输入格式），求出小球触碰光线的次数，如果碰到交点只算一次。

当小球触碰到边界时，会发生反弹，也就是说，假设当前每秒 $x$ 坐标增加 $vx$，$y$ 增加 $vy$，如果碰到上下边界，则 $vy$ 变为 $-vy$，如果碰到左右边界，将 $vx$ 变为 $-vx$，如果仍不理解可以见样例解释的图片。

inputFormat:
第一行两个整数 $n,m$，表示网格的行数和列数。

接下来一行一个长为 $n$ 的 $01$ 串，如果第 $i$ 个数为 $1$，则表示这一行有光线，否则表示没有。

接下来一行一个长为 $m$ 的 $01$ 串，如果第 $i$ 个数为 $1$，则表示这一列有光线，否则表示没有。

接下来一行一个数 $q$，表示询问次数。

下面 $q$ 行，每五个整数 $x,y,vx,vy,t$ 表示小球初始时在 $(x,y)$，每秒 $x$ 增加 $vx$，$y$ 坐标增加 $vy$，总共运动 $t$ 秒。保证 $vx,vy$ 均为 $1$ 或 $-1$。

outputFormat: 对于每一次询问，输出一行一个数，表示小球触碰光线的次数。

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

$1\leq n,m\leq 10^5$，$1\leq q\leq 10^4$，$1\leq t \leq 10^9$，保证球的初始位置在网格内且不在边界上，$vx,vy$ 均为 $1$ 或 $-1$。


title: [CCO2017] 接雨滴

description:
晚上，夜黑风高，大雨疯狂地从天而降。

Lucy 想要接住一些雨滴，但她只有有限的工具。她有一套不同高度的柱子来接住雨滴。每根柱子的高度为整数，宽度为 $1$。她排列好柱子之后，就会用其他器具夹紧柱子，来让雨滴顺利地储存在柱子的间隙里。你可以认为雨滴的数量是无限的。

举个例子，如果 Lucy 有高度分别为 $(1,5,2,1,4)$ 的五根柱子，她可以这样排列柱子。

```
 *
 *  *
 *  *
 ** *
*****
```

这样会接住 $5r$ 雨滴（$r$ 代表 $1$ 个单位的雨滴）。

**为了方便表述，我们定义 $r$ 为雨滴的单位。**

```
 *
 *RR*
 *RR*
 **R*
*****
```

当然了，她也可以这样摆放柱子，这样可以接住 $6r$ 雨滴。

```
 *
 *RR*
 *RR*
**RR*
*****
```

再举一个例子，如果柱子的高度分别为 $(5,1,5,1,5)$，Lucy 可以接住 $8r$ 雨滴。

```
*R*R*
*R*R*
*R*R*
*R*R*
*****
```

最后一个例子，如果柱子的高度分别为 $(5,1,4,1,5)$，她可以接住 $9r$ 雨滴。

```
*RRR*
*R*R*
*R*R*
*R*R*
*****
```

Lucy 有 $n$ 个高度为 $h_1,h_2,...,h_n$ 的柱子。她想知道，在所有可能的摆放方案中，所有可能的雨滴量（以 $r$ 为单位）是多少。（具体可看样例解释）

inputFormat:
第一行有一个整数 $n$，表示柱子的个数；

第二行包含 $n$ 个整数 $h_i$，表示柱子的高度 。

outputFormat: 输出只有一行，把所有可能接住的雨滴数量（以 $r$ 为单位）按照升序输出。

hint:
#### 样例解释

参见上文的三个例子。

#### 数据范围及约定

**本题采用多测试点捆绑测试，共有 $3$ 个子任务。**

- Subtask 1（20 points）：$2 \le n \le 10$；
- Subtask 2（40 points）：$2 \le n \le 50$；
- Subtask 3（40 points）：$2 \le n \le 500$，$1 \le h_i \le 50$。

对于全部的测试点，保证 $2 \le n \le 500$，$1 \le h_i \le 50$。

来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/) Day2「[Rainfall Capture](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day2.pdf)」。

说明：翻译来自 [LOJ](https://loj.ac/problem/2753)。


title: [CCO2017] 专业网络

description:
Kevin 正在一个社区中开发他的专业网络。不幸的是，他是个外地人，还不认识社区中的任何人。但是他可以与 $n$ 个人建立朋友关系 。

然而，社区里没几个人想与一个外地人交朋友。Kevin 想交朋友的 $n$ 个人都有类似但不同的与外地人交友的准则。在 Kevin 已经直接认识了社区中的 $a_i$ 个人后，第 $i$ 个人就愿意与 Kevin 交朋友了，否则 Kevin 就要付出 $b_i$ 的代价与他成为朋友。

你的任务是，使 Kevin 与这 $n$ 个人都交上朋友，并且最小化他付出的代价。

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

接下来的 $n$ 行，每行包含两个整数 $a_i,b_i$。

outputFormat: 输出一行一个整数，表示 Kevin 付出的最小代价。

hint:
#### 样例解释

对于样例 $1$：Kevin 可以立即与 $3$ 号人成为朋友，因为已经建立了这个朋友关系，他也能与 $2$ 号人成为朋友。他需要付出 $3$ 的代价与 $1$ 号人成为朋友，这样他一共有 $3$ 个朋友，使得他能与 $4$ 号人成为朋友。

对于样例 $2$：Kevin 不用付出任何代价就能和所有人成为朋友。

对于样例 $3$：Kevin 应该立即与 $1$ 号人成为朋友，然后付出 $8$ 的代价与 $3$ 号人成为朋友， 最后与 $2$ 号人建立朋友关系。

#### 数据范围及约定

**本题采用多测试点捆绑测试，共有 $4$ 个子任务。**

- Subtask 1（15 points）：所有的 $b_i$ 都等于 $1$；
- Subtask 2（30 points）：$1 \le n \le 10$；
- Subtask 3（30 points）：$1 \le n \le 10^3$。
- Subtask 4（25 points）：$1 \le n \le 2 \times 10^5$。

对于全部的测试点，保证 $1 \le n \le 2 \times 10^5$，$1 \le i \le n$，$0 \le a_i \le n$，$0 \le b_i \le 10^4$。

来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/) Day2「[Professional Network](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day2.pdf)」。

说明：翻译来自 [LOJ](https://loj.ac/problem/2754)。


title: [CCO2017] 移动数组

description:
给你一个二维数组。我们只能通过 **移动(Shift)** 操作来改动这个数组。一次移动操作可以将一行元素向左（或向右）移几个单位；或将一列元素向上（或向下）移几个单位。如果被移动的元素越界，则将越界元素移动到该行或列的另一侧。

举个例子：

```
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
```

将第二列向下移动 $1$ 个单位（或向上移动 $3$ 个单位），二维数组将会变成这样：

```
0 13 2 3
4 1 6 7
8 5 10 11
12 9 14 15
```

一次移动 $k$ 个单位的 **左移** 操作等价于移动 $n-k$ 个单位的 **右移** 操作。在列上的变换同样。

因此，我们规定只有 **下移** 和 **右移** 操作。

在一个 $n \times m$ 的二维数组中，所有的数各不相同，且 $Num_{ij} \in [0,n-1]$（规定第 $i$ 行 $j$ 列的数编号为 $Num_{ij}$）。

在第一个例子中，我们给你的二维数组非常 **和谐**，我们叫它 **和谐数组 (Solved)**。一个二维数组当且仅当第一行的元素按照升序编号分别为从 $0$ 到 $m-1$，第二行元素为从 $m$ 到 $2m-1$，以此类推时，我们称它为 **和谐数组**。

你的任务是找到一系列的操作，使得二维数组变成 **和谐数组**。

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

下面的 $n$ 行将会包含 $m$ 个代表二维数组的正整数。

outputFormat:
第一行输出移动的步数 $k$（$1\leq k\leq 10 ^ 5$）。

下面的 $k$ 行输出：`1 i r` （$1 \le i \le n$，$0 \le r < m$），代表使第 $i$ 行 **右移** $r$ 格，或 `2 j d` （$1 \le j \le m$，$0 \le d <n$），代表使第 $j$ 列 **下移** $d$ 格。

如果数组本身就是和谐数组，输出 $0$。

hint:
#### 样例解释

对于样例 $1$：经过如下变换

```
4 2 3 0  -> 1 2 3 0 -> 0 1 2 3
1 5 6 7     4 5 6 7    4 5 6 7
```

对于样例 $2$：经过如下变换

```
2 3      3 2      6 2      6 2      6 2      1 2      2 1      0 1
5 0   -> 5 0   -> 3 0   -> 0 3   -> 0 3   -> 4 3   -> 4 3   -> 2 3
4 1      4 1      5 1      5 1      1 5      6 5      6 5      4 5
6 7      6 7      4 7      4 7      4 7      0 7      0 7      6 7
```

#### 数据范围及约定

**本题采用多测试点捆绑测试，共有 $3$ 个子任务。**

- Subtask 1（20 points）：$2 \le n \times m \le 8$；
- Subtask 2（40 points）：$1 \le k \le 2$；
- Subtask 3（40 points）：无特殊限制。

对于全部的测试点，保证 $2 \le n,m \le 100$，$1 \le k \le 10^5$，保证 $n,m$ 为偶数。

来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/) Day2「[Shifty Grid](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day2.pdf)」。

说明：翻译来自 [LOJ](https://loj.ac/problem/2755)。


title: [COCI2007-2008#1]  CETVRTA

description:
给出坐标系中一个矩形的三个顶点的坐标，请你确定第四个顶点的坐标并输出。

保证矩形的边与坐标轴平行。

inputFormat: 共 $3$ 行，每行两个 $1\sim 1000$ 之间的整数（含端点），表示这个矩形一个顶点的坐标。

outputFormat: 输出一行两个整数，表示第四个顶点的坐标。

hint:
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #1](https://hsin.hr/coci/archive/2007_2008/contest1_tasks.pdf) *T1 CETVRTA***


title: [COCI2007-2008#1]  PEG

description:
给定一个 $7\times 7$ 的矩阵，表示一个跳棋棋盘。

其中，棋盘的第一二行和倒数第一二行的首位两列都是空格（如果不能理解可观察样例），其余格子 `o` 表示有棋子，`.` 表示没有。

每次对于一个棋子，如果它的上、下、左、右有相邻的棋子，且那个方向棋子的另一面是个空格，那么它就可以跳过去，并把那一块被跳跃的棋子从棋盘上拿走，记为一次移动。

请你求出这个棋盘最多能进行多少次移动。

inputFormat: 输入一个棋盘。

outputFormat: 输出最多能移动的次数。

samples:
  ooo
  ooo
ooooooo
ooo.ooo
ooooooo
  ooo
  ooo

samples:
  ooo
  ooo
..ooo..
oo...oo
..ooo..
  ooo
  ooo

hint:
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #1](https://hsin.hr/coci/archive/2007_2008/contest1_tasks.pdf) *T2 PEG***


title: [传智杯 #2 初赛] 软件工程实习

description:
某大学的《软件工程》必修课分为理论和实践部分。理论部分由该校教授完成授课；而实践部分是由第三方的公司主导，需要同学们在五周时间内自学 HTML、css、JavaScript、vue、Python、django 等技术，并组队完成一个真实的互联网商业应用。

参与这个课程的有 $n(0\le n \le 1000)$ 个学生，分成了不超过 $26$ 个队伍，每个队伍用 `A` 到 `Z` 来表示。每个队伍都会完成一个项目，并以队伍为单位，给所有队伍（包括自己队伍）打分，范围是 $0$ 到 $100$ 的整数。

为了平息学生对这门课产生的出多问题的不满（比如工作量太大、时间过于紧张、考核方式不公平等），老师决定使用一种“看起来”很公平的方式来决定每组队伍的项目得分：

对于某个队伍，首先计算所有队伍（包括自己）给这个队伍评分的平均值，然后剔除掉和这个平均值差别超过 $15$ 分的评分（保证不会出现所有的评分全部被剔除的情况），最后再对剩余的评分求平均值，四舍五入取整后作为这个队伍的项目得分。

对于每一个同学，我们已经得知他们的队伍代号和理论成绩（也是 $0$ 到 $100$ 分的整数）。这位同学的最后得分就是 $60\%$ 的理论成绩加上 $40\%$ 的所在队伍的项目得分，然后四舍五入取整。

现在老师想知道所有同学的分数排行。请按最后得分从高到低的顺序，输出每位同学的得分和他所在的队伍。

inputFormat:
第一行两个整数 $n$ 和 $k$，分别表示学生数和队伍数。

接下来 $n$ 行，每行一个整数 $s_i$ 和一个大写字母 $c_i$，表示第 $i$ 个选手的理论分数和队伍编号。保证队伍编号范围是从 `A` 开始后连续 $k$ 个字母中的一个。

接下来 $k$ 行，每行 $k$ 个整数。其中第 $i$ 行第 $j$ 列的整数 $a_{i,j}$ 表示第 $i$ 个队伍给第 $j$ 个队伍的评分，当 $i=j$ 时，就是自评。

outputFormat: 输出 $n$ 行表示答案，得分高的同学优先输出，得分相同时队伍编号较小的同学优先输出。对于每一行，先输出这位同学成绩，然后输出代表他的队伍编号的大写英文字母。

hint:
A 组收到的分数分别是 $70,95,30$，其平均分为 $65$，则 $95,30$  被作为无效成绩剔除，因此 A 组的项目得分是 $70$ 分。
B 组收到的分数分别是 $90,88,47$，其平均分为 $75$，则 $47$  被作为无效成绩剔除，因此 B 组的项目得分是 $89$ 分。
C 组收到的分数分别是 $100,85,100$，其平均分为 $95$，没有打分被剔除，因此 C 组的项目得分是 $95$ 分。


title: [传智杯 #2 初赛] 1024 程序员节发橙子

description:
每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。

班级里有 $n$ 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 $i$ 名同学的成绩是 $a_i$。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求：

- 相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。
- 每个同学至少分配一个橙子

由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？

inputFormat:
第一行是一个整数 $n$，表示学生数量。

接下来一行有 $n$ 个整数，第 $i$ 个整数 $a_i$，表示第 $i$ 个同学的成绩。

outputFormat: 输出答案，也就是需要最少准备多少个橙子。

hint:
#### 样例 1 解释

每位同学拿到的橙子的数量分别是 $1,2,3,2,1$，所以至少需要准备 $9$ 个。

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10^6$，$0 \leq a_i \leq 10^9$。


title: [传智杯 #2 初赛] 众数出现的次数

description:
传智专修学员的课堂上，为了活跃气氛，并巩固位运算的知识，同学们玩起了一个游戏。

班级里有 $n(n\le10^6)$ 名同学，每位同学都获得了两张卡，红卡或者黑卡。每张卡上都有一个不超过 $10^9$ 的非负整数。第 $i$ 位同学手里红卡数字是 $a_i$ ，黑卡数字是 $b_i$。

现在需要每位同学出牌。每位同学可以直接将红卡上的数字打出，或者将自己的红卡上的数字和自己黑卡数字进行按位异或操作后的结果打出。最后老师会收集所有同学打出的数字。

这些数字中出现次数最多的数字是众数。在所有同学合作的最优策略下，我们希望众数对应数字出现的次数尽可能多。请问出现次数最多的数字是多少呢？

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

接下来 $n$ 行，其中第 $i$ 行时非负整数 $a_i,b_i$ 代表第 $i$ 名同学手上红卡和黑卡的数字。

outputFormat: 一个整数，表示答案。如果有多个解，请输出最小的那个。

hint:
样例解释：

众数出现次数最多是 $3$ 次，有如下两种方法：

- $1$ 号同学直接出红卡，$2$ 号同学出红黑异或，$3$ 号同学随便出，$4$ 号同学出红黑异或。这样 $1,2,4$ 号同学都可以打出 $21$。
- $1$ 号同学出红黑异或，$2$ 号同学直接出红卡，$3$ 号同学直接出红卡，$4$ 号同学随便出。这样 $1,2,3$ 号同学都可以打出 $28$。

所以 $21$ 和 $28$ 都是出现次数最多的众数，因为最多可以出现 $3$ 次，不存在出现 $4$ 次的方案。但是由于要求如果有多解输出小的，请输出 $21$。


title: [传智杯 #2 初赛] 特殊的翻转

description:
k 老师在研究一段病毒程序的代码。这段代码是由一段长度不超过 $10^6$ 的十六进制字符（也就是 `0` 到 `9` 和 `A` 到 `F`）组成的信息。现在 k 老师要将其转换为二进制的 0/1 串（这个时候需要确保最高位是 1）。然后对这个 0/1 串进行“翻转”操作。

对于每次“翻转”操作，k 老师可以选择这个 0/1 串中的其中一位，将这一位和这一位相邻的两位，一共三位，分别进行“翻转”（也就是 0 变 1，1 变 0）。如果指定的这一位是序列的开头或者结尾，那么翻转这一位和存在的相邻位即可。

k 老师想知道，如何用最少的“翻转”步骤，将这个 0/1 串变为全 0 的串。

inputFormat: 一个十六进制的字符串，由 `0` 到 `9` 和 `A` 到 `F` 构成。

outputFormat: 最少能将其变为全 0 串需要的“翻转”步骤次数。如果无论如何都不能将其变为全 0 串，则输出 `No`。

hint:
样例解释：

十六进制的 15 对应二进制的 10101，翻转第 1/3/5 位，就可以全部变为 0。

十六进制的 FF 对应二进制的 11111111，翻转第 2/5/8 位，就可以全部变为 0。

十六进制的 10 对应二进制的 10000，无法全变为 0。


title: 『MdOI R3』Pekka Bridge Spam

background:
JohnVictor 比较喜欢玩 Clash Royale。

他喜欢玩一套叫做 Pekka Bridge Spam 的卡组，然而这卡组被削弱了。现在他天梯已经掉了很多分了，不会玩了，只能在竞技场上给他的攻城锤安排地方了。

于是就有了这道题。

description:
JohnVictor 的皇室竞技场是一个 $2n \times 2m$（$2n$ 行，$2m$ 列）的方格表，他要在上面放 $n\times m$ 个 $1 \times 2$ 的攻城锤，使得任意两个攻城锤不相交。

然而攻城锤里面的野蛮人靠太近会打架，所以他要求任意一个 $2 \times 2$ 的正方形中有两个相邻的格子没有被任何攻城锤占有。

现在已经摆好了 $k$ 个攻城锤了，JohnVictor 想要知道有多少种方法能摆放这些攻城锤，注意，攻城锤两两之间没有区别。

由于这个答案实在是太大了，JohnVictor 只想知道这个答案对素数 $p$ 取模后的余数。**保证取模前的真实答案大于 $0$**。

为了避免玩过皇室的参赛者对题目理解产生问题，这里的攻城锤看做一个 $1 \times 2$ 的多米诺，翻转后也与自身一样。如果还是不理解可以参考样例。

**由于本题数据范围较大，使用 C++ 的选手可以使用以下代码来加快取模速度。**

代码出自 [KATCL](https://github.com/kth-competitive-programming/kactl/blob/master/content/various/FastMod.h) 。

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};
FastMod F(2);

int main() {
    int M = 1000000007; F = FastMod(M);
    ull x = 10ULL*M+3;
    cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}
```

使用方法：

假设当前程序中需要取模的数为 $p$，那么就在 `main` 函数开头处调用 `F = FastMod(p);`。

计算 $a\bmod p$ 的时候调用
`
F.reduce(a);
`，
返回值就是 $a\bmod p$ 的值。

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

接下来 $k$ 行，每行四个整数 $x_{1i},y_{1i},x_{2i},y_{2i}(1 \le i \le k)$，代表一块攻城锤的位置。

注意这里 $x,y$ 坐标表示的是在第 $x$ 行第 $y$ 列，并不是横纵坐标。

outputFormat: 一行一个整数，输出答案对 $p$ 取模后的值。


title: Shopping

description:
马上就是小苗的生日了，为了给小苗准备礼物，小葱兴冲冲地来到了商店街。商店街有 $n$ 个商店，并且它们之间的道路构成了一棵树的形状。

第 $i$ 个商店只卖第 $i$ 种物品，小苗对于这种物品的喜爱度是 $w_i$，物品的价格为 $c_i$，物品的库存是 $d_i$。但是商店街有一项奇怪的规定：如果在商店 $u,v$ 买了东西，并且有一个商店 $p$ 在 $u$ 到 $v$ 的路径上，那么必须要在商店 $p$ 买东西。小葱身上有 $m$ 元钱，他想要尽量让小苗开心，所以他希望最大化小苗对买到物品的喜爱度之和。

这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为OI选手的你，你能帮帮他吗？

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

对于每组数据，

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

第二行 $n$ 个非负整数 $w_1,w_2...w_n$ 。

第三行 $n$ 个正整数 $c_1,c_2...c_n$ 。

第四行 $n$ 个正整数 $d_1,d_2...d_n$ 。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示 $u$ 和 $v$之间有一条道路。

outputFormat: 输出共 $T$ 行，每行一个整数，表示最大的喜爱度之和。

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

对于全部的测试点，保证 $1\leq n\le 500$，$1\le m\le 4000$，$1\le T \le 5$，$0\le w_i\le 4000$，$1 \leq c_i \leq m$，$1\le d_i\le 100$。

#### 说明

题目来源：BZOJ4182。


title: [COCI2007-2008#1] PRINOVA

description: 给定一个长度为 $n$ 的偶数序列 $p_1,\dots,p_n$ 和两个整数 $A,B$，请你找出一个奇数 $X\in [A,B]$，使得 $\min{\{|X-p_i|}\}$ 最大。

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

第二行 $n$ 个数 $p_1,\dots,p_n$，描述这个偶数数列。

第三行为两个整数 $A,B$，意义如题目描述所示。

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

**如果有多种答案，打印任意一种即可，本题使用 SPJ。**

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

对于 $100\%$ 的数据，保证 $1\le n\le 100$，$2\le p_i\le 10^9$，$1\le A,B \le 10^9$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #1](https://hsin.hr/coci/archive/2007_2008/contest1_tasks.pdf) *T3 PRINOVA***


title: [COCI2007-2008#1] ZAPIS

description:
定义一个规则括号序列如下：

- 空串是规则括号序列。

- 如果 A 是规则括号序列，那么 `(`A`)` `[`A`]` `{`A`}` 都是规则括号序列。

- 如果 A,B 都是规则括号序列，那个序列 AB 也是规则括号序列。

Ivica 发现了一个长度为 $n$ 的疑似规则括号序列的串。但有一些字符已经模糊不清了，用 `?` 表示。

他想请你帮忙计算有多少种可能的情况使得这个疑似的串为规则括号序列。

inputFormat:
输入第一行为一个整数 $n$，表示这个疑似的串。

第二行为 $n$ 个字符，可能为 `?` `{` `}` `[` `]` `(` `)`中的任何字符。

outputFormat: 输出一行一个整数，表示情况的总数。因为答案可能很大，所以只需输出答案的 **后 $5$ 位**。（如果不足 $5$ 位不需要补前导 $0$）


title: 平面欧几里得最小生成树

description: 平面上有 $n$ 个点，第 $i$ 个点坐标为 $(x_i, y_i)$。连接 $i, j$ 两点的边权为 $\sqrt{(x_i - x_j) ^ 2 + (y_i - y_j) ^ 2}$。求最小生成树的边权之和。

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

接下来 $n$ 行，每行输入两个整数 $x_i, y_i$。

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

当你的答案与标准输出的绝对误差或相对误差在 $10^{-6}$  内时，就会被视为正确。

hint:
#### 样例解释 1

该样例中，最小生成树如下图所示：

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

边权之和为 $2 \sqrt{5} + 2 \approx 6.47213595500$。

---

#### 数据规模与约定

- 对于 $50\%$ 的数据，$n \le 5000$。
- 对于 $100\%$ 的数据，$3 \le n \le 10 ^ 5$，$\lvert x_i \rvert, \lvert y_i \rvert \le 10 ^ 5$。


title: [COCI2007-2008#1] SREDNJI

description:
给定一个长度为 $n$ 的 $1\sim n$ 的排列 $a_1,\dots ,a_n$，请你找出这个排列有多少个长度为奇数的**子串**的中位数为 $B$。

- 子串定义：把这个排列从开头（可能无）和从结尾（可能无）分别删去一些数后得到的剩下的数列。

- 中位数定义：将一个数列从小到大排序后排在中间的那个数字。

inputFormat:
输入第一行为两个整数 $n,B$。

第二行包含 $n$ 个整数，为一个 $1\sim n$ 的排列。

outputFormat: 输出中位数为 $B$ 的长度为奇数的子串的个数。

hint:
#### 样例 $3$ 解释

所有可能的情况： `4` `7 2 4` `5 7 2 4 3` `5 7 2 4 3 1 6`。

#### 数据规模与约定

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

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #1](https://hsin.hr/coci/archive/2007_2008/contest1_tasks.pdf) *T5 SREDNJI***


title: [COCI2007-2008#1] STAZA

description:
一场自行车比赛将在一个国家举行。全国的交通网络由 $n$ 个城市组成，编号为 $1\sim n$，由 $m$ 条双向道路连接。我们定义以下术语：

- 一条路线是一系列道路，当且仅当这些道路每条都从上一条道路的结束城市出发。

- 一条简单路线是指一条不经过一个城市一次以上的道路。

- 环是一条起点与终点相同的简单路线。

对于任意两个城市之间，保证至少有一条路线，且每条整个交通系统中的每条道路最多是一个环的一部分。

你的任务是找到满足以下两个约束条件的最长路线：

- 路线可以从任何城市开始，但必须在城市 $1$ 结束。

- 这条路线可以多次访问同一个城市，但不能经过同一条道路超过一次。

请你输出最长的路线的长度。

inputFormat:
输入第一行为两个整数 $n,m$，表示城市的数量和道路的数量。

接下来的 $m$ 行，每行两个整数 $a,b$，描述一条连接 $a,b$ 的双向道路。

保证不会出现两个城市直接由多条道路连接。

outputFormat: 输出最长路线的长度。

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

对于 $100\%$ 的数据，保证 $2\le n\le 10^4$，$1\le m\le 2n-2$，$1\le a,b\le n$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #1](https://hsin.hr/coci/archive/2007_2008/contest1_tasks.pdf) *T6 STAZA***


title: [CEOI2018] Fibonacci representations

background: 译自 CEOI2018 Day2 T1. [Fibonacci Representations](https://ceoi2018.pl/wp-content/uploads/2018/08/fib.pdf)。

description:
我们定义斐波那契数列为
$$
\begin{aligned}
F_1&=1\\
F_2&=2\\
F_n&=F_{n-1}+F_{n-2} \text{ for } n \ge 3
\end{aligned}
$$
序列的前面若干项为 $1,2,3,5,8,13,21,\ldots$。

对一个正整数 $p$，定义 $X(p)$ 为将 $p$ 用若干个**不同的**斐波那契数的和表示的方案数，两个方案不同当且仅当有一个斐波那契数恰好只在其中一个方案中出现。

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$，对于他的一个非空前缀 $a_1,a_2,\ldots,a_k$，我们定义 $p_k=F_{a_1}+F_{a_2}+\cdots+F_{a_k}$。

你的任务是对于所有 $k=1, 2, \ldots, n$，求出 $X(p_k)$ 对 $10^9+7$ 取模的值。

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

第二行 $n$ 个用空格隔开的整数 $a_1,a_2,\ldots,a_n$。

outputFormat: 标准输出包含 $n$ 行，在第 $k$ 行输出 $X(p_k)$ 对 $10^9+7$ 取模后的值。


title: [CEOI2018] Cloud computing

background: 译自 CEOI2018 Day1 T1. [Cloud Computing](https://ceoi2018.pl/wp-content/uploads/2018/08/clo.pdf)。

description:
Johnny 创立了 Bytecomp，一家提供云计算能力的公司。这样的公司通常拥有许多快速的计算机，可以让客户在上面进行计算。

Johnny 仍然没有购买任何机器。他去了一家计算机商店，收到了一个包含所有 $n$ 台可用的计算机的清单。每台计算机都可以用三个属性描述：处理器内核数 $c_i$，时钟频率 $f_i$ 和价格 $v_i$。这样的计算机包含 $c_i$ 个独立的内核，所以他们可以被分配不同的任务。

当客户订购资源时，她会指定所需的内核数 $C_j$ 和最小的时钟频率 $F_j$。订单还包含客户愿意支付的价格 $V_j$。如果接受订单，Bytecomp 需要提供客户所需计算能力的独占访问权。Johnny 需要选择 $C_j$ 个核心（可能来自不同的计算机），且它们的时钟频率至少为 $F_j$，这些核心不能被分配给其它订单。

帮助 Johnny 赚尽可能多的钱：接受一个最优的订单子集，选择所有计算机的一个子集来满足所有接受了的订单。你的目标是最大化利润，即为客户提供计算能力的收入与购买计算机的成本之差。

inputFormat:
标准输入的第一行包含一个整数 $n$，表示商店中可用计算机的数量。

接下来 $n$ 行，每行描述一台计算机，包含三个空格隔开的整数 $c_i, f_i, v_i$，分别表示内核数，时钟频率和价格。

接下来一行一个整数 $m$，表示客户的订单数量。

接下来 $m$ 行，每行描述一个订单，包含三个空格隔开的整数 $C_j, F_j, V_j$，分别表示需要的核心数，最低的允许的时钟频率以及预算。

outputFormat: 标准输出唯一的一行包含一个整数，表示能够得到的最大利润。

hint:
#### 样例解释

一共有四台可用的计算机和三个订单。

最佳方案是购买两台价格为 $700$ 和 $750$（总计 $1450$）的四内核的计算机，然后接受前两个订单获得 $300+1500=1800$ 的收益。

我们获得了四个时钟频率为 $2000$ 的内核，和四个时钟频率为 $2200$ 的内核。可以将其中六个分配给第二个订单（需要 $1900$ 的时钟频率），再将其中一个分配给第一个订单（需要 $1500$ 的时钟频率），剩下一个核心不使用，这是允许的。

总利润为 $1800-1450=350$。

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 2\times 10^3,\ 1\le c_i,C_i\le 50,\ 1\le f_i,F_i,v_i,V_i\le 10^9$。

所有测试数据被划分成若干个有附加限制的子任务，每个子任务中包含若干测试点。

| 子任务 | 附加限制 | 分值 |
| :--: | :---: | :--: |
| $1$ | $n \le 15$ | $18$ |
| $2$ | $m \le 15$ | $18$ |
| $3$ | $n,m \le 100$，$c_i = C_j = 1$ | $18$ |
| $4$ | $f_i = F_j = 1$ | $18$ |
| $5$ | $v_i = V_j = 1$ | $18$ |
| $6$ | 无附加限制 | $10$ |


title: [CEOI2018] Lottery

background: 译自 CEOI2018 Day1 T3. [Lottery](https://ceoi2018.pl/wp-content/uploads/2018/08/lot.pdf)。

description:
**请注意特殊的内存限制。**

长期以来，你一直是 Bytelotto 的忠实粉丝，但你的家人一直告诉你所有这样的游戏都是在浪费钱。你觉得这肯定是因为他们缺少技巧。你有一个很棒的计划，每个人都将很快看到你赢得游戏。

游戏类型很多，你对其中之一感兴趣：Bitlotto。游戏规则很简单，每天随机抽取一个数字作为中奖数字。你记下了连续 $n$ 天的中奖数字 $a_1, a_2, \ldots, a_n$。你确信这当中存在某种规律，尤其是连续 $l$ 天的区间中。你的家人仍然不相信你，所以说服他们的唯一方法是可靠的数学。

一共有 $n-l+1$ 个长度为 $l$ 的区间。第 $i$ 个区间从 $i$ 开始，因此它包含元素 $a_i, a_{i+1}, \ldots, a_{i+l-1}$。定义两个区间的距离为他们对应位置上的数字不相等的数量。形式化地说，第 $x$ 个区间与第 $y$ 个区间的距离为满足 $a_{x+i}\ne a_{y+i}$ 的位置 $i\ (0\le i < l)$ 的数量。然后我们定义两个区间是 $k$-相似的当且仅当这两个区间的距离不超过 $k$。

现在给出连续 $n$ 天的中奖数字和 $q$ 个询问，每个询问给出一个整数 $k_j$，你需要对序列中的每个长度为 $l$ 的区间，求出与该区间 $k_j$-相似的区间个数（不包括本身）。

inputFormat:
标准输入的第一行包含两个整数 $n,l$，分别表示天数和你需要分析的区间长度。

第二行包含 $n$ 个空格隔开的整数 $a_1, a_2, \ldots, a_n$，$a_i$ 表示第 $i$ 天的中奖数字。

第三行包含一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行包含一个整数 $k_j$，表示第 $j$ 个询问的相似参数。

outputFormat: 输出 $q$ 行，第 $j$ 行包含 $n-l+1$ 个空格隔开的整数，表示第 $j$ 个询问的答案。一行中的第 $i$ 个数表示与第 $i$ 个区间 $k_j$-相似的不包括本身的区间数量。

hint:
#### 样例解释

整个序列有五个长度为 $2$ 的区间：

- 第一个区间包含 $1$ $2$；
- 第二个区间包含 $2$ $1$；
- 第三个区间包含 $1$ $3$；
- 第四个区间包含 $3$ $2$；
- 第五个区间包含 $2$ $1$。

共有两个询问。

第一个询问 $k=1$。第一个和第三个区间——$1$ $2$ 和 $1$ $3$——只有第二个位置不同，所以他们的距离为 $1$。类似地，第一个和第四个区间——$1$ $2$ 和 $3$ $2$——只有第一个位置不同，所以他们的距离为 $1$。与第一个区间 $1$-相似的区间只有这两个，所以第一个数输出 $2$。

第二个询问 $k=2$，所有区间都是 $2$-相似的。

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^4,\ 1\le a_i\le 10^9,\ 1\le q\le 100,\ 0\le k_j\le l$。

所有测试数据被划分成若干个有附加限制的子任务，每个子任务中包含若干测试点。

| 子任务 | 附加限制 | 分值 |
| :--------: | :------------: | :--: |
|    $1$     |  $n \le 300$  | $25$ |
|    $2$     | $n \le 2000$  | $20$ |
|    $3$     | $q=1, k_1=0$ | $20$ |
|    $4$     |     $q=1$      | $15$ |
|    $5$     |   无附加限制   | $20$ |


title: [COCI2007-2008#2] BIJELE

background: Mirko 在阁楼发现了一套残缺的棋子。

description:
对于一套正确的棋子，应该包含：

- 一个国王；
- 一个皇后；
- 两个车；
- 两个象；
- 两个马；
- 八个兵。

现在给出这套残缺的棋子中每种棋子分别有多少个，请你求出需要如何添加或删除棋子来凑出完整的棋盘。

inputFormat: 输入一行六个数，依次表示国王，皇后，车，象，马，兵的数量。这些数字都在 $0\sim 10$ 之间（包含端点）。

outputFormat: 输出一行六个数，依次表示国王，皇后，车，象，马，兵需要添加或删除的数量。用正数来表示添加，用负数来表示删除。

hint:
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T1 BIJELE***。


title: [COCI2007-2008#2] CRNE

description: 在一个矩形棋盘上，切与矩形的边平行的 $n$ 次，问最多棋盘能被切成多少块？

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

outputFormat: 输出一行一个整数表示棋盘最多被分成的块数。

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

对于 $100\%$ 的数据，保证 $1\le n\le 100$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T2 CRNE***。


title: [COCI2007-2008#2] PRVA

description:
给定一个 $r\times c$ 的符号方阵组成的填词游戏，里面由小写字母和 `#` 组成。

一个单词指的是在方阵中从左到右或从上到下把经过的字母依次相连（不得包含 `#`）形成的字母串。不一定要整行或整列都包含，且这个字母串的长度至少为 $2$。对于竖向的单词，头尾的上方或者下方要么顶着 `#`，要么处于边界；横向单词的左右也需要符合这个要求。

请你求出字典序最小的单词。

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

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

outputFormat: 输出一行若干个字母，表示字典序最小的单词。

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

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

#### 说明
**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T3 PRVA***。


title: [COCI2007-2008#2] TURBO

description:
给定一个长度为 $n$ 的 $1\sim n$ 的排列，你需要对其进行从小到大的排序，排序的规则如下：

- 第一个阶段，将数字 $1$  通过与和它相邻的数字的交换来放置到 $1$ 号下标上。
- 第二个阶段，将数字 $n$ 进行如上同样的操作来放置到 $n$ 号下标上。
- 第三个阶段，将数字 $2$ 进行如上同样的操作来放置到 $2$ 号下标上。
- 第四个阶段，将数字 $n-1$ 进行如上同样的操作来放置到 $n-1$ 号下标上。

以此类推。

对于每一个阶段，输出交换的次数。

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

接下来的 $n$ 行，每行一个整数。描述了一个 $1\sim n$ 的排列。

outputFormat: 输出共 $n$ 行，对于每个阶段，输出交换的次数。

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

- 对于 $70\%$ 的数据，保证 $n<100$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T4 TURBO***。


title: [COCI2007-2008#2] KEMIJA

description: 请你构造一个由 $n$ 个数字围成的环，使得环中的所有数都加上其相邻两个数之后的结果等于给定的目标环。

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

接下来的 $n$ 行，每行一个整数，表示给定的目标环。

outputFormat:
输出共 $n$ 行，每行一个整数。描述你构造的环。

**可能存在多种构造方法，本题使用SPJ。**

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

- 对于 $70\%$ 的数据，保证 $n<100$。
- 对于 $100\%$ 的数据，保证 $3\le n\le 10^4$，给定的目标环中的数字不超过 $10^9$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T5 KEMIJA***。


title: [COCI2007-2008#2]  PRAVOKUTNI

description:
给出平面内的 $n$ 个点，计算有多少不同的直角三角形，满足其顶点均为给出的点。

两个直角三角形不同当且仅当它们存在至少一个顶点不同。

inputFormat:
输入第一行包含一个整数 $n$，表示点的数量。

接下来的 $n$ 行，每行两个整数，表示一个点的坐标。

outputFormat: 输出直角三角形的数量。

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

对于 $100\%$ 的数据，保证 $3\le n\le 1500$，坐标的数值在 $-10^9$ 和 $10^9$ 之间，且不存在任何两个点的坐标相同。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #2](https://hsin.hr/coci/archive/2007_2008/contest2_tasks.pdf) *T6  PRAVOKUTNI***。


title: Forget You

background:
「话说回来，你是谁？」

『竟然来这一手吗......』

『也是呢......』

『毕竟你夺走了几千、几万的能力，』

『他们对脑部造成的负担不是一般地大，』

『还能正常与人交谈已经很好了。』

「......」

『我啊，』

『是你的恋人。』

description:
为了让 おとさか ゆう 恢复记忆， ともり なお 找到了 PZY 。

PZY 经过研究，发现能力主要是根据体内的能力基因决定的，并把一共 $m$ 个能力基因用 $1$ 到 $m$ 表示，并依次分成了 $n$ 个集合，第 $i$ 个集合包含了编号从 $(\sum\limits_{j=1}^{i-1} a_j)+1$ 到 $\sum\limits_{j=1}^{i} a_j$ 的 $a_i$ 个能力基因。

经过大量的实验， PZY 发现基因的排序可以简化为一个数列，并按照需求， 定义一个数列被称为基因样品，当且仅当这个数列只由 $1$ 到 $m$ 的数字组成，对于属于第 $i$ 个集合里的数字，满足在该数列中**非严格单调递增**，且在数列中出现的次数不超过 $b_i$ 。

特别的，一个基因样本的研究价值就是构成这个基因样本的所有数字之和，注意重复的数字也要重复计算。

为了帮助 おとさか ゆう 恢复记忆， PZY 想知道所有的基因样品的研究价值之和是多少。

由于答案非常大，所以他只想知道对于答案除以 $998244353$ 的余数。

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

第 $2$ 到第 $n+1$ 行，包括 $2$ 个正整数 $a_i , b_i$ ，意义如题面所示。

outputFormat: 输出所有的基因样品的研究价值除以 $998244353$ 的余数。


title: [COCI2007-2008#3] CETIRI

description:
你原本有 $4$ 个数，它们从小到大排序后构成了等差数列。

但是现在丢失了一个数，并且其余的三个数的顺序也被打乱了。

请你找出第四个数。

inputFormat: 输入一行三个整数。保证这些数字在 $-100\sim 100$ 之间。

outputFormat:
输出一行一个数，为第四个数。

**方案可能不是唯一的，但保证一定存在，本题使用SPJ。**

hint:
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #3](https://hsin.hr/coci/archive/2007_2008/contest3_tasks.pdf) *T1 CETIRI***。


title: [COCI2007-2008#3] OKTALNI

description:
给你一个二进制的数字，请将其转换到八进制。

---

可以使用如下转换方法：

- 如果二进制的数字的位数不能被三整除，则在左侧补 $0$ 直到数字位数是 $3$ 的倍数。
- 将这个二进制数每三位分成一组。
- 每组的二进制可用如下表格所示的数字替换。

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

现在请你完成这个操作，并输出最终的八进制结果。

inputFormat:
输入一行一个二进制数。

保证位数不超过 $100$，并且首位为 $1$。

outputFormat: 输出一行一个八进制数。

hint:
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #3](https://hsin.hr/coci/archive/2007_2008/contest3_tasks.pdf) *T2 OKTALNI***。


title: [COCI2007-2008#3] TAJNA

description:
使用一种加密算法。

设字符串的长度为 $n$，则构造一个矩阵，使得 $r\times c=n$ 且在 $r\le c$ 的情况下使得 $r$ 尽量大。

然后把给定的明文按照由上到下，从左到右的顺序填充这个 $r\times c$ 的矩阵。

得到的密文就是把矩阵按照从左到右，从上到下的顺序输出的字符串。

给定你明文，请你输出密文。

inputFormat: 一行一个字符串，表示明文。

outputFormat: 一行一个字符串，表示密文。

samples: bok bok

samples: koaski kakosi

samples: boudonuimilcbsai bombonisuuladici

hint:
#### 样例 3 解释

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

共 $16$ 个字符，对于矩阵的长宽，可以选择 $1\times 16$，$2\times 8$ 和 $4\times 4$ 这三种，因为要求 $r$ 尽量大，所以选择 $4\times 4$。

然后进行填充，填充的结果如上图所示。

最后从左到右，从上到下输出每个字符即可。

#### 数据规模与约定

对于 $100\%$ 的数据，保证输入字符串只含小写字母，长度不超过 $100$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #3](https://hsin.hr/coci/archive/2007_2008/contest3_tasks.pdf) *T3 TAJNA***。


title: [COCI2007-2008#3] DEJAVU

description:
给出平面内的 $n$ 个点，计算有多少不同的直角三角形，满足其顶点均为给出的点，**且直角边均平行于坐标轴**。

两个直角三角形不同当且仅当它们存在至少一个顶点不同。

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

- 对于 $40\%$ 的数据，保证 $n<100$；
- 对于 $70\%$ 的数据，保证 $n<10^4$；
- 对于 $100\%$ 的数据，保证 $3\le n\le 10^5$，坐标的数值在 $1$ 和 $10^5$ 之间，且不存在任何两个点的坐标相同。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #3](https://hsin.hr/coci/archive/2007_2008/contest3_tasks.pdf) *T4 DEJAVU***。


title: [COCI2007-2008#3] CUDAK

description: 求出在区间 $[A,B]$ 中有多少个整数的各位数字之和是 $S$。并请找出最小的那个整数。

inputFormat: 输入一行三个整数 $A,B,S$。

outputFormat:
输出共两行，第一行为整数的个数，第二行为最小的整数。

输入数据保证至少有一个这样的数。

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

对于 $100\%$ 的数据，保证 $1\le A,B\le 10^{15}$，$1\le S\le 135$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #3](https://hsin.hr/coci/archive/2007_2008/contest3_tasks.pdf) *T5 CUDAK***。


title: 鬼故事 加强版

description:
[原题链接](https://www.luogu.com.cn/problem/P5126)

给定 $l,r,k$，求：
$$\sum_{i=l}^r \prod_{j=i}^{i+k-1}f_j$$
其中 $f_0= 0$，$f_1 = 1$，$f_n = f_{n-1}+f_{n-2} \ (n \geq 2)$。
作为良心（迫真）出题人，你只需要将答案对 $998244353$ 取模。

inputFormat: 输入一行三个正整数 $l,r,k$。

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

hint:
【数据范围】
对于 $30\%$ 的数据，$1\le k \le 1000$；
对于 $70\%$ 的数据，$1\le k \le 10^5$；
对于 $100\%$ 的数据，$1\le k \le 5 \times 10^5$，$1\le l \le r \le 10^{18}$。

**请注意常数优化。**

由于 $l,r$ 开到高精度范围也没什么意义，因此这里就改为 $10^{18}$ 了。


title: [COCI2007-2008#3] REDOKS

description:
给定一串长度为 $n$ 的数字，数字为 $0\sim 9$ 之间的任意一个，下标从 $1$ 记起。

然后进行 $m$ 次区间查询，每次查找区间 $[A,B]$ 的区间和，并在查询结束后将区间里的每一个数都 $+1$。特殊地，如果 $+1$ 前的数字为 $9$，那么 $+1$ 之后就变成了 $0$。

请输出每次查询的区间和。

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

第二行 $n$ 个数字字符，字符间无空格。

接下来的 $m$ 行，每行两个整数 $A,B$，表示查询区间 $[A,B]$。

outputFormat: 输出共 $m$ 行，每行为一次查询的区间和。

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

对于 $100\%$ 的数据，保证 $1\le n\le 2.5\times 10^5$，$1\le m\le 10^5$，$1\le A,B\le n$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #3](https://hsin.hr/coci/archive/2007_2008/contest3_tasks.pdf) *T6 REDOKS***。


title: [PA2010] Termites

description: 有一个长度为 $n$ 的数列 $a$，两名玩家轮流行动，每次可以选择一个与 $0$ 相邻的数字，得到数字大小的得分，并将它变为 $0$。求如果两个人都采取最优策略，两个人的得分。

inputFormat:
第一行一个整数 $n$，意义如题面。

接下来一行 $n$ 个整数，表示这个数列。

outputFormat: 一行两个整数，表示两个人都采取最优策略的答案。

hint:
#### 数据规模与约定
对于全部的测试点，保证 $1\leq n\leq 10^6$，且对于任何一个 $a$ 中的元素 $x$，都保证 $0\leq x\leq 10^6$ 且至少存在一个 $0$。


title: [PA2010] Riddle

description:
$n$ 个点 $m$ 条边的无向图被分成 $k$ 个部分。每个部分包含一些点。

请选择一些关键点，使得每个部分**恰**有一个关键点，且每条边**至少**有一个端点是关键点。

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

接下来 $m$ 行，每行两个整数 $a,b$，表示有一条 $a,b$ 间的边。

接下来 $k$ 行，每行第一个整数为 $w$，表示这个部分有 $w$ 个点；接下来 $w$ 个整数，为在这个部分中的点的编号。

outputFormat: 若可能选出请输出 `TAK`，否则输出 `NIE`。

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

对于全部的测试点，保证 $1\le k,w\le n\le 10^6$，$\sum w=n$，$1\le a,b\le n$，$0\le m\le 10^6$。


title: [PA2010] Planning the Roadworks【征集 spj】

background:
# 本题征集 SPJ，暂时无法评测。
# 如果您有意提供 SPJ，请在讨论区发帖或私信管理员。

description:
给定一个 $n$ 个点，$m$ 条边的有向图，求一个极大的可行边集使得删去这个边集之后原图连通性不变（能达到的仍然能到达）。

请给出一种可行的方案。

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

接下来 $m$ 行，每行两个数 $x,y$，表示存在一条从 $x$ 到 $y$ 的有向边。

outputFormat:
**本题存在 Special Judge**。

请在第一行输出一个整数 $k$，表示边集的大小。

接下来 $k$ 行，每行输出一个整数 $e_i$，表示删掉输入的第 $e_i$ 条边。

输入的边的编号从 $1$ 开始。

hint:
#### 样例 1 解释

一种可行的方案是，删除输入的第 $2$ 条边 $(1, 3)$ 和第 $6$ 条边 $(3, 4)$。

---

#### 数据规模与约定
对于全部的测试点，保证 $1\leq n\leq 5000$，$1\leq m\leq100000$，给定的图没有重边和自环。


title: [PA2010] The Goat

description: 平面上有 $n$ 个点。重复 $k$ 次以下操作：随机选择一个点，并以这个点为圆心作半径为 $r$ 的圆。求最后所有圆面积并的期望。

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

接下来 $n$ 行，每行两个整数 $x,y$，为一个点。

outputFormat: 输出面积并的期望。误差在 $10^{-2}$ 以内算对。

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

对于全部的测试点，保证 $1\le n,k\le 10^3$，$1\le r\le 10^3$，$|x|,|y|\le 10^3$。


title: [COCI2006-2007#6] MARATON

description:
给定一个 $n\times n$ 的正方形棋盘，几位玩家在上面玩三子棋。

三子棋的规则是每位玩家轮流写下一个字母，同一名玩家的字母相同。当有一名玩家在行、列或者斜线上连续组成了 $3$ 个自己的字母时，即为获胜。

给定棋盘的当前状态，请找出获胜的玩家。

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

接下来的 $n$ 行，每行 $n$ 个字符，可能为大写字母或 `.`（表示没人在这下棋）。

outputFormat:
输出一行一个大小字母，表示获胜的玩家所写的那种字母。

如果没有人获胜，则输出 `ongoing`。

数据保证最多只有一个人获胜。

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

对于 $100\%$ 的数据，保证 $1\le n\le 30$。
#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #6](https://hsin.hr/coci/archive/2006_2007/contest6_tasks.pdf) *T3 MARATON***。


title: [COCI2006-2007#6] KAMEN

description:
在一个 $r\times c$ 的方阵里，有些点是 `.`，表示为空；有些点是 `X`，表示这里是一堵墙。

我们可以认为这个方阵在竖直方向放置。

有一个人在这 $c$ 列的第一行会抛下 $n$ 块石头，用 `O` 来表示。如果这一个石头由于重力作用会向下滚动。具体来说，就是会从第一行向最后一行滚动，规则如下：

- 如果下一个格子是空格，那么向下运动一格。
- 如果下一个格子是墙或者已经到了第 $r$ 行，则停止滚动并停在原处。
- 如果下一个格子是一块停止的石头，则如果在左侧和左下方为空格时首选滚动到左侧的那一行，否则如果右侧和右下方为空格，则滚动到右侧的那一行。如果两侧都不为空，则石头静止不在移动。

只有前一块石头永久静止后，下一块石头才会被抛下。

请你输出最终方阵的状态。

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

接下来的 $r$ 行，每行 $c$ 个字符，每个字符可能为 `.` 或 `X`。

下一行为一个整数 $n$，表示石头的数量。

接下来的 $n$ 行，每行一个整数 $1\le x\le c$，表示这个石头位于第 $x$ 列被抛下，按照输入顺序依次抛下。

outputFormat: 输出一个 $r\times c$ 的方阵，包含 `.` `X` `O`，为最终石头都抛完后的状态。

hint:
#### 样例 1 解释

$4$ 块石头依次在第一列被抛下。第一块石头被唯一一堵墙堵住。这样剩下的石头都可以向右滚动一列。第二块石头毫无障碍地下落，第三四块分别落在了它的左边和右边。

#### 数据规模与约定

- 对于 $60\%$ 的数据，保证 $r\le 30$。
- 对于 $100\%$ 的数据，保证 $1\le r\le 3\times 10^4$，$1\le c\le 30$，$1\le n\le 10^5$。
#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #6](https://hsin.hr/coci/archive/2006_2007/contest6_tasks.pdf) *T4 KAMEN***。


title: [COCI2006-2007#6] V

description: 使用给定的数字，组成一些在 $[A,B]$ 之间的数使得这些数每个都能被 $X$ 整除。

inputFormat:
输入第一行包含三个整数 $X,A,B$。

第二行为一个数字串，表示可以使用的数字。一个数字可以使用多次，数字不会重复出现。

outputFormat: 输出一行一个整数，表示在 $[A,B]$ 这个区间用这些给定的数字能组成多少个被 $X$ 整除的数字。

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

- 对于 $100\%$ 的数据，保证 $1\le X\lt 10^{11}$，$1\le A\le B\lt 10^{11}$。
#### 说明

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


title: [COCI2006-2007#6] PROSTOR

description: 给定三维空间内的 $n$ 个长方体的位置，请你判断有多少对矩形会互相有重合的部分。（如果仅有一个点也会被计入结果）

inputFormat:
输入第一行为一个整数 $n$，表示矩形的数量。

接下来的 $n$ 行，每行六个整数。前三个数表示这个矩形左下角顶点的坐标，后三个数表示这个矩形右上角顶点的坐标。

outputFormat: 输出一行一个整数，表示有重合的矩形对数。

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

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，坐标介于 $1\sim 999$ 之间，保证每个矩形平行于一个坐标面。
#### 说明

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


title: 「EZEC-1」数列

description:
给你一个正整数 $n$，有数列 $1,2,3,...,n$。

分别求相邻两项中左边一项的 $a$ 倍与右边一项的 $b$ 倍的和再加上 $c$，得到一个有 $n-1$ 项的新数列：

 $1\times a+2\times b+c,2\times a+3\times b +c,...,(n-1)\times a+n\times b+c$。

对这个新数列重复上述操作得到若干数列，最后的数列只有一项，求最后这个项对 $p$ 取模的值。

inputFormat: 一行，五个**非负**整数 $n,a,b,c,p$。

outputFormat: 一个整数，表示答案对 $p$ 取模的值。


title: [COCI2007-2008#4] LEKTIRA

description: 给定一个字符串，请你将其分成三段，并将每一段倒序后按照分段的顺序输出。由于方案有多种，请输出答案字典序最小的那一种。

inputFormat: 输入一行为一个字符串，表示待分段的串。

outputFormat: 输出一行为一个字符串，表示答案串，需要保证字典序最小。

samples: dcbagfekjih abcdefghijk

samples: mobitel bometil

samples: anakonda aanadnok

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

对于 $100\%$ 的数据，保证输入的字符串长度在 $3\sim 50$ 之间。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #4](https://hsin.hr/coci/archive/2007_2008/contest4_tasks.pdf) *T3 LEKTIRA***。


title: [COCI2007-2008#4]  MUZICARI

description:
在一场音乐会上，一支有 $n$ 名乐师的乐队共连续演奏 $t$ 分钟，但每名乐师都有自己想要休息的时长。对于第 $i$ 名乐师，他想休息 $a_i$ 分钟。但为了整体的和谐，不能有**三个及以上**的乐师在同一个时刻休息（但是可以在上一个乐师刚刚结束的时刻开始下一个人的休息）。

请你安排每名乐师开始休息的时刻。

inputFormat:
输入第一行为两个整数 $t,n$。

第二行为 $n$ 个整数 $a_1,\dots ,a_n$，表示每名乐师希望休息的时长。

outputFormat:
输出一行 $n$ 个整数，表示安排每名乐师的开始休息的时刻，按照输入的顺序输出每名乐师。

**注意：尽管方案可能不唯一，但数据保证方案一定存在，本题使用SPJ。**

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

对于 $100\%$ 的数据，保证 $1\le t\le 5000$，$1\le n\le 500$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #4](https://hsin.hr/coci/archive/2007_2008/contest4_tasks.pdf) *T4  MUZICARI***。


title: [COCI2007-2008#4] POKLON

description: 给定 $n$ 个区间，Mirko 想要构造一些区间，满足后续的区间是前面区间的子区间，且区间里的每个数都包含在给定的区间里。

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

接下来的 $n$ 行，每行两个整数 $[A,B]$，表示一个给定的区间。

outputFormat:
输出第一行为一个整数 $k$，表示可以构造出的区间数。

接下来的 $k$ 行，每行两个整数，依次表示构造的区间。

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

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le A<B\le 10^6$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #4](https://hsin.hr/coci/archive/2007_2008/contest4_tasks.pdf) *T5 POKLON***。


title: [COCI2007-2008#4] KOCKE

description:
在一个平面直角坐标系中，有一个位于坐标 $(0,0)$ 点的机器人。每次可以向上下左右移动一格。还有 $5$ 个分布于不同位置的磁石。

机器人每次移动都可以推动他目的地那一格的磁石。但是当两块磁石有一个面互相接触时（即处于相邻坐标），它们就会互相吸引而构成一个整体。机器人推其中的任何一块都会对这个整体造成同样的效果。

请你给出机器人的一种移动方案，使得经过移动能使这 $5$ 块磁石构成一个 `T` 形（不能旋转）。

inputFormat:
输入共 $5$ 行，每行包含两个整数 $x,y$，描述一块磁石的位置。

数据保证不会有任何两块磁石位于相同的或者相邻的坐标。

outputFormat:
输出一行一个字符串，表示磁石移动的方案，种类如下：

- `L`：向左移动一格；
- `R`：向右移动一格；
- `U`：向上移动一格；
- `D`：向下移动一格。

至多有 $9999$ 步。

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

对于 $100\%$ 的数据，保证 $-5\le x,y\le 5$。
#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #4](https://hsin.hr/coci/archive/2007_2008/contest4_tasks.pdf) *T6 KOCKE***。

**感谢 @[一扶苏一](https://www.luogu.com.cn/user/65363) 提供SPJ！**


title: [COCI2008-2009#1] SKOCIMIS

description:
三只袋鼠在沙漠里的一条数轴上玩耍，每只袋鼠都占据一个不同的整数点。在一次移动中，一只不在中间的袋鼠跳进另两只袋鼠之间的空间。两只袋鼠决不能占据同一位置。

请让它们尽可能久地玩耍。

inputFormat: 三个整数 $A,B,C$，表示三只袋鼠最初的位置。

outputFormat: 输出袋鼠们最多能移动的次数。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，$0 < A < B < C < 100$。
#### 说明
#### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #1](https://hsin.hr/coci/archive/2008_2009/contest1_tasks.pdf) SKOCIMIS，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2008-2009#1] PTICE

description:
Adrian 、Bruno 和 Goran 想加入鸟类爱好者俱乐部。然而，他们并不知道所有的申请者都必须通过加入俱乐部的考试。考试由 $n$ 道题组成，每道题有三个可能的答案：`A`、`B` 和 `C`。

不幸的是，他们不能区分各种鸟类，所以他们试图猜测正确的答案。每一个男孩都有一套关于哪一种答案序列最有效的理论：

Adrian 声称最好的顺序是：`A`，`B`，`C`，`A`，`B`，`C`，`A`，`B`，`C`，`A`，`B`，`C`$\ldots$

Bruno 确信这样更好：`B`，`A`，`B`，`C`，`B`，`A`，`B`，`C`，`B`，`A`，`B`，`C`$\ldots$

Goran 嘲笑他们，并使用这个序列：`C`，`C`，`A`，`A`，`B`，`B`，`C`，`C`，`A`，`A`，`B`，`B`$\ldots$

写一个程序，根据给出的正确答案，确定三个人中谁对的题目最多。

inputFormat:
第一行一个整数 $n$，表示考试的题目数量。

第二行一个长度为 $n$ 的字符串（只包含`A`、`B`、`C`三种字符），表示考试的正确答案。

outputFormat:
第一行输出一个整数 $m$，表示三个人中做对题目最多的数量。

从第二行开始，输出答对题目数最多的人的名字（每行一个，按照字典序输出）

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，有 $1≤n≤100$。
#### 说明
#### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #1](https://hsin.hr/coci/archive/2008_2009/contest1_tasks.pdf) PTICE，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2014-2015#2] MOBITEL

description:
蚱蜢 Marko 高兴地在草地上跳来跳去。他不小心，他的手机掉进了水坑。他的手机现在触键弄湿了，键盘的工作方式完全不可预知！所有的数字键都坏了。当我们按下其中一个键时，手机就好像我们按下了另一个键一样。幸运的是，没有两个键按下后的作用是一样的，所以 Marko 仍然可以写出所有的字母。

蚱蜢 Marko 正在做一些实验以找出每个键的动作。现在他想给他的女朋友写封信。因为他只是一只蚱蜢，所以它需要你帮忙。

对于那些不记得手机的按键是如何工作的人，这里有一个简短的描述。

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

这张图片显示了我们可以通过按那个键（在一个没有掉进水坑的工作手机上）得到的带有字母的按键。例如，如果我们想要字母 `a`，我们将按一次键 2，如果我们想要字母 `b`，我们将按两次键 2。如果我们想连续用同一个键写两个字母，我们必须按一次键 `#`。例如，如果要编写字符串 `klor`，我们将按以下顺序按键：`55#555666777`。

inputFormat:
第一行输入包含 $9$ 个整数。第一个整数表示按下键 `1` 的作用相当于原来的哪个键，第二个表示按下键 `2` 的作用相当于原来的哪个键，第三个表示表示按下键 `3` 的作用相当于原来的哪个键，依此类推。马尔科不会使用 `*` 和 `0` 键。键 `#` 不会坏。

第二行输入包含一个字符串 $s$，该字符串仅由英文字母表中的小写字母组成，表示蚱蜢 Marko 想要打出的字符串。

outputFormat: 第一行也是唯一一行，输出可以打印出蚱蜢 Marko 所想要的字符串需要按的键序列。

hint:
#### 样例 1 说明

所有键的功能都向右移动一个位置，因此输出与题目中的示例语句中的示例略有不同。

#### 数据规模与约定

令 $|s|$ 为字符串 $s$ 的长度，则对于 $100\%$ 的数据，都有 $1\le |s|\le 100$。

#### 说明

**题目译自 [COCI2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST #2](https://hsin.hr/coci/archive/2014_2015/contest2_tasks.pdf) _T1 MOBITEL_。**


title: [COCI2014-2015#2] UTRKA

description:
许多本地和国际的休闲跑步者都渴望参加今年的萨格勒布马拉松！这是一场 42125 米长的传统比赛。一个奇怪的统计信息是，今年每个参赛者除了一个以外都设法完成了比赛。

请帮助组织者根据注册参赛者名单和排名表，确定**未完成比赛**的参赛者的身份。

inputFormat:
第一行输入包含整数 $n$，即参赛者人数。

以下 $n$ 行中的每一行都包含注册参赛者的姓名。

其他的 $n-1$ 行包含完成比赛者的姓名，按他们完成比赛的顺序排列。参赛者的名字由英文字母组成。参赛者的名字**不一定是唯一的**。

outputFormat: 第一行也是唯一一行，输出必须包含未完成比赛的参赛者的姓名。

samples:
5
marina
josipa
nikola
vinko
filipa
josipa
filipa
marina
nikola

samples:
4
mislav
stanko
mislav
ana
stanko
ana
mislav

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

- 对于 $50\%$ 的数据，有 $1\le n\le 10^3$。
- 对于 $100\%$ 的数据，有 $1\le n\le 10^5$。

令 $|s|$ 为参赛者姓名的长度，则对于所有合法的姓名，都有 $1\le |s|\le 20$，且姓名只由**小写字符**组成。

#### 说明

**题目译自 [COCI2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST #2](https://hsin.hr/coci/archive/2014_2015/contest2_tasks.pdf) _T2 UTRKA_。**


title: [COCI2014-2015#2] STUDENTSKO

description:
一年一度的萨格勒布大学学生乒乓球团体赛将于下周六举行！每队由 $k$ 名学生组成。$n$ 个兴奋的学生们正在排队等候登记。Krešo 在登记处工作。他真的不想做他的工作，所以他决定不让学生选择团队。他决定第一组将由第一个排队的 $k$ 名学生组成，第二组由下面的 $k$ 名学生组成，第三组由后面的 $k$ 名学生组成，以此类推。（$n\equiv 0\pmod k$，因此没有人剩余。）

Ante 用一个整数来估计每个玩家的技能。他希望第一队拥有最弱的 $k$ 个球员，第二队拥有第二弱的 $k$ 个球员，依此类推，最后一队拥有最强的 $k$ 个球员。

Krešo 刚刚休息了一下，Ante 决定转移排队的学生以达到自己的目标。他转移学生的方式是告诉一个学生从队列中走出来，在另一个学生后面排队，或者走到队列的前面。每转移一个学生花费一分钟。Krešo 有可能随时从休息中回来，所以 Ante 需要尽快实现他的目标。帮助 Ante 确定实现目标所需的最少分钟数。

inputFormat:
第一行输入包含整数 $n$ 和 $k$，满足 $n\bmod k=0$。

第二行包含 $n$ 个空格分隔的整数 $v_i$，表示第 $i$ 个站在队列中的玩家技能的水平。

所有参赛者都有不同水平的技能。

outputFormat: 仅一行，即转移学生所用的最短分钟数。

hint:
#### 样例 3 说明

Ante 应该将技能等级为 $5,6$ 和 $3$ 的学生移到队列的前面，花了三分钟。

#### 数据范围与约定

- 对于 $30\%$ 的数据，有 $1\le n\le 20$。
- 对于 $100\%$ 的数据，有 $1\le n\le k\le 5\times 10^3$。

对于所有合法的 $v_i$，都有 $1\le v_i\le 10^9$。

#### 说明

**题目译自 [COCI2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST #2](https://hsin.hr/coci/archive/2014_2015/contest2_tasks.pdf) _T3 STUDENTSKO_。**


title: [COCI2014-2015#2] BOB

description:
Bob 是一位著名的建设者。他买了地，想盖房子。不幸的是，问题是土地的地形，土地不同地方的海拔不一定一样。

这块地呈长方形，宽 $n$ 米，长 $m$ 米。它可以分为 $n\times m$ 个方格（见图片）。Bob 的房子将被塑造成一个长方形，它的边与土地的边平行，其顶点与正方形的顶点重合。Bob 的房子所覆盖的所有土地必须具有相同的高度，以防倒塌。

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

请计算出 Bob 建房的方法数。

**形式化地**，求出一个矩阵中所有元素均相等的子矩阵个数。

inputFormat:
第一行输入包含整数 $n$ 和 $m$。

以下 $n$ 行中的每一行都包含 $m$ 个整数 $a_{i,j}$，分别是每平方土地的海拔高度。

**由于输入量很大，请使用更快的输入方法。**

outputFormat: 仅一行，即 Bob 建房的方法数。

hint:
#### 样例 1 说明

一些可能的房屋位置是分别以 $(0,0)-(1,1),(0,0)-(0,2)$ （高度为 $2$）$(2,0)-(2,2),(1,2)-(2,2)$（高度为 $1$）为左上角顶点和右下角顶点的矩形。括号中的第一个数字表示行号，第二个数字表示列号（坐标以 $0$ 开始）。

#### 数据规模与约定

- 对于 $20\%$ 的数据，有 $1\le n,m\le 50$。
- 对于 $60\%$ 的数据，有 $1\le n,m\le 500$。
- 对于 $100\%$ 的数据，有 $1\le n,m\le 10^3$。

对于所有合法的 $a_{i,j}$，都有 $1\le a_{i,j}\le 10^9$。

#### 说明

**题目译自 [COCI2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST #2](https://hsin.hr/coci/archive/2014_2015/contest2_tasks.pdf) _T4 BOB_。**


title: [COCI2014-2015#2] ŠUMA

description:
森林可以抽象为一个 $n\times n$ 的矩阵，每个元素描述一棵树的高度。

Mirko 为每棵树测量了它们一年生长的米数。**注意：如果一棵树一年长 $5$ 米，半年就会长 $2.5$ 米。**

Mirko 想知道，若已知森林里所有树木的当前高度及生长速度，如果这些树继续以它们当时生长的速度生长，那么所有高度相同的连成一组的树的的树的棵数最大会是多少。

两棵树或一组树是相邻的条件如下：

- 如果两棵树在矩阵中共享一条公共边，则它们是**相邻的**。
- 如果有从第一棵树到第二棵树的相邻树序列，则两棵树是**相邻的**。
- 如果组中的每对树都是相邻的，则一组树是**相邻的**。

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

接下来 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个数指 $h_{i,j}$，表示第 $i$ 行第 $j$ 列中树的初始高度，以米为单位。

接下来 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个数指 $v_{i,j}$，表示第 $i$ 行第 $j$ 列中树的生长速度，以米为单位。

**由于输入量较大，请使用更快的输入方法。**

outputFormat: 仅一行一个整数，即为题中所求。

hint:
#### 样例 2 说明

$8$ 个月后，位于 $(0,0),(0,1),(1,0)$ 的树木高度将达到 $\dfrac{13}{3}$ 米，这 $3$ 棵树是相邻的一组树，所以应该输出 `3`。

#### 数据规模与约定

- 对于 $30\%$ 的数据。有 $1\le n\le 70$。
- 对于 $100\%$ 的数据，有 $1\le n\le 700$。

对于所有合法的 $h_{i,j}$ 和 $v_{i,j}$，都有 $1\le h_{i,j},v_{i,j}\le 10^6$。

#### 说明

**题目译自 [COCI2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST #2](https://hsin.hr/coci/archive/2014_2015/contest2_tasks.pdf) _T5 ŠUMA_。**


title: [COCI2008-2009#1] MRAVOJED

description:
考古学家最近发现了希腊罗马建筑的遗迹。该遗迹可以建模成为为 $r \times c$ 正方形单元的网格。对于每一个位置，考古学家已经确定是否有建筑存在。

他们详细检查了这些文物后得出结论，该地点包含两座不同时期的建筑，两座建筑的平面图都是正方形的。

由于这些建筑在时间上来自不同的时期，它们的楼层平面可能重叠。

为每栋建筑确定可能的位置和大小（平面图所占广场的边长）。

inputFormat:
第一行两个整数 $r$ 和 $c$，表示遗迹的长宽。

以下 $r$ 行每行 $c$ 个字符，其中`.`表示该地无遗址被发现，`x`表示该地有遗址被发现。

outputFormat: 对于每一个建筑，输出其左上角顶点的坐标（$2$ 个数字）和其边长（$1$ 个数字），每两个数字之间用空格隔开。

hint:
#### 提示
解决方案可能不唯一。
#### 数据规模与约定
对于 $100\%$ 的数据，保证存在解决方案，有 $1 \leq r \leq 100,1 \leq c \leq 100$。
#### 说明
题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #1](https://hsin.hr/coci/archive/2008_2009/contest1_tasks.pdf) MRAVOJED，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。
#### 鸣谢
感谢 @[y0y68](https://www.luogu.com.cn/user/115668) 提供的 SPJ。


title: [COCI2008-2009#1] JEZ

description:
有一个长为 $r$ 宽为 $c$ 的矩形，将其划分为 $r\times c$ 个 $1\times 1$ 的小矩形。

**行数从上到下从 $0$ 到 $r-1$ 编号，列数从左到右从 $0$ 到 $c-1$ 编号。**

每个小矩形都有颜色，如果一个小矩形的行数为 $x$，列数为 $y$，则：
- 若 $x\oplus y=x+y$ 这个小矩形为灰色。
- 反之，则为白色。

下左图为 $r=c=10$ 的情况：

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

现在有人沿着上右图的轨迹沿着这个矩形走 $k$ 步，求他走了多少个灰色格子。

inputFormat:
第一行为两个整数 $r$ 和 $c$。

第二行为一个整数 $k$。

outputFormat: 一行，表示他走的灰色格子的个数。

hint:
#### 数据规模与约定
- 对于 $50\%$ 的数据，保证 $k\le 10^6$。
- 对于 $100\%$ 的数据，保证 $1\le r,c\le 10^6$，$1\le k\le r\times c$，答案在 $32$ 位整数范围之内。
#### 说明：
#### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #1](https://hsin.hr/coci/archive/2008_2009/contest1_tasks.pdf) JEZ，译者 @[菜鸟一只](https://www.luogu.com.cn/user/175829)。


title: [COCI2008-2009#1] SKAKAVAC

background: 一只蚱蜢在花田。

description:
花田是一个 $n\times n$ 的正方形，每一朵花都有它的编号，$f_{i,j}$ 就代表第 $i$ 行，第 $j$ 列的编号。

现在蚱蜢在第 $r$ 行，第 $c$ 列。

蚱蜢决定去看一看新世界，于是它决定在遵守以下规则的情况下尽可能多的跳到花朵上。

如果它要从 $(r_1,c_1)$ 跳到 $(r_2,c_2)$ 需满足以下条件中的一个：

- $|r_1-r_2|=1$ 且$|c_1-c_2|>1$，
- $|c_1-c_2|=1$ 且$|r_1-r_2|>1$，

并且，$f_{r_2,c_2}>f_{r_1,c_1}$。

请你求出蚱蜢最多能经过几朵花。

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

第二行有两个整数 $r$，$c$。

接下来 $n$ 行，每行 $n$ 个整数，代表 $f$ 数组。

outputFormat: 一个整数，代表蚱蜢最多能经过几朵花。

hint:
#### 数据规模与约定
- 对于 $50\%$ 的数据，$n\le 100$。
- 对于 $80\%$ 的数据，$n\le 10^3$。
- 对于 $100\%$ 的数据，$1\le n\le 1.5\times 10^3$，$1\le r,c\le n$，$1\le f_{i,j}\le 10^6$。
#### 说明
本题译自 [Croatian Open Competition in Informatics 2008/2009](https://hsin.hr/coci/archive/2008_2009) [Contest #1](https://hsin.hr/coci/archive/2008_2009/contest1_tasks.pdf) T5 SKAKAVAC。


title: [COCI2008-2009#1] KRTICA

description:
有一棵 $n$ 个点的树，边权都为 $1$。

现在想删去一条边，增加一条边，使得最远的两个点距离最短。

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

接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$，表示有树上有一条从 $a$ 到 $b$ 的无向边。

outputFormat:
**本题存在 SPJ**。

第一行只有一个整数，表示删去一条边，增加一条边后最远的两个点的距离。

第二行两个整数，表示被删掉的一条边。

第三行两个整数，表示被增加的一条边。

hint:
#### 数据规模与约定
- 对于 $40\%$ 的数据，保证 $n\le 30$。
- 对于 $70\%$ 的数据，保证 $n\le 3\times 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le n \le 3\times 10^5$，$1\le a,b\le n$。

---

#### 计分标准

- 如果输出的第一行不正确，得 $0$ 分。
- 如果输出得第一行正确，但是剩下的数字不正确或数量不足四个，得对应测试点 $70\%$ 的分数。
- 如果输出第一行正确，且给出的方案是可行且正确的，得到对应测试点 $100\%$ 的分数。

---
#### 说明
本题译自 [Croatian Open Competition in Informatics 2008/2009](https://hsin.hr/coci/archive/2008_2009) [Contest #1](https://hsin.hr/coci/archive/2008_2009/contest1_tasks.pdf) T6 KRTICA。

SPJ provided by @Tweetuzki


title: [Cnoi2020] 梦原

background:
> 成熟是一种明亮而不刺眼的光辉，一种圆润而不腻耳的音响，一种不再需要对别人察言观色的从容，一种终于停止向周围申述求告的大气，一种不理会哄闹的微笑，一种洗刷了偏激的淡漠,一种无须声张的厚实，一种并不陡峭的高度。勃郁的豪情发过了酵，尖利的山风收住了劲，湍急的溪流汇成了湖。
——余秋雨《文化苦旅》

在一个偶然的梦境中，Cirno 发现了一棵树，在一望无际的昏暗平原上，发出了淡淡的蓝色荧光。

Here lies $\ \ \ \ \ \ \ \ \ $.

description:
不幸的是，这棵树尚未长成，只有一个根节点 $1$。

Cirno 只能知道这棵树将会有 $n$ 个结点，上面分别有 $a_1,a_2,\ldots,a_n$ 颗果实，却无法知道树的形状。

但是树的生长总是具有某种规律。

对于结点 $i$，它会**等概率地**从 $[i-k,i-1] \cap N^+$ 中选择一个结点连接，并成为那个节点的子节点。

其中，$k$ 是一个 Cirno 已经测出的常数。

为了摘下所有的果实，在树长成之后，Cirno 会多次使用魔法。其中每次会在树上选一个联通块，并从联通块内每个结点上摘取一个果子（必须保证该联通块内**每个结点都有果子**）。

显然，Cirno 会采取**最佳策略**使得使用魔法的次数最少。

现在，Cirno 已经知道了 $n$，$k$ 和每个结点将会长出的果子数 $a_i$，请你帮她计算出她最少使用的魔法次数的数学期望。为了简单起见，你只需要输出答案除以 $998244353$ 的余数。

inputFormat:
第一行输入两个整数 $n$，$k$，含义如上所述。

第二行输入 $n$ 个整数，表示 $a_1,a_2,\cdots,a_n$。

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

hint:
## 样例 1 解释：

可能长成的树有如下两种（黑色为结点编号，红色为结点上果子数）：

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

最佳方案是对联通块 $\{1,2,3\}$ 和 $\{1\}$ 各使用一次魔法，$\{3\}$ 使用两次，共四次。

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

最佳方案对联通块 $\{1,2,3\},\{1,3\}$ 和 $\{3\}$ 各使用一次魔法，共三次。

所以答案为 $\frac{7}{2}\equiv 499122180\pmod{998244353}$

## 数据范围与约定

对于 $100\%$ 的数据，保证 $1\le k<n\le 10^6$，$0\le a_i<998244353$。

### 子任务「本题采用捆绑测试」

- Subtask1（$10\%$）: $k=1$。
- Subtask2（$10\%$）: $n \le 10$，$a_i \in \{0,1\}$。
- Subtask3（$10\%$）: $n \le 10$。
- Subtask4（$10\%$）: $n \le 1000$。
- Subtask5（$60\%$）: 无特殊限制。


title: [COCI2008-2009#3] PET

description:
在一项受欢迎的比赛 _Dinner for Five_ 中，有 $5$ 名选手和 $4$ 名裁判，这 $4$ 个裁判会对每一道菜用 $1 \sim 5$ 的数字进行评估，每位选手的总分即是所有裁判评分的总和，参赛者按照其评分顺序从 $1$ 到 $5$ 进行编号。

请你编写一个程序，输出评分最高的选手的编号以及其分数。

inputFormat:
输入共 $5$ 行，每一行有 $4$ 个正整数，表示每位裁判对第 $i$ 位选手的评分。

输入数据将确保胜者是唯一的。

outputFormat: 输出仅 $1$ 行，有 $2$ 个正整数，中间有一个空格，分别表示评分最高的选手以及其分数。

hint:
#### 说明

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


title: [COCI2008-2009#3] KEMIJA

background: Luka 天天上课走神。

description:
Luka 又在化学课上鬼混了！他不是在写化学方程式，而是在写一句奇怪的话。

Luka 通过在每一个元音字母（$\texttt{a}$，$\texttt{e}$，$\texttt{i}$，$\texttt{o}$，$\texttt{u}$）后面加上 $\texttt{p}$ 再加上原来的元音字母的方式加密这一个单词，如  $\texttt{kemija}$ 变成  $\texttt{kepemipijapa}$， $\texttt{paprika}$ 变成  $\texttt{papapripikapa}$ 。

老师想知道调皮的 Luka 写了些什么，请你帮助老师，写出一个解密程序。

inputFormat: 一行一个字符串 $s$，表示加密后的句子，数据保证不会有前导空格与尾随空格，但句子中间可能出现空格。

outputFormat: 一行一个字符串，表示解密后的句子。

samples:
zepelepenapa papapripikapa
zelena paprika

samples: bapas jepe doposapadnapa opovapa kepemipijapa

hint:
#### 数据范围

令 $|s|$ 为 $s$ 的长度，则 $1 \leq |s| \leq 100$，数据保证字符串的内容一定是小写字母或空格。

#### 说明

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


title: [COCI2008-2009#3] CROSS

background:
在数独游戏中，目标是将 $1 \sim 9$ 的整数放入 $9 \times 9$ 网格中，这样每行每列以及 $9$ 个 $3 \times 3$ 框的每一个都包含所有 $9$ 个数字不重复的数字。开始 $9 \times 9$ 的方格纸已部分填充，因此可以从逻辑上推导出其他单元格的值。

数独有很多难题，解决越困难的往往需要越复杂的分析方法。

description:
在这道题中，你需要用到最简单的方法，即交叉影线。

在方格之中，我们选择 $9$ 个数字中的 $1$ 个，并针对网格中每个出现的数字划掉相应的行，列和 $3 \times 3$ 的框。 寻找一个的 $3 \times 3$ 区域，将号码的位置并将其放置在此处。

系统会为您提供部分填充的网格。您的任务是重复使用交叉影线的方法，对于不同的数字，直到无法再对任何数字进行推论。

下面的第一张图片显示了一个非常稀疏的数独。但是，即使如此稀疏，但在此网格中仍然可以使用交叉阴影线推断左上角单元格中的数字为 $4$，如第二张图片。

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

另外，在下列情况下，您需要输出 $\tt ERROR$：
- 数字在网格中的初始放置无效。
- 在所有的 $3 \times 3$ 框中无法填写此数字。

inputFormat: 输入有 $9$ 行，每行 $9$ 个字符。每个字符将是一个在 $1$ 到 $9$ 之间，或是一个 $\tt .$，表示空。

outputFormat:
如果输入有效且求解时没有矛盾，则应在相同的位置输出网格给出的格式。

如果可以使用交叉阴影线推导出其值，则填充单元格。

否则输出 $\tt ERROR$。

hint:
#### 说明

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf) *T3 CROSS*。**


title: [COCI2008-2009#3] NAJKRACI

description:
有一个含 $n$ 个点，$m$ 条边的**有向图**。

对于每一条边，求出它被任意两点的最短路径经过的次数对 $10^9+7$ 取模的值。

如果 $A, B$ 两点之间有多条最短路，每条最短路都要计算一遍。你可以参考样例 $4$ 中第 $3, 4$ 条边的输出来理解这句话。

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

接下来 $m$ 行，每行三个整数 $x$ ，$y$，$d$，即有一条 $x$ 到 $y$ 的有向边，边权为 $d$。

outputFormat: 共 $m$ 行，每一行输出一个整数，第 $i$ 行的数表示在第 $i+1$ 行读入的边被任意两点的最短路径经过的次数对 $10^9+7$ 取模的值。

hint:
#### 数据范围与约定
- 对于 $30\%$ 的数据，保证 $n\le 15$，$m\le 30$。
- 对于 $60\%$ 的数据，保证 $n\le 300$，$m\le 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 1.5\times 10^3$，$1\le m\le 5\times 10^3$，$a\neq b$，$1\le a,b\le n$，$1\le d\le 10^4$。
#### 说明
本题译自 [Croatian Open Competition in Informatics 2008/2009](https://hsin.hr/coci/archive/2008_2009) [Contest #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf) T6 NAJKRACI。


title: [COCI2008-2009#3] BST

description:
现在有一个 $1\sim n$ 的排列 $a$，将序列中的元素依次放进一个 BST 里，求 BST 中插入函数的执行次数。

**注意：第一个数已经作为 BST 的根。**

如果您无法理解上面说的话，这里有一份伪代码：

```
insert( number x, node n )
    c+1;
    if x is less than the number in node n
        if n has no left child
            create a new node with the number x and set it to be the left child of node n
     else
         insert(x, left child of node n)
     else (x is greater than the number in node n)
         if n has no right child
             create a new node with the number x and set it to be the right child of node n
         else
             insert(x, right child of node n)
```
您需要求的就是上面的 insert 函数每进行一次后 $c$ 的值。

**再次注意：第一个数已经作为 BST 的根。**

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

接下来 $n$ 行，每行一个整数，第 $i$ 行为 $a_i$。

outputFormat: 共 $n$ 行，一行一个整数，表示上面的 insert 函数每进行一次后 $c$ 的值。

hint:
#### 数据范围及限制
- 对于 $50\%$ 的数据，保证 $n\le 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^5$，$1\le a_i\le n$，$a_i$ 互不相同。
#### 说明
本题译自 [Croatian Open Competition in Informatics 2008/2009](https://hsin.hr/coci/archive/2008_2009) [Contest #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf) T5 BST。


title: [COCI2008-2009#3] MATRICA

description:
您需要构造一个 $n\times n$ 字符矩阵 $M$。

这个字符矩阵有如下几条限制：
1. $M_{i,j}=M_{j,i}(1\le i,j\le n)$。
1. 必须恰好含有 $a_i$ 个字符 $c_i$。

因为构造的方案有很多种，所以你需要输出方案中字典序最小的。

因为输出太多不好，所有你只需要输出 $p$ 列，具体的方案将会在输入格式中声明。

如果无解，请输出 `IMPOSSIBLE`。

inputFormat:
第一行为两个整数 $n$ 和 $k$，$k$ 表示限制 $2$ 的条数。

接下来 $k$ 行，每一行为一个大写字母和一个整数，分别为 $c_i$ 和 $a_i$。

接下来一行为一个整数 $p$。

接下来一行 $p$ 个整数，表示你需要输出的列的标号，保证按升序出现。

outputFormat: 为一个 $n$ 行 $p$ 列的字符矩阵，如果无解，请输出 `IMPOSSIBLE`。

hint:
#### 数据范围与限制
- 对于 $60\%$ 的数据，保证 $n\le 300$。
- 对于 $80\%$ 的数据，保证 $n\le 3\times 10^3$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^4$，$1\le k\le 26$，$\sum a_i=n^2$，$c_i\neq c_j$，$1\le p\le 50$。

#### 说明
本题译自 [Croatian Open Competition in Informatics 2008/2009](https://hsin.hr/coci/archive/2008_2009) [Contest #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf) T4 MATRICA。


title: [COCI2014-2015#4] CESTA

description:
Mirko 发现了一个正整数 $n$，由于 Mirko 喜欢数字 $30$，他想知道用 $n$ 的每位数字所组成的数中 $30$ 的最大倍数。

写一个计算这个数字的程序（如果不存在，则输出 `-1`）。

inputFormat: 一个数 $n$。

outputFormat: 仅一行，即题中所求。

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

对于 $100\%$ 的数据，$n$ 的位数不超过 $10^5$。

#### 说明

**题目译自 [COCI2014-2015 CONTEST #4](https://hsin.hr/coci/archive/2014_2015/contest4_tasks.pdf) _T1 CESTA_。**


title: [COCI2014-2015#4] PŠENICA

description:
Mirko 和 Slavko 每年在 Saint Lucy’s Day 种植圣诞小麦。小麦的茎秆生长速度不同，经过一段时间后，小麦变得相当凌乱。他们决心通过玩下面的游戏来解决这个问题，游戏将轮流进行如下环节：

- Mirko 选择一根高度最小的麦秆使其高度变成次小值。
- Slavko 选择一根高度最大的麦秆使其高度变成次大值。
- 如果剩下的不同高度的数量不小于 $3$，游戏继续进行，否则结束，结束时需要操作者为输家了。

给定小麦秸秆的高度，Mirco 先手。请确定游戏的赢家以及结束后高度的最小值与最大值。

inputFormat:
第一行输入包含整数 $n$，即小麦秸秆的数量。

第二行输入包含 $n$ 个空格分隔的整数 $h_i$，表示单个小麦秸秆的高度。

outputFormat:
第一行输出输出赢家的姓名（`Mirko`或 `Slavko`）。

第二行输出游戏结束时最短和最长的麦秆的高度。

hint:
#### 样例 1 说明

初始时 Mirko 便不能操作，因此，Slavko 是赢家。

#### 数据规模与约定

- 对于 $50\%$ 的数据，有 $1\le n\le 500$。
- 对于 $80\%$ 的数据，有 $1\le n\le 3\times 10^3$。
- 对于 $100\%$ 的数据，有 $1\le n\le 10^5$。

对于所有合法的 $h_i$，都有 $1\le h_i\le 10^5$。

#### 说明

**题目译自 [COCI2014-2015 CONTEST #4](https://hsin.hr/coci/archive/2014_2015/contest4_tasks.pdf) _T2 PŠENICA_。**


title: [COCI2014-2015#4] PRIPREME

description:
Ante 和 Goran 正在准备 $n$ 个团队。他们每个人各有一个算法需要向所有团队讲解。

当然，他们不能两人同时对同一个团队讲解，也不能同时对多个团队讲解。

给定对每个团队讲解所需的时间，你需要确定讲解所需的最少时间。

inputFormat:
第一行输入包含整数 $n$，即团队数量。

下一行包含 $n$ 个空格分隔的整数 $a_i$，表示对第 $i$ 个团队讲解所需的时间。

outputFormat: 仅一行，即讲解所需的最少时间。

hint:
#### 样例 1 说明

每个团队都需要 $2$ 个单位时间来理解和实现一个算法，以下是一种可行的授课方法。

| Ante | Goran | 用时 |
| :----------: | :----------: | :----------: |
| 团队 1 | 团队 2 | $2$ |
| 团队 2 | 团队 3 | $2$ |
| 团队 3 | 团队 1 | $2$ |
| 全部完成 | 全部完成 | $6$ |

#### 样例 2 说明

其中一种最佳的时间安排是 Ante 依次给团队 $2,3, {\color{red}x},1$ 讲解，但是在 $\color{red}x$ 中有一个 $1$ 个单位时间的暂停。Goran 将依次给团队 $1,3,2$ 讲课。

#### 数据规模与约定

- 对于 $40\%$ 的数据，有 $1\le n\le 7$。
- 对于 $100\%$ 的数据，有 $1\le n\le 3\times 10^5$。

对于所有合法的 $a_i$，都有 $a_i\in [1,3\times 10^5]$。

#### 说明

**题目译自 [COCI2014-2015 CONTEST #4](https://hsin.hr/coci/archive/2014_2015/contest4_tasks.pdf) _T3 PRIPREME_。**


title: [COCI2014-2015#4] MRAVI

description:
Bobi 每天早上起床喂他最喜欢的宠物：蚂蚁。他把它们放在一个有管道系统的玻璃瓶中，管道系统可以表示为一棵有 $n$ 个节点的树。管道用树的边缘表示。树的根位于用 $1$ 表示的节点上。在管道系统内部，由于重力的作用，液体从节点流向其子节点。我们知道每个管道的流量 $x_i$：从父节点到子节点的流量百分比。让我们观察以下示例：

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

图片中的节点 $1$ 有 $12$ 升液体，之后有两个管道。一个的流量是 $x_i=30$，另一个是 $x_i=70$。节点 $2$ 将得到 $3.6$ 升，节点 $3$ 得到 $8.4$ 升。在输入数据中，来自同一节点的管道流量之和始终等于 $100$。Bobi 的一些管子不只是普通的管子，它们有点奇怪。它们是超级管道，有超能力将流经它们的液体流量平方。在前面的例子中，如果第一个管道有超能力，节点 $2$ 得到 $12.96$ 升，节点 $3$ 仍然只有 $8.4$ 升。现在请注意，一个节点的流出液体比进入的液体多。这正是这些管道是超级管道的原因！

所有的超级管道都可以由波比开启或关闭。蚂蚁只生活在树的叶子里（没有孩子的节点）。对于每一片叶子，我们知道需要多少液体来喂养生活在叶子里的蚂蚁。Bobi 想把 $L$ 升液体倒进树根里喂蚂蚁。他没有多少钱，所以他想知道他需要购买的最低液体量，以保证所有蚂蚁的饲料。

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

以下 $n-1$ 行中的每一行包含四个整数 $a_i,b_i,x_i,t_i$，其中 $a_i$ 和 $b_i$ 是管道的末端（管道连接的节点的编号），$x_i$ 是液体通过管道的流量，$t_i$ 表示管道是否具有超能力。如果 $t_i$ 为 $1$，则该管道具有超能力，否则它不具有超能力。

下一行包含 $n$ 个整数 $k_i$，用于描述第 $i$ 个节点中蚂蚁所需的液体量。如果第 $i$ 个节点不是叶，$k_i$ 将是 $-1$。

outputFormat:
仅一行，即 $L$。

**注意：本题采用 SPJ，与正确解的误差不超过 $10^{-3}$ 即视为正确。**

hint:
#### 样例 1 说明

如果 Bobi 向根节点中注入 $8$ 升液体，节点 $3$ 得到 $4$ 升，节点 $4$ 得到 $1$ 升，节点 $5$ 得到 $9$ 升。这些节点是叶子（其中有蚂蚁）中蚂蚁需要得到的最小数量。所以，$8$ 升是满足“蚂蚁”条件的最低液体量。

#### 数据规模与约定

对于 $100\%$ 的数据，都有 $1\le n\le 10^3$，$1\le a_i,b_i\le n$，$1\le x_i\le 100$，$t_i\in\{0,1\}$，$k_i\in[1,10]$。

**数据保证 $L$ 的值不超过 $2\times 10^9$。**

#### 说明

**题目译自 [COCI2014-2015 CONTEST #4](https://hsin.hr/coci/archive/2014_2015/contest4_tasks.pdf) _T4 MRAVI_。**


title: [COCI2014-2015#4] SABOR

description: 一片遥远的土地上有 $n$ 名议员。他们就新全民公决法修正案进行了激烈的辩论。从周一到周五，所有议员都兴高采烈地来上班，整天争论不休。一位勤奋的新闻记者每周每个工作日都会在激烈的争论中拍摄议员们在工作场所的照片。她在照片上捕捉到的是一对相互怒视的议员。五张照片已转发给你作全面分析。事实上，每个议员都属于两个政党中的一个。让我们用字母 `A` 和 `B` 来表示两个政党。你的任务是估计每个议员属于哪个政党。你需要确保每个议员最多与**两位不同的**本政党中的议员争吵。

inputFormat:
第一行输入包含整数 $n$，即议员的数量。议员从 $1$ 到 $n$ 编号。

以下五行描述了从周一到周五拍摄的照片。五行中的每一行都包含了当天在照片上争论的两名议员的名单（相互怒视）。每一行的第一个数是 $p$，表示有 $p$ 议员在争吵，然后有 $p$ 对 `k l` 形式的数字，表示 $k$ 号议员和 $l$ 号议员在争吵。在每一对数字之前都有一个**双空格**。

outputFormat: 仅一行，即一个长度为 $n$ 的仅由字符 `A` 和 `B` 组成的字符串，第 $i$ 个字符表示满足给定条件的分区中第 $i$ 个议员是哪个政党。因为答案不会是唯一的，所以输出**任何一种**。

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

- 对于 $30\%$ 的数据，有 $1\le n\le 15$。
- 对于 $100\%$ 的数据，有 $1\le n\le 2\times 10^5$。

对于所有合法的 $p$，都有 $1\le p\le\dfrac{n}{2}$。

#### 说明

**题目译自 [COCI2014-2015 CONTEST #4](https://hsin.hr/coci/archive/2014_2015/contest4_tasks.pdf) _T5 SABOR_。**

感谢 @[shenyouran](https://www.luogu.com.cn/user/137367) 提供的 SPJ。


title: [COCI2014-2015#4] STANOVI

description:
Stanko 在一家建筑公司做建筑师。他目前的任务是为萨格勒布的一栋住宅楼制定一个平面图。他必须确定一种方法，用墙将楼层建筑分割成矩形的公寓。每面墙必须与建筑物的侧面平行。更准确地说，楼层在平面图中表示为一个尺寸为 $n\times m$ 的大矩形，其中每个公寓都是一个较小的矩形，尺寸为 $a\times b$，位于较大的矩形的内部。数字 $a$ 和 $b$ 必须是整数。

此外，楼层必须完全覆盖公寓——楼层中的每个点都必须位于公寓内。公寓不能交叉，但它们可以接触。为了防止室内黑暗，公寓必须有窗户。因此，每套公寓必须有一条在代表楼层的矩形边缘上的边，这样就可以放置一个窗户。

此外，所有公寓的面积 $k$ 必须近似相等。尺寸为 $a\times b$ 的公寓的面积偏差定义为 $(a\times b-k)^2$。平面图的偏差是公寓所有偏差的总和。

Stanko 想建造他能建造的最好的建筑，一座偏差最小的建筑。帮助他并编写一个程序，以确定满足任务条件的平面图的最小可能偏差。

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

inputFormat: 仅一行三个整数 $n,m,k$。

outputFormat: 一行，即公寓布局的最小可能偏差。

hint:
#### 样例 1 说明

该样例对应于题目描述的左图。请注意，不可能实现 $0$ 的偏差值。

#### 数据规模与约定

对于 $100\%$ 的数据，有 $1\le n,m\le 300$，$1\le k\le 10^4$。

#### 说明

**题目译自 [COCI2014-2015 CONTEST #4](https://hsin.hr/coci/archive/2014_2015/contest4_tasks.pdf) _T6 STANOVI_。**


title: [COCI2019-2020#2] ACM

description:
一场有着悠久历史的比赛马上开始了，它是由 ACM 组织的。确切地说，有 $n$ 个团队将角逐头名，其中包括克罗地亚黄金三人组：Paula、Marin 和 Josip。竞赛采用标准形式，通过团队成员之间的协作，共同编写代码并提交。

比赛由 $m$ 个不同的题目组成，各小组按已解决的题目数排序（不递增）。

具有相同数量已解决任务的团队按所谓的罚时排序（不递减）。某个团队的罚时是他们在每一个正确解决的任务上获得的罚时的总和。正确解决的任务的罚时等于团队解决该任务所花费的时间（从比赛开始）增加。

每个提交但未通过的代码将给提交该代码的团队增加 $20$ 分钟罚时。任何团队都不会为他们已经解决的问题提交代码，并且每个团队的每一个问题的最大提交次数为 $9$。如果一些团队有相同数量的问题解决和相同的罚时，他们将按字典序在排行榜中排列。

比赛持续 $5$ 个小时。在前 $4$ 个小时内，所有团队都可以获得排名，并包含有关每个团队的每个题目状态的信息（提交的次数、是否已解决以及何时解决）。在这 $4$ 个小时里，队伍的排名将在每一次提交后自动更新。不过，在最后 $1$ 小时内，排行榜被冻结，即评测新提交的代码后，参赛队伍的排名不会更新。在这段时间里，每个团队都知道自己提交的代码的评测结果，但不知道其他团队提交的代码的评测结果。他们只知道其他团队提交了哪些任务、提交了多少次以及每个任务的最后一次提交时间。

比赛结束了，排行榜很快就会解冻。我们的英雄，NijeZivotJedanACM 需要你的帮助。他们想知道在排行榜上最差的排名是什么，在排行榜解冻后他们最终可能会排在什么位置。请你帮助他们！

inputFormat:
输入数据共 $1 + n$ 行。

第一行两个整数 $n$ 和 $m$，表示参赛队伍的个数和题目的个数。

接下来 $n$ 行，每行的输入格式如下：
1. 首先输入队伍名称；
2. 接下来 $m$ 个字符串，格式均为 `SX/V`，说明如下：
- `S` 表示题目状态，共有三种字符：`-`、`+`、`?`。`-` 表示该题目该团队未通过，`+` 表示该题目该团队已通过，`?` 表示该题目最后一次提交时排行榜已冻结。
- `X` 表示该题目该团队的提交次数。特别地，如果该题目该团队未提交，则 `X` 省略。
- `V` 表示该题目该团队最后一次提交时比赛已经开始的时间，用 `HH:MM:SS` 表示，可能有前导零来补足。特别地，如该题目未通过，则整个 `/V` 部分省略。

最后一行按照前面的格式，输入 NijeZivotJedanACM 的最终成绩（即排行榜解冻后的成绩）

outputFormat:
输入数据共一行。

第一行，输出 NijeZivotJedanACM 可能会处在的最差排名。

samples:
2 1
NijeZivotJedanACM -
ZivotJESTJedanACM -
NijeZivotJedanACM -

samples:
3 2
StoJeZivot ?1/04:00:00 +1/02:04:06
JeLiZivotJedanACM ?1/04:59:59 -
NijeZivotJedanACM ?1/04:42:43 -
NijeZivotJedanACM +1/04:42:43 -

hint:
#### 数据规模及约定
- 对于 $40\%$ 的数据，保证所有输入的 `S` 状态均不为 `?`。
- 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le m \le 15$，保证所有测试数据中，任意两个小组的名字均不同。

#### 说明

**本题满分 $50$ 分。**

**题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T1 ACM*。**


title: [COCI2008-2009#2] KORNISLAV

description:
乌龟 Kornislav 从来没有什么有趣的事。 由于他将生活三百年，他一直在努力寻找消磨时间的方法。 这个周末，他开始玩“面积最大的矩形”这个游戏。
首先，Kornislav 需要四个正整数。他通过向一个方向移动，旋转 $90°$ ，在新方向上行走等方式来形成一个图案。Kornislav 总共进行了三个 $90°$ 旋转，并走过了四条线段。
当朝某个方向行走时，他的步数必须等于四个所选整数中的一个，并且每个整数只能成为一条线段的长度。根据 Kornislav 使用这四个整数的顺序，他的步行将形成各种形状，其中也包括一些未封闭的图案。
编写一个程序，计算出乌龟的行进轨迹可以形成的最大矩形面积。

inputFormat: 一行四个整数 $a,b,c,d$，表示 Kornislav 挑选的四个整数。

outputFormat: 一行一个整数，表示 Kornislav 的行进轨迹所能形成的最大矩形面积。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，有 $1<a,b,c,d<100$。
#### 说明
#### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) KORNISLAV，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2008-2009#2] RESETO

description:
埃拉托色尼筛法是一种著名的素数筛法，可以查找所有直至 $n$ 的素数。该算法的步骤是：
1. 写下 $2$ 到 $n$ 之间的所有整数（包括 $2$ 和 $n$）。
2. 找到尚未删除的最小数，并将其命名为 $p$； 则 $p$ 是素数。
3. 划掉 $p$ 及其所有尚未划掉的倍数。
4. 如果尚有数未被划掉，请转到步骤 $2$。

编写一个程序，给定 $n$ 和 $k$，找出第 $k$ 个被删除的整数。

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

outputFormat: 一行一个整数，表示第 $k$ 个被划掉的整数。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，有 $2 \leq k < n \leq 1000$。
#### 说明
#### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) RESETO，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2008-2009#2] SVADA

description:
当地的动物园已经获得了一个大型开放式花园，动物可以像在其自然栖息地中那样随意移动，并以平常的恶作剧来招待游客。

最受欢迎的动物是猴子。随着他们的攀登，跳跃和其他坎，他们使老老游客都感到高兴。

一种猴子专门研究爬高大的树木和摘椰子。另一种专门研究它们的开放性。
有 $n$ 只第一种猴子（编号 $1$ 到 $n$）和 $m$ 种第二种猴子（编号 $1$ 到 $m$）。

第一种猴子的第 $k$ 只需要 $A_k$ 秒才能在树上找到一个好地方，然后摘下第一个椰子。之后，猴子每 $B_k$ 秒产生一个新的椰子。

第二种猴子的第 $k$ 只需要 $C_k$ 秒的时间才能找到打开椰子的好工具，然后打开第一个椰子。之后，猴子每 $D_k$ 秒打开另一个椰子。

不幸的是，第二种猴子非常具有攻击性，因此这两种类型可能不会同时出现在花园中。因此，动物园管理员会在第一类猴子摘下所有椰子后立刻赶走它们。类似地，如果打开所有椰子后，相同类型的猴子停留时间过长，则会发生争斗。因此，动物园管理员将在它们打开所有椰子后将它们送走。

动物园管理员需要在所有椰子都被采摘后立即到达，然后在猴子将它们全部打开后立即返回。猴子进入或离开花园所需的时间也很小。

Tomislav 特别喜欢第二种猴子，但到来时总是看不见它们。请帮助他计算第二种猴子到达的时间（他知道猴子在花园里度过的总时间，但不知道花园里椰子的数量）。

inputFormat:
第一行一个整数 $t$，表示猴子在花园中度过的总时间，以秒为单位。

第二行一个整数 $n$，表示第一种猴子的只数。

以下 $n$ 行，每行两个整数 $A_k$ 和 $B_k$，表示第 $k$ 只第一种猴子的两个相关数据，具体解释请参照题目描述。

接下来一行一个整数 $m$，表示第二种猴子的只数。

以下 $m$ 行，每行两个整数 $C_k$ 和 $D_k$，表示第 $k$ 只第二种猴子的两个相关数据，具体解释请参照题目描述。

outputFormat: 一行一个整数，表示第一种猴子到来到第二种猴子到来之间的秒数。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，有 $1 \leq t \leq 1 \times 10^9,1 \leq n,m \leq 100,1 \leq A_k,B_k,C_k,D_k \leq 1 \times 10^9$。
#### 说明
#### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) SVADA，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2008-2009#2] SETNJA

description:
在二叉树中：

- 每个节点都有两个孩子——一个左孩子和一个右孩子。
- 如果节点标记为整数 $x$，则其左子节点标记为 $2x$，右子节点标记为 $2x+1$。
- 树的根标为 $1$。

在二叉树上从根开始遍历。遍历中的每一步要么是跳到左孩子上，要么是跳到右孩子上，或暂停休息（停留在同一节点上）。

用由字符 `L`，`R` 和 `P` 组成的字符串描述遍历过程。

- `L `表示跳到左孩子；
- `R `表示跳到右孩子；
- `P `表示暂停一轮操作。

$walk$ 的值是我们最终到达的节点的标签。例如，`LR` 的 $walk$ 值为 $5$，而 `RPP` 的 $walk$ 值为 $3$。

一次遍历由 `L`，`R`，`P` 和 `*` 描述。每个 `*` 可以是三个动作中的任何一个。  例如， `L*R` 可能代表 `LLR`，`LRR` 和 `LPR`。集合 `**` 可能代表 `LL`，`LR`，`LP`，`RL`，`RR`，`RP`，`PL`，`PR ` 和 `PP`。

最后，一次遍历后的 $walk$ 的总值是该次遍历中所有可能的遍历顺序的每一步所形成的 $walk$ 的值的总和。

计算给定遍历顺序后的 $walk$ 的总值。

inputFormat: 一行一个字符串，表示遍历顺序。

outputFormat: 一行一个整数，表示 $walk$ 的总值。

hint:
#### 数据规模与约定
- 对于 $30\%$ 的数据，保证输入的字符串中无 `*` 字符。
- 对于 $50\%$ 的数据，保证输入的字符串中至多有三个 `*` 字符。
- 对于 $100\%$ 的数据，保证输入字符串长度小于 $10000$，字符串的每一位只可能是 `L`，`R`，`P`，`*`。
#### 说明
- #### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) SETNJA，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COCI2008-2009#2] CAVLI

description:
Mirko 在阁楼上发现了一块木板和 $n$ 个钉子。 Mirko 尽快将钉子钉在板上。 通过坐标平面对板进行建模，钉子作为其中的点。 没有两个钉子具有相同的 $x$ 或 $y$ 坐标。
为了继续玩乐，Mirko 偷走了姐姐的松紧发带，将其散布在所有的钉子上，然后放开。 松紧带自然在钉子周围收紧。

然后，Mirko 重复这些步骤，保证在板上至少留下三个钉子：

1. 记录下由发圈围成的图形面积；

2. 在板上选择最左边，最右边，最上面或最下面的钉子。

3. 从板上卸下选择的钉子； 松紧带再次把仍留在板上的最靠外钉子绑起来。
   现在我们知道 Mirko 在每次执行步骤 $2$ 时选择的钉子，编写一个程序来计算在每次执行步骤 $1$ 时计算出的图形面积的大小。

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

接下来 $n$ 行，每行两个整数 $x_i$ 和 $y_i$，用空格隔开，表示第 $i$ 个钉子的坐标。

下面一行一个字符串，由 $n-2$ 个字符组成，这些字符可能为 `L`，`R`，`U`，`D`，分别表示 Mirko 选择拔掉的钉子。这四个字符的含义如下：

- `L` 表示拔掉最左边的钉子（横坐标最小的钉子）；
- `R` 表示拔掉最右边的钉子（横坐标最大的钉子）；
- `U` 表示拔掉最上方的钉子（纵坐标最大的钉子）；
- `D` 表示拔掉最下方的钉子（纵坐标最小的钉子）。

outputFormat: 共 $n-2$ 行，每行一个浮点数，表示每一次执行步骤 $1$ 时计算出的图形面积的大小，保留一位小数。

hint:
#### 样例 #2 解释：
![](https://cdn.luogu.com.cn/upload/image_hosting/y16d8wid.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/qefp7alq.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/puomeovd.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/lp53b1zy.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/6rgbxuyo.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/5g5xhv94.png)

以上是对于样例 #2 的输入数据，程序应该按顺序模拟的六个步骤。
#### 数据规模与约定
- 对于 $50\%$ 的数据，保证 $3 \leq n \leq 1000$。
- 对于 $100\%$ 的数据，保证 $3 \leq n \leq 3 \times 10^5$。
#### 说明
#### 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) CAVLI，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: [COI2008] TAMNICA

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

现在有一个无限大的迷宫，数字如图方式排列。两个数字之间的黑线表示有一堵墙隔开，如果没有则可以互相到达。

你从 $1$ 出发，出口在 $n$ 。现在由于地震，有一些墙倒了，这正好便利了你的通行。趁着人们的慌乱，你需要经过尽可能少的数字来迅速出逃。请你算出出逃最少需要的步数。

inputFormat:
输入第一行为一个整数 $n$ ，表示出口所在的格子。

第二行为一个整数 $k$，表示因地震倒塌的墙的数量。

接下来的 $k$ 行，每行一个整数 $b$，表示一堵倒塌的墙的一侧的数字。

另一侧的数字 $a$ 没有给出，但已知 $a<b$，所以你可以自己推导出 $a$ 的值，进而得出是哪堵墙倒塌了。当然，有些数字（比如 $2,3,5,7,10,13$） 永远不会是 $b$ 数字。

outputFormat: 输出一行一个整数，表示最少需要经过的数字的数量（不包含 $1$）。

hint:
#### 样例 1 解释

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

对于样例 $1$ 的地震后迷宫的状态如图所示。

$1-4-15-14-13-30-31$ 这条线路溜得最快。共经过了 $6$ 个数字。

#### 数据规模与约定

- 对于 $50\%$ 的数据，$n\le 10^6$；
- 对于 $100\%$ 的数据，$1\le n\le 10^{15}$，$1\le k\le 10^5$，$4\le b\le 10^{15}$。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [COI2008](https://hsin.hr/coci/archive/2007_2008/olympiad_tasks.pdf) *T3 TAMNICA***。


title: 猜数

background: 这是一道**交互题**。

description:
珂愛给了你一个 $[1,n]$ 之间的整数 $k$，你每次可以询问一个整数 $x$，然后珂愛会告诉你 $x$ 和 $k$ 的大小关系。

你需要用尽可能少的次数猜出珂愛想的数。

你需要实现一个函数 `int Chtholly(int n,int c)`，这个函数的作用是在不超过 $c$ 次询问中猜对 $[1,n]$ 中的一个数，返回值为你最终确定的数。

你可以调用交互库中一个叫做 `Seniorious` 的函数，其原型为 `int Seniorious(int x)`，返回值为：

- 若 $k\lt x$，则返回 $1$。
- 若 $k\gt x$，则返回 $-1$。
- 若 $k=x$，则返回 $0$。

你调用 `Seniorious` 函数的次数不超过 $c$ 才能得到这个点的分数，否则这个点为 $0$ 分。有关该函数的调用请参考【说明/提示】部分。

由于珂愛只会写 C++ 语言的交互库，所以你只能使用 C++ 语言（包括 C++，C++11，C++14，C++17）来解决本题。

inputFormat: 样例输入中三个数分别为 $n,c,k$。这些数据你都**无法读取**。

outputFormat: 样例输出中第一个数是你猜的 $k$，第二个数是你调用 `Seniorious` 函数的次数。这些数据你**不必输出**。

hint:
#### 样例解释

你要猜的 $k$ 为 $3$。

由于你和珂愛心灵相通，所以在没有调用 `Seniorious` 的情况下就猜出来了。

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $c=n-1$。
- 对于 $100\%$ 的数据，保证 $2\leq n\leq 10^6$，$\min(20,n-1)\leq c\leq n$。

#### 提示

[关于交互题](https://help.luogu.com.cn/manual/luogu/problem/interactive-problems)。

[样例交互库源代码链接](https://www.luogu.com.cn/paste/uimmq4nj)。**注意，此交互库仅供测试样例使用，实际评测时的交互库此交互库不同**。

如果您不知道如何在本地调试您的代码，请参考[这篇文章](https://www.luogu.com.cn/blog/fusu2333/solution-p1947)。

请特别注意，你的答案应该作为函数的返回值给出，**你不需要，也不应该向标准输出输出任何内容，否则将无法获得分数**。

如果有需要，你可以在选手程序的开头加入一些头文件，当然在本题中这并不是必须的。

交互库给出的函数 `Seniorious` 无法直接调用，需要在选手程序中用 `extern "C"` 关键字声明一次。

下面给出本题的模板程序（请不要使用 gcc9 提交）：

```cpp
#include <cstdio>                         // 在本题中并不是必须的

extern "C" int Seniorious(int);           // 在这里需要声明一次交互库给出的函数。

extern "C" int Chtholly(int n, int OvO) { // 在这里实现交互库要求你实现的函数。
  int ans = 1;
  for (int l = 1, r = n, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (Seniorious(mid) >= 0) {
    r = (ans = mid) - 1;
  } else {
    l = mid + 1;
  }
  return ans;
}
```


title: [COI2008] UMNOZAK

description:
定义一个正整数的位数积为其每一个数位的数字相乘的结果。例如：

$2612$ 的位数积为：$2\times 6\times 1\times 2=24$。

定义一个正整数的自积为这个数乘它的位数积之后的结果。例如：

$2612$ 的自积为：$2612\times 24=62688$。

给定两个整数 $A,B$，请你求出自积在 $[A,B]$ 这个区间内的正整数的个数。

inputFormat: 输入一行两个整数 $A,B$。

outputFormat: 输出一行一个整数，表示有多少个正整数的自积在区间 $[A,B]$ 内。


title: [SDOI2012] 棋盘覆盖

description:
在一个 $n\times m$ 的棋盘内，有 $K$ 个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘，保证特殊方格不能被覆盖，非特殊方格只能被一个俄罗斯方块覆盖，求最多能容纳的俄罗斯方块的数量。

已知有以下三组俄罗斯方块，一个棋盘可能用其中的某一组。

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

inputFormat:
第一行三个整数 $n,m,K$ 和一个字符 `type` 为所用的俄罗斯方块组。

接下来 $K$ 行每行两个整数 $x,y$ 表示第 $x$ 行第 $y$ 列为特殊方格。

outputFormat: 一个整数，为所求的答案。

hint:
对于测试点 $1\sim 6$，$1\le n,m\le 100$，$0\le K\le nm$，`type` 为 `A`；

对于测试点 $7\sim 12$，$2\le n=m\le 2^{2\times 10^5}$，$n,m$ 为 $2$ 的整数次幂，$K=1$，`type` 为 `B`；

对于测试点 $13\sim 21$，$1\le n,m\le 11$，$0\le K\le nm$，`type` 为 `C`。


title: [COCI2014-2015#1] PROSJEK

description:
有一个数列 $a$，现在按照下列公式求出一个数列 $b$：

$$b_i=\frac{ \sum^i_{j=1} a_j }{i}$$

给你数列 $b$，请求出数列 $a$。

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

接下来一行 $n$ 个整数，表示数列 $b$。

outputFormat: 一行 $n$ 个整数，表示数列 $a$。

hint:
#### 样例输入输出 3 解释
当数列 $a=1,3,2,6,8$ 时，数列 $b=\frac{1}{1},\frac{1+3}{2},\frac{1+3+2}{3},\frac{1+3+2+6}{4},\frac{1+3+2+6+8}{5}$，即 $b=1,2,2,3,4$。

#### 数据规模与约定
对于 $100\%$ 的数据，保证 $1\le n\le 100$，$1\le a_i,b_i\le 10^9$。

#### 说明
**本题总分 $50$ 分。**

本题译自 [Croatian Open Competition in Informatics 2014/2015](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf) T1 PROSJEK。


title: [COCI2014-2015#1] KLOPKA

description:
在平面直角坐标系上有 $n$ 个点。

现在要用一个正方形将点框起来，使得每一个点都能在正方形的内部或边上。要求这个正方形的边平行于坐标轴。

求出这个正方形的最小面积。

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

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

outputFormat: 一行一个整数，表示正方形的最小面积。

hint:
#### 样例输入输出 1 解释
一个方案是正方形的右上角在 $(7,7)$，左下角在 $(3,3)$。
#### 数据规模与约定
对于 $100\%$ 的数据，保证 $2\le n\le 20$，$1\le x,y\le 100$。
#### 说明
**本题总分 $80$ 分。**

本题译自 [Croatian Open Competition in Informatics 2014/2015](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf) T2 KLOPKA。


title: [COCI2014-2015#1] PIRAMIDA

background: Zoran 和 Tomislav 今天很无聊。

description:
于是，他们把他们喜欢的字符串 `JANJETINA` 按照一定规律在一个塔上从左到右从上到下写了一遍又一遍。

这是塔只有六层的情况：

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

现在他们想考你一个问题：给定字符串 $s$ 与塔的层数 $n$，将这个字符串在塔上写一遍又一遍，接下来会有 $k$ 个问题，第 $i$ 次问你字符 $c_i$ 在第 $a_i$ 层出现了几次。

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

第二行一个字符串 $s$。

第三行一个整数 $k$。

接下来 $k$ 行，第 $i$ 行为一个整数 $a_i$ 和一个字符 $c_i$。

outputFormat: 对于每个问题，输出一个一行一个整数。

hint:
#### 样例输入输出 1 解释

为题目中的例子。

#### 数据规模与约定

- 对于 $50\%$ 的数据，保证 $n\le 10^3$。
- 对于 $70\%$ 的数据，保证 $|s|\le 10^5$。
- 对于 $100\%$ 的数据，保证 $1\le n \le 10^{18}$，$1\le |s|\le 10^6$，$1\le k\le 5\times 10^4$，$1\le a_i\le n$，输入中涉及的字符均为大写字母。

#### 说明
**本题总分 $100$ 分。**

本题译自 [Croatian Open Competition in Informatics 2014/2015](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf) T3 PIRAMIDA。


title: [COCI2014-2015#1] MAFIJA

description:
有 $n$ 个人，其中有一些人是平民，有一些人是坏蛋。

现在，平民们想揪出所有的坏蛋，于是 $n$ 个人都指认了一个人是坏蛋。

如果一个人是平民，他会随便乱指认，否则，他会指认一个平民。

求出最多的坏蛋个数。

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

接下来 $n$ 行，每行一个整数 $k$，第 $i$ 行表示第 $i$ 个人指认了第 $k$ 个人。

outputFormat: 仅一行一个整数，表示最多的坏蛋个数。

hint:
#### 样例解释
#### 样例输入输出 1 解释
坏蛋可以是第 $2$ 个人和第 $3$ 个人。
#### 样例输入输出 2 解释
坏蛋可能是所有人，但是只能是其中的一个人，因为再多一个坏蛋的话会有坏蛋指控坏蛋的情况发生。

#### 数据范围与限制
- 对于 $40$ 分的数据，保证 $n\le 15$。
- 对于 $80$ 分的数据，保证 $n\le 2\times 10^4$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$1\le k\le n$。

#### 说明
**本题总分 $120$ 分。**

本题译自 [Croatian Open Competition in Informatics 2014/2015](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf) T4 MAFIJA。


title: [COCI2010-2011#1] PROFESOR

description:
在一个较长的教室中，$n$ 张桌子排成一排，每张桌子坐着 $2$ 个学生。
学生之所以胡思乱想是因为他们即将参加美术课，而他们的老师正计划对他们进行检查。

每个学生都学习过美术，但是只学习了一定水平。 这位教授可以通过脸上的表情告诉他们他们学了多少。 这位教授是一名艺术家，每个年级都使用不同的彩色铅笔。不幸的是，今天他只带了 $1$ 支铅笔。

为了使考试看起来公平，他想选择 $2$ 张桌子，并从他所选择的 $2$ 张桌子（包括所选的桌子）之间的每张桌子中向 $1$ 位学生提问。 重要的是所有受试学生都应获得相同的成绩，因此他可以用唯一的铅笔将其写下来。

教授想知道他可以通过这种方式检查的最大学生人数，以及学生将获得的分数。

inputFormat:
输入数据共 $n+1$ 行。

第一行包含一个整数 $n$，含义如题所示。

接下来的 $n$ 行，每行包含两个整数：$a_i$ 和 $b_i$，分别表示坐在课桌 $i$ 上的学生的成绩。

outputFormat:
输出数据共一行。

第一行包含 $2$ 个数字，并用一个空格隔开，分别表示教授可以考核的最大学生人数以及这些学生将获得的分数。

如果有多种解决方案，请输出分数最小的解决方案。

hint:
#### 数据范围

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

#### 说明

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


title: 「SWTR-7」My rating is -32（easy version）

background:
#### 本题是 My rating is ... 的 easy 版本。注意题目限制和数据范围与 [hard](https://www.luogu.com.cn/problem/T167832) 版本不同。

#### 请注意特殊的时空限制，题目描述下方有简化题意。

[My rating is -32.](https://codeforces.com/blog/entry/71123)

说明：上方的帖子是机房里某个同学很久很久以前的黑历史，现在成了机房传世经典，不是为了出比赛才发的，请不要误会。

description:
小 A 想在 Codeforces 上发 $n$ 篇帖子！例如：

> “My rating is 1064.”
>
> “I am PolarSea.”
>
> “你知道 phi 吗？你知道你的 phi 处是哪里吗？你知道它的 price 吗？1e9 + 7。”
>
>“每道题都很简单，全场虐题不用烦。T1 到场先签到，T2 上手随便切，T3 一交就能过，T4 稍想也能 A。DP 转移很容易，数学结论尽皆知。建图方法极明显，数据结构很一般。不卡空间不卡常，码量不大手不酸。没有毒瘤大模拟，只有良多大水题。片刻四题提交过，人人 AK 笑开颜。”
>
> “……”

为此，小 A 新注册了 $k$ 个账号。他决定**按照从 $1$ 到 $n$ 的顺序**发出每篇帖子，并**用到所有 $k$ 个账号**。不过刷屏过多会引起 Mike 的注意并被封号，小 A 当然不希望这样：他进行了一些评估，得到了每篇帖子的安全指数 $a_i$，表示他发出第 $i$ 篇帖子后不被封号的概率。

由于第一印象非常重要，小 A 定义一个账号的安全指数为该账号所发出的**第一篇**帖子的安全指数。此外，如果**用同一个账号连续发出两个帖子**，Mike 会立刻封掉这个账号，因此这种情况**是不合法的**。

小 A 希望找到这样一个发帖方案，使得所有账号的安全指数之和最大。你只需要求出安全指数之和的最大值即可。

---

**「简化题意」**

将 $1\sim n$ **不重不漏**地分进 $k$ 个集合 $S_1,S_2,\cdots,S_k$ 中，满足**相邻的数不在同一集合** 且 $|S_i|>0$。求

$$\sum_{i=1}^k a[{\min_{j\in S_i}j}]$$

的最大值，其中 $[]$ 表示**下标**。

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

第一行一个整数 $t$，表示该测试点编号。
第二行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个帖子的安全指数。

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

hint:
**「样例 1 说明」**

小 A 只能使用账号 $1$ 发帖子 $1$ 和 $3$，剩下的帖子用账号 $2$ 发。其安全程度为 $a_{\min(1,3)}+a_{\min(2,4)}=2$。

**「数据范围与约定」**

本题共有 6 个测试点。

- Testcase #0（1 points）：是样例。
- Testcase #1（10 points）：$k=2$。
- Testcase #2（30 points）：$n\leq 10$，$k\leq 4$。
- Testcase #3（15 points）：$k=3$。
- Testcase #4（20 points）：$n\leq 64$，$k\leq 7$。
- Testcase #5（24 points）：无特殊限制。

对于 $100\%$ 的数据，$2 \leq k \leq n \leq 10^4$，$0 \leq a_i \leq 10^9$，$T=10$。
对于所有测试点，**时间限制 200ms，空间限制 16MB。**

**「题目来源」**

[Sweet Round 07](https://www.luogu.com.cn/contest/) B1。
idea & solution：[tzc_wk](https://www.luogu.com.cn/user/115194)；data & 验题：[Alex_Wei](https://www.luogu.com.cn/user/123294)。

> **My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. ……**
>
> **Upvote -43 Downvote                  PolarSea**


title: [COCI2014-2015#1] ZABAVA

description:
一座新的公寓开放了，这座公寓有 $m$ 栋楼。

现在会有 $n$ 个学生，每一天都会进来一个人。

一栋楼进来一个人后，会进行一场派对，派对会有与当前人数相等的吵闹指数。

但是，现在可以进行 $k$ 次操作，每一次操作可以将一栋楼里的全部学生踢出这座新公寓。

请注意，学生先进楼，然后才能进行操作。

现在求出最小吵闹指数的相加之和。

你不必使用完全部的操作。

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

接下来 $n$ 行，一行一个整数 $p$，第 $i$ 行表示在第 $i$ 天，第 $i$ 个同学搬进了第 $p$ 栋楼。

outputFormat: 仅一行，表示最小吵闹指数的相加之和。

hint:
#### 样例说明
#### 样例输入输出 1 说明
可以在第一天和第三天清空第一栋楼，这样每一天的吵闹指数为 $1,1,2,1,2$，如果不清空每一天的吵闹指数为 $1,2,3,4,5$。
#### 样例输入输出 2 说明
在第四天和第八天清空第一栋楼，在第六天清空第二栋楼，这样每一天的吵闹指数为 $1,1,2,2,1,3,2,1,1,2,2$。
#### 数据范围及限制
- 对于 $40$ 分的数据，保证 $m=1$。
- 对于 $60$ 分的数据，保证 $n\le 10^3$。
- 对于 $80$ 分的数据，保证 $n\le 5\times 10^4$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le m\le 100$，$1\le k\le 500$，$1\le p\le m$。

#### 说明
**本题总分 $140$ 分。**

本题译自 [Croatian Open Competition in Informatics 2014/2015](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf) T5 ZABAVA。


title: 「SWTR-5」Sequence

description:
小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。他可以选择一个区间 $[l,r]$ 满足其最大值与最小值的差不超过 $k$。

他还需找出 $m$ 个**互不相同的整数** $p_1,p_2,\cdots,p_m$，满足：

- $m$ 为正整数。
- $\prod\limits_{i=l}^ra_i=\prod\limits_{i=1}^mp_i$。即选择区间的乘积等于这 $m$ 个数的乘积。
- $p_i$ 为一个质数的正整数次幂。

这 $m$ 个数的约数个数之和就是小 A 的得分。帮他求出得分的最大值。

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

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示这个序列。

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

hint:
「样例说明」

样例 $1$：选择区间 $[1,2]$，再选择 $p_1=2$，$p_2=3$，$p_3=4$，可以达到最大值 $7$，方案不唯一。

样例 $2$：选择区间 $[1,4]$，再选择 $p_1=4$，$p_2=8$，$p_3=3$，$p_4=27$，可以达到最大值 $13$。

「数据范围与约定」

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

- Subtask 1（1 points）：$n=1$ 且 $a_1$ 为质数。
- Subtask 2（9 points）：$n=1$。
- Subtask 3（20 points）：$n\leq 10$，$a_i \leq 20$。
- Subtask 4（13 points）：$n\leq 200$，$a_i \leq 200$。
- Subtask 5（17 points）：$n\leq 2\times 10^3$。
- Subtask 6（15 points）：$a_i$ 为质数。
- Subtask 7（25 points）：无特殊限制。

对于 $100\%$ 的数据：$1 \leq n \leq 10^5$，$2 \leq a_i \leq 10^5$，$0 \leq k \leq 10^5$。

---

「题目来源」

[Sweet Round 05](https://www.luogu.com.cn/contest/28195) B。
idea & solution：[ET2006](https://www.luogu.com.cn/user/115194)。


title: [COCI2010-2011#1] TABOVI

background: Zvonkec 是在一家小公司工作的程序员。

description:
Zvonkec 每天都必须重构一个源代码文件。令他大为沮丧的是，源代码的代码风格很奇怪。他尤其会受到缩进不均匀的困扰，即缩进每行的制表符（即键盘上的 `Tab`）的数量。

幸运的是，他的编辑器具有命令来选择一组连续的行，并从每行的开头添加或删除字符。请你帮助 Zvonkec 尽快整理代码。

给出的行数为 $n$，在每行开始处指定当前制表符数量的序列以及在每行开始处指定所需制表符数量的序列。

Zvonkec 可以执行许多命令，包括：

- 选择任意数量的连续行。
- 向每条选定行的开头添加或删除单个制表符。

无论选择多少行，以上两个动作都包含一个命令。

应该注意的是，禁止从一行中删除的制表符比在一行的开始处实际显示的要多，因为编辑器将开始删除除制表符以外的字符。

要求您计算整理代码所需的最少命令数。

inputFormat:
输入数据共三行。

第一行，一个正整数 $n$。

第二行有 $n$ 个整数 $p_i$，表示在进行任何编辑之前在第 $i$ 行的开头的制表符数。

第三行有 $n$ 个整数 $k_i$，表示 Zvonkec 在第 $i$ 行的开头想要的制表符数。

outputFormat:
输出数据共一行。

第一行，一个正整数，表示问题编号中指定的所需编号。

hint:
#### 数据范围
- 对于 $70\%$ 的数据，$1 \leq n \leq 100$，$0 \le p_i \le 80$，$0 \leq k_i \leq 80$。
- 对于 $100\%$ 的数据，$1 \leq n \le 1000$，$0 \le p_i \le 80$，$0 \leq k_i \leq 80$。
#### 说明

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


title: 「SWTR-7」IOI 2077

background:
#### 友情提醒：本题输入输出量很大，请不要使用 cin 或 scanf。题目最下方附有快读及其使用方法。

#### 赛时提醒：若对于选出的 $m$ 无解，则期望值为 $0$。可以结合样例 2 的解释说明以更好理解。

#### 赛时提醒：你需要求的是能力值之和的期望而不是最大值。

---

小 A 被 FCC 钦定参加 IOI 2077！71 岁老将请求出战！

description:
IOI 2077 有 $n$ 位**候选**参赛者，他们分别编号为 $1\sim n$。每位候选参赛者都有一个能力值，且**能力值互不相等**，第 $i$ 位候选参赛者的能力值为 $a_i$。小 A 更喜欢有序的数字，所以他将这 $n$ 位候选参赛者按照能力值**从小到大**排好了序，即**满足 $a_i<a_{i+1}\ (1\leq i<n)$。**

正式参赛者将会从这 $n$ 位候选参赛者中产生。具体地，所有参赛者将是候选参赛者的一个子串 $[l,r]$，即编号为 $l,l+1,\cdots,r$ 的选手将参加 IOI 2077，其中，小 A 的编号为 $k$。因为他知道自己被钦定参加 IOI 2077，所以 $l\leq k\leq r$。可能的参赛者一共有 $q$ 种情况，每种情况用三个数 $l_i,r_i,k_i\ (l_i\leq k_i\leq r_i)$ 描述，即参赛者为编号在区间 $[l_i,r_i]$ 中的候选参赛者，而小 A 的编号为 $k_i$。

由于自己太菜，小 A 对即将到来的 IOI 感到力不从心。他决定选择一些参赛者作为队友，并与他们在赛场上相互帮（zuo）助（bi）。具体地，设正式参赛人数为 $s$，那么小 A 会在 $[0,\lfloor\frac{s-1}{2}\rfloor]$ 中**等概率随机**选择一个数 $m$，并从 $s$ 位参赛者中**随机**选出 $2m$ 个作为他的队友。不过，小 A 不希望自己显得太菜，所以**他的能力值 $a_k$ 必须是这 $2m+1$ 个人的能力值的中位数**。

俗话说，人多力量大，小 A 希望他与所有选出的队友的能力值之和尽量地大。**不过在此之前，他想知道这个值的期望值是多少**。请对 $998244353$ 取模，保证答案在该模数下有意义。**对于每一种可能的参赛者情况，你都需计算该情况下的答案。为了避免过大的输出，你只需要计算所有答案的异或和。**

inputFormat:
第一行一个整数 $t$，**表示该测试点 Subtask 编号。**
第二行两个整数 $n,q$，分别表示候选参赛者个数和情况总数。
第三行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个候选参赛者的能力值。**保证 $a_i$ 递增。**
接下来 $q$ 行，每行三个整数 $l_i,r_i,k_i$ 描述一个可能的参赛者情况。

outputFormat: 输出一行一个整数，表示所有答案的异或和。

hint:
**「样例 1 说明」**

- 第 1 个询问：
  因为 $s_1=r_1-l_1+1=5$，所以 $m$ 可以为 $0,1$ 或 $2$。
  $m=0$ 时：小 A 没有队友，那么期望值就是他自身的能力值 $a_{k_1}=a_3=5$。
  $m=1$ 时：小 A 可以选**编号** $(1, 4)$ 或 $(1, 5)$ 或 $(2, 4)$ 或 $(2, 5)$ 的参赛者作为他的队友，能力值之和分别为 $14,15,15,16$，期望值为 $\frac{14+15+15+16}{4}=15$。
  $m=2$ 时：小 A 只能全选，期望值为 $2+3+5+7+8=25$。
	综上，期望值为 $\frac{5+15+25}{3}=15$。

- 第 2 个询问：
  因为 $s_2=r_2-l_2+1=3$，所以 $m$ 可以为 $0$ 或 $1$。
  $m=0$ 时，小 A 没有队友，期望值为 $3$。
  $m=1$ 时，小 A 无法选择，期望值为 $0$。
  综上，期望值为 $\frac{3+0}{2}=\frac{3}{2}$，对 $998244353$ 取模后为 $499122178$。

$15\oplus499122178=499122189$。

**「数据范围与约定」**

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

记 $s_i=r_i-l_i+1$。

- Subtask #0（1 point）：是样例。
- Subtask #1（10 points）：$s_i\leq 2$。
- Subtask #2（20 points）：$s_i\leq 16$，$q\leq 40$，$n\leq 640$。
- Subtask #3（15 points）：$s_i,q\leq 500$，$n\leq 10^5$。
- Subtask #4（15 points）：$s_i,q\leq 3\times 10^3$，$n\leq 10^5$。
- Subtask #5（15 points）：$s_i,q\leq 2\times 10^5$，$n\leq 5\times 10^5$。
- Subtask #6（24 points）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,q\leq 2\times 10^6$，$1\leq l_i\leq k_i\leq r_i\leq n$，$1 \le a_i \le 998244352$，$a_i<a_{i+1}\ (1\leq i<n)$。

对于所有测试点，时间限制 1s，空间限制 512MB。

**「帮助/提示」**

关于 [有理数取余](https://www.luogu.com.cn/problem/P2613)，[中位数](https://baike.baidu.com/item/%E4%B8%AD%E4%BD%8D%E6%95%B0/3087401?fr=aladdin)。

本题输入输出量**极大**，**请注意 I/O 优化。**
本题提供**有符号 32 位整数**快读模板，保证读入用时不超过 250ms：

```cpp
#define gc getchar()
inline int read(){
	int x=0; bool sgn=0; char s=gc;
	while(!isdigit(s))sgn|=s=='-',s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
	return sgn?-x:x;
}

// 如果需要读入直接调用 read() 即可。
// 一个例子（与正解无关，仅供参考）：

int t=read(),n=read(),q=read();
int a[2000005],l[2000005],r[2000005],k[2000005];
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=q;i++)l[i]=read(),r[i]=read(),k[i]=read();

// 这样你就可以在 250ms 内读入全部数据了。
```

**「题目来源」**

[Sweet Round 07](https://www.luogu.com.cn/contest/51773) C。
idea & solution：[SSerWarriors_Cat](https://www.luogu.com.cn/user/147999)；data：[Alex_Wei](https://www.luogu.com.cn/user/123294) ；验题：[chenxia25](https://www.luogu.com.cn/user/138400)。

---

IOI 2077 落下帷幕，小 A 凭借出（dui）色（you）的发（bang）挥（zhu）成功 AK 了 IOI，这不禁让他回想起曾经满腔热血的自己，以及和他共同奋斗在 OI 路上的战友们。如今他们虽已天各一方，说起来也有十几年没见过面了，但他们真挚的友谊未曾淡去，也将永远不会褪色。

>*“爷爷，您手机里有段录音，还写着 'ycx txdy!'。”*
>*“哦，是嘛？放出来听听。”*
>>*“I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you are vegetable chickens.”*
>>*“I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you are vegetable chickens.”*
>>*“I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you ............”*

2077.7.7


title: [COCI2011-2012#6] KOŠARE

description:
在一个废弃的阁楼里放置有 $n$ 个箱子，这些箱子里存放着 $m$ 种玩具。对于第 $i$ 个箱子，它里面有 $k_i$ 个玩具（不同的箱子里可能有相同的玩具）。

现在你需要选出一部分箱子，使得它们中共有 $m$ 种玩具（即所有种类的玩具都包含）。求选择的方案总数（$\bmod\ 10^9+7$）。

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

接下来的 $n$ 行，每行首先输入一个整数 $k_i$；接下来 $k_i$ 个数表示第 $i$ 个箱子里所含的玩具情况。

outputFormat: 输入一行一个整数，为方案总数（$\bmod\ 10^9+7$）。

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

- 对于 $50\%$ 的数据，保证 $n\le 100$，$m\le 15$；
- 对于 $70\%$ 的数据，保证 $m\le 15$；
- 对于 $100\%$ 的数据，保证 $1\le n\le 1\times 10^6$，$1\le m\le 20$，$0\le k_i\le m$。

#### 说明

- **题目译自 [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T6 KOŠARE***。
- 感谢 @[一扶苏一](https://www.luogu.com.cn/user/65363) 的翻译支持！


title: [COCI2011-2012#6] PASTELE

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

Mirko 收到了一份礼物。

description:
这份礼物共包含 $n$ 支蜡笔。每只蜡笔的颜色由色光三原色组成：红、绿、蓝。分别用参数 $R_i,G_i,B_i$ 表示。这只蜡笔的颜色就由这三个参数来决定。

对于两支蜡笔 $i,j$，我们定义它们之间的差异值为 $\max(|R_i-R_j|,|G_i-G_j|,|B_i-B_j|)$。定义一些蜡笔的色彩值为这些蜡笔中任意两支蜡笔差异值的最大值。

给出这 $n$ 支蜡笔的特征值，请找出 $k$ 支蜡笔，使得色彩值最小。

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

接下来的 $n$ 行，每行三个整数 $R_i,G_i,B_i$，表示第 $i$ 支蜡笔的颜色参数。

outputFormat:
输出第一行为一个整数，表示 $k$ 支蜡笔的色彩值的最小值。

接下来的 $k$ 行，每行三个整数，描述这 $k$ 支蜡笔都由哪些蜡笔组成。

**由于方案的组成可能不唯一，本题使用SPJ**。

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

- 对于 $50\%$ 的数据，保证 $R_i,G_i,B_i\le 20$；
- 对于另 $30\%$ 的数据，保证 $R_i,G_i,B_i\le 50$；
- 对于 $100\%$ 的数据，保证 $2\le k\le n\le 10^5$，$0\le R_i,G_i,B_i\le 256$，$0\le k_i\le m$。

#### 提示

请注意常数因子对程序效率造成的影响。

#### 说明

**题目译自 [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T5 PASTELE***。


title: 麻将 加强版

background:
此题我本来是想出公开赛的，没想到撞题了。

题面是我自己撰写的，与原题不同。

此题题意与 [P4050](https://www.luogu.com.cn/problem/P4050) 大致相同，**有少许不同**，**且数据范围有所更改**。

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

小 A 喜欢打麻将。

description:
小 A 找到了一副奇怪的麻将牌：只有一种 $1,2,\cdots,n$ 的数牌，且每种牌都有**无穷多张**。

定义「雀头」为两张一样的牌（如 $2,2$，$7,7$），「刻子」为三张一样的牌（如 $1,1,1$，$4,4,4$），「顺子」为三张序数相邻的牌（如 $1,2,3$，$9,10,11$，注意 $1$ 与 $n$ 不相邻）。「顺子」与「刻子」统称「面子」。

假如你能把你的手牌分为若干组「雀头」（**可以相同**），或者分为若干组「面子」（**可以相同**）以及一组「雀头」，那么你就可以「和牌」。

假如某副手牌加上某张牌后可以「和牌」，则称这副手牌「听」这张牌。

现在小 A 随意摸了 $k$ 张牌，他想知道他「听」哪些牌。

inputFormat:
第一行两个正整数 $n,k$，分别表示牌的范围和小 A 手上牌的张数。

接下来一行 $k$ 个整数 $a_1,a_2,\cdots,a_k$ 给出小 A 的手牌，每个数表示小 A 手上的一张牌。**不保证按升序给出。**

outputFormat:
第一行一个正整数 $t$，表示小 A「听」的牌的种数。

接下来一行 $t$ 个正整数，表示小 A「听」哪些牌。**请按照升序输出。**


title: [COCI2011-2012#6] ZAGRADE

description:
给定一个算术表达式，有些部分用括号括起来表示优先级的不同。请你删除一些互相匹配的括号对，并输出所以删除的方案。按照字典序输出。

比如，给定一个算术表达式 `(2+(2*2)+2)`，所有合法的方案为 `(2+2*2+2)` `2+(2*2)+2` `2+2*2+2`。而 `(2+2*2)+2` `2+(2*2+2)` 并不合法，因为删除的括号对不互相匹配。

inputFormat: 输入一行一个算术表达式。

outputFormat: 输出不同的通过删除合法的括号对获得的算术表达式。按照字典序输出。

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

对于 $100\%$ 的数据，保证给出的算术表达式的长度不超过 $200$，输入仅包含 `+` `-` `*` `/` `(` `)`。

#### 说明

**题目译自 [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T3 ZAGRADE***。


title: [COCI2011-2012#6] REZ【征集SPJ】

background: ## 本题征集SPJ，有意提供者可发帖并@题目提供者或私信。

description:
有一个由蓝莓、草莓和巧克力制成的矩形蛋糕。它的形状类似一个广场，左下角坐标为 $(-5000,-5000)$，右上角坐标为 $(5000,5000)$。（坐标系的单位是毫米）面积为 $100$ 平方米。

专业人员强烈建议用湿刀和干勺子食用这块蛋糕。并且：

- 每一刀的起始点都在蛋糕的边上；
- 一次切割不能完全切割在蛋糕的边上；
- 没有任何两刀有相同的起点和终点；也就是说，所有的切割线都是不同的。

只有在切割完最后一次后才能进行分离和计数。也就是说，在切割蛋糕的过程中，蛋糕始终保持矩形不变。

请你找出：最少要切几刀才能把蛋糕切成至少 $k$ 块？并输出每一刀的起点和终点坐标。

inputFormat: 输入一行一个整数 $k$，表示至少把蛋糕切成的块数。

outputFormat:
输出第一行为一个整数 $n$，表示最少的刀数。

接下来的 $n$ 行，每行四个整数。分别为这一刀起点的坐标和终点的坐标。

对于蛋糕边上的每个点，保证 $\max(|x|,|y|)=5000$。

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

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

#### 说明

**题目译自 [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T4 REZ***。


title: [COCI2019-2020#5] Emacs

description:
给定一个 $n\times m$ 的只含有 `.` 和 `*` 的矩阵。

矩阵中 `*` 形成一些不重叠的长方形。它们不在边缘或顶点接触。

求长方形有多少个？

inputFormat:
第一行：两个正整数 $n$ 和 $m$。

以下 $n$ 行：表示题目描述中的矩阵。矩阵只含有 `.` 和 `*`。

outputFormat: 一行一个非负整数，你的答案。

hint:
### 数据范围

- 对于 $10 pts$ 的数据，矩阵中每个长方形只含一个 `*`。
- 对于另外 $15 pts$ 的数据，保证 $n=1$。
- 对于所有的数据，$1\leq n,m\leq 100$。

### 说明

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


title: [COCI2019-2020#5] Politicari

description:
有 $n$ 个人互相批评。

另提供矩阵 $A$。

规则如下：

- 第一次，第 $1$ 个人批评第 $2$ 个人。

- 如果第 $i-1$ 次为第 $u$ 个人批评第 $v$ 个人，

	那么第 $i$ 次为第 $v$ 个人批评第 $A_{v,u}$ 个人。

求第 $k$ 次是谁**进行**批评（注意：不是**被**批评）。

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

以下 $n$ 行：矩阵 $A$。矩阵的主对角线（就是从左上到右下的那条对角线）全是 $0$，其他部分由从 $1$ 到 $n$ 的正整数组成。

outputFormat: 一行：你的答案。

hint:
### 数据范围

- 对于 $35 pts$ 的数据，保证 $1\leq k\leq 10^5$。
- 对于所有的数据，$2\leq n\leq 500$ 且 $1\leq k\leq 10^{18}$。

### 说明

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


title: [COCI2011-2012#6] JACK

description: 给定 $n$ 个正整数 $a_1 \dots a_n$，请从中选择 $3$ 个数字，满足他们的和不大于给定的整数 $m$，请求出这个和最大可能是多少。

inputFormat:
第一行有两个整数，分别表示数字个数 $n$ 和给定的整数 $m$。

第二行有 $n$ 个整数，表示给定的 $n$ 个数字 $a_i$。

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

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

- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$6 \leq m \leq 3 \times 10^5$，$1 \leq a_i \leq 10^5$，数据保证有解。

#### 说明

**题目译自 [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T1 JACK***，翻译来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: [COCI2011-2012#6] PROZORI

background: 春天来了，人们渐渐的开始拉下了自己的百叶窗。

description:
我们把一扇百叶窗用一个 $4 \times 4$ 的方阵表示。其中每一行要么全是字符 `*`，要么全是字符 `.`。百叶窗只会有下面五种状态：

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

对面的大楼共有 $n$ 层，每层有 $m$ 扇窗户。给定大楼的窗户状态表示，请求出上面五种状态的百叶窗各有几扇。

inputFormat:
第一行有两个整数，分别表示大楼的层数 $n$ 和窗户数 $m$。

下面 $(5n + 1)$ 行，每行 $(5m + 1)$ 个字符，描述大楼的窗户。窗户的边框用 `#` 表示，内部只有可能是上面给出的五种状态。你可以阅读样例来更好的理解输入格式。

outputFormat: 输出一行五个用空格隔开的整数，依次表示上述五种状态的百叶窗各有几扇。

hint:
#### 样例 1 解释

- 以第 $2$ 行第 $2$ 列为左上角，第 $5$ 行第 $5$ 列为右下角的是一扇窗户，是第一种状态。
- 以第 $2$ 行第 $7$ 列为左上角，第 $5$ 行第 $10$ 列为右下角的是另一扇窗户，是第三种状态。

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n, m \leq 100$。

#### 说明

**题目译自 [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T2 PROZORI***，翻译来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: 不可视境界线[环版本]

background:
- 原题 : [P5617 [MtOI2019]不可视境界线](https://www.luogu.com.cn/problem/P5617)

**附** : [关于本题的`SPJ`和数据的一些信息](https://www.luogu.com.cn/paste/tmwvh5vh)

若出现卡精度或数据出锅,吊打标算等情况,请联系出题人。

description:
有 $n$ 个半径为 $r$ 的圆,画在一个长度为 $L$ 的首尾相接的纸环上。

所有的圆心都在同一高度,可以看做在纸上画一个数轴然后卷起来,圆心的位置用这个数轴上的点描述。

如果无法理解纸环上圆的分布,可以查看样例解释以及子问题。

要求选出 $k$ 个圆,使得所有圆的并面积最大。

注意,您需要回答确切的选取方案而不是仅仅给出最大并面积。

inputFormat:
第一行包含四个整数 $n,k,r,L$ ,意义如题目所述。

第二行包含 $n$ 个整数,第 $i$ 个整数 $p[i]$ 描述了第 $i$ 个圆心在纸环上的位置(数轴上的坐标)。

对于 $2<i<n$ ,有 $p[i-1]<p[i]$。

outputFormat:
一行包含 $k$ 个整数,分别表示您选取的圆的编号,由`SPJ`来计算并面积。

您需要保证这些编号严格递增,并且在 $[1,n]$ 以内,否则被认为不合法而不得分。

与标准答案**相对误差**不超过 $10^{-9}$ ,**且绝对误差**不超过 $0.1$ 则认为正确。

通过估算,答案不会超过 $10^{12}$ 量级。

hint:
**样例解释** :

- **样例1** : 最终的并面积约为 $565.871835$。

圆的分布如图所示,其中, $⊙A$ 和 $⊙A2$ 是同一个圆, $⊙B$ 和 $⊙B2$ 是同一个圆。

可以视作向右平移 $L=30$ 个单位长度而得,事实上就相当于在纸环上绕了一圈回到起点。

由于是同一个圆,被红色部分覆盖的面积不能重复计算,最大的并面积即为蓝色部分的面积。

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

- **样例2** : 最终的并面积约为 $942.477796$。

- **样例3** : 最终的并面积约为 $16817.058547$。

**数据范围与约定** :

| 子任务编号 | n | k | 时限 |
| :--: | :--: | :--: | :--: |
| 1 | $10$ | - | $\texttt{1s}$ |
| 2 | $100$ | - | $\texttt{1s}$ |
| 3 | $2000$ | - | $\texttt{1.6s}$ |
| 4 | $3\times 10^4$ | $100$ | $\texttt{2.2s}$ |
| 5 | $1\times 10^5$ | - | $\texttt{3s}$ |

时限在 `std` 耗时的两倍以上。

对于所有的数据, $n\leq 10^5$，$10\leq r\leq 2000$，$0\leq p[i]< L\leq 10^8$，$4r<L$，$3\leq k \leq n$。

表格中均为上界。注意,一些下界限制可能帮助省去了问题的某些边界情况。

tags: 凸完全单调性, wqs 二分


title: [COCI2010-2011#4] PARKET

description:
有一个 $n$ 行 $m$ 列的方格阵，最外圈的方格是红色的，其余方格是黑色的。

给出红色方格的个数 $r$ 和黑色方格的个数 $b$，请给出一组可行的 $n$，$m$ 的取值。

inputFormat: 输入只有一行两个整数，分别表示红色方格的个数 $r$ 和黑色方格的个数 $b$。

outputFormat: 输出一行两个整数，分别表示方格阵的行数 $n$ 和列数 $m$。如果有多组解，请输出 $n$ 最大的一组。

hint:
#### 样例 2 解释

输出给出的方格阵如图：其中浅色格子代表红色，深色格子代表黑色。

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

#### 数据规模与约定

对于全部的测试点，保证 $8 \leq r \leq 2 \times 10^6$，$1 \leq b \leq 2 \times 10^{6}$。数据保证至少存在一组解。

#### 说明

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


title: [COCI2008-2009#6] CUSKIJA

description: 给定一个长度为 $n$ 的序列 $a$，请将其重新排序，新序列中任意相邻两个数之和都不能被 $3$ 整除。

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

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个元素 $a_i$。

outputFormat:
**本题存在 Special Judge**。

- 如果存在解，请在第一行输出一行一个字符串 `Yes`，并在第二行输出 $n$ 个整数，第 $i$ 个整数表示新序列的第 $i$ 个元素。
- 如果无解，请只输出一行一个字符串 `No`。

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

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

#### 【说明】

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T4 CUSKIJA***，翻译与 SPJ 均来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)。为了 SPJ 判定方便，输出格式较原题略有修改。


title: [COCI2008-2009#4] ROT

description:
给定一个 $r\times c$ 的由字符组成的方桌，你需要输出这个桌子按顺时针方向旋转 $k$ 度之后的状态。

保证 $k$ 为 $45$ 的倍数。

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

接下来的 $r$ 行，每行 $c$ 个字符，表示这个字符方桌初始排列状态。

接下来的一行为一个整数 $k$，表示顺时针旋转的角度。

outputFormat: 输出这个方桌最终旋转的状态。

samples:
  d
 m a
d a m
 a r i
  r k r
   k o
    o

samples:
    e
   d f
  c e g
 b d f h
a c e g i
 b d f h
  c e g
   d f
    e

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

对于 $100\%$ 的数据，$1\le r,c\le 10$。

#### 说明

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #4](https://hsin.hr/coci/archive/2008_2009/contest4_tasks.pdf) *T3 ROT***。


title: [COCI2008-2009#4] SLIKAR

background: Josip 是一个奇怪的画家。

description:
他想画一幅由 $n\times n$ 个像素点组成的画。其中 $n$ 是 $2$ 的幂次（如 $1,2,4,8,16,\dots$）。每个像素点将会被着色为黑色或者白色。Josip 目前已经知道他的理想画作了。

他将按照如下步骤作画：

- 如果整幅画是一个像素点，那么他将依照自己的目标把这个像素点涂成黑色或者白色。

- 否则，他会将正方形分为四个更小的正方形，然后：

1. 从中选择一个正方形全部涂成白色。
1. 再从剩下的三个正方形中选择一个全部涂成黑色。
1. 把剩下的两个正方形当成一幅新的画作，重复上述步骤。

很快他就发现把心目中的画作完完整整的画出来是不可能的。所以，他希望你来编写一个程序，使得画出的一幅画与他心目中的理想画作的差异尽量小。

两张画作之间的差异为颜色不同的像素点的数目。

inputFormat:
输入第一行为一个整数 $n$，表示画作的边长。

接下来的 $n$ 行，每行 $n$ 个为 $0$ 或 $1$ 的数字，表示理想状态当前像素点为黑色或者白色。

outputFormat:
输出第一行一个整数，表示最小的差异值。

接下来的 $n$ 行，每行 $n$ 个为 $0$ 或 $1$ 的数字，表示实际上当前像素的颜色。

**注意：染色的方案可能有多种，输出任意一种即可，本题使用SPJ**。

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

- 对于 $50\%$ 的数据，$n\le 8$；
- 对于 $100\%$ 的数据，$1\le n\le 512$。

#### 说明

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #4](https://hsin.hr/coci/archive/2008_2009/contest4_tasks.pdf) *T4 SLIKAR***。


title: [COCI2008-2009#4] TREZOR

description:
在平面直角坐标系中，有一个以 $(1,-A)$ 和 $(L,B)$ 为对角线上的两个端点的矩形。这个矩形内有 $L\times (A+1+B)$ 个点。

现在有两名警卫分别在 $(0,-A)$ 和 $(0,B)$ 两个点。他们都看向这个矩形。如果他的视线（为一条射线）与矩形内的一个点之间有其他点阻隔，那么他就看不到这个点。

对于每一个点：

- 如果它能被两个警卫都看到，那么就认为它是非常安全的；
- 如果z只能被其中一个警卫都看到，那么就认为它是安全的；
- 如果两个警卫都看不到它，那么就认为它是危险的。

给定 $A,B,L$，你需要找出非常安全的点、安全的点和危险的点分别的数量。

inputFormat:
输入第一行为两个整数 $A,B$。

第二行为一个整数 $L$。

outputFormat: 输出共 $3$ 行。每行一个整数，依次为危险、安全、非常安全的点的数量。

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

- 对于 $50\%$ 的数据，$L\le 1000$；
- 对于另 $25\%$ 的数据，$A,B\le 100$；
- 对于 $100\%$ 的数据，$1\le A,B\le 2000$，$1\le L\le 10^9$。

#### 说明

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #4](https://hsin.hr/coci/archive/2008_2009/contest4_tasks.pdf) *T5 TREZOR***。


title: [COCI2008-2009#4] PERIODNI

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

如图，给定一个由 $n$ 列组成的表格，每一列的底部都是对齐的。

你需要再里面填入 $k$ 个相同的数。但不得有任意两个数在同一行或者同一列。

比如，上图中 `b` 的填写就是不合法的；因为两个 `b` 在同一列上。但 `a` 的填写是合法的，因为这两个 `a` 虽然在同一行，但是中间断开了，所以不算做非法。

请求出填写的方案总数 $\bmod\ 10^9+7$ 的结果。

inputFormat:
输入第一行两个整数 $n,k$，表示表格的列数和相同数字的数量。

第二行包含 $n$ 个整数，第 $i$ 个整数表示从左至右第 $i$ 列的层数。

outputFormat: 输出一行一个整数，表示方案总数 $\bmod\ 10^9+7$ 的结果。

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

- 对于 $40\%$ 的数据，输入的数字都小于 $15$；
- 对于 $70\%$ 的数据，输入的数字都小于 $100$；
- 对于 $100\%$ 的数据，$1\le n,k\le 500$，层高不会超过 $10^6$。

#### 说明

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


title: [COCI2008-2009#4] A

description:
给定五个数字组成的序列 $a$，$1 \sim 5$ 在这五个数字中均恰好出现一次。现在请按照如下操作对序列进行排序。

1. 若 $a_1 > a_2$，则交换 $a_1$ 和 $a_2$。
2. 若 $a_2 > a_3$，则交换 $a_2$ 和 $a_3$。
3. 若 $a_3 > a_4$，则交换 $a_3$ 和 $a_4$。
4. 若 $a_4 > a_5$，则交换 $a_4$ 和 $a_5$。
5. 如果序列没有变成 $\{1, 2, 3, 4, 5\}$，则回到第一步，继续排序。

请在**每次交换**后输出当前序列。

inputFormat: 输入只有一行五个数，表示序列 $a$。

outputFormat: 输出若干行，每行输出五个用空格隔开的整数，表示一次交换后的序列。

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

对于全部的测试点，保证 $1 \leq a_i \leq 5$，$a_i$ 互不相同，且不是单调递增的。

#### 提示

可以证明，交换次数不超过 $25$ 次。

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


title: [COCI2008-2009#4] B

description: 给定一个 $2009$ 年的日期，请确定这一天是周几。

inputFormat: 输入只有一行两个整数 $d$，$m$，其中 $m$ 表示月份，$d$ 表示该月的哪一天。

outputFormat:
输出一行一个字符串，表示答案。对于一周中每天的对应输出如下：

| 日期 |    输出     |
| :--: | :---------: |
| 周一 |  `Monday`   |
| 周二 |  `Tuesday`  |
| 周三 | `Wednesday` |
| 周四 | `Thursday`  |
| 周五 |  `Friday`   |
| 周六 | `Saturday`  |
| 周日 |  `Sunday`   |

samples:
1 1
Thursday

samples:
17 1
Saturday

samples:
25 9
Friday

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

对于全部的测试点，保证给出的日期是一个真实存在于 $2009$ 年的日期。

#### 提示

- $2009$ 年 $1$ 月 $1$ 日是周四。
- 请注意输入时先输入日再输入月。

#### 说明
**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #4](https://hsin.hr/coci/archive/2008_2009/contest4_tasks.pdf) *T2 DATUM***。


title: [COCI2008-2009#6] NERED

description:
有一个方阵，方阵每行、每列均有 $n$ 个格子。每个格子上都有一个数，初始时均为 $0$。有 $m$ 次修改，每次会将某个格子上的数 $+1$。

定义一步操作为将某个**非零**格子上的数 $-1$，将另一个格子（可以为 $0$）上的数 $+1$。

请求出最小的操作步数，使得所有格子上的数均为 $0$ 或 $1$，且所有为 $1$ 的格子构成一个矩形。输出操作步数。

inputFormat:
第一行有两个整数，分别表示方阵的行列数 $n$ 和修改数 $m$。

接下来 $m$ 行，每行两个整数 $x, y$，表示将 $x$ 行 $y$ 列的格子上的数增加 $1$。

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

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

**样例 1 解释**

将第 $1$ 行第 $1$ 列减去 $1$，第 $2$ 行第 $1$ 列加上 $1$。

**样例 3 解释**

- 将第 $2$ 行第 $3$ 列减去 $1$，在第 $3$ 行第 $3$ 列加上 $1$。
- 将第 $4$ 行第 $2$ 列减去 $1$，在第 $2$ 行第 $5$ 列加上 $1$。
- 将第 $4$ 行第 $4$ 列减去 $1$，在第 $3$ 行第 $5$ 列加上 $1$。

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

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

- $1 \leq n \leq 100$，$1 \leq m \leq n^2$。
- $1 \leq x, y \leq n$。
- 输入数据一定存在解。

#### 【说明】

**题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T3 NERED***，翻译来自 @[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: [COCI2006-2007#5] TRIK

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

有三个杯口朝下的杯子，其中有一个小球在最左边的杯子下。

接下来，对这三个杯子进行一系列的换位操作，操作用一个字符串来表示，其中 `A` `B` `C` 分别对应了上图所示的三种换位方式。

你需要找出最终小球在哪个杯子下面。

inputFormat: 输入一行一个字符串，表示操作的顺序，保证操作数不超过 $50$ ，且每个字母都为 `A` `B` `C` 中的一种，无空格。

outputFormat:
输出一行一个整数：

- 如果球在左边的杯子下：输出 $1$；
- 如果球在中间的杯子下：输出 $2$；
- 如果球在右边的杯子下：输出 $3$。

hint:
#### 说明

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


title: [COCI2006-2007#5] NATRIJ

description:
给定一个起始时间和结束时间，你需要求出这段时间间隔是多长。

保证时间间隔至少是 $1$ 秒钟，最多是 $24$ 小时。

inputFormat:
输入共两行。每行一个字符串，分别表示起始时间和结束时间。

格式为 `hh:mm:ss` （时，分，秒）。

输入保证小时为 $0\sim 23$ 之间的整数，分钟和秒钟为 $0\sim59$ 之间的整数

outputFormat: 输出一行一个字符串，表示间隔的时间，格式同输入。

hint:
#### 说明

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


title: [COCI2006-2007#5] TENIS

description:
两个球员正常进行一次网球比赛，比赛由 $n$ 轮组成，每一轮都会进行 $1\sim 5$ 次对决不等。每次对决的结果用 `A:B` 表示，其中 `A` 为第一个球员的获胜场次，`B` 为第二个球员的获胜场次。

比赛有以下规则：

- 如果其中一个球员获胜了 $6$ 个球及以上，并且他比另一个球员至少多获胜两个球，那么这一次对决他就胜利了。
- 此外，如果第一、二次对决的结果都是 `6:6` 那么将会进行一轮决赛来准确的得出一位球员获胜。
- 当有一名球员获胜两次对决时，他就是这轮比赛的胜者，且这轮比赛结束。

如果一轮比赛按照上述规则顺利进行，并且最终得以结束，那么我们就认为这轮是有效的。

但是，有一名特殊的球员—— `federer`,他不会输掉任意一次对决。（因为我们知道他来自外太空..）

你需要检验这 $n$ 轮比赛是否有效。

inputFormat:
输入第一行两个字符串，用空格隔开，表示两名参赛的选手。

第二行为一个整数 $n$，表示一共进行了 $n$ 轮比赛。

接下来的 $n$ 行，每行有 $1\sim 5$ 个形如 `A:B` 的对决结果。保证 `A` `B` 是介于 $0\sim 99$ 之间的整数。

outputFormat:
输出共 $n$ 行。

对于每轮比赛，输出 `da` 表示结果有效或输出 `ne` 表示结果无效。

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

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

#### 说明

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


title: [COCI2006-2007#5] LIGA

description:
一共有 $n$ 支队伍参加了一场大赛。每支队伍会有 $5$ 个参数：总参加场次、胜场数、平场数、负场数和得分。其中，每胜一场记 $3$ 分，每平一场记 $1$ 分，负场不计分。

但由于统计表收到了污损，一些数据看不清了（用 `?` 表示），所以你需要根据其他数据进行推理，补全表格。

已知每队最多进行 $100$ 场比赛，保证每处污损都有唯一的原数据与之对应。

注意，可能所有队伍的获胜场数不符合比赛的逻辑，可以把每支队伍看成独立的个体。

inputFormat:
输入第一行一个整数 $n$，表示队伍的数量。

接下来的 $n$ 行，每行 $5$ 个整数或者 `?`，依次为总参加场次、胜场数、平场数、负场数和得分。

outputFormat:
输出共 $n$ 行，每行 $5$ 个整数，为数据全部恢复后的表格。

**保证有唯一解。**

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

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

#### 说明

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