title: 数楼梯

description:
楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

inputFormat: 一个数字，楼梯数。

outputFormat: 输出走的方式总数。


title: 显示图像

type: P

description:
古老的显示屏是由 $N \times M$ 个像素（Pixel）点组成的。一个像素点的位置是根据所在行数和列数决定的。例如 $P(2,1)$ 表示第 $2$ 行第 $1$ 列的像素点。那时候，屏幕只能显示黑与白两种颜色，人们用二进制 $0$ 和 $1$ 来表示。$0$ 表示黑色，$1$ 表示白色。当计算机发出一个指令：$P(x,y)=1$，则屏幕上的第 $x$ 行第 $y$ 列的阴极射线管就开始工作，使该像素点显示白色，若 $P(x,y)=0$，则对应位置的阴极射线管不工作，像素点保持黑色。在某一单位时刻，计算机以 $N \times M$ 二维 $01$ 矩阵的方式发出显示整个屏幕图像的命令。

例如，屏幕是由 $3 \times 4$ 的像素点组成，在某单位时刻，计算机发出如下命令：

$$\begin{pmatrix}
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 \\
\end{pmatrix}$$

对应屏幕显示应为：

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

假设放大后，一个格子表示一个像素点。

由于未知的原因，显示黑色的像素点总是受显示白色的像素点的影响——可能是阴极射线管工作的作用。并且，距离越近，影响越大。这里的距离定义如下：

设有像素点 $P_1(x_1,y_1)$ 和像素点 $P_2(x_2,y_2)$，则它们之间的距离 $D(P_1,P_2)=|x_1-x_2|+|y_1-y_2|$。

在某一时刻，计算机发出显示命令后，科学家们期望知道，每个像素点和其最近的显示白色的像素点之间的最短距离是多少——科学家们保证屏幕上至少有一个显示白色的像素点。

上面的例子中，像素 $P(1,1)$ 与最近的白色像素点之间的距离为 $3$，而像素 $P(3,2)$ 本身显示白色，所以最短距离为 $0$。

inputFormat:
第一行有两个数字，$N$ 和 $M\ (1 \le N,M \le 182)$，表示屏幕的规格。

以下 $N$ 行，每行 $M$ 个数字，$0$ 或 $1$。为计算机发出的显示命令。

outputFormat: 输出文件有 $N$ 行，每行 $M$ 个数字，中间用 $1$ 个空格分开。第 $i$ 行第 $j$ 列的数字表示距像素点 $P(i,j)$ 最近的白色像素点的最短距离。


title: 平面上的最接近点对

description: 给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的。

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

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

outputFormat: 仅一行，一个实数，表示最短距离，四舍五入保留 $4$ 位小数。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^4$，$0 \leq x, y \leq 10^9$。


title: 小车问题

description: 甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。

inputFormat: 仅一行，三个实数，分别表示 AB 两地的距离 $s$，人的步行速度 $a$，车的速度 $b$。

outputFormat: 两人同时到达 B 地需要的最短时间，保留 $6$ 位小数。

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

对于 $100\%$ 的数据，保证 $0 \leq s, a, b \leq 10^9$。


title: 黑白棋子的移动

description:
有 $2n$ 个棋子排成一行，开始为位置白子全部在左边，黑子全部在右边，如下图为 $n=5$ 的情况：

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

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如 $n=5$ 时，成为：

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

任务：编程打印出移动过程。

inputFormat: 一个整数 $n$。

outputFormat: 若干行，表示初始状态和每次移动的状态，用 $\verb!o!$ 表示白子，$\verb!*!$ 表示黑子，$\verb!-!$ 表示空行。


title: 工程规划

description:
造一幢大楼是一项艰巨的工程，它是由 $n$ 个子任务构成的，给它们分别编号 $1,2,\cdots,n\ (5≤n≤1000)$。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间 $T_1,T_2,\cdots,T_n$ 并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。

这种要求就可以用 $m\ (5≤m≤5000)$ 个不等式表示，不等式形如 $T_i-T_j≤b$ 代表 $i$ 和 $j$ 的起始时间必须满足的条件。每个不等式的右边都是一个常数 $b$，这些常数可能不相同，但是它们都在区间 $(-100,100)$ 内。

你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列 $T_1,T_2,\cdots,T_n$，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，$T_1,T_2,\cdots,T_n$ 中至少有一个为 $0$。

inputFormat: 第一行是用空格隔开的两个正整数 $n$ 和 $m$，下面的 $m$ 行每行有三个用空格隔开的整数 $i,j,b$ 对应着不等式 $T_i-T_j≤b$。

outputFormat: 如果有可行的方案，那么输出 $n$ 行，每行都有一个非负整数且至少有一个为 $0$，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息 `NO SOLUTION`。


title: 服务器储存信息问题

description:
Byteland 王国准备在各服务器间建立大型网络并提供多种服务。

网络由 $n$ 台服务器组成，用双向的线连接。两台服务器之间最多只能有一条线直接连接，同时，每台服务器最多只能和 $10$ 台服务器直接连接，但是任意两台服务器间必然存在一条路径将它们连接在一起。

每条传输线都有一个固定传输的速度。$\delta(v,w)$ 表示服务器 $v$ 和 $w$ 之间的最短路径长度，且对任意的 $v$ 有 $\delta(v,v)=0$。

有些服务器比别的服务器提供更多的服务，它们的重要程度要高一些。我们用 $r(v)$ 表示服务器 $v$ 的重要程度 $\texttt{rank}$。$\texttt{rank}$ 越高的服务器越重要。

每台服务器都会存储它附近的服务器的信息。当然，不是所有服务器的信息都存，只有感兴趣的服务器信息才会被存储。服务器 $v$ 对服务器 $w$ 感兴趣是指，不存在服务器 $u$ 满足，$r(u)>r(w)$ 且 $\delta(v,u)\le\delta(v, w)$。

举个例子来说，所有具有最高 $\texttt{rank}$ 的服务器都会被别的服务器感兴趣。如果 $v$ 是一台具有最高 $\texttt{rank}$ 的服务器，由于 $\delta(v,v)=0$，所以 $v$ 只对具有最高 $\texttt{rank}$ 的服务器感兴趣。

我们定义 $B(v)$ 为 **$v$ 感兴趣**的服务器的集合。我们希望计算所有服务器储存的信息量，即所有服务器的 $|B(v)|$ 之和。Byteland 王国并不希望存储大量的数据，所以所有服务器存储的数据量 （$|B(v)|$ 之和）不会超过 $30n$。

你的任务是写一个程序，读入 Byteland 王国的网络分布，计算所有服务器存储的数据量。

inputFormat:
第一行两个整数 $n$ 和 $m$。$n$ 表示服务器的数量，$m$ 表示传输线的数量。

接下来 $n$ 行，每行一个整数，第 $i$ 行的整数为 $r(i)$，表示第 $i$ 台服务器的 $\texttt{rank}$。

接下来 $m$ 行，每行表示各条传输线的信息，包含三个整数 $a,b,t$ 。$a$ 和 $b$ 是传榆线所连接的两台服务器的编号，$t$ 是传输线的长度。

outputFormat: 一个整数，表示所有服务器存储的数据总量，即 $|B(v)|$ 之和。


title: 间谍网络

description:
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 $n$ 个间谍（$n$ 不超过 $3000$），每个间谍分别用 $1$ 到 $3000$ 的整数来标识。

请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

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

第二行是整数 $p$。表示愿意被收买的人数，$1\le p\le n$。

接下来的 $p$ 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过 $20000$。

紧跟着一行只有一个整数 $r$，$1\le r\le8000$。然后 $r$ 行，每行两个正整数，表示数对 $(A, B)$，$A$ 间谍掌握 $B$ 间谍的证据。

outputFormat: 如果可以控制所有间谍，第一行输出 `YES`，并在第二行输出所需要支付的贿金最小值。否则输出 `NO`，并在第二行输出不能控制的间谍中，编号最小的间谍编号。


title: [CEOI2002] Royal guards

description:
从前有一个王国，这个王国的城堡是 $m$ 行 $n$ 列的一个矩形，被分为 $m \times n$ 个方格。一些方格是墙，而另一些是空地。这个王国的国王在城堡里设了一些陷阱，每个陷阱占据一块空地。

一天，国王决定在城堡里布置守卫，他希望安排尽量多的守卫。

守卫们都是经过严格训练的，所以一旦他们发现同行或同列中有人的话，他们立即向那人射击。因此，国王希望能够合理地布置守卫，使他们互相之间不能看见，这样他们就不可能互相射击了。守卫们只能被布置在空地上，不能被布置在陷阱或墙上，且一块空地只能布置一个守卫。如果两个守卫在同一行或同一列，并且他们之间没有墙的话，他们就能互相看见。(守卫就像象棋里的车一样)

你的任务是写一个程序，根据给定的城堡，计算最多可布置多少个守卫，并设计出布置的方案。

inputFormat:
第一行有两个整数 $m$ 和 $n$，表示城堡的规模。

第 $2$ 到第 $(m + 1)$ 行，每行 $n$ 个整数，第 $(i +1)$ 行第 $j$ 列的数 $a_{i, j}$ 表示城堡第 $i$ 行第 $j$ 列的方格的信息，其中 $0$ 表示空地，$1$ 表示陷阱，$2$ 表示墙。

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

首先输出一行一个整数 $k$，表示最多可布置的守卫个数。

然后输出 $k$ 行，每行两个整数 $x, y$，表示在第 $x$ 行第 $j$ 列放一个守卫。

hint:
#### 样例输入输出 1 解释

如图（黑色方格为墙，白色方格为空地，圆圈为陷阱，G表示守卫）

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

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq m, n \leq 200$，$0 \leq a_{i, j} \leq 2$。


title: K-联赛

description:
K-联赛职业足球俱乐部的球迷们都是有组织的训练有素的啦啦队员，就像红魔啦啦队一样（2002 年韩日世界杯上韩国队的啦啦队）。

这个赛季，经过很多场比赛以后，球迷们希望知道他们支持的球队是否还有机会赢得最后的联赛冠军。换句话说，球队是否可以通过某种特定的比赛结果最终取得最高的积分（获胜场次最多），允许出现多支队并列第一的情况。

现在，有 $n$ 支球队，每支队伍已经胜负的场次分别是 $w_i$ 和 $d_i$。同时还有些比赛没有进行，第 $i$ 支球队和第 $j$ 支球队之间还剩 $a_{ij}$ 场比赛要进行。

你需要找出所有可能获得冠军的球队。

所有队参加的比赛数是相同的，并且为了简化问题，你可以认为不存在平局，即比赛结果只有胜或负两种。

inputFormat:
第一行一个正整数 $n$，表示球队数。

第二行 $2n$ 个正整数，分别表示 $w_1,d_1,w_2,d_2,\cdots,w_n,d_n$。

第三行 $n^2$ 个正整数，分别表示 $a_{11},a_{12},\cdots,a_{1n},a_{21},\cdots,a_{2n},\cdots,a_{n1},\cdots,a_{nn}$。

outputFormat: 仅一行，输出所有可能获得冠军的球队，按其编号升序输出，中间用空格分隔。


title: 公路修建

description:
某国有 $n$ 个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。

修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。

政府审批的规则如下：

1. 如果两个或以上城市申请修建同一条公路，则让它们共同修建；
2. 如果三个或以上的城市申请修建的公路成环。如下图，A 申请修建公路 AB，B 申请修建公路 BC，C 申请修建公路 CA。则政府将否决其中最短的一条公路的修建申请；
3. 其他情况的申请一律同意。

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

一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。

当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。

你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。

inputFormat:
第一行一个整数 $n$，表示城市的数量。（$n \leq 5000$）

以下 $n$ 行，每行两个整数 $x$ 和 $y$，表示一个城市的坐标。（$-10^6 \leq x,y \leq 10^6$）

outputFormat: 一个实数，四舍五入保留两位小数，表示公路总长。（保证有唯一解）


title: 速度限制

description:
在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。

你将获得一份现代化城市的道路交通信息。为了使问题简化，地图只包括路口和道路。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。两地 $A$ 和 $B$，最多只有一条道路从 $A$ 连接到 $B$。你可以假设加速能够在瞬间完成并且不会有交通堵塞等情况影响你。当然，你的车速不能超过当前的速度限制。

inputFormat:
第一行是 $3$ 个整数 $N$，$M$ 和 $D$（$2\leq N\leq 150$，$1\leq M\leq 22500$），表示道路的数目，用 $0 \sim N-1$ 标记。$M$ 是道路的总数，$D$ 表示你的目的地。

接下来的 $M$ 行，每行描述一条道路，每行有 $4$ 个整数 $A$（$0\leq A<N$），$B$（$0\leq B<N$），$V$ （$0\leq V\leq 500$）和 $L$（$1\leq L\leq 500$），这条路是从 $A$ 到 $B$ 的，速度限制是 $V$，长度为 $L$。如果 $V$ 是 $0$，表示这条路的限速未知。

如果 $V$ 不为 $0$，则经过该路的时间 $T=\frac{L}{V}$。否则 $T=\frac{L}{\text{Vold}}$，$\text{Vold}$ 是你到达该路口前的速度。开始时你位于 $0$ 点，并且速度为 $70$。

outputFormat:
输出文件仅一行整数，表示从 $0$ 到 $D$ 经过的城市。

输出的顺序必须按照你经过这些城市的顺序，以 $0$ 开始，以 $D$ 结束。仅有一条最快路线。


title: 排序二叉树

description:
一个边长为 $n$ 的正三角形可以被划分成 $n^2$ 个小的边长为 $1$ 的正三角形，称为单位三角形。边长为 $3$ 的正三角形被分成三层共 $9$ 个小的正三角形，我们把它们从顶到底，从左到右以 $1\sim 9$ 编号，见下图。

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

四个这样的边长为 $n$ 的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依顺时针次序（从顶向底视角）编号为 $A,B,C$，底面编号为 $D$。侧面的 $A,B,C$ 号三角形以三棱锥的顶点为顶，底面的 $D$ 号三角形以它与 $A,B$ 三角形的交点为顶。

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

其中 $\tt .$ 表示这个三角形面的 $1$ 号三角形位置，并依次编号下去。

上图为三棱锥展开后的平面图，每个面上标有圆点的是该面的顶，该图中侧面 $A,B,C$ 分别向纸内方向折叠即可还原成三棱锥。我们把这 $A,B,C,D$ 四个面各自划分成 $n^2$ 个单位三角形。

对于任意两个单位三角形，如有一条边相邻，则称它们为相邻的单位三角形。显然，每个单位三角形有三个相邻的单位三角形。现在，把 $1\sim 4n^2$ 里的所有整数分别随机填入四个面总共 $4n^2$ 个单位三角形中。

现在要求你编程求由单位三角形组成的最大二叉搜索树。所谓最大二叉搜索树，是指在所有由单位三角形组成的二叉搜索树中节点最多的一棵树。要求当 $i$ 作为二叉搜索树的一个节点时，$i$ 的儿子（如果有的话）和 $i$ 的父亲（如果有的话）必须与 $i$ 有邻边（三棱锥状态下的邻边，而非展开图的邻边）。

一棵二叉搜索树满足这个节点的左子树得每个值全部小于这个节点，这个节点的右子树的每个值全部大于这个节点。

inputFormat:
输入的第一行为一个整数 $n$，表示展开图中每个面的三角形边长，也就是这个面有 $n^2$ 个单位三角形。

接下来每行 $n^2$ 个整数，一共四行，第一行表示 $A$ 面的单位三角形中填入的数，第二行表示 $B$ 面，以此类推。

outputFormat: 输出仅一行一个整数，表示最大二叉搜索树的节点个数。

hint:
### 样例解释

以下以 $A$ 面为例。记 $f(A,x)$ 表示 $A$ 面的第 $x$ 个单位三角形，以此类推。

$f(A,9)$ 与 $f(D,1)$ 有邻边，$f(A,7)$ 与 $f(D,2)$ 有邻边，$f(A,5)$ 与 $f(D,5)$ 有邻边。

$f(A,1)$ 与 $f(B,1)$ 有邻边，$f(A,4)$ 与 $f(B,2)$ 有邻边，$f(A,9)$ 与 $f(B,5)$ 有邻边。

$f(A,1)$ 与 $f(C,1)$ 有邻边，$f(A,2)$ 与 $f(C,4)$ 有邻边，$f(A,5)$ 与 $f(C,9)$ 有邻边。

以数字 $1$ 为二叉搜索树的根，可以得到节点最多的二叉搜索树为：

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

### 数据范围

对于 $100\%$ 的数据，$1\leqslant n\leqslant 18$，保证四个面所有单位三角形上填入的数互不相同且都取自 $[1,4n^2]$。


title: 树的重量

description:
树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树，其叶节点表示一个物种，两个叶节点之间的距离表示两个物种的差异。现在，一个重要的问题是，根据物种之间的距离，重构相应的“进化树”。

令 $N=\{1,2,3,\cdots ,n\}$，用一个 $N$ 上的矩阵 $M$ 来定义树 $T$。其中，矩阵 $M$ 满足：对于任意的 $i$，$j$，$k$，有 $M[i,j]+M[j,k] \ge M[i,k]$。树 $T$ 满足：

1. 叶节点属于集合 $N$；
2. 边权均为非负整数；
3. $d_T(i,j)=M[i,j]$，其中 $d_T(i,j)$ 表示树上 $i$ 到 $j$ 的最短路径长度。

如下图，矩阵 $M$ 描述了一棵树。

$$M=\begin{bmatrix}
0 & 5 & 9 & 12 & 8 \\
5 & 0 & 8 & 11 & 7 \\
9 & 8 & 0 & 5 & 1 \\
12 & 11 & 5 & 0 & 4 \\
8 & 7 & 1 & 4 & 0 \\
\end{bmatrix}$$

树的重量是指树上所有边权之和。对于任意给出的合法矩阵 $M$，它所能表示树的重量是惟一确定的，不可能找到两棵不同重量的树，它们都符合矩阵 $M$。你的任务就是，根据给出的矩阵 $M$，计算 $M$ 所表示树的重量。下图是上面给出的矩阵 $M$ 所能表示的一棵树，这棵树的总重量为 $15$。

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

inputFormat:
第一行是一个整数 $n\ (2<n<30)$。

其后 $n-1$ 行，给出的是矩阵 $M$ 的一个上三角（不包含对角线），矩阵中所有元素是不超过 $100$ 的非负整数。输入数据保证合法。

outputFormat: 对于每组输入，输出一行，一个整数，表示树的重量。


title: 信号放大器

description:
树型网络是最节省材料的网络。所谓树型网络，是指一个无环的连通网络，网络中任意两个结点间有且仅有一条通信道路。

网络中有一个结点是服务器，负责将信号直接或间接地发送到各终端机。如图上方，server 结点发出一个信号给结点 $a$ 和 $c$，$a$ 再转发给 $b$。如此，整个网络都收到这个信号了。

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

但是，实际操作中，信号从一个结点发到另一个结点，会出现信号强度的衰减。衰减量一般由线路长度决定。

如图下方，边上所标的数字为边的衰减量。假设从 server 出发一个强度为 $4$ 个单位的信号，发到结点 $a$ 后强度衰减为 $4-3=1$ 个单位。结点 $a$ 再将其转发给结点 $b$。由于信号强度为 $1$，衰减量为 $2$，因此信号无法发送到 $b$。

一个解决这一问题的方法是，安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度（从服务器出发时的强度）。

上图中，若在结点 $a$ 处安装一个信号放大器，则强度为 $4$ 的信号发到 $a$ 处，即被放大至 $4$。这样，信号就可以被发送的网络中的任意一个节点了。为了简化问题，我们假定每个结点只处理一次信号，当它第二次收到某个信号时，就忽略此信号。

你的任务是根据给出的树型网络，计算出最少需要安装的信号放大器数量。

inputFormat:
第一行一个整数 $n$，表示网络中结点的数量。（$n \le 20000$）

第 $2 \sim n+1$ 行，每行描述一个节点的连接关系。其中第 $i+1$ 行，描述的是结点 $i$ 的连接关系：首先一个整数 $k$，表示与结点 $i$ 相连的结点的数量。此后 $2k$ 个数，每两个描述一个与结点 $i$ 相连的结点，分别表示结点的编号（编号在 $1 \sim n$ 之间）和该结点与结点 $i$ 之间的边的信号衰减量。结点 $1$ 表示服务器。

最后一行，一个整数，表示从服务器上出发信号的强度。

outputFormat:
一个整数，表示要使信号能够传遍整个网络，需要安装的最少的信号放大器数量。

如果不论如何安装信号放大器，都无法使信号传遍整个网络，则输出 `No solution.`。


title: “访问”美术馆

description:
经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer 知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要 $5$ 秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。假定他回到起点后还需要留至少 $1$ 秒逃跑。

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

inputFormat:
第一行是警察赶到的时间，以秒为单位。第 $2$ 行描述了艺术馆的结构，是一串非负整数，成对地出现：每一对的第一个数是走过一条走廊的时间，第 $2$ 个数是它末端的藏画数量；如果第 $2$ 个数是 $0$，那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出，请看样例。

一个展室最多有 $20$ 幅画。通过每个走廊的时间不超过 $20$ 秒。艺术馆最多有 $100$ 个展室。警察赶到的时间在 $6000$ 秒以内。

outputFormat: 输出最多能偷到的画的数量。


title: 重建道路

description:
一场可怕的地震后，人们用 $N$ 个牲口棚（编号 $1\sim N$）重建了农夫 John 的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是唯一的。因此，牧场运输系统可以被构建成一棵树。

John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有 $P$ 个牲口棚的子树和剩余的牲口棚分离，John 想知道这些道路的最小数目。

inputFormat:
第一行两个整数，$N$ 和 $P$。

第二行到第 $n$ 行，每行两个整数 $I$ 和 $J$，表示节点 $I$ 是节点 $J$ 的父节点。牧场运输系统可以被构建成一棵以 1 号节点为根的树

outputFormat: 单独一行，包含一旦被破坏将分离出恰含 $P$ 个节点的子树的道路的最小数目。

hint:
### 样例解释

如果道路 $1-4$ 和 $1-5$ 被破坏，含有节点（$1,2,3,6,7,8$）的子树将被分离出来。

### 限制与约定

$1\le N\le 150$，$1\le P\le N$，保证给出的是一棵树。


title: 有线电视网

description:
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

inputFormat:
输入文件的第一行包含两个用空格隔开的整数 $N$ 和 $M$，其中 $2 \le N \le 3000$，$1 \le M \le N-1$，$N$ 为整个有线电视网的结点总数，$M$ 为用户终端的数量。

第一个转播站即树的根结点编号为 $1$，其他的转播站编号为 $2$ 到 $N-M$，用户终端编号为 $N-M+1$ 到 $N$。

接下来的 $N-M$ 行每行表示—个转播站的数据，第 $i+1$ 行表示第 $i$ 个转播站的数据，其格式如下：

$K \ \ A_1 \ \ C_1 \ \ A_2 \ \ C_2 \ \ \ldots \ \ A_k \ \ C_k$

$K$ 表示该转播站下接 $K$ 个结点（转播站或用户），每个结点对应一对整数 $A$ 与 $C$ ，$A$ 表示结点编号，$C$ 表示从当前转播站传输信号到结点 $A$ 的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过 10。

