title: [ZJOI2015] 醉熏熏的幻想乡

description:
傲娇少女幽香是一个很萌很萌的妹子，这些天幻想乡的大家都不知道为何还是拼命喝酒。很快酒就供不应求了，为了满足大家的需求，幽香决定在森林里酿酒。

经过调查，幽香发现森林里面有一些地方非常适合酿酒，有一些地方则非常适合存酒。幽香把这些适合酿酒的地方成为酿酒点，不妨认为有 $n$ 个酿酒点，从 $1$ 到 $n$ 标号。同时也有 $m$ 个适合存酒的地方，幽香将它们成为存酒点，从 $1$ 到 $m$ 标号。在一些酿酒点和存酒点之间存在通道，如果酿酒点 $i$ 到存酒点 $j$ 之间存在通道，那么 $i$ 生产的酒就可以被运输到 $j$。

但是在一个地方酿酒是需要消耗幽香的魔力的，由于存在管理上的因素，在酿酒点 $i$，制造 $x$ 升的酒，需要花费 $a_i\cdot x^2+b_i\cdot x$ 的魔力，注意 $x$ 不一定是一个非负整数，也可以是一个非负实数，同时在这个点最多只能制造 $c_i$ 升的酒。每个存酒点 $j$ 有一个容量 $d_j$，表示这个存酒点最多能存多少升的酒。

幽香打算存尽量多的酒，那么她需要再一些酿酒点生产一些酒并且通过通道将酒运送到存酒点。当然幽香想要节省自己的魔力，所以想让你帮忙算出在满足要求的情况下，最少花费的魔力是多少？

inputFormat: 第一行两个正整数 $n$，$m$，表示酿酒点和存酒点的数量。接下来 $n$ 行，第 $i$ 行三个数 $a_i$，$b_i$，$c_i$，表示在酿酒点 $i$ 制造酒的花费系数和上限。接下来一行 $m$ 个整数，一次为每个存酒点的 $d_i$ 值。接下来 $n$ 行，每行 $m$ 个数，其中第 $i$ 行第 $j$ 个表示酿酒点 $i$ 到存酒点 $j$ 有没有通道（$1$ 表示有，$0$ 表示没有）。

outputFormat:
输出第一行表示幽香最多能存多少升酒（注意这肯定是个整数，直接输出即可）。

输出第二行表示最小花费魔力，注意这肯定是一个有理数，化简后按照 $a/b$ 的形式输出（$0$输出 $0/1$）

hint:
对于 $30\%$ 的数据：所有 $a_i=0$。

对于另 $30\%$ 的数据：最终答案的分母 $\leq 1000$。

对于 $100\%$ 的数据：$1\leq n\leq100$，$1\leq m\leq100$。

对于所有数据，$0\leq a_i,b_i,c_i,d_i\leq3$ 且都是整数。同时对于每个 $i$，$a_i+b_i>0$ 的通道的数量不超过 $1000$ 条。

非常神奇的是，对于所有数据存在一个正整数 $X\leq10^7$，使得存在一个最优解，使得所有路径上运送的酒的体积都是 $1/X$ 的倍数。


title: [ZJOI2016] 大森林

type: P

description:
小 Y 家里有一个大森林，里面有 $n$ 棵树，编号从 $1$ 到 $n$。一开始这些树都只是树苗，只有一个节点，标号为 $1$。这些树都有一个特殊的节点，我们称之为生长节点，这些节点有生长出子节点的能力。

小 Y 掌握了一种魔法，能让第 $l$ 棵树到第 $r$ 棵树的生长节点长出一个子节点。同时她还能修改第 $l$ 棵树到第 $r$ 棵树的生长节点。她告诉了你她使用魔法的记录，你能不能管理她家的森林，并且回答她的询问呢？

inputFormat:
第一行包含 $2$ 个正整数 $n,m$，共有 $n$ 棵树和 $m$ 个操作。

接下来 $m$ 行，每行包含若干非负整数表示一个操作，操作格式为：

`0 l r` 表示将第 $l$ 棵树到第 $r$ 棵树的生长节点下面长出一个子节点，子节点的标号为上一个 $0$ 号操作叶子标号加 $1$（例如，第一个 $0$ 号操作产生的子节点标号为 $2$）， $l$ 到 $r$ 之间的树长出的节点标号都相同。保证 $1\leq l\leq r\leq n$ 。

`1 l r x` 表示将第 $l$ 棵树到第 $r$ 棵树的生长节点改到标号为 $x$ 的节点。对于 $i$ ($l\leq i\leq r$) 这棵树，如果标号 $x$ 的点不在其中，那么这个操作对该树不产生影响。保证 $1\leq l\leq r\leq n$，$x$ 不超过当前所有树中节点最大的标号。

`2 x u v` 询问第 $x$ 棵树中节点 $u$ 到节点 $v$ 点的距离，也就是在第 $x$ 棵树中从节点 $u$ 和节点 $v$ 的最短路上边的数量。保证 $1\leq x\leq n$，这棵树中节点 $u$ 和节点 $v$ 存在。

outputFormat: 输出包括若干行，按顺序对于每个小 Y 的询问输出答案。


title: [ZJOI2016] 小星星

description:
小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 $n$ 颗小星星，用 $m$ 条彩色的细线串了起来，每条细线连着两颗小星星。

有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 $n-1$ 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。

只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢。

inputFormat:
第一行包含 $2$ 个正整数 $n,m$，表示原来的饰品中小星星的个数和细线的条数。

接下来 $m$ 行，每行包含 $2$ 个正整数 $u,v$，表示原来的饰品中小星星 $u$ 和 $v$ 通过细线连了起来。这里的小星星从 $1$ 开始标号。保证 $u\neq v$，且每对小星星之间最多只有一条细线相连。

接下来 $n-1$ 行，每行包含 $2$ 个正整数 $u,v$，表示现在的饰品中小星星 $u$ 和 $v$ 通过细线连了起来。保证这些小星星通过细线可以串在一起。

outputFormat:
输出共 $1$ 行，包含一个整数表示可能的对应方式的数量。

如果不存在可行的对应方式则输出 `0`。

hint: 对于 $100\%$ 的数据，$n\leq 17$，$m\leq \frac 12n(n-1)$。


title: [ZJOI2016] 旅行者

description:
小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有  $n$ 条从东到西的道路和  $m$ 条从南到北的道路，这些道路两两相交形成  $n\times m$ 个路口  $(i,j)$，  $(1\leq i\leq n,1\leq j\leq m)$

她发现不同的道路路况不同，所以通过不同的路口需要不同的时间。通过调查发现，从路口  $(i,j)$ 到路口  $(i,j+1)$ 需要时间  $r(i,j)$ ，从路口  $(i,j)$ 到路口  $(i+1,j)$ 需要时间  $c(i,j)$ 。注意这里的道路是双向的。小 Y 有  $q$ 个询问，她想知道从路口  $(x1,y1)$ 到路口  $(x2,y2)$ 最少需要花多少时间。

inputFormat:
第一行包含 2 个正整数  $n,m$ 表示城市的大小。

接下来  $n$ 行，每行包含  $m-1$ 个整数，第  $i$ 行第  $j$ 个正整数表示从一个路口到另一个路口的时间  $r(i,j)$ 。

接下来  $n-1$ 行，每行包含  $m$ 个整数，第  $i$ 行第  $j$ 个正整数表示从一个路口到另一个路口的时间  $c(i,j)$。

接下来一行，包含一个正整数  $q$，表示小 Y 的询问个数。

接下来  $q$ 行，每行包含  $4$ 个正整数  $x1,y1,x2,y2$，表示两个路口的位置。

outputFormat: 输出共  $q$ 行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。


title: [ZJOI2016] 电阻网络

description:
小 Y 是一个充满智慧的女孩子，但是她只会使用串并联的方法计算两个节点之间的电阻。现在小 Y 有一个电阻网络问有多少点对 $u, v$（$u \ne v$）之间的电阻可以用串并联的方法计算出来。

我们来形式化地定义一下点对 $u, v$（$u \ne v$）之间的电阻能否用串并联的方法计算出来。首先我们把电阻网络看成一个 $n$ 个点 $m$ 条边的图（每个电阻对应一条边）。

令 $S$ 表示从 $u$ 到 $v$ 的所有简单路径（不经过重复的点的路径）上点的并集，也就是对于一个点 $x$，如果存在一条从 $u$ 到 $v$ 的简单路径经过这个点，那么它就在集合 $S$ 中。

如果 $S$ 非空且 $S$ 的导出子图是 $u, v$ 为端点的二端串并联图，那么 $u, v$ 之间的电阻就能用串并联方法计算。

一个有两个不同端点 $s, t$ 的图被称为二端图，其中一个称为源点，另一个称为汇点。两个二端图 $X, Y$ 并联（parallel composition）是指建一个新图，把 $X$ 和 $Y$ 的源点和汇点分别合并起来。两个二端图 $X, Y$ 串联（series composition）是指建一个新图，把 $X$ 的汇点和 $Y$ 的源点合并起来。由若干个两个点一条边的二端图经过一系列串并联变化之后形成的图称为二端串并联图。

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

集合 $S$ 的导出子图点集为 $S$，边集由原图中两个端点都在 $S$ 中的边构成。

inputFormat:
第一行包含两个正整数 $n, m$，表示电阻网络中的节点数和电阻数。
接下来 $m$ 行，每行包含两个正整数 $u, v$（$1 \le u, v \le n$，$u \ne v$），表示有一个电阻在节点 $u$ 和 $v$ 之间。

outputFormat: 输出共一行，表示答案，即有多少点对之间的电阻可以使用串并联的方法计算出来。

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

可行的点对有 $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (5, 6)$。

**【数据范围】**

对于 $10 \%$ 的数据，$n, m \le 10$，保证原图连通，并且不存在一个点删去之后使得原图不连通。
对于另外 $10 \%$ 的数据，$n, m \le 100$，保证原图连通，并且不存在一个点删去之后使得原图不连通。
对于 $30 \%$ 的数据，$n, m \le 100$。
对于 $40 \%$ 的数据，$n, m \le 1000$。
对于另外 $30 \%$ 的数据，保证原图连通，并且不存在一个点删去之后使得原图不连通。
对于 $100 \%$ 的数据，$1 \le n, m \le {10}^5$。


title: [ZJOI2016] 线段树

description:
小 Yuuka 遇到了一个题目：有一个序列 $a_1,a_2,\ldots,a_n$，$q$ 次操作。每次操作把一个区间内的数改成区间内的最大值，问最后每个数是多少。小 Yuuka 很快地就使用了线段树解决了这个问题。

于是充满智慧的小 Yuuka 想，如果操作是随机的，即在这 $q$ 次操作中每次等概率随机地选择一个区间 $[l,r]$（$1 \leq l \leq r \leq n$），然后将这个区间内的数改成区间内最大值（注意这样的区间共有 $\frac{n(n+1)}{2}$ 个），最后每个数的期望大小是多少呢？

小 Yuuka 非常热爱随机，所以她给出的输入序列也是随机的（随机方式见数据规模和约定）。

对于每个数，输出它的期望乘 $\left(\frac{n(n+1)}{2} \right)^q$ 再对 $10^9+7$ 取模的值。

inputFormat:
第一行包含两个正整数 $n,q$，表示序列里数的个数和操作的个数。

接下来一行，包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

outputFormat: 输出共一行，包含 $n$ 个整数，表示每个数的答案。


title: 分段

description:
给定你n个数$a_1、a_2、a_3、...、a_n$，要求将它们分成若干连续的段。

要求：

1. 有m对给定的数不能被分到同一段。

2. 分出一个段的代价是$K + S \times (P - Q)$，其中K和S均为给定的常数，而P则是该段中所有数的最大值，Q是该段中所有数的最小值。

3. 要求你求出每段代价之和最小的分段方案。

inputFormat:
第一行两个正整数n和m，表示数的个数和不能共存的m对数。

第二行两个非负整数K和S，含义见题面。

第三行n个非负整数，即给定的n个数。

接下来m行每行2个数$p_i$和$q_i$，表示$p_i$和$q_i$这两个编号的数不能共存。（编号从1开始）

outputFormat: 输出仅一行，表示最小的每段代价之和。

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

对于30%的数据，$n \leq 1500$；

对于另外10%的数据，$S = 0$；

对于另外30%的数据，$m = 0$；

对于100%的数据，1≤m,n≤100000，0≤K,S,a\_i≤100000，1≤pi,qi≤n，pi≠qi。


title: 仓鼠找sugar II

description:
小仓鼠和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 $1\sim n$ 间的一个整数。地下洞穴是一个树形结构（两个洞穴间距离为 $1$）。这一天小仓鼠打算从从他的卧室 $a$（**是任意的**）走到他的基友卧室 $b$（还**是任意的**）（注意，$a$ 有可能等于 $b$）。然而小仓鼠学 OI 学傻了，不知道怎么怎么样才能用最短的路程走到目的地，于是他只能随便乱走。当他在一个节点时，会等概率走到这个点的母亲或者所有孩子节点（例如这个节点有一个母亲节点和两个子节点，那么下一步走到这 $3$ 个节点的概率都是 $\dfrac{1}{3}$），一旦走到了他基友的卧室，就会停下。

现在小仓鼠希望知道，他走到目的地时，走的步数的期望。这个期望本来是一个有理数，但是为了避免误差，我们要求输出这个有理数对 $998,244,353$ 取模的结果。

形式化地说，可以证明答案可以被表示为既约分数 $\dfrac{y}{x}$，其中 $x\not\equiv 0\pmod {998,244,353}$。可以证明存在一个唯一的整数 $z$（$0\le z\lt 998,244,353$），使得 $xz=y$，你只需要输出 $z$ 的值。

小仓鼠那么弱，还要天天被 JOHNKRAM 大爷虐，请你快来救救他吧！

inputFormat:
第一行一个正整数 $n$，表示这棵树节点的个数。

接下来 $n-1$ 行，每行两个正整数 $u$ 和 $v$，表示节点 $u$ 到节点 $v$ 之间有一条边。

outputFormat: 一个整数，表示取模后的答案。

hint:
样例解释：期望的真实值为 $\dfrac {16}{9}$。

如果 $a$ 是叶子，$b$ 是根，此时期望 $\mathbb{E}_1=1$，有 $2$ 种情况。

如果 $a$ 是根，$b$ 是叶子，则 $\displaystyle \mathbb{E}_2=\frac{1}{2}+\frac{3}{4}+\frac{5}{8}+\cdots=3$。有 $2$ 种情况。

如果 $a,b$ 是不同的叶子，则 $\mathbb{E}_3=\mathbb{E}_2+1=4$。有 $2$ 种情况。

如果 $a=b$，则 $\mathbb{E}_4=0$。有 $3$ 种情况。

所以答案为 $\displaystyle \frac{2\times 1+2\times 3+2\times 4+3\times 0}{2+2+2+3}=\frac{16}{9}$。

由于 $110,916,041\times 9=998,244,369\equiv 16\pmod {998,244,353}$，所以输出 $110,916,041$。

对于 $30\%$ 的数据，$n\le 5$；

对于 $50\%$ 的数据，$n\le 5000$；

对于所有数据，$n\le 100000$。

$\text{Statement fixed by @Starrykiller.}$


title: 地毯

description:
在 $n\times n$ 的格子上有 $m$ 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

inputFormat:
第一行，两个正整数 $n,m$。意义如题所述。

接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。

outputFormat:
输出 $n$ 行，每行 $n$ 个正整数。

第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。


title: 骑士共存问题

description:
在一个 $n \times n$ 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。

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

对于给定的 $n \times n$ 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

inputFormat: 第一行有 $2$ 个正整数 $n$ 和 $m$ ，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 $2$ 个正整数，表示障碍的方格坐标。

outputFormat: 将计算出的共存骑士数输出。

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

对于全部的测试点，保证 $1 \leq n \leq 200$，$0 \leq m \lt n^2$。

tags: 网络流与线性规划 24 题


title: 火星探险问题

description:
火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。

探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后，其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。

本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动，而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进，则该车所采集的岩石标本将全部损失。

用一个 $p \times q$ 网格表示登陆舱与传送器之间的位置。登陆舱的位置在
$(x_1,y_1)$ 处，传送器的位置在 $(x_py_q)$ 处。

$$\begin{bmatrix} (x_1,y_1) & (x_2,y_1) & \dots & (x_{p-1},y_1) & (x_p,y_1) \\ (x_1,y_2) & (x_2,y_2) & \dots & (x_{p-1},y_2) & (x_p,y_2) \\ \dots & \dots & \dots & \dots & \dots \\ (x_1,y_{q-1}) & (x_2,y_{q-1}) & \dots & (x_{p-1},y_{q-1}) & (x_p,y_{q-1}) \\ (x_1,y_q) & (x_2,y_q) & \dots & (x_{p-1},y_q) & (x_p,y_q) \end{bmatrix}$$

给定每个位置的状态，计算探测车的最优移动方案，使到达传送器的探测车的数量最多，而且探测车采集到的岩石标本的数量最多。

inputFormat:
第一行为探测车数 $n$，接下来两行分别为 $p,q$。

接下来的 $q$ 行是表示登陆舱与传送器之间的位置状态的 $p \times q$ 网格。
用三种数表示火星表面位置的状态：$0$ 表示平坦无障碍，$1$ 表示障碍，$2$ 表示石块。

outputFormat: 每行包含探测车号和一个移动方向，$0$ 表示向南移动，$1$ 表示向东移动。

hint:
【数据范围】
对于 $100\%$ 的数据，$1 \le n,p,q \le 35$。

tags: 网络流与线性规划 24 题


title: 最长k可重线段集问题

description:
给定平面 $x-O-y$ 上 $n$ 个开线段组成的集合 $I$，和一个正整数 $k$ 。试设计一个算法，从开线段集合 $I$ 中选取出开线段集合 $S\subseteq I$ ,使得在 $x$ 轴上的任何一点 $p$，$S$ 中与直线 $x=p$ 相交的开线段个数不超过 $k$，且$\sum\limits_{z\in S}|z|$达到最大。这样的集合 $S$ 称为开线段集合 $I$ 的最长  $k$ 可重线段集。$\sum\limits_{z\in S}|z|$ 称为最长  $k$ 可重线段集的长度。

对于任何开线段 $z$，设其断点坐标为 $(x_0,y_0)$ 和 $(x_1,y_1)$，则开线段 $z$ 的长度 $|z|$ 定义为：
$$|z|=\lfloor\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}\rfloor$$

对于给定的开线段集合 $I$ 和正整数 $k$，计算开线段集合 $I$ 的最长 $k$ 可重线段集的长度。

inputFormat:
文件的第一 行有 $2$ 个正整数 $n$ 和 $k$，分别表示开线段的个数和开线段的可重叠数。

接下来的 $n$ 行，每行有 $4$ 个整数，表示开线段的 $2$ 个端点坐标。

outputFormat: 程序运行结束时，输出计算出的最长 $k$ 可重线段集的长度。

hint: $1\leq n\leq 500$，$1 \leq k \leq 13$，坐标值在 `int` 范围内。

tags: 网络流与线性规划 24 题


title: 最长k可重区间集问题

description:
给定实直线 $\text{L}$ 上 $n$ 个开区间组成的集合 $\mathbf{I}$，和一个正整数 $k$，试设计一个算法，从开区间集合 $\mathbf{I}$ 中选取出开区间集合 $\mathbf{S}\subseteq\mathbf{I}$，使得在实直线 $\text{L}$ 上的任意一点 $x$，$\text{S}$ 中包含 $x$ 的开区间个数不超过 $k$，且 $\sum_{z\in\text{S}}\lvert z\rvert$ 达到最大（$\lvert z\rvert$ 表示开区间 $z$ 的长度）。

这样的集合 $\mathbf{S}$ 称为开区间集合 $\mathbf{I}$ 的最长 $k$ 可重区间集。$\sum_{z\in\text{S}}\lvert z\rvert$ 称为最长 $k$ 可重区间集的长度。

对于给定的开区间集合 $\mathbf{I}$ 和正整数 $k$，计算开区间集合 $\mathbf{I}$ 的最长 $k$ 可重区间集的长度。

inputFormat: 输入的第一行有 $2$ 个正整数 $n$ 和 $k$，分别表示开区间的个数和开区间的可重叠数。接下来的 $n$ 行，每行有 $2$ 个整数，表示开区间的左右端点坐标 $l,r$，数据保证 $l<r$。

outputFormat: 输出最长 $k$ 可重区间集的长度。

tags: 网络流与线性规划 24 题


title: 涂条纹

description:
只要一个由 $N \times M$ 个小方块组成的旗帜符合如下规则，就是合法的图案。

- 从最上方若干行（至少一行）的格子全部是白色的；
- 接下来若干行（至少一行）的格子全部是蓝色的；
- 剩下的行（至少一行）全部是红色的；

现有一个棋盘状的布，分成了 $N$ 行 $M$ 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成合法图案，方法是在一些格子上涂颜料，盖住之前的颜色。

小 A 很懒，希望涂最少的格子，使这块布成为一个合法的图案。

inputFormat:
第一行是两个整数 $N,M$。

接下来 $N$ 行是一个矩阵，矩阵的每一个小方块是 `W`（白），`B`（蓝），`R`（红）中的一个。

outputFormat: 一个整数，表示至少需要涂多少块。

hint:
### 样例解释

目标状态是：

```plain
WWWWW
BBBBB
RRRRR
RRRRR
```
一共需要改 $11$ 个格子。

### 数据范围

对于 $100\%$ 的数据，$N,M \leq 50$。


title: 散步

description:
一条道路上，位置点用整数 $A$ 表示。

当 $A=0$ 时，有一个王宫。当 $A>0$，就是离王宫的东边有 $A$ 米，当 $A<0$，就是离王宫的西边有 $-A$ 米。

道路上，有 $N$ 个住宅从西向东用 $1\sim N$ 来标号。每个住宅有一个人。住宅只会存在于偶数整数点。

该国国王认为，国民体质下降，必须要多运动，于是下命令所有人都必须出门散步。所有的国民，一秒钟可以走 $1$ 米。每个国民各自向东或者向西走。这些方向你是知道的。命令发出后所有人同时离开家门开始散步。

然而该国的国民个都很健谈，如果在散步途中两个人相遇，就会停下来交谈。正在走路的人碰到已经停下来的人（重合）也会停下来交谈。一但停下来，就会聊到天昏地暗，忘记了散步。

现在命令已经发出了 $T$ 秒，该国有 $Q$ 个重要人物，国王希望能够把握他们的位置。你能帮他解答吗？

inputFormat:
第一行是 $3$ 个整数，$N,T,Q$

接下来 $N$ 行，每行两个整数 $A_i,R_i$。$A_i$ 是家的坐标，如果 $R_i$ 是 $1$，那么会向东走，如果是 $2$，向西。数据保证 $A_i$ 是升序排序，而且不会有两个人初始位置重合。

接下来 $Q$ 行，每行一个整数，表示国王关心的重要人物。

outputFormat: $Q$ 行，每行一个整数，表示这个人的坐标。


title: 逃离僵尸岛

description:
小 a 住的国家被僵尸侵略了！小 a 打算逃离到该国唯一的国际空港逃出这个国家。

该国有 $N$ 个城市，城市之间有道路相连。一共有 $M$ 条双向道路。保证没有自环和重边。

其中 $K$ 个城市已经被僵尸控制了，如果贸然闯入就会被感染 TAT...所以不能进入。由其中任意城市经过不超过 $S$ 条道路就可以到达的别的城市，就是危险城市。换句话说只要某个城市到任意被僵尸控制的城市距离不超过 $S$，就是危险的。

小 a 住在 $1$ 号城市，国际空港在 $N$ 号城市，这两座城市没有被侵略。小a走每一段道路（从一个城市直接到达另外一个城市）得花一整个白天，所以晚上要住旅店。安全的的城市旅馆比较便宜要 $P$ 元，而被危险的城市，旅馆要进行安保措施，所以会变贵，为 $Q$ 元。所有危险的城市的住宿价格一样，安全的城市也是。在 $1$ 号城市和 $N$ 城市，不需要住店。

小 a 比较抠门，所以他希望知道从 $1$ 号城市到 $N$ 号城市所需要的最小花费。

输入数据保证存在路径，可以成功逃离。输入数据保证他可以逃离成功。

inputFormat:
第一行 4 个整数 $N,M,K,S$。

第二行两个整数 $P,Q$。

接下来 $K$ 行，每行一个整数 $c_i$，表示僵尸侵占的城市编号。

接下来 $M$ 行，$a_i,b_i$，表示一条无向边。

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


title: 改造二叉树

background:
勤奋又善于思考的小L接触了信息学竞赛，开始的学习十分顺利。但是，小L对数据结构的掌握实在十分渣渣。

所以，小L当时卡在了二叉树。

description:
在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p，若其存在左孩子lch，则key[p]>key[lch]；若其存在右孩子rch，则key[p]<key[rch]；注意，本题中的二叉搜索树应满足对于所有结点，其左子树中的key小于当前结点的key，其右子树中的key大于当前结点的key。（因为小L十分喜欢装xx，所以这里他十分装xx的给大家介绍了什么是二叉树和二叉搜索树）。

可是善于思考的小L不甘于只学习这些基础的东西。他思考了这样一个问题：现在给定一棵二叉树，可以任意修改结点的数值。修改一个结点的数值算作一次修改，且这个结点不能再被修改。若要将其变成一棵二叉搜索树，且任意时刻结点的数值必须是整数（可以是负整数或0），所要的最少修改次数。

这一定难不倒聪明的你吧！如果你能帮小L解决这个问题，也许他会把最后的资产分给你1/16哦！

inputFormat:
第一行一个正整数n表示二叉树节点数。

第二行n个正整数用空格分隔开，第i个数ai表示结点i的原始数值。

此后n - 1行每行两个非负整数fa, ch，第i + 2行描述结点i + 1的父亲编号fa，以及父子关系ch，(ch = 0 表示i + 1为左儿子，ch = 1表示i + 1为右儿子)。

为了让你稍微减轻些负担，小L规定：结点1一定是二叉树的根哦！

outputFormat: 仅一行包含一个整数，表示最少的修改次数


title: 牛场围栏

background:
小L通过泥萌的帮助，成功解决了二叉树的修改问题，并因此写了一篇论文，

成功保送了叉院（羡慕不？）。勤奋又勤思的他在研究生时期成功转系，考入了北京大学光华管理学院！毕业后，凭着自己积累下的浓厚经济学与计算机学的基础，成功建设了一个现代化奶牛场！

description:
奶牛们十分聪明,于是在牛场建围栏时打算和小L斗智斗勇！小L有N种可以建造围栏的木料，长度分别是l1,l2 … lN，每种长度的木料无限。

修建时，他将把所有选中的木料拼接在一起，因此围栏的长度就是他使用的木料长度之和。但是聪明的小L很快发现很多长度都是不能由这些木料长度相加得到的，于是决定在必要的时候把这些木料砍掉一部分以后再使用。

不过由于小L比较节约，他给自己规定：任何一根木料最多只能削短M米。当然，每根木料削去的木料长度不需要都一样。不过由于测量工具太原始，小L只能准确的削去整数米的木料，因此，如果他有两种长度分别是7和11的木料，每根最多只能砍掉1米，那么实际上就有4种可以使用的木料长度，分别是6， 7，10, 11。

因为小L相信自己的奶牛举世无双，于是让他们自己设计围栏。奶牛们不愿意自己和同伴在游戏时受到围栏的限制，于是想刁难一下小L，希望小L的木料无论经过怎样的加工，长度之和都不可能得到他们设计的围栏总长度。不过小L知道，如果围栏的长度太小，小L很快就能发现它是不能修建好的。因此她希望得到你的帮助，找出无法修建的最大围栏长度。

这一定难不倒聪明的你吧！如果你能帮小L解决这个问题，也许他会把最后的资产分给你1/8哦！

inputFormat: 输入的第一行包含两个整数N,  M，分别表示木料的种类和每根木料削去的最大值。以下各行每行一个整数li(1< li< 3000),表示第i根木料的原始长度。

outputFormat: 输出仅一行，包含一个整数，表示不能修建的最大围栏长度。如果任何长度的围栏都可以修建或者这个最大值不存在，输出-1。


title: 珍珠项链

background:
小L通过泥萌的帮助，成功解决了牛栏的修建问题。奶牛们觉得主人非常厉害，于是再也不敢偷懒，母牛们奋力挤奶，生娃。子子孙孙无穷匮也！小L于是成为了一代富豪！

但是一直困扰小L的就是单身问题！小L经过长久的寻觅，小L终于找到了一个心仪的漂亮妹子。于是，小L打算在520那天给妹子一个惊喜！（虽然小L很节约，但是对妹子还是很阔绰的！）

description:
小L决定用K种珍珠为妹子做一串举世无双的珍珠垂饰。珍珠垂饰是由珍珠连接而成的，其长度可以认为就是珍珠垂饰上珍珠的个数。小L现在腰缠万贯，每种珍珠他都拥有N颗。根据将珍珠垂饰打开后珍珠不同的排列顺序可以区别不同种类的项链。现在，小L好奇自己可以组成多少种长度为1至N的不同的珍珠垂饰？当然，为显富有，每串珍珠垂饰都要必须由K种珍珠连成。 答案取模1234567891。

这一定难不倒聪明的你吧！如果你能帮小L解决这个问题，也许他会把最后的资产分给你1/4哦！

inputFormat: 输入包含多组数据。第一行是一个整数T，表示测试数据的个数。每组数据占一行，包含两个整数N和K，用一个空格隔开。

outputFormat: 每组数据输出仅一行，包含一个整数，表示项链的种类数。


title: 改造异或树

description: 给定一棵n 个点的树，每条边上都有一个权值。现在按顺序删掉所有的n-1条边，每删掉一条边询问当前有多少条路径满足路径上所有边权值异或和为0。

inputFormat:
第一行一个整数n。

接下来n-1 行，每行三个整数ai，bi， zi，满足1<= ai， bi <=n，表示树上编号为ai 的点和编号为bi 的点中间连有一条权值为zi 的边。

接下来一行n-1 个整数，两两之间有一个空格隔开，表示一个1~ n- 1 的排列，表示n - 1 条边的删边顺序。

outputFormat: 输出n 行，每行一个整数，依次表示删掉第0~  n - 1 条边之后的边权异或和为零的路径数。

hint:
对于20% 数据，满足n  <= 1000。

对于另外30% 数据，满足所有的zi = 0。

对于全部数据，满足n <=10^5，0<= zi<= 10^9。


title: 逛庙会

background: 本题时限3s，请考虑常数优化或者读入优化。（std没有特别进行优化）

description:
城市里正在举行庙会。庙会里有很多摊位。庙会的会场是一个南北向H个摊位、东西向W个摊位组成的大型方阵。从北开始第i行、西开始第j列的一个摊位，我们表示为(i,j)。

正妹现在处于庙会的(1,1)位置，然后要往东或者往南走，一直走到(H,W)跟小 B 汇合。(1,1)点和(H,W)和它们的东西南北邻近一个摊位都没有开张。别的地方也可能有一些摊位没有开张。

正妹是个吃货。只要到达一个摊位，总是经不起小吃的诱惑。如果这个摊位开张了，而且该摊位小吃还没有买过，就会买下这个摊位的小吃。无论这个摊位是否有开张，其东西南北直接相邻的摊位小吃的香味也很诱人，如果邻近的摊位的小吃没有买过，那么就在这些邻近（上下左右）的且没有买过的摊位（假设有r个）中，买其中的r-1个摊位的小吃。然后继续往东或者南走。同一家小摊，不会购买多次。

虽然正妹是个吃货，但是零用钱还是很有限。可是她又是管不住自己，就是要买买买。所以她希望知道自己最少能吃掉多少钱的东西。

inputFormat:
第一行2个数，H，W

接下来H行，每行W个字符串，**没有空格隔开**，是1-9或者'.'中的一个，表示价格，一个点表示没有开张。

outputFormat: 一个整数，表示最少花掉的钱

hint:
```cpp
样例解释：o为正妹经过的路线，x为她顺便买的小吃。当走到(2,4)时，左下右都有开张且没有买过的摊位，于是买左和右，继续沿着路线走。由于之后路线没有经过没有买过摊位，而且上下左右开张且没买过的摊位不超过1，所以一个都不买了。
5 5
oooo7
.2xoo
9346o
..45o
.8..o
```
20%数据，开张的摊位不超过20

100%数据， (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000)

特别注意：数据是在windows生成，输入数据换行符可能是“\r\n”（两个字符）或者"\n"。而评测机是linux。请特别注意。不接受赛后以“本地能过，评测wa”的理由申诉。

参考读入方式（节选自std）：

```cpp
    for (i = 0; i < H; ++i) {
        scanf("%s", in);
        for (j = 0; j < W; ++j) {
            shop[i][j] = blabla..
        }
    }
```


title: [USACO16DEC] Cities and States S

description:
Farmer John 有若干头奶牛。为了训练奶牛们的智力，Farmer John 在谷仓的墙上放了一张美国地图。地图上表明了每个城市及其所在州的代码（前两位大写字母）。

由于奶牛在谷仓里花了很多时间看这张地图，他们开始注意到一些奇怪的关系。例如，FLINT 的前两个字母就是 MIAMI 所在的 `FL` 州，MIAMI 的前两个字母则是 FLINT 所在的 `MI` 州。
确切地说，对于两个城市，它们的前两个字母互为对方所在州的名称。

我们称两个城市是一个一对「特殊」的城市，如果他们具有上面的特性，并且来自不同的州。对于总共 $N$ 座城市，奶牛想知道有多少对「特殊」的城市存在。请帮助他们解决这个有趣的地理难题！

inputFormat:
输入共 $N + 1$ 行。

第一行一个正整数 $N$，表示地图上的城市的个数。
接下来 $N$ 行，每行两个字符串，分别表示一个城市的名称（$2 \sim 10$ 个大写字母）和所在州的代码（$2$ 个大写字母）。同一个州内不会有两个同名的城市。

outputFormat: 输出共一行一个整数，代表特殊的城市对数。

samples:
6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL

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

对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10 ^ 5$，城市名称长度不超过 $10$。


title: 偷天换日

background: 神偷对艺术馆内的名画垂涎欲滴准备大捞一把。

description:
艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。

每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是要耗费时间的。

警察会在 $n$ 秒后到达进口，在不被逮捕的情况下你最多能得到的价值。

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

inputFormat:
第一行一个整数 $n (n \leq 600)$。

第二行若干组整数，对于每组整数 $(t,x)$，$t$ 表示进入这个展览厅或经过走廊要耗费 $t$ 秒的时间，若 $x>0$ 表示走廊通向的展览厅内有 $x$ 幅画。

接下来 $x$ 对整数 $(w,c)$ 表示偷一幅价值为 $w$ 的画需要 $c$ 秒的时间。若 $x=0$ 表示走廊一分为二。$t,c \leq 5;x \leq 30$。

输入是按深度优先给出的。房间和走廊数不超过 $300$ 个。

outputFormat: 仅一个整数，表示能获得的最大价值。

hint: 来源：改编


title: 【模板】文艺平衡树

description:
您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。

inputFormat:
第一行两个正整数 $n,m$，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$。
接下来 $m$ 行，每行两个正整数 $l,r$，表示翻转的区间。

outputFormat: 输出一行 $n$ 个正整数，表示原始序列经过 $m$ 次变换后的结果。

hint:
【数据范围】
对于 $100\%$ 的数据，$1 \le n, m \leq 100000 $，$1 \le l \le r \le n$。


title: 仓鼠找 sugar

description:
小仓鼠的和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 $1\sim n$。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（$a$）到餐厅（$b$），而他的基友同时要从他的卧室（$c$）到图书馆（$d$）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被 zzq 大爷虐，请你快来救救他吧！

inputFormat:
第一行两个正整数 $n$ 和 $q$，表示这棵树节点的个数和询问的个数。

接下来 $n-1$ 行，每行两个正整数 $u$ 和 $v$，表示节点 $u$ 到节点 $v$ 之间有一条边。

接下来 $q$ 行，每行四个正整数 $a$、$b$、$c$ 和 $d$，表示节点编号，也就是一次询问，其意义如上。

outputFormat: 对于每个询问，如果有公共点，输出大写字母 `Y`；否则输出`N`。

hint:
**本题时限 1s，内存限制 128M，因新评测机速度较为接近 NOIP 评测机速度，请注意常数问题带来的影响。**

$20\%$ 的数据 $n, q\le200$。

$40\%$ 的数据 $n, q\le 2\times10^3$。

$70\%$ 的数据 $n, q\le 5\times10^4$。

$100\%$ 的数据 $1\le n, q\le10^5$。


title: yyy棋 II

background:
本题是提交答案题，所有测试数据的输入均开放下载。选手需要提供输出数据。洛谷评测机会根据提交的数据来评分。

输入数据和windows的checker

http://pan.baidu.com/s/1jHU2UwQ

linux的checker

http://pan.baidu.com/s/1nv8Yuy1

#udp1：所有答案文件末尾必须有且只有一个回车

description:
我们的英明的yyy某日无聊，发(chao)明(xi)了一款风靡世界的游戏。为了纪念这个伟大的发明，自己起名为“yyy棋”（kkk：喂！P2361已经叫做yyy棋了这个是smg？）

在其中的一种情况下棋盘是长这样的：

```cpp
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ
．．．．．．．
．．．．．．．
．．．．．．．
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ
```
这种情况下一个7\*7的棋盘，‘.’上可以走棋，而‘x’上不能。只有1种棋子，我们假设是‘Y’。

最开始的初始棋子和障碍都是系统给定的。我们假设是这个样子：

```cpp
ｘｘ．．．ｘｘ
ｘｘ．Ｙ．ｘｘ
．．．Ｙ．．．
．．．．．．．
．．．．．．．
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ
```
走棋的规则很简单。任意一个棋子可以而且仅可以跳过它相邻的上下左右的一颗棋子而移动两格，而且目的地没有棋子且不是'x'。跳过之后，被跳的那个棋子就会消失。所以像刚刚给出的的那个，我们可以将上方的一个棋子跳到下方，然后就成了这样：

```cpp
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ
．．．．．．．
．．．Ｙ．．．
．．．．．．．
ｘｘ．．．ｘｘ
ｘｘ．．．ｘｘ
```
我们的目标是通过一系列运♂动，消除尽可能多的棋子。希望最后可以只留下一个棋子。由于yyy有强迫症，他还希望最后的这一个棋子能够停留在**Zhong央**。

inputFormat:
所有输入数据 yyychess1.in~yyychess10.in ，分别对应 10 个任务。

对于每一个任务：

第一行一个整数N，表示棋盘的大小。

为了方便选手，我们定义坐标(i,j)为第i行第j列。

接下来一行，一个自然数M。

- 如果M=0，那么

接下来是N\*N的矩阵序列。我们用x表示不可走的地方，o表示可以走但是没有放棋的地方，y表示放棋的地方。每个字符不用空格隔开。

- 如果M>0，那么

接下来是M行，每行两个数字，依次表示每个棋子的坐标。这种情况下，没有障碍点。

outputFormat:
输出若干行，表示走法。

对于每一行，输出两个数字和一个字母。两个数字代表(i,j)也就是棋子的坐标，剩下的一个字母是UDLR中的一个，分别表示上下左右跳。

samples:
7
0
xxoooxx
xxoyoxx
oooyooo
ooooooo
ooooooo
xxoooxx
xxoooxx

hint:
样例解释

两个样例描述的是同一个棋盘，只是第二个没有障碍点。

第一个样例输出，可以拿100%的分数。

第二个样例输出，只能拿90%的分数，因为最后没有在中心$(\frac{n+1}{2},\frac{n+1}{2})$

评分标准：

当你的答案是合法的，并且最后只剩下一个棋子，而且这个棋子在最中心，得该点100%的分数。

当你的答案是合法的，并且最后只剩下一个棋子，而且这个棋子不在最中心，得该点90%的分数。

当你的答案是合法的，并且最后剩下2个，3个，4/5个棋子，分别得该点80%，60%，40%的分数。

除此之外，包括有非法的走法以及剩下超过5个棋子的，该点不得分。

压缩文件提供checker.exe可供预先使用。

方法：

所有文件解压，在命令行中输入checker.exe yyychess1.in youranswer.txt youranswer.txt (最后两个是你的输出文件，请输入两次)

就会告诉你结果。


title: 于是他错误的点名开始了

background:
XS中学化学竞赛组教练是一个酷爱炉石的人。

他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛 CON900）。

description: 这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）

inputFormat:
第一行一个整数 $n$，表示班上人数。

接下来 $n$ 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 $50$）。

第 $n+2$ 行一个整数 $m$，表示教练报的名字个数。

接下来 $m$ 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 $50$）。

outputFormat:
对于每个教练报的名字，输出一行。

如果该名字正确且是第一次出现，输出 `OK`，如果该名字错误，输出 `WRONG`，如果该名字正确但不是第一次出现，输出 `REPEAT`。


title: 富金森林公园