[](https://paste.ubuntu.com/p/xN9NRmYvpY/)

outputFormat: 输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

hint:
**样例解释**

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

如图所示，共有五个结点。结点 ① 为根结点，即现场直播站，② 为一个中转站，③④⑤ 为用户端，共 $M$ 个，编号从 $N-M+1$ 到 $N$，他们为观看比赛分别准备的钱数为 $3$、$4$、$2$。

从结点 ① 可以传送信号到结点 ②，费用为 $2$；

也可以传送信号到结点 ⑤，费用为 $3$（第二行数据所示）；

从结点 ② 可以传输信号到结点 ③，费用为$2$；

也可传输信号到结点 ④，费用为 $3$（第三行数据所示）。

如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：$2+3+2+3=10$，大于用户愿意支付的总费用 $3+4+2=9$，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。

[](https://paste.ubuntu.com/p/H9BMGJvFHH/)


title: 魔术数字游戏

description:
填数字方格的游戏有很多种变化，如下图所示的 $4 \times 4$ 方格中，我们要选择从数字 $1$ 到 $16$ 来填满这十六个格子($A_{i,j}$ ，其中 $i=1 \cdots 4$ ，$j=1 \cdots 4$)。为了让游戏更有挑战性，我们要求下列六项中的每一项所指定的四个格子，其数字累加的和必须为 $34$ ：

| $A_{1,1}$ | $A_{1,2}$ | $A_{1,3}$ |  $A_{1,4}$|
| :----------- | :----------- | :----------- | :----------- |
| $A_{2,1}$ | $A_{2,2}$ | $A_{2,3}$ | $A_{2,4}$ |
| $A_{3,1}$ | $A_{3,2}$ | $A_{3,3}$ | $A_{3,4}$ |
| $A_{4,1}$ | $A_{4,2}$ | $A_{4,3}$ | $A_{4,4}$ |

- 四个角落上的数字，即 $A_{1,1}+A_{1,4}+A_{4,1}+A_{4,4}=34$ 。
- 每个角落上的 $2 \times 2$ 方格中的数字，例如左上角 $A_{1,1}+A_{1,2}+A_{2,1}+A_{2,2}=34$ 。
- 最中间的 $2 \times 2$ 方格中的数字，即 $A_{2,2}+A_{2,3}+A_{3,2}+A_{3,3}=34$ 。
- 每条水平线上四个格子中的数字，即 $A_{i,1}+A_{i,2}+A_{i,3}+A_{i,4}=34$，其中 $i=1 \cdots 4$ 。
- 每条垂直线上四个格子中的数字，即 $A_{1,j}+A_{2,j}+A_{3,j}+A_{4,j}=34$，其中 $j=1 \cdots 4$ 。
- 两条对角线上四个格子中的数字，例如左上角到右下角 $A_{1,1}+A_{2,2}+A_{3,3}+A_{4,4}=34$ 。
- 右上角到左下角：$A_{1,4}+A_{2,3}+A_{3,2}+A_{4,1}=34$ 。

特别的，我们会指定把数字 $1$ 先固定在某一格内。

inputFormat: 输入只有一行包含两个正数据 $i$ 和 $j$ ，表示第 $i$ 行和第 $j$ 列的格子放数字 $1$。剩下的十五个格子，请按照前述六项条件用数字 $2$ 到 $16$ 来填满。

outputFormat:
输出所有合法解，并且依序排好。相邻两组合法解之间用一个空行隔开。

对于每一组合法解，输出四行，每行四个数，相邻两数之间用一个空格隔开。

合法解排序的方式，是先从第一行的数字开始比较，每一行数字，由最左边的数字开始比，数字较小的解答必须先输出到文件中。

hint:
可以得到，对于样例，合理的填写方法有 $216$ 种，以上仅为其中的两种。

#### 数据规模与约定
对于全部的测试点，保证 $1 \leq i, j \leq 4$。


title: 魔板

description:
有这样一种魔板：它是一个长方形的面板，被划分成 $n$ 行 $m$ 列的 $n \times m$ 个方格。每个方格内有一个小灯泡，灯泡的状态有两种（亮或暗）。我们可以通过若干操作使魔板从一个状态改变为另一个状态。操作的方式有两种：

1. 任选一行，改变该行中所有灯泡的状态，即亮的变暗、暗的变亮；
2. 任选两列，交换其位置。

当然并不是任意的两种状态都可以通过若干操作来实现互相转化的。

你的任务就是根据给定两个魔板状态，判断两个状态能否互相转化。

inputFormat:
文件中包含多组数据。第一行一个整数 $k$，表示有 $k$ 组数据。

每组数据的第一行两个整数 $n$ 和 $m$（$0 < n,m \leq 100$）。

以下的 $n$ 行描述第一个魔板。每行有 $m$ 个数字（$0$ 或 $1$），中间用空格分隔。若第 $x$ 行的第 $y$个数字为 $0$，则表示魔板的第 $x$ 行 $y$ 列的灯泡为“亮”；否则为“暗”。

然后的 $n$ 行描述第二个魔板。数据格式同上。

任意两组数据间没有空行。

outputFormat:
共 $k$ 行，依次描述每一组数据的结果。

若两个魔板可以相互转化，则输出 $\texttt{YES}$，否则输出 $\texttt{NO}$。(注意：请使用大写字母)


title: 校门外的树（增强版）

description: 校门外马路上本来从编号 $0$ 到 $L$，每一编号的位置都有一棵树。有砍树者每次从编号 $A$ 到 $B$ 处连续砍掉每一棵树，就连树苗也不放过（记 `0 A B`，含 $A$ 和 $B$）；幸运的是还有植树者每次从编号 $C$ 到 $D$ 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 `1 C D`，含 $C$ 和 $D$）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？

inputFormat:
第一行，两个正整数 $L$ 和 $N$，表示校园外原来有 $L + 1$ 棵树，并有 $N$ 次砍树或种树的操作。

以下 $N$ 行，每行三个整数，表示砍树或植树的标记和范围。

outputFormat: 共两行。第一行校门外留下的树苗数目，第二行种上又被拔掉的树苗数目。


title: 拼字游戏

description:
有一个未知的 $4 \times 4$ 的拼盘 $M$，它的每个元素都是正整数。给出 $4$ 行元素的总和，$4$ 列元素的总和以及两条对角线元素总和。另外还给出了拼盘中任意 $4$ 个位置的元素值，它们的位置在输入文件中给定。

编写一个程序求出拼盘中另外 $12$ 个位置的正整数的值，要求这些元素的行之和，列之和以及对角线之和与输入文件中给定的值相一致。

inputFormat:
输入文件包含用空格隔开的 $22$ 个正整数。

前四个数字分别表示四行中每一行元素的总和，接下来的 $4$ 个数字分别表示 $4$ 列中每列元素的总和。接下来的数字表示主对角线元素的总和，即 $M(0, 0)+M(1,1)+M(2, 2)+M(3, 3)$。然后的数字（第 $10$ 个数字）表示逆对角线上元数之和，即 $M(0, 3)+M(1, 2)+M(2, 1)+M(3, 0)$ 。剩下的部分还包含 $12$ 个数字，被分成三个一组的形式 $i,j,k$。表示 $M(i,j)=k$。

你可以假设任何行对角线或列之和不会超过 $300$。另外还可假设对于给定的输入文件总是存在解决方案。

outputFormat: 输出文件应包含按 $4 \times 4$ 的形式输出的 $16$ 个数字，同一行的四个数字用一个空个隔开。注意：对于给定的输入文件，可能有一个以上可能的解决方案。任何一个方案都是可接受的。

hint:
- 对于 $10\%$ 的数据，任何行，列或对角线之和不会超过 $20$；
- 对于 $30\%$ 的数据，任何行，列或对角线之和不会超过 $80$；
- 对于 $60\%$ 的数据，任何行，列或对角线之和不会超过 $200$；
- 对于 $100\%$ 的数据，任何行，列或对角线之和不会超过 $300$。

感谢 @Jomoo 的贡献。


title: 单词游戏

description:
Io 和 Ao 在玩一个单词游戏。

他们轮流说出一个仅包含元音字母的单词，并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。

游戏可以从任何一个单词开始。

任何单词禁止说两遍，游戏中只能使用给定词典中含有的单词。

游戏的复杂度定义为游戏中所使用的单词长度总和。

编写程序，求出使用一本给定的词典来玩这个游戏所能达到的游戏最大可能复杂度。

inputFormat: 输入文件的第一行，表示一个自然数 $N(1 \le N \le 16)$，$N$ 表示一本字典中包含的单词数量以下的每一行包含字典中的一个单词，每一个单词是由字母 `A`、`E`、`I`、`O` 和 `U` 组成的一个字符串，每个单词的长度将小于等于 $100$，所有的单词是不一样的。

outputFormat: 输出文件仅有一行，表示该游戏的最大可能复杂度。


title: 字串距离

description:
设有字符串 $X$，我们称在 $X$ 的头尾及中间插入任意多个空格后构成的新字符串为 $X$ 的扩展串，如字符串 $X$ 为$\verb!abcbcd!$，则字符串 $\verb!abcb␣cd!$，$\verb!␣a␣bcbcd␣!$ 和 $\verb!abcb␣cd␣!$ 都是 $X$ 的扩展串，这里 $\verb!␣!$ 代表空格字符。

如果 $A_1$ 是字符串 $A$ 的扩展串，$B_1$ 是字符串 $B$ 的扩展串，$A_1$ 与 $B_1$ 具有相同的长度，那么我们定义字符串 $A_1$ 与 $B_1$ 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为 $0$。在字符串 $A$、$B$ 的所有扩展串中，必定存在两个等长的扩展串 $A_1$，$B_1$，使得 $A_1$ 与 $B_1$ 之间的距离达到最小，我们将这一距离定义为字符串 $A$，$B$ 的距离。

请你写一个程序，求出字符串 $A$，$B$ 的距离。

inputFormat: 输入文件第一行为字符串 $A$ ，第二行为字符串 $B$。$A$，$B$ 均由小写字母组成且长度均不超过 $2000$。第三行为一个整数 $K(1\leq K\leq 100)$，表示空格与其他字符的距离。

outputFormat: 输出文件仅一行包含一个整数，表示所求得字符串 $A,B$ 的距离。


title: 尼克的任务

description:
尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。

尼克的一个工作日为 $n$ 分钟，从第 $1$ 分钟开始到第 $n$ 分钟结束。当尼克到达单位后他就开始干活，公司一共有 $k$ 个任务需要完成。如果在同一时刻有多个任务需要完成，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去完成，假如某些任务开始时刻尼克正在工作，则这些任务也由尼克的同事完成。如果某任务于第 $p$ 分钟开始，持续时间为 $t$ 分钟，则该任务将在第 $(p+t-1)$ 分钟结束。

写一个程序计算尼克应该如何选取任务，才能获得最大的空暇时间。

inputFormat:
输入数据第一行含两个用空格隔开的整数 $n$ 和 $k$。

接下来共有 $k$ 行，每一行有两个用空格隔开的整数 $p$ 和 $t$，表示该任务从第 $p$ 分钟开始，持续时间为 $t$ 分钟。

outputFormat: 输出文件仅一行，包含一个整数，表示尼克可能获得的最大空暇时间。

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

- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^4,1 \leq k \leq 10^4,1 \leq p \leq n,1 \leq p+t-1 \leq n$。


title: 书的复制

background:
大多数人的错误原因：尽可能让前面的人少抄写，如果前几个人可以不写则不写，对应的人输出 `0 0` 。

不过，已经修改数据，保证每个人都有活可干。

description:
现在要把 $m$ 本有顺序的书分给 $k$ 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

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

第二行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 本书的页数。

outputFormat: 共 $k$ 行，每行两个整数，第 $i$ 行表示第 $i$ 个人抄写的书的起始编号和终止编号。 $k$ 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

hint: $1\le k \le m \le 500$。


title: 多米诺骨牌

description:
多米诺骨牌由上下 $2$ 个方块组成，每个方块中有 $1\sim6$ 个点。现有排成行的上方块中点数之和记为 $S_1$，下方块中点数之和记为 $S_2$，它们的差为 $\left|S_1-S_2\right|$。如图，$S1=6+1+1+1=9$，$S2=1+5+3+2=11$，$\left|S_1-S_2\right|=2$。每个多米诺骨牌可以旋转 $180°$，使得上下两个方块互换位置。请你计算最少旋转多少次才能使多米诺骨牌上下 $2$ 行点数之差达到最小。

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

对于图中的例子，只要将最后一个多米诺骨牌旋转 $180°$，即可使上下 $2$ 行点数之差为 $0$。

inputFormat: 输入文件的第一行是一个正整数 $n(1\leq n\leq 1000)$，表示多米诺骨牌数。接下来的 $n$ 行表示 $n$ 个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数 $a$ 和 $b$，且 $1\leq a,b\leq 6$。

outputFormat: 输出文件仅一行，包含一个整数。表示求得的最小旋转次数。


title: 平板涂色

description:
CE 数码公司开发了一种名为自动涂色机（APM）的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。

为了涂色，APM 需要使用一组刷子。每个刷子涂一种不同的颜色 $C_i$ 。APM 拿起一把有颜色 $C_i$ 的刷子，并给所有颜色为 $C_i$ 且符合下面限制的矩形涂色：

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

为了避免颜料渗漏使颜色混合，一个矩形只能在所有紧靠它上方的矩形涂色后，才能涂色。例如图中矩形 $F$ 必须在 $C$ 和 $D$ 涂色后才能涂色。注意，每一个矩形必须立刻涂满，不能只涂一部分。

写一个程序求一个使 APM 拿起刷子次数最少的涂色方案。注意，如果一把刷子被拿起超过一次，则每一次都必须记入总数中。

inputFormat:
第一行为矩形的个数 $N$。下面有 $N$ 行描述了 $N$ 个矩形。每个矩形有 $5$ 个整数描述，左上角的 $y$ 坐标和 $x$ 坐标，右下角的 $y$ 坐标和 $x$ 坐标，以及预定颜色。

平板的左上角坐标总是 $(0,0)$。

outputFormat: 一个整数，表示拿起刷子的最少次数。


title: 三角形牧场

description:
和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。她拥有 $n$ 块木板，每块的长度 $l_i$ 都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。

请帮助 Hei 小姐构造这样的牧场，并计算出这个最大牧场的面积。

inputFormat:
第 $1$ 行：一个整数 $n$；

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $l_i$ 表示第 $i$ 块木板的长度。

outputFormat: 仅一个整数：最大牧场面积乘以 $100$ 然后舍尾的结果。如果无法构建，输出 $-1$。

hint:
#### 样例输入输出 1 解释

$692=\text{舍尾后的}(100\times\text{三角形面积})$，此三角形为等边三角形，边长为 $4$。

#### 数据规模与约定

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


title: 队员分组

description:
有 $n$ 个人从 $1$ 至 $n$ 编号，相互之间有一些认识关系，你的任务是把这些人分成两组，使得：

- 每个人都被分到其中一组。
- 每个组都至少有一个人。
- 一组中的每个人都认识其他同组成员。

在满足上述条件的基础上，要求两组成员的人数之差（绝对值）尽可能小。请构造一种可行的方案。

请注意，$x$ 认识 $y$ 不一定说明 $y$ 认识 $x$；$x$ 认识 $y$ 且 $y$ 认识 $z$ 不一定说明 $x$ 认识 $z$。即认识关系是单向且不可传递的。

inputFormat:
输入的第一行是一个整数，代表总人数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行有若干个互不相同的整数，以 $0$ 结尾，第 $(i + 1)$ 行的第 $j$ 个整数 $a_{i, j}$（$0$ 除外）代表第 $i$ 个人认识 $a_{i, j}$。

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

如果无解，请输出一行一个字符串 `No solution`。

如果有解，请输出两行整数，分别代表两组的成员。每行的第一个整数是该组的人数，后面**以升序**若干个整数代表该组的成员编号，数字间用空格隔开。

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

对于全部的测试点，保证 $2 \leq n \leq 100$，$1 \leq a_{i, j} \leq n$。

#### 说明

由 @zhouyonglong 提供 SPJ。


title: 两数之和

description: 我们知道从 $n$ 个非负整数中任取两个相加共有 $\frac{n(n-1)}{2}$ 个和，现在已知这 $\frac{n(n-1)}{2}$ 个和值，要求 $n$ 个非负整数。

inputFormat: 输入文件有若干行，每行一组数据，包含 $\frac{n(n-1)}{2}+1$ 个空格隔开的非负整数，其中第一个数表示 $n$（$2<n<10$），其余 $\frac{n(n-1)}{2}$ 个数表示和值，每个数不超过 $100000$。文件末以 `EOF` 结尾。

outputFormat: 输出文件若干行，对应每一个输入，该行按从小到大的次序依次输出一组满足要求的 $n$ 个非负整数，相邻两个整数之间用一个空格隔开；若问题无解则输出 `Impossible`。


title: 盒子与球

description:
现有 $r$ 个互不相同的盒子和 $n$ 个互不相同的球，要将这 $n$ 个球放入 $r$ 个盒子中，且不允许有空盒子。请求出有多少种不同的放法。

两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。

inputFormat: 输入只有一行两个整数，分别代表 $n$ 和 $r$。

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


title: 取数游戏 II

description:
有一个取数的游戏。初始时，给出一个环，环上的每条边上都有一个非负整数。这些整数中至少有一个 $0$。然后，将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏，两人轮流取数，取数的规则如下：

1.  选择硬币左边或者右边的一条边，并且边上的数非 $0$；
1.  将这条边上的数减至任意一个非负整数（至少要有所减小）；
1.  将硬币移至边的另一端。

如果轮到一个玩家走，这时硬币左右两边的边上的数值都是 $0$，那么这个玩家就输了。

如下图，描述的是 Alice 和 Bob 两人的对弈过程（其中黑色节点表示硬币所在节点）。

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

各图的结果为：

- $\text{A}$：轮到 Alice 操作；
- $\text{B}$：轮到 Bob 操作；
- $\text{C}$：轮到 Alice 操作；
- $\text{D}$：轮到 Bob 操作。

$\text{D}$ 中，轮到 Bob 走时，硬币两边的边上都是 $0$，所以 Alice 获胜。

现在，你的任务就是根据给出的环、边上的数值以及起点（硬币所在位置），判断先走方是否有必胜的策略。

inputFormat:
第一行一个整数 $N$ $(N \leq 20)$，表示环上的节点数。

第二行 $N$ 个数，数值不超过 $30$，依次表示 $N$ 条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。

outputFormat: 仅一行。若存在必胜策略，则输出 ```YES```，否则输出 ```NO```。


title: 磁盘碎片整理

description:
出于最高安全性考虑，司令部采用了特殊的安全操作系统，该系统采用一个特殊的文件系统。在这个文件系统中所有磁盘空间都被分成了相同尺寸的 $N$ 块，用整数 $1$ 到 $N$ 标识。每个文件占用磁盘上任意区域的一块或多块存储区，未被文件占用的存储块被认为是可是用的。如果文件存储在磁盘上自然连续的存储块中，则能被以最快的速度读出。

因为磁盘是匀速转动的，所以存取上面不同的存储块需要的时间也不同。读取磁盘开头处的存储块比读取磁盘尾处的存储块快。根据以上现象，我们事先将文件按其存取频率的大小用整数 $1$ 到 $K$ 标识。按文件在磁盘上的最佳存储方法，$1$ 号文件将占用 $1,2,\cdots,S_1$ 的存储块，$2$ 号文件将占用 $S_1+1,S_1+2,\cdots, S_1+S_2$ 的存储块，以此类推（$S_i$ 是被第 $i$ 个文件占用的存储块的个数）。为了将文件以最佳形式存储在磁盘上，需要执行存储块移动操作。一个存储块移动操作包括从磁盘上读取一个被占用的存储块至内存并将它写入其他空的存储块，然后宣称前一个存储块被释放，后一个存储块被占用。

本程序的目的是通过执行最少次数的存储块移动操作，将文件按最佳方式存储到磁盘上，注意同一个文件的存储块在移动之后其相对次序不可改变。

inputFormat: 每个磁盘说明的第一行包含两个用空格隔开的整数 $N$ 和 $K(1 \le K \le N \le 10^5)$，接下来的 $K$ 行每行说明一个文件，对第 $i$ 个文件的说明是这样的：首先以整数 $S_i$ 开头，表示第 $i$ 个文件的存储块数量，$1 \le S_i \le N-K$，然后跟 $S_i$ 个整数，每个整数之间用空格隔开，表示该文件按自然顺序在磁盘上占用的存储块的标识。所有这些数都介于 $1$ 和 $N$ 之间，包括 $1$ 和 $N$。一个磁盘说明中所有存储块的标识都是不同的，并且该盘至少有一个空的存储块。

outputFormat: 对于每一个磁盘说明，只需输出一行句子 $\text{``\texttt{We need \textrm{\textit{M}} move operations.}''}$，$M$ 表示将文件按最佳方式存储到磁盘上所需进行的最少存储块移动操作次数。如果文件已按最佳方式存储，仅需输出 $\text{``\texttt{No optimization needed.}''}$。


title: 欧几里德的游戏

description:
欧几里德的两个后代 Stan 和 Ollie 正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数 $M$ 和 $N$，从 Stan 开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于 $0$。然后是 Ollie，对刚才得到的数，和 $M,N$ 中较小的那个数，再进行同样的操作……直到一个人得到了 $0$，他就取得了胜利。下面是他们用 $(25,7)$ 两个数游戏的过程：

- 初始：$(25,7)$；
- Stan：$(11,7)$；
- Ollie：$(4,7)$；
- Stan：$(4,3)$；
- Ollie：$(1,3)$；
- Stan：$(1,0)$。

Stan 赢得了游戏的胜利。

现在，假设他们完美地操作，谁会取得胜利呢？

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

第一行为测试数据的组数 $C$。
下面 $C$ 行，每行为一组数据，包含两个正整数 $M,N(M,N<2^{31})$。

outputFormat: 对每组输入数据输出一行，如果 Stan 胜利，则输出 `Stan wins`；否则输出 `Ollie wins`。

hint: $1 \leq C \leq 6$。


title: [SHOI2002] 百事世界杯之旅

background: “……在 2002 年 6 月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更可赴日韩观看世界杯。还不赶快行动！”

description: 你关上电视，心想：假设有 $n$ 个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？

inputFormat: 输入只有一行一个整数，表示不同球星名字的个数 $n$。

outputFormat:
输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为：

```plain
 3
5--
 20
```

第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。减号的个数应等于分母的位数。分子和分母的首位都与第一个减号对齐。

分数必须是不可约的。

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

对于全部的测试点，保证 $2 \leq n \leq 33$。


title: 倒酒

description:
Winy是一家酒吧的老板，他的酒吧提供两种体积的啤酒，$a$ ml 和 $b$ ml，分别使用容积为 $a$ ml 和 $b$ ml 的酒杯来装载。

酒吧的生意并不好。Winy 发现酒鬼们都非常穷。有时，他们会因为负担不起 $a$ ml 或者 $b$ ml 啤酒的消费，而不得不离去。因此，Winy 决定出售第三种体积的啤酒（较小体积的啤酒）。

Winy 只有两种杯子，容积分别为 $a$ ml 和 $b$ ml，而且啤酒杯是没有刻度的。他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。

为了简化倒酒的步骤，Winy 规定：

1.  $a≥b$；
2.  酒桶容积无限大，酒桶中酒的体积也是无限大（但远小于桶的容积）；
3. 只包含三种可能的倒酒操作：
   1. 将酒桶中的酒倒入容积为 $b$ ml 的酒杯中；
   2. 将容积为 $a$ ml 的酒杯中的酒倒入酒桶；
   3. 将容积为 $b$ ml 的酒杯中的酒倒入容积为 $a$ ml 的酒杯中。
4. 每次倒酒必须把杯子倒满或把被倾倒的杯子倒空。

Winy希望通过若干次倾倒得到容积为 $a$ ml 酒杯中剩下的酒的体积尽可能小，他请求你帮助他设计倾倒的方案。

inputFormat: 输入共一行两个整数 $a$ 和 $b$，满足 $0<b≤a≤10^9$。

outputFormat:
第一行一个整数 $c$，表示可以得到的酒的最小体积。

第二行两个整数 $P_a$ 和 $P_b$（中间用一个空格分隔），分别表示从体积为 $a$ ml 的酒杯中倒出酒的次数和将酒倒入体积为 $b$ ml 的酒杯中的次数。

若有多种可能的 $P_a,P_b$ 满足要求，那么请输出 $P_a$ 最小的一个。若在 $P_a$ 最小的情况下，有多个 $P_b$ 满足要求，请输出 $P_b$ 最小的一个。

hint:
### 样例解释

倾倒的方案为：

1. 桶 $\to$ B 杯；
2. B 杯 $\to$ A 杯；
3. 桶 $\to$ B 杯；
4. B 杯 $\to$ A 杯；
5. A 杯 $\to$ 桶;
6. B 杯 $\to$ A 杯。


title: 班级聚会

description:
毕业25年以后，我们的主人公开始准备同学聚会。打了无数电话后他终于搞到了所有同学的地址。他们有些人仍在本城市，但大多数人分散在其他的城市。不过，他发现一个巧合，所有地址都恰好分散在一条铁路线上。他准备出发邀请但无法决定应该在哪个地方举行宴会。最后他决定选择一个地点，使大家旅行的花费和最小。

不幸的是，我们的主人公既不擅长数学，也不擅长计算机。他请你帮忙写一个程序，根据他同学的地址，选择聚会的最佳地点。花费相同时优先取靠近莫斯科的城市。

inputFormat:
输入数据的每一行描述一个城市的信息。对于每个城市，

首先是城市里同学的个数，紧跟着是这个城市到 Moscow（起点站）的距离（单位 $\rm km$），最后是城市的名称。最后一行描述的总是 Moscow，它在铁路线的一端，距离为 $0$。

outputFormat: 聚会地点城市名称和旅行费用（单程），两者之间用一空格隔开。每 $\rm km$ 花费一个卢布。

samples:
7 9289 Vladivostok
5 8523 Chabarovsk
3 5184 Irkutsk
8 2213 Yalutorovsk
10 0 Moscow

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

对于全部数据，保证城市数量 $ \le 150$，距离 $ \le 10000$，同学个数 $ \le 50$。


title: 高手去散步

background: 高手最近谈恋爱了。不过是单相思。“即使是单相思，也是完整的爱情”，高手从未放弃对它的追求。今天，这个阳光明媚的早晨，太阳从西边缓缓升起。于是它找到高手，希望在晨读开始之前和高手一起在鳌头山上一起散步。高手当然不会放弃这次梦寐以求的机会，他已经准备好了一切。

description: 鳌头山上有 $n$ 个观景点，观景点两两之间有游步道共 $m$ 条。高手的那个它，不喜欢太刺激的过程，因此那些没有路的观景点高手是不会选择去的。另外，她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长（观景时它不会理高手），已知高手的穿梭机可以让他们在任意一个观景点出发，也在任意一个观景点结束。

inputFormat: 第一行，两个用空格隔开的整数 $n$ 、 $m.$ 之后 $m$ 行，为每条游步道的信息：两端观景点编号、长度。

outputFormat: 一个整数，表示他们最长相伴的路程。

hint: 对于 $100\%$ 的数据：$n \le 20$，$m \le 50$，保证观景点两两之间不会有多条游步道连接。


title: [TJOI2011] 书架

background:
由于最近又购买了很多书，所以你打算在自己的书房做一个新书架，为了照顾整体效果，你希望你的书架的宽度越小越好。

书架背靠墙摆放，宽度就是指书架在垂直于墙面的方向上占据的距离。

description:
现按一定顺序给出所有要放置于书架上的书，共有 $n$ 本，第 $i$ 本书有一个长度 $h_i$。

书架有若干层，层与层之间的宽度不一定相等，但是一层的宽度不能小于其上所摆放的任何一本书的长度。同时，每层上的书的长度之和不能超过一个给定的参数 $m$，且任何层上的书必须是给出的书的序列中连续的几本。

书架的宽度是所有层的宽度之和，求书架的最小宽度。

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

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 本书的长度 $h_i$。

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

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

- 对于 $30\%$ 的数据，保证 $ n \leq 10^3$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq h_i \leq 10^9$，$\max\limits_{i = 1}^{n} h_i \leq m \leq 10^9$。

#### 提示

由于原题题意严重模糊不清，现给出简化版题意：

给出一个长度为 $n$ 的序列 $h$，请将 $h$ 分成若干段，满足每段数字之和都不超过 $m$，最小化每段的最大值之和。


title: 奶牛的耳语

description: 在你的养牛场，所有的奶牛都养在一排呈直线的牛栏中。一共有 $n$ 头奶牛，其中第 $i$ 头牛在直线上所处的位置可以用一个整数坐标 $p_i(0\le p_i \le 10^8)$ 来表示。在无聊的日子里，奶牛们常常在自己的牛栏里与其它奶牛交流一些八卦新闻。每头奶牛发出的声音响度是一样的，而由于声波的能量衰减，某头奶牛发出的声音只能被与它距离不超过 $d(0 \le d \le 10^4)$ 的奶牛所听到，这样这对奶牛就称为可以相互交流的。现在给出所有奶牛的位置和声音所能传播的最远距离 $d$ ，请你编个程序来计算你的养牛场里究竟有多少对可以相互交流的奶牛。

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

第二行包含 $n$ 个整数，每个整数都是一个坐标 $p_i$，描述一头奶牛在直线上的位置。

outputFormat: 一个数，表示养牛场中可以相互交流奶牛的对数。

hint:
数据规模

对于 $40\%$ 的数据，$1 \leq n \leq 10^3$。

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


title: [国家集训队] 单选错位

description:
gx 和 lc 去参加 noip 初赛，其中有一种题型叫单项选择题，顾名思义，只有一个选项是正确答案。

试卷上共有 $n$ 道单选题，第 $i$ 道单选题有 $a_i$ 个选项，这 $a_i$ 个选项编号是 $1,2,3,\ldots,a_i$，每个选项成为正确答案的概率都是相等的。

lc 采取的策略是每道题目随机写上 $1 \sim a_i$ 的某个数作为答案选项，他用不了多少时间就能期望做对 $\sum_{i=1}^n \frac{1}{a_i}$ 道题目。gx 则是认认真真地做完了这 $n$ 道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了：第 $i$ 道题目的答案抄到了答题纸上的第 $i+1$ 道题目的位置上，特别地，第 $n$ 道题目的答案抄到了第 $1$ 道题目的位置上。

现在 gx 已经走出考场没法改了，不过他还是想知道自己期望能做对几道题目，这样他就知道会不会被 lc 鄙视了。

我们假设 gx 没有做错任何题目，只是答案抄错位置了。

inputFormat:
$n$ 很大，为了避免读入耗时太多，输入文件只有 $5$ 个整数参数 $n, A, B, C, a_1$，由上交的程序产生数列 $a$。下面给出 pascal/C/C++ 的读入语句和产生序列的语句（默认从标准输入读入）：

```cpp
// for pascal
readln(n,A,B,C,q[1]);
for i:=2 to n do
q[i] := (int64(q[i-1]) * A + B) mod 100000001;
for i:=1 to n do
q[i] := q[i] mod C + 1;

// for C/C++
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
	a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
	a[i] = a[i] % C + 1;
```

选手可以通过以上的程序语句得到 $n$ 和数列 $a$（$a$ 的元素类型是 $32$ 位整数），$n$ 和 $a$ 的含义见题目描述。

outputFormat: 输出一个实数，表示 gx 期望做对的题目个数，保留三位小数。


title: 最接近的分数

description: 给出一个正小数，找出分子（分子 $ \ge 0$）不超过 $M$，分母不超过 $N$ 的最简分数或整数，使其最接近给出的小数。“最接近”是指在数轴上该分数距离给出的小数最近，如果这个分数不唯一，输出 ``TOO MANY``。

inputFormat: 输入共有 $2$ 行，第一行包含两个用空格隔开的正整数 $M$ 和 $N$，表示要求的分数其分子不超过 $M$，分母不超过 $N$；第二行为小数 $R(R>0)$，$R$ 的整数部分为一个阿拉伯数字，小数部分最多有十位。

outputFormat: 输出仅 $1$ 行，若解唯一则输出 `分子/分母`（整数 $K$ 写成 $\dfrac{K}{1}$），否则输出 ``TOO MANY``。

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

对于全部数据，保证 $1\le M,N\le 10^7$。


title: 切孔机

description:
司令部的助理经常需要在大纸上切割各种形状的孔。他们刚刚购买了一台新的切孔机，该机比他们以前使用的要方便自由的多。他们想编写一个程序来求出经过一系列复杂的切孔后会发生什么情况，他们特别想知道纸上形成的孔的数量。

下图列出了经过切割后形成的一些图样。

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

inputFormat: 输入文件第一行是一个整数 $N$，表示切纸操作的次数，$1≤N≤100$。接下来的 $N$ 行中每行给出一个精确的切割操作，每次切割都给出了用空格隔开的四个整数，$x_1,y_1,x_2,y_2,\ -1000≤x_1,y_1,x_2,y_2≤1000$。$x_1$ 和 $y_1$ 是切割线开始处的坐标值，$x_2$ 和 $y_2$ 是切割线结束时的坐标值。你可以假设所有的切割点都在纸上，不会出界。每次切割都平行于纸上的 $x$ 和 $y$ 坐标轴。

outputFormat: 对于每次切割操作，要求输出纸上留下的单独的孔数。注意任何孔的最小面积不低于 $1$ 平方单位。


title: 城市街道交通费系统

description:
城市街道交费系统最近创立了。一辆汽车左转一次需付费 $1$ ，右转一次需付费 $5$ 。只有当前进、左转、右转都无路可走的时候，调头才是允许的，调头每次付费 $10$ 。

给出一张城市地图，要求你求出从起始点到达终止点的花费最少的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。

inputFormat:
输入格式如下：

1. 第一行有两个整数，地图高度 $h$ 和宽度 $w$。
2. 其后 $h$ 行，每行 $w$ 个字符，将是以下字符中的一个：

- `.` 表示障碍区。
- `#` 表示道路。
- `E` 表示起始点且汽车面朝东。
- `W` 表示起始点且汽车面朝西。
- `N` 表示起始点且汽车面朝北。
- `S` 表示起始点且汽车面朝南。
- `F` 表示终点。

outputFormat: 仅包含一个整数，即为最便宜路径的费用。

hint:
样例一解释：

直走，然后左转 $3$ 次，最后右转到终止点 `F`。如果先直走然后右转 $2$ 次，花费将是 $10$ 。

---

样例二解释：

最便宜的路径花费 $7$ ：立刻左转，直走，在第一个岔路口左转，随后右转。

---

对于 $100\%$ 的数据：$4 \leq h,w \leq 30$。

数据保证地图中只有一个起点，一个终点，他们之间存在着可通达的路径。同时保证地图最外层一圈都是障碍。


title: 魔鬼之城

description:
在一个被分割为 $N\times M$ 个正方形房间的矩形魔鬼之城中，一个探险者必须遵循下列规则才能跳跃行动。他必须从 $(1,1)$ 进入，从 $(N,M)$ 走出；在每一房间的墙壁上都写了一个魔法数字，是 $1\sim 13$ 之内的自然数；探险者可以想像出 $8$ 个方向中的任何一个（水平或垂直或对角线方向），随后他就可以作一次空间跳跃穿过这一方向上的连续的 $X$ 个房间，其中 $X$ 是他原来所在房间的魔法数字。但如果在这一方向上的房间数小于 $X$，则他不作任何跳跃，而必须想像另一个方向。同时，探险者不能作连续两次相同方向的跳跃。

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

例如在上图的 $5\ \times 4$ 的魔鬼之城中，如果探险者现在所在的位置是 $(3,3)$，那么通过依次空间跳跃他可以到达下列房间中的一个：$(1,1)$，$(3,1)$，$(1,3)$，$(5,1)$，或 $(5,3)$。另外，如果他要用两次跳跃从 $(5,4)$ 到达 $(3,2)$，则他不能首先跳到 $(4,3)$（因为这样他第二次跳跃的方向将和第一次相同，而这是不允许的）。所以他必须先跳跃到 $(2,1)$。
请你写一个程序，对给定的地图，算出探险者至少需要跳跃多少步才能离开魔鬼之城。

inputFormat:
第一行两个整数 $N,M\ (1\le N,M\le 100)$。

下来有 $M$ 行，每行为 $N$ 个自然数，表示对应房间中的魔法数字。

outputFormat: 出最小步数，如果探险者无法离开魔鬼之城，请输出 `NEVER`。


title: 可见矩形

description:
给定平面上 $n$ 个互不相交（指公共面积为零）的正方形，它们的顶点坐标均为整数。设坐标原点为 $O(0,0)$。对于任一正方形 $R$，如果可以找到 $R$ 的边上 $2$ 个不同的点 $A$ 和 $B$，使 $\triangle OAB$ 的内部与其他正方形无公共点，则称正方形 $R$ 是从 $O$ 点可见的正方形。

对于给定的 $n$ 个互不相交的正方形，计算从坐标原点 $O$ 可见的正方形个数。

inputFormat:
输入文件的第一行是正方形个数 $n$（$1\le n\le 1000$）。

接下来 $n$ 行中，每行有三个表示正方形的整数 $X,Y,L$。其中，$X$ 和 $Y$ 表示正方形的左下角顶点坐标，$L$ 表示边长，$1\le X,Y,L\le 10000$。

outputFormat: 输出文件仅有一行包含一个整数，表示从坐标原点 $O$ 可见的正方形个数。


title: A*B Problem

background: 高精度乘法模板题。

description: 给出两个非负整数，求它们的乘积。

inputFormat: 输入共两行，每行一个非负整数。

outputFormat: 输出一个非负整数表示乘积。


title: 哥德巴赫猜想

description: 输入一个偶数 $N$，验证 $4\sim N$ 所有偶数是否符合哥德巴赫猜想：任一大于 $2$ 的偶数都可写成两个质数之和。如果一个数不止一种分法，则输出第一个加数相比其他分法最小的方案。例如 $10$，$10=3+7=5+5$，则 $10=5+5$ 是错误答案。

inputFormat: 第一行输入一个正偶数 $N$

outputFormat:
输出 $\dfrac{N-2}{2}$ 行。对于第 $i$ 行：

首先先输出正偶数 $2i+2$，然后输出等号，再输出加和为 $2i+2$ 且第一个加数最小的两个质数，以加号隔开。

hint: 数据保证，$ 4 \leq N\leq10000$。


title: 新二叉树

description: 输入一串二叉树，输出其前序遍历。

inputFormat:
第一行为二叉树的节点数 $n$。($1 \leq n \leq 26$)

后面 $n$ 行，每一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。

空节点用 `*` 表示

outputFormat: 二叉树的前序遍历。


title: 斐波那契公约数

description:
对于 Fibonacci 数列：

$$ f_i = \begin{cases}
  [i = 1]               & i \leq 1 \\
  f_{i - 1} + f_{i - 2} & i \gt 1
\end{cases}$$

请求出 $f_n$ 与 $f_m$ 的最大公约数，即 $\gcd(f_n, f_m)$。

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

outputFormat: 输出一行一个整数，代表 $f_n$ 和 $f_m$ 的最大公约数。答案请对 $10^8$ 取模。

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

- 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^9$。


title: [NOIP2011 普及组] 数字反转

description: 给定一个整数 $N$，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例 2）。

inputFormat: 一个整数 $N$。

outputFormat: 一个整数，表示反转后的新数。


title: [NOIP2011 普及组] 统计单词数

description:
一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例 1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例 2）。

inputFormat:
共 $2$ 行。

第 $1$ 行为一个字符串，其中只含字母，表示给定单词；

第 $2$ 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

outputFormat:
一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 $0$ 开始）；如果单词在文章中没有出现，则直接输出一个整数 $-1$。

注意：空格占一个字母位

samples:
to
Did the Ottoman Empire lose its power at that time

hint:
数据范围

$1\leq $ 第一行单词长度 $\leq10$。

$1\leq $ 文章长度 $\leq10^6$。

noip2011 普及组第 2 题


title: [NOIP2011 普及组] 瑞士轮

background:
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。

本题中介绍的瑞士轮赛制，因最早使用于$1895$年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长。

description:
$2 \times N$ 名编号为 $1\sim 2N$ 的选手共进行R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关：第$1$ 名和第$2$ 名、第 $3$ 名和第 $4$名、……、第$2K - 1 $名和第$ 2K$名、……  、第$2N - 1 $名和第$2N$名，各进行一场比赛。每场比赛胜者得$1 $分，负者得 $0 $分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值，试计算在R 轮比赛过后，排名第$ Q$ 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

inputFormat:
第一行是三个正整数$N,R ,Q$,每两个数之间用一个空格隔开，表示有 $2 \times N $名选手、$R$ 轮比赛，以及我们关心的名次 $Q$。

第二行是$2 \times N$ 个非负整数$s_1, s_2, …, s_{2N}$，每两个数之间用一个空格隔开，其中$ s_i $表示编号为$i$ 的选手的初始分数。 第三行是$2 \times N$ 个正整数$w_1 , w_2 , …, w_{2N}$，每两个数之间用一个空格隔开，其中 $w_i$ 表示编号为$i$ 的选手的实力值。

outputFormat: 一个整数，即$R$ 轮比赛结束后，排名第$ Q$ 的选手的编号。


title: [NOIP2011 普及组] 表达式的值

description:
对于1 位二进制变量定义两种运算：

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|} \hline
\kern{5em}\mathclap\textsf{运算符}\kern{5em} & \kern{5em}\mathclap\textsf{运算规则}\kern{5em} \\ \hline
\oplus &
\begin{aligned}
0 \oplus 0 &= 0 \\
0 \oplus 1 &= 1 \\
1 \oplus 0 &= 1 \\
1 \oplus 1 &= 1 \\
\end{aligned} \\ \hline
\times &
\begin{aligned}
0 \times 0 &= 0 \\
0 \times 1 &= 0 \\
1 \times 0 &= 0 \\
1 \times 1 &= 1 \\
\end{aligned} \\ \hline
\end{array}
$$

运算的优先级是：

1. 先计算括号内的，再计算括号外的。

2. “× ”运算优先于“⊕”运算，即计算表达式时，先计算× 运算，再计算⊕运算。例如：计算表达式A⊕B × C时，先计算 B × C，其结果再与 A 做⊕运算。

现给定一个未完成的表达式，例如\_+(\_\*\_)，请你在横线处填入数字$0 $或者$1$ ，请问有多少种填法可以使得表达式的值为$0 $。

inputFormat:
共 2 行。

第1 行为一个整数 $L$，表示给定的表达式中除去横线外的运算符和括号的个数。

第2 行为一个字符串包含 $L$ 个字符，其中只包含’（’、’）’、’+’、’\*’这$4$ 种字符，其中’（’、’）’是左右括号，’+’、’\*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。

outputFormat: 共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对$10007 $取模后的结果。

hint:
【输入输出样例说明】

  给定的表达式包括横线字符之后为：\_+(\_\*\_)

  在横线位置填入(0 、0 、0) 、(0 、1 、0) 、(0 、0 、1) 时，表达式的值均为0 ，所以共有3种填法。

【数据范围】

对于 $20\%$ 的数据有 $ 0 \le L \le 10$。

对于 $50\%$ 的数据有 $0 \le L \le 1,000$。

对于 $70\%$ 的数据有 $ 0 \le L \le 10,000$ 。

对于 $100\%$的数据有 $ 0 \le L \le 100,000$。

对于$50\%$ 的数据输入表达式中不含括号。


title: [NOIP2011 提高组] 选择客栈

description:
丽江河边有 $n$ 家很有特色的客栈，客栈按照其位置顺序从 $1$ 到 $n$ 编号。每家客栈都按照某一种色调进行装饰（总共 $k$ 种，用整数 $0 \sim k-1$ 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 $p$ 。

他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 $p$ 元的咖啡店小聚。

inputFormat:
共 $n+1$ 行。

第一行三个整数 $n, k, p$，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；

接下来的 $n$ 行，第 $i+1$ 行两个整数，之间用一个空格隔开，分别表示 $i $ 号客栈的装饰色调 $a_i$ 和 $i$ 号客栈的咖啡店的最低消费 $b_i$。

outputFormat: 一个整数，表示可选的住宿方案的总数。

hint:
### 样例解释

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

2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，但是若选择住 $4,5$号客栈的话，$4,5$ 号客栈之间的咖啡店的最低消费是 $4$ ，而两人能承受的最低消费是 $3$ 元，所以不满足要求。因此只有前 $3$ 种方案可选。

### 数据范围

- 对于 $30\% $ 的数据，有 $n \leq 100$ ；
- 对于 $50\% $ 的数据，有 $n \leq 1\,000$；
- 对于 $100\%$ 的数据，有 $2 \leq n \leq 2 \times 10^5$，$1 \leq k
 \leq 50$，$0 \leq p \leq 100$，$0 \leq b_i \leq 100$。


title: [NOIP2011 提高组] Mayan 游戏

description:
Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个$7$ 行 $\times5$ 列的棋盘，上面堆放着一些方块，方块不能悬空堆放，即方块必须放在最下面一行，或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块，消除方块的规则如下：

1. 每步移动可以且仅可以沿横向（即向左或向右）拖动某一方块一格：当拖动这一方块时，如果拖动后到达的位置（以下称目标位置）也有方块，那么这两个方块将交换位置（参见输入输出样例说明中的图 $6$ 到图 $7$）；如果目标位置上没有方块，那么被拖动的方块将从原来的竖列中抽出，并从目标位置上掉落（直到不悬空，参见下面图 $1$ 和图 $2$）；

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

2. 任一时刻，如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块，则它们将立即被消除（参见图1 到图3）。

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

注意：

a) 如果同时有多组方块满足消除条件，几组方块会同时被消除（例如下面图 $4$，三个颜色为 $1$ 的方块和三个颜色为 $2$ 的方块会同时被消除，最后剩下一个颜色为 $2$ 的方块）。