description:
博艾的富金森林公园里有一个长长的富金山脉，山脉是由一块块巨石并列构成的，编号从 $1$ 到 $N$ 。每一个巨石有一个海拔高度。而这个山脉又在一个盆地中，盆地里可能会积水，积水也有一个海拔高度，所有**严格低于**这个海拔高度的巨石，就会在水面下隐藏。

由于地壳运动，巨石的海拔高度可能会随时变化，每次一块的巨石会变成新的海拔高度。当然，水面的高度也会随时发生变化。

因为有这样奇妙的地质奇观，吸引了很多游客来游玩。uim 作为一个游客，可以告诉你此时水位海拔，你得告诉他，能看到有几个连续露出水面的部分。（与水面持平我们也认为是露出）

inputFormat:
第一行两个整数 $N$ 和 $M$,分别表示 $N$ 块石头，$M$ 个询问。

接下来一行，$N$ 个整数 $A_i$ 表示每个巨石的初始海拔。

接下来 $M$ 行，每行有两个或者三个数，每一行如果第一个数是 `1`，那么后面跟一个 $B_j$，表示水面海拔。如果第一个数是 `2`，后面跟两个整数，$C_j$ 和 $D_j$，表示编号 $C_j$ 的巨石海拔变为 $D_j$。

outputFormat: 对于每个 `1` 询问，给出一个整数答案，也就是露出了几部分的山峰。


title: 值日班长值周班长

description: 话说，在一个学期共有 $n$ 个值日班长，其中 A 是第 $m$ 个值日班长，共有 $p$ 个值周班长，B是第 $q$ 个值周班长。假设不考虑假期及其他额外上课休假，以及重排值日班长值周班长，即永远每周上 $5$ 天休息 $2$ 天，且这个学期永远不会结束。请问这学期第几天会第一次遇上 $A$ 是值日班长且 $B$ 是值周班长，若永远不会输出 `Orz mgh!!!`。

inputFormat: 有多组测试数据。每组数据占 $1$ 行四个数$n,m,p,q$。保证 $m\le n$，$q\le p$。

outputFormat: 每组数据输出 $1$ 行表示结果


title: 恋爱

description:
小 A 爱上了小 B！！！可是小 A 相对小 B 太弱，所以她当然不会同意小 A 的请求。小 A 苦苦追求，最终小 B 就提这样的条件：

- 小 B 有 $n$ 个下属（不包括小 B）组成了树状结构，小 B 在顶端，其他人都有一个直属上司。
- 小 B 编号 $0$，其他人编号 $1 \sim n$。
- 对于第 $i$ 人，如果这个人没有下属，那么小 A 可以给他 $A_i$ 元钱，则他会向他的直属上司写一封信，表示小 A 向小 B 求爱；
- 如果他的直属下属有占比不小于 $\dfrac{A_i}{T}$ 的人写信表示小 A 向小 B 求爱，那么他也会向他的直属上司写一封信，表示小 A 向小 B 求爱。
- 如果小 B 的直属下属有占比不小于 $\dfrac{C}{T}$ 的人写信表示小 A 向小 B 求爱，那么她会同意小 A 的请求。

请问小 A 至少需要给多少钱才会让小 B 同意小 A 的求爱。

inputFormat:
第一行三个整数 $n, T, C$。

然后 $n$ 行，第 $i$ 行两个整数 $B_i, A_i$，$B_i$ 表示 $i$ 的直属上司，保证 $B_i < i$。

outputFormat: 需要给的钱数。


title: 拍照

description:
小 B 有 $N$ 个下属，现小 B 要带着一些下属让别人拍照。

有 $M$ 个人，每个人都愿意付给小B一定钱来和 $N$ 个下属中的一些人进行合影。如果这一些下属没带齐那么就不能拍照，小B也不会得到钱。

注意：带下属不是白带的！！！对于每个下属，如果他带了那么小B需要给他一些钱，保证当他拍照时配合。

inputFormat: 第 $1$ 行有 $2$ 个正整数 $M$ 和 $N$（$0<M,N\le 100$）。接下来的 $M$ 行，每行是一个要求拍照的人的有关数据。第一个数是他同意支付该合影的费用；接着是该合影需要的若干下属的编号，以一个 $0$ 作为行的结束标记。最后一行的 $N$ 个数是带每个下属的费用。

outputFormat: 一个数，表示最大收益。小 B 可以一个人也不带。

hint:
对于 $10\%$ 的数据每个人都要求让全部 $N$ 个人合影。

对于 $30\%$ 的数据 $N\le15,M\le 15$。

另有 $10\%$ 的数据答案为 $0$。

对于 $50\%$ 的数据 $N\le 40,M\le 40$。

另有 $10\%$ 的数据每个人只愿意拍一个人。

对于 $100\%$ 的数据 $M,N\le100$。


title: 有机化学之神偶尔会做作弊

background:
XS 中学化学竞赛组教练是一个酷爱炉石的人。

有一天他一边搓炉石一边监考，而你作为一个信息竞赛的大神也来凑热闹。

然而你的化竞基友却向你求助了。

“第 1354 题怎么做？”<--手语  他问道。

description:
你翻到那一题：给定一个烃，只含有单键（给初中生的一个理解性解释：就是一堆碳用横线连起来，横线都是单条的）。

然后炎魔之王拉格纳罗斯用他的火焰净化了一切环（？？？）。所有的环状碳都变成了一个碳，如图所示。