b) 当出现行和列都满足消除条件且行列共享某个方块时，行和列上满足消除条件的所有方块会被同时消除（例如下面图5 所示的情形，$5$ 个方块会同时被消除）。

3. 方块消除之后，消除位置之上的方块将掉落，掉落后可能会引起新的方块消除。注意：掉落的过程中将不会有方块的消除。

上面图 $1$ 到图 $3$ 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为 $(0,0)$，将位于 $(3,3)$ 的方块向左移动之后，游戏界面从图 $1$ 变成图 $2$ 所示的状态，此时在一竖列上有连续三块颜色为 $4$ 的方块，满足消除条件，消除连续 $3$ 块颜色为 $4$ 的方块后，上方的颜色为 $3$ 的方块掉落，形成图 $3$ 所示的局面。

inputFormat:
共 $6$ 行。

第一行为一个正整数 $n$，表示要求游戏通关的步数。

接下来的 $5$ 行，描述 $7 \times 5$ 的游戏界面。每行若干个整数，每两个整数之间用一个空格隔开，每行以一个 $0$ 结束，自下向上表示每竖列方块的颜色编号（颜色不多于 $10$ 种，从 $1$ 开始顺序编号，相同数字表示相同颜色）。

输入数据保证初始棋盘中没有可以消除的方块。

outputFormat:
如果有解决方案，输出 $n$ 行，每行包含 $3$ 个整数 $x,y,g$，表示一次移动，每两个整数之间用一个空格隔开，其中 $(x,y)$ 表示要移动的方块的坐标，$g$ 表示移动的方向，$1$ 表示向右移动，$-1$ 表示向左移动。注意：多组解时，按照 $x$ 为第一关键字，$y$ 为第二关键字，$1$ 优先于 $-1$，给出一组字典序最小的解。游戏界面左下角的坐标为 $(0,0)$。

如果没有解决方案，输出一行 `-1`。

hint:
**【输入输出样例说明】**

按箭头方向的顺序分别为图 $6$ 到图 $11$

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

样例输入的游戏局面如上面第一个图片所示，依次移动的三步是：$(2,1)$ 处的方格向右移动，$(3,1)$ 处的方格向右移动，$(3,0)$ 处的方格向右移动，最后可以将棋盘上所有方块消除。

**【数据范围】**

对于 $30\%$ 的数据，初始棋盘上的方块都在棋盘的最下面一行；

对于 $100\%$ 的数据，$0<n \le 5$。


title: [NOIP2011 提高组] 计算系数

description: 给定一个多项式 $(by+ax)^k$，请求出多项式展开后 $x^n\times y^m$ 项的系数。

inputFormat: 输入共一行，包含 $5$ 个整数，分别为 $a,b,k,n,m$，每两个整数之间用一个空格隔开。

outputFormat:
输出共一行，包含一个整数，表示所求的系数。

这个系数可能很大，输出对 $10007$ 取模后的结果。

hint:
【数据范围】

对于 $30\%$ 的数据，有 $ 0\le k\le 10$。

对于 $50\%$ 的数据，有 $ a=1$，$b=1$。

对于 $100\%$ 的数据，有 $0\le k\le 1000$，$0\le n,m\le k$，$n+m=k$，$0\le a,b\le 10^6$。

noip2011 提高组 day2 第 1 题。


title: [NOIP2011 提高组] 聪明的质监员

description:
`小T` 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 $n$ 个矿石，从 $1$ 到 $n$ 逐一编号，每个矿石都有自己的重量 $w_i$ 以及价值 $v_i$ 。检验矿产的流程是：

1. 给定$ m$ 个区间 $[l_i,r_i]$；
2. 选出一个参数 $W$；
3. 对于一个区间 $[l_i,r_i]$，计算矿石在这个区间上的检验值 $y_i$：

$$y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j$$

其中 $j$ 为矿石编号。

这批矿产的检验结果 $y$ 为各个区间的检验值之和。即：$\sum\limits_{i=1}^m y_i$

若这批矿产的检验结果与所给标准值 $s$ 相差太多，就需要再去检验另一批矿产。`小T` 不想费时间去检验另一批矿产，所以他想通过调整参数 $W$ 的值，让检验结果尽可能的靠近标准值 $s$，即使得 $|s-y|$ 最小。请你帮忙求出这个最小值。

inputFormat:
第一行包含三个整数 $n,m,s$，分别表示矿石的个数、区间的个数和标准值。

接下来的 $n$ 行，每行两个整数，中间用空格隔开，第 $i+1$ 行表示 $i$ 号矿石的重量 $w_i$ 和价值 $v_i$。

接下来的 $m$ 行，表示区间，每行两个整数，中间用空格隔开，第 $i+n+1$ 行表示区间 $[l_i,r_i]$ 的两个端点 $l_i$ 和 $r_i$。注意：不同区间可能重合或相互重叠。

outputFormat: 一个整数，表示所求的最小值。

hint:
【输入输出样例说明】

当 $W$ 选 $4$ 的时候，三个区间上检验值分别为 $20,5 ,0$ ，这批矿产的检验结果为 $25$，此时与标准值 $S$ 相差最小为 $10$。

【数据范围】

对于 $10\% $ 的数据，有 $1 ≤n ,m≤10$；

对于 $30\% $的数据，有 $1 ≤n ,m≤500$ ；

对于 $50\% $ 的数据，有 $ 1 ≤n ,m≤5,000$；

对于 $70\%$ 的数据，有 $1 ≤n ,m≤10,000$ ；

对于 $100\%$ 的数据，有 $ 1 ≤n ,m≤200,000$，$0 < w_i,v_i≤10^6$，$0 < s≤10^{12}$，$1 ≤l_i ≤r_i ≤n$ 。


title: [NOIP2011 提高组] 观光公交

background: 感谢 @Transhumanist 提供的一组 Hack 数据

description:
风景迷人的小城 Y 市，拥有 $n$ 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 $0$ 分钟出现在 $1$ 号景点，随后依次前往 $2,3,4,\cdots,n$ 号景点。从第 $i$ 号景点开到第 $i+1$ 号景点需要 $D_i$ 分钟。任意时刻，公交车只能往前开，或在景点处等待。

设共有 $m$ 个游客，每位游客需要乘车 $1$ 次从一个景点到达另一个景点，第 $i$ 位游客在 $T_i$ 分钟来到景点 $A_i$，希望乘车前往景点 $B_i$（$A_i<B_i$）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。

假设乘客上下车不需要时间。一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 $k$ 个氮气加速器，每使用一个加速器，可以使其中一个 $D_i-1$。对于同一个 $D_i$ 可以重复使用加速器，但是必须保证使用后 $D_i\ge0$。

那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

inputFormat:
第 $1$ 行是 $3$ 个整数 $n,m,k$，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 $2$ 行是 $n-1$ 个整数，每两个整数之间用一个空格隔开，第 $i$ 个数表示从第 $i$ 个景点开往第 $i+1$ 个景点所需要的时间，即 $D_i$。

第 $3$ 行至 $m+2$ 行每行 $3$ 个整数 $T_i,A_i,B_i$，每两个整数之间用一个空格隔开。第 $i+2$ 行表示第 $i$ 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

outputFormat: 一个整数，表示最小的总旅行时间。


title: 低洼地

description:
一组数，分别表示地平线的高度变化。高度值为整数，相邻高度用直线连接。找出并统计有多少个可能积水的低洼地？

如图：地高变化为 $[0,1,0,2,1,2,0,0,2,0]$。

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

inputFormat: 两行，第一行 $n,$ 表示有 $n$ 个数。第 $2$ 行连续 $n$ 个数表示地平线高度变化的数据，保证首尾为 $0$。$(3 \le n \le 10000,0 \le $ 高度 $ \le 1000)$。

outputFormat: 一个数，可能积水低洼地的数目。


title: 积水面积

description:
一组正整数，分别表示由正方体叠起的柱子的高度。若某高度值为 $x$，表示由 $x$ 个正立方的方块叠起（如下图，$0 \le x \le 5000$）。找出所有可能积水的地方（图中蓝色部分），统计它们可能积水的面积总和（计算的是图中的横截面积。一个立方体的位置，为一个单位面积）。

如图：柱子高度变化为 `0 1 0 2 1 2 0 0 2 0`。

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

图中蓝色部分为积水面积，共有 $6$ 个单位面积积水。

inputFormat: 两行，第一行 $n$，表示有 $n$ 个数（$3 \le n \le 10000$）。第 $2$ 行连续 $n$ 个数表示依次由正方体叠起的高度，保证首尾为 $0$。

outputFormat: 一个数，可能积水的面积。


title: 压缩技术

description:
设某汉字由 $N \times N$ 的 $\texttt 0$ 和 $\texttt 1$ 的点阵图案组成。

我们依照以下规则生成压缩码。连续一组数值：从汉字点阵图案的第一行第一个符号开始计算，按书写顺序从左到右，由上至下。第一个数表示连续有几个 $\texttt 0$，第二个数表示接下来连续有几个 $\texttt 1$，第三个数再接下来连续有几个 $\texttt 0$，第四个数接着连续几个 $\texttt 1$，以此类推……

例如: 以下汉字点阵图案：

```
0001000
0001000
0001111
0001000
0001000
0001000
1111111
```

对应的压缩码是： $\texttt {7 3 1 6 1 6 4 3 1 6 1 6 1 3 7}$ （第一个数是 $N$ ,其余各位表示交替表示0和1 的个数，压缩码保证 $N \times N=$ 交替的各位数之和）

inputFormat:
数据输入一行，由空格隔开的若干个整数，表示压缩码。

其中，压缩码的第一个数字就是 $N$，表示这个点阵应当是 $N\times N$ 的大小。

接下来的若干个数字，含义如题目描述所述。

outputFormat: 输出一个 $N\times N$ 的 01 矩阵，表示最后的汉字点阵图（点阵符号之间不留空格）。

hint:
## 样例解释

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

## 数据范围

数据保证，$3\leq N\leq 200$。


title: 压缩技术（续集版）

inputFormat: 汉字点阵图（点阵符号之间不留空格）。

outputFormat: 输出一行，压缩码。

hint: 数据保证，$3\leq N\leq 200$。


title: 单词覆盖还原

description:
我有一个长度为 $l$ 的字符串，最开始时，这个字符串由 $l$ 个句号（`.`）组成。

我在这个字符串中，将多次把 `boy` 或者 `girl` 两单词，依次贴到这个字符串中。

后贴上单词，会覆盖之前贴上的单词，或者覆盖句号。最终，每个单词至少有一个字符没有被覆盖。

请问，一共贴有几个 `boy` 几个 `girl`？

inputFormat: 一行被反复贴有 `boy` 和 `girl` 两单词的字符串。

outputFormat: 两行，两个整数。第一行为 `boy` 的个数，第二行为 `girl` 的个数。

hint: 数据保证，$3\le l\le255$，字符串仅仅包含如下字符：$\texttt{.bgilory}$。


title: logo语言

description:
Logo 语言命令可以指挥海龟在屏幕中爬行。本问题只使用 Logo 语言的三个语句：前进 `FD`，倒退 `BK` 和重复 `REPEAT`，因此，海龟只在一条直线上来回爬行。输入一行 logo 的命令行，输出海龟在屏幕中离开原来位子的距离（假设屏幕很大，可以让海龟移开 $10^9$ 的距离）。

例如：

- 输入 `FD 100` ，输出：$100$。

- 输入 `FD 100 BK 150`， 输出：$50$。

- 输入 `REPEAT 5[FD 100 BK 50]`， 输出：$250$。

- 输入 `REPEAT 5[FD 50 REPEAT 10[FD 100]]`， 输出：$5250$。

inputFormat: 一行，一个字符串，符合上述规定的 logo 命令行。

outputFormat: 一个数据，海龟离开原来位子的距离。

hint: 每个语句输入数据的绝对值不超过 $1000$。输出结果不会超过 $10^9$。


title: 删数问题

description:
一个集合有如下元素：$1$ 是集合元素；若 $P$ 是集合的元素，则 $2\times P+1$，$4\times P+5$ 也是集合的元素。

取出此集合中最小的 $k$ 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 $m$ 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。

注：不存在所有数被删除的情况。

inputFormat: 只有一行两个整数，分别代表 $k$ 和 $m$。

outputFormat: 输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。

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

- 对于 $30\%$ 的数据，保证 $1\le k,m\le300$。
- 对于 $100\%$ 的数据，保证 $1\le k,m\le3\times10^4$。


title: 矩形分割

description:
出于某些方面的需求，我们要把一块 $N \times M$ 的木板切成一个个 $1 \times 1$ 的小方块。

对于一块木板，我们只能从某条横线或者某条竖线（要在方格线上），而且这木板是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块木板，切割一次以后就被分割成两块，而且不能把这两块木板拼在一起然后一刀切成四块，只能两块分别再进行一次切割。

现在，给出从不同的线切割所要花的代价，求把整块木板分割成 $1 \times 1$ 块小方块所需要耗费的最小代价。

inputFormat:
输入文件第一行包括 $N$ 和 $M$，表示长 $N$ 宽 $M$ 的矩阵。

第二行包括 $N-1$ 个非负整数，分别表示沿着 $N-1$ 条横线切割的代价。

第三行包括 $M-1$ 个非负整数，分别表示沿着 $M-1$ 条竖线切割的代价。

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

hint:
数据范围：

对于 $60\%$ 的数据，有 $1 \le N,M \le 100$；

对于 $100\%$ 的数据，有 $1 \le N,M \le 2000$。


title: 雷达安装

description:
假设海岸线是一条无限延伸的直线。它的一侧是陆地，另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上（包括海岸线），并且每个雷达都有相同的扫描范围 $d$。你的任务是建立尽量少的雷达站，使所有小岛都在扫描范围之内。

数据使用笛卡尔坐标系，定义海岸线为 $x$ 轴。在 $x$ 轴上方为海洋，下方为陆地。

inputFormat:
第一行包括 $2$ 个整数 $n$ 和 $d$，$n$ 是岛屿数目，$d$ 是雷达扫描范围。

接下来 $n$ 行，每行两个整数，为岛屿坐标。

outputFormat: 一个整数表示最少需要的雷达数目，若不可能覆盖所有岛屿，输出 `-1`。

hint:
### 样例 1 解释

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

### 数据范围

对于全部数据，$n\le1000$，$ d \le 2\times 10^4$，$ | x_i | \le 2 \times 10^6 $，$ 0 \le y_i \le 2\times 10^4$。


title: 足球

description:
我们当中有很多热爱中国足球的同学，我们都知道中超（中国足球超级联赛）的规则：

一场比赛中，若获胜（即你的得分严格大于对手得分）则获得 $3$ 的积分，若打平（即你的得分等于对手得分）则获得 $1$ 分，若失败（即你的得分严格小于对手得分）获得 $0$ 积分。

这个问题很简单，假设 $N$ 轮比赛中你一共攻入 $S$ 个球，丢掉 $T$ 个球，那么你可能获得的最大得分和最小得分是多少？

inputFormat: 多组数据，每组数据一行三个整数 $S,T,N$（$10^9\ge S,T \ge 0$，$10^9\ge N \ge 1$）。每个测试点内数据组数不超过 $3\times 10^4$ 组。

outputFormat: 对于每组数据输出一行，两个整数表示最大得分和最小得分。


title: 数列排序

description: 给定一个数列 $a$，这个数列满足 $a_i \not  =a_j$（$i\not=j$），现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？

inputFormat:
第一行是一个整数，代表数字个数 $n$。

第二行有 $n$ 个整数用空格分隔开，表示数列 $a$。

outputFormat: 只有一行，包含一个数，表示最少的交换次数。


title: [NOIP2014 提高组] 生活大爆炸版石头剪刀布

background: NOIP2014 提高组 D1T1

description:
石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

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

现在，小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小 A 以 `石头-布-石头-剪刀-蜥蜴人-斯波克` 长度为 $6$ 的周期出拳,那么他的出拳序列就是 `石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-...`，而如果小 B 以 `剪刀-石头-布-斯波克-蜥蜴人` 长度为 $5$ 的周期出拳,那么他出拳的序列就是 `剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-...`。

已知小 A 和小 B 一共进行 $N$ 次猜拳。每一次赢的人得 $1$ 分，输的得 $0$ 分；平局两人都得 $0$ 分。现请你统计 $N$ 次猜拳结束之后两人的得分。

inputFormat:
第一行包含三个整数：$N,N_A,N_B$，分别表示共进行 $N$ 次猜拳、小 A 出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含 $N_A$ 个整数,表示小 A 出拳的规律,第三行包含 $N_B$ 个整数，表示小 B 出拳的规律。其中，$0$ 表示 `剪刀`，$1$ 表示 `石头`，$2$ 表示 `布`，$3$ 表示 `蜥蜴人`，$4$ 表示 `斯波克`。数与数之间以一个空格分隔。

outputFormat: 输出一行，包含两个整数，以一个空格分隔，分别表示小 A、小 B 的得分。


title: 数列

description:
有这样一种数列 $a_1, a_2, \cdots a_n$，其中 $a_{1}=0$，且对任意一项 $a_{i}$ 满足 $|a_{i}-a_{i+1}|=1$（$1\le i<n$）。设 $s=\sum_{i = 1}^n a_i = a_{1}+a_{2}+ \cdots +a_{n}$，表示前 $n$ 项之和。

现在给出数列长度 $n$ 与数列前 $n$ 项之和 $s$，要求：

输出满足条件的数列的总数对 $2^{64}$ 取模后的结果。

输出满足条件的 $100$ 个数列（如果不满 $100$ 个就全部输出）。

inputFormat: 输入只有一行两个整数，分别表示数列长度 $n$ 与数列之和 $s$。

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

在第一行输出一行一个整数 $t$，表示满足条件的数列总数对 $2^{64}$ 取模后的结果。

接下来若干行，每行 $n$ 个整数，表示一个数列。

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

对于全部的测试点，保证 $1 \leq n \leq 100$，$-2^{63} \leq s \lt 2^{63}$。

#### 说明

spj provider：@[xiaolilsq](user/230249)。


title: 封锁阳光大学

description:
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由 $n$ 个点构成的无向图，$n$ 个点之间由 $m$ 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

inputFormat:
第一行两个正整数，表示节点数和边数。
接下来 $m$ 行，每行两个整数 $u,v$，表示点 $u$ 到点 $v$ 之间有道路相连。

outputFormat: 仅一行如果河蟹无法封锁所有道路，则输出 `Impossible`，否则输出一个整数，表示最少需要多少只河蟹。

hint:
【数据规模】
对于 $100\%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，保证没有重边。


title: 海战

background:
在峰会期间，武装部队得处于高度戒备。警察将监视每一条大街，军队将保卫建筑物，领空将布满了 F-2003 飞机。

此外，巡洋船只和舰队将被派去保护海岸线。不幸的是，因为种种原因，国防海军部仅有很少的几位军官能指挥大型海战。因此，他们培养了一些新海军指挥官。军官们选择了“海战”游戏来帮助他们学习。

description:
在一个方形的盘上，放置了固定数量和形状的船只，每只船却不能碰到其它的船。在本题中，我们认为船是方形的，所有的船只都是由图形组成的方形。

求出该棋盘上放置的船只的总数。

inputFormat:
第一行为两个整数 $R$ 和 $C$，用空格隔开，分别表示游戏棋盘的行数和列数。

接下来 $R$ 行，每行 $C$ 个字符，为 `#` 或 `.`。`#` 表示船只的一部分，`.` 表示水。

outputFormat: 一行一个字符串，如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个 `#` 号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出 `There are S ships.`，$S$ 表示船只的数量。否则输出 `Bad placement.`。


title: 血色先锋队

background: 巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。

description: 军团是一个 $n$ 行 $m$ 列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。

inputFormat:
第 $1$ 行：四个整数 $n$，$m$，$a$，$b$，表示军团矩阵有 $n$ 行 $m$ 列。有 $a$ 个感染源，$b$ 为血色敢死队中领主的数量。

接下来 $a$ 行：每行有两个整数 $x$，$y$，表示感染源在第 $x$ 行第 $y$ 列。

接下来 $b$ 行：每行有两个整数 $x$，$y$，表示领主的位置在第 $x$ 行第 $y$ 列。

outputFormat: 第 $1$ 至 $b$ 行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为 $0$。

hint:
#### 输入输出样例 1 解释

如下图，标记出了所有人感染瘟疫的时间以及感染源和领主的位置。

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

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n,m\le500$，$1\le a,b\le10^5$。


title: 瑞瑞的木棍

description:
瑞瑞有一堆的玩具木棍，每根木棍的两端分别被染上了某种颜色，现在他突然有了一个想法，想要把这些木棍连在一起拼成一条线，并且使得木棍与木棍相接触的两端颜色都是相同的，给出每根木棍两端的颜色，请问是否存在满足要求的排列方式。

例如，如果只有 2 根木棍，第一根两端的颜色分别为 red, blue，第二根两端的颜色分别为 red, yellow，那么 blue---red | red----yellow 便是一种满足要求的排列方式。

inputFormat: 输入有若干行，每行包括两个单词，表示一根木棍两端的颜色，单词由小写字母组成，且单词长度不会超过 $10$ 个字母，最多有 $250000$ 根木棍。

outputFormat: 如果木棒能够按要求排列，输出 `Possible`，否则输出 `Impossible`

samples:
blue red
red violet
cyan blue
blue magenta
magenta cyan


title: 瑞瑞的木板

background: 瑞瑞想要亲自修复在他的一个小牧场周围的围栏。

description:
他测量栅栏并发现他需要 $n$ 根木板，每根的长度为整数 $l_i$。于是，他买了一根足够长的木板，长度为所需的 $n$ 根木板的长度的总和，他决定将这根木板切成所需的 $n$ 根木板（瑞瑞在切割木板时不会产生木屑，不需考虑切割时损耗的长度)。

瑞瑞切割木板时使用的是一种特殊的方式，这种方式在将一根长度为 $x$ 的木板切为两根时，需要消耗 $x$ 个单位的能量。瑞瑞拥有无尽的能量，但现在提倡节约能量，所以作为榜样，他决定尽可能节约能量。显然，总共需要切割 $(n-1)$ 次，问题是，每次应该怎么切呢？请编程计算最少需要消耗的能量总和。

inputFormat:
输入的第一行是整数，表示所需木板的数量 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $l_i$ 代表第  $i$ 根木板的长度 $l_i$。

outputFormat: 一个整数，表示最少需要消耗的能量总和。

hint:
#### 输入输出样例 1 解释

将长度为 $21$ 的木板，第一次切割为长度为 $8$ 和长度为 $13$ 的，消耗 $21$ 个单位的能量，第二次将长度为 $13$ 的木板切割为长度为 $5$ 和 $8$ 的，消耗 $13$ 个单位的能量，共消耗 $34$ 个单位的能量，是消耗能量最小的方案。

----

#### 数据规模与约定

- 对于 $100\%$ 的数据，保证 $1\le n \le 2 \times 10^4$，$1 \leq l_i \leq 5 \times 10^4$。


title: [NOI2013] 小 Q 的修炼

description:
小 Q 最近发现了一款新游戏，游戏的目标是从一个新手修炼成为武功高强的大侠。面对错综复杂的游戏世界，小 Q 要对他面临的每件事情做出谨慎的选择。例如，是否参加一个陌生人邀请的比武；同意或是拒绝用宝剑交换他人的武功秘籍......而小 Q 做出的每一个选择都有可能影响到他以后的发展：面对一个高手，若主动与之比武，很可能会损失惨重；但若不去比武，也许今后就再也见不到这个高手了。

对着这个游戏，小 Q 玩了很多次仍然玩不出他想要的结局，于是他费尽千辛万苦找到了游戏的剧本。令人惊讶的是,游戏的剧本并不像我们平时见到的剧本，反而很像代码。这个剧本是这样描述的：
- 量：有 $2$ 种量，常数和变量。
- 常数：一个整数。
- 变量：初始值为 $0$ 的可变整数，不同变量用不同正整数编号区分。
- 事件：整个剧本由若干个事件构成。所有的事件按照给定的顺序从 $1$ 开始依次编号。事件共有 $3$ 种：普通事件、选择跳转和条件跳转。
- 执行位置：一个整数，表示接下来将会执行的事件编号，如果不存在这个编号的事件则停止，即游戏到了一个结局。最初的时候执行位置为 $1$。
- 普通事件：一个变量增加或减少一个量的值。之后执行位置增加 $1$。
- 选择跳转：两个整数。执行到这里时玩家需要在这两个整数中选择一个，之后执行位置将被修改为这个整数。
- 条件跳转：两个量和两个整数。执行到这里时，若第一个量小于第二个量，则执行位置将被修改为第一个整数，否则将被修改为第二个整数。