![环状碳变为一个碳](https://cdn.luogu.com.cn/upload/pic/2758.png)

然后指定多组碳，求出它们之间总共有多少碳，如图所示（和上图没有关系）。

![求出有多少碳](https://cdn.luogu.com.cn/upload/pic/2759.png)

但是因为在考试，所以你只能把这个答案用手语告诉你的基友。你决定用二进制来表示最后的答案，如图所示（不要在意，和题目没有什么没关系）。

![二进制手语](https://cdn.luogu.com.cn/upload/pic/2760.png)

### 题意简述

给你一个 $n$ 个点，$m$ 条边的无向图。把图中所有的环变为一个点，求变化后某两个点之间有多少个点。

inputFormat:
第一行两个整数 $n$，$m$。表示有 $n$ 个点，$m$ 根键。

接下来 $m$ 行每行两个整数 $u$，$v$ 表示 $u$ 号碳和 $v$ 号碳有一根键。

接下来一个整数 $tot$ 表示询问次数。

接下来 $tot$ 行每行两个整数，$a$，$b$ 表示询问的两个碳的编号。

outputFormat: 共 $tot$ 行，每行一个二进制数，表示答案。

hint:
两个碳不成环。

## 数据范围及约定

对于 $100\%$ 的数据，$1<n\le10 ^ 4$，$1<m\le5\times 10 ^ 4$。


title: 如厕计划

description:
竞赛比完之后，水箱里充满水的选手们鱼贯而出。凡华中学的厕所规划的很糟，只有两个厕位，于是厕所门前排起了长长的队伍。

厕所有两个，一个是女生专用厕所，另一个是男女混用厕所。**一共有2N个选手正在排队**，男女生数量可能不同。如果队头的是妹子，只要某个厕所是空的就可以进入，但是如果两个厕所都是空的，那么优先进入女性专用厕所。而如果队头是个绅♂士，只有在男女混用厕所是空的时候才能使用；如果只有女性专用厕所是空的，那么队伍中最靠前的妹子就可以不用继续等直接如厕。我们假设所有人如厕都需要花1分钟，不考虑切换的时间。

然而，**N分钟后，就要开饭了，所有人必须如厕完**，不过看样子似乎来不及。主办方可以重新调换顺序，不过有些人会因为新的顺序中自己更加后面了而感到不满，不满度是自己相比于原队列后退了几个顺序（除此之外跟自己的实际如厕顺序无关）。

主办方发现了这一点，所以希望你帮助他们解决这个问题，设计出一种方案，对于其中不满意度最大的学生，尽可能让他的不满意度最小。你只需要告诉他门最不满意的学生的不满意度是多少。

inputFormat:
由于人相当多，我们用几段字符串来描述这个队列。

第一行一个整数N

第二行一个整数M

接下来M行，有一个字符串Si和一个整数Ki构成，中间有空格隔开，字符串中只有'M'（男）和'F'（女）。最后的字符串就是 S1拼接K1次+ S2拼接K2次+ ... +SM拼接KM次

outputFormat: 输出一个整数，表示答案。如果无论怎么样都没办法N分钟之内达成，请输出-1

hint:
原队列是FFFMMMMMFF

改进后的队列是FMMFFMMMFF

所以厕所会按照下面的时间使用：

```cpp
分钟 1   2   3   4   5
共用 2   3   6   7   8
女用 1   4   5   9   10
```
两个妹子往后面移动了2位，所以不满意度是2

20% N<=10;M=1;K1=1

40% N<=100000;M=1;K1=1

100% 1<=N,Ki<=10^18;1<=M<=100000;所有Si字符串长度之和不超过200000


title: Y的积木

background: Y 是个大建筑师，他总能用最简单的积木拼出最有创意的造型。

description: Y 手上有 $n$ 盒积木，每个积木有个重量。现在他想从每盒积木中拿一块积木，放在一起，这一堆积木的重量为每块积木的重量和。现在他想知道重量和最小的 $k$ 种取法的重量分别是多少。（只要任意更换一块积木，就视为一种不同的取法。如果多种取法重量总和一样，我们需要输出多次。）

inputFormat:
第一行输入两个整数，$n,k$，意义如题目所描述。

每组数据接下来的 $n$ 行，第一个整数为 $m_i$，表示第 $i$ 盒积木的数量，在同一行有 $m_i$ 个整数，分别表示每个积木的重量。

outputFormat: 一行，重量最小的 $k$ 种取法的重量，要求对于每个数据，从小到大输出。

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

- 对于 $30\%$ 的数据，$2 \le m_i \le 10$，$1 \le n \le 10$。
- 对于 $50\%$ 的数据，$2 \le m_i \le 50$，$1 \le n \le 50$。
- 对于 $100\%$ 的数据，$2 \le m_i \le 100$，$1 \le n \le 100$，$1 \le k \le 10^4$，每个积木的重量为不超过 $100$ 的正整数，所有 $m_i$ 的积大于等于 $k$。

本题不卡常。


title: 宋荣子搭积木

description: saruka 非常喜欢搭积木，他一共有 $n$ 块积木。而且 saruka 的积木很特殊，只能一块块的竖着摞，可以摞很多列。说过 saruka 的是特殊的积木了，这些积木都非常智能，第 $i$ 块积木有一个情绪值 $x_i$ ，当摞在这块积木上的积木总数超过 $x_i$ 时，这块积木就会很不高兴，发誓以后不会再和 saruka 一起玩耍了。saruka 这么爱玩积木，肯定不会让积木不高兴的，但是 saruka 又希望每块积木都被用上，并且摞的积木列数最少。你能来帮帮 saruka 吗?

inputFormat:
第一行一个整数 $n$，含义如题目描述所示，

第二行有 $n$ 个数 $x_i$，含义如题目描述所示。

outputFormat: 输出一个数字，代表最小的积木列数。


title: 宋荣子的城堡

description:
saruka 有一座大大的城堡！城堡里面有 $n$ 个房间，每个房间上面都写着一个数字 $p_i$。有一天，saruka 邀请他的小伙伴 LYL 和 MagHSK 来城堡里玩耍，他们约定，如果某一个人当前站在 $i$ 号房间里，那么下一步他就要去 $p_i$ 号房间，在下一步就要去 $p_{p_i}$ 号房间。

为了增加趣味性，saruka 决定重新书写一下每个房间的 $p_i$，以满足：

- 如果从编号为 $1 \sim k$ 的某个房间走，按照规则走，必须能走回 $1$ 号房间。特别的，如果从 $1$ 号房间开始走，也要走回 $1$ 号房间。（至少走一步，如果 $p_1 = 1$，从 $1$ 走到 $1$ 也算合法）。

- 如果从编号大于 $k$ 的房间开始，按照规则走，一定不能走到 $1$ 号房间。

saruka 想知道，一共有多少书写 $p_i$ 的方案可以满足要求，答案对 $10 ^ 9 + 7$ 取模。

inputFormat: 共一行两个数字 $n,k$，含义如题。

outputFormat: 一个数字，表示合法的方案数。答案对 $10 ^ 9 + 7$ 取模。


title: 小A和uim之大逃离 II

background:
话说上回……还是参见 <https://www.luogu.com.cn/problem/P1373> 吧

小 a 和 uim 再次来到雨林中探险。突然一阵南风吹来，一片乌云从南部天边急涌过来，还伴着一道道闪电，一阵阵雷声。刹那间，狂风大作，乌云布满了天空，紧接着豆大的雨点从天空中打落下来，只见前方出现了一个牛头马面的怪物，低沉着声音说：“呵呵，既然你们来到这，两个都别活了！”。小 a 和他的小伙伴再次惊呆了！

description:
瞬间，地面上出现了一个 $H$ 行 $W$ 列的巨幅矩阵，矩阵的每个格子上要么是空地 `.` 或者障碍 `#`。

他们起点在 $(1,1)$，要逃往 $(H,W)$ 的出口。他们可以一次向上下左右移动一格，这个算一步操作。不过他们还保留着上次冒险时收集的魔液，一口气喝掉后可以瞬移到相对自己位置的 $(D,R)$ 向量；也就是说，原来的位置是 $(x,y)$，然后新的位置是 $(x+D,y+R)$，这个也算一步操作，不过他们仅能至多进行一次这种操作（当然可以不喝魔液）。

这个地方是个是非之地。所以他们希望知道最小能有几步操作可以离开这个鬼地方。不过他们可能逃不出这个鬼地方，遇到这种情况，只能等死，别无他法。

inputFormat:
第一行个整数，$H,W,D,R$，意义在描述已经说明。

接下来 $H$ 行，每行长度是 $W$，仅有 `.` 或者 `#` 的字符串。

outputFormat: 请输出一个整数表示最小的逃出操作次数。如果他们逃不出来，就输出 $-1$。

hint:
样例解释 $1$

$(1,1) \to (1,2)\to (1,3)\to$ 喝魔液 $\to (3,4)\to (3,5)\to (3,6)$。

样例解释 $2$

因为只有一瓶魔液所以他们没办法逃出来。

样例解释 $3$

$D$ 和 $R$ 还可以是 $0$或者负数。

数据范围与约定

$40\%$ 的测试数据 $2\leq H,W\leq 5$。

$70\%$ 的测试数据 $2\leq H,W\leq 100$。

$100\%$ 的测试数据 $2\leq H,W\leq 1000,|D|<H,|R|<W$。


title: 康娜的线段树

description:
小林是个程序媛，不可避免地康娜对这种人类的“魔法”产生了浓厚的兴趣，于是小林开始教她OI。

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

今天康娜学习了一种叫做线段树的神奇魔法，这种魔法可以维护一段区间的信息，是非常厉害的东西。康娜试着写了一棵维护区间和的线段树。由于她不会打标记，因此所有的区间加操作她都是暴力修改的。具体的代码如下：

```cpp
struct Segment_Tree{
#define lson (o<<1)
#define rson (o<<1|1)
    int sumv[N<<2],minv[N<<2];
    inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
    inline void build(int o,int l,int r){
        if(l==r){sumv[o]=a[l];return;}
        int mid=(l+r)>>1;
        build(lson,l,mid);build(rson,mid+1,r);
        pushup(o);
    }
    inline void change(int o,int l,int r,int q,int v){
        if(l==r){sumv[o]+=v;return;}
        int mid=(l+r)>>1;
        if(q<=mid)change(lson,l,mid,q,v);
        else change(rson,mid+1,r,q,v);
        pushup(o);
    }
}T;
```

在修改时，她会这么写：

```cpp
for(int i=l;i<=r;i++)T.change(1,1,n,i,addv);
```
显然，这棵线段树每个节点有一个值，为该节点管辖区间的区间和。

康娜是个爱思考的孩子，于是她突然想到了一个问题：

如果每次在线段树区间加操作做完后，从根节点开始等概率的选择一个子节点进入，直到进入叶子结点为止，将一路经过的节点权值累加，最后能得到的期望值是多少？

康娜每次会给你一个值 $qwq$ ，保证你求出的概率乘上 $qwq$ 是一个整数。

这个问题太简单了，以至于聪明的康娜一下子就秒了。

现在她想问问你，您会不会做这个题呢？

inputFormat:
第一行整数 $n,m,qwq$ 表示线段树维护的原序列的长度，询问次数，分母。

第二行 $n$ 个数，表示原序列。

接下来 $m$ 行，每行三个数 $l,r,x$ 表示对区间$[l,r]$ 加上 $x$

outputFormat: 共 $m$ 行，表示期望的权值和乘上qwq结果。

hint:
对于30%的数据，保证 $1 \leq n,m \leq 100$

对于70%的数据，保证 $1 \leq n,m, \leq 10^{5}$

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

$-1000 \leq a_i,x \leq 1000$


title: 超级玛丽游戏

background:
本题是洛谷的试机题目，可以帮助了解洛谷的使用。

建议完成本题目后继续尝试 [P1001](/problem/P1001)、[P1008](/problem/P1008)。

另外强烈推荐[新用户必读贴](/discuss/show/241461)

description:
超级玛丽是一个非常经典的游戏。请你用字符画的形式输出超级玛丽中的一个场景。

```
                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###            ###
                ...........               #...#          #...#
               ##*#######                 #.#.#          #.#.#
            ####*******######             #.#.#          #.#.#
           ...#***.****.*###....          #...#          #...#
           ....**********##.....           ###            ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################
#...#......#.##...#......#.##...#......#.##------------------#
###########################################------------------#
#..#....#....##..#....#....##..#....#....#####################
##########################################    #----------#
#.....#......##.....#......##.....#......#    #----------#
##########################################    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#
##########################################    ############
```

inputFormat: 无

outputFormat: 如描述


title: AKN’s PPAP

description:
“I have a pen,I have an apple.Eh,Apple-Pen!.

I have a pen,I have pineapple.En,Pineapple-Pen!

Apple-Pen,Pineapple-Pen.Eh,Pen-Pineapple-Apple-Pen!”

Akn最近中毒于一首音乐，于是他买来了一堆苹果来学习这首音乐。Akn发现，只要边唱这首歌，边做把两个完整的苹果碰在一起的动作，两个苹果就会融合成一个新的大苹果，但是大苹果却不能再融合，因为他的细胞内部结构已经改变。Akn还发现，当两个苹果融合的时候，苹果的质量会发生一些玄妙的改变，就是与运算（a&b）。但是，最近他的同学找他要一个苹果吃，akn出于好心，准备把他学习ppap用的苹果融合成的大苹果给同学吃，好让同学一起中毒于ppap，而且akn还想让大苹果的质量最大，那么请问akn能给同学吃的苹果质量最大是多少？

inputFormat:
第一行包含一个整数T，表示数据组数

接下来T组数据，每组数据第一行包含一个整数n，表示n个苹果

第二行包含n个整数wi，表示第i个小苹果重wi kg

outputFormat: 每组数据输出一行一个整数大苹果最大的质量，注意格式，Case #x: ans，case和#间有空格，:和ans之间有空格


title: XOR的艺术

description:
AKN 觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下：

1. 拥有一个伤害串，是一个长度为 $n$ 的只含字符 ``0`` 和字符 ``1`` 的字符串。规定这个字符串的首字符是第一个字符，即下标从 $1$ 开始。
2. 给定一个范围 $[l,~r]$，伤害为伤害串的这个范围内中字符 ``1`` 的个数。
3. 会修改伤害串中的数值，修改的方法是把 $[l,~r]$ 中所有原来的字符 ``0`` 变成 ``1``，将 ``1`` 变成 ``0``。

AKN 想知道一些时刻的伤害，请你帮助他求出这个伤害。

inputFormat:
输入的第一行有两个用空格隔开的整数，分别表示伤害串的长度 $n$，和操作的个数 $m$。

输入第二行是一个长度为 $n$ 的字符串 $S$，代表伤害串。

第 $3$ 到第 $(m + 2)$ 行，每行有三个用空格隔开的整数 $op, l, r$。代表第 $i$ 次操作的方式和区间，规则是：

- 若 $op = 0$，则表示将伤害串的 $[l,~r]$ 区间内的 ``0`` 变成 ``1``，``1`` 变成 ``0``。
- 若 $op = 1$，则表示询问伤害串的 $[l,~r]$ 区间内有多少个字符 ``1``。

outputFormat: 对于每次询问，输出一行一个整数，代表区间内 ``1`` 的个数。

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

原伤害串为 ``1011101001``。

对于第一次操作，改变 $[2,~4]$ 的字符，伤害串变为 ``1100101001``。

对于第二次操作，查询 $[1,~5]$ 内 ``1`` 的个数，共有 $3$ 个。

对于第三次操作，改变 $[3,~7]$ 的字符，伤害串变为 ``1111010001``。

对于第四次操作，查询 $[1,~10]$ 内 ``1`` 的个数，共有 $6$ 个。

对于第五次操作，改变 $[1,~4]$ 的字符，伤害串变为 ``0000010001``。

对于第六次操作，查询 $[2,~6]$ 内 ``1`` 的个数，共有 $1$ 个。

#### 数据范围与约定

对于 $10\%$ 的数据，保证 $n, m \leq 10$。

另有 $30\%$ 的数据，保证 $n, m \leq 2 \times 10^3$。

对于 $100\%$ 的数据，保证 $2 \leq n, m \leq 2 \times 10^5$，$0 \leq op \leq 1$，$1 \leq l \leq r \leq n$，$S$ 中只含字符 ``0`` 和字符 ``1``。


title: 高手过招

description:
AKN 玩游戏玩累了，于是他开始和同伴下棋了，玩的是跳棋！对手是 wwx！这两位上古神遇在一起下棋，使得棋局变得玄幻莫测，高手过招，必有一赢，他们都将用最佳策略下棋，现在给你一个 $n \times 20$ 的棋盘，以及棋盘上有若干个棋子，问谁赢？akn 先手！

游戏规则是这样的：

对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。

inputFormat:
第一行一个 $T$，表示 $T$ 组数据。

每组数据第一行 $n$，表示 $n \times 20$ 的棋盘。

接下来 $n$ 行每行第一个数 $m$ 表示第 $i$ 行有 $m$ 个棋子。

随后跟着 $m$ 个数 $p_j$ 表示第 $i$ 行的棋子布局。

outputFormat: 如果 AKN 能赢，则输出 `YES`，否则输出 `NO`。


title: SAC#1 - Hello World（升级版）

background:
#T1答案要mod1000000007(10^9+7)，请重新提交，非常抱歉！

一天，智障的pipapi正在看某辣鸡讲义学程序设计。

description:
在讲义的某一面，他看见了一篇文章。这篇文章由英文字母（大小写均有）、数字、和空白字符（制表/空格/回车）构成。

pipapi想起了他最近刚刚学会写的Hello World程序。他非常好奇，这篇文章中，“HelloWorld”作为子序列到底出现过多少次呢？

由于papapi是个智障，大小写对于他而言毫无区别；因此，“hEllOWorLD”这样的子序列也是可以接受的。O和W之间的空格是也是可以少的；也就是说，“HelloWorld”是可以的。根据标程的意思，就是没有空格，不用考虑空格的情况。

两个子序列相同当且仅当它们每一个字符所在的位置都相同。

由于答案可能很大，请输出结果对1000000007(10^9+7)的余数。

inputFormat:
输入包含若干行。这些行的内容共同构成一篇文章。

文章以EOF（文件结尾）结束。

outputFormat: 输出仅包含一个整数，表示这篇文章中“Hello World”出现的次数。 d

samples:
Gou Li Guo Jia Sheng Si Yi
Qi Yin Huo Fu Bi Qu Zhi
River can feed people
Also can race boats
Hall Ellen Ok Words locked

hint:
记n为输入的文章的长度（字符数）。

对于20%的数据，n <= 20。

对于50%的数据，n <= 500。

对于所有的数据，15 <= n <= 500000。


title: SAC#1 - ACOJ云评测计划

background:
本题由世界上最蒟蒻最辣鸡最撒比的 SOL 提供。

寂月城网站是完美信息教室的官网。地址：http://191.101.11.174/mgzd 。

description:
ACOJ 的服务器简直是差到了一个令人发指的地步。于是 SAC 的出题人，也就是傻逼 SOL，不得不强制要求每一个通过下载 ACOJ 软件包而搭建的分站，都为主站启动云端评测服务。

云评测服务是由网络来连接的。这样的网络连接是双向的；但是由于地理位置等因素的限制，并不是任意两台服务器都可以直接相连。ACOJ 主站已经得到了可以直连的服务器的表，其中包含 $n$ 个分站（包括主站）以及它们的 $m$ 条连接情况，可以根据这个来分配各个分站的任务。

有一些分站的服主是 SOL 的脑残粉。他们会无条件地将他们的服务器提供给 SOL。这些 ACOJ 分站称作“好站”。但是还有一些分站的服主是 SOL 黑。他们虽然拿到了 ACOJ 的服务端，但是并不愿意为 SOL 提供资源，于是利用黑科技关掉了云服务。也就是说，虽然主站仍然认为这些站点存在，但是它们不会起到任何作用——既不能传递通信，也不能进行评测。它们称作“坏站”。

经过千辛万苦的调查，SOL 确定了 ACOJ 云评测系统中有最多 $k$ 个坏站存在，而且这 $k$ 个坏站似乎会使得 ACOJ 的云网络不再联通！大危机！

但是 SOL 太弱智了，并不能确定是哪 $k$ 个。于是他请你来帮他找出任意一组可能会使得网络不再联通的 $k$ 个站点，以便加强防范。

inputFormat:
输入包含 $m+1$ 行。

第 $1$ 行 $3$ 个整数 $n,m,k$。

接下来 $m$ 行，每行两个整数 $a,b$，表示标号为 $a$ 和 $b$ 的站点可以直接相连。

outputFormat:
输出包含 $1$ 行。

不超过 $k$ 个整数，表示能够将原图割开的任意一组节点组合。

因为使用了 Special Judge，所以节点的顺序并不用担心。只需要满足能够割开原图即可。

如果不存在这样的站点集合，输出 `How oversuspicious you are, SOL!`；如果网络不存在任何坏站时本来就无法连通，输出 `Poor SOL!`。

samples:
4 0 2
Poor SOL!

hint:
对于 $20\%$ 的数据，$n \le 15$；

对于另外 $20\%$ 的数据，$n \le 100$，$k=1$；

对于另外 $20\%$ 的数据，$n \le 100$，$k=2$；

对于 $100\%$ 的数据，$3 \le  n\le 500$，$k \le 3$，$2\le n - k$，云网络不存在自环和重边。


title: 电阻网络

background:
什么是电阻?这个大家应该都知道。什么是电路?大家也应该知道。但是本题当中，电路的定义或许有点不同：

电路都带有正、负极接点，正极在左，负极在右。具体地：电路分为以下几类：

单独的一个1Ω电阻(及其两端的接点)是电路(虽然导线也可以被视为0Ω的电阻，但是单独的导线不是电路)

如果A和B都是电路，设1,2,3是从左到右的三个接点，那么将A的正负极分别接在1与2上，将B的正负极分别接在2与3上，那么1到3的部分是电路，其中1为正极，3为负极。

如果A和B都是电路,设1,2,3,2',3',1’是六个接点，其中1在2和3的左侧，2在2’的左侧，3在3’的左侧，2,和3,在1’的左侧，并且1与2，1与3，2’与1’，3’与1’间均连有导线, 那么将A的正负极分别接在2与2’上，将B的正负极分别接在3与3’上，那么1到1'的部分是电路，其中1为正极，1’为负极。

现在给出一个电路，求它正负极之间的电阻。

description:
Cjwssb最近在物理学科上遇到了难题，他不会计算一个电路中的总电阻，现在他找到了你，希望你能帮助他。

这个电路有如下限定

1、    电路只由导线以及电阻为一欧的电阻组成

2、    保证电路从左到右连接，即每个电阻或导线的两个连接点xy保证x<y

3、    保证接线柱1为电源正极，接线柱n为电源负极

4、    保证每个接线柱只会被串联或者并联两个分支电路或者不接任何电线或电阻

inputFormat:
第一行为两个正整数n,m,分别代表接点数和电阻数。保证编号小的接点在编号大的接点的左侧。

接下来m行，每行三个整数ai,bi,ci，代表这个电阻连接了ai与bi接点，其阻值为ci ，其中ci只可能是0或1，且对于任意的i，保证ai<bi。

outputFormat: 输出一个实数，表示总的电阻值，保留三位小数输出。

hint:
样例解释

画出图来，答案是显然的。

数据规模与约定

对于20%的数据n≤5,m≤5。

对于50%的数据n≤100,m≤120。

对于70%的数据n≤1,000,m≤1200。

对于100%的数据n≤100,000,m≤120000

数据是在人工指定的n下随机生成的，保证答案不会超过10.000。

By：saffah


title: 误会

description:
Cjwssb得到了你的帮助，显得很开心，跟你道谢，你回谢了他。但随后他由于少听了一些词，对你的回谢造成了误会，这使你们两个产生了隔阂，你很不甘心，于是打算告诉他这句话有几种理解方式，以告诉他他误解你了。一句话的理解方式如下

对于一句原句和听到的句子，理解方式是将听到的句子替换掉原句的相同部分，替换成\*，使得原句形成一个新的句子，以达到新的意思，你的任务是统计有多少种意思

inputFormat:
第一行一个整数T，表示T组测试点

每组测试点两个字符串，一个字符串一行，第一行字符串是原句，第二行是听到的句子

outputFormat: 对于每一个测试点，输出一行“Case #x: y”,x表示测试点，y表示答案，由于答案可能很大，你只需要输出答案%1000000007.

samples:
4
hehehe
hehe
woquxizaolehehe
woquxizaole
hehehehe
hehe
owoadiuhzgneninougur
iehiehieh

samples:
Case #1: 3
Case #2: 2
Case #3: 5
Case #4: 1

hint:
在第一个测试点，“ hehehe”有三个理解意思，分别是“\*he”, “he\*”, “hehehe”.

在第三个测试点，“hehehehe”有五个理解意思，分别是“\*hehe”, “he\*he”, “hehe\*”, “**”, “hehehehe”.

对于100%的数据

T <= 30

|A| <= 100000

|B| <= |A|

By：2016 Mul


title: 魔法

description: cjwssb 知道是误会之后，跟你道了歉。你为了逗笑他，准备和他一起开始魔法。不过你的时间不多了，但是更惨的是你还需要完成 $n$ 个魔法任务。假设你当前的时间为 $T$，每个任务需要有一定的限制 $t_i$ 表示只有当你的 $T$ 严格大于 $t_i$ 时你才能完成这个任务，完成任务并不需要消耗时间。当你完成第 $i$ 个任务时，你的时间 $T$ 会加上 $b_i$，此时要保证 $T$ 在任何时刻都大于 $0$，那么请问你是否能完成这 $n$ 个魔法任务，如果可以，输出 $\texttt{+1}\texttt{s}$，如果不行，输出 $\texttt{-1}\texttt{s}$。

inputFormat:
第一行：一个整数 $Z$，表示有 $Z$ 个测试点。

对于每个测试点：

第一行：两个整数 $n,T$，表示有 $n$ 个任务,你一开始有 $T$ 的时间。

接下来 $n$ 行，每行 $2$ 个数字，$t_i$ 与 $b_i$。

outputFormat: 对于每个测试点，输出 $\texttt{+1}\texttt{s}$ 或者 $\texttt{-1}\texttt{s}$。

hint:
对于 $20\%$ 的数据，$n\leq10$；

对于 $100\%$ 的数据，$n\leq10^5,Z\leq10,t_i\leq10^5,T\leq10^5,-10^5\leq b_i\leq 10^5$。

By lantian

$\LaTeX$ By ⚡炭治郎⚡

## 因为历史遗留问题，博客讨论可能无法发出样例输出的字符串，可以考虑使用其他方式规避。


title: SAC E#1 - 一道不可做题 Jelly

background: SOL君（炉石主播）和SOL菌（完美信息教室讲师）是好朋友。

description:
SOL君很喜欢吃蒟蒻果冻。而SOL菌也很喜欢蒟蒻果冻。

有一天，他们在一起搓炉石，而SOL菌则要拿出蒟蒻果冻招待他的客人。

蒟蒻果冻一般在a度下保存在冰箱里。但是刚拿出来的时候太冰了，需要加热。SOL菌打算用一种神奇的电炉加热蒟蒻果冻。根据观察，它有一个特点：

1、蒟蒻果冻小于c度的时候，每p单位时间加热1单位温度；

2、当蒟蒻果冻等于c度的时候，需要q单位时间解冻（大家都知道，晶体物态变化温度不变……SOL君认为果冻属于晶体）；

3、当蒟蒻果冻解冻完成之后，每r单位时间加热1单位温度。

SOL想知道，将果冻加热x单位时间的时候果冻的温度。

温度向下取整，也就是说，如果加热结束时不足p（或q）单位时间，则认为在这最后一小段时间内果冻温度没有任何变化。

inputFormat: 输入仅包含一行，6个整数，依次为a，c，p，q，r，x。

outputFormat: 输出仅包含一个整数：即为所求温度。

hint:
对于 $30\%$ 的数据，$|a|, |c| \leq 200, x \leq 100$。

对于 $60\%$ 的数据，$|a|, |c| \leq 2 \times 10^9, x \leq 100$。

对于 $100\%$ 的数据，$|a|, |c| \leq 2 \times 10^9, 1 \leq x, p, q, r \leq 10^9$。

数据中可能有 $a = c$，此时算还未解冻的状态。

提示：请使用long long数据类型。


title: SAC#1 - 萌数

background:
本题由世界上最蒟蒻的 SOL 提供。

寂月城网站是完美信息教室的官网。地址：<http://191.101.11.174/mgzd>。

description:
蒟蒻 SOL 居然觉得数很萌！

好在在他眼里，并不是所有数都是萌的。只有满足“存在长度至少为 $2$ 的回文子串”的数是萌的——也就是说，$101$ 是萌的，因为 $101$ 本身就是一个回文数；$110$ 是萌的，因为包含回文子串 $11$；但是 $102$ 不是萌的，$1201$ 也不是萌的。

现在 SOL 想知道从 $l$ 到 $r$ 的所有整数中有多少个萌数。

由于答案可能很大，所以只需要输出答案对 $1000000007$（$10^9+7$）的余数。

inputFormat: 输入包含仅 $1$ 行，包含两个整数：$l$，$r$。

outputFormat: 输出仅 $1$ 行，包含一个整数，即为答案。

hint:
记 $n$ 为 $r$ 在 $10$ 进制下的位数。

对于 $10\%$ 的数据，$n \le 3$。

对于 $30\%$ 的数据，$n \le 6$。

对于 $60\%$ 的数据，$n \le 9$。

对于全部的数据，$n \le 1000$，$l < r$。

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

2024/2/4 添加一组 hack 数据。


title: SAC#1 - 组合数

description:
今天小明学习了组合数，现在他很想知道 $\sum \rm{C}$$_{n}^{i}$ 是多少。其中 $\rm{C}$ 是组合数（即 $\rm{C}$$_{n}^{i}$ 表示 $n$ 个物品无顺序选取 $i$ 个的方案数），$i$ 取从 $0$ 到 $n$ 的所有偶数。

由于答案可能很大，请输出答案对 $6662333$ 的余数。

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

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


title: 序列变换

description:
给定一个长度为 $n$ 的数列 $A_i$。

你可以对数列进行若干次操作，每次操作可以从数列中任选一个数，把它移动到数列的开头或者结尾。

求最少经过多少次操作，可以把数列变成单调不减的。“单调不减”意味着数列中的任意一个数都不大于排在它后边的数。

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

第二行是 $n$ 个正整数 $A_i$。

outputFormat: 输出一个整数，表示最少需要的操作次数。


title: 祭坛

background: 在遥远的Dgeak大陆，生活着一种叫做Dar-dzo-nye的怪物。每当这种怪物降临，人们必须整夜对抗怪物而不能安睡。为了乞求这种怪物不再降临，人们决定建造祭坛。

description:
Dgeak大陆可以看成一个用平面直角坐标系表示的巨大平面。在这个平面上，有 n 个Swaryea水晶柱，每个水晶柱可以用一个点表示。

如果 4 个水晶柱依次相连可以构成一个四边形，满足其两条对角线分别平行于 x 轴和 y 轴，并且对角线的交点位于四边形内部（不包括边界），那么这 4 个水晶柱就可以建立一个结界。其中，对角线的交点称作这个结界的中心。

例如下左图中，水晶柱 ABCD 可以建立一个结界，其中心为 O。

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

为了起到抵御Dar-dzo-nye的最佳效果，人们会把祭坛修建在最多层结界的保护中。其中不同层的结界必须有共同的中心，这些结界的边界不能有任何公共点，并且中心处也不能有水晶柱。这里共同中心的结界数量叫做结界的层数。

为了达成这个目的，人们要先利用现有的水晶柱建立若干个结界，然后在某些结界的中心建立祭坛。

例如上右图中，黑色的点表示水晶柱（注意 P 和 O 点不是水晶柱）。祭坛的一个最佳位置为 O 点，可以建立在 3 层结界中，其结界的具体方案见下左图。当然，建立祭坛的最佳位置不一定是唯一，在上右图中，O 点左侧 1 单位的点 P 也可以建立一个在 3 层结界中的祭坛，见下右图。

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

现在人们想知道：

1. 祭坛最佳选址地点所在的结界层数；

2. 祭坛最佳的选址地点共有多少个。

inputFormat:
输入的第一行包含两个正整数 n,表示水晶柱的个数

接下来 n 行，每行包含两个非负整数 x,y，表示每个水晶柱的坐标。保证相同的坐标不会重复出现。

outputFormat:
第一行一个整数，表示祭坛最多可以位于多少个结界的中心

第二行一个整数，表示结界数最多的方案有多少种。


title: 在你窗外闪耀的星星

background:
飞逝的的时光不会模糊我对你的记忆。难以相信从我第一次见到你以来已经过去了 3 年。我仍然还生动地记得，3 年前，在美丽的集美中学，从我看到你微笑着走出教室，你将头向后仰，柔和的晚霞照耀着你玫瑰色的脸颊。我明白，我已经沉醉于你了。之后，经过几个月的观察和窥探，你的优雅与智慧，你对待生活的态度和你对未来的愿望深切地在我心中留下了印象。你是迷人的阳光女孩，我总是梦想着与你分享余生。唉，实际上你远远超过了我最疯狂的梦想。我不知道如何桥起我与你之间的鸿沟。所以我没有任何计划，仅仅只是等待，等待一个适当的机会到来。直到现在，毕业的到来，我意识到我是个傻瓜，我应该创造机会并且抓住它而不只是等待。

这些日子里，我和我的朋友、室友、同学一个接一个地分开。我仍无法相信，在挥手之后，这些熟悉的面孔很快就会从我们的生活中消失，仅仅留下回忆。我明天就将离开学校。你已经计划远走高飞，追求你的未来，实现你的梦想。如果没有命运，也许我们不会再次相遇。所以今晚，我正在你的宿舍楼下徘徊，希望能偶然遇见你。但矛盾的是，你的美貌一定会使我心跳加速，我笨拙的舌头也许无法吐出一个字。我不记得我曾多少次经过你的宿舍楼，每次都希望看到你出现在阳台上或是窗台上。我不记得这个想法曾多少次在我的脑海中涌出：打电话叫她一起吃晚饭或是聊聊天。但每次，考虑到你的优秀和我的平凡，胆怯的优势超越勇气驱使我静静地离开。

毕业，意味着中学生活的终结。这些光荣与浪漫的时代结束。你可爱的微笑是我原来努力学习的动力，这单相思的爱情会被密封，作为一个我心灵深处的记忆。毕业，也意味着新生活的开始，一个到达光明未来的足迹。我真希望你在国外天天开心，一切顺利。同时，我将努力从幼稚中走出来，变得更加成熟。我的理想将是在现实中追求我的爱与幸福，我永远不会放弃。

再见了，我的公主！

如果有一天，在某个天涯海角，我们有机会相聚，即使是白发苍苍的男人和女人，在那个时候，我希望我们可以成为好朋友来自豪地分享这个记忆，重温年轻快乐的激情。如果这个机会永远没有到来，我希望我是天空中的星星，在你的窗外闪烁。远远地保佑着你，就像一个朋友，每天晚上陪伴在你左右，一同分享甜美的梦亦或是一同经历可怕的梦。

description: 现在问题来了：天空可以理解为一条数轴，在这条数轴上分布着许多颗星星，对于每颗星星都有它的位置 $X_i$ 和自身的亮度 $B_i$。**一个位置可能有多颗星星**。而窗户所能看到的范围是一个给出的参数 $W$，我们看到的星星也包括窗户边缘的星星。现在，要你求出调整窗户位置后能看到星星的亮度之和最大值。

inputFormat:
一行 $N,W$，分别代表星星的数量和窗户的宽度。

余下 $N$ 行，输入 $X_i$ 和 $B_i$，代表星星的坐标和亮度。

outputFormat: 一个数字，代表能看到星星的最大亮度和。

hint:
样例说明：

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

对于 $10\%$ 的数据，$W=0$（没有边缘）；

对于 $40\%$ 的数据，$W\leq 1000$；

对于 $100\%$ 的数据，$1 \leq N\leq 10 ^ 5$，$0 \leq W\leq 10 ^ 5$，$1 \leq X_i\leq 10 ^ 5$，$1\leq B_i\leq 100$。

除 $W=0$ 的情况外，$W$ 均为 $\geq 3$ 的奇数。


title: 树上游戏

description:
lrb 有一棵树，树的每个节点有个颜色。给一个长度为 $n$ 的颜色序列，定义 $s(i,j)$ 为 $i$ 到 $j$ 的颜色数量。以及

$$sum_i=\sum_{j=1}^n s(i, j)$$

现在他想让你求出所有的 $sum_i$。

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

第二行为 $n$ 个整数，分别表示 $n$ 个节点的颜色 $c_1,c_2\ldots c_n$。

接下来 $n-1$ 行，每行为两个整数 $x,y$，表示 $x$ 和 $y$ 之间有一条边。

outputFormat: 输出 $n$ 行，第 $i$ 行为 $sum_i$。


title: [USACO17JAN] Promotion Counting P

description:
奶牛们又一次试图创建一家创业公司，还是没有从过去的经验中吸取教训——牛是可怕的管理者！

为了方便，把奶牛从 $1\sim n$ 编号，把公司组织成一棵树，1 号奶牛作为总裁（这棵树的根节点）。除了总裁以外的每头奶牛都有一个单独的上司（它在树上的 “双亲结点”）。

所有的第 $i$ 头牛都有一个不同的能力指数 $p_i$，描述了她对其工作的擅长程度。如果奶牛 $i$ 是奶牛 $j$ 的祖先节点，那么我们我们把奶牛 $j$ 叫做 $i$ 的下属。

不幸地是，奶牛们发现经常发生一个上司比她的一些下属能力低的情况，在这种情况下，上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之，对于公司的中的每一头奶牛 $i$，请计算其下属 $j$ 的数量满足 $p_j > p_i$。

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

接下来的 $n$ 行包括奶牛们的能力指数 $p_1,p_2 \dots p_n$。保证所有数互不相同。

接下来的 $n-1$ 行描述了奶牛 $2 \sim n$ 的上司的编号。再次提醒，1 号奶牛作为总裁，没有上司。

outputFormat: 输出包括 $n$ 行。输出的第 $i$ 行应当给出有多少奶牛 $i$ 的下属比奶牛 $i$ 能力高。


title: [USACO17JAN] Building a Tall Barn P

description:
Farmer John is building a brand new, $N$-story barn, with the help of his $K$ cows ($1 \leq N \leq K \leq 10^{12}$ and $N \leq 10^5$). To build it as quickly as possible, he needs your help to figure out how to allocate work among the cows.

Each cow must be assigned to work on exactly one specific floor out of the $N$ total floors in the barn, and each floor must have at least one cow assigned to it. The $i$th floor requires $a_i$ units of total work, and each cow completes one unit of work per hour, so if $c$ cows work on floor $i$, it will be completed in $a_i / c$ units of time. For safety reasons, floor $i$ must be completed before construction can begin on floor $i+1$.

Please compute the minimum total time in which the barn can be completed, if the cows are allocated to work on floors in an optimal fashion. Output this number rounded to the nearest integer; it is guaranteed that the solution will be more than 0.1 from the boundary between two integers.

inputFormat:
The first line of input contains $N$ and $K$.

The next $N$ lines contain $a_1 \ldots a_N$, each a positive integer of size at most $10^{12}$.

outputFormat:
Please output the minimum time required to build the barn, rounded to the

nearest integer.

translation:
### 题目大意
FJ 正在他的 $K$ 头奶牛的帮助下建造一个全新的 $N$ 层谷仓（$1\le N\le K\le 10^{12}，N\le 10^5$)。为了能够尽快的建造它，他需要你帮助他来找出如何在奶牛间分配工作。

每一头牛必须分配到 $N$ 层中的某一个特定楼层中，并且每一层楼必须至少有一头牛在其中工作。第i层楼需要 $a_i$ 个单位的工作，并且每一头牛完成每一单位的工作需要一个单位时间。所以如果有 $C$ 头牛在第 $i$ 层工作，那么第 $i$ 层需要 $\frac{a_i}{c}$ 个单位时间。为了安全起见，在开始施工第 $i+1$ 层楼之前，必须先完成第 $i$ 层。

如果奶牛被分配以最佳方式在楼层上工作，请计算完成谷仓的最小总时间。输出这个时间四舍五入到整数的结果；数据保证答案离两个整数间的中界大于 $0.1$。
### 输入格式
第一行包括两个数 $N$ 和 $K$。

接下来 $N$ 行包括了$a_1\dots a_n$，每行一个不大于 $10^{12}$ 的正整数。
### 输出格式
请输出完成谷仓的最小总时间（四舍五入至整数）。

by @Happy_mouse


title: [USACO17JAN] Subsequence Reversal P

description:
Farmer John is arranging his $N$ cows in a line to take a photo ($1 \leq N \leq 50$). The height of the $i$th cow in sequence is $a(i)$, and Farmer John thinks it would make for an aesthetically pleasing photo if the cow lineup has a large increasing subsequence of cows by height.

To recall, a subsequence is a subset $a(i_1), a(i_2), \ldots, a(i_k)$ of elements from the cow sequence, found at some series of indices $i_1 < i_2 < \ldots < i_k$. We say the subsequence is increasing if $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

FJ would like there to be a long increasing subsequence within his ordering of the cows. In order to ensure this, he allows himself initially to choose any subsequence and reverse its elements.

```cpp
For example, if we had the list

1 6 2 3 4 3 5 3 4
We can reverse the chosen elements

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^
to get

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^
```
Observe how the subsequence being reversed ends up using the same indices as it initially occupied, leaving the other elements unchanged.

Please find the maximum possible length of an increasing subsequence, given that you can choose to reverse an arbitrary subsequence once.

FJ正在安排他的N头奶牛排成一队以拍照（1<=n<=50)。队列中的第i头奶牛的身高为a[i]，并且FJ认为如果奶牛的身高序列中含有一个很长的不下降子序列的话，这会是一张很好的照片。

回忆一下，子序列是由牛序列中的一些元素a[i\_1],a[i\_2],.....a[i\_k]组成的子集。(i\_1<i\_2<...<i\_k) 如果a[i\_1]<=a[i\_2]<=a[i\_3]<=......<=a[i\_k]的话，我们就说这个序列是不下降的。

FJ想要在他的奶牛序列中包括一个长期增长的子序列（也就是很长的不下降子序列）。为了确保这一点，他允许自己在一开始选择任何子序列并逆转其元素。

观察这个子序列（上方英文）是如何反转并占据他们最初的相同的位置的，且其他元素保持不变。

在只能反转一次任意子序列的情况下，请找到不下降子序列的最大可能长度。

inputFormat:
The first line of input contains $N$. The remaining $N$ lines contain $a(1) \ldots a(N)$, each an integer in the range $1 \ldots 50$.

第一行一个整数N。

接下来N行包括N个整数a[1]...a[n]，每行一个在1到50之间的整数。

outputFormat:
Output the number of elements that can possibly form a longest increasing subsequence after reversing the contents of at most one subsequence.

输出反转一次任意子序列后所得到的不下降子序列的最大可能长度。

hint: 感谢 @XY星系质量PK  的翻译


title: [USACO17JAN] Balanced Photo G

description:
Farmer John is arranging his $N$ cows in a line to take a photo ($1 \leq N \leq 100,000$). The height of the $i$th cow in sequence is $h_i$, and the heights of all cows are distinct.

As with all photographs of his cows, FJ wants this one to come out looking as nice as possible. He decides that cow $i$ looks "unbalanced" if $L_i$ and $R_i$ differ by more than factor of 2, where $L_i$ and $R_i$ are the number of cows taller than $i$ on her left and right, respectively. That is, $i$ is unbalanced if the larger of $L_i$ and $R_i$ is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his cows are unbalanced.

Please help FJ compute the total number of unbalanced cows.

FJ 正在安排他的 $N$ 头奶牛站成一排来拍照（$1\le N \le 10^5$）。序列中的第 $i$ 头奶牛的高度是 $h_i$，且序列中所有的奶牛的身高都不同。

就像他的所有牛的照片一样，FJ希望这张照片看上去尽可能好。他认为，如果 $L_i$ 和 $R_i$ 的数目相差 $1$ 倍以上，第 $i$ 头奶牛就是不平衡的（$L_i$ 和 $R_i$ 分别代表第 $i$ 头奶牛左右两边比她高的奶牛的数量）。也就是说，如果 $L_i$ 和 $R_i$ 中的较大数大于较小数的 $2$ 倍，第 $i$ 头奶牛就是不平衡的。FJ 不希望他有太多的奶牛不平衡。

请帮助 FJ 计算不平衡的奶牛数量。

inputFormat:
The first line of input contains $N$.  The next $N$ lines contain $h_1 \ldots h_N$, each a nonnegative integer at most 1,000,000,000.

第一行一个整数 $N$。

接下 $N$ 行包括 $H_1$ 到 $H_n$，每行一个不超过 $10^9$ 的非负整数。

outputFormat:
Please output a count of the number of cows that are unbalanced.

请输出不平衡的奶牛数量。

hint: 感谢 @XY星系质量PK  的翻译


title: [USACO17JAN] Hoof, Paper, Scissor G

background: *本题与 [银组同名题目](/problem/P6120) 在题意上一致，唯一的差别在于对变手势次数的限制。*

description:
你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。

“蹄子，剪刀，布”和“石头，剪刀，布”的规则十分类似，两只奶牛数到三，然后出一个代表蹄子，剪刀或布的手势。蹄子胜过剪刀，剪刀胜过布，布胜过蹄子。特别地，如果两只奶牛的手势相同，则视为平局。

现在 FJ 和 Bassie 要进行 $N$ 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换 $K$ 次手势。

现在请你帮 Bassie 求出她最多能赢多少轮。

inputFormat:
第一行输入两个整数 $N,K$（$1 \leq N \leq 10^5$，$0 \leq K \leq 20$）。

接下来 $N$ 行，每行一个字母，代表 FJ 这一轮出的手势。`H` 代表蹄子（Hoof），`S` 代表剪刀（Scissors），`P` 代表布（Paper）。

outputFormat: 输出一个整数，代表 Bassie 在最多变换 $K$ 次手势的前提下最多赢多少轮。


title: [USACO17JAN] Cow Navigation G

description:
Bessie has gotten herself stuck on the wrong side of Farmer John's barn again, and since her vision is so poor, she needs your help navigating across the barn.

The barn is described by an $N \times N$ grid of square cells ($2 \leq N \leq 20$), some being empty and some containing impassable haybales. Bessie starts in the lower-left corner (cell 1,1) and wants to move to the upper-right corner (cell $N,N$). You can guide her by telling her a sequence of instructions, each of which is either "forward", "turn left 90 degrees", or "turn right 90 degrees". You want to issue the shortest sequence of instructions that will guide her to her destination. If you instruct Bessie to move off the grid (i.e., into the barn wall) or into a haybale, she will not move and will skip to the next command in your sequence.

Unfortunately, Bessie doesn't know if she starts out facing up (towards cell 1,2) or right (towards cell 2,1). You need to give the shortest sequence of directions that will guide her to the goal regardless of which case is true. Once she reaches the goal she will ignore further commands.

inputFormat:
The first line of input contains $N$.

Each of the $N$ following lines contains a string of exactly $N$ characters, representing the barn. The first character of the last line is cell 1,1. The last character of the first line is cell N, N.

Each character will either be an H to represent a haybale or an E to represent an empty square.

It is guaranteed that cells 1,1 and $N,N$ will be empty, and furthermore it is guaranteed that there is a path of empty squares from cell 1,1 to cell $N, N$.

outputFormat: On a single line of output, output the length of the shortest sequence of directions that will guide Bessie to the goal, irrespective whether she starts facing up or right.

translation:
贝西误把自己困在了FJ谷仓的一侧。因为她的视力很差，她在脱困时需要你的帮助。

谷仓的平面图由一个方形细胞图（即所画图）呈现，有些细胞（即单位）是空的，其他的则是不可通过的柴草堆。贝西从左下角开始（细胞1，1）想一路搬到右上角。你可以引导她，告诉她一个指令序列，指令可以为“前进”“左转90度”“右转90度”。你需要得出能够使她到达目的地所用的最短指令序列。如果你指示贝西离开谷仓或至柴草堆，她不会移动，会直接跳到下一个命令序列。

不幸的是，贝西不知道她一开始所朝的方向（可能是上或右），而序列无需考虑这种情况，（使得bessie无论是朝上还是朝右，根据给出的指令都能到达终点。）

注意：**到了终点就不会再移动了**

翻译提供者：lzyzz250
翻译修正者：szh_0808 lord_grim


title: [USACO17JAN] Cow Dance Show S

description:
After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet "Cowpelia".

The only aspect of the show that remains to be determined is the size of the stage. A stage of size $K$ can support $K$ cows dancing simultaneously. The $N$ cows in the herd ($1 \leq N \leq 10,000$) are conveniently numbered $1 \ldots N$ in the order in which they must appear in the dance. Each cow $i$ plans to dance for a specific duration of time $d(i)$. Initially, cows $1 \ldots K$ appear on stage and start dancing. When the first of these cows completes her part, she leaves the stage and cow $K+1$ immediately starts dancing, and so on, so there are always $K$ cows dancing (until the end of the show, when we start to run out of cows). The show ends when the last cow completes her dancing part, at time $T$.

Clearly, the larger the value of $K$, the smaller the value of $T$. Since the show cannot last too long, you are given as input an upper bound $T_{max}$ specifying the largest possible value of $T$. Subject to this constraint, please determine the smallest possible value of $K$.

经过几个月的排练，奶牛们基本准备好展出她们的年度舞蹈表演。今年她们要表演的是著名的奶牛芭蕾——“cowpelia”。

表演唯一有待决定的是舞台的尺寸。一个大小为 $K$ 的舞台可以支持 $K$ 头牛同时在舞台上跳舞。在牛群中的 $N$ 头牛按照她们必须出现在舞蹈中的顺序方便地编号为 $1,2,...N$。第 $i$ 头牛计划跳 $d_i$ 的特定持续时间。
一开始，第 $1,2,...K$ 头牛出现在舞台上并开始跳舞。当这些牛中的某一头牛首先完成了她的部分，她会马上离开舞台并且第 $K+1$ 头牛会出现在舞台上并开始跳舞。所以，舞台上总有 $K$ 头奶牛在跳舞（直到表演的尾声，奶牛不够的时候）。当最后一头奶牛完成了她的舞蹈部分，表演结束，共花了 $T$ 个单位时间。

显然，$K$ 的值越大，$T$ 就越小。由于表演不能拖太长，你得知了指定 $T$ 的最大可能值的上限 $T_{max}$。请根据这个约束，确定 $K$ 的最小值。

inputFormat:
The first line of input contains $N$ and $T_{max}$, where $T_{max}$ is an integer of value at most 1 million.

The next $N$ lines give the durations $d(1) \ldots d(N)$ of the dancing parts for cows $1 \ldots N$. Each $d(i)$ value is an integer in the range $1 \ldots 100,000$.

It is guaranteed that if $K=N$, the show will finish in time.

第一行包括 $N$ 和 $T_{max}$ 两个整数。

接下来的 $N$ 行，第 $i$ 行给出了第 $i$ 头牛跳舞的持续时间 $d_i$。第 $i$ 行包括一个整数 $d_i$。

保证 $K=N$ 时表演会按时完成。

outputFormat:
Print out the smallest possible value of $K$ such that the dance performance will take no more than $T_{max}$ units of time.

输出在表演时间不大于 $T_{max}$ 时的 $K$ 的最小可能值。

hint:
于 $100\%$ 的数据，$1 \le N \le 10^4$，$T_{max} \le 10^6$，$1 \le d_i \le 10^5$。

感谢@XY星系质量PK 提供的翻译


title: 区间方差

background: 出题人并没有能力写有趣的题面……

description:
对于一个长度为 $n$ 的序列 $a_1,a_2,a_3\cdots a_n$，我们定义它的平均数 $a$ 为:

$$a=\frac{1}{n}\sum_{i=1}^{n}a_i$$

并定义它的方差 $d$ 为:

$$d=\frac{1}{n}\sum_{i=1}^{n}(a_i-a)^2$$

现在给定一个长度为 $n$ 的序列 $b_1,b_2\cdots b_n$。你需要支持两种操作。每种操作的格式为 `c x y`。

若 $c=1$，为修改操作，代表将 $b_x$ 赋值为 $y$。

若 $c=2$，为查询操作，代表查询 $b_x$ 到 $b_y$ 的方差。

为了避免浮点数误差，请以分数取模形式输出结果（对 1000000007（$10^9+7$）取模）。

inputFormat:
第一行两个整数 $n,m$，代表序列 $b$ 的长度为 $n$，有 $m$ 个操作。

第二行 $n$ 个整数 $b_i$，表示序列 $b$ 的初始值。

下面有 $m$ 行整数，每行格式为 `c x y`，含义如上文所示。保证所有操作合法。

outputFormat: 对于每个操作 2，输出一行。


title: [USACO17JAN] Secret Cow Code S

description:
The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string $s$, let $F(s)$ be $s$ followed by $s$ "rotated" one character to the right (in a right rotation, the last character of $s$ rotates around and becomes the new first character). Given an initial string $s$, the cows build their infinite-length code string by repeatedly applying $F$; each step therefore doubles the length of the current string.

Given the initial string and an index $N$, please help the cows compute the character at the $N$th position within the infinite code string.

inputFormat:
The input consists of a single line containing a string followed by $N$. The string consists of at most 30 uppercase characters, and $N \leq 10^{18}$.

Note that $N$ may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a "long long" in C/C++).