小 Q 认为，整个游戏是希望一个叫做「成就值」的变量（编号为 $1$）最大。

inputFormat:
该题为提交答案型试题，所有输入数据 `train1.in`~`train10.in` 已在附加文件中。

输入的第一行包含两个正整数 $n, m$，表示事件的个数和变量的个数。

接下来有 $n$ 行，每行描述一个事件。这些事件按照给出的顺序依次编号为 $1$ 到 $n$。

描述量和事件的格式如下（格式中 `#`表示空格）

| 类型 | 格式 | 例子 |
|:-:|:-:|:-:|
| 常数 | `c#整数` | `c -2` |
| 变量 | `v#正整数` | `v 5` |
| 普通事件 | `变量#+#量` | `v 1 + c 1` |
| 普通事件 | `变量#-#量` | `v 2 - c 2` |
| 选择跳转 | `s#整数 1#整数 2` | `s 10 20` |
| 条件跳转 | `i#量 1#量 2#整数 1#整数 2` | `i c 99 v 2 0 1` |

outputFormat:
针对给定的 $10$ 个输入文件 `train1.in`~`train10.in`，你需要分别提交你的输出文件 `train1.out`~`train10.out`。

每个文件需要输出若干行，每行输出一个字符 `1` 或 `2`，表示执行过程中遇到的每个选择跳转所作的选择。输出的行数需要严格等于此次游戏执行过程中遇到的选择跳转的个数。

hint:
### 评分标准

对于每组数据，我们采用如下方式评分：
- 如果你的输出不合法,得 $0$ 分。
- 如果你的输出执行了超过 $10^6$ 行剧本,得 $0$ 分。
- 如果你的输出能让剧本正常结束，得 $1$ 分。
- 如果你的输出能让剧本正常结束，且结束时成就值为正数，得 $2$ 分。

我们设置了 $8$ 个评分参数 $a_3 , a_4 , \ldots , a_{10}$。

如果你的输出能让剧本正常结束，且结束时成就值不小于 $a_s$，得 $s$ 分。

如果以上条目有多项满足，则取满足条件中的最高得分。

### 如何测试你的输出

我们提供 `checker` 这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是，首先进入终端，在终端中运行下面的命令进入本题的文件夹：

`cd train`

然后运行：

`./checker <case_no>`

其中 `case_no` 是测试数据的编号。例如

`./checker 3`

将测试 `train3.out` 是否可以接受。

在你调用这个程序后，`checker` 将根据你给出的输出文件给出测试的结果，其中包括：
- 非法退出：未知错误。
- `Input/Output file does not exist.`：输入/输出文件不存在。
- `Output invalid.`：输出文件有误,此时可能包含具体错误信息。
- `Correct! Your answer is x.`：输出可接受,最后的成就值为 $x$。

### 更多功能
`checker` 还可以检查任意输入输出文件的测试结果，方法是在终端中运行：

`cd train`

`./checker <input_file_name> <output_file_name>`

其中 `input_file_name` 和 `output_file_name` 分别是输入输出文件的名称。例如

`./checker train3.in train3.out`

将测试 `train3.out` 是否可以接受。

使用 `-w` 可以输出每步运行的结果。用法是

`./checker -w <input_file_name> <output_file_name>`

或者

`./checker -w <case_no>`

例如

`./checker -w train3.in train3.out`

### 特别提示

如果选手使用自己生成输入文件进行调试，有可能因规模过大造成 checker 出错。若发生这类情况，请尝试较小规模的数据。


title: 最佳课题选择

description: Matrix67 要在下个月交给老师 $n$ 篇论文，论文的内容可以从 $m$ 个课题中选择。由于课题数有限，Matrix67 不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题 $i$，若 Matrix67 计划一共写 $x$ 篇论文，则完成该课题的论文总共需要花费 $A_i\times x^{B_i}$ 个单位时间。给定与每一个课题相对应的 $A_i$ 和 $B_i$ 的值，请帮助 Matrix67 计算出如何选择论文的课题使得他可以花费最少的时间完成这 $n$ 篇论文。

inputFormat:
第一行两个整数 $n$ 和 $m$，分别代表需要完成的论文数和可供选择的课题数。

接下来 $m$ 行每行两个整数。其中，第 $i$ 行的两个数分别代表与第 $i$ 个课题相对应的时间系数 $A_i$ 和指数 $B_i$。

outputFormat: 输出完成 $n$ 篇论文所需要耗费的最少时间。

hint:
### 样例说明

$4$ 篇论文选择课题一，$5$ 篇论文选择课题三，剩下一篇论文选择课题二，总耗时为 $2\times4^1+1\times1^2+2\times5^1=8+1+10=19$ 。可以证明，不存在更优的方案使耗时小于 $19$。

### 数据规模与约定

对于 $30\%$ 的数据，$n\le10,m\le5$。

对于 $100\%$ 的数据，$1\le n\le200$，$1\le m\le20$，$1\le A_i\le100$，$1\le B_i \le 5$。


title: [JSOI2004] 平衡点 / 吊打XXX

description:
如图，有 $n$ 个重物，每个重物系在一条足够长的绳子上。

每条绳子自上而下穿过桌面上的洞，然后系在一起。图中 $x$ 处就是公共的绳结。假设绳子是完全弹性的（即不会造成能量损失），桌子足够高（重物不会垂到地上），且忽略所有的摩擦，求绳结 $x$ 最终平衡于何处。

**注意**：桌面上的洞都比绳结 $x$ 小得多，所以即使某个重物特别重，绳结 $x$ 也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

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

inputFormat:
文件的第一行为一个正整数 $n$（$1\le n\le 1000$），表示重物和洞的数目。

接下来的 $n$ 行，每行是 $3$ 个整数 $x_i, y_i, w_i$，分别表示第 $i$ 个洞的坐标以及第 $i$ 个重物的重量。（$-10000\le x_i,y_i\le10000, 0<w_i\le1000$）

outputFormat: 你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结 $x$ 的横坐标和纵坐标。两个数以一个空格隔开。


title: 末日的传说

description:
只要是参加 jsoi 活动的同学一定都听说过 Hanoi 塔的传说：三根柱子上的金片每天被移动一次，当所有的金片都被移完之后，世界末日也就随之降临了。

在古老东方的幻想乡，人们都采用一种奇特的方式记录日期：他们用一些特殊的符号来表示从 $1$ 开始的连续整数，$1$ 表示最小而 $n$ 表示最大。创世纪的第一天，日历就被赋予了生命，它自动地开始计数，就像排列不断地增加。

我们用 $1-n$ 来表示日历的元素，第一天日历就是：
$$1,2,\ldots,n-2,n-1,n$$
第二天，日历自动变为
$$1,2,\ldots,n-2,n,n-1$$
······每次它都生成一个以前未出现过的“最小”的排列——把它转为 $n+1$ 进制后数的数值最小。

日子一天一天地过着。有一天，一位预言者出现了——他预言道，当这个日历到达某个上帝安排的时刻，这个世界就会崩溃······他还预言到，假如某一个日期的逆序达到一个值 $m$ 的时候，世界末日就要降临。

什么是逆序？日历中的两个不同符号，假如排在前面的那个比排在后面的那个更大，就是一个逆序，一个日期的逆序总数达到 $m$ 后，末日就要降临，人们都期待一个贤者，能够预见那一天到底将在什么时候到来？

inputFormat: 只包含一行两个正整数，分别为 $n$ 和 $m$。

outputFormat: 输出一行，为世界末日的日期，每个数字之间用一个空格隔开。

hint:
对于 $10\%$ 的数据有 $n\le10$；

对于 $40\%$ 的数据有 $n\le1000$；

对于 $100\%$ 的数据有 $n\le5\times10^4$。

所有数据均有解。


title: [USACO09OCT] Heat Wave G

description: 有一个 $n$ 个点 $m$ 条边的无向图，请求出从 $s$ 到 $t$ 的最短路长度。

inputFormat:
第一行四个正整数 $n,m,s,t$。
接下来 $m$ 行，每行三个正整数 $u,v,w$，表示一条连接 $u,v$，长为 $w$ 的边。

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


title: 兽径管理

description:
约翰农场的牛群希望能够在 $N$ 个草地之间任意移动。草地的编号由 $1$ 到 $N$。草地之间有树林隔开。牛群希望能够选择草地间的路径，使牛群能够从任一 片草地移动到任一片其它草地。 牛群可在路径上双向通行。

牛群并不能创造路径，但是他们会保有及利用已经发现的野兽所走出来的路径（以下简称兽径）。每星期他们会选择并管理一些或全部已知的兽径当作通路。

牛群每星期初会发现一条新的兽径。他们接着必须决定管理哪些兽径来组成该周牛群移动的通路，使得牛群得以从任一草地移动到任一草地。牛群只能使用当周有被管理的兽径做为通路。

牛群希望他们管理的兽径长度和为最小。牛群可以从所有他们知道的所有兽径中挑选出一些来管理。牛群可以挑选的兽径与它之前是否曾被管理无关。

兽径决不会是直线，因此连接两片草地之间的不同兽径长度可以不同。 此外虽然两条兽径或许会相交，但牛群非常的专注，除非交点是在草地内，否则不会在交点换到另外一条兽径上。

在每周开始的时候，牛群会描述他们新发现的兽径。如果可能的话，请找出可从任何一草地通达另一草地的一组需管理的兽径，使其兽径长度和最小。

inputFormat:
输入的第一行包含两个用空白分开的整数 $N$ 和 $W$。$W$ 代表你的程序需要处理的周数。

以下每处理一周，读入一行数据，代表该周新发现的兽径，由三个以空白分开的整数分别代表该兽径的两个端点（两片草地的编号) 与该兽径的长度。一条兽径的两个端点一定不同。

outputFormat: 每次读入新发现的兽径后，你的程序必须立刻输出一组兽径的长度和，此组兽径可从任何一草地通达另一草地，并使兽径长度和最小。如果不能找到一组可从任一草地通达另一草地的兽径，则输出 $-1$。

hint:
### 样例解释

对于每一周，

- 第一周时 $4$ 号草地不能与其他草地连通，输出 $-1$；
- 第二周时 $4$ 号草地不能与其他草地连通，输出 $-1$；
- 第三周时 $4$ 号草地不能与其他草地连通，输出 $-1$；
- 第四周时可以选择兽径 $(1,4,3),(1,3,8)$ 和 $(3,2,3)$；
- 第五周时可以选择兽径 $(1,4,3),(1,3,6)$ 和 $(3,2,3)$；
- 第六周时可以选择兽径 $(1,4,3),(2,1,2)$ 和 $(3,2,3)$。

### 数据范围及约定

对于全部数据，$1\le N\le 200$，$1 \le W \le 6000$，兽径的长度不超过 $10^4$ 且为正整数。


title: 无序字母对

description: 给定 $n$ 个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有 $(n+1)$ 个字母的字符串使得每个字母对都在这个字符串中出现。

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

第二行到第 $(n+1)$ 行每行两个字母，表示这两个字母需要相邻。

outputFormat:
输出满足要求的字符串。

如果没有满足要求的字符串，请输出 `No Solution`。

如果有多种方案，请输出字典序最小的方案（即满足前面的字母的 ASCII 编码尽可能小）。

hint: 不同的无序字母对个数有限，$n$ 的规模可以通过计算得到。


title: 请柬

background: 在电视时代，没有多少人观看戏剧表演。 Malidinesia 古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。

description:
他们已经打印了请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。

这里的公交系统是非常特殊的：共有 $n$ 个站点和 $m$ 个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。

学生每天早上从总部所在的 $1$ 号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候，所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

inputFormat:
输入的第一行是两个整数，代表站点个数 $n$ 和线路条数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数 $u, v, w$，代表存在一条从 $u$ 出发到达 $v$ 的线路，费用为 $w$。

outputFormat: 输出一行一个整数，表示最小费用。

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

对于 $100\%$ 的数据，保证：

- $1 \leq n, m \leq 10^6$。
- $1 \leq u, v \leq n$，$1 \leq w \leq 10^9$。
- 从 $1$ 出发可以到达所有的站点。


title: 地震逃生

description: 汶川地震发生时，四川\*\*中学正在上课，一看地震发生，老师们立刻带领 $x$ 名学生逃跑，整个学校可以抽象地看成一个有向图，图中有 $n$ 个点，$m$ 条边。$1$ 号点为教室，$n$ 号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生，只有第一批学生全部逃生完毕后，第二批学生才能从 $1$ 号点出发逃生，现在请你帮校长算算，每批最多能运出多少个学生，$x$ 名学生分几批才能运完。

inputFormat:
第一行三个整数 $n,m,x$；
以下 $m$ 行，每行三个整数 $a,b,c$（$1\leq a,b\leq n$，$0\leq c\leq x$）描述一条边，分别代表从 $a$ 点到 $b$ 点有一条边，且可容纳 $c$ 名学生。

outputFormat: 两个整数，分别表示每批最多能运出多少个学生，$x$ 名学生分几批才能运完。如果无法到达目的地（$n$ 号点）则输出 `Orz Ni Jinan Saint Cow!`。

hint:
**【注释】**

比如有图

```plain
1 2 100
2 3 1
```

$100$ 个学生先冲到 $2$ 号点，然后一个一个慢慢沿 $2 \to 3$ 边走过去。

18 神牛规定这样是不可以的……

也就是说，每批学生必须同时从起点出发，并且同时到达终点。

**【数据范围】**

对于 $100 \%$ 的数据，$0 \le x < 2^{31}$，$1 \le n \le 200$，$1 \le m \le 2000$。


title: [USACO4.4] 追查坏牛奶 Pollutant Control

description:
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。

很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。

送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。

你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

inputFormat:
第 $1$ 行两个整数 $N$、$M$，$N$ 表示仓库的数目，$M$ 表示运输卡车的数量。仓库 $1$ 代表发货工厂，仓库 $N$ 代表有三聚氰胺的牛奶要发往的零售商。

第 $2\sim M+1$ 行，每行 $3$ 个整数 $S_i$、$E_i$ 和 $C_i$。其中 $S_i$、$E_i$ 分别表示这辆卡车的出发仓库和目的仓库。$C_i$ 表示让这辆卡车停止运输的损失。

outputFormat: 两个整数 $C$ 和 $T$，$C$ 表示最小的损失，$T$ 表示在损失最小的前提下，最少要停止的卡车数。

hint:
对于 $100 \%$ 的数据，满足 $2 \le N \le 32$，$0 \le M \le 10^3$，$1 \le S_i \le N$，$1 \le E_i \le N$，$0 \le C_i \le 2 \times 10^6$。

题目翻译来自 NOCOW。

USACO Training Section 4.4


title: [USACO5.4] 奶牛的电信Telecowmunication

description:
农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用如下的方式发送电邮：如果存在一个由 $c$ 台电脑组成的序列$a_1,a_2,\cdots ,a_c$，且 $a_1$ 与 $a_2$ 相连，$a_2$ 与 $a_3$ 相连，等等。那么电脑 $a_1$ 和 $a_c$ 就可以互发电邮。

很不幸，有时候奶牛会不小心踩到电脑上，农夫约翰的车也可能碾过电脑，这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。

有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？请注意，$c_1,c_2$ 不能被破坏。请编写一个程序为她们计算这个最小值。

以如下网络为例：

```plain
   1*
  /
 3 - 2*
```

这张图画的是有 $2$ 条连接的 $3$ 台电脑。我们想要在电脑 $1$ 和 $2$ 之间传送信息。电脑 $1$ 与 $3$，$2$ 与 $3$ 直接连通。如果电脑 $3$ 坏了，电脑 $1$ 与 $2$ 便不能互发信息了。

inputFormat:
第一行：四个由空格分隔的整数：$N,M,c_1,c_2$。$N$ 是电脑总数，电脑由 $1$ 到 $N$ 编号。$M$ 是电脑之间连接的总数。后面的两个整数 $c_1$ 和 $c_2$ 是上述两头奶牛使用的电脑编号。连接没有重复且均为双向的（即如果 $c_1$ 与 $c_2$ 相连，那么 $c_2$ 与 $c_1$ 也相连）。两台电脑之间至多有一条连接。电脑 $c_1$ 和 $c_2$ 不会直接相连。

第 $2$ 到 $M+1$ 行：接下来的 $M$ 行中，每行包含两台直接相连的电脑的编号。

outputFormat: 一行，一个整数，表示使电脑 $c_1$ 和 $c_2$ 不能互相通信需要坏掉的电脑数目的最小值。


title: 电车

description:
在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。

为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口 $A$ 到路口 $B$ 最少需要下车切换几次开关。

inputFormat:
第一行有 $3$ 个整数 $N,A,B$（$2 \leq N \leq 100, 1 \leq A,B \leq N$），分别表示路口的数量，和电车的起点，终点。

接下来有 $N$ 行，每行的开头有一个数字 $K_i$（$0 \leq K_i \leq N-1$），表示这个路口与 $K_i$ 条轨道相连，接下来有 $K_i$ 个数字表示每条轨道所通向的路口，开关默认指向第一个数字表示的轨道。

outputFormat: 输出文件只有一个数字，表示从 $A$ 到 $B$ 所需的最少的切换开关次数，若无法从 $A$ 前往 $B$，输出 $-1$。


title: 排序

description: 一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 $A,B,C,D$ 表示 $A<B,B<C,C<D$。在这道题中，我们将给你一系列形如 $A<B$ 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

inputFormat:
第一行有两个正整数 $n,m$，$n$ 表示需要排序的元素数量，$2\leq n\leq 26$，第 $1$ 到 $n$ 个元素将用大写的 $A,B,C,D,\dots$ 表示。$m$ 表示将给出的形如 $A<B$ 的关系的数量。

接下来有 $m$ 行，每行有 $3$ 个字符，分别为一个大写字母，一个 `<` 符号，一个大写字母，表示两个元素之间的关系。

outputFormat:
若根据前 $x$ 个关系即可确定这 $n$ 个元素的顺序 `yyy..y`（如 `ABC`），输出

`Sorted sequence determined after xxx relations: yyy...y.`

若根据前 $x$ 个关系即发现存在矛盾（如 $A<B,B<C,C<A$），输出

`Inconsistency found after x relations.`

若根据这 $m$ 个关系无法确定这 $n$ 个元素的顺序，输出

`Sorted sequence cannot be determined.`

（提示：确定 $n$ 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

samples: Sorted sequence determined after 4 relations: ABCD.

hint: $2 \leq n \leq 26,1 \leq m \leq 600$。


title: Couple number

description:
对于一个整数 $n$，若存在两个自然数 $x, y$，满足 $n = x^2 - y^2$，则称 $n$ 是 Couple number。

给出 $a,b$，请求出 $[a, b]$ 范围内有多少个 Couple number。

inputFormat: 输入只有一行两个整数，分别表示 $a, b$。

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

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

对于全部的测试点，保证 $-10^7 \le a < b \le 10^7$ ，$b - a \le 10^7$。


title: 广义斐波那契数列

description:
广义的斐波那契数列是指形如 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 的数列。

今给定数列的两系数 $p$ 和 $q$，以及数列的最前两项 $a_1$ 和 $ a_2$，另给出两个整数 $n$ 和 $m$，试求数列的第 $n$ 项 $a_n$ 对 $m$ 取模后的结果。

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


title: 车的放置

description:
有下面这样的一个网格棋盘，$a,b,c,d$ 表示了对应边长度，也就是对应格子数：

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

当 $a=b=c=d=2$ 时，对应下面这样一个棋盘：

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

要在这个棋盘上放 $k$ 个相互不攻击的车，也就是这 $k$ 个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。

inputFormat: 只有一行，为五个非负整数，分别代表 $a,b,c,d$ 和 $k$。

outputFormat: 输出一行一个整数代表答案 $\bmod$ $10^5+3$ 后的结果。

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

- 存在部分数据，保证 $b=0$；
- 存在部分数据，保证 $a,b,c,d\leq 4$。
- 对于 $100\%$ 的数据，保证 $0\leq a,b,c,d,k\leq 10^3$，且至少有一种可行方案。


title: [NOIP2014 提高组] 联合权值

background: NOIP2014 提高组 D1T2

description:
无向连通图 $G$ 有 $n$ 个点，$n-1$ 条边。点从 $1$ 到 $n$ 依次编号,编号为 $i$ 的点的权值为 $W_i$，每条边的长度均为 $1$。图上两点 $(u, v)$ 的距离定义为 $u$ 点到 $v$ 点的最短距离。对于图 $G$ 上的点对 $(u, v)$，若它们的距离为 $2$，则它们之间会产生 $W_v \times W_u$ 的联合权值。

请问图 $G$ 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

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

接下来 $n-1$ 行,每行包含 $2$ 个用空格隔开的正整数 $u,v$，表示编号为 $u$ 和编号为 $v$ 的点之间有边相连。

最后 $1$ 行，包含 $n$ 个正整数，每两个正整数之间用一个空格隔开，其中第 $i$ 个整数表示图 $G$ 上编号为 $i$ 的点的权值为 $W_i$。

outputFormat: 输出共 $1$ 行，包含 $2$ 个整数，之间用一个空格隔开,依次为图 $G$ 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对 $10007$ 取余。

hint:
**样例解释**

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

本例输入的图如上所示，距离为 $2$ 的有序点对有$(1,3)$ 、$(2,4)$ 、$(3,1)$ 、$(3,5) $、$(4,2)$ 、$(5,3) $。

其联合权值分别为 $2,15,2,20,15,20$。其中最大的是 $20$，总和为 $74$。

**数据说明**

- 对于 $30\%$ 的数据，$1 < n \leq 100$；
- 对于 $60\%$ 的数据，$1 < n \leq 2000$；
- 对于 $100\%$ 的数据，$1 < n \leq 2\times 10^5$，$0 < W_i \leq 10000$。

保证一定存在可产生联合权值的有序点对。


title: 没有上司的舞会

description:
某大学有 $n$ 个职员，编号为 $1\ldots n$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

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

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$。

第 $(n + 2)$ 到第 $2n$ 行，每行输入一对整数 $l, k$，代表 $k$ 是 $l$ 的直接上司。

outputFormat: 输出一行一个整数代表最大的快乐指数。

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

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$，$-128 \leq r_i\leq 127$，$1 \leq l, k \leq n$，且给出的关系一定是一棵树。


title: [USACO08JAN] Running S

description:
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行 $n$ 分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。

贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第 $i$ 分钟内跑步，她可以在这一分钟内跑 $d_i$ 米，并且她的疲劳度会增加 $1$。不过，无论何时贝茜的疲劳度都不能超过 $m$。

如果贝茜选择休息，那么她的疲劳度就会每分钟减少 $1$，但她必须休息到疲劳度恢复到 $0$ 为止。在疲劳度为 $0$ 时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为 $0$ 。

还有，在 $n$ 分钟的锻炼结束时，贝茜的疲劳度也必须恢复到 $0$，否则她将没有足够的精力来对付这一整天中剩下的事情。

请你计算一下，贝茜最多能跑多少米。

inputFormat:
第一行两个正整数 $n,m$。
接下来 $n$ 行，每行一个正整数 $d_i$。