outputFormat: Please output the $N$th character of the infinite code built from the initial string. The first character is $N=1$.

translation:
奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。

给定一个字符串，对字符串进行一次操作（每一次正确的操作，最后一个字符都会成为新的第一个字符），然后把操作后的字符串放到操作前的字符串的后面。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。

给定初始字符串和 $N$，请帮助奶牛计算无限字符串中位置为 $N$ 的字符。

第一行输入一个字符串。该字符串包含最多 $30$ 个大写字母，数据保证 $N \leq 10^{18}$。

第二行输入 一个整数 $N$。请注意，数据可能很大，放进一个标准的 $32$ 位整数容器可能不够，所以你可能要使用一个 $64$ 位的整数容器（例如，在 C/C++ 中是 `long long`）。

请输出从初始字符串生成的无限字符串中的下标为 $N$ 的字符。第一个字符的下标是 $N=1$。

感谢 @y\_z\_h 的翻译

samples:
COW 8
C

hint:
In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC

12345678


title: 攀爬者

background: HKE 考完 GDOI 之后跟他的神犇小伙伴们一起去爬山。

description:
他在地形图上标记了 $N$ 个点，每个点 $P_i$ 都有一个坐标 $(x_i,y_i,z_i)$。所有点对中，高度值 $z$ 不会相等。HKE 准备从最低的点爬到最高的点，他的攀爬满足以下条件：

 (1) 经过他标记的每一个点；

 (2) 从第二个点开始，他经过的每一个点高度 $z$ 都比上一个点高；

 (3) HKE 会飞，他从一个点 $P_i$ 爬到 $P_j$ 的距离为两个点的欧几里得距离。即，$\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2}$

现在，HKE 希望你能求出他攀爬的总距离。

inputFormat:
第一行，一个整数 $N$ 表示地图上的点数。

接下来 $N$ 行，三个整数 $x_i,y_i,z_i$ 表示第 $i$ 个点的坐标。

outputFormat: 一个实数，表示 HKE 需要攀爬的总距离（保留三位小数）

hint: 对于100%的数据，$1\leq N\leq 50000$，答案的范围在 double 范围内。


title: 蜈蚣

background: 一群人在山上遇见了一条蜈蚣。

description:
在一条山路的转角处，WYH 发现了一条有中指一样粗的有 $N$ 节的蜈蚣。这只蜈蚣马上就吸引了 HKE 的眼球，HKE 深深地爱上了这条魔性的蜈蚣。它的很多对足在前进的时候像波浪一样，颇是有毒。