outputFormat: 输出一个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10^4$，$1\le d_i \le 1000$，$1\le m \le 500$。

【样例说明】

贝茜在第 $1$ 分钟内选择跑步（跑了 $5$ 米），在第 $2$ 分钟内休息，在第 $3$ 分钟内跑步（跑了 $4$ 米），剩余的时间都用来休息。
因为在晨跑结束时贝茜的疲劳度必须为0，所以她不能在第 $5$ 分钟内选择跑步。
最终跑的总距离为 $9$。


title: 房间最短路问题

description:
在一个长宽均为 $10$，入口、出口分别为 $(0,5)$、$(10,5)$ 的房间里，有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。

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

inputFormat:
第一排为 $n$（$n \le 20$），墙的数目。

接下来 $n$ 排，每排 $5$ 个实数 $x,a_1,b_1,a_2,b_2$。

$x$ 表示墙的横坐标（所有墙都是竖直的），$a_1 \sim b_1$ 和 $a_2 \sim b_2$ 之间为空缺。

$a_1,b_1,a_2,b_2$ 保持递增，$x_1 \sim x_n$ 也是递增的。

outputFormat: 输出最短距离，保留 $2$ 位小数。


title: 神秘大三角

description: 判断一个点与已知三角形的位置关系。

inputFormat:
前三行，每行一个坐标，表示该三角形的三个顶点。

第四行，一个点的坐标，试判断该点与前三个点围成三角形的位置关系。

所有坐标值均为整数。

outputFormat:
- 若点在三角形内（不含边界），输出 $1$；
- 若点在三角形外（不含边界），输出 $2$；
- 若点在三角形边界上（不含顶点），输出 $3$；
- 若点在三角形顶点上，输出 $4$。

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

对于 $100\%$ 数据，$0\le x_i,y_i\le 100$。


title: 数列的整除性

description: 对于任意一个整数数列，我们可以在每两个整数中间任意放一个符号 `+` 或 `-`，这样就可以构成一个表达式，也就可以计算出表达式的值。对于一个整数数列来说，我们能通过如上的方法构造出不同的表达式，从而得到不同的数值，如果其中某一个数值能够被 $k$ 整除的话，我们就称该数列能被 $k$ 整除。现在你的任务是判断某个数列是否能被某数整除。

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

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

对于每组数据：

第一行两个整数 $n$ 和 $k$，$n$ 表示数列中整数的个数。

第二行  $n$ 个整数，表示输入数列 $\{a_n\}$。

outputFormat: 输出应有 $M$ 行，依次对应输入文件中的 $M$ 个子任务，若数列能被 $k$ 整除则输出 `Divisible`，否则输出 `Not divisible` ，行首行末应没有空格。


title: 花园

description:
小 L 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 $1 \sim n$。花园 $1$ 和 $n$ 是相邻的。

他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则：任意相邻 $m$ 个花圃中都只有不超过 $k$ 个 C 形的花圃，其余花圃均为 P 形的花圃。

例如，若 $n=10$ , $m=5$ , $k=3$ ，则

- `CCPCPPPPCC` 是一种不符合规则的花圃。
- `CCPPPPCPCP` 是一种符合规则的花圃。

请帮小 L 求出符合规则的花园种数对 $10^9+7$ 取模的结果。

inputFormat: 只有一行三个整数，分别表示 $n, m, k$。

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

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

- 对于 $40\%$ 的数据，保证 $n \le 20$。
- 对于 $60\%$ 的数据，保证 $m=2$。
- 对于 $80\%$ 的数据，保证 $n \le 10^5$；
- 对于 $100\%$ 的数据，保证 $2 \leq n \le 10^{15}$，$2 \leq m \leq \min(n, 5)$，$1 \leq k \lt m$。


title: 扑克牌

description:
组合数学是数学的重要组成部分，是一门研究离散对象的科学，它主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。

随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。

今天我们来研究组合数学中的一个有趣的问题，也是一个简单的计数问题：

从一副含有 $n$ 张的扑克牌(每张扑克牌都不相同)中，分给 $m$ 个人，第 $i$ 个人得到 $a_i$ 张牌，求一共有几种分法，这个数可能非常大，请输出此数模 $10007$ 后的结果。

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

第二行 $m$ 个整数 $a_i$。

outputFormat: 此数模 $10007$ 后的结果。


title: 租用游艇

description: 长江游艇俱乐部在长江上设置了 $n$ 个游艇出租站 $1,2,\cdots,n$。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r(i,j)$（$1\le i\lt j\le n$）。试设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

inputFormat: 第一行中有一个正整数 $n$，表示有 $n$ 个游艇出租站。接下来的 $n-1$ 行是一个半矩阵 $r(i,j)$（$1\le i<j\le n$）。

outputFormat: 输出计算出的从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

hint: $n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。


title: [USACO07MAR] Gold Balanced Lineup G

description:
神仙 $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 在许多方面都有着很强的能力。具体的说，他总共有 $m$ 种能力，并将这些能力编号为 $1 \sim m$。

他的能力是一天一天地提升的，每天都会有一些能力得到一次提升，她对每天的能力提升都用一个数字表示，称之为能力提升数字，比如数字 $13$，转化为二进制为 $1101$，并且从右往左看，表示他的编号为 $1,3,4$ 的能力分别得到了一次提升。

$\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 把每天表示能力提升的数字的记了下来，如果在连续的一段时间内，她的每项能力都提升了相同的次数，她就会称这段时间为一个均衡时期，比如在连续 $5$ 天内，她的每种能力都提升了 $4$ 次，那么这就是一个长度为 $5$ 的均衡时期。

于是，问题来了，给出 $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ $n$ 天的能力提升数字，请求出均衡时期的最大长度。

inputFormat:
第一行有两个整数 $n,m$，表示有 $n$ 天，$m$ 种能力。

接下来有 $n$ 行，每行有一个整数，分别表示第 $1\sim n$ 天的能力提升数字。

能力提升数字转化为二进制后，从右到左的每一位表示对应的能力是否在当天得到了一次提升。

outputFormat: 输出只有一个整数，表示长度最大的均衡时期的长度。


title: 小M的作物

description:
小 M 在 MC 里开辟了两块巨大的耕地 $A$ 和 $B$（你可以认为容量是无穷），现在，小 P 有 $n$ 种作物的种子，每种作物的种子有 $1$ 个（就是可以种一棵作物），编号为 $1$ 到 $n$。

现在，第 $i$ 种作物种植在 $A$ 中种植可以获得 $a_i$ 的收益，在 $B$ 中种植可以获得 $b_i$ 的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小 M 找到了规则中共有 $m$ 种作物组合，第 $i$ 个组合中的作物共同种在 $A$ 中可以获得 $c_{1,i}$ 的额外收益，共同种在 $B$ 中可以获得 $c_{2,i}$ 的额外收益。

小 M 很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？

inputFormat:
第一行一个整数 $n$，表示作物种数。

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

第三行 $n$ 个整数，表示 $b_i$。

第四行一个整数 $m$，表示组合种数。

接下来 $m$ 行中，第 $i$ 行第一个整数 $k_i$，表示第 $i$ 个作物组合中的作物种数，接下来两个整数 $c_{1,i},c_{2,i}$，然后 $k_i$ 个整数，表示该组合中的作物编号。

outputFormat: 只有一行，包括一个整数，表示最大收益。

hint:
### 样例解释

 $A$ 耕地种作物 $1,2$，$B$ 耕地种作物 $3$，收益： $4+2+3+2=11$。

### 数据范围

对于 $100\%$ 的数据，$1 \le k < n \le 10^3$，$1 \le m \le 10^3$。题目当中出现的所有权值均为不大于 $1000$ 的非负整数。


title: 兔子数

description:
设 $S(N)$ 表示 $N$ 的各位数字之和，如 $S(484) = 4+8+4 = 16$， $S(22) = 2+2 = 4$。如果一个正整数满足 $S(x \cdot x) = S(x) \cdot S(x)$，我们称之为 Rabbit Number。比方说，$22$ 就是一个 Rabbit Number，因为 $S(484) = S(22) \cdot S(22)$。

现在，给出一个区间 $[L,R]$，求在该区间内的 Rabbit Number 的个数。

inputFormat: 输入仅一行，为空格隔开的两个数 $L$ 和 $R$。

outputFormat: 输出仅一行一个整数，表示所求 Rabbit Number 的个数。


title: 幻象迷宫

background:
（喵星人 LHX 和 WD 同心协力击退了汪星人的入侵，不幸的是，汪星人撤退之前给它们制造了一片幻象迷宫。）

WD：呜呜，肿么办啊……

LHX：momo...我们一定能走出去的！

WD：嗯，+U+U！

description:
幻象迷宫可以认为是无限大的，不过它由若干个 $N\times M$ 的矩阵重复组成。矩阵中有的地方是道路，用 $\verb!.!$ 表示；有的地方是墙，用 $\verb!#!$ 表示。LHX 和 WD 所在的位置用 $\verb!S!$ 表示。也就是对于迷宫中的一个点$(x,y)$，如果 $(x \bmod n,y \bmod m)$ 是 $\verb!.!$ 或者 $\verb!S!$，那么这个地方是道路；如果 $(x \bmod n,y \bmod m)$ 是$\verb!#!$，那么这个地方是墙。LHX 和 WD 可以向上下左右四个方向移动，当然不能移动到墙上。

请你告诉 LHX 和 WD，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，LHX 就只好启动城堡的毁灭程序了……当然不到万不得已，他不想这么做。

inputFormat:
输入包含多组数据，以 EOF 结尾。

每组数据的第一行是两个整数 $N,M$。

接下来是一个 $N\times M$ 的字符矩阵，表示迷宫里 $(0,0)$ 到 $(n-1,m-1)$ 这个矩阵单元。

outputFormat: 对于每组数据，输出一个字符串，`Yes` 或者 `No`。


title: 医院设置

description:
设有一棵二叉树，如图：

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

其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 $1$。如上图中，若医院建在 $1$ 处，则距离和 $=4+12+2\times20+2\times40=136$；若医院建在 $3$ 处，则距离和 $=4\times2+13+20+40=81$。

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

接下来的 $n$ 行每行描述了一个结点的状况，包含三个整数 $w, u, v$，其中 $w$ 为居民人口数，$u$ 为左链接（为 $0$ 表示无链接），$v$ 为右链接（为 $0$ 表示无链接）。

outputFormat: 一个整数，表示最小距离和。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$0 \leq u, v \leq n$，$1 \leq w \leq 10^5$。


title: WJMZBMR打osu! / Easy

background: 原 维护队列 参见 P1903

description:
某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(

我们来简化一下这个游戏的规则

有 $n$ 次点击要做，成功了就是 `o`，失败了就是 `x`，分数是按 combo 计算的，连续 $a$ 个 combo 就有 $a\times a$ 分，combo 就是极大的连续 `o`。

比如`ooxxxxooooxxx`，分数就是 $2 \times 2 + 4 \times 4 = 4 +16=20$。

Sevenkplus 闲的慌就看他打了一盘，有些地方跟运气无关要么是 `o` 要么是 `x`，有些地方 `o` 或者 `x` 各有 $50\%$ 的可能性，用 `?` 号来表示。

比如 `oo?xx` 就是一个可能的输入。
那么 WJMZBMR 这场 osu 的期望得分是多少呢？

比如 `oo?xx` 的话，`?` 是 `o` 的话就是 `oooxx`（$9$），是x的话就是 `ooxxx`（$4$），期望自然就是 $(4+9)/2 =6.5$ 了。

inputFormat:
第一行一个整数 $n$（$n\le3\times10^5$），表示点击的个数

接下来一个字符串，每个字符都是 `o`，`x`，`?` 中的一个

outputFormat:
一行一个浮点数表示答案

四舍五入到小数点后 $4$ 位

如果害怕精度跪建议用 long double 或者 extended。


title: 有序表的合并

description:
给出两个数列 $a, b$，均按不降序排序。其中保证 $a$ 中没有重复的数字。

现在请你求出：$a$ 中每一个数字在 $b$ 中出现了几次？

inputFormat:
**本题单测试点内有多组测试数据**。

输入的第一行是一个整数，表示数据组数 $T$。接下来按顺序给出每组数据的输入信息：

第一行为两个整数，依次表示 $a$ 数列的长度 $n$ 和 $b$ 数列的长度 $m$。
第二行有 $n$ 个整数表示数列 $a$，第 $i$ 个整数表示 $a_i$。
第三行有 $m$ 个整数表示数列 $b$，第 $i$ 个整数表示 $b_i$。

outputFormat:
为了避免输出过大，对于每组数据，请你输出一行一个整数，表示数列 $a$ 的每个数在 $b$ 中出现次数的**按位异或和**。

形式化的，设 $a_i$ 在 $b$ 中出现了 $c_i$ 次，则你需要输出 $c_1 \bigoplus c_2 \bigoplus \dots \bigoplus c_n$ 的值，其中 $\bigoplus$ 表示按位异或操作。你可以参考提示来完成计算。

hint:
### 样例 1 解释

- $a_1 = 1$ 在 $b$ 中出现了 $1$ 次。
- $a_2 = 3$ 在 $b$ 中出现了 $2$ 次。
- $a_3 = 6$ 在 $b$ 中出现了 $0$ 次。

故输出为 $1 \bigoplus 2 = 3$。

### 样例 2 解释

$1, 4, 5$ 分别在 $b$ 中出现了 $2, 1, 1$ 次，故输出为 $2 \bigoplus 1 \bigoplus 1 = 2$。

### 数据规模与约定

对于全部的测试点，保证：
- $1 \leq T \leq 10$；
- $1 \leq n, m \leq 10^7$，$\sum (n + m) \leq  10^7$；
- $1 \leq a_i, b_i < 2^{64}$，且 $a_i < a_{i + 1}$，$b_i \leq b_{i + 1}$。

其中 $\sum (n+m)$ 表示单测试点内所有 $n$ 与 $m$ 的和，即输入数列的总长度不超过 $10^7$。

### 提示

- 请注意大量数据读入对程序效率造成的影响，选择合适的读入方式，避免超时。
- 请采用合适的数据类型存储变量，避免溢出。
- 如果你不知道什么是按位异或和，可以在你的代码里添加如下的函数：

```cpp
template <class T>
T getXorSum(T *begin, T *end) {
  T ret = 0;
  for (T *it = begin; it != end; ++it) ret ^= *it;
  return ret;
}
```
这一函数的作用是计算传入数组（包括 `std::vector`）某一左闭右开区间的按位异或和，返回值类型与传入数组的类型相同，调用方法与 `std::sort` 类似，例如，要求数组 $a$ 的 $a_1 \sim a_n$ 的按位异或和，则调用 `getXorSum(a + 1, a + 1 + n)`，求 $a_0 \sim a_{n - 1}$ 的按位异或和，则调用 `getXorSum(a, a + n)`。如果 $a$ 是 `std::vector`，则将上述调用代码里的 `a` 均改为 `a.begin()` 即可。


title: 蚂蚁

description: 有许多蚂蚁在一根无限长的木棍上，每一只蚂蚁都有一个初始位置和初始朝向（任意两只蚂蚁的初始位置不同）。蚂蚁们以每秒一个单位的速度向前移动，当两只蚂蚁相遇时，它们会掉头（掉头时间忽略不计）。现给出每只蚂蚁的初始位置和初始朝向，请你计算出它们在 $t$ 秒后的位置和朝向。

inputFormat:
第一行，两个空格隔开的整数 $n,t$（代表蚂蚁数 $n$ 和时间 $t$）。

第 $2\sim n+1$ 行每行两个整数，第 $i+1$ 行代表第 $i$ 只蚂蚁的初始位置 $a_i$ 及初始朝向 $b_i$（$b_i=1$ 时蚂蚁朝右，$b_i=-1$ 时蚂蚁朝左）。

outputFormat: 共 $n$ 行，每行两个整数，第 $i$ 行代表 $t$ 秒后第 $i$ 只蚂蚁的位置及朝向（$-1$ 表示朝左，$1$ 表示朝右，$0$ 表示正在转向中）。


title: 【模板】最小表示法

description:
小敏和小燕是一对好朋友。

他们正在玩一种神奇的游戏，叫 Minecraft。

他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。

他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。

两个工艺品美观的比较方法是，从头开始比较，如果第 $i$ 个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第 $i+1$ 个方块。如果全都一样，那么这两个工艺品就一样漂亮。

inputFormat:
第一行一个整数 $n$，代表方块的数目。

第二行 $n$ 个整数，每个整数按从左到右的顺序输出方块瑕疵度的值，保证其小于 $30$。

outputFormat: 一行 $n$ 个整数，代表最美观工艺品从左到右瑕疵度的值。


title: 矩形

description: 给出平面上的 $n$ 个点，请找出一个边与坐标轴平行的矩形，使得它的边界上有尽量多的点。

inputFormat:
第一行一个整数 $n$，为平面内点的个数。

第 $2\sim n+1$ 行每行两个整数，为点的横、纵坐标。

outputFormat: 只有一个数，为所取矩形边界上能包含尽量多的点的个数。

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

- 对于 $40\%$ 的数据，$1\le n\le 30$；
- 对于 $100\%$ 的数据，$1\le n\le 300$，各点的横、纵坐标在 $[1,100]$ 范围内。


title: NOI元丹

description:
小A打算开始炼 $\texttt{NOI}$ 元丹（什么鬼），据说吃了可以提高 $\texttt{NOI}$ 时的成绩。

是这么练的。元丹有三种元核，`N`、`O`、`I`。现有很多个这样原核，按顺序排成一行。炼元丹时，从左往右分别挑出 `N`、`O`、`I` 三个原核吞下。

现在他关心，有几种服用方式……且慢！

他觉得服用方式太少，以至于不能成仙。所以他可以通过某个途径，得到 `N`、`O`、`I` 的三种原核中的**任意一个**，至于哪一种由他决定。然后他将获得这个原核的插入到这一排原核中的任意位置（包括最前最后）。

现在你要知道，新的元核序列中能有多少种 `N`、`O`、`I` 的取出方式。子串的字母并不要求连续。

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

第二行，一行字符串，里面只有只有 `N`、`O`、`I` 三种字母。

outputFormat: 表示出最多可以提炼出来的 $\texttt{NOI}$ 元丹的方案种数。

hint:
样例解释：

他可以获取一个 `N` 元核，加到最前面。

```plain
NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI
~ ~~   | ~ ~  ~ | ~   ~~ |  ~~~   |  ~~  ~ |  ~  ~~
```
对于 $30\%$ 的数据 $N \le 200$。

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

对于 $100\%$ 的数据 $3 \le N \le 10 ^ 5$。


title: 又是毕业季I

background: “叮铃铃铃”，随着高考最后一科结考铃声的敲响，三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍，憧憬着未来仍毋忘逝去的歌。$1000$ 多个日夜的欢笑和泪水，全凝聚在毕业晚会上，相信，这一定是一生最难忘的时刻！

description:
为了把毕业晚会办得更好，老师想要挑出默契程度最大的 $k$ 个人参与毕业晚会彩排。可是如何挑呢？老师列出全班同学的号数 $1,2,\ldots ,n$ 并且相信 $k$ 个人的默契程度便是他们的最大公约数（这不是迷信哦~）。这可难为了他，请你帮帮忙吧！

PS：一个数的最大公约数即本身。

inputFormat: 两个空格分开的正整数 $n$ 和 $k$。

outputFormat: 一个整数，为最大的默契值。

hint:
对于 $20\%$ 的数据，$k \le 2$，$n \le 10^3$。

对于另 $30\%$ 的数据，$k \le 10$，$n \le 100$。

对于 $100\%$ 的数据，$k \le 10^9$，$n \le 10^9$，$n \ge k \ge 1$（神犇学校，人数众多）。


title: 小 a 和 uim 之大逃离

background: 小 a 和 uim 来到雨林中探险。突然一阵北风吹来，一片乌云从北部天边急涌过来，还伴着一道道闪电，一阵阵雷声。刹那间，狂风大作，乌云布满了天空，紧接着豆大的雨点从天空中打落下来，只见前方出现了一个披头散发、青面獠牙的怪物，低沉着声音说：“呵呵，既然你们来到这，只能活下来一个！”。小 a 和他的小伙伴都惊呆了！

description:
瞬间，地面上出现了一个 $n\times m$ 的巨幅矩阵，矩阵的每个格子上有一坨 $0\sim k$ 不等量的魔液。

怪物各给了小 a 和 uim 一个魔瓶，说道，你们可以从矩阵的任一个格子开始，每次向右或向下走一步，从任一个格子结束。开始时小 a 用魔瓶吸收地面上的魔液，下一步由 uim 吸收，如此交替下去，并且要求最后一步必须由 uim 吸收。魔瓶只有 $k$ 的容量，也就是说，如果装了 $k+1$ 那么魔瓶会被清空成零，如果装了 $k+2$ 就只剩下 $1$，依次类推。

怪物还说道，最后谁的魔瓶装的魔液多，谁就能活下来。小 a 和 uim 感情深厚，情同手足，怎能忍心让小伙伴离自己而去呢？沉默片刻，小 a 灵机一动，如果他俩的魔瓶中魔液一样多，不就都能活下来了吗？小 a 和他的小伙伴都笑呆了！

现在他想知道他们都能活下来有多少种方法。

inputFormat:
第一行，三个空格隔开的整数 $n,m,k$。

接下来 $n$ 行，$m$ 列，表示矩阵每一个的魔液量。同一行的数字用空格隔开。

outputFormat: 一个整数，表示方法数。由于可能很大，输出对 $1,000,000,007$ 取余后的结果。


title: 进攻幽暗城

background: 由于震惊海内外的 “愤怒门投毒事件” 的发生，部落为了对抗皇家药剂师协会的叛乱，所有的外交工作完成后，部落大酋长萨尔带领着小 A 穿过传送门到达幽暗城平叛。

description:
幽暗城的地图是一个 $n \times m$ 的 $01$ 串。$a_{i, j} = 1$ 时表示 $(i, j)$ 的位置是障碍，无法通过；$a_{i, j} = 0$ 时表示 $(i, j)$ 的位置可以进入。

小 A 与萨尔的初始位置是 $(x_1, y_1)$，而恐惧魔王的初始位置是 $(x_2, y_2)$。小 A 的目标就是到达恐惧魔王的位置。

萨尔会按照一个特定的路线行走，该路线是一个数字串，由 $0 \sim 4$ 组成。

第 $i$ 秒，若数字串第（$i \bmod {}$数字串的长度）位等于 $0$，则表示这一秒萨尔将会原地不动；
等于 $1$，则表示这一秒萨尔会向上走一格；
等于 $2$，则表示这一秒萨尔会向下走一格；
等于 $3$，则表示这一秒萨尔会向左走一格；
等于 $4$，则表示这一秒萨尔会向右走一格。

若萨尔将要移动的位置是墙或者超出迷宫的范围，则萨尔会原地不动。恐惧魔王也是这样。（换句话说，你可以认为如果将数字串是重复无限次，第 $i$ 秒就是字符串第 $i$ 位）

小A每秒可以选择从上下左右四个方向中选择一个方向，朝那个方向走一格，前提是那个位置不是墙并且没有超出迷宫的范围；或者原地不动。不过，由于幽暗城的诡异环境，小 A 只能持续脱离萨尔的光环 $s$ 秒，若超过 $s$ 秒小 A 则会死亡。光环的有效半径为 $d$ ，表示当小 A 与萨尔之间的距离 $\sqrt{(x-xx)^2+(y-yy)^2}$ 小于等于 $d$ 时小 A 才能受到萨尔光环的效果。若小 A 脱离萨尔的光环又重新进入光环有效区域，则再次离开光环时持续时间归零重记。

小 A 想知道最少需要几秒他才能到达恐惧魔王所在的位置。

inputFormat:
第一行四个数 $n,m,s,d$。

接下来的 $n$ 行，每行 $m$ 个数（$0$ 或 $1$），之间没有空格，表示幽暗城的地图。

接下来的一行四个整数，$x_1,y_1,x_2,y_2$（$1 \le x_1,x_2 \le n$，$1 \le y_1,y_2 \le m$）。

接下来的一行是一个数字串，表示萨尔的移动方式。

接下来的一行是一个数字串，表示恐惧魔王的移动方式。

outputFormat: 一行一个整数，表示需要最少的时间。

hint:
**【题目来源】**

kiro 原创

**【数据范围】**

对于 $100\%$ 的数据，$1 \le n,m \le 50$，$0 \le s \le 1000$，$0 \le d \le 100$，$1 \le $ 数字串长度 $ \le 100$，$0 \le $ 答案 $ \le 100$。


title: 小猫

description:
有 $2n$ 只小猫站成一圈，主人小明想把它们两两之间用绳子绑住尾巴连在一起。同时小明是个完美主义者，不容许看到有两根绳子交叉。请问小明有几种连线方案，可以把让所有小猫两两配对？

方案数很大，仅需输出方案数模 $10^9+7$（一个质数）的值。

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

outputFormat: 输出方案数对 $10^9+7$ 取模后的值。


title: [USACO05MAR] Yogurt factory 机器工厂

description:
小 T 开办了一家机器工厂，在 $N$个星期内，原材料成本和劳动力价格不断起伏，第 $i$ 周生产一台机器需要花费 $C_i$ 元。若没把机器卖出去，每保养一台机器，每周需要花费 $S$ 元，这个费用不会发生变化。

机器工厂接到订单，在第 $i$ 周需要交付 $Y_i$ 台机器给委托人，第 $i$ 周刚生产的机器，或者之前的存货，都可以进行交付。

请你计算出这 $n$ 周时间内完成订单的最小代价。

inputFormat: 第一行输入两个整数 $N$ 和 $S$，接下来 $N$ 行每行两个数 $C_i$ 和 $Y_i$。

outputFormat: 输出一个整数，表示最少的代价。


title: [TJOI2011] 树的序

description:
众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：
1. 空树中加入一个键值 $k$，则变为只有一个结点的二叉查找树，此结点的键值即为 $k$。
2. 在非空树中插入一个键值 $k$，若 $k$ 小于其根的键值，则在其左子树中插入 $k$，否则在其右子树中插入 $k$。

我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为 $n$ 的生成序列，先比较第一个插入键值，再比较第二个，依此类推。

inputFormat: 第一行，一个整数 $n$，表示二叉查找树的结点个数。第二行，有 $n$ 个正整数 $k_1, k_2, \cdots,k_n$，表示生成序列，简单起见，$k_1 \sim k_n$ 为一个 $1$ 到 $n$ 的排列。

outputFormat: 一行，$n$ 个正整数，为能够生成同样二叉查找树的所有生成序列中最小的。


title: 油滴扩展

description:
在一个长方形框子里，最多有 $N$ 个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这 $N$ 个点上放置油滴，才能使放置完毕后所有油滴占据的总面积最大呢？（不同的油滴不会相互融合）

注：圆的面积公式 $S = \pi r^2$，其中 $r$ 为圆的半径。

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

第二行，四个整数 $x, y, x', y'$，表示长方形边框一个顶点及其对角顶点的坐标。

接下来 $N$ 行，第 $i$ 行两个整数 $x_i, y_i$，表示盒子内第 $i$ 个点的坐标。

outputFormat: 一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。


title: 八数码难题

description: 在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

inputFormat: 输入初始状态，一行九个数字，空格用 $0$ 表示。

outputFormat: 只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

hint:
### 样例解释

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

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。


title: T型骨牌

description:
现在要在 $n\times m$ 的棋盘上，摆入 T 型，T 型可以旋转，具体包括如下四个样式（“#”代表被T型占据的格子，“.”代表自由的格子）：

```plain
###      ..#      .#.      #..
.#.      ###      .#.      ###
.#.      ..#      ###      #..
```

问最多能在 $n\times m$ 的棋盘上摆入多少个不重叠的 T 型。

inputFormat: 输入共一行两个数 $n,m$。

outputFormat: 输出共一个数，表示最多能放入多少个 T 型。

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

对于全部数据，$1\le n,m\le 9$。

### 样例说明

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


title: 单词背诵

description:
灵梦有 $n$ 个单词想要背，但她想通过一篇文章中的一段来记住这些单词。

文章由 $m$ 个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。

inputFormat:
第 $1$ 行一个数 $n$，接下来 $n$ 行每行是一个长度不超过 $10$ 的字符串，表示一个要背的单词。

接着是一个数 $m$，然后是 $m$ 行长度不超过 $10$ 的字符串，每个表示文章中的一个单词。

outputFormat: 输出文件共 $2$ 行。第 $1$ 行为文章中最多包含的要背的单词数，第 $2$ 行表示在文章中包含最多要背单词的最短的连续段的长度。


title: 楼房

description:
地平线（$x$ 轴）上有 $n$ 个楼房，每个楼房可以表示为一个矩形。

用三个整数 $h_i,l_i,r_i$ 来表示第 $i$ 个矩形：矩形左下角为 $(l_i,0)$，右上角为 $(r_i,h_i)$。

地平线高度为 $0$。在轮廓线长度最小的前提下，从左到右输出轮廓线。

inputFormat:
第一行一个整数 $n$，表示矩形个数。

以下 $n$ 行，每行 $3$ 个整数 $h_i,l_i,r_i$ 表示第 $i$ 个矩形。

outputFormat:
第一行一个整数 $m$，表示节点个数。

以下 $m$ 行，每行一个坐标表示轮廓线上的节点。

要求从左到右遍历轮廓线并顺序输出节点。

注：第一个和最后一个节点的 $y$ 坐标必然为 $0$。

hint:
样例二如图：

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

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

数据范围:

对于 $30\%$ 的数据，$n\le100$。

对于另外 $30\%$ 的数据，$1\le h_i,l_i,r_i\le 1000$。

对于 $100\%$ 的数据，$1\le n\le10^5$，$1\le h_i\le 10^9$，$-10^9\le l_i<r_i\le10^9$。


title: 高级打字机

description:
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。

请为这种高级打字机设计一个程序，支持如下 $3$ 种操作：

1. `T x`：Type 操作，表示在文章末尾打下一个小写字母 $x$。
2. `U x`：Undo 操作，表示撤销最后的 $x$ 次修改操作。
3. `Q x`：Query 操作，表示询问当前文章中第 $x$ 个字母并输出。请注意 Query 操作并不算修改操作。

文章一开始可以视为空串。

inputFormat:
第 $1$ 行：一个整数 $n$，表示操作数量。

以下 $n$ 行，每行一个命令。保证输入的命令合法。

outputFormat: 每行输出一个字母，表示 Query 操作的答案。

hint:
对于前 $20\%$ 的数据，$n\le 200$。

对于前 $50\%$ 的数据，保证 Undo 操作不会撤销 Undo 操作。

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


title: 幸运数与排列

description:
一个数是幸运数当且仅当这个数仅由 $4$ 和 $7$ 构成，比如 $47$，$744$，$4747$。

询问在 $1$ 到 $n$ 的全排列中字典序第 $k$ 小的排列中，有多少个幸运数在排列中的位置编号也是幸运数。

inputFormat: 一行，包含两个整数 $n$，$k$。

outputFormat: 一个整数表示答案。如果不存在第 $k$ 小的排列，则输出 $-1$。


title: 密令

description:
给定一小写字母串 $s$，每次操作你可以选择一个 $p$（$1 \leq p \lt |s|$）执行下述修改中的任意一个：

1. 将 $s_p$ 改为其字典序 $+1$ 的字母，将 $s_{p+1}$ 改为其字典序 $-1$ 的字母；
2. 将 $s_p$ 改为其字典序 $-1$ 的字母，将 $s_{p+1}$ 改为其字典序 $+1$ 的字母。

在经过任意多次操作后，串 $s$ 能变化成多少种字符串？

修改过程中必须保证 $s$ 是合法的小写字母串（即不能对字母 a 进行字典序 $-1$ 的操作），答案对 $10^9 + 7$ 取模。

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

接下来 $T$ 行，每行一个小写字母串 $s$。

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


title: 座位安排

description:
给 $n$ 个人安排座位，先给每个人一个 $1\sim n$ 的编号，设第i个人的编号为 $a_i$（不同人的编号可以相同），接着从第一个人开始，大家依次入座。

第 $i$ 个人来了以后尝试坐到 $a_i$，如果 $a_i$ 被占据了，就尝试 $a_{i+1}$，$a_{i+1}$ 也被占据了的话就尝试 $a_{i+2}$，……，如果一直尝试到第 $n$ 个都不行，该安排方案就不合法。

然而有 $m$ 个人的编号已经确定（他们或许贿赂了你的上司…)，你只能安排剩下的人的编号。求有多少种合法的安排方案。由于答案可能很大，只需输出其除以 $M$ 后的余数即可。

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

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

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

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