但是，热爱解剖动物的 MZL 却准备把蜈蚣切了。HKE 很失落，于是 MZL 承诺不会完全肢解它，只把它的 $N$ 节切成 $M$ 段，每一段包含原蜈蚣完整的一节或多节。

HKE 看到他心爱的蜈蚣会切掉是会觉得恶心的。蜈蚣的每一节都有一个权值 $W_i$，切下来的一段 $(W_i, W_{i + 1}, \ldots, W_j)$ 带给 HKE 的恶心值是 $W_i \mathbin{\mathrm{xor}} W_{i + 1} \mathbin{\mathrm{xor}} \cdots \mathbin{\mathrm{xor}} W_j$，这里的 $\mathbin{\mathrm{xor}}$ 代表按位异或操作。邪恶的 LJC 希望 HKE 受到的总恶心值 —— 也就是每一段子蜈蚣带给 HKE 的恶心值的和最大，请你求出 HKE 的最大恶心值。

（注：按位异或，其运算符号在 Pascal 中为 `xor`，在 C++ 中为 `^` 或 `xor`；请注意加法与异或运算的优先级先后顺序）

inputFormat:
第一行，两个整数 $N, M$，表示蜈蚣长 $N$ 节，切成 $M$ 段。

第二行 $N$ 个整数用空格分开，表示蜈蚣每一节的权值 $W_1, W_2, \ldots, W_n$。

outputFormat: 一个整数表示最大恶心值。

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

第一段的恶心值为 $1 \mathbin{\mathrm{xor}} 2 = 3$。

第二段的恶心值为 $3 \mathbin{\mathrm{xor}} 4 = 7$

第三段的恶心值为 $5$

总恶心值为 $3 + 7 + 5 = 15$。此时为最优解。

**【数据范围】**

对于 $30 \%$ 的数据，$1 \le N \le 100$，$1 \le M \le 10$；

对于 $100 \%$ 的数据，$1 \le N \le 1000$，$1 \le M \le 100$，保证结果在 $2^{30} - 1$ 内；


title: 漂浮的鸭子

description: 下雨时地上会有一个个水坑，但一个水坑只会流向另一个特定的水坑，而且水不会回流。可能会有多个水坑同时流向一个水坑。这天又下起了雨夹鸭，每个水坑里都漂浮着一只鸭子。WYH在每个水坑旁派遣了一个特派员，特派员会在鸭子上做记号。在某一时刻，全部鸭子开始顺水漂浮，同时特派员开始计时。当某个特派员发现他做的那个记号的鸭子漂浮回来的时候，他就会停止计时，把时间上报给WYH。现在WYH探勘了地形后把每段水流的关系与时间告诉了你，他想知道他所获得的所有数据中最大的那个是？

inputFormat:
第一行一个正整数n，代表有n个水坑（从1到n编号）

第2~n+1行每行两个正整数，其中第i+1行的两个整数为Di与Ti，代表第i号水坑的水会流向Di号坑，流动所需时间为Ti。保证Di≠i。

outputFormat: 一个整数，代表WYH手上获得的特派员数据中最大的那个数。


title: 最大差值

description:
HKE 最近热衷于研究序列，有一次他发现了一个有趣的问题：

对于一个序列 $A_1,A_2,\cdots,A_n$，找出两个数 $i,j$（$1\le i<j\le n$），使得 $A_j-A_i$ 最大。

现在给出这个序列，请找出 $A_j-A_i$ 的最大值。

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

接下来 $n$ 行，每行一个整数，第 $(i + 1)$ 行的整数为 $A_i$。

outputFormat: 一行，为 $A_j-A_i$ 的最大值。


title: 随机数生成器

description:
HKE最近编写了一个函数 $\text{rand}(l,r)$，其中 $l,r$ 为正整数且 $l \le r$。这个函数会等概率返回区间 $[l,r]$ 中任意一个正整数。然后，他又编写了一个函数：

```cpp
int work(int x){
    if(x==1) return 0;
    else return work(rand(1,x))+1;
}
```
这段代码用pascal写起来就是：
```pascal
function work(x:integer):integer;
begin
    if x=1 then exit(0);
    else exit(work(rand(1,x))+1);
end;
```
现在给定一个正整数 $n$，请问 $\text{work}(n)$ 的返回值的期望值是多少？

期望的定义：假设 $\text{work}(n)$ 返回的所有可能的值为 $x_1,x_2,\dots ,x_k$，它们出现的概率分别为 $p_1,p_2,\dots,p_k$，则期望为：

$$\mathbb{E}=\sum_{i=1}^{k}x_i p_i$$

inputFormat: 一个正整数 $n$

outputFormat: 一个实数，表示 $\text{work}(n)$ 的期望值。保留 $5$ 位小数。


title: [USACO16DEC] Moocast S

background: 欢迎提供翻译，请直接在讨论区发帖，感谢你的贡献。

description:
Farmer John's $N$ cows ($1 \leq N \leq 200$) want to organize an emergency"moo-cast" system for broadcasting important messages among themselves.

Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow.  These walkie-talkies each have a limited transmission radius -- a walkie-talkie of power $P$ can only transmit to other cows up to a distance of $P$ away (note that cow A might be able to transmit to cow B even if cow B cannot transmit back, due to cow A's power being larger than that of cow B).  Fortunately, cows can relay messages to one-another along a path consisting of several hops, so it is not necessary for every cow to be able to transmit directly to every other cow.

Due to the asymmetrical nature of the walkie-talkie transmission, broadcasts from some cows may be more effective than from other cows in their ability toreach large numbers of recipients (taking relaying into account).  Please  help the cows determine the maximum number of cows that can be reached by a broadcast originating from a single cow.

约翰农场主的 $N$ 头奶牛想建立一个紧急情况下的“哞哞广播”系统，这样它们就可以在自己中间广播重要信息。

奶牛们想让每头牛装备上一个对讲机，而不是在长距离中向另一头奶牛“哞哞”乱叫。这些对讲机每台都有各自的有效传输半径——一个拥有 $P$ 能量的对讲机只能向距离在 $P$ 以内的牛发送信息（注意可能出现 $A$ 牛对讲机的能量比 $B$ 牛的大，而 $A$ 牛可以给 $B$ 牛发送信息，但 $B$ 牛不能传回信息）。幸运的是，奶牛们可以通过其他奶牛中继，沿着一条跳跃的路径传递信息，因此每个奶牛不必要直接向每个其他奶牛传播。

由于对讲机的费堆成性质，来自一些奶牛的广播可能比其他奶牛的广播能够达到更多的接受者（考虑中继的情况）的能力更有效。请帮助奶牛确定来自单个奶牛的广播可以达到的奶牛的最大数量。

inputFormat:
The first line of input contains $N$.

The next $N$ lines each contain the $x$ and $y$ coordinates of a single cow ( integers in the range $0 \ldots 25,000$) followed by $p$, the power of the walkie-talkie held by this cow.

第一行，一个整数 $N$。

接下来 $N$ 行，第 $i$ 行包括第 $i$ 只牛的坐标 $(x_i,y_i)$，
以及这只牛所持有对讲机的能量 $P_i$。

outputFormat:
Write a single line of output containing the maximum number of cows a broadcast from a single cow can reach.  The originating cow is included in this number.

一行，一个整数，表示从来自单个奶牛的广播可以达到的奶牛的最大数量。

开始的牛也包括在这个数量中。


title: 大循环

description:
hke 有一天学会了循环语句，感到很神奇。回到家，他用 C++ 写下这段代码：

```cpp
void work()
{
  ans=0;
    for(a[1]=1;a[1]<=n;++a[1])
      for(a[2]=1;a[2]<a[1];++a[2])
        for(a[3]=1;a[3]<a[2];++a[3])
          //......
            for(a[k]=1;a[k]<a[k-1];++a[k])
              ans+=f(q);
  cout<<ans;
}
```
其中，$q$ 是给定的常数，$f(x)$ 是一个关于 $x$ 的 $m$ 次多项式，它的表达式为：

$$f(x) = a _ m x ^ m + a _ {m - 1} x ^ {m - 1} + \cdots + a _ 1 x + a _ 0$$

hke 迫不及待地开始运行这个程序，但程序运行得实在太慢了。于是他找到了你，想知道这段程序输出的结果是？答案可能很大，你只需输出其对 $10^9+7$ 取模的结果即可。假设运算过程中不存在溢出。

inputFormat:
第一行 $4$ 个正整数，分别为 $n,m,k,q$；

第二行 $m+1$ 个正整数，分别为 $a_0,a_1,a_2\cdots a_m$；

outputFormat: 一个数，表示程序运行结果对 $10^9+7$ 取模的结果。


title: 会议座位

background: 话说校长最近很喜欢召开全校教职工大会，让老师们强行听他装逼

description:
现在校长在校园网上公布了一份座位表，$n$ 位老师从左到右依次排成一行。老师们都对这个座位很满意。

然而到了开会时，校长不小心把座位表打乱了，老师们很不满。老师们并不在意自己的位置变了多少，但如果有一对老师 $a$ 和 $b$，他们原来的座位是 $a$ 在 $b$ 左边，现在变成了 $a$ 在 $b$ 右边，那么这一对老师便会贡献一单位不满值。

校长想知道这些老师的总不满值是多少。

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

第二行有 $n$ 个字符串，每个字符串代表老师的名字（大小写敏感）。这一行代表原来的座位表。

第三行有 $n$ 个字符串，代表打乱后的座位表。

outputFormat: 一行，一个正整数，表示老师们的总不满值。

hint:
对于 $30\%$ 的数据，$1\le n \le 10^3$。

对于 $100\%$ 的数据，$1\le n \le 10^5$，每位老师名字长度不超过 $5$，只有大小写字母并且互不相同。注意名字对大小写敏感。


title: 生日礼物

background: wyh 快过生日了，hke 和 ljc 打算送他生日礼物。

description:
wyh 有一个幸运数字 $n$。现在 hke 打算送他用心度为 $a$ 的礼物，ljc 打算送他用心度为 $b$ 的礼物。两个人的礼物合在一起，用心度为 $\operatorname{lcm}(a,b)$，其中 $\operatorname{lcm}$ 代表最小公倍数。wyh 收到的是这份合在一起的礼物。

如果 wyh 收到礼物的用心度恰好为 $n$，他就会很高兴。现在请问有多少种送礼物的方案使得 wyh 高兴？

inputFormat: 一个正整数 $n$。

outputFormat: 一个整数表示答案。


title: HKE与他的小朋友

background: HKE 带着 $n$ 个小朋友做游戏。

description:
现在有 $n$ 个座位编号为 $1$ 至 $n$，这些小朋友也编号 $1$ 至 $n$。一开始所有小朋友都坐在相应的座位上。HKE 的游戏可用一个 $n$ 的排列 $A(A_1,A_2, \cdots, A_n)$ 表示。一轮游戏时，对于所有的 $1\leq i\leq n$，坐在位置 $i$ 上的小朋友坐到位置 $A_i$ 上。

现在游戏进行了 $k$ 轮，HKE 想知道游戏结束后，位置 $1,2,\cdots, n$ 分别坐了几号小朋友？

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

第二行一个排列 $A_1,A_2, \cdots, A_n$。

outputFormat: 一行 $n$ 个数表示位置 $1,2, \cdots, n$ 上的小朋友的编号。


title: 宝藏

background:
此题为改编题，特别鸣谢倪星宇同学。

一群海盗抢到了许多宝藏，准备埋在自己的山洞里。

description: 海盗的山洞是一个n×n的方格，每个方格都可以储存很多宝藏。所有方格初始时是空的。海盗头头决定把这些宝藏藏在某些矩形区域里，同时了解某些矩阵区域里宝藏数量的奇偶性。但是宝藏实在太多了，他整理得眼花缭乱，所以他找到了你来帮忙。

inputFormat:
第一行两个正整数n,m，表示方格的大小与操作的数量。

下面m行有两种操作：

（1）P x1 y1 x2 y2 k a1 b1 a2 b2……ak bk，表示在(x1,y1)到(x2,y2)这段矩形区域中加入b1种a1物品，b2种a2物品……bk种ak物品

（2）Q  x1 y1 x2 y2，表示询问(x1,y1)到(x2,y2)这段矩形区域中所有物品的奇偶性

outputFormat:
对于每种操作Q，输出一行字符串。该字符串长度为30，由'1'与'2'组成。若第k种物品数量为**偶数**，则该字符串从左到右第k位为'1'，否则为'2'。字符之间没有空格。

（注意是偶1奇2）

hint:
30%的数据，n≤300，m≤300；

100%的数据，n≤2500，m≤50000，1≤x1≤x2≤n，1≤y1≤y2≤n，1≤ak≤30，1≤bk≤100；


title: 简单的函数

background: 此题为改编题，特别鸣谢吴作凡同学。

description:
HKE 有一次发现了一个很有趣的函数。

定义 $f(2)=1$。对于 $n\geq3$，设 $t$ 为最小的使得 $n$ 不能被 $t$ 整除的正整数，则 $f(n)=f(t)+1$。

举个栗子。比如 $n=6$，此时 $t=4$，$f(6)=f(4)+1=f(3)+2=f(2)+3=4$。

现在，HKE 想知道 $f(2)\times f(3)\times\cdots\times f(n)$ 是多少？答案可能很大，请对 $10^9+7$ 取模。

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

outputFormat: 一行为所求的结果。


title: [POI2005] BANK-Cash Dispenser

description:
The BBB (short for Byteotian Bit Bank) owns the largest net of cash dispensers in Byteotia. The clients of the BBB can draw their money from the cash dispensers on the basis of a cash card and a 4-digit PIN code. Lately, in order to increase their clients' security, the BBB has had a camera installed by each cash dispenser. The cameras transmit the recorded image to the BBB using radio signals. Unfortunately, the signals are being intercepted by a gang of computer thieves. The thieves attempt to discover the 4-digit PIN codes of the BBB clients, whose cash cards they subsequently steal. Being aware of this fact, the BBB clients try to perform redundant movements over the keyboard while entering the PIN. The camera is not able to pick out the keystrokes, it only records the finger movements. Consequently, it is usually not possible to determine the PIN unambiguously. For instance, the client moving his finger over the key 1 and then over the key 5 could have entered the following PIN codes: 1111, 1115, 1155, 1555, 5555. Desperate thieves glean the camera recordings, counting on being able to determine the PIN of a client or at least limiting the number of possible codes on the basis of multiple recordings of his transactions. Having accumulated sequences entered by a particular wealthy client of the BBB, they made you an "unnegotiable proposition".

TaskWrite a programme which:

reads from the standard input a description of the recorded sequences of finger movements, which the client has performed whilst entering his PIN,determines the number of distinct PIN codes, which the client can have (i.e. the number of those 4-digit PIN codes, which could have been entered by performing the given finger movement sequences),writes the outcome to the standard output.

BBB（Byteotian Bit Bank的缩写）拥有Byteotia最大的自动提款机网络。 BBB的客户可以根据现金卡和4位数的PIN码从自动柜员机中提取款项。最近，为了提高客户的安全性，BBB已经给每台自动提款机安装了相机。摄像机使用无线电信号将记录的图像发送到BBB。不幸的是，这些信号正被一群电脑盗贼拦截。盗贼试图发现BBB用户的4位PIN码，他们随后窃取了他们的现金卡。意识到这一事实，BBB用户尝试在输入PIN时执行键盘上的冗余动作。相机只能记录手指的动作。因此，通常不可能明确地确定PIN码。例如，用户将手指移动到键1上，然后移动到键5可以输入以下PIN码：1111,1115,1155,1555,5555。绝望的盗贼们收集相机记录，现在盗贼们给你一个手指移动序列，要求你确定用户可以具有的不同PIN码的数量。

写一个程序：

从标准输入读取记录的手指移动序列的描述，用户在输入PIN码时执行的手指移动序列，确定客户端可以具有的不同PIN码的数量（即，这些4位PIN码的数量，这可以通过执行给定的手指移动顺序进入），将结果写入标准输出。

inputFormat:
The first line of the standard input contains a single integer $n$ denoting the number of recorded scenes depicting the action of entering the PIN by the client, $1\le n\le 1\ 000$. In the following $n$ lines there are descriptions of these scenes, a single one per line. The description of each scene consists of two positive integers separated by a single space. The first of those numbers, $t$, denotes the length of the sequence of movements, $1\le t\le 10\ 000$. The other is a $t$-digit number, whose consecutive digits denote consecutive keys, over which the client has moved his finger. The total length of all sequences does not exceed $1\ 000\ 000$.

标准输入的第一行包含一个整数n，表示用户输入PIN的动作数，$1\le n\le 1\ 000$。 在以下n行中，对这些动作进行了描述，每行描述一个动作。每个动作的描述由两个由单个空格分开的正整数组成。 这些数中的第一个数字t表示运动序列的长度，$1\le t\le 10\ 000$。另一个是一个t位的正整数，其连续的数字表示连续的键，表示用户移动他的手指到的目标。保证$\sum t\le 1\ 000\ 000$。

outputFormat:
The first and only line of the output should contain a single positive integer - the number of possible PIN codes of the client.

输出有一行，应包含一个正整数，用户可能的PIN码的数量。


title: [POI2005] PUN-Points

description:
A set of grid points in a plane (points whose both cartesian coordinates are integers) which we shall refer to as the pattern, as well as a group of other sets of grid points on the plane are given. We would like to know which of the sets are similar to the pattern, i.e. which of them can be transformed by rotations, translations, reflections and dilations so that they are identical to the pattern. For instance: the set of points $\{(0,0),(2,0),(2,1)\}$ is similar to the set $\{(6,1),(6,5),(4,5)\}$, it is however not similar to the set $\{(4,0),(6,0),(5,-1)\}$.

TaskWrite a programme which:

reads from the standard input the description of the pattern and the family of the investigated sets of points,determines which of the investigated sets of points are similar to the pattern,writes the outcome to the standard output.

题目描述：

给出一个包含平面上格点的集合（格点的定义是xy坐标均为整数），我们将其称作“模式集合”。

接下来给出另外的几个包含平面上点的集合。我们想要考察后面给出的哪些集合和“模式集合”是“相似”的，即：该集合可以通过 旋转，平移，翻转，和缩放 使得该集合和“模式集合”完全相同。

例：{(0,0),(2,0),(2,1)}这个集合和{(6,1),(6,5),(4,5)}这个集合是相似的，但和{(4,0),(6,0),(5,-1)}这个集合是不相似的。

任务：

写一个程序，使得

能从标准输入读取“模式集合”和需要考察（是否相似）的集合，判断哪些集合和“模式集合”相似，并将结果输出到标准输出

输入格式：

标准输入的第一行有一个整数 k (1<=k<=25000)，代表“模式集合”中的点数

接下来k行，每行两个数，用一个空格分隔，第i+1行的两个数分别代表“模式集合”中第i个点的x坐标和y坐标(-20000<=x,y<=20000)

“模式集合”中的点两两不同。

接下来一行一个整数n，代表有n个需要考察的集合

接下来有n个对需要考察的集合的描述：

每个描述的第一行包含一个整数l，代表该集合中的点数(1<=l<=25000)

接下来l行每行包含该集合中一个点的x坐标和y坐标，用一个空格分隔(-20000<=x,y<=20000，为整数)

包含在同一集合中的点两两不同。

输出格式：

你的程序应该向标准输出流输出n行，每行代表对于一个需要考察的集合的结果。

如果第i个需要考察的集合与“模式集合”相似，则第i行应包含单词TAK，即波兰语中的yes

否则第i行应包含单词NIE，即波兰语中的no

inputFormat: In the first line of the standard input there is a single integer $k$ ($1\le k\le 25\ 000$) - the number of points the pattern consists of. In the following $k$ lines there are pairs of integers, separated by single spaces. The $(i+1)$'st line contains the coordinates of $i$'th point belonging to the pattern: $x_{i}$ and $y_{i}$ ($-20\ 000\le x_{i},y_{i} \le 20\ 000$). The points forming the pattern are pairwise different. In the next line there is the number of sets to be investigated: $n$ ($1\le n\le 20$). Next, there are $n$ descriptions of these sets. The description of each set begins with a line containing a single integer $l$ - the number of points belonging to that particular set($1\le l\le 25\ 000$).These points are described in the following lines, a single point per line. The description of a point consists of two integers separated by a single space - its coordinates $x$ and $y$ ($-20\ 000\le x,y\le 20\ 000$).The points which belong to the same set are pairwise different.

outputFormat: Your programme should write to the standard output $n$ lines - one for each of the investigated sets of points. The $i$'th line should contain the word TAK (i.e. yes in Polish), if the $i$'th of the given sets of points is similar to the pattern, or the word NIE (i.e. no in Polish) if the set does not satisfy this condition.


title: [POI2005] SAM-Toy Cars

description:
Jasio 是一个只有三岁的小男孩，他喜欢玩玩具车。他有 $n$ 辆玩具车被保存在书架上。

架子上的玩具车 Jasio 拿不到，但地板上的他可以拿到。Jasio 的母亲会帮 Jasio 拿架子上的玩具车到地板上。

地板最多只能放 $k$ 辆玩具车。

当地板已经放了 $k$ 辆玩具车时，Jasio 的母亲都会从地板上先拿走一个玩具车放回书架，再拿来 Jasio 想要的玩具车。

现在 Jasio 一共想依次玩 $p$ 个玩具车，问 Jasio 的母亲最少需要拿几次玩具车。（只算拿下来的，不算拿上去的）

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

接下来 $p$ 行，每一行有且仅有一个整数 $a_i$，表示 Jasio 想玩的玩具玩家车编号。

outputFormat: 输出一行一个整数，表示最少 Jasio 的母亲最少需要拿玩家车的次数。

hint: 对于 $100\%$ 的数据：$1\le k\le n\le 10^5$，$1\le p\le 5\times 10^5$，$1\le a_i\le n$。


title: [POI2005] SKA-Piggy Banks

description: Byteazar the Dragon 拥有 $N$ 个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。Byteazar 已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，Byteazar 想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助 Byteazar 去决策最少要破坏多少存钱罐。

inputFormat:
第一行包括一个整数 $N$ ($1\le N\le 1000000$)，表示 Byteazar the Dragon 拥有的存钱罐的数量。

存钱罐（包括它们对应的钥匙）从 $1$ 到 $N$ 编号。

接下来有 $N$ 行：第 $i+1$ 行包括一个整数 $x$，表示第 $i$ 个存钱罐对应的钥匙放置在了第 $x$ 个存钱罐中。

outputFormat: 仅一行：包括一个整数，表示能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量。


title: [POI2005] SKO-Knights

description:
一个骑士在一个无限的棋盘上移动。它可以执行的每一个动作都必须由一对整数 $(a,b)$ 来描述——表示这个骑士可以从 $(x,y)$ 移动到 $(x+a,y+b)$ 或者 $(x-a,y-b)$ 。每个骑士都有一组这样的移动描述，表示了骑士可以做出的移动。我们假设每一个骑士从 $(0,0)$ 出发移动到的所有位置不共线。

如果他们能从 $(0,0)$ 到达完全相同的坐标，我们就说两个骑士是等价的。(让我们指出，相同的骑士可以在不同的动作中到达这些方块)。可以看出，对于每一个骑士，都存在一对$(a,b)$，其移动仅由两对数字来描述。

你的任务是写一个程序，读入对骑士移动的表示，确定两对表示等价的骑士移动的整数，并输出这两对整数。

inputFormat: 第一行读入一个整数 $n$，表示有几个骑士（$3\le n\le 100$）。在以下 $n$ 行为表示骑士移动的整数对，每一行是一对整数。在这两行中，有两个整数 $a_i$ 和 $b_i$，并由一个空格分隔开，$-100\le a_i,b_i\le 100,(a_i,b_i)\neq (0,0)$。

outputFormat:
第一行输出两个整数 $a$ 和 $b$，并由一个空格分隔。

第二行输出两个整数 $c$ 和 $d$，并由一个空格分隔。

上述整数应满足以下条件：$-10000\le a,b,c,d\le 10000$，且输出的两对整数描述的骑士和输入数据中描述的骑士是等价的。


title: [POI2005] LOT-A Journey to Mars

background: Byteazar 决定去火星参加一个空间站旅行。

description:
火星的所有空间站都位于一个圆上，Byteazar 在其中一个空间站登陆然后开始绕圈旅行。

旅行需要耗费油料，一升油料只能跑 $1$ 米，每个空间站可以补给的油料都有所不同。

Byteazar 每到一个空间站便可以把该空间站的油料全部拿走（他的油箱是没有容量限制的）。但是如果走到某个时候突然没油了那么旅行便失败了。

Byteazar 需要决定要在哪个地方登陆使得他能顺利访问完所有的空间站后回到他当初登陆的地方，他登陆后可以选择两个方向中的任意一个进行旅行。

inputFormat:
第一行一个整数 $n$，代表空间站数量，所有空间站由 $1$ 至 $n$ 进行标号。

之后 $n$ 行，每行两个整数 $p_i,d_i$，第 $i + 1$ 行描述了第 $i$ 号空间站的信息，其中 $p_i$ 表示该空间站可以补给的油量，$d_i$ 则指明了它到 $i+1$ 号空间站的距离，对于 $n$ 号空间站，$d_i$ 表示它和 $1$ 号空间站的距离。

outputFormat:
输出 $n$ 行，每行一个字符串 `TAK` 或 `NIE`。

若你认为在 $i$ 号空间站登陆是可行的，则需要在第 $i$ 行输出 `TAK`，否则输出 `NIE`。

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

对于 $100\%$ 的数据，$3\le n\le10^6$，$p_i\ge0$，$d_i>0$，$\sum d_i\le2\times10^9$。


title: [POI2005] BAN-Bank Notes

description: `Byteotian Bit Bank(BBB)` 拥有一套先进的货币系统，这个系统一共有 $n$ 种面值的硬币，面值分别为 $b_1,b_2,\cdots,b_n$。但是每种硬币有数量限制，现在我们想要凑出面值 $k$，求最少要用多少个硬币。数据保证 $k$ 可以被凑出。

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

第二行 $n$ 个整数 $b_i$，表示这 $n$ 种硬币的面值。

第三行 $n$ 个整数 $c_i$，表示这 $n$ 种硬币的数量。

第四行一个整数 $k$。

outputFormat:
第一行一个整数，表示最少需要多少个硬币。

第二行 $n$ 个整数，表示第 $i$ 种硬币需要多少个。

如果有多种方案，输出其中一种即可。


title: [POI2005] SUM-Fibonacci Sums

description:
Fibonacci numbers are an integer sequence defined in the following way: $Fib_0=1$, $Fib_1=1$, $Fib_i=Fib_{i-1}+Fib_{i-2}$ (for $i\ge 2$). The first few numbers in this sequence are: ($1,1,2,3,5,8,\cdots$).

The great computer scientist Byteazar is constructing an unusual computer, in which numbers are represented in Fibonacci system i.e. a bit string $(b_1,b_2,\cdots,b_n)$ denotes the number $b_1\cdot Fib_1+b_2\cdot Fib_2+\cdots+b_n\cdot Fib_n$. (Note that we do not use $Fib_0$.) Unfortunately, such a representation is ambiguous i.e. the same number can have different representations. The number $42$, for instance, can be written as: $(0,0,0,0,1,0,0,1)$, $(0,0,0,0,1,1,1,0)$ or $(1,1,0,1,0,1,1)$. For this very reason, Byteazar has limited himself to only using representations satisfying the following conditions:

if $n>1$, then $b_n=1$, i.e. the representation of a number does not contain leading zeros.

if $b_i=1$, then $b_{i+1}=0$ (for $i=1,\cdots,n-1$), i.e. the representation of a number does not contain two (or more) consecutive ones.

The construction of the computer has proved more demanding than Byteazar supposed. He has difficulties implementing addition. Help him!

TaskWrite a programme which:

reads from the standard input the representations of two positive integers,calculates and writes to the standard output the representation of their sum.

inputFormat: The input contains the Fibonacci representations (satisfying the aforementioned conditions) of two positive integers $x$ and $y$ - one in the first, the other in the second line. Each of these representations is in the form of a sequence of non-negative integers, separated by single spaces. The first number in the line denotes the length of the representation $n$, $1\le n\le 1\ 000\ 000$. It is followed by $n$ zeros and/or ones.

outputFormat: In the first and only line of the output your programme should write the Fibonacci representation (satisfying the aforementioned conditions) of the sum $x+y$. The representation should be in the form of a sequence of non-negative integers, separated by single spaces, as it has been described in the Input section. The first number in the line denotes the length of the representation $n$, $1\le n\le 1\ 000\ 000$. It is followed by $n$ zeros and/or ones.

translation:
斐波那契数是一个这样定义的整数：$F(0)=1$，$F(1)=1$，$F(i)=F(i-1)+F(i-2)$  $(i>=2)$，前几个数是这样的 $1, 1, 2, 3, 5, 8, \ldots$

伟大的计算机学家 $\texttt{Byteazar}$ 正在做一个非凡的计算机，其中的数由斐波那契表示！

如一个数列 $b_1, b_2, \ldots , b_n$ 表示数字 $F(1) \times b_1+b_2 \times F(2)+ \ldots +b_n \times F(n)$（不使用 $F(0)$ ）。

不幸的是，这样的表示并不明确，即相同的数字可以有不同的表示。比如 $42$ 可以表示为 $(0,0,0,0,1,0,0,1)$，$(0,0,0,0,1,1,1,0)$ 或 $(1,1,0,1,0,1,1)$，于是  $\texttt{Byteazar}$ 加了一个限制：

- 如果 $n>1$，那么$b_n=1$，即数字的表示不包含前导零。
- 如果 $b_i=1$，那么 $b_{i+1}=0$，即数字的表示不包含两个（或多个）连续的数字。

这个计算机的建设比  $\texttt{Byteazar}$ 所认为的要难，现在请你来帮帮他~。

你需要写一个程序：

读取两个正整数的表示，计算并向标准输出写入其和的表示。

### 输入格式

输入的第一行先是一个正整数，为 $x$ 的斐波那契表示的长度，接下来的序列是 $x$ 的斐波那契表示。

第二行的第一个数字也是一个正整数，为 $y$ 的斐波那契表示的长度，接下来的序列是 $y$ 的斐波那契表示。

### 输出格式

输出只有一行程序，应写入$x+y$ 的和的斐波纳契表示（满足上述条件），同样是先输出一个正整数 $n$ ，表示 $x+y$ 的和的斐波纳契表示的长度，然后再输出 $x+y$ 的和的斐波那契表示。

$1\leq n \leq 10^6$。

感谢@codesonic 提供的翻译


title: [POI2005] KOS-Dicing

description:
Dicing is a two-player game and its outcome is fully random. Lately its popularity increases all over Byteotia. There is even a special club for dicing amateurs in the capital city of Byteotia. The club patrons take their time talking to each other and playing their favourite game with a randomly chosen opponent every once in a while. Everyone who wins the most games one day gains the title of the lucky chap. Sometimes it happens that the night at the club is a quiet one and only few games are played. It is a time when even one win can make you a lucky chap.

Once upon a time a most unlucky fellow, Byteasar, won the glorious title. He was so deeply shocked that he completely forgot how many games he had won. Now he is wondering how good his luck was and whether fortune finally smiled upon him - perhaps his luck changed for good? He knows exactly how many games and between whom were played that lucky night. However, he does not know the results. Byteasar desires to find out what is the smallest number of wins that could provide the title of the lucky chap. Be a good fellow and help him satisfy his curiosity!

TaskWrite a programme that:

for each game played reads from the standard input the pair of players who competed in it.

finds the smallest number $k$, such that a set of games' outcomes exists in which each player wins $k$ games at the most,writes the number $k$ and the results of games in the found set to the standard output.

Dicing 是一个两人玩的游戏,这个游戏在Byteotia非常流行. 甚至人们专门成立了这个游戏的一个俱乐部. 俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.

inputFormat: In the first line of the standard input there is a pair of integers $n$ and $m$ separated by a single space, $1\le n\le 10000$, $0\le m\le 10000$; $n$ denotes the number of players, while $m$ is the number of games. The players are numbered from $1$ to $n$. In the following $m$ lines there are pairs of players' numbers depicting the sequence of games, separated by single spaces. One pair may occur many times in the sequence.

outputFormat: The first line of the standard output should contain the determined number $k$. For each pair of players' numbers $a$, $b$ specified in the $i$'th line of the input, in the $i$'th line of the output the number $1$ should be written if the player no. $a$ wins against player no. $b$ in the found set of outcomes, or $0$ otherwise.

translation:
描述

掷骰子是一种双人游戏，它的结果是完全随机的。最近它在整个Byteotia变得非常流行。在Byteotia的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静，只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。

很久很久以前有一个很不走运的人，叫Byteasar，赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运，以及幸运之神是否最终会向他微笑——也许他的运气会变好？他确切地知道在那个幸运的晚上有多少场游戏以及是谁玩的。然而，他不知道结果。Byteasar希望查明至少要赢几场才能获得“幸运者”头衔。做个好人，帮他满足他的好奇心吧！

任务：写一个程序：

对于每场游戏从stdin读入这场游戏的一对玩家 找到最小的数k，使得存在一个游戏结果的集合，其中赢最多的玩家赢了k场。向stdout输出数k和找到的集合中游戏的结果

输入

stdin的第一行有一个一对由一个空格分开整数n和m (1 <= n, m <= 10000) 。n表示玩家数，m表示游戏数。玩家从1到n编号。在接下来的m行中有每场游戏的一对玩家的编号，由一个空格分开，描述了游戏的序列。一对玩家可能会在这个序列中多次出现。

输出

stdout的第一行应该包含一个确定的数k。对于在输入的第i行指定的一对玩家a, b，如果在找到的结果集合中a胜过b，则在输出的第i行输出1, 否则输出0.

感谢 @zyt1253679098  提供的翻译。


title: [POI2005] SZA-Template

description:
你打算在纸上印一串字母。

为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的**所有**字母印到纸上。

同一个位置的相同字符可以印多次。例如：用 `aba` 这个印章可以完成印制 `ababa` 的工作（中间的 `a` 被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用 `aba` 这个印章不可以完成印制 `abcba` 的工作。

因为刻印章是一个不太容易的工作，你希望印章的字符串长度尽可能小。

inputFormat: 输入一个长度不超过 $5 \times 10^5$ 的非空字符串（只包含小写字母），代表要在纸上印的字符。

outputFormat: 输出一个整数，代表印章上字符串长度的最小值。

hint:
印章为 `ababbaba`。

印制过程如下：

```plain
ababbababbabababbabababbababbaba
ababbaba
     ababbaba
            ababbaba
                   ababbaba
                        ababbaba
```


title: [POI2005] DZI-Hollows

description:
在 Byteotia 有两棵非常高的树，而每一棵的树干上都被挖出了许多洞，高度各不相同。现在 $n$ 只可以飞得非常快的鸟决定住在这些洞里，它们中的一些互相认识因此它们想要访问认识的的鸟。鸟们飞得非常快，而且通常沿着一条直线走。为了避免在飞行中撞到别的鸟，它们决定找到某种居住的方式可以满足下面的条件：

- 任何的鸟都可以访问它认识的鸟，而使访问的路线不与其他鸟访问的路线相交（但是可以有同一个终点）.

此外，还要使每只鸟居住的高度尽量低，保证树洞比鸟多。

我们都知道鸟的大脑很小，所以它们请你帮它们算一共有多少个方法可以满足以上条件，将答案模 $k$ 输出。

inputFormat:
在标准输入流的第一行有三个整数 $n，m$ 和 $k$，分别表示鸟的数量，鸟的关系数取模数（$2\le n\le 1000000,1\le m\le 10000000,2\le k\le 2000000$）。鸟的编号是 $1$ 到 $n$。

接下来 $m$ 行是鸟的认识关系，第 $i+1$ 行是两个数字 $a_i$和 $b_i$，用一个空格隔开。$1\le a,b\le n,a_i\ne b_i$。每一对认识的鸟只给出一次。

outputFormat: 设 $r$ 表示满足给定约束的鸟类的不同方案数。您的程序应该在标准输出的第一行中输出一个整数 $r\bmod k$。如果没有方案，则正确的结果为 $0$。


title: [POI2005] AKC-Special Forces Manoeuvres

description:
一个秘密组织正在沙漠中举行一次军事演习。本次演习的目标是拆除隐藏在沙漠中的一个炸弹。

演习的第一部分是空降作战。每个士兵**按照一定的顺序**从悬停在沙漠上空的直升机上跳下。着陆时，每个士兵都会停在他所在的着陆点。

每个空降兵都有一个生存半径。如果炸弹与他的距离小于或等于这个生存半径的话，空降兵便会牺牲自己引爆炸弹。指挥官希望能派出尽可能少的士兵，但他希望在**最坏情况下**至少有一个士兵能够生还。

整个沙漠可以抽象为一个平面，每个士兵的着陆点可以用一个坐标 $(x,y)$ 表示，他的生存半径我们设为 $r$。所有士兵的信息按照他们跳伞时的顺序给出，即第 $i$ 个士兵跳伞时，前 $i-1$ 个士兵都已经着陆。

你的任务是：从标准输入读入所有士兵的信息，输出最少需要派出的士兵数量。

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

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i,r_i$，代表第 $i$ 个士兵的着陆坐标为 $(x_i,y_i)$，生存半径为 $r_i$。

outputFormat:
如果无法让至少一个士兵生还的话，输出 `NIE`。

否则输出一个整数，代表至少需要派出的士兵数量。

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

最坏情况下炸弹位于 $(5,3)$，前三个士兵都会被炸死，第四个士兵会生还。


title: [POI2005] DWA-Two Parties

description:
拜占庭国王要举办两个大派对，并且希望邀请更多的居民。

国王从他的丰富经验里知道，如果一个居民在派对上能遇到偶数个的朋友，那他会非常高兴。因此，他要求你邀请国家的居民去两个派对，而使尽可能多的人在他们的聚会上有偶数个的朋友。

认识是一种对称关系，如 $A$ 认识 $B$，那么 $B$ 也认识 $A$。

inputFormat:
共 $N+1$ 行。

第一行读入一个整数 $N$（$1\le N\le 200$），表示居民的数量。

接下来 $N$ 行，第 $i+1$ 行是一个整数 $l_i$，表示第 $i$ 个居民的朋友数量，接着是 $l_i$ 个数，为第 $i$ 个居民的朋友编号。我们假设没有人是自己的朋友。如果 $B$ 出现在了 $A$ 的朋友列表中，那么 $A$ 也会出现在$B$ 的列表中。

outputFormat:
第一行是一个整数 $M$，是前往第一个排队的人数。第二行 $M$ 个整数，是去第一个派对的居民编号，其余的居民前往第二个派对。

如果有多种答案，你只需要输出一个。


title: [POI2005] DWU-Double-row

description:
$2n$ soldiers are standing in a double-row. They have to be rearranged, so that there are no equally tall soldiers in each row - then we shall say, that the soldiers are set up properly.

A single operation consists in swapping two soldiers who occupy the same position (but in different rows). Your task is to determine the minimum number of swaps necessary to set the soldiers up properly.

Example:

There is a double-row of $18$ soldiers in the figure. Arrows indicate the swaps that rearrange the soldiers in a proper way.

TaskWrite a programme that:

reads from the standard input the number and heights of soldiers, as they stand initially,determines the minimum number of swaps (of soldiers standing on the same position in different rows) necessary to set up soldiers properly,writes the result to the standard output.

**一句话题意By Scarlet：$2n$个数站成两排（每个数在$2n$个数中最多出现两遍），一次操作可以交换任意一列中两个数，求使每行数不重复的最少操作数。**

inputFormat:
In the first line of the input there is one integer $n$, $1\le n\le 50\ 000$. In each of the two rows there are $n$ soldiers standing. In each of the following two lines there are $n$ positive integers separated by single spaces. In the second line there are numbers $x_1,x_2,\cdots,x_n$, $1\le x_i\le 100\ 000$; $x_i$ denotes the height of the $i$'th soldier in the first line. In the third line there are numbers $y_1,y_2,\cdots,y_n$, $1\le y_i\le 100\ 000$; $y_i$ denotes the height of the $i$'th soldier in the second line.

It is guaranteed that in the instances from the test data it is possible to set up soldiers properly.

outputFormat: In the first and only line of the standard output one integer should be written - the minimum number of swaps necessary to set up soldiers properly.

translation:
题目描述

有2n个士兵站成两排，他们需要被重新排列，以保证每一排里没有同样高的士兵——这样我们就说，士兵们被合理地安排了位置。 每次操作可以交换两个在同一位置（但不在同一排）的士兵。你的任务是用最少的操作来确保士兵们被合理地安排了位置。 例如： 有18个士兵站成两排，箭头标明了重新安排士兵位置的正确方式（图飞了?）。 写一个这样的程序： 读入n与士兵的身高，以及他们最初所站的位置，确保以最小的交换（站在同一位置的不同排的士兵）的次数来合理地安排士兵的位置，输出操作数。

输入格式

第一行为一个整数n（1<=n<=50000），接下来的两行每行有n个数表示每行站着的n个士兵的身高（1<=士兵的身高<=100000）。 数据保证你能够合理地安排士兵的位置（即每个数在2n个数中最多出现两次）。

输出格式

只有一行，输出最小操作数。
![](https://cdn.luogu.org/upload/pic/14829.png)
翻译贡献者UID：57699


title: [POI2005] AUT-The Bus

description:
The streets of Byte City form a regular, chessboardlike network - they are either north-south or west-east directed. We shall call them NS- and WE-streets. Furthermore, each street crosses the whole city. Every NS-street intersects every WE- one and vice versa. The NS-streets are numbered from $1$ to $n$, starting from the westernmost. The WE-streets are numbered from $1$ to $m$, beginning with the southernmost. Each intersection of the $i$'th NS-street with the $j$'th WE-street is denoted by a pair of numbers $(i,j)$ (for $1\le i\le n$, $1\le j\le m$).

There is a bus line in Byte City, with intersections serving as bus stops. The bus begins its itinerary by the $(1,1)$ intersection, and finishes by the $(n,m)$ intersection. Moreover, the bus may only travel in the eastern and/or northern direction.

There are passengers awaiting the bus by some of the intersections. The bus driver wants to choose his route in a way that allows him to take as many of them as possible. (We shall make an assumption that the interior of the bus is spacious enough to take all of the awaiting passengers, regardless of the route chosen.)TaskWrite a programme which:

reads from the standard input a description of the road network and the number of passengers waiting at each intersection,finds, how many passengers the bus can take at the most,writes the outcome to the standard output.

inputFormat:
The first line of the standard input contains three positive integers $n$, $m$ and $k$ - denoting the number of NS-streets, the number of WE-streets and the number of intersections by which the passengers await the bus, respectively ($1\le n\le 10^9$, $1\le m\le 10^9$, $1\le k\le 10^5$).

The following $k$ lines describe the deployment of passengers awaiting the bus, a single line per intersection. In the $(i+1)$'st line there are three positive integers $x_i$, $y_i$ and $p_i$, separated by single spaces, $1\le x_i\le n$,$1\le y_i\le m$,$1\le p_i\le 10^6$ . A triplet of this form signifies that by the intersection$(x_i,y_i)p_i$ passengers await the bus. Each intersection is described in the input data once at the most. The total number of passengers waiting for the bus does not exceed $1\ 000\ 000\ 000$.

outputFormat: Your programme should write to the standard output one line containing a single integer - the greatest number of passengers the bus can take.

translation: Byte City 的街道形成了一个标准的棋盘网络，他们要么是北南走向要么就是西东走向。北南走向的路口从 $1$ 到 $n$ 编号, 西东走向的路从 $1$ 到 $m$ 编号。 每个路口用两个数 $(i,j)$ 表示 $(1 \le i \le n, 1 \le j \le m)$。 Byte City 里有一条公交线, 在某一些路口设置了公交站点。 公交车从 $(1, 1)$ 发车, 在 $(n, m)$ 结束。公交车只能往北或往东走。 现在有一些乘客在某些站点等车。 公交车司机希望在路线中能接到尽量多的乘客。帮他想想怎么才能接到最多的乘客。


title: [POI2005] LUS-Mirror Trap

description:
A mirror trap is a cuboid made of mirrors, the reflecting sides of which are facing the interior of the cuboid. Precisely in the geometric centre of the cuboid there is a miniature laser (whose dimensions we shall neglect). The task is to aim the laser in such a way that the beam travels the longest total distance possible and returns to the laser itself. By total distance we shall denote the sum of distances traveled by the laser beam in each of the three directions parallel to the edges of the mirrors (i.e. we are using the so called Manhattan (city) metric).

镜子陷阱是由镜子构成的长方体，镜子的反射面对着长方体的内部。在长方体的几何中心放入一个微型激光器（尺寸忽略）。现在我们的任务是把激光向某一个方向发射，并且使光束在回到激光器自身之前，通过的总距离尽可能长。通过的总距离表示为激光束在与镜子反射面平行的三个方向的距离之和，也就是曼哈顿（城市）度量。

The dimensions of the trap are even integers. The edges and vertices of the trap, where distinct sides meet, do not reflect the laser beam. Inside the cuboid we shall introduce a cartesian coordinate system. Its axes are parallel to the edges of the trap and the laser shall be placed in the origin. The laser may be aimed at any integer point (a point whose all coordinates are integers) within the trap, the points on the surface of the mirrors included (with the single exception of the laser itself, i.e. the point $(0,0,0)$).

不同的侧面相遇的陷阱的边和顶点不会反射激光束，且陷阱的边长是整数。在长方形陷阱中，使用笛卡尔坐标系。坐标系的纵横轴分别平行于陷阱的长和宽，激光器的位置在原点。激光器可以瞄准陷阱内的任意一个点包括反射镜的表面上的点（唯一的例外就是激光器本身，点（0,0,0））。

TaskWrite a programme which:

reads from the standard input the dimensions of the mirror trap,calculates such a point, that a laser beam fired from the laser it the direction of this point:

shall be reflected from the mirrors (but not necessarily from all of them),  shall neither intersect an edge nor a vertex of the mirror trap,  shall return to the laser, possibly from a different direction,  shall travel the longest total distance possible (in the sense of the definition provided).

writes the outcome to the standard output.

我们的任务：

输入这个镜子陷阱的尺寸，通过编写的程序计算出一个点，即激光器指向这一点：这一束激光应在反射镜（但不一定是所有反射镜）反射，但是不与陷阱的边、顶点相交，最后需要回到激光器本身（不需要一定的方向）同时尽可能使得总距离长。

inputFormat:
A single test consists of many mirror traps to be analysed. The first line of the standard input contains a single integer $1\le K\le 1000$, denoting the number of traps to be analysed. In the lines $2..K+1$ there are descriptions of the traps, a single per line. The description of the trap consists of three numbers $5\le x,y,z\le 1000$, separated by single spaces. The mirror trap has the dimensions of $2x\times 2y\times 2z$.

输入有多个陷阱。输入的第一行包含一个整数 K（1≤K≤1000），表示要分析的陷阱数。 在2.K + 12..K + 1行中，有一个陷阱的描述，每行一个。 陷阱的描述由三个用空格分隔的数字5≤x，y，z≤1000组成。 镜面陷阱的尺寸为2x×2y×2z。

outputFormat:
Your programme should write exactly $K$ lines to the standard output. The $i$'th line should contain a solution for the $i$'th trap: three integers $k_x,k_y,k_z$separated by single spaces, $-x\le k_{x}\le x$, $-y\le k_{y}\le y$, $-z\le k_{z}\le z$,$ \{k_{x},k_{y},k_{z}\}\neq\{0,0,0\}$. Those numbers signify that in the $i$'th trap the laser should be aimed at the point, whose coordinates are $\{k_{x},k_{y},k_{z}\}$.

Should there be a greater number of correct solutions, your programme ought to output any one of them.

输出K行。 第K行应包含第K个陷阱的解决方案，由空格分隔的3个数x，y，z，表示激光器需要瞄准的点的坐标。

如果有多个不同的正确解决方案，则任意的输出一个。

hint: 感谢@SLYZ\_0120 提供翻译。


title: [POI2005] PRA-Dextrogyrate Camel

background: 征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

description:
Byteotia consists of $N$ oasis in the desert, no three of which are collinear. Byteasar lives in one of these oasis and moreover he has an acquaintance in every other. Byteasar wants to pay a visit to as many of them as possible. He plans to travel on the back of his camel. The camel is as obstinate as a mule and thus moves in its own peculiar way:

After departure from an oasis it moves along a straight line, until it gets to another oasis.

The camel turns only at oasis, but it turns only right (clockwise) and by an angle from the interval $[0\degree,180\degree]$ (the camel makes only one turn at an oasis, i.e. it will not turn by f.i. $200\degree$ as a result of two subsequent turns by $100\degree$).

The camel doesn't want to follow its own footprints.

Help Byteasar in planning such a route that he will be able to visit as many friends as possible. It should both begin and end in the oasis where Byteasar lives. It has to consist of segments connecting subsequently visited oasis. The route may not pass through any point two times, except the Byteasar's oasis, where the camel turns up twice: at the beginning and the end of the journey.

Byteasar's camel is initially facing a certain oasis and it has to start moving toward it. The direction the camel faces after returning from the journey is of no importance.

TaskWrite a programme that:

reads from the standard input the camel's coordinates and the direction it faces as well as the coordinates of the Byteotian oasis,determines the maximum number of friends Byteasar can pay a visit to while sticking to the presented rules,writes the result to the standard output.

Byteotia大陆由沙漠中的N个绿洲组成，没有三个绿洲是共线的。Byteasar住在其中的一个绿洲中，而他在每个绿洲里都有一个朋♂友。Byteasar想骑羊驼出去旅行一趟，拜访尽量多的朋友。这只羊驼非常固执，它只以它独特的方式前进： 离开一个绿洲后，它只沿一条直线前进，直到它到达另一个绿洲； 它只在绿洲里转弯，但它只朝右转（顺时针），并且角度在[0°,180°]内（它在一个绿洲只做一次转弯，也就是说，它不会转超过180°）；它的路线不会交叉，也就是说，它不会经过任何一个点两次（除了出发点）。 请你帮助Byteasar（的羊驼）设计一条路线，让他能访问尽量多的朋♂友。这条路线必须从Byteasar住的绿洲出发，最后回到原处。Byteasar最初在绿洲1,他的骆驼首先面朝绿洲2

inputFormat:
In the first line of the standard input there is one integer $N$ ($3\le N\le 1\ 000$) - the number of oasis in Byteotia. The oasis are numbered from $1$ to $N$. Byteasar lives in the oasis no. $1$ and his camel is facing the oasis no. $2$. In the following $N$ lines the coordinates of the oasis are given. In the $(i+1)$'th line there are two integers $x_i$, $y_i$ - the horizontal and vertical coordinate of the $i$'th oasis - separated by a single space. All coordinates are from the interval from $-16\ 000$ to $16\ 000$.

第一行，输入一个整数N(3≤N≤1,000)代表Byteotia大陆中的绿洲数。

绿洲被从1到N编号，Byteasar住在1号绿洲，而他的羊驼面向2号绿洲。

接下来的N行输入，第（i+1）行有两个整数xi,yi（-16,000≤xi,yi≤16,000）代表i号绿洲的横纵坐标，他们之间被一个空格隔开。

outputFormat:
In the first and only line of the standard output your programme should write one integer - the maximum number of friends Byteasar can visit.

只有一行输出，即Byteasar能拜访的最多的好♂友数量。

hint:
样例解释：

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

感谢@Paperback\_Writer 提供翻译


title: [POI2006] KRA-The Disks

description:
Johnny 在他生日的那天收到了来自他父母的生日礼物：一个管子和一套圆盘。管子由若干个高度相等的圆柱体组合而成，并且每个圆盘拥有和每段圆柱相同的高度，每个圆柱体上开大小不同的孔。

Johnny 收到这套礼物后，发明了一个小游戏：他按一定顺序将圆盘放入管子当中，他想算出最后一个圆盘会停在哪个深度。

显然，有两种情况会让圆盘停止掉落：其一是圆盘无法通过小孔（即孔的直径小于圆盘的直径），其二则是被其他圆盘挡住。

Johnny 被他自己发明的游戏难住了，他现在把这个问题交给了你，你一定会帮助他解决这个难题的！

inputFormat:
第一行两个整数 $n$ 和 $m$，分别代表管子的深度和圆盘的数量。

下一行 $n$ 个整数 $r_i$，代表第 $i$ 层管子小孔的直径。

第三行 $m$ 个整数 $k_i$，代表第 $i$ 个放入管子的圆盘的直径。

outputFormat:
输出一个整数，代表最后一个圆盘会停留在第几层。

如果最后一个圆盘无法放入管子，则输出 $0$。

hint: $1 \leq n,m \leq 3 \times 10^5$，$1 \leq r_i,k_i \leq 10^9$


title: [POI2006] OKR-Periods of Words

description:
A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn't have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task Write a programme that:

reads from the standard input the string's length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

inputFormat: In the first line of the standard input there is one integer $k$ ($1\le k\le 1\ 000\ 000$) - the length of the string. In the following line a sequence of exactly $k$ lower-case letters of the English alphabet is written - the string.

outputFormat: In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

translation:
对于一个仅含小写字母的字符串 $a$，$p$ 为 $a$ 的前缀且 $p\ne a$，那么我们称 $p$ 为 $a$ 的 proper 前缀。

规定字符串 $Q$ 表示 $a$ 的周期，当且仅当 $Q$ 是 $a$ 的 proper 前缀且 $a$ 是 $Q+Q$ 的前缀。若这样的字符串不存在，则 $a$ 的周期为空串。

例如 `ab` 是 `abab` 的一个周期，因为 `ab` 是 `abab` 的 proper 前缀，且 `abab` 是 `ab+ab` 的前缀。

求给定字符串所有前缀的最大周期长度之和。


title: [POI2006] PRO-Professor Szu

description:
某大学校内有一栋主楼，还有 $n$ 栋住宅楼。这些楼之间由一些单向道路连接，但是任意两栋楼之间可能有多条道路，也可能存在起点和终点为同一栋楼的环路。存在住宅楼无法到达主楼的情况。

现在有一位古怪的教授，他希望每天去主楼上班的路线不同。

一条上班路线中，每栋楼都可以访问任意多次。我们称两条上班路线是**不同的**，当且仅当两条路线中存在一条路是不同的（两栋楼之间的多条道路被视为是不同的道路）。

现在教授希望知道，从哪些住宅楼前往主楼的上班路线数最多。

inputFormat:
第一行两个整数 $n,m$，分别为大学内住宅楼的数量和道路的数量。大学内所有住宅楼编号为 $1 \sim n$，主楼编号为 $n+1$。

接下来 $m$ 行，第 $i$ 行两个整数 $u_i,v_i$，代表大学内存在一条从 $u_i$ 号楼到 $v_i$ 号楼的道路。

outputFormat:
第一行：如果存在一栋楼到主楼的上班路线数超过了 $36500$，输出 `zawsze`。否则输出一个整数，代表从一栋住宅楼前往主楼的最多上班路线数。

第二行：输出一个整数 $p$，代表有多少栋住宅楼能使前往主楼的上班路线数最大化。特别地，如果最大上班路线数超过了 $36500$，那么这一行请输出能使上班路线数超过 $36500$ 的住宅楼的数量。

第三行：按编号从小到大的顺序输出 $p$ 个整数，代表能使前往主楼的上班路线最大化的住宅楼的编号。特别地，如果最大上班路线数超过了 $36500$，那么这一行请输出所有能使上班路线数超过 $36500$ 的住宅楼的编号。

translation: $1 \leq n,m \leq 10^6$，$1 \leq u_i,v_i \leq n+1$。


title: [POI2006] TET-Tetris 3D

description:
The authors of the game "Tetris" have decided to make a new, three-dimensional version, in which cuboids would fall down on a rectangular platform. The blocks fall down separately in a certain order, just like in the two-dimensional game. A block falls down until it reaches an obstacle: the platform or another block, that has already stopped - then it stops and remains in this exact position till the game is over.

However, the authors wanted to change the spirit of the game, turning it from a simple arcade-game into a play far more puzzling. Knowing the order of the falling blocks and their flight path the player's task is to tell the height of the highest point of the arrangement after all blocks have fallen down (and stopped). All the blocks are falling down vertically and do not rotate while falling. For convenience we'll introduce a cartesian coordinate system on the platform, with the center in one of the platform's corners and the axes parallel to the platform's edges.

Write a programme that automates verification of the player's answer.

TaskWrite a programme that:

reads the descriptions of subsequent falling blocks from the standard input,determines the height of the highest point of the arrangement of blocks after all have fallen down and stopped,writes the result to the standard output.

inputFormat:
In the first line of the input there are three integers $D$, $S$ and $N$ ($1\le N\le 20\ 000$, $1\le D,S\le 1\ 000$), separated by single spaces and denoting respectively: the length and the depth of the platform and the number of blocks that are going to fall down on it. In the following $N$ lines the descriptions of subsequent blocks are given, one in each line.

Each description of a block consists of five integers: $d$,$s$,$w$,$x$ and $y$ ($1\le d$, $0\le x$, $d+x\le D$, $1\le s$, $0\le y$, $s+y\le S$, $1\le w\le 100\ 000$), representing a block of length $d$ depth $s$ and height $w$. This very block will be be falling down on the platform with its $d\times s$ face as the bottom, where the length and depth of the block are parallel to those of the platform. The coordinates of the vertices of the projection of the block on the platform are: $(x,y)$, $(x+d,y)$, $(x,y+s)$ and $(x+d,y+s)$.

outputFormat: The first and only line of the standard output should contain exactly one integer, the height of the highest point of the arrangement of blocks after all have fallen down and stopped.

translation:
### 题目描述

最近，有人发明了一种三维版的俄罗斯方块。和二维版本类似，一些立方体按照一定的顺序掉落，直到碰到别的方块或是地面才会停止掉落。立方体停止掉落后会一直保持掉落时的位置，直到游戏结束。

你的朋友决定以这个新版本的俄罗斯方块为背景，出一道题。给出每个立方体的掉落顺序和其掉落的轨迹，在所有方块完成掉落后求出最高方块的高度。在这个游戏中，方块均垂直下落，且方块不会旋转或翻转。为了方便描述，我们会建立一个空间直角坐标系，该坐标系的原点为地面的一角，并且坐标轴与地面边缘平行。

现在轮到你解决这个问题了。

### 输入格式

第一行三个整数 $D,S,N$，分别为地面的长度，宽度，和将要掉落的立方体数量。

接下来 $N$ 行，每行五个整数 $d_i,s_i,w_i,x_i,y_i$，描述一个掉落的立方体。其中 $d_i,s_i,w_i$ 分别代表立方体的长，宽，高。立方体的底面（即长 $\times$ 宽的那一面）将正对地面。立方体底面四个角在地面的投影坐标分别为 $(x_i,y_i)$，$(x_i+d_i,y_i)$，$(x_i,y_i+s_i)$，$(x_i+d_i,y_i+s_i)$。

### 输出格式

输出一个整数，即方块掉落结束后最高方块的高度。

### 数据范围

$1 \leq N \leq 20\,000$，$1 \leq D,S \leq 1\,000$，$d_i,s_i \geq 1$，$1 \leq w_i \leq 100\,000$，$0 \leq x_i,d_i+x_i \leq D$，$0 \leq y_i,s_i+y_i \leq S$。


title: [POI2006] ZAB-Frogs

description:
A scourge of frogs destroying all the crop has started in Byteotia. A farmer named Byteasar has decided to fight the vermin with peculiar "scarefrogs", that he has set up at certain points of his field. While moving from one place to another, every frog tries to keep as far of them as possible, i.e. maximizes the distance to the closest scarefrog.

The field that belongs to Byteasar has rectangular shape. The frogs leap in directions parallel to the field's sides and their leaps are unitary (of length 1). The scarefrogs-distance, for a given frog's route, is the minimum of all distances from all scarefrogs at all inter-leap-points of the route.

Byteasar already knows the most common starting and destination points of the frogs' routes, therefore he experiments with various deployments of the scarefrogs. He asks you for help, namely he would like you to write a programme that calculates the maximum (over all routes) scarefrogs-distance for a given deployment of scarefrogs - which we call in short the frogshold distance.

TaskWrite a programme that:

reads from the standard input the size of the field, the coordinates of the screfrogs and the source and target position of a frog,determines the frogshold distance (the maximum scarefrogs-distance a frog may achieve while still being able to reach the target point)writes the square of this number to the standard output.

给定一个网格图，其中有一些坏点，要求使起点到终点的路径上的所有点到离该点最近的坏点的最小距离距离最大，求这个最大值。

inputFormat: The first line of the input contains two integers: $w_x$ and $w_y$ separated by a single space - the breadth and length of the field ($2 \le w_x, w_y \le 1000$). The second line of the input contains four integers: $p_x$, $p_y$, $k_x$ and $k_y$ separated by single spaces; $(p_x, p_y)$ is the initial position of the frog, $(k_x, k_y)$is the target (final) position of the frog ($1 \le p_x, k_x \le w_x$, $1 \le p_y, k_y \le w_y$). The third line of the standard input contains one integer $n$ - these are the coordinates of the ith scarefrog ($1 \le n \le w_x \cdot w_y$). No two scarefrogs occupy the same position and none of them is at the point $(p_x, p_y)$ nor $(k_x, k_y)$.

outputFormat: In the first and only line of the standard output one integer should be written, namely the square of the frogshold distance. If the frog cannot avoid leaping directly on some scarefrog the result is 0.