title: 最大正方形

description: 在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

inputFormat: 输入文件第一行为两个整数 $n,m(1\leq n,m\leq 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

outputFormat: 一个整数，最大正方形的边长。


title: 算式

description:
给出 $n$ 个数字，不改变它们的相对位置，在中间加入 $k$ 个乘号和 $(n-k-1)$ 个加号，括号随便加，使最终结果尽量大。因为乘号和加号一共就是 $n-1$ 个了，所以恰好每两个相邻数字之间都有一个符号。例如：

$n=5$，$k=2$，$5$ 个数字分别为 $1$，$2$，$3$，$4$，$5$，可以加成：

$$1\times 2\times(3+4+5)=24$$
$$1\times(2+3)\times(4+5)=45$$
$$(1\times2+3)\times(4+5)=45$$
$$\ldots\ldots$$

inputFormat:
输入的第一行为两个用空格隔开的整数，分别表示表示 $n$ 和 $k$。

第二行为 $n$ 个用空格隔开的整数 $a_i$，代表给出的数字。

outputFormat: 输出文件仅一行包含一个整数，表示要求的最大的结果。

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

- 对于 $100\%$ 的数据，保证 $2\le n\le15$，$0\le k\lt n$，$0 \leq a_i \leq 9$，答案小于 $2^{31}$。


title: 一个关于序列的游戏

description:
有一个序列，你可以在上面删除符合要求的连续段若干次。每次删除都会得到连续段长度对应的分数。

需要符合的要求为：

1. 相邻两个元素相差为 $1$。
2. 如果某个元素不在连续段的最左或最右，那么这个元素就不能同时小于相邻的左右两个元素。

$[1,2,3,4,3],[1,2],[3,2],[3]$ 都符合条件。

显然，删除掉连续段后，这个段的左边和右边并在一起成为相邻元素。

你的任务是对于给出的序列，计算出可能获得的最大总分。

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

第二行 $N$ 个数，$V_1,V_2 \cdots V_N$，代表每个长度对应的分数。

第三行 $N$ 个数，$A_1,A_2 \cdots A_N$，代表初始序列的每个元素。

outputFormat: 一个数，可以获得的最大总分。


title: 公约数的和

background: 有一天，TIBBAR 和 LXL 比赛谁先算出 $1 \sim n$ 这 $n$ 个数中每任意两个不同的数的最大公约数的和。LXL 还在敲一个复杂而冗长的程序，争取能在 $100s$ 内出解。而 TIBBAR 则直接想 $1s$ 秒过而获得完胜，请你帮他完成这个任务。

description:
给定 $n$，求
$$\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)$$

其中 $\gcd(i, j)$ 表示 $i$ 和 $j$ 的最大公约数。

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

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

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

- 对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^3$。
- 对于 $100\%$ 的数据，保证 $2 \leq n \leq 2 \times 10^6$。


title: 方阵安排

description:
A 班希望在学校的行军比赛中取得一个好成绩，他们希望自己班级的行军方阵是一个完美的方阵。他们认为，如果每个人四周的男生个数为偶数，那么这就是一个完美的方阵。

现在你已知道 A 班现有的方阵，你需要把尽量少的女生改成男生，使这个方阵变成一个完美的方阵。

inputFormat:
输入的第一行是一个正整数 $n$，表示方阵大小为 $n \times n$ 。

第 $2$ 到第 $(n+1)$ 行，每行 $n$ 个数非零即一的数字，第 $(i + 1)$ 行的第 $j$ 个数字代表方阵第 $i$ 行第 $j$ 列的人的性别，其中 $0$ 为女生，$1$ 为男生。

outputFormat: 输出一个数，表示最少需要把女生改成男生的个数。若无解，输出 $-1$。


title: 取数

description: 在一个 $n$ 行 $m$ 列的数阵中，你须在每一行取一个数（共 $n$ 个数），并将它们相加得到一个和。对于给定的数阵，请你输出和前 $k$ 小的取数方法。

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

第 $2\sim n+1$ 行，每行 $m$ 个正整数。

outputFormat: 一行共 $k$ 个数，代表在每一行取一个数前 $k$ 小的加和。


title: 山上的国度

description:
有一个神秘的小国坐落在南方的青山之上，只有当黄昏时，落日耀眼的余晖刺破薄雾的遮拦，有机缘者才可看到小山上面的 $n$ 个美丽的村庄。

传说这个古老的国家里有 $m$ 条枢纽管道，每一条苍老的管道连接着两个村庄，千百年来为村民提供水源的流通。

$n$ 个村庄里只有一个水库，从有水库的村庄通过这些枢纽管道向其它村庄提供水源。大家都明白水往低处流，所有村庄都能得到水库的供水。

黄小明就是那个有机缘者，同时他也是个偏执狂（把小猫绑在一起的那个变态小明），他迫切的想要知道水库应该在哪一个村庄，你能帮他解决疑惑吗？

inputFormat:
第一行输入 $n,m$（$n,m \leq 300$）。

第二行输入 $n$ 个正整数，第 $i$ 个数表示第 $i$ 个村庄的海拔。之后 $m$ 行每行两个数表示这两个村庄之间有一条道路。（同海拔之间不能相互流水）

outputFormat:
若存在这样的村庄，输出两行：第一行为 `Oui, j'ai trouve la solution.`，第二行为村庄的编号。

否则，请输出 `Non`。


title: 会议

description: 有一个村庄居住着 $n$ 个村民，有 $n-1$ 条路径使得这 $n$ 个村民的家联通，每条路径的长度都为 $1$。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

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

接下来 $n-1$ 行，每行两个数字 $a$ 和 $b$，表示村民 $a$ 的家和村民 $b$ 的家之间存在一条路径。

outputFormat:
一行输出两个数字 $x$ 和 $y$。

$x$ 表示村长将会在哪个村民家中举办会议。

$y$ 表示距离之和的最小值。


title: 营救

background: “咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

description:
妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 $t$ 区，而自己在 $s$ 区。

该市有 $m$ 条大道连接 $n$ 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 $s$ 至 $t$ 的路线，使得经过道路的拥挤度最大值最小。

inputFormat:
第一行有四个用空格隔开的 $n$，$m$，$s$，$t$，其含义见【题目描述】。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示有一条大道连接区 $u$ 和区 $v$，且拥挤度为 $w$。

**两个区之间可能存在多条大道**。

outputFormat: 输出一行一个整数，代表最大的拥挤度。

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

- 对于 $30\%$ 的数据，保证 $n\leq 10$。
- 对于 $60\%$ 的数据，保证 $n\leq 100$。
- 对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m \leq 2 \times 10^4$，$w \leq 10^4$，$1 \leq s, t \leq n$。且从 $s$ 出发一定能到达 $t$ 区。

---

#### 样例输入输出 1 解释

小明的妈妈要从 $1$ 号点去 $3$ 号点，最优路线为 $1$->$2$->$3$。


title: [NOI2013] 矩阵游戏

description:
婷婷是个喜欢矩阵的小朋友，有一天她想用电脑生成一个巨大的 $n$ 行 $m$ 列的矩阵（你不用担心她如何存储）。她生成的这个矩阵满足一个神奇的性质：若用 $F[i,j]$ 来表示矩阵中第 $i$ 行第 $j$ 列的元素，则 $F[i,j]$ 满足下面的递推式:

$$\begin{aligned}
F[1, 1] &= 1 \\
F[i, j] &=a\times F[i, j-1]+b, &j\neq 1 \\
F[i, 1] &=c\times F[i-1, m]+d, &i\neq 1 \\
\end{aligned}$$

递推式中 $a,b,c,d$ 都是给定的常数。

现在婷婷想知道 $F[n,m]$ 的值是多少，请你帮助她。由于最终结果可能很大，你只需要输出 $F[n,m]$ 除以 $10^9+7$ 的余数。

inputFormat: 包含一行有六个整数 $n,m,a,b,c,d$。意义如题所述。

outputFormat: 包含一个整数，表示 $F[n,m]$ 除以 $10^9+7$ 的余数。


title: [NOI2013] 书法家

description:
小 E 同学非常喜欢书法，他听说 NOI2013 已经开始了，想题一幅 “NOI” 的字送给大家。

小 E 有一张非常神奇的纸，纸可以用一个 $n$ 行 $m$ 列的二维方格矩阵来表示，为了描述方便，我们定义矩阵左下角方格坐标为 $(1,1)$，右上角方格坐标为 $(m, n)$。

矩阵的每个方格有一个整数的幸运值。在格子上面写字可以增加大家的幸运度，幸运度的大小恰好是所有被笔写到的方格的幸运值之和。现在你要在上面写
上 `N`，`O`，`I` 三个字母。

下面给出 $3$ 个书法字的定义:
- `N` 由若干（$\ge 3$）个边平行于坐标轴的矩形组成，设由 $K$ 个矩形组成（标号 $1 \ldots K$），第 $i$ 个矩形的左下角方格坐标设为 $(L_i, B_i)$，右上角坐标设为 $(R_i, T_i )$，要求满足：
  1. $L_i \le R_i, B_i \le T_i$；
  2. 对任意 $1 < i \le K$，有 $L_i = R_{i-1} + 1$；
  3. 对任意 $3 \le i < K$，有 $B_{i−1} − 1 \le T_i \le T_{i-1}$，$B_i \le B_{i-1}$；
  4. $B_2 > B_1$，$T_2 = T_1$，$B_{K-1} = B_K$，$T_{K-1} < T_K$；
- `O` 由一个大矩形 $A$，挖去一个小矩形 $B$ 得到，这两个矩形的边都平行于坐标轴。设大矩形 $A$ 左下角的方格坐标为 $(u, v)$，长为 $W$，宽为 $H$，则小矩形 $B$ 满足左下角方格坐标为 $(u + 1, v + 1)$，长 $W - 2$，宽 $H - 2$。要求满足：
  1. $W \ge 3$，$H \ge 3$；
  2. $u > R_K + 1$；
- `I` 为 $3$ 个边平行于坐标轴的从下到上的实心矩形组成，从下到上依次标号为 $1,2,3$，第 $i$ 个矩形的左下角格子坐标设为 $(P_i , Q_i )$，右上角格子坐标设为 $(G_i , H_i )$，要求满足：
  1. $P_i \le G_i , Q_i \le H_i$；
  2. $P_1 = P_3 > u + W$，$G_1 = G_3$；
  3. $Q_1 = H_1 = Q_2 - 1, H_2 + 1 = Q_3 = H_3$；
  4. $P_1 < P_2 \le G_2 < G_1$。

下图是一个 `N`,`O`,`I` 的例子：

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

另外，所有画的图形均不允许超过纸张的边界。现在小 E 想要知道,他能画出的最大幸运度是多少。

inputFormat:
第一行包含两个正整数 $n$ 和 $m$ ,分别表示矩阵的行数和列数。

接下来 $n$ 行，每行有 $m$ 个整数，第 $i + 1$ 行的第 $j$ 个数表示格子 $(j, n - i + 1)$ 的幸运值。

outputFormat: 输出一个整数 $T$，表示小 E 能够获得的最大幸运度。


title: [NOI2013] 快餐店

description:
小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。

快餐店的顾客分布在城市 C 的 $N$ 个建筑中，这 $N$ 个建筑通过恰好 $N$ 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。

现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。

inputFormat:
第一行包含一个整数 $N$，表示城市 C 中的建筑和道路数目。

接下来 $N$ 行，每行 $3$ 个整数，$A_i,B_i,L_i$（$1\leq i\leq N$，$L_i>0$），表示一条道路连接了建筑 $A_i$ 与 $B_i$，其长度为 $L_i$。

outputFormat:
输出仅包含一个实数，四舍五入保留**恰好一位小数**，表示最佳快餐店选址距离最远用户的距离。

注意：你的结果必须恰好有一位小数，小数位数不正确不得分。

hint:
### 样例解释 1

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

### 样例解释 2

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

### 数据范围

- 对于 $10\%$ 的数据，$N\leq 80$，$L_i=1$；
- 对于 $30\%$ 的数据，$N\leq 600$，$L_i\leq 100$；
- 对于 $60\%$ 的数据，$N\leq 2000$，$L_i\leq 10^9$；
- 对于 $100\%$ 的数据，$1\leq N\leq 10^5$，$1\leq L_i \leq 10^9$。


title: 酒店之王

description:
XX 酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有 $p$ 间房间，一天只有固定的 $q$ 道不同的菜，每个房间只能住一位客人，每道菜也只能给一位客人食用。

有一天来了 $n$ 个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间且吃到喜欢的菜）。

要怎么分配，能使最多顾客满意呢？

inputFormat:
第一行给出三个整数，分别表示表示 $n,p,q$。

之后 $n$ 行，每行 $p$ 个整数，只可能是 $0$ 或 $1$，第 $i$ 行第 $j$ 个数表示第 $i$ 个人喜不喜欢第 $j$ 个房间（$1$ 表示喜欢， $0$ 表示不喜欢）。

之后 $n$ 行，每行 $q$ 个整数，只可能是 $0$ 或 $1$，第 $i$ 行第 $j$ 个数表示第 $i$ 个人喜不喜欢第 $j$ 道菜（$1$ 表示喜欢， $0$ 表示不喜欢）。

outputFormat: 最大的顾客满意数。

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

对于全部的测试点，保证 $1 \leq n,p,q \leq 100$。


title: [AHOI2005] 约数研究

description:
科学家们在 Samuel 星球上的探险得到了丰富的能源储备，这使得空间站中大型计算机 Samuel II 的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩，小联被允许用 Samuel II 进行数学研究。

小联最近在研究和约数有关的问题，他统计每个正数 $N$ 的约数的个数，并以 $f(N)$ 来表示。例如 $12$ 的约数有 $1,2,3,4,6,12$，因此 $f(12)=6$。下表给出了一些 $f(N)$ 的取值：

| $N$    | $1$  | $2$  | $3$  | $4$  | $5$  | $6$  |
| ------ | ---- | ---- | ---- | ---- | ---- | ---- |
| $f(N)$ | $1$  | $2$  | $2$  | $3$  | $2$  | $4$  |

现在请你求出：

$$
\sum_{i=1}^n f(i)
$$

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

outputFormat: 输出答案。


title: 平均数

description: 给一个长度为 $n$ 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度 $\ge m$。

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

接下来 $n$ 行，每行一个整数 $a_i$，表示序列第 $i$ 个数字。

outputFormat: 一个整数，表示最大平均数的 $1000$ 倍，如果末尾有小数，直接舍去，不要用四舍五入求整。

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

- 对于 $60\%$ 的数据，保证 $m\le n\le 10^4$；
- 对于 $100\%$ 的数据，保证 $1 \leq m\le n\le 10^5$，$0\le a_i\le2000$。


title: 苦恼的小明

description:
黄小明和他的合伙人想要创办一所英语培训机构，注册的时候要填一张个人情况的表格，在身高一栏小明犯了愁。

身高要求精确到厘米，但小明实在太高了，无法在纸上填下这么长的数字。小明花钱买通了办事人员，于是只要写上他的身高模 $10007$ 的结果就行了。

可小明不会取模，想起前几天请你帮他解决了水库的问题，于是又来找你帮忙。

inputFormat: 小明的身高用 $a_1^{a_2^{\cdots^{a_n}}}$ 表示，第一行输入 $n$，第二行输入 $n$ 个正整数表示 $a_1$ 至 $a_n$。

outputFormat: 一个数字表示小明身高 $\bmod 10007$的值。


title: 方格填数

description:
给一个 $n\times n$ 的方格矩阵，还有 $n\times n$ 个整数，让你将这些整数填入矩阵，使得每行每列每个对角线上整数的和都相等。下面给出几个例子：

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

inputFormat:
第一行一个整数 $n\ (1 \le n \le 4)$。

第二行 $n\times n$ 个整数 $a_i\ (-10^8 \le a_i \le 10^8)$。

outputFormat:
第一行一个整数 $s$ 代表每行每列每个对角线的和值。

接下来输出一个 $n\times n$ 的矩阵，表示填数方案。

数据保证有解，可能存在多种方案，输出字典序最小的（将每行顺次相连之后，字典序最小）

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

- 对于 $80\%$ 的数据，保证 $1 \le n \le 3$；
- 对于 $100\%$ 的数据，保证 $1 \le n \le 4$。


title: [国家集训队] 稳定婚姻

description:
我们已知 $n$ 对夫妻的婚姻状况，称第 $i$ 对夫妻的男方为 $B_i$，女方为 $G_i$。若某男 $B_i$ 与某女 $G_j$ 曾经交往过（无论是大学，高中，亦或是幼儿园阶段，$i \le j$），则当某方与其配偶（即 $B_i$ 与 $G_i$ 或 $B_j$ 与 $G_j$）感情出现问题时，他们有私奔的可能性。不妨设 $B_i$ 和其配偶 $G_i$ 感情不和，于是 $B_i$ 和 $G_j$ 旧情复燃，进而 $B_j$ 因被戴绿帽而感到不爽，联系上了他的初恋情人 $G_k$ ……一串串的离婚事件像多米诺骨牌一般接踵而至。若在 $B_i$ 和 $G_i$ 离婚的前提下，这 $2n$ 个人最终依然能够结合成 $n$ 对情侣，那么我们称婚姻 $i$ 为不安全的，否则婚姻 $i$ 就是安全的。

给定所需信息，你的任务是判断每对婚姻是否安全。

inputFormat:
第一行为一个正整数 $n$，表示夫妻的对数；

以下 $n$ 行，每行包含两个字符串，表示这 $n$ 对夫妻的姓名（先女后男），由一个空格隔开；

第 $n+2$ 行包含一个正整数 $m$，表示曾经相互喜欢过的情侣对数；

以下 $m$ 行，每行包含两个字符串，表示这 $m$ 对相互喜欢过的情侣姓名（先女后男），由一个空格隔开。

outputFormat: 输出文件共包含 $n$ 行，第 $i$ 行为 `Safe`（如果婚姻 $i$ 是安全的）或 `Unsafe`（如果婚姻 $i$ 是不安全的）。

samples:
2
Melanie Ashley
Scarlett Charles
1
Scarlett Ashley

samples:
2
Melanie Ashley
Scarlett Charles
2
Scarlett Ashley
Melanie Charles

hint:
对于 $20\%$ 的数据，$n \le 20$；

对于 $40\%$ 的数据，$n \le 100$，$m \le 400$；

对于 $100\%$ 的数据，所有姓名字符串中只包含英文大小写字母，大小写敏感，长度不大于 $8$，保证每对关系只在输入文件中出现一次，输入文件的最后 $m$ 行不会出现未在之前出现过的姓名，这 $2n$ 个人的姓名各不相同，$1 \le n \le 4000$，$0 \le m \le 20000$。


title: 互质数列sequence【数据疑似有误】

description: 一个数列有 $n$ 个数字，我们定义一种操作：我们可以将相邻两个数字同时除以它们的一个公约数，这个操作所花费的代价为作为除数的这个公约数的值。我们经过若干次这样操作，可以将原数列变为相邻的数对都互质的数列。问达成要求的最小代价。

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

接下来 $n$ 行，每行一个整数，依次表示数列中的每个数字。

outputFormat: 输出最小代价。


title: 骰子

description:
$n$ 个人排成一排，你排在第 $m$ 个。

每轮队首的人投一次骰子。

- 若掷到 $1$，则队首的人获胜。
- 若掷到 $2,4,6$，则队首的人排到队尾。
- 若掷到 $3,5$，则队首的人出队。

若队列中仅剩一人，则该人获胜，求你获胜的概率。

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

outputFormat: 一个实数表示获胜概率，精确到小数点后 $9$ 位。


title: 子序列

description: 给定一个长度为 $N$（$N$ 为偶数）的序列，问能否将其划分为两个长度为 $N / 2$ 的严格递增子序列。

inputFormat:
若干行，每行表示一组数据。

对于每组数据，首先输入一个整数 $N$，表示序列的长度。之后 $N$ 个整数表示这个序列。

outputFormat:
输出行数与输入行数相同。

对于每组数据，如果存在一种划分，则输出 `Yes!`，否则输出`No!`。


title: 树

background: L 发明了一种与树有关的游戏。

description:
他从树中删除任意数量（可以为 $0$）的边，计算删除后所有连通块大小的乘积，L 将得到这么多的分数。

你的任务就是对于一颗给定的树，求出 L 能得到的最大分数。

inputFormat:
第一行一个整数 $n$，表示树的节点个数。

接下来 $(n-1)$ 行，每行两个整数 $u, v$，代表存在一条连接 $u, v$ 的边。

outputFormat: 输出一行一个整数，表示 L 能得到的最大分数。

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

- 对于 $10\%$ 的数据，保证 $n \leq 5$。
- 对于 $30\%$ 的数据，保证 $n \leq 100$。
- 另有 $30\%$ 的数据，保证给出的树是一条链。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 700$，$1 \leq u, v \leq n$。


title: 经营与开发

description:
$4X$ 概念体系，是指在 PC 战略游戏中一种相当普及和成熟的系统概念，得名自 $4$ 个同样以 EX 为开头的英语单词。

- $\verb!eXplore!$（探索）
- $\verb!eXpand!$（拓张与发展）
- $\verb!eXploit!$（经营与开发）
- $\verb!eXterminate!$（征服）

——维基百科

今次我们着重考虑 exploit 部分，并将其模型简化：

你驾驶着一台带有钻头（初始能力值 $w$）的飞船，按既定路线依次飞过 $n$ 个星球。星球笼统的分为 $2$ 类：资源型和维修型。（$p$ 为钻头当前能力值）

1. 资源型：含矿物质量 $a_i$，若选择开采，则得到 $a_i\times p$ 的金钱，之后钻头损耗 $k\%$，即 $p\gets p\times (1-0.01k)$；
2. 维修型：维护费用 $b_i$，若选择维修，则支付 $b_i\times p$ 的金钱，之后钻头修复 $c\%$，即 $p\gets p\times (1+0.01c)$。

注：维修后钻头的能力值可以超过初始值（你可以认为是翻修 + 升级）

金钱可以透支。

请作为舰长的你仔细抉择以最大化收入。

inputFormat:
第一行 $4$ 个整数 $n,k,c,w$。

以下 $n$ 行，每行 $2$ 个整数 $\mathrm{type},x$。

- $\mathrm{type}$ 为 $1$ 则代表其为资源型星球，$x$ 为其矿物质含量 $a_i$；
- $\mathrm{type}$ 为 $2$ 则代表其为维修型星球，$x$ 为其维护费用 $b_i$；

outputFormat: 一个实数（保留 $2$ 位小数），表示最大的收入。


title: 坚果保龄球

description:
PVZ 这款游戏中，有一种坚果保龄球。zombie 从地图右侧不断出现，向左走，玩家需要从左侧滚动坚果来碾死他们。

我们可以认为地图是一个行数为 $6$，列数为 $60$ 的棋盘。zombie 出现的那一秒站在这一行的第 $60$ 列，之后每秒向左移动一步。玩家可以随时在屏幕最某一行第一列摆放坚果，这一行的 zombie 瞬间全被滚过去的坚果碾死。如果 zombie 走到第 $1$ 列没有被消灭，如果再向左走，则你的大脑就会被 zombie 吃掉。

现在有 $n$ 只 zombie！告诉你每只 zombie 出现的时间以及在出现的行数（可能会同时出现同一位置的僵尸），请问至少需要多少坚果才能消灭所有的 zombie。

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

之后 $n$ 行中，每行两个正整数 $P$ 和 $t$，分别表示 zombie 所在行和 zombie 出现的时间。

outputFormat: 一个正整数，最少需要的坚果数。

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

对于全部数据，$n \le 2000$，$t \le 100000$，$1 \le P \le 6$。

### 题目来源

kkksc03 改编


title: 又是毕业季II

background: “叮铃铃铃”，随着高考最后一科结考铃声的敲响，三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍，憧憬着未来仍毋忘逝去的歌。一千多个日夜的欢笑和泪水，全凝聚在毕业晚会上，相信，这一定是一生最难忘的时刻！

description:
彩排了一次，老师不太满意。当然啦，取每位同学的号数来找最大公约数显然不太合理。于是老师给每位同学评了一个能力值。于是现在问题变为，从 $n$ 个学生中挑出 $k$ 个人使得他们的默契程度（即能力值的最大公约数）最大。但因为节目太多了，而且每个节目需要的人数又不知道。老师想要知道所有情况下能达到的最大默契程度是多少。这下子更麻烦了，还是交给你吧~

PS：一个数的最大公约数即本身。

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

第二行为 $n$ 个空格隔开的正整数，表示每个学生的能力值。

outputFormat: 总共 $n$ 行，第 $i$ 行为 $k=i$ 情况下的最大默契程度。

hint:
【题目来源】

lzn 原创

【数据范围】

记输入数据中能力值的最大值为 $\textit{inf}$。

- 对于 $20\%$ 的数据，$n \leq 5$，$\textit{inf}\leq 10^3$；
- 对于另 $30\%$ 的数据，$n \leq 100$，$\textit{inf} \leq 10$；
- 对于 $100\%$ 的数据，$n \leq 10^4$，$\textit{inf} \leq 10^6$。


title: 拆分数列

description: 给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。

inputFormat: 共一行，为初始的数字。

outputFormat: 共一行，为拆分之后的数列。每个数之间用逗号分隔。行尾无逗号。

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

记输入的字符串的长度为 $l$。

- 对于 $10\%$ 的数据，$l \le 5$；
- 对于 $30\%$ 的数据，$l \le 15$；
- 对于 $50\%$ 的数据，$l \le 50$；
- 对于 $100\%$ 的数据，$l \le 500$。

### 题目来源

lzn 改编


title: 攻击火星

description:
一群外星人将要攻击火星。

火星的地图是一个 $n$ 个点的无向图。这伙外星人将按照如下方法入侵，先攻击度为 $0$ 的点（相当于从图中删除掉它），然后是度为 $1$ 的点，依此类推直到度为 $n-1$ 的点。

所有的点度统计是动态统计的。（一个点删掉后，与之相连的点的点度都会 $-1$）。外星人攻击度为某个数的点时是同时攻击的。

你需要设计这个图的边的方案来使得未被攻击的点最多。注意：你设计的图**不允许自环及重边**。

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

outputFormat: 一行一个整数，表示最多的最后未被攻击的点。

hint:
【样例解释】

一种可能的方案是 $1\leftrightarrow 2\leftrightarrow 3$，这样首先删掉度为 $1$ 的点 $1$ 和点 $3$，此时点 $2$ 度数为 $0$，不会被删去。

【数据范围】

- 对于 $20\%$ 的数据 $1\le n\le 10$；
- 对于 $100\%$ 的数据 $1\le n\le 5\times 10^4$。

【题目来源】

tinylic改编


title: 烹调方案

background:
由于你的帮助，火星只遭受了最小的损失。但 gw 懒得重建家园了，就造了一艘飞船飞向遥远的 earth 星。不过飞船飞到一半，gw 发现了一个很严重的问题：肚子饿了 ~。

gw 还是会做饭的，于是拿出了储藏的食物准备填饱肚子。gw 希望能在 $T$ 时间内做出最美味的食物，但是这些食物美味程度的计算方式比较奇葩，于是绝望的 gw 只好求助于你了。

description:
一共有 $n$ 件食材，每件食材有三个属性，$a_i$，$b_i$ 和 $c_i$，如果在 $t$ 时刻完成第 $i$ 样食材则得到 $a_i-t\times b_i$ 的美味指数，用第 $i$ 件食材做饭要花去 $c_i$ 的时间。

众所周知，gw 的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大。

inputFormat:
第一行是两个正整数 $T$ 和 $n$，表示到达地球所需时间和食材个数。

- 下面一行 $n$ 个整数，$a_i$；
- 下面一行 $n$ 个整数，$b_i$；
- 下面一行 $n$ 个整数，$c_i$。

outputFormat: 输出最大美味指数。

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

- 对于 $40\%$ 的数据 $1 \le n \le 10$；
- 对于 $100\%$ 的数据 $1 \le n \le 50$。

所有数字均小于 $10^5$。

### 题目来源

tinylic 改编


title: [TJOI2011] 构造矩阵

description:
要求构造一个 $n\times m$ 的 $01$ 矩阵，满足每一行中 $1$ 的个数分别为 $r_1,r_2,\ldots,r_n$ ,每一列中1的个数为 $c_1,c_2,\ldots,c_m$。

在此基础上要求字典序最小。两个矩阵比较字典序时先比较第一行，第一行相等再比较第二行……

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

第二行输入 $n$ 个整数 $r_1,r_2,\ldots,r_n$。

第三行输入 $m$ 个整数 $c_1,c_2,\ldots,c_m $。

outputFormat: 输出一个 $n\times m$ 的矩阵。


title: 寻找段落

description:
给定一个长度为 $n$ 的序列 $a$，定义 $a_i$ 为第 $i$ 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 $[S, T]$ 之间的连续序列。最有价值段落是指平均值最大的段落。

**段落的平均值** 等于 **段落总价值** 除以 **段落长度**。

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

第二行两个整数 $S$ 和 $T$，表示段落长度的范围，在 $[S, T]$ 之间。

第三行到第 $n+2$ 行，每行一个整数表示每个元素的价值指数。

outputFormat: 一个实数，保留 $3$ 位小数，表示最优段落的平均值。

hint:
【数据范围】

对于 $30\%$ 的数据有 $n \le 1000$。

对于 $100\%$ 的数据有 $1 \le n \le 100000$，$1 \le S \le T \le n$，$-{10}^4 \le a_i \le {10}^4$。

【题目来源】

tinylic 改编


title: 最长连号

description:
输入长度为 $n$ 的一个正整数序列，要求输出序列中最长连号的长度。

连号指在序列中，从小到大的连续自然数。

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

第二行，$n$ 个整数 $a_i$，之间用空格隔开。

outputFormat: 一个数，最长连号的个数。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^4$，$1 \leq a_i \leq 10^9$。


title: 小玉买文具

description: 班主任给小玉一个任务，到文具店里买尽量多的签字笔。已知一只签字笔的价格是 $1$ 元 $9$ 角，而班主任给小玉的钱是 $a$ 元 $b$ 角，小玉想知道，她最多能买多少只签字笔呢。

inputFormat: 输入只有一行两个整数，分别表示 $a$ 和 $b$。

outputFormat: 输出一行一个整数，表示小玉最多能买多少只签字笔。

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

对于全部的测试点，保证 $0 \leq a \leq 10^4$，$0 \leq b \leq 9$。


title: 小玉家的电费

description: 夏天到了，各家各户的用电量都增加了许多，相应的电费也交的更多了。小玉家今天收到了一份电费通知单。小玉看到上面写：据闽价电 [2006]27 号规定，月用电量在 $150$ 千瓦时及以下部分按每千瓦时 $0.4463$ 元执行，月用电量在 $151\sim 400$ 千瓦时的部分按每千瓦时 $0.4663$ 元执行，月用电量在 $401$ 千瓦时及以上部分按每千瓦时 $0.5663$ 元执行。小玉想自己验证一下，电费通知单上应交电费的数目到底是否正确呢。请编写一个程序，已知用电总计，根据电价规定，计算出应交的电费应该是多少。

inputFormat: 输入一个正整数，表示用电总计（单位以千瓦时计），不超过 $10000$。

outputFormat: 输出一个数，保留到小数点后 $1$ 位（单位以元计，保留到小数点后 $1$ 位）。


title: 小玉在游泳

description: 小玉开心的在游泳，可是她很快难过的发现，自己的力气不够，游泳好累哦。已知小玉第一步能游 $2$ 米，可是随着越来越累，力气越来越小，她接下来的每一步都只能游出上一步距离的 $98\%$。现在小玉想知道，如果要游到距离 $s$ 米的地方，她需要游多少步呢。请你编程解决这个问题。

inputFormat: 输入一个实数 $s$（单位：米），表示要游的目标距离。

outputFormat: 输出一个整数，表示小玉一共需要游多少步。

hint: 数据保证，$0 \leq s < 100$，且 $s$ 小数点后最多只有一位。


title: 小鱼的航程（改进版）

description: 有一只小鱼，它平日每天游泳 $250$ 公里，周末休息（实行双休日)，假设从周 $x$ 开始算起，过了 $n$ 天以后，小鱼一共累计游泳了多少公里呢？

inputFormat: 输入两个正整数 $x,n$，表示从周 $x$ 算起，经过 $n$ 天。

outputFormat: 输出一个整数，表示小鱼累计游泳了多少公里。

hint: 数据保证，$1\le x \le 7$，$1 \le n\le 10^6$。


title: 小鱼的游泳时间

description:
伦敦奥运会要到了，小鱼在拼命练习游泳准备参加游泳比赛，可怜的小鱼并不知道鱼类是不能参加人类的奥运会的。

这一天，小鱼给自己的游泳时间做了精确的计时（本题中的计时都按 $24$ 小时制计算），它发现自己从 $a$ 时 $b$ 分一直游泳到当天的 $c$ 时 $d$ 分，请你帮小鱼计算一下，它这天一共游了多少时间呢？

小鱼游的好辛苦呀，你可不要算错了哦。

inputFormat: 一行内输入四个整数，以空格隔开，分别表示题目中的 $a, b, c, d$。

outputFormat: 一行内输出两个整数 $e$ 和 $f$，用空格间隔，依次表示小鱼这天一共游了多少小时多少分钟。其中表示分钟的整数 $f$ 应该小于 $60$。

hint: 对于全部测试数据，$0\le a,c \le 24$，$0\le b,d \le 60$，且结束时间一定晚于开始时间。


title: 小鱼会有危险吗

description: 有一次，小鱼要从 A 处沿直线往右边游，小鱼第一秒可以游 $7$ 米，从第二秒开始每秒游的距离只有前一秒的 $98\%$。有个极其邪恶的猎人在距离 A 处右边 $s$ 米的地方，安装了一个隐蔽的探测器，探测器左右 $x$ 米之内是探测范围。一旦小鱼进入探测器的范围，探测器就会在这一秒结束时把信号传递给那个猎人，猎人在一秒后就要对探测器范围内的水域进行抓捕，这时如果小鱼还在这范围内就危险了。也就是说小鱼一旦进入探测器范围，如果能在下 $1$ 秒的时间内马上游出探测器的范围，还是安全的。现在给出 $s$ 和 $x$ 的数据，请你判断小鱼会不会有危险？如果有危险输出 `y`，没有危险输出 `n`。

inputFormat: 一行内输入两个实数，用空格分隔，表示 $s$ 和 $x$。

outputFormat: 一行内输出'y'或者'n'表示小鱼是否会有危险。

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

对于 $100\%$ 的数据，保证 $1 \leq s,x\le100$，小数点后最多有 $6$ 位小数。


title: 小鱼的数字游戏

description: 小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字 $a_i$（长度不一定，以 $0$ 结束），记住了然后反着念出来（表示结束的数字 $0$ 就不要念出来了）。这对小鱼的那点记忆力来说实在是太难了，你也不想想小鱼的整个脑袋才多大，其中一部分还是好吃的肉！所以请你帮小鱼编程解决这个问题。

inputFormat: 一行内输入一串整数，以 $0$ 结束，以空格间隔。

outputFormat: 一行内倒着输出这一串整数，以空格间隔。

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

对于 $100\%$ 的数据，保证 $0 \leq a_i \leq 2^{31} - 1$，数字个数不超过 $100$。


title: 小鱼比可爱

description: 人比人，气死人；鱼比鱼，难死鱼。小鱼最近参加了一个“比可爱”比赛，比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排，头都朝向左边，然后每只鱼会得到一个整数数值，表示这只鱼的可爱程度，很显然整数越大，表示这只鱼越可爱，而且任意两只鱼的可爱程度**可能一样**。由于所有的鱼头都朝向左边，所以每只鱼只能看见在它左边的鱼的可爱程度，它们心里都在计算，在自己的眼力范围内有多少只鱼不如自己可爱呢。请你帮这些可爱但是鱼脑不够用的小鱼们计算一下。

inputFormat:
第一行输入一个正整数 $n$，表示鱼的数目。

第二行内输入 $n$ 个正整数，用空格间隔，依次表示从左到右每只小鱼的可爱程度 $a_i$。

outputFormat: 一行，输出 $n$ 个整数，用空格间隔，依次表示每只小鱼眼中有多少只鱼不如自己可爱。

hint: 对于 $100\%$ 的数据，$1 \leq n\leq 100$，$0 \leq a_i \leq 10$。


title: 平面最近点对（加强版）

background: [P7883](/problem/P7883) 平面最近点对（加强加强版）

description: 给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的

inputFormat:
第一行：$n$ ，保证 $2\le n\le 200000$ 。

接下来 $n$ 行：每行两个实数：$x\ y$ ，表示一个点的行坐标和列坐标，中间用一个空格隔开。

outputFormat: 仅一行，一个实数，表示最短距离，精确到小数点后面 $4$ 位。

hint: 数据保证 $0\le x,y\le 10^9$


title: 序列取数

description: 给定一个长为 $n$ 的整数序列 $(n \le 1000)$，由 A 和 B 轮流取数（A 先取）。每个人可从序列的左端或右端取若干个数（至少一个），但不能两端都取。所有数都被取走后，两人分别统计所取数的和作为各自的得分。假设 A 和 B 都足够聪明，都使自己得分尽量高，求 A 的最终得分。

inputFormat:
第一行，一个正整数 $T$，表示有 $T$ 组数据。（$T \le 100$）

接着 $T$ 行，每行第一个数为 $n$，接着 $n$ 个整数表示给定的序列。

outputFormat: 输出T行，每行一个整数，表示 A 的得分。