title: 封印

background: 很久以前，魔界大旱，水井全部干涸，温度也越来越高。为了拯救居民，夜叉族国王龙溟希望能打破神魔之井，进入人界“窃取”水灵珠，以修复大地水脉。可是六界之间皆有封印，神魔之井的封印由蜀山控制，并施有封印。龙溟作为魔界王族，习有穿行之术，可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙！ 龙溟无奈之下只能强行破除封印。破除封印必然消耗一定的元气。为了寻找水灵珠，龙溟必须减少体力消耗。他可以在破除封印的同时使用越行术。

description: 神魔之井的封印共有  $n$ 层，每层封印都有一个坚固值。身为魔族的龙溟单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数  $n$ 的平方的乘积； 但他也可以打破第 i 层到第 j 层之间的所有封印( $i<j$)，总元气消耗为第  $i,j$ 层封印的坚固值之和与第  $i,j$ 层之间所有封印层（包括第  $i,j$ 层）的坚固值之和的乘积，但为了不惊动蜀山，第  $i,j$ 层封印的坚固值之和不能大于  $t$ （单独打破可以不遵守）。

inputFormat:
第一行包含两个正整数  $n$ 和  $t$。
第二行有  $n$ 个正整数，第  $i$ 个数为  $a_i$，表示第  $i$ 层封印的坚固值。

outputFormat: 仅一行，包含一个正整数，表示最小消耗元气。

hint:
#### 样例解释
先单独打破第一层，再用越行术从第二层直接打破到最后一层。 这样消耗元气  $8 \times 6^2 + (5 + 5) \times (5 + 7 + 9 + 3 + 5) = 578$。
#### 数据范围
对于  $10\%$ 的数据， $n\le10$；
对于  $50\%$ 的数据， $n\le100$；
对于  $70\%$ 的数据， $n\le500$；
对于  $100\%$ 的数据， $n\le1000$， $a_i(1 \le i \le n) , t \le 20000$。


title: [国家集训队] 圈地计划

type: P

description: 最近房地产商 GDOI(Group of Dumbbells Or Idiots) 从 NOI(Nuts Old Idiots) 手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为 $N\times M$ 块小区域。GDOI 要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第 $i$ 行第 $j$ 列的区域，建造商业区将得到 $A_{i,j}$ 收益，建造工业区将得到 $B_{i,j}$ 收益。另外不同的区域连在一起可以得到额外的收益，即如果区域 $(i,j)$ 相邻（相邻是指两个格子有公共边）有 $k$ 块（显然 $k$ 不超过 $4$）类型不同于 $(i,j)$ 的区域，则这块区域能增加 $k\times C_{i,j}$ 收益。经过 Tiger.S 教授的勘察，收益矩阵 $A,B,C$ 都已经知道了。你能帮 GDOI 求出一个收益最大的方案么？

inputFormat:
输入第一行为两个整数，分别为正整数 $N$ 和 $M$，分别表示区域的行数和列数；

第 $2$ 到 $N+1$ 行，每行 $M$ 个整数，表示商业区收益矩阵 $A$；

第 $N+2$ 到 $2N+1$ 行，每行 $M$ 个整数，表示工业区收益矩阵 $B$；

第 $2N+2$ 到 $3N+1$ 行，每行 $M$ 个整数，表示相邻额外收益矩阵 $C$。

outputFormat: 输出只有一行，包含一个整数，为最大收益值。


title: 水晶灯火灵

background:
《爱与愁的故事第五弹·Halloween》第二章。

题目容易吐血请谨慎阅读！

description:
爱与愁大神兴高采烈地踏出妖精系道馆——他已经获得了妖精系徽章（鼓掌）！可是一出门就遇到一群パンプジン（Because today is Halloween）！仲谋半？没事，爱与愁大神手上还仅存着一只水晶灯火灵（完克パンプジン）。或许是因为这是爱与愁大神存活的最后一只精灵，水晶灯火灵十分振奋，一击打垮了一群パンプジン。水晶灯火灵使用了一招***（被打上了马赛克？！），刚好符合以下③条规则：

1. $m,n \in \{1,2,\cdots ,k\}$；
2. $(n^2-m\times n-m^2)^2=1$；
3. $m,n$ 为整数。

爱与愁大神非常高兴，他想要知道 $m^2+n^2$ 的最大值，以及在什么情况下可以取得最大值。你能帮助他吗？请输出 $m$ 和 $n$。

inputFormat: 输入共一个整数 $k$。

outputFormat: 共两行，第一行是 $m$ 的最大值，第二行是 $n$ 的最大值。


title: [USACO10MAR] Barn Allocation G

description:
Farmer John recently opened up a new barn and is now accepting stall allocation requests from the cows since some of the stalls have a better view of the pastures.

The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered 1..N; stall i has capacity C\_i cows (1 <= C\_i <= 100,000). Cow i may request a contiguous interval of stalls (A\_i, B\_i) in which to roam (1 <= A\_i <= N; A\_i <= B\_i <= N), i.e., the cow would like to wander among all the stalls in the range A\_i..B\_i (and the stalls must always have the capacity for her to wander).

Given M (1 <= M <= 100,000) stall requests, determine the maximum number of them that can be satisfied without exceeding stall

capacities.

农夫约翰最近开了一个新的牲口棚屋，并且现在接受来自奶牛的分配畜栏请求因为其中的一些畜栏有更好风景。

畜栏包括N个畜栏(1 ≤ N ≤ 100,000)，方便起见，我们把它们编号为1..N，畜栏i能容纳Ci只牛(1 ≤ Ci ≤ 100,000)，第i只牛需要连续编号畜栏（从Ai到Bi）来漫步其中，

(1 ≤ Ai ≤ N; Ai ≤ Bi ≤ N)，换言之，这只牛想要在编号范围为Ai..Bi的畜栏漫步（所有它想要畜栏必须实施为它空出位置来供它散步）

给出M个畜栏分配请求（1 ≤ M ≤ 100,000），回答最多能满足多少只牛的要求（不增加另外畜栏）

考虑以下例子：

```cpp
畜栏号:    1   2   3   4   5
           +---+---+---+---+---+
容纳空间:  | 1 | 3 | 2 | 1 | 3 |
           +---+---+---+---+---+
Cow 1       XXXXXXXXXXX             (1, 3)
Cow 2           XXXXXXXXXXXXXXX     (2, 5)
Cow 3           XXXXXXX             (2, 3)
Cow 4                   XXXXXXX     (4, 5)
```
约翰显然不能满足所有的牛，因为畜栏3，4请求太多了

经过试验，我们发现，我们能满足牛1，3，4需要，所以这组数据答案为3

inputFormat:
第一行包括两个以空格隔开的正整数：N,M

第二行到第N+1行：第i+1行包括一个整数：Ci

第N+2到第N+M+1行：第i+N+1 包括两个整数Ai、Bi

outputFormat: 仅一行：能满足的最大需要

hint:
Source: USACO 2010 March Gold

Translator: @chrome01


title: [USACO09NOV] Job Hunt S

description:
Bessie is running out of money and is searching for jobs. Farmer John knows this and wants the cows to travel around so he has imposed a rule that his cows can only make D (1 <= D <= 1,000) dollars in a city before they must work in another city. Bessie can, however, return to a city after working elsewhere for a while and again earn the D dollars maximum in that city. There is no limit on the number of times Bessie can do this.

Bessie's world comprises P (1 <= P <= 150) one-way paths connecting C (2 <= C <= 220) cities conveniently numbered 1..C. Bessie is currently in city S (1 <= S <= C). Path i runs one-way from city A\_i to city B\_i (1 <= A\_i <= C; 1 <= B\_i <= C) and costs nothing to traverse.

To help Bessie, Farmer John will give her access to his private jet service. This service features F (1 <= F <= 350) routes, each of which is a one way flight from one city J\_i to a another K\_i (1 <= J\_i <= C; 1 <= K\_i <= C) and which costs T\_i (1 <= T\_i <= 50,000) dollars. Bessie can pay for the tickets from future earnings if she doesn't have the cash on hand.

Bessie can opt to retire whenever and wherever she wants. Given an unlimited amount of time, what is the most money that Bessie can make presuming she can make the full D dollars in each city she can travel to?  Print -1 if there is no limit to this amount.

奶牛们正在找工作。农场主约翰知道后，鼓励奶牛们四处碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚D（1≤D≤1000）美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵子后又回到原来的城市再最多赚D美元。而且这样的往返次数没有限制。

城市间有P（1≤P≤150）条单向路径连接，共有C（2≤C≤220）座城市，编号从1到C。奶牛贝茜当前处在城市S（1≤S≤C）。路径i从城市A\_i到城市B\_i（1≤A\_i≤C，1≤B\_i≤C），在路径上行走不用任何花费。

为了帮助贝茜，约翰让它使用他的私人飞机服务。这项服务有F条（1≤F≤350）单向航线，每条航线是从城市J\_i飞到另一座城市K\_i（1≤J\_i≤C，1≤K\_i≤C），费用是T\_i（1≤T\_i≤50000）美元。如果贝茜手中没有现钱，可以用以后赚的钱来付机票钱。

贝茜可以选择在任何时候，在任何城市退休。如果在工作时间上不做限制，贝茜总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出-1。

inputFormat:
第一行：5个用空格分开的整数D，P，C，F，S。

第2到第P+1行：第i+1行包含2个用空格分开的整数，表示一条从城市A\_i到城市B\_i的单向路径。

接下来F行，每行3个用空格分开的整数，表示一条从城市J\_i到城市K\_i的单向航线，费用是T\_i。

outputFormat: 一个整数，在上述规则下最多可以赚到的钱数。

hint:
This world has five cities, three paths and two jet routes. Bessie starts out in city 1, and she can only make 100 dollars in each city before moving on.

Bessie can travel from city 1 to city 5 to city 2 to city 3, and make a total of 4\*100 - 150 = 250 dollars.

Source: USACO 2009 November Silver

这个世界上有五个城市，三条单向路径和两条单向航线。贝茜从一号城市开始她的旅行，她在离开一个城市前最多只能在这个城市赚100美元。

贝茜可以通过从一号城市-->五号城市-->二号城市-->三号城市的旅行赚到4\*100-150=250美元。

(注:在四个城市各赚100美元,从五号城市飞到二号城市花掉150美元)

来源:USACO 2009 十一月银组


title: 矩阵加速（数列）

description:
已知一个数列 $a$，它满足：

$$
a_x=
\begin{cases}
 1 & x \in\{1,2,3\}\\
 a_{x-1}+a_{x-3} & x \geq 4
\end{cases}
$$

求 $a$ 数列的第 $n$ 项对 $10^9+7$ 取余的值。

inputFormat:
第一行一个整数 $T$，表示询问个数。

以下 $T$ 行，每行一个正整数 $n$。

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


title: Reversible Number

background: 欧拉工程 145 有改动

description:
Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10^x)?

有些正整数n可能满足n + 回文(n)（回文(n)是把n倒过来写所得的数）得到的结果的各位都是奇数。

比方说，n=36时，36+63=99;

n=409时，409+904=1313。

规定满足上述的n称为reversible数。所以36,63,409,904都是reversible数。

当然，以0开头的数统统不算啦~

那么，小于等于10^x的Reversible数有多少个？方便起见，x是大于等于3小于等于400的正整数。

inputFormat: 一个正整数x

outputFormat: reversible数的数量

hint: 30%的数据的输出在2^32-1范围内


title: [NOIP2014 提高组] 飞扬的小鸟

background: NOIP2014 提高组 D1T3

description:
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 $n$，高为 $m$ 的二维平面，其中有 $k$ 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 $1$，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 $x$，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 $y$。小鸟位于横坐标方向不同位置时，上升的高度 $x$ 和下降的高度 $y$ 可能互不相同。

小鸟高度等于 $0$ 或者小鸟碰到管道时，游戏失败。小鸟高度为 $m$ 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

inputFormat:
第 $1$ 行有 $3$ 个整数 $n, m, k$，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 $n$ 行，每行 $2$ 个用一个空格隔开的整数 $x$ 和 $y$，依次表示在横坐标位置 $0 \sim n-1$ 上玩家点击屏幕后，小鸟在下一位置上升的高度 $x$，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 $y$。

接下来 $k$ 行，每行 $3$ 个整数 $p,l,h$，每两个整数之间用一个空格隔开。每行表示一个管道，其中 $p$ 表示管道的横坐标，$l$ 表示此管道缝隙的下边沿高度，$h$ 表示管道缝隙上边沿的高度（输入数据保证 $p$ 各不相同，但不保证按照大小顺序给出）。

outputFormat:
共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 $1$，否则输出 $0$。

第二行，包含一个整数，如果第一行为 $1$，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

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

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

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

【数据范围】

对于 $30\%$ 的数据：$5 \leq n \leq 10, 5 \leq m \leq 10, k=0$，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $50\%$ 的数据：$5 \leq n \leq 20, 5 \leq m \leq 10$，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $70\%$ 的数据：$5 \leq n \leq 1000, 5 \leq m \leq 100$；

对于 $100\%$ 的数据：$5 \leq n \leq 10000$，$5 \leq m \leq 1000$，$0 \leq k < n$，$0 < x,y < m$，$0 < p < n$，$0 \leq l < h \leq m$， $l + 1 < h$。


title: 词编码

description:
一个发送机可以通过一条隧道发送一些以二进制代码组成的单词。在其尽头的接收机可以使用特殊技术恢复到最初的单词。每个单词最初都由0和1组成。所有的单词最初长度都为n（4<=n<=1000）。当穿过隧道之后单词可能发生以下几种情况之一：

1. 任意（一个）0被1取代
2. 任意（一个）符号被删除
3. 一个符号（0或1）被插入到任何位置
4. 不改变

我们知道最初的单词都具有以下性质：有1的位置号的总和是n+1的倍数，或者是0.

inputFormat: n和转换后的单词，每个单词占一行。单词数不大于2001，不会有其他任何东西，除了一些空格和空行。

outputFormat:
你的程序应该打印输出原始序列的词，注意换行。

若有多解，操作4优先，不行则按操作1，2，3优先。同一操作，按操作位置最优的优先（从左到右数起1,2,3……n），还有操作2时，被删数列，先在被删数列添0，不行再添1。

如果没答案输出-1。


title: Local Maxima

description:
给出一个排列。如果其中一个数比它前面的数都大，则称为**局部最大值**（Local Maxima）。

现在问在一个长度为 $n$ 的随机生成的排列中，期望有多少个数为局部最大值。

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

outputFormat: 输出一行一个实数表示答案，保留八位小数。

hint:
长度为 $2$ 的排列共 $2$ 种，为 $(1,2)$ 和 $(2,1)$。前者两个数都为局部最大值，后者仅有第一个数 $2$ 为局部最大值。

### 数据范围及约定

- 对于 $30\%$ 的数据，$n \leq 10$；
- 对于 $80\%$ 的数据，$n \leq 10^6$；
- 对于 $100\%$ 的数据，$1\leq n < 2^{31}$。


title: 最长括号匹配

description:
对一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串：

  1.(),[]是括号匹配的字符串。

2.若A是括号匹配的串，则(A),[A]是括号匹配的字符串。

3.若A,B是括号匹配的字符串，则AB也是括号匹配的字符串。

例如：(),[],([]),()()都是括号匹配的字符串，而][,[(])则不是。

字符串A的子串是指由A中连续若干个字符组成的字符串。

例如，A,B,C,ABC,CAB,ABCABCd都是ABCABC的子串。空串是任何字符串的子串。

inputFormat: 输入一行，为一个仅由()[]组成的非空字符串。

outputFormat: 输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。

hint:
【数据范围】

对20%的数据，字符串长度<=100.

对50%的数据，字符串长度<=10000.

对100%的数据，字符串长度<=1000000.


title: 无边的网格

description:
在一个 $R$ 行 $C$ 列的表格中，每个单元格都是正方形。这种表格便被称为“网格”，每个单元格的四个顶点都叫做“格点”。四个顶点都在格点上的正方形叫做“格点正方形”；类似地，三个顶点都在格点上的正三角形叫做“格点正三角形”。

对于给定的正整数 $R$ 和 $C$（$R,C \le 10$），请计算出网格中格点正方形和格点正三角形的个数。

这种题目 GZH 已经在数学试卷上见得多了。经过浮想联翩、鸟语花香的过程，他认为它与网格问题、计数问题、对称性问题等经典数学题型有异曲同工之妙，可以很方便快捷地解出。但是同时他也发现，一旦 $R$ 和 $C$ 不再满足题中的条件，而是变得很大，计数将会变得枯燥。

当然，聪明的你们对此肯定是喜闻乐见，因为编程在这里又可以派上用处了。

你们能写一个程序来帮 GZH 在这无边的网格中完成枯燥的计数吗？

inputFormat: 共一行，包含 $2$ 个用单个空格隔开的正整数 $R$ 和 $C$。

outputFormat: 共一行，包含 $2$ 个用单个空格隔开的整数 $\mathit{ans}_1$ 和 $\mathit{ans}_2$，按序表示网格中格点正方形和格点正三角形的个数。

hint:
### 样例解释

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

输入文件表明，要求求出图中的格点正方形个数和格点正三角形个数。

- 格点正方形的个数被分类计数如下：
  ![](https://cdn.luogu.com.cn/upload/image_hosting/fb9fn4gw.png)
  共十个。
- 不难发现，所给的网格中找不到格点正三角形。

### 数据范围及约定

- 对于 $30\%$ 的数据，$R,C \le 50$；
- 对于 $50\%$ 的数据，$R,C \le 10^3$；
- 对于 $70\%$ 的数据，$R,C \le 10^5$，$\mathit{ans}_1,\mathit{ans}_2<2^{63}$；
- 对于 $90\%$ 的数据，$R,C \le 10^{100}$；
- 对于 $100\%$ 的数据，$R,C \le 10^{1000}$。


title: Olympic

description: 奥运会正在如火如荼的进行着，金牌榜上也有许多队伍需要排名。你需要选择三个整数 $P_g,P_s$ 和 $P_b$，分别表示每获得一块金、银、铜牌所对应得分。并且满足 $1000 \ge P_g \ge P_s \ge P_b \ge 1$。队伍将依据他们获得的分数进行排序（高分在前）。现在，为了使你所在的队伍排名尽可能的靠前，由你来选择 $P_g,P_s,P_b$。

inputFormat:
第一行一个整数 $n\ (1\le n\le 15)$，表示有 $n$ 支队伍进行排名。

以下 $n$ 行，每行三个整数 $G,S,B\ (0\le G,S,B\le 10^5)$，表示每只队伍获得的金、银、铜牌个数。

1. 第一支队伍即为你所在的队伍；
2. 分数相同时，你所在的队伍排名为最前。

outputFormat:
一行输出三个数 $P_g,P_s,P_b$，中间用空格隔开。

若有多组解，则输出 $P_g$ 最小的解，若仍有多组，则输出 $P_s$ 最小的解，若还有多组解，输出 $P_b$ 最小的解。

hint:
### 数据范围

- 对于 $10\%$ 的数据，保证最优解的 $P_g \le 10$；
- 对于 $30\%$ 的数据，保证最优解的 $P_g \le 100$。


title: [USACO08JAN] Telephone Lines S

description:
Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John's property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着 $1\le N\le1000$ 根据 $1\cdots N$ 顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有 $1\le p\le10000$ 对电话杆可以拉电话线。其他的由于地震使得无法连接。

第i对电线杆的两个端点分别是 $a_i$ ，$b_i$，它们的距离为 $1\le l_i\le1000000$。数据中每对 $(a_i,b_i)$ 只出现一次。编号为 $1$ 的电话杆已经接入了全国的电话网络，整个市的电话线全都连到了编号 $N$ 的电话线杆上。也就是说，笨笨的任务仅仅是找一条将 $1$ 号和 $N$ 号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。

电信公司决定支援灾区免费为此市连接 $k$ 对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度（每根电话线仅连接一对电话线杆）。如果需要连接的电话线杆不超过 $k$ 对，那么支出为 $0$。

请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？

inputFormat:
输入文件的第一行包含三个数字 $n,p,k$。

第二行到第 $p+1$ 行，每行分别都为三个整数 $a_i,b_i,l_i$。

outputFormat: 一个整数，表示该项工程的最小支出，如果不可能完成则输出 `-1`。


title: [NOI2001] 聪明的打字员

description:
阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。

不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：`swap0`，`swap1`，`up`，`down`，`left`，`right`。为了说明这 $6$ 个键的作用，我们先定义录入区的 $6$ 个位置的编号，从左至右依次为 $1,2,3,4,5,6$。下面列出每个键的作用：

- `swap0`：按 `swap0`，光标位置不变，将光标所在的位置的数字与录入区的 $1$ 号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的 $1$ 号位置，则按 `swap0` 键之后录入区的数字不变。

- `swap1`：按 `swap1`，光标位置不变，将光标所在位置的数字与录入区的 $6$ 号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的 $6$ 号位置，则按 `swap1` 键之后录入区的数字不变。

- `up`：按 `up`，光标位置不变，讲光标所在位置的数字加 $1$（除非该数字是 $9$）。例如，如果光标所在位置的数字为 $2$，按 `up` 之后，该处的数字变为 $3$；如果光标所在位置的数字为 $9$，按 `up` 之后，该处的数字不变，光标位置也不变；

- `down`：按 `down`，光标位置不变，讲光标所在位置的数字减 $1$（除非该数字是 $0$）。如果光标所在位置的数字为 $0$，按 `down` 之后，该处的数字不变，光标位置也不变；

- `left`：按 `left`，光标左移一个位置，如果光标已在录入区的 $1$ 号位置（左起第一个位置）上，则光标不动；

- `right`：按 `right`，光标右移一个位置，如果光标已在录入区的 $6$ 号位置（左起第六个位置）上，则光标不动；

当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为 $6$ 的初始密码，而且光标会固定出现在 $1$ 号位置上。当巧妙的使用上述六个特殊键之后，可以得到目标密码，这时光标允许停留在任何一个位置。

现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。

inputFormat: 仅一行，含有两个长度为 $6$ 的数，前者为初始密码，后者为目标密码，两个密码之间用一个空格隔开。

outputFormat: 仅一行，含有一个正整数，为最少需要的击键次数。


title: 长方形

description:
小明今天突发奇想，想从一张用过的纸中剪出一个长方形。

为了简化问题，小明做出如下规定：

（1）这张纸的长宽分别为 $n,m$。小明将这张纸看成是由$n\times m$个格子组成，在剪的时候，只能沿着格子的边缘剪。

（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。

（3）剪出来的长方形的大小没有限制。

小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？

inputFormat:
第一行两个正整数 $n,m$，表示这张纸的长度和宽度。

接下来有 $n$ 行，每行 $m$ 个字符，每个字符为 `*` 或者 `.`。

字符 `*` 表示以前在这个格子上画过，字符 `.` 表示以前在这个格子上没画过。

outputFormat: 仅一个整数，表示方案数。

hint:
【数据规模】

对 $10\%$ 的数据，满足 $1\leq n\leq 10,1\leq m\leq 10$

对 $30\%$ 的数据，满足 $1\leq n\leq 50,1\leq m\leq 50$

对 $100\%$ 的数据，满足 $1\leq n\leq 1000,1\leq m\leq 1000$


title: 火星上的加法运算

description: 最近欢欢看到一本有关火星的书籍，其中她被一个加法运算所困惑，由于她的运算水平有限.她想向你求助，作为一位优秀的程序员，你当然不会拒绝。

inputFormat: 第一行先输入一个运算的进制N(2<=N<=36)，接下来两行为需要进行运算的字符，其中每个字符串的长度不超过200位，其为N进制的数。其中包括0-9及a-z（代表10-35）。

outputFormat: 在N进制下它们的和


title: 易语言

description:
老师近段时间正在研究易语言，这是一款 Windows 下的可视化编程系统，由大连大有吴涛软件开发公司开发的、具有中国知识产权的系统。为了更好地学习该套系统，老师总是有意识地在实践中运用这套系统来开发程序。

这不，今天老师碰到了一个问题，那就是“当把数据放置到 KOJ 上去时，需要把测试数据改成相应的文件名”。举个例子说，如果原始测试数据文件名是 $\text{e0.in,\,e1.in\;...\;e9.in}$ 和 $\text{e0.out,\,e1.out\;...\;e9.out}$，则老师需要把文件全部改为 $\text{data1.in,\,data2.in\;...\;data10.in}$ 和 $\text{data1.out,\,data2.out\;...\;data10.out}$。程序界面如下图所示：

*（注：此处似乎缺少一张图片，但不影响对题意的理解）*

当然了，老师是编程的菜鸟，比起你可是差多了，所以他的程序不是很好，现在想请你帮老师改进这个程序。

事先，老师会告诉你所需要生成的目标文件名格式，比如，他告诉你 $\text{enger0.in}$ 和 $\text{ans}$ ，则表示目标文件中输入文件的主名是 $\text{enger}$，扩展名是 $\text{in}$，编号从 $0$ 开始而且跟在主名后面，当然了，输出文件名就依次是 $\text{enger0.ans,\,enger1.ans\;...\;enger}x\text{.ans}$，其中的 $x$ 你可以统计老师告诉你的原始文件名的个数来确定。另外，老师也会告诉你原始的所有输入数据的文件名全称，比如 $\text{a1.txt,\,a2.txt\;...\;a}x\text{.txt}$。但老师是一个粗心的人，你不要期望老师给你的文件名是按照编号从小到大给出的，但给出的文件名肯定是正确的而且满足一般输入输出文件名的规律的(编号数字肯定出现在文件主名末尾或者扩展名末尾，而且除了这个编号数字外，在原始文件名和生成的目标文件名其他的任何地方都不会出现数字)。

有些原始的输入输出文件名并不需要改变主名和扩展名，而只需改变文件编号即可，此时，老师首先会告诉你一个数字 $1$（或者 $0$），表示最终生成的目标文件的主名和扩展名不必改变，而只需把编号改为从 $1$（或者 $0$）开始即可。

inputFormat: 输入的第一行有两种情况，第一种情况是两个字符串，分别表示最终生成的目标文件名的格式（第一个表示生成的目标文件中的第一个输入文件的名字）；第二种情况是只有一个数字 $1$（或者 $0$），表示文件名主名和扩展名不必更改，只需修改成从 $1$（或者 $0$）开始编号的文件名即可。接下来 $n$ 行（$1 \le n \le 10^5$），每行两个用一个空格分隔的字符串，分别表示原始输入和输出文件的文件名（对于输入和输出文件中所有文件名的主名和扩展名都不超过 $10$ 个字符，而且文件的最大编号不会超过 $2 \times 10^5$）。

outputFormat: 输出包含 $n$ 行，每行两个用一个空格分隔的字符串，分别表示最终生成的目标文件的文件名。第一个表示输入文件，第二个表示输出文件。按照编号从小到大输出。

samples:
enger0.in ans
abc1.in abc1.out
abc2.in abc2.out
abc3.in abc3.out
abc4.in abc4.out

samples:
enger0.in enger0.ans
enger1.in enger1.ans
enger2.in enger2.ans
enger3.in enger3.ans

samples:
1
aa.in0 aa.ou0
aa.in1 aa.ou1
aa.in2 aa.ou2

samples:
aa.in1 aa.ou1
aa.in2 aa.ou2
aa.in3 aa.ou3


title: [NOI2010] 航空管制

description:
世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小 X 就因为航空管制，连续两次在机场被延误超过了两小时。对此，小 X 表示很不满意。

在这次来烟台的路上，小 X 不幸又一次碰上了航空管制。于是小 X 开始思考关于航空管制的问题。

假设目前被延误航班共有 $n$ 个，编号为 $1$ 至 $n$。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。

起飞序列还存在两类限制条件：

- 第一类（最晚起飞时间限制）：编号为 $i$ 的航班起飞序号不得超过 $k_i$。

- 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制 $(a,b)$，表示航班 $a$ 的起飞时间必须早于航班 $b$，即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。

小 X 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

inputFormat:
第一行包含两个正整数 $n$ 和 $m$，$n$ 表示航班数目，$m$ 表示第二类限制条件（相对起飞顺序限制）的数目。

第二行包含 $n$ 个正整数 $k_1,k_2,\cdots,k_n$。

接下来 $m$ 行，每行两个正整数 $a$ 和 $b$，表示一对相对起飞顺序限制 $(a,b)$，其中 $1\leq a,b\leq n$，表示航班 $a$ 必须先于航班 $b$ 起飞。

outputFormat:
第一行包含 $n$ 个整数，表示一个可行的起飞序列，相邻两个整数用空格分隔。输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案，输出任意一个即可。

第二行包含 $n$ 个整数 $t_1,t_2,\cdots,t_n$，其中 $t_i$ 表示航班 $i$ 可能的最小起飞序号，相邻两个整数用空格分隔。

hint:
### 样例解释

在样例 $1$ 中：

起飞序列 $3\ 5\ 1\ 4\ 2$ 满足了所有的限制条件，所有满足条件的起飞序列有：

$$
\begin{aligned}
3\ 4\ 5\ 1\ 2\\
3\ 5\ 1\ 2\ 4\\
3\ 5\ 1\ 4\ 2\\
3\ 5\ 4\ 1\ 2\\
5\ 3\ 1\ 2\ 4\\
5\ 3\ 1\ 4\ 2\\
5\ 3\ 4\ 1\ 2
\end{aligned}
$$

由于存在 $(5,1)$ 和 $(3,1)$ 两个限制，航班 $1$ 只能安排在航班 $5$ 和 $3$ 之后，故最早起飞时间为 $3$，其他航班类似。

在样例 $2$ 中：

虽然航班 $4,5$ 没有相对起飞顺序限制，但是由于航班 $1,2,3$ 都必须安排在前 $3$ 个起飞，所以 $4,5$ 最早只能安排在第 $4$ 个起飞。

### 数据范围

对于 $30\%$ 数据：$n\leq 10$。

对于 $60\%$ 数据：$n\leq 500$。

对于 $100\%$ 数据：$n\leq 2\times 10^3,m\leq 10^4$。

感谢 @FlierKing 提供 spj


title: [NOI2015] 程序自动分析

description:
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 $x_1,x_2,x_3,\cdots$ 代表程序中出现的变量，给定 $n$ 个形如 $x_i=x_j$ 或 $x_i\neq x_j$ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：$x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1$，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

inputFormat:
输入的第一行包含一个正整数 $t$，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第一行包含一个正整数 $n$，表示该问题中需要被满足的约束条件个数。接下来 $n$ 行，每行包括三个整数 $i,j,e$，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 $e=1$，则该约束条件为 $x_i=x_j$。若$e=0$，则该约束条件为 $x_i\neq x_j$。

outputFormat:
输出包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串 `YES` 或者 `NO`（字母全部大写），`YES` 表示输入中的第 $k$ 个问题判定为可以被满足，`NO` 表示不可被满足。

hint:
【样例解释1】

在第一个问题中，约束条件为：$x_1=x_2,x_1\neq x_2$。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：$x_1=x_2,x_1 = x_2$。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：$x_1=x_2,x_2= x_3,x_3=x_1$。只需赋值使得 $x_1=x_2=x_3$，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：$x_1=x_2,x_2= x_3,x_3=x_4,x_4\neq x_1$。由前三个约束条件可以推出 $x_1=x_2=x_3=x_4$，然而最后一个约束条件却要求 $x_1\neq x_4$，因此不可被满足。

【数据范围】

所有测试数据的范围和特点如下表所示：

### 勘误：测试点 $8 \sim 10$ 的 $i, j$ 约束为 $1 \leq i, j \leq 10^9$，而不是下图中的 $10^{10}$。

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


title: Sum

description:
给出一个数列  $a_1,a_2,\cdots,a_n$ 和  $k,p$；

设  $S_{i,j}=\sum\limits_{k=i}^ja_k$，则：
 $$\mathit{Answer}=\min\{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}$$
其中， $i\le j, \{S_{i,j}\bmod p\ |\ S_{i,j}\bmod p\ge k\}\ne\varnothing$。

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

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

outputFormat: 一行一个正整数，表示  $\mathit{Answer}$。


title: 口算练习题

description: 王老师正在教简单算术运算。细心的王老师收集了 $i$ 道学生经常做错的口算题，并且想整理编写成一份练习。 编排这些题目是一件繁琐的事情，为此他想用计算机程序来提高工作效率。王老师希望尽量减少输入的工作量，比如 $\texttt{5+8}$ 的算式最好只要输入 $\texttt 5$ 和 $\texttt 8$，输出的结果要尽量详细以方便后期排版的使用，比如对于上述输入进行处理后输出 $\texttt{5+8=13}$ 以及该算式的总长度 $6$。王老师把这个光荣的任务交给你，请你帮他编程实现以上功能。

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

接着的 $i$ 行为需要输入的算式，每行可能有三个数据或两个数据。

若该行为三个数据则第一个数据表示运算类型，$\texttt a$ 表示加法运算，$\texttt b$ 表示减法运算，$\texttt c$ 表示乘法运算，接着的两个数据表示参加运算的运算数。

若该行为两个数据，则表示本题的运算类型与上一题的运算类型相同，而这两个数据为运算数。

outputFormat: 输出 $2\times i$ 行。对于每个输入的算式，输出完整的运算式及结果，第二行输出该运算式的总长度。

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

对于 $50\%$ 的数据，输入的算式都有三个数据，第一个算式一定有三个数据。

对于所有数据，$0<i\leq 50$，运算数为非负整数且小于 $10000$。


title: 上学路线

description:
你所在城市的街道好像一个棋盘，有 $a$ 条南北方向的街道和 $b$ 条东西方向的街道。南北方向的 $a$ 条街道从西到东依次编号为 $1$ 到 $a$，而东西方向的 $b$ 条街道从南到北依次编号为 $1$ 到 $b$，南北方向的街道 $i$ 和东西方向的街道 $j$ 的交点记为 $(i,j)$。

你住在 $(1,1)$ 处，而学校在 $(a,b)$ 处，你骑自行车去上学，自行车只能沿着街道走，而且为了缩短时间只允许沿着向东和北的方向行驶。

现在有 $N$ 个交叉路口在施工 $(X_1,Y_1)$、$(X_2,Y_2)$……，$(X_n,Y_n)$，这些路口是不能通车的。

问你上学一共有多少走法?

inputFormat:
第一行包含两个整数 $a$ 和 $b$，并且满足 $1 \le a,b \le 16$。

第二行包含一个整数 $N$，表示有 $N$ 个路口在维修 $(1\le N\le 40)$。

接下来 $N$ 行，每行两个整数$X_i,Y_i$，描述路口的位置。

outputFormat: 输出一个整数表示从 $(1,1)$ 到 $(a,b)$ 的行车路线总数。


title: 遗址

description:
很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，由 $4$ 个角上竖立的圆柱搭建而成。现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。

写一个程序，给出圆柱的坐标，找出由 $4$ 个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。

例如图有 $10$ 根柱子，其中 $(4,2),\allowbreak(5,2),\allowbreak(5,3),\allowbreak(4,3)$ 可以形成一个正方形，$(1,1),\allowbreak(4,0),\allowbreak(5,3),\allowbreak(2,4)$ 也可以，后者是其中最大的，面积为 $10$。

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

inputFormat:
第一行包含一个 $N(1\leq N\leq 3000)$，表示柱子的数量。

接下来 $N$ 行，每行有两个空格隔开的整数表示柱子的坐标（坐标值在 $0$ 到 $5000$ 之间），柱子的位置互不相同。

outputFormat: 如果存在正方形，输出最大的面积，否则输出 $0$。


title: 郁闷的记者

description:
你是一个体育报社的记者，你接受到一个艰难的任务：有 $N$ 支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从 $1$ 到 $N$。

以下是给你的一些信息：

 1. 没有平局；
 2. 不同的球队排名不能相同；
 3. 对于所有满足 $1 \le a<b \le N$，第 $a$ 名的球队一定可以打败第 $b$ 名的球队。

给你部分比赛结果，要求给出排名，并且判断是否存在另一种排名方法满足给你的比赛结果。

inputFormat:
第一行输入 $N(1 \le N \le 5000)$，表示球队的数量，编号为 $1$ 到 $N$。

第二行输入 $M(1 \le M \le 100,000)$，表示给出的比赛场数。

接下来 $M$ 行，每行两个整数 $X_i$，$Y_i$，表示 $X_i$ 能打败 $Y_i$。

outputFormat: 输出包含 $N+1$ 行，前 $N$ 行描述球队的排名，第 $i$ 个数表示第 $i$ 名的球队，第 $N+1$ 行包含一个整数，如果为 $0$ 表示不存在其他的排名方法，如果为 $1$ 表示还有其他的排名方法。

hint:
【数据范围】

$30\%$ 的数据满足：$1 \le N \le7$，$1 \le M \le 15$

$60\%$的数据满足：$1 \le N \le 100$，$1 \le M \le 2000$

$100\%$ 的数据满足：$1 \le N \le 5000$，$1 \le M \le 100000$

本题已加入spj，如果输出的最后一行错误将会提示 `Your decide is wrong!`

如果存在多种排名情况，排名错误将会提示 `Wrong ranks!`

如果情况固定且您的答案错误将会提示 `In line X,Your ans is wrong:expected = X,found = Y`


title: 最轻的天平

description: 天平的两边有时不一定只能挂物品，还可以继续挂着另一个天平，现在给你一些天平的情况和它们之间的连接关系，要求使得所有天平都能平衡所需物品的总重量最轻，一个天平平衡当且仅当“左端点的重量\*左端点到支点的距离=右端点的重量\*右端点到支点的距离”。注意题目中的输入保证这些天平构成一个整体。

inputFormat:
第一行包含一个 $N(N \le 100)$，表示天平的数量，天平编号为 $l$ 到 $N$，接下来包含 $N$ 行描述天平的情况，每行 $4$ 个整数 $P,Q,R,B$，$P$ 和 $Q$ 表示横杆上支点到左边的长度与到右边的距离的比例为 $P:Q$，$R$ 表示左边悬挂的情况，如果 $R=0$ 说明悬挂的是物品，否则表示左边悬挂的是天平 $R:B$ 表示右边的悬挂情况，如果 $B=O$ 表示右边悬挂的是物品，否则右边悬挂着天平 $B$。

对于所有的输入，保证 $W\times L<2^{31}$，其中 $w$ 为最轻的天平重量，而 $L$ 为输入中描述左右比例时出现的最大值。

outputFormat: 输出一个整数表示使得所有天平都平衡所需最轻的物品总重量。


title: 斐波那契数列

description:
大家都知道，斐波那契数列是满足如下性质的一个数列：

$$F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$

请你求出 $F_n \bmod 10^9 + 7$ 的值。

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

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


title: [NOI2009] 变换序列

description:
对于 $N$ 个整数 $0, 1, \cdots, N-1$，一个变换序列 $T$ 可以将 $i$ 变成 $T_i$，其中 $T_i \in \{ 0,1,\cdots, N-1\}$ 且 $\bigcup_{i=0}^{N-1} \{T_i\} = \{0,1,\cdots , N-1\}$。$\forall x,y \in  \{0,1,\cdots , N-1\}$，定义 $x$ 和 $y$ 之间的距离 $D(x,y)=\min\{|x-y|,N-|x-y|\}$。给定每个 $i$ 和 $T_i$ 之间的距离 $D(i,T_i)$，你需要求出一个满足要求的变换序列 $T$。如果有多个满足条件的序列，输出其中字典序最小的一个。

说明：对于两个变换序列 $S$ 和 $T$，如果存在 $p<N$，满足对于 $i=0,1,\cdots p-1$，$S_i=T_i$ 且 $S_p<T_p$，我们称 $S$ 比 $T$ 字典序小。

inputFormat: 第一行包含一个正整数 $N$，表示序列的长度。接下来的一行包含 $N$ 个整数 $D_i$，其中 $D_i$ 表示 $i$ 和 $T_i$ 之间的距离。

outputFormat: 如果至少存在一个满足要求的变换序列 $T$，则输出文件中包含一行 $N$ 个整数，表示你计算得到的字典序最小的 $T$；否则输出 `No Answer`（不含引号）。注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。


title: 【mc生存】卖东西

background: 服务器好好玩。

description:
lcy0x1 去服务器的系统商店买东西。

一个人的背包有 $21$ 格。

一开始他的背包里有 $m$ 件不同的物品（**不能卖**）。

他要买 $n$ 种物品，第 $i$ 件物品的名字为 $st_i$，有 $a_i$ 件，价值为 $b_i$，一格可以放 $c_i$ 个。

相同的物品可以放同一格（只要没放满）。

问：他跑一次最多能卖多少钱。

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

下面 $n$ 行，第 $i+1$ 行三个整数 $a_i,b_i,c_i$ 与一个字符串 $st_i$。

outputFormat: 最多卖的钱 $s$。

samples:
20 3
63 1 64 yinshifen
1 10 1 men
1 1 64 yinshifen


title: [NOIP2013 提高组] 转圈游戏

background: NOIP2013 提高组 D1T1

description:
$n$ 个小伙伴（编号从 $0$ 到 $n-1$）围坐一圈玩游戏。按照顺时针方向给 $n$ 个位置编号，从 $0$ 到 $n-1$。最初，第 $0$ 号小伙伴在第 $0$ 号位置，第 $1$ 号小伙伴在第 $1$ 号位置，……，依此类推。游戏规则如下：每一轮第 $0$ 号位置上的小伙伴顺时针走到第 $m$ 号位置，第 $1$ 号位置小伙伴走到第 $m+1$ 号位置，……，依此类推，第 $n - m$ 号位置上的小伙伴走到第 $0$ 号位置，第 $n - m+1$ 号位置上的小伙伴走到第 $1$ 号位置，……，第 $n-1$ 号位置上的小伙伴顺时针走到第 $m-1$ 号位置。

现在，一共进行了 ${10}^k$ 轮，请问 $x$ 号小伙伴最后走到了第几号位置。

inputFormat: 共一行，包含四个整数 $n, m, k, x$，每两个整数之间用一个空格隔开。

outputFormat: 一个整数，表示 ${10}^k$ 轮后 $x$ 号小伙伴所在的位置编号。


title: [NOIP2013 提高组] 火柴排队

background: NOIP2013 提高组 D1T2

description:
涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$ \sum (a_i-b_i)^2$。

其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第  $i$ 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $10^8-3$ 取模的结果。

inputFormat:
共三行，第一行包含一个整数 $n$，表示每盒中火柴的数目。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

outputFormat: 一个整数，表示最少交换次数对 $10^8-3$ 取模的结果。

hint:
**输入输出样例说明一**

最小距离是 $ 0$，最少需要交换 $1$ 次，比如：交换第 $1 $ 列的前 $ 2$ 根火柴或者交换第 $2$ 列的前 $2 $ 根火柴。

**输入输出样例说明二**

最小距离是 $10$，最少需要交换 $2$ 次，比如：交换第 $1$ 列的中间 $2$ 根火柴的位置，再交换第 $2$ 列中后 $2$ 根火柴的位置。

**数据范围**

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

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

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

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq$ 火柴高度 $< 2^{31}$。


title: [NOIP2013 提高组] 货车运输

background: NOIP2013 提高组 D1T3

description:
A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

inputFormat:
第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行三个整数 $x, y, z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x \neq y$，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x \neq y$

outputFormat:
共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 $-1$。


title: 美元汇率

background: 此处省略 `MAX_INT+1` 个数。

description: 在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从 $100$ 美元开始，最后能获得最高可能的价值。

inputFormat:
输入文件的第一行是一个自然数 $N$，$1≤N≤100$，表示戴维学习汇率的天数。

接下来的 $N$ 行中每行是一个自然数 $A$，$1≤A≤1000$。第 $i+1$ 行的 $A$ 表示预先知道的第 $i+1$ 天的平均汇率，在这一天中，戴维既能用 $100$ 美元买 $A$ 马克也能用 $A$ 马克购买 $100$ 美元。

outputFormat:
输出文件的第一行也是唯一的一行应输出要求的钱数（单位为美元，保留两位小数）。

注意：考虑到实数算术运算中进位的误差，结果在正确结果 $0.05$ 美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。


title: [NOIP2013 提高组] 积木大赛

background: NOIP2013 提高组 D2T1

description:
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 $n$ 的大厦，大厦可以看成由 $n$ 块宽度为 $1$ 的积木组成，第 $i$ 块积木的最终高度需要是 $h_i$。

在搭建开始之前，没有任何积木（可以看成 $n$ 块高度为 $0$ 的积木）。接下来每次操作，小朋友们可以选择一段连续区间 $[l, r]$，然后将第 $L$ 块到第 $R$ 块之间（含第 $L$ 块和第 $R$ 块）所有积木的高度分别增加 $1$。

小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

inputFormat:
包含两行，第一行包含一个整数 $n$，表示大厦的宽度。

第二行包含 $n$ 个整数，第 $i$ 个整数为 $h_i$。

outputFormat: 建造所需的最少操作数。


title: [NOIP2013 提高组] 花匠

background: NOIP2013 提高组 D2T2

description:
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数 $h_1,h_2,\ldots,h_n$。设当一部分花被移走后，剩下的花的高度依次为 $g_1,g_2,\ldots,g_m$，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有的 $1 \le i \le \frac{m}{2}$，有 $g_{2 i} > g_{2 i - 1}$，同时对于所有的 $1 \le i \le \frac{m}{2}$，有 $g_{2 i} > g_{2 i + 1}$；
条件 B：对于所有的 $1 \le i \le \frac{m}{2}$，有 $g_{2 i} < g_{2 i - 1}$，同时对于所有的 $1 \le i \le \frac{m}{2}$，有 $g_{2 i} < g_{2 i + 1}$。

注意上面两个条件在 $m = 1$ 时同时满足，当 $m > 1 $ 时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

inputFormat:
第一行包含一个整数 $n$，表示开始时花的株数。

第二行包含 $n$ 个整数，依次为 $h_1,h_2,\ldots,h_n$，表示每株花的高度。

outputFormat: 输出一行，包含一个整数，表示最多能留在原地的花的株数。

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

有多种方法可以正好保留 $3$ 株花，例如，留下第 $1$、$4$、$5$ 株，高度分别为 $5$、$1$、$2$，满足条件 B。

**数据范围**

对于 $20\%$的数据，$n \le 10$；

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

对于 $70\%$的数据，$n \le 1000$，$0 \le h_i \le 1000$；

对于 $100\%$的数据，$1 \le n \le {10}^5$，$0 \le h_i \le {10}^6$，所有的 $h_i$ 随机生成，所有随机数服从某区间内的均匀分布。


title: [NOI2011] 兔兔与蛋蛋游戏

description:
这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。

这个游戏是在一个 $n$ 行 $m$ 列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。

每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为：

* 兔兔每次操作时，选择一枚与空格相邻的白色棋子，将它移进空格。
* 蛋蛋每次操作时，选择一枚与空格相邻的黑色棋子，将它移进空格。

第一个不能按照规则操作的人输掉游戏。为了描述方便，下面将操作“将第x行第y列中的棋子移进空格中”记为 $M(x,y)$。

例如下面是三个游戏的例子。

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

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

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

最近兔兔总是输掉游戏，而且蛋蛋格外嚣张，于是兔兔想请她的好朋友——你——来帮助她。她带来了一局输给蛋蛋的游戏的实录，请你指出这一局游戏中所有她“犯错误”的地方。

注意：

* 两个格子相邻当且仅当它们有一条公共边。
* 兔兔的操作是“犯错误”的，当且仅当，在这次操作前兔兔有必胜策略，而这次操作后蛋蛋有必胜策略。

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

接下来 $n$ 行描述初始棋盘。其中第 $i$ 行包含 $m$ 个字符，每个字符都是大写英文字母 `X`、大写英文字母 `O` 或点号 `.` 之一，分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号 `.` 恰好出现一次。

接下来一行包含一个整数 $k$（$1\leq k\leq 1000$） ，表示兔兔和蛋蛋各进行了 $k$ 次操作。

接下来 $2k$ 行描述一局游戏的过程。其中第 $2i - 1$ 行是兔兔的第 $i$ 次操作（编号为 $i$ 的操作） ，第 $2i$ 行是蛋蛋的第 $i$ 次操作。每个操作使用两个整数 $x,y$ 来描述，表示将第 $x$ 行第 $y$ 列中的棋子移进空格中。

输入保证整个棋盘中只有一个格子没有棋子， 游戏过程中兔兔和蛋蛋的每个操作都是合法的，且最后蛋蛋获胜。

outputFormat:
输出文件的第一行包含一个整数 $r$，表示兔兔犯错误的总次数。

接下来 $r$ 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 $i$ 行包含一个整数 $a_i$ 表示兔兔第 $i$ 个犯错误的操作是他在游戏中的第 $a_i$ 次操作。

samples:
4 4
OOXX
OXXO
OO.O
XXXO
2
3 2
2 2
1 2
1 3


title: [SDOI2009] HH的项链

description:
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

inputFormat:
一行一个正整数 $n$，表示项链长度。
第二行 $n$ 个正整数 $a_i$，表示项链中第 $i$ 个贝壳的种类。

第三行一个整数 $m$，表示 HH 询问的个数。
接下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。

outputFormat: 输出 $m$ 行，每行一个整数，依次表示询问对应的答案。

hint:
【数据范围】

对于 $20\%$ 的数据，$1\le n,m\leq 5000$；
对于 $40\%$ 的数据，$1\le n,m\leq 10^5$；
对于 $60\%$ 的数据，$1\le n,m\leq 5\times 10^5$；
对于 $100\%$ 的数据，$1\le n,m,a_i \leq 10^6$，$1\le l \le r \le n$。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB


title: [NOI2011] NOI 嘉年华

description:
NOI2011 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，吉林大学决定举办两场盛大的 NOI 嘉年华活动，分在两个不同的地点举办。每个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。

现在嘉年华活动的组织者小安一共收到了 $n$ 个活动的举办申请，其中第 $i$ 个活动的起始时间为 $S_i$，活动的持续时间为 $T_i$。这些活动都可以安排到任意一个嘉年华的会场，也可以不安排。

小安通过广泛的调查发现，如果某个时刻，两个嘉年华会场同时有活动在进行（不包括活动的开始瞬间和结束瞬间），那么有的选手就会纠结于到底去哪个会场，从而变得不开心。所以，为了避免这样不开心的事情发生，小安要求不能有两个活动在两个会场同时进行（同一会场内的活动可以任意进行）。

另外，可以想象，如果某一个嘉年华会场的活动太少，那么这个嘉年华的吸引力就会不足，容易导致场面冷清。所以小安希望通过合理的安排，使得活动相对较少的嘉年华的活动数量最大。

此外，有一些活动非常有意义，小安希望能举办，他希望知道，如果第 $i$ 个活动必须举办（可以安排在两场嘉年华中的任何一个），活动相对较少的嘉年华的活动数量的最大值。

inputFormat:
输入的第一行包含一个整数 $n$，表示申请的活动个数。

接下来 $n$ 行描述所有活动，其中第 $i$ 行包含两个整数 $S_i,T_i$，表示第 $i$ 个活动从时刻 $S_i$ 开始，持续 $T_i$ 的时间。

outputFormat:
输出的第一行包含一个整数，表示在没有任何限制的情况下，活动较少的嘉年华的活动数的最大值。

接下来 $n$ 行每行一个整数，其中第 $i$ 行的整数表示在必须选择第 $i$ 个活动的前提下，活动较少的嘉年华的活动数的最大值。

hint:
### 样例解释

在没有任何限制的情况下，最优安排可以在一个嘉年华安排活动 $1, 4$，而在另一个嘉年华安排活动 $3, 5$，活动 $2$ 不安排。

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

对于 $30\%$ 的数据，$1\leq n\leq 40$。

对于 $100\%$ 的数据，$1\leq n\leq 200$，$0\leq S_i\leq 10^9$，$1\leq T_i\leq 10^9$。

如果输出格式不正确（比如输出不足 $n+1$ 行），得 $0$ 分；

如果输出文件第一行不正确，而且后 $n$ 行至少有一行不正确，得 $0$ 分；

如果输出文件第一行正确，但后 $n$ 行至少有一行不正确，得 $4$ 分；

如果输出文件第一行不正确，但后 $n$ 行均正确，得 $6$ 分；

如果输出文件中的 $n+1$ 行均正确，得 $10$ 分。


title: 基因聚合

description:
德国科学家总是对非洲野猴的抵抗力感到惊奇，因为他们发现在没有医疗条件的情况下，非洲野猴总是比其他所有野生动物少生病。最近的研究有了新发现，科学家Dr.Smith从非洲野猴身上发现了一种罕见的抗体，他猜测可能正是该罕见的抗体在帮助非洲野猴抵抗外来病毒的侵害。

Dr.Smith就立刻展开了对该抗体的研究。在初始的观察中Dr.Smith发现该抗体没什么特别，而且非常简单，因为抗体的每组基因只有一对基元（Dr.Smith把一组基因看成由若干对基元组成）。但是当Dr.Smith把病毒植入抗体所在的培养液后，奇迹出现了！那些简单的基因组通过不断地聚合（每个基因组两两合并生成新的基因组），最终所有的基因组合并成了一个非常庞大的基因组，而正是这庞大的基因组，因为聚合了所有原始基因组的优点，这庞大的基因组才可以慢慢地、逐个地去吃掉那些植入培养液的病毒。

下面是Dr.Smith在高倍显微镜下看到的抗体基因组基元聚合的大致过程：

图3－1  Dr.Smith在显微镜下看到的开始时有3个基因组的抗体聚合过程

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

Dr.Smith通过进一步观察和研究发现，抗体基因在聚合过程中似乎总是按照某个方法在进行，该方法能保证最终产生的基因组的基元对数量最多（每个基元对的存在能产生1u单位的生物能量），而在每次两个基因组聚合后所得到的新基因组的总的基元对由下面两部分相加组成：

1、每两个基因组一发生聚合，就产生一个额外的、未知的基元对。

2、当两个基因组聚合时，每个基因组中的每对基元都会与另一个基因组中的每对基元两两聚合产生一个新的基元对。

Dr.Smith还发现，抗体在每个时刻总是只有两个基因组会发生聚合，也就是说，每两个基因组的聚合都是依次进行的，而不是同时进行的。

虽然观察到聚合原理，但Dr.Smith即使在知道一开始基因组个数的前提下，还是无法统计最终聚合产生的那个庞大的基因组所具有的总能量有多大。现在他想请你编程来统计一下。

inputFormat: 包含一行一个整数n，表示一开始放入培养液中的基因组的总数（这些基因组每组只包含一个相同的基元对），其中1<=n<=10000。

outputFormat: 包含一行一个整数，表示最终得到的那个庞大的基因组所具有的最大总能量。


title: [国家集训队] 排队

description:
排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。

红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第 $i$ 个小朋友的身高为 $h_i$。

幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的逆序对数。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的逆序对数。

inputFormat:
第一行为一个正整数 $n$，表示小朋友的数量；

第二行包含 $n$ 个由空格分隔的正整数 $h_1,h_2,\dots,h_n$，依次表示初始队列中小朋友的身高；

第三行为一个正整数 $m$，表示交换操作的次数；

以下m行每行包含两个正整数 $a_i,b_i$，表示交换位置 $a_i$ 和 $b_i$ 的小朋友。

outputFormat: 输出文件共 $m+1$ 行，第 $i$ 行一个正整数表示交换操作 $i$ 结束后，序列的逆序对数。

hint:
【样例说明】
未进行任何操作时，$(2,3)$ 为逆序对；
操作一结束后，序列为 $130 \ 140 \ 150$，不存在逆序对；
操作二结束后，序列为 $150 \ 140 \ 130$，$(1,2),(1,3),(2,3)$ 共 $3$ 个逆序对。

【数据范围】
对于 $10\%$ 的数据，$n,m \le 15$；
对于 $25\%$ 的数据，$n,m \le 200$；
另有 $25\%$ 的数据，$h_i$ 各不相同；
另有 $15\%$ 的数据，$110 \le h_i \le 160$；
以上两类数据交集为空。

对于100%的数据，$1 \le m \le 2\times 10^3$，$1 \le n \le 2 \times 10^4$，$1 \le h_i \le 10^9$，$a_i \ne b_i$，$1 \le a_i,b_i \le n$。


title: 鸡蛋饼

background: Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问，小 x 道出了实情：因为他喜欢圆。

description: 最近小 x 又发现了一个关于圆的有趣的问题：在圆上有 $2N$ 个不同的点，小 x 想用 N 条线段把这些点连接起来（每个点只能连一条线段）， 使所有的线段都不相交，他想知道这样的连接方案有多少种？

inputFormat: 有且仅有一个正整数 N 。 （$N \le 2999$）

outputFormat: 要求的方案数（结果 $\bmod 100000007$）。


title: 出租车拼车

background:
话说小 x 有一次去参加比赛，虽然学校离比赛地点不太远，但小 x 还是想坐出租车去。大学城的出租车总是比较另类，有“拼车”一说，也就是说，你一个人坐车去，还是一堆人一起，总共需要支付的钱是一样的（每辆出租上除司机外最多坐下 $4$ 个人）。刚好那天同校的一群 OIer 在校门口扎堆了，大家果断决定拼车去赛场。

问题来了，一辆又一辆的出租车经过，但里面要么坐满了乘客，要么只剩下一两个座位，众 OIer 都觉得坐上去太亏了，小 x 也是这么想的。

description:
假设 $N$ 位 OIer 准备拼车，此时为 $0$ 时刻，从校门到目的地需要支付给出租车师傅 $D$ 元（按车次算，不管里面坐了多少 OIer），假如 $S$ 分钟后恰能赶上比赛，那么 $S$ 分钟后经过校门口的出租车自然可以忽略不计了。现在给出在这 $S$ 分钟当中经过校门的所有的 $K$ 辆出租车先后到达校门口的时间 $T_i$  及里面剩余的座位 $Z_i$
，OIer 可以选择上车几个人（不能超过），当然，也可以选择上 $0$ 个人，那就是不坐这辆车。

俗话说，时间就是金钱，这里小 x 把每个 OIer 在校门等待出租车的分钟数 等同于花了相同多的钱（例如小 x 等待了 $20$ 分钟，那相当于他额外花了 $20$ 元钱）。

在保证所有 OIer 都能在比赛开始前到达比赛地点的情况下，聪明的你能计算出他们最少需要花多少元钱么？

inputFormat:
每组数据以四个整数 $N$ , $K$ , $D$ , $S$ 开始，具体含义参见题目描述。

接着 $K$ 行，表示第 $i$ 辆出租车在第 $T_i$ 分钟到达校门，其空余的座位数为 $Z_i$

时间按照先后顺序。

outputFormat:
对于每组测试数据，输出占一行，如果他们所有人能在比赛前到达比赛地点，

则输出一个整数，代表他们最少需要花的钱（单位：元），否则请输出 `impossible`。


title: 集合

description:
集合是数学中的一个概念，用通俗的话来讲就是：一大堆数在一起就构成了集合。

集合有如下的特性：

- 无序性：任一个集合中，每个元素的地位都是相同的，元素之间是无序的。

- 互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。

- 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

例如 $A = \{ 1, 2, 3 \}$ 就是一个集合。我们可以知道，$1$ 属于 $A$，即 $1 \in A$；$4$ 不属于 $A$，即 $4 \notin A$。一个集合的大小，就是其中元素的个数。

现在定义一个特殊的 $k$-集合，要求满足：

- 集合的所有特性
- 对任意一个该集合内的元素 $x$，不存在一个数 $y$，使得 $y = k x$ 并且 $y$ 属于该集合。即集合中的任意一个数，它乘以 $k$ 之后的数都不在这个集合内。

给你一个由 $n$ 个不同的数组成的集合，请你从这个集合中找出一个最大的 $k$-集合。

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

第二行：$n$ 个整数：$a_i$ 表示给定的集合。

outputFormat: 第一行：一个整数：$\mathit{ans}$ 表示最大的 $k$-集合的大小。


title: [NOIP2013 提高组] 华容道

background: NOIP2013 提高组 D2T3

description:
`小 B` 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面， 华容道是否根本就无法完成，如果能完成， 最少需要多少时间。

`小 B` 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：

1.   在一个 $n \times m$ 棋盘上有 $ n \times m$ 个格子，其中有且只有一个格子是空白的，其余 $ n \times m-1$ 个格子上每个格子上有一个棋子，每个棋子的大小都是 $1 \times 1$ 的；
2.  有些棋子是固定的，有些棋子则是可以移动的；
3.  任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。

游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘，游戏可以玩 $q$ 次，当然，每次棋盘上固定的格子是不会变的， 但是棋盘上空白的格子的初始位置、 指定的可移动的棋子的初始位置和目标位置却可能不同。第 $i$ 次玩的时候， 空白的格子在第 $EX_i$ 行第 $EY_i$ 列，指定的可移动棋子的初始位置为第 $SX_i$ 行第 $SY_i$列，目标位置为第 $TX_i$ 行第 $TY_i$ 列。

假设 `小 B` 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉 `小 B` 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。

inputFormat:
第一行有 $3$个整数，每两个整数之间用一个空格隔开，依次表示 $ n,m,q$；

接下来的 $n$ 行描述一个 $ n \times m$ 的棋盘，每行有 $ m $ 个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，$0$ 表示该格子上的棋子是固定的，$1$ 表示该格子上的棋子可以移动或者该格子是空白的。

接下来的 $q$ 行，每行包含 $6$ 个整数依次是 $EX_i,EY_i,SX_i,SY_i,TX_i,TY_i$，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。

outputFormat: 共 $ q$ 行，每行包含 $1$ 个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出 $−1$。

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

棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示棋子，其中绿色圆圈表示目标棋子。

1.   第一次游戏，空白格子的初始位置是 $(3,2)$（图中空白所示），游戏的目标是将初始位置在 $(1, 2)$ 上的棋子（图中绿色圆圈所代表的棋子）移动到目标位置 $(2, 2)$（图中红色的格子）上。

移动过程如下：

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

2.  第二次游戏，空白格子的初始位置是 $(1, 2)$（图中空白所示），游戏的目标是将初始位置在 $(2, 2)$ 上的棋子（图中绿色圆圈所示）移动到目标位置  $(3, 2)$ 上。

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

要将指定块移入目标位置，必须先将空白块移入目标位置，空白块要移动到目标位置，必然是从位置 $(2,2)$ 上与当前图中目标位置上的棋子交换位置，之后能与空白块交换位置的只有当前图中目标位置上的那个棋子，因此目标棋子永远无法走到它的目标位置， 游戏无法完成。

**数据范围**

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

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

对于 $100\%$ 的数据，$1 ≤ n, m ≤ 30,q ≤ 500$。


title: [NOIP2013 普及组] 计数问题

background: NOIP2013 普及组 T1

description: 试计算在区间 $1$ 到 $n$ 的所有整数中，数字 $x$（$0\le x\le9$）共出现了多少次？例如，在 $1$ 到 $11$ 中，即在 $1,2,3,4,5,6,7,8,9,10,11$ 中，数字 $1$ 出现了 $4$ 次。

inputFormat: $2$ 个整数 $n,x$，之间用一个空格隔开。

outputFormat: $1$ 个整数，表示 $x$ 出现的次数。


title: [NOIP2013 普及组] 表达式求值

background: NOIP2013 普及组 T2

description: 给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

inputFormat:
一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 `+` 和乘法运算符 `*`，且没有括号，所有参与运算的数字均为 $0$ 到   $2^{31}-1$ 之间的整数。

输入数据保证这一行只有 `0123456789+*` 这 $12$ 种字符。

outputFormat:
一个整数，表示这个表达式的值。

注意：当答案长度多于 $4$ 位时，请只输出最后 $ 4$ 位，前导 $ 0$ 不输出。

hint:
对于 $30\%$ 的数据，$0≤$ 表达式中加法运算符和乘法运算符的总数 $≤100$。

对于 $80\%$ 的数据，$0≤$ 表达式中加法运算符和乘法运算符的总数 $≤1000$。

对于 $100\%$ 的数据，$0≤$ 表达式中加法运算符和乘法运算符的总数 $≤100000$。


title: [NOIP2013 普及组] 小朋友的数字

background: NOIP2013 普及组 T3

description:
有 $n$ 个小朋友排成一列。每个小朋友手上都有一个数字，这个数字可正可负。规定每个小朋友的特征值等于排在他前面（包括他本人）的小朋友中连续若干个（最少有一个）小朋友手上的数字之和的最大值。

作为这些小朋友的老师，你需要给每个小朋友一个分数，分数是这样规定的：第一个小朋友的分数是他的特征值，其它小朋友的分数为排在他前面的所有小朋友中（不包括他本人），小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值，输出时保持最大值的符号，将其绝对值对 $p$ 取模后输出。

inputFormat:
第一行包含两个正整数 $n,p$，之间用一个空格隔开。

第二行包含 $n$ 个数，每两个整数之间用一个空格隔开，表示每个小朋友手上的数字。

outputFormat: 一个整数，表示最大分数对 $p$ 取模的结果。


title: [NOIP2013 普及组] 车站分级

background: NOIP2013 普及组 T4

description:
一条单向的铁路线上，依次有编号为 $1, 2, …, n$ 的 $n $ 个火车站。每个火车站都有一个级别，最低为 $1$ 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 $x$，则始发站、终点站之间所有级别大于等于火车站 $ x$ 的都必须停靠。
注意：起始站和终点站自然也算作事先已知需要停靠的站点。

例如，下表是 $ 5 $ 趟车次的运行情况。其中，前 $ 4$ 趟车次均满足要求，而第 $5$ 趟车次由于停靠了 $3$ 号火车站（$2$ 级）却未停靠途经的 $6$ 号火车站（亦为 $2$ 级）而不满足要求。

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

现有 $m$ 趟车次的运行情况（全部满足要求），试推算这 $ n$ 个火车站至少分为几个不同的级别。

inputFormat:
第一行包含 $2$ 个正整数 $n, m$，用一个空格隔开。

第 $i + 1$ 行 $(1 ≤ i ≤ m)$ 中，首先是一个正整数 $s_i\ (2 ≤ s_i ≤ n)$，表示第 $ i$ 趟车次有 $s_i$ 个停靠站；接下来有 $ s_i$ 个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

outputFormat: 一个正整数，即 $n$ 个火车站最少划分的级别数。


title: [SDOI2008] 烧水问题

description:
把总质量为 $1\ \rm kg$ 的水分装在 $n$ 个杯子里，每杯水的质量均为 $(1/n)\ \rm kg$，初始温度均为 $0$ 度。现需要把每一杯水都烧开。我们可以对任意一杯水进行加热。把一杯水的温度升高 $t$ 度所需的能量为 $(4200\times t/n)\rm J$，其中，$\rm J$ 是能量单位“焦耳”。如果一旦某杯水的温度达到 $100$ 度，那么这杯水的温度就不能再继续升高，此时我们认为这杯水已经被烧开。显然地，如果直接把水一杯一杯地烧开，所需的总能量为 $(4200\times 100)\rm J$。

在烧水的过程中，我们随时可以在两杯温度不同的水之间进行热传递操作。热量只能从温度较高的那杯水传递到温度较低的那杯水。由于两杯水的质量相同，所以进行热传递操作之后，原来温度较高的那杯水所降低的温度总是等于原来温度较低的那杯水所升高的温度。

一旦两杯水的温度相同，热传递立刻停止。

为了把问题简化，我们假设：

1. 没有进行加热或热传递操作时，水的温度不会变化。
2. 加热时所花费的能量全部被水吸收，杯子不吸收能量。
3. 热传递总是隔着杯子进行，$n$ 杯水永远不会互相混合。
4. 热传递符合能量守恒，而且没有任何的热量损耗。

在这个问题里，只要求把每杯水都至少烧开一遍就可以了，而不要求最终每杯水的温度都是 $100$ 度。我们可以用如下操作把两杯水烧开：先把一杯水加热到 $100$ 度，花费能量 $(4200\times 100/2)\rm J$，然后两杯水进行热传递，直到它们的温度都变成 $50$ 度为止，最后把原来没有加热到 $100$ 度的那杯水加热到 $100$ 度，花费能量 $(4200\times 50/2)\rm J$，此时两杯水都被烧开过了，当前温度一杯 $100$ 度，一杯 $50$ 度，花费的总能量为 $(4200\times 75)\rm J$，比直接烧开所需的 $(4200\times 100)\rm J$ 少花费了 $25\%$ 的能量。

你的任务是设计一个最佳的操作方案使得 $n$ 杯水都至少被烧开一遍所需的总能量最少。

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

outputFormat: 输出 $n$ 杯水都至少被烧开一遍所需的最少的总能量，单位为 $J$，四舍五入到小数点后两位。

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

对于全部数据，$1 \le n \le 3000000$。


title: [USACO07OPEN] 翻转棋 Fliptile S

description:
FJ 知道，智商高的奶牛产奶量也大，所以他为奶牛们准备了一个翻动瓦片的益智游戏。

在一个 $M \times N$ 的方阵上（$1 \leq M,N \leq 15$），每个格子都有一个可以翻转的瓦片。瓦片的一面是黑色，另一面是白色。对一个瓦片翻转，可以让它的颜色由黑到白，或是由白到黑。

然而奶牛们很笨拙，它们翻转一个格子的瓦片时，与其有公共边的所有瓦片也会翻转。

现在奶牛们想知道，至少需要多少次翻转，使所有的瓦片都变成白色朝上呢？

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

接下来 $M$ 行，每行 $N$ 个整数，表示初始状态，$0$ 表示白面朝上，$1$ 表示黑面朝上。

outputFormat:
如果不能将所有瓦片都翻转为白面朝上的话，输出 `IMPOSSIBLE`。

否则输出 $M$ 行，每行 $N$ 个整数，第 $i$ 行的第 $j$ 个数代表第 $i$ 行第 $j$ 列的瓦片被翻转了多少次。

你的输出应该确保翻转次数最少。如果存在多种方案，输出字典序最小的方案。

这里的字典序最小指将输出中的所有空白字符去掉后，形成的字符串字典序最小。

hint:
下面的方案操作次数同样是最小的，但是字典序不是最小的。

```plain
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
```


title: 元旦晚会

background:
玛雅人预言的世界末日没有发生，我们迎来了地球的第五个太阳纪。

学校将要举办第五个太阳纪的第一次元旦晚会。Brett 的班级要参加，并且还表演节目。

description:
Brett 班的节目是这样的：全班 $n$ 个同学排成一排，同学们手拿话筒，齐唱《喜洋洋与灰太狼》（这个节目看起来有点二） 。

Brett 班的同学分成了 $m$ 个声部，一个声部由连续的同学组成，第 $i$ 个声部由 $a_i$ 到 $b_i$ 之间的同学组成（包括 $a_i$ 和 $b_i$ ）

但是一个同学有可能同时属于多个声部，且有可能有同学不属于任何一个声部。为了保证演唱效果，第 $i$ 个声部必须至少有 $c_i$ 个同学持有话筒（即第 $i$ 个声部持有话筒的同学数大于等于 $c_i$）。

请你算出 Brett 班最少需要几个话筒。

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

以下 $m$ 行，每行 $3$ 个正整数 $a_i, b_i, c_i$。

outputFormat: 一个正整数表示满足要求的最少话筒数。


title: 摇钱树

description: Cpg 正在游览一个梦中之城，在这个城市中有 $n$ 棵摇钱树。这下，可让 Cpg 看傻了。可是 Cpg 只能在这个城市中呆 $k$ 天，但是现在摇钱树已经成熟了，每天每棵都会掉下不同的金币（不属于 Cpg！）。Cpg 每天可以砍掉其中一颗，并获得其树上所有的金币（怎么会有这种好事）。请你帮助 Cpg 算出他在这 $k$ 天中最多能获得多少金币。

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

每个测试点中有不超过 $10$ 组的测试数据。

每组测试数据：

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

第二行包含 $n$ 个整数 $m_i$，表示 Cpg 刚看到这 $n$ 棵树时每刻树上的金币数。

第三行 $n$ 个整数 $b_i$，表示每颗摇钱树，每天将会掉落的金币。

以 `0 0` 结束。

outputFormat: 对每组测试数据，输出仅一行，Cpg 在 $k$ 天中能获得的最大金币数。


title: 火炬

description:
2008 北京奥运会，你想成为四川汶川的一名火炬手，经过层层选拔，终于到了最后一关。

这一关是一道很难的题：任意给定一个正整数 $N$，求一个最小的正整数 $M$，使得 $N \times M$ 的十进制表示形式里只含有 `1` 和 `0`。

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

outputFormat: 输出一行，如果有解，输出一个整数，表示最小的 $M$，否则输出 `No Solution`。


title: 覆盖墙壁

description:
你有一个长为 $N$ 宽为 $2$ 的墙壁，给你两种砖头：一个长 $2$ 宽 $1$，另一个是 L 型覆盖 $3$ 个单元的砖头。如下图：

```
0  0
0  00
```

砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖 $N\times 2$ 的墙壁的覆盖方法。例如一个 $2\times3$ 的墙可以有 $5$ 种覆盖方法，如下：
```
012 002 011 001 011
012 112 022 011 001
```
注意可以使用两种砖头混合起来覆盖，如 $2\times4$ 的墙可以这样覆盖：
```
0112
0012
```
给定 $N$，要求计算 $2\times N$ 的墙壁的覆盖方法。由于结果很大，所以只要求输出最后 $4$ 位。例如 $2\times 13$ 的覆盖方法为 $13465$，只需输出 $3465$ 即可。如果答案少于 $4$ 位，就直接输出就可以，不用加前导 $0$，如 $N=3$ 时输出 $5$。

inputFormat: 一个整数 $N$，表示墙壁的长。

outputFormat: 输出覆盖方法的最后 $4$ 位，如果不足 $4$ 位就输出整个答案。

hint: 数据保证，$1\leq N\leq 1000000$。


title: 无线通讯网

description:
国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络；

每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所（两边都有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 $D$，这是受收发器的功率限制。收发器的功率越高，通话距离 $D$ 会更远，但同时价格也会更贵。

收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 $D$。你的任务是确定收发器必须的最小通话距离 $D$，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

inputFormat:
第一行，$2$ 个整数 $S$ 和 $P$，$S$ 表示可安装的卫星电话的哨所数，$P$ 表示边防哨所的数量。

接下里 $P$ 行，每行两个整数 $x，y$ 描述一个哨所的平面坐标 $(x, y)$，以 km 为单位。

outputFormat: 第一行，$1$ 个实数 $D$，表示无线电收发器的最小传输距离，精确到小数点后两位。


title: 不想兜圈的老爷爷

description:
一位年过古稀的老爷爷在乡间行走

而他不想兜圈子 因为那会使他昏沉

偶然路过小A发扬助人为乐优良传统 带上地图 想知道路况是否一定使他清醒

usqwedf补充：为了让欢乐赛充满欢乐 小A还想问你一些数学作业……

inputFormat:
一行 n m k 表示乡间共有 n 个村庄 m 条道路

接下来 m 行 每行两个整数 x y 表示 村 x -> 村 y 单向连通

outputFormat:
第一行 输出 Yes/No [清醒/不清醒]

第二行 若为 Yes 输出 2^k对9997取模 反之 输出 k^2


title: 小 K 的农场

description:
小 K 在 MC 里面建立很多很多的农场，总共 $n$ 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 $m$ 个），以下列三种形式描述：
- 农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物；
- 农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物；
- 农场 $a$ 与农场 $b$ 种植的作物数一样多。

但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

inputFormat:
第一行包括两个整数 $n$ 和 $m$，分别表示农场数目和小 K 记忆中的信息数目。

接下来 $m$ 行：
- 如果每行的第一个数是 $1$，接下来有三个整数 $a,b,c$，表示农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物；
- 如果每行的第一个数是 $2$，接下来有三个整数 $a,b,c$，表示农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物;
- 如果每行的第一个数是 $3$，接下来有两个整数 $a,b$，表示农场 $a$ 种植的的数量和 $b$ 一样多。

outputFormat: 如果存在某种情况与小 K 的记忆吻合，输出 `Yes`，否则输出 `No`。

hint: 对于 $100\%$ 的数据，保证 $1 \le n,m,a,b,c \le 5 \times 10^3$。


title: 有机物燃烧

background: 本来准备弄难点的，还是算了吧

description: 输入一种有机物，输出与氧气反应化学方程式中CO2和H2O的系数

inputFormat: 一行，一个字符串，表示有机物

outputFormat: 两个数，分别为CO2和H2O的系数

hint: 只含有C、H、O三种元素


title: [NOI2011] 智能车比赛

description:
新一届智能车大赛在 JL 大学开始啦！比赛赛道可以看作是由 $n$ 个矩形区域拼接而成（如下图所示），每个矩形的边都平行于坐标轴，第 $i$ 个矩形区域的左下角和右上角坐标分别为 $(x_{i,1},y_{i,1})$ 和 $(x_{i,2},y_{i,2})$。

题目保证：$x_{i,1}<x_{i,2}=x_{i+1,1}$，且 $y_{i,1}< y_{i,2}$，相邻两个矩形一定有重叠在一起的边（如图中虚线所示），智能车可以通过这部分穿梭于矩形区域之间。

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

选手们需要在最快的时间内让自己设计的智能车从一个给定的起点 $S$ 点到达一个给定的终点 $T$ 点，且智能车不能跑出赛道。假定智能车的速度恒为 $v$ 且转向不消耗任何时间，你能算出最快需要多少时间完成比赛么？

inputFormat:
输入的第一行包含一个正整数 $n$，表示组成赛道的矩形个数。

接下来 $n$ 行描述这些矩形，其中第 $i$ 行包含 $4$ 个整数 $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}$，表示第 $i$ 个矩形左下角和右上角坐标分别为 $(x_{i,1}, y_{i,1})$ 和 $(x_{i,2}, y_{i,2})$。

接下来一行包含两个整数 $x_S, y_S$，表示起点坐标。

接下来一行包含两个整数 $x_T, y_T$，表示终点坐标。

接下来一行包含一个实数 $v$，表示智能车的速度。

outputFormat:
仅输出一个实数，至少精确到小数点后第六位，为智能车完成比赛的最快时间。

对于每个测试点，如果你的输出结果和参考结果相差不超过 $10^{-6}$，该测试点得满分，否则不得分。


title: 约瑟夫问题

description:
$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

**注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 $n-1$ 名小朋友，而该题是全部出圈。**

inputFormat: 输入两个整数 $n,m$。

outputFormat: 输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。


title: faebdc 的烦恼

background:
upd on On July 29, 2024：加入一组 hack 数据，之前的数据均满足 $q\le 10^5$。

鸟哥（faebdc）自从虐暴 NOIP2013 以来依然勤奋学习，每天上各种 OJ 刷题，各种比赛更是不在话下。但这天他遇到了一点小小的麻烦：在一届“Orz 鸟哥杯”上，题目是在是太多了！鸟哥看得头晕眼花，他需要你的帮助。

description:
这场比赛共有 $n$ 道题，每道题都有一个难度值 $a_i$，由于 wangxz 神犇已经提前帮助鸟哥将这些难度值升序排列，所以鸟哥并不想知道哪些题难度低或者高，他只想知道在某些题目 $a_l,a_{l+1},\ldots,a_r$中，出现最多的难度值出现的次数。

你的任务就是对于鸟哥的每一次询问 $(l, r)$，告诉他在从 $a_l$ 到 $a_r$ 这 $(r-l+1)$ 道题之中，出现最多的难度值出现的次数（询问共有 $q$ 次）。

如果你成功地帮助了鸟哥，鸟哥将会带你通过省选。

inputFormat:
每个测试点有且仅有一组测试数据。

第一行有两个整数，分别表示题目的数量 $n$ 和询问的次数 $q$。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 道题的难度。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。

outputFormat: 对于每组询问，输出一行一个整数表示答案。

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

对于全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq q \leq 2\times 10^5$，$-10^5 \leq a_i \leq 10^5$，$1 \leq l \leq r \leq n$。


title: 高维正方体

description:
$0$ 维空间的元素是点，这个毋庸置疑。

- $2$ 个 $0$ 维空间的元素可以围成一个 $1$ 维空间的元素，线段。
- $4$ 个 $1$ 维空间的元素可以围成一个 $2$ 维空间的元素，正方形。
- $6$ 个 $2$ 维空间的元素可以围成一个 $3$ 维空间的元素，正方体。
- $8$ 个 $3$ 维空间的元素可以围成一个 $4$ 维空间的元素，超正方体。

……

- 一个正方形中，有 $4$ 个（顶）点，$4$ 条线段（边），$1$ 个正方形。
- 一个正方体中，有 $8$ 个（顶）点，$12$ 条线段（棱），$6$ 个正方形（面），$1$ 个正方体。

……

我们的问题是：给出 $a$ 与 $b$，请求出：在 $a$ 维空间的元素中，包含着多少个 $b$ 维空间的元素。答案可能很大，只需要输出它除以 $10^9+7$ 的余数。

inputFormat: 两个整数 $a,b$，以空格隔开。

outputFormat: 一个整数，即答案。

hint:
### 样例解释

$3$ 维空间的元素是正方体，$1$ 维空间的元素是线段。所求即是一个正方体中棱的数量，为 $12$。

### 数据范围及约定

- 对于 $5\%$ 的数据，$a,b \le 1$；
- 对于 $10\%$ 的数据，$a,b \le 2$；
- 对于 $20\%$ 的数据，$a,b \le 3$；
- 对于 $35\%$ 的数据，$a,b \le 4$；
- 对于 $70\%$ 的数据，$a,b \le 1000$；
- 对于 $100\%$ 的数据，$0\le a,b \le 100000$。

此外，对于 $15\%$ 的数据，$b=0$，对于各 $10\%$ 的数据，$b=1$ 或 $b=2$。

### 提示

不保证 $a \ge b$。


title: 拯救世界

background: 公元 2000 年，根据预言家诺查丹玛斯的预言，世界就要毁灭了！！！

description:
为了拯救世界，小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。根据古籍记载，召唤出任何一位大神，都需要使用金木水火土五种五行神石来摆一个特定的大阵。而在古籍中，记载是这样的：

kkksc03 大神召唤方法：

- 金神石的块数必须是 $6$ 的倍数；
- 木神石最多用 $9$ 块；
- 水神石最多用 $5$ 块；
- 火神石的块数必须是 $4$ 的倍数；
- 土神石最多用 $7$ 块。

lzn 大神召唤方法:

- 金神石的块数必须是 $2$ 的倍数；
- 木神石最多用 $1$ 块；
- 水神石的块数必须是 $8$ 的倍数；
- 火神石的块数必须是 $10$ 的倍数；
- 土神石最多用 $3$ 块。

现在是公元 $1999$ 年 $12$ 月 $31$ 日，小 a 和 uim 从 $00{:}00{:}00$ 开始找，一直找到 $23{:}00{:}00$，终于，还是没找到神石。

不过，他们在回到家后在自家地窖里发现了一些奇怪的东西，一查古籍，哎呦妈呀，怎么不早点来呢？这里有一些混沌之石，可以通过敲击而衰变成五行神石。于是，他们拼命地敲，终于敲出了 $n$ 块神石，在 $23{:}59{:}59$ 完成了两座大阵。

然而，kkksc03 大神和 lzn 大神确实出现了，但是由于能量不够，无法发挥神力。只有把所有用 $n$ 块神石可能摆出的大阵都摆出来，才能给他们充满能量。这下小 a 和 uim 傻了眼了，赶快联系上了你，让你帮忙算一下，一共有多少种大阵。

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

outputFormat: 输出用 $n$ 块混沌之石能摆出的大阵的种数。

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

对于全部数据，$10^{99999}\leq n\lt 10^{100000}$。

### 提示

由于现在已经是 $23{:}59{:}59$，所以你只有 $0.5$ 秒时间。（小 a 与 uim 需要 $0.5\texttt s$ 排出所有阵法）。


title: 硬币的面值

description: 小 A 有 $n$ 种硬币，现在要买一样不超过 $m$ 元的商品，他不想得到找钱（多脏啊），同时又不想带太多的硬币，且硬币可以重复，现在已知这 $n$ 种硬币的价值，请问最少需要多少硬币就能组合成所有可能的价格？

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

下一行，共 $n$ 个数字，表示硬币的面值。

outputFormat: 一行一个数，表示最少需要多少硬币。如果无解请输出 `No answer!!!`。


title: 消息扩散

background: 本场比赛第一题，给个简单的吧，这 100 分先拿着。

description: 有 $n$ 个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出 $n$ 个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有 $n$ 个城市都得到消息。

inputFormat:
第一行两个整数 $n, m$，表示 $n$ 个城市，$m$ 条单向道路。

以下 $m$ 行，每行两个整数 $b, e$ 表示有一条从 $b$ 到 $e$ 的道路，道路可以重复或存在自环。

outputFormat: 一行一个整数，表示至少要在几个城市中发布消息。


title: [CRCI 2008] PLATFORME 平板

description:
为了进行一种游戏，现决定搭造一些平板，而各个平板的地址已经选定。基于最普遍的认识，没有任何支持物的平板不可能漂浮在空中。说的更精确些，任意一平板的两端必需有支柱或者它在另一块平板上。

你会得到各个平板在坐标系中的坐标（如左下图）。每一块平板的坐标都是由它的高度（与地板间的垂直距离）和它的水平方位（开始和结束）决定的。每个支柱都距它支撑的平板的边缘半个单位（如图）。

算出支持所有平板的支柱的总长度。

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

inputFormat:
第一行包括 $1$ 个整数 $N$，$1 \le N \le 100$，即平板的总数。

接下来的 $N$ 行每行都是一块平板的坐标，是相应的 $Y$，$X_1$ 和 $X_2$。即高度和水平的边缘坐标。所有的数都是不大于 $10000$ 的正整数且满足 $X_2>X_1+1$（也可这样理解，每一块平板的长度至少为 $2$）。

输入保证任意两块平板间没有重叠部分。

outputFormat: 要撑起所有平板所需的支柱的总长度。


title: 领地选择

description:
作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 $C\times C$ 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

inputFormat:
第一行三个整数 $N,M,C$，表示地图的宽和长以及首都的边长。

接下来 $N$ 行每行 $M$ 个整数，表示了地图上每个地块的价值。价值可能为负数。

outputFormat: 一行两个整数 $X,Y$，表示首都左上角的坐标。


title: A/B Problem II

background: 为了让大家紧张的心情放松一下，这一题题是一道非常简单的题目。

description: 给出正整数 $N$ 和 $M$，请你计算 $N \div M$（$N / M$ 的下取整）。

inputFormat: 两行，两个正整数，$N$ 和 $M$。

outputFormat: 一行，一个整数，表示 $N \div M$。

hint:
- 对于 $60 \%$ 的数据：$ N,M \le 750!$，答案 $ \le 7!$。
- 对于 $100 \%$ 的数据：$N,M \le 6250!$，答案 $ \le 13!$。

请注意：上面的两句话并不是感叹句，而是陈述句。标点符号使用没有错误。


title: 赵神牛的游戏

description:
在 DNF 中，赵神牛有一个缔造者，他一共有 $k$ 点法力值，一共有 $m$ 个技能，每个技能耗费的法力值为 $a_i$，可以造成的伤害为 $b_i$，而 boss 的体力值为 $n$，请你求出它放哪个技能，才可以打死 boss。

当然，赵神牛技术很菜，他一局只放一个技能,不过每个技能都可以放无数次。

inputFormat:
第一行有三个整数，分别表示 $k,m,n$。

后面 $m$ 行，每行两个整数，第 $(i + 1)$ 行的整数表示耗费的法力值 $a_i$ 和造成的伤害 $b_i$。

outputFormat: 输出仅一行，即可以杀死 boss 的技能序号，如果有多个，按从小到大的顺序输出，中间用一个空格隔开；如果没有技能能杀死 boss，输出 `-1`。

hint:
#### 数据规模与约定
对于全部的测试点，满足：

- $0\le n,m,k\le 3\times 10^4$,
- $0 \leq a_i,b_i\le 2147483647$。


title: 魔方

background: 常神牛从来没接触过魔方，所以他要借助计算机来玩。即使是这样，他还是很菜。

description:
常神牛家的魔方都是3\*3\*3的三阶魔方，大家都见过。

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

（更正：3 4以图为准。）

作为一名菜鸟，常神牛从网上搜了一篇攻略，并找人翻译成了他自己会做的方法。现在告诉你他的魔方情况，以及他从网上搜到的攻略，请你求出最后魔方变成什么样子。

inputFormat:
第一行，一串数字（长度不大于100），表示常神牛从网上搜到的攻略。

下面6\*3行，每行3个数字，每三行表示魔方一个面的情况，六个面的顺序是前、后、左、右、上、下。

outputFormat: $6 \times 3$ 行，表示处理后的魔方，形式同输入。

hint:
【样例解释】

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

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


title: 大朋友的数字

background: 在 NOIP2013 的赛场上，常神牛华丽丽的手残了，小朋友的数字一题只得了 $10$ 分。于是，他要恶搞一下这道题。

description: 有一批大朋友（年龄 $15$ 岁以上），他们每人手上拿着一个数字，当然这个数字只有 $1$ 位，也就是 $0$ 到 $9$ 之间。每个大朋友的分数为在他之前的最长不下降子序列中所有数之和。（这个序列必须以它作为结尾！）如有多个最长不下降子序列，那么取编号字典序最小的。现在告诉你有 $n$ 个大朋友，以及他们各自的数字，请你求出他们每个人的分数。

inputFormat:
第一行，$1$ 个数 $n$。

第二行，$n$ 个数，分别表示每个人的数字。

outputFormat: 一行，$n$ 个数，分别表示每个人的分数。


title: 跑步

background: 跑步是一项有意思的运动，尤其是可以开发人的脑筋。常神牛很喜欢跑步。

description:
常神牛跑步的场地是一个多边形（边数 $\leq 20$，每个顶点用英文大写字母表示），并且在这个多边形内部，还会有一些小道，连接两个不相邻的顶点。所有的边长和小道都是双向通行的举例来说，下面一个图：

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

假设常神牛从 $A$ 点跑到 $D$ 点，最短的路径是 $A-E-D$（长度为 $6$）。

现在告诉你多边形的边数 $n$，多边形每条边的长度，多边形内的连线数 $k$，每条连线的两个端点及长度，以及起始点和结束点，请你输出最短路径的长度。但是常神牛有点强迫症，如果两点之间有多条道路直接连接，他会选择最长的那条。

注意：输入数据不保证起点和终点不同，也不保证小道的起点和终点不同。在读入过程中，如果两点之间有多条小道，那么它们间的距离为这些小道的最大值。所以，如果读入一个小道起点和终点相同，那么这个点到它本身的距离不为 $0$。

inputFormat:
第一行，$2$ 个数，$n,k$。

第二行，$n$ 个数，分别表示多边形每条边的长度（按顺时针次序依次给出，即分别为 $AB,BC,CD,DE……$ 的长度）。

以下 $k$ 行，每行两个字母和一个数，两个字母表示该连线的起止点，数字表示长度。

最后一行，两个字母，分别为他跑步的起点和终点。

所有的一行的字母、数字之间用一个空格隔开。

outputFormat: 一行，一个数，表示最短路的长度。

hint:
对于 $20\%$ 的数据，$k=0$；

对于 $50\%$ 的数据，$k \leq 10$；

对于 $100\%$ 的数据，$1 \leq n \leq 20$，$0 \leq m \leq 50$，$k \leq 100$，所有路径长度均不大于 $1000$。


title: [NOIP2016 普及组] 回文日期

background: NOIP2016 普及组 T2

description:
在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 $8$ 位数字表示一个日期，其中，前 $4$ 位代表年份，接下来 $2$ 位代表月份，最后 $2$ 位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的 $8$ 位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 $8$ 位数字是回文的，当且仅当对于所有的 $i$（$1  \le i \le 8$）从左向右数的第 $i$ 个数字和第 $9-i$ 个数字（即从右向左数的第 $i$ 个数字）是相同的。

例如：

- 对于 2016 年 11 月 19 日，用 $8$ 位数字 $20161119$ 表示，它不是回文的。
- 对于 2010 年 1 月 2 日，用 $8$ 位数字 $20100102$ 表示，它是回文的。
- 对于 2010 年 10 月 2 日，用 $8$ 位数字 $20101002$ 表示，它不是回文的。

每一年中都有 $12$ 个月份：

其中，$1, 3, 5, 7, 8, 10, 12$ 月每个月有 $31$ 天；$4, 6, 9, 11$ 月每个月有 $30$ 天；而对于 $2$ 月，闰年时有 $29$ 天，平年时有 $28$ 天。

一个年份是闰年当且仅当它满足下列两种情况其中的一种：

1. 这个年份是 $4$ 的整数倍，但不是 $100$ 的整数倍；
2. 这个年份是 $400$ 的整数倍。

例如：

- 以下几个年份都是闰年：$2000, 2012, 2016$。
- 以下几个年份是平年：$1900, 2011, 2014$。

inputFormat:
两行，每行包括一个 $8$ 位数字。

第一行表示牛牛指定的起始日期。

第二行表示牛牛指定的终止日期。

保证 $\mathit{date}_1$ 和 $\mathit{date}_2$ 都是真实存在的日期，且年份部分一定为 $4$ 位数字，且首位数字不为 $0$。

保证 $\mathit{date}_1$ 一定不晚于 $\mathit{date}_2$。

outputFormat: 一个整数，表示在 $\mathit{date}_1$ 和 $\mathit{date}_2$ 之间，有多少个日期是回文的。

hint:
**【样例说明】**

对于样例 1，符合条件的日期是 $20111102$。

对于样例 2，符合条件的日期是 $20011002$ 和 $20100102$。

**【子任务】**

对于 $60 \%$ 的数据，满足 $\mathit{date}_1 = \mathit{date}_2$。


title: 计算电压

background: 相信不少人轻松灭掉 1，2 两题（蒟蒻无视此句） ，我相信，大家对物理也是很有兴趣的（众人：我们对揍人也是很有兴趣的） ，那么，再奉上 100 分给 Physicaler 们。

description: 现给定一个电阻网络，已知其中每条边上的电阻，和若干个点和负极之间的电压（电源电压不变） ，现在求任意两点之间的电压。

inputFormat:
第一行四个正整数 $n,m,k,q$，表示有 $n$ 个节点（可能是几个点用导线相连接，与一个点等价，编号为 $1$ 至 $n$，$0$ 号节点为电源负极），$m$ 个定值电阻（每个定值电阻连接两个点），电源正极有 $k$ 个接口，有 $q$ 个询问。

接下来 $k$ 行，每行两个正整数，表示这个正极的编号与该接线柱与电源负极之间的电压 $u_i$。

再接下来 $m$ 行，每行三个正整数 $v_i,w_i,r_i$，表示节点 $v_i$ 与 $w_i$ 之间有一条阻值为 $r_i$ 的电阻丝。

再接下来 $q$ 行，每行两个正整数 $a_i,b_i$，表示要求 $a_i$ 与 $b_i$ 之间的电压。

outputFormat: 一共 $q$ 行，每行一个实数表示 $a_i$ 与 $b_i$ 之间的电压（保留两位小数）。若 $a_i$ 点电压小于 $b_i$ 点电压，输出负值。

hint:
【数据范围】

对于 $10\%$ 的数据，$1\le q\le 10$；

对于 $20\%$ 的数据，$1\le n\le 10$，且保证电路为串联、并联或混联；

对于 $40\%$ 的数据，$1\le n\le 40$，$k\le 5$；

对于 $100\%$ 的数据，$1\le k\le n\le 200$，$1\le m\le 2\times 10^5$，$1\le r_i,u_i\le 10^4$，$1\le q\le 10^6$。

【时空限制】

时间限制：1.00s，空间限制：125.00MB。

【样例解释】

如图所示。

![样例解释](https://cdn.luogu.com.cn/upload/pic/722.png)


title: 拯救世界2

background: 前三题太弱了嘛，在看看最后一道渣题。

description:
经过 12 年的韬光养晦，世界末日再次来临（众人：什么鬼逻辑......）。

这次，小a 和 uim 已经做好了一切准备，顺利召唤出了 kkksc03 大神和 lzn 大神。然而，kkksc03 和 lzn 告诉他们，这次世界末日太过强大，他们已无法挽回，只有创世神 JOHNKRAM 能拯救这个世界。

然而，创世神 JOHNKRAM 是无法召唤的，除非把整个宇宙按照 $E=mc^2$ 全部转化成能量。因为根据 C\_SUNSHINE 大神随手推算出的召唤定律，至少需要被召唤者百万亿分之一的能量才能召唤（众人：什么鬼定律......）。
****
当然，还有一种方法，那就是找出创世神 JOHNKRAM 的基因序列。普通人基因序列由 A、C、G、T 构成，创世神 JOHNKRAM 不是普通人（是个胖纸），基因序列也不一样。除了这四种普通的，还有乾、兑、离、震、巽、坎、艮、坤八种特殊基因。其中乾、坎、艮、震属阳，只能出现奇数次；坤、兑、离、巽属阴，只能出现偶数次。

现在只知道创世神 JOHNKRAM 的基因序列共有 $n$ 位，其他一概不知。小a 和 uim 想知道他们最多要试多少次，才能召唤出创世神 JOHNKRAM 。这个数字有可能很大，所以输出答案模 $10^9$ 即可（C\_SUNSHINE 的忠告：远离八卦，远离肥胖）。

inputFormat: 输入由多组数据组成，每组数据一行，输入一个数 $n$，输入以 $0$ 结束。

outputFormat: 对于每组数据，输出一行一个整数，表示答案对 $10^9$ 取模的结果。

hint:
【数据范围】
对于 $10\%$ 的数据：$1\le n < 25$，数据不超过 $10$ 组；
对于 $50\%$ 的数据：$1\le n < 2^{31}$，数据不超过 $10^3$ 组；
对于 $100\%$ 的数据：$1\le n < 2^{63}$，数据不超过 $2\times 10^5$ 组。

【样例解释】
第一个数据解释：
只有 $3$ 位，没有合法方案，故答案为 $0$。

【备注】

附件：聊天记录（纯粹扯淡）

JOHNKRAM 8:50:33

喂喂，坑神之赛2可以开始了吧

C_SUNSHINE 8:50:34

[自动回复]恩！

JOHNKRAM 8:51:12

我准备把最后一题数据从 $50$ 放到 $2^{63}$。

C_SUNSHINE 8:51:12

[自动回复]恩！

JOHNKRAM 8:51:45

你同意喽？

C_SUNSHINE 8:51:46

[自动回复]恩！

C_SUNSHINE 11:58:50

你疯了吗？！

JOHNKRAM 11:58:52

[自动回复]您好，我现在有事不在，一会再和您联系。 不再提醒


title: 无线电测向

description:
有天线定位装置的船能通过接收当地灯塔信号来确定自己的位置。每个灯塔固定在已知点上并发出特有的信号。当船检测到信号，它可通过旋转天线直到信号达到最大强度。这样就可确定自身与该灯塔的位置关系。只要接收到两个灯塔的信息，就有可能确定船当前的位置。

编程任务：通过一对灯塔信息来确定船的位置。

灯塔和船的位置被确定在一个直角坐标系内。$x$ 轴正向指向东，$y$ 轴正向指向北。船的航行路线从正北开始按顺时针用度表示。北是 $0^\circ$，东是 $90^\circ$，南是 $180^\circ$，西是 $270^\circ$。灯塔与船的位置关系用相对于船的航行方向顺时针用度表示。

inputFormat:
文件的第一行是一个整数，表示灯塔的数目 $N$。以下 $N$ 行，每行表示一个灯塔，为灯塔名称，$x$ 坐标和 $y$ 坐标。它们都用空格隔开。

灯塔信息下面是船的信息包括三行，一行是船的方向，其余两行是所接收到的灯塔信号。

具体如下：

| 输入数据 | 数据的含义|
| :-: | :-:|
| 方向 | 船的航行方向 |
| 名称 $1$，角度 $1$ | 第一个灯塔信息的名称，灯塔的方位 |
| 名称 $2$，角度 $2$ | 第二个灯塔信息的名称，灯塔的方位 |

灯塔的方位为船与灯塔所在的直线与船的航行方向的夹角（从船的航行方向开始顺时针）。$2$ 个数据用空格隔开。

outputFormat: 输出船的位置（精确到 $2$ 位小数）。如果无法确定船的位置，应输出 `NO ANSWER`（不能使用小写）。

hint: 对于 $100 \%$ 的数据，$1 \le N \le 30$，灯塔名称是 $20$ 个以下的字母。


title: [CTSC1997] 选课

description: 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

inputFormat:
第一行有两个整数 $N$ , $M$ 用空格隔开。( $1 \leq N \leq 300$ , $1 \leq M \leq 300$ )

接下来的 $N$ 行,第 $I+1$ 行包含两个整数 $k_i $和 $s_i$, $k_i$ 表示第I门课的直接先修课，$s_i$ 表示第I门课的学分。若 $k_i=0$ 表示没有直接先修课（$1 \leq {k_i} \leq N$ , $1 \leq {s_i} \leq 20$）。

outputFormat: 只有一行，选 $M$ 门课程的最大得分。


title: 二叉苹果树

description:
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：

```
2   5
 \ /
  3   4
   \ /
    1
```

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

inputFormat:
第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。

接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。

outputFormat: 一个数，最多能留住的苹果的数量。

hint: $1 \leqslant Q < N \leqslant 100$，每根树枝上的苹果 $\leqslant 3 \times 10^4$。


title: 战略游戏

background: Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。

description:
他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。

请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。

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

第二行至第 $n+1$ 行，每行描述每个结点信息，依次为：一个整数 $i$，代表该结点标号，一个自然数 $k$，代表后面有 $k$ 条无向边与结点 $i$ 相连。接下来 $k$ 个整数，分别是每条边的另一个结点标号 $r_1,r_2,\cdots,r_k$，表示 $i$ 与这些点间各有一条无向边相连。

对于一个 $n$ 个结点的树，结点标号在 $0$ 到 $n-1$ 之间，在输入数据中每条边只出现一次。保证输入是一棵树。

outputFormat: 输出文件仅包含一个整数，为所求的最少的士兵数目。

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

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


title: [USACO09DEC] Dizzy Cows G

description:
The cows have taken to racing each other around the farm but they get very dizzy when running in circles, and everyone knows that dizzy cows don't produce any milk. Farmer John wants to convert all of the two-way cow paths in the farm to one-way paths in order to eliminate any 'cycles' and prevent the cows from getting dizzy.  A 'cycle' enables a cow to traverse one or more cow paths and arrive back at her starting point, thus completing a loop or circle.

The farm comprises N pastures (1 <= N <= 100,000) conveniently numbered 1..N. M1 (1 <= M1 <= 100,000) one-way cow paths and M2 two-way cow paths (1 <= M2 <= 100,000) connect the pastures. No path directly connects a pasture to itself, although multiple paths might connect two different pastures. A cow may or may not be able to travel between any two given pastures by following a sequence of cow paths.

Your job is to assign a direction to the two-way cow paths such that the entire farm (ultimately with only one-way paths) has no cycles. That is, there should be no sequence of one-way cow paths which leads back to its starting position. The existing one-way cow paths do not form a cycle and should be left as they are.

One-way cow paths run from pasture A\_i (1 <= A\_i <= N) to pasture B\_i (1 <= B\_i <= N). Two-way cow paths connect pastures X\_i (1 <= X\_i <= N) and Y\_i (1 <= Y\_i <= N).

Consider this example:

```cpp
1-->2
|  /|
| / |
|/  |
3<--4
```
The cow paths between pastures 1 and 3, 2 and 3, and 2 and 4 are two-way paths. One-way paths connect 1 to 2 and also 4 to 3. One valid way to convert the two-way paths into one-way paths in such a way that there are no cycles would be to direct them from 1 to 3, from 2 to 3, and from 3 to 4:

```cpp
1-->2
|  /|
| / |
vL  v
3<--4
```

inputFormat:
第一行三个整数 $n,m_1,m_2$，分别表示点数，有向边的数量，无向边的数量。

第二行起输入 $m_1$ 行，每行 $2$ 个整数 $a,b$，表示 $a$ 到 $b$ 有一条有向边。

接下来输入 $m_2$ 行，每行 $2$ 个整数 $a,b$，表示 $a$ 和 $b$ 中间有一条无向边。

outputFormat:
对于每条无向边，我们要求按输入顺序输出你定向的结果，也就是如果你输出 $a\ b$，那表示你将 $a$ 和 $b$ 中间的无向边定向为 $a \to b$。

注意，也许存在很多可行的解。你只要输出其中任意一个就好。

translation:
奶牛们发现，在农场里面赛跑是很有趣的一件事.可是她们一旦在农场里面不断地转圈，就 会变得头晕目眩.众所周知，眩晕的奶牛是无法产奶的.于是，农夫约翰想要把他农场里面的双 向道路全部改为单向道路，使得他的农场里面一个圈都没有，以避免他的奶牛们被搞得晕头转 向.如果奶牛可以经过若干条道路回到起点，那么这些道路就称为一个圈.

农场有 $n\ (1 < n < 100000)$ 片草地，编号为 $1$ 到 $n$。这些草地由 $m_1$ 条单向 道路和 $m_2$ 条双向道路连接起来.任何一条道路都不会把一片草地和这片草地本身连接起来.但是，任意两片草地之间都可能有多条道路连接.不保证任意两片草地之间都有路 径相连。

你的任务是给所有的双向道路设定一个方向，使得整个农场(只剩下单向道路)最后一个圈都没有。也就是说，不存在一个单向道路序列的终点和起点重合。数据保证一开始就有的单向道路中，一个圈都没有。而且一开始就有的单向道路不能改变。

单向道路的起点是草地 $A_i$，终点是草地 $B_i$。双向道路连接草地 $X_i,Y_i$。


title: 消息传递

description:
巴蜀国的社会等级森严，除了国王之外，每个人均有且只有一个直接上级，当然国王没有上级。如果 $A$ 是 $B$ 的上级，$B$ 是 $C$ 的上级，那么 $A$ 就是 $C$ 的上级。绝对不会出现这样的关系：$A$ 是 $B$ 的上级，$B$ 也是 $A$ 的上级。

最开始的时刻是 $0$，你要做的就是用 $1$ 单位的时间把一个消息告诉某一个人，让他们自行散布消息。在任意一个时间单位中，任何一个已经接到消息的人，都可以把消息告诉他的一个直接上级或者直接下属。

现在，你想知道：

1. 到底需要多长时间，消息才能传遍整个巴蜀国的所有人？
2. 要使消息在传递过程中消耗的时间最短，可供选择的人有那些？

inputFormat: 输入文件的第一行为一个整数 $N$（$N\le 1000$），表示巴蜀国人的总数，假如人按照 $1$ 到 $n$ 编上了号码，国王的编号是 $1$。第 $2$ 行到第 $N$ 行（共 $N-1$ 行），每一行一个整数，第 $i$ 行的整数表示编号为 $i$ 的人直接上级的编号。

outputFormat:
文件输出共计两行：

- 第一行为一个整数，表示最后一个人接到消息的最早时间。
- 第二行有若干个数，表示可供选择人的编号，按照编号从小到大的顺序输出，中间用空格分开。


title: [NOI2011] 兔农

description:
农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。

问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 $n$ 个月有多少只兔子？

聪明的你可能已经发现，第 $n$ 个月的兔子数正好是第 $n$ 个 Fibonacci（斐波那契）数。栋栋不懂什么是 Fibonacci 数，但他也发现了规律：第 $i+2$ 个月的兔子数等于第 $i$ 个月的兔子数加上第 $i+1$ 个月的兔子数。前几个月的兔子数依次为：

$$1,1,2,3,5,8,13,21,34,\ldots$$

栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。

每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每 $k$ 对兔子围成一圈，最后剩下的不足 $k$ 对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。

我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当 $k=7$ 时，前几个月的兔子数依次为：

$$1,1,2,3,5,7,12,19,31,49,80,\ldots$$

给定 $n$，你能帮助栋栋计算第 $n$ 个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第 $n$ 个月的兔子对数除 $p$ 的余数即可。

inputFormat: 输入一行，包含三个正整数 $n, k, p$。

outputFormat: 输出一行，包含一个整数，表示栋栋第 $n$ 个月的兔子对数除 $p$ 的余数。


title: faebdc玩扑克

background: faebdc 和 zky 在玩一个小游戏

description: zky 有 $n$ 个扑克牌，编号从 $1$ 到 $n$，zky 把它排成一个序列，每次把最上方的扑克牌放在牌堆底，然后把下一张扑克牌拿出来输出，最终输出的序列恰好是从 $1$ 到 $n$，faebdc 问你原序列是什么，因为 faebdc 神犇早已在 $\mathcal O (1)$ 的时间得出结果，如果你在 1 s 内答不出来，faebdc 会吃了你。

inputFormat: 一个整数 n，表示扑克数目。

outputFormat: $n$ 个数，表示扑克序列。


title: 有趣的数

description:
让我们来考虑 $1$ 到 $N$ 的正整数集合。让我们把集合中的元素按照字典序排列，例如当 $N=11$ 时，其顺序应该为：$1,10,11,2,3,4,5,6,7,8,9$。

定义 $K$ 在 $N$ 个数中的位置为 $Q(N,K)$，例如 $Q(11,2)=4$。现在给出整数 $K$ 和 $M$，要求找到最小的 $N$，使得 $Q(N,K)=M$。

inputFormat: 输入文件只有一行，是两个整数 $K$ 和 $M$。

outputFormat: 输出文件只有一行，是最小的 $N$，如果不存在这样的 $N$ 就输出 $0$。


title: [AHOI2009] 维护序列

background: 老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

description:
有一个长为 $n$ 的数列 $\{a_n\}$，有如下三种操作形式：

1. 格式 `1 t g c`，表示把所有满足 $t\le i\le g$ 的 $a_i$ 改为 $a_i\times c$ ;
2. 格式 `2 t g c` 表示把所有满足 $t\le i\le g$ 的 $a_i$ 改为 $a_i+c$ ;
3. 格式 `3 t g` 询问所有满足 $t\le i\le g$ 的 $a_i$ 的和，由于答案可能很大，你只需输出这个数模 $p$ 的值。

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

第二行含有 $n$ 个非负整数，表示数列 $\{a_i\}$ 。

第三行有一个整数 $m$，表示操作总数。

从第四行开始每行描述一个操作，同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

outputFormat: 对每个操作 3，按照它在输入中出现的顺序，依次输出**一行一个整数**表示询问结果。


title: [NOI2001] 食物链

description:
动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。

现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

- 第一种说法是 `1 X Y`，表示 $X$ 和 $Y$ 是同类。
- 第二种说法是`2 X Y`，表示 $X$ 吃 $Y$。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
- 当前的话表示 $X$ 吃 $X$，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。

inputFormat:
第一行两个整数，$N,K$，表示有 $N$ 个动物，$K$ 句话。

第二行开始每行一句话（按照题目要求，见样例）

outputFormat: 一行，一个整数，表示假话的总数。

hint: 对于全部数据，$1\le N\le 5 \times 10^4$，$1\le K \le 10^5$。


title: 求一次函数解析式

background: 做数学寒假作业的怨念……

description: 给定两个整点的坐标，求它们所在直线的函数解析式（一次函数）。

inputFormat:
第一行有两个整数 $x_1,y_1$，表示第一个整点的坐标为 $(x_1,y_1)$。

第二行有两个整数 $x_2,y_2$，表示第二个整点的坐标为 $(x_2,y_2)$。

outputFormat: 输出共一行，即这个函数解析式。


title: bf

description:
bf 是一种编程语言，全称为 BrainFuck，因为题目名称不能太露骨，所以就简写成 bf 了。

这种语言的运行机制十分简单，只有一个大小为 $30000$ 的有符号 $8$ 位整数（范围 $[-128,127]$ ）的内存槽，和一个指向内存槽中位置的指针，在最初的时候指向内存槽的第一个整数。

这种语言的字符集也是十分的简单，只有`+ - , . > < []`。

```cpp
字符|意义
< 　|指针所指向的内存地址减一。
> 　|指针所指向的内存地址加一。
+ 　|指针所指向的内存里面的数值加一。
- 　|指针所指向的内存里面的数值减一。
. 　|输出当前指针所指向的内存里面的数值（以字符形式输出）。
, 　|将读入缓冲区中的一个字节送入当前指针指向的内存里面。如果读入缓冲区为空则送入-1。
[ 　|当前指针指向的内存里面的数值不为0时，重复执行与之相匹配的]之间的语句，直到回到[时当前指针指向的内存中的数值为0。
] 　|如上。
```

inputFormat:
输入数据若干行，代码有注释。直到一个 `$` 为代码截止。

`$` 后面紧跟一个空格（不属于输入缓冲区），空格后面是输入缓冲区里面的内容，以一个空格和一个 `$` 截止。

outputFormat: 输出这段代码的执行结果。

samples:
write whatever u c ,.,.,.,. $ asdf $
asdf

hint:
对于 $10\%$ 的数据，没有循环。

对于另外 $10\%$ 的数据，循环没有嵌套。

对于 $100\%$ 的数据，输入的程序不会访问越界，输入的程序能够在 $10^6$ 步内运行结束，| 输入的字符串 | $\leq 30000$。
字符在内存中的数值为字符所对应的 Ascii 码。


title: 龙兄摘苹果

description:
龙兄在淘淘摘苹果的那个果园里摘了 $n$ 个完全互不相同的苹果，好客的园主为他提供了 $k$ 个篮子，他想把苹果装在篮子里拎回家（由于龙兄的手是无限大的，所以你不必考虑他能不能同时拎这么多篮子）。

同时，他不希望有任何一个篮子里是空的，因为这样就做不到物尽其用。因此他想知道一共有多少种放苹果的方法，由于他的大脑运算过慢，所以找到了聪明机智的你，他在摘苹果上已经花了很长时间，所以他只能等 $1$ 秒。

由于方法很可能非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常多，龙兄的大脑无法存储，所以他会给你一个数 $p$，输出方法数除以 $p$ 的余数就可以了。

inputFormat: 一行三个数，依次为 $n$，$k$，$p$，含义如题面所示。

outputFormat: 一个数，方法数除以 $p$ 的余数，行末有回车。


title: 跳舞

description:
小明今天得到一个跳舞毯游戏程序Dance。游戏每次连续出N个移动的“箭头”，箭头依次标号为1到N，并且的相应的分数S[1..N]。如果你能“踏中”第i号箭头，你将获得相应的分数S[i]；否则将被扣除相应的分数。

另外，游戏还有一个累计奖励机制：如果踏准次数累计达到T，并且是在踏中第i个箭头达到的，则将得到B[i]的奖励分数,累计也将清零，重新开始。

例如：N＝6，T=3，相应的S和B分别为{1,2,3,4,5,6}、{0,0,4,7,9,10},如果小明踏中所有箭头，则得分为：(1+2+3+4)+(4+5+6+10)＝35

小明是个Dance高手，可以踏中他想踏中的任意一个箭头。但他发现，根据给定的N，T，S，B，踏中所有的箭头不一定能得最高分，小明很想知道最高能得多少分，你能帮助小明计算一下最多可得多少分吗？

inputFormat:
第一行两个整数N和T。

第二行N个整数，为S的相应分数。

第三行也有N个整数，为B的相应分数。

outputFormat: 一个整数，可得到的最高分数。

hint:
【样例解释】

跳过第一个，扣1分，连踩3个，得9分，并获得附加分20分，之后再连踩2个，共39分。

【数据范围】

对于20%的数据0≤N,T≤100；

对于100%的数据0≤N,T≤5000；

S和B各有N个数，所有分数为[0，10000]之间的整数。


title: 遥控车

description:
平平带着韵韵来到了游乐园，看到了 $n$ 辆漂亮的遥控车，每辆车上都有一个唯一的名字 name[i]。韵韵早就迫不及待地想玩名字是 $s$ 的遥控车。可是韵韵毕竟还小，她想象的名字可能是一辆车名字的前缀（也就是说能确定一个 $i$，使 $s$ 是 name[i] 的前缀），这时她就能玩第 $i$ 辆车；或者是一个无中生有的名字，即 $s$ 不是任何一辆车名字的前缀，这时候她什么也不能玩。

你需要完成下面的任务：

1. 韵韵想了 $m$ 个她想要的名字，请告诉她能玩多少次。

2. 由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第 $i$ 辆车现在的位置可能是 $i-1$ 、 $i$ 、 $i+1$ 中的任意一个（第 $1$ 辆车的位置不可能是 $0$，第 $n$ 辆车的位置不可能是 $n+1$）。请你计算出共有多少种可能的排列。

注：数据保证当 $s$ 是 name[i] 的前缀时，$i$ 是唯一确定的。一辆车可以玩多次。

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

接下来 $n$ 行，每行 $1$ 个字符串 name[i]，表示第 $i$ 辆车的名字。接下来 $m$ 行，每行 $1$ 个字符串 $s$，表示韵韵想要的名字。

outputFormat: 第一行输出韵韵能玩的次数。第二行输出共有多少种可能的排列。

hint:
【注意】

对于题目涉及到的字符串严格区分大小写，且长度小于 $255$。

【数据范围】

对于 $20\%$ 的数据 $n \le 10,m \le 10$；

对于 $40\%$ 的数据 $n \le 1000$，$m \le 1000$；

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


title: 脑力达人之分割字串

background:
好吧，该来的废话还是要来的。

画外音：

终于，在两轮的重重选拔之后，我们的海选终于结束了。现在进入我们的循环赛环节。循坏赛一共有四场，最后选出得分最高的 $16$ 人进入对决，得分相同则和按用时排名，若仍有不能确定 $16$ 人的情况，则去尾处理。

欢迎您收看有洛谷卫视重磅推出的综合性文艺知识类节目“开心玩游戏，轻松赢比赛”，我是 LUWM。学编程，就选洛谷， 感谢洛谷 Online Judge 对本节目的大力支持。下面，我们有请 $10$ 位选手上台，由大屏幕给出题目。

description: 现在有一个字符串，你可以对这个字符串进行拆分，如 `abcvsdaas` 可以拆分为 `abc|vs|d|aas`，现在再给你一个字典，要求分割成的每一个子串必须要有包含其中的任意一个单词。那么最多可以分为几个子串呢？

inputFormat:
第一行，一行字符串

第二行一个正整数 $N$，表示字典中字符串的数量

接下来 $N$ 行，每行一个字符串 $A_i$，表示字典中的一个字符串。

outputFormat: 一个整数，表示最多的分割数。

hint:
特殊情况：

如果原字符串不能被分割，请输出 $0$。

数据范围：

对于 $20\%$ 的数据，$1\leq |s| \leq 50,1\leq n\leq 50$。

对于 $100\%$ 的数据，$1\leq |A_i| \leq |s|\leq 300，1\leq N\leq 500$。

其中，$|s|,|A_i|$ 表示字符串 $s$ 与 $A_i$ 的长度。


title: 扫描

description:
有一个 $1 \times n$ 的矩阵，有 $n$ 个整数。

现在给你一个可以盖住连续 $k$ 个数的木板。

一开始木板盖住了矩阵的第 $1 \sim k$ 个数，每次将木板向右移动一个单位，直到右端与第 $n$ 个数重合。

每次移动前输出被覆盖住的数字中最大的数是多少。

inputFormat:
第一行两个整数 $n,k$，表示共有 $n$ 个数，木板可以盖住 $k$ 个数。

第二行 $n$ 个整数，表示矩阵中的元素。

outputFormat:
共 $n - k + 1$ 行，每行一个整数。

第 $i$ 行表示第 $i \sim i + k - 1$ 个数中最大值是多少。

hint:
对于 $20\%$ 的数据，$1 \leq k \leq n \leq 10^3$。

对于 $50\%$ 的数据，$1 \leq k \leq n \leq 10^4$。

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^6$，矩阵中的元素大小不超过 $10^4$ 并且均为正整数。


title: Chessboard Dance

description:
在棋盘上跳舞是件有意思的事情。现在给你一张国际象棋棋盘和棋盘上的一些子以及你的初始位置和方向。求按一定操作后，棋盘的状态。

操作有四种，描述如下：

move n        n是非负整数，表示你按目前所在方向前进n步，如果即将走出棋盘，则停止。如果面前有棋子，则将其向前推一步。

turn left    向左转90度

turn right    向右转90度

turn back    向后转

inputFormat:
输入前8行，每行8个字符，给出棋盘状态。“.”表示该格为空，字母表示棋子，不同字母表示不同的棋子。你所在位置用“^”、“<”、“>”、“v”四个字母中一个表示，分别表示你的方向上、左、右、下。

接下来有若干行，每行一个操作。以“#”结束。操作数不超过1000个。

outputFormat: 输出8行，每行8个字符，表示经过一系列操作后棋盘和你的状态。表示方法同输入。


title: 选择数字

description: 给定一行 $n$ 个非负整数 $a_1 \cdots a_n$。现在你可以选择其中若干个数，但不能有超过 $k$ 个连续的数字被选择。你的任务是使得选出的数字的和最大。

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

以下 $n$ 行，每行一个整数表示 $a_i$。

outputFormat: 输出一个值表示答案。


title: [USACO08JAN] iCow B

description:
被无止境的农活压榨得筋疲力尽后，FarmerJohn 打算用他在 MP3 播放器市场新买的 iCow 来听些音乐，放松一下。FJ 的 iCow 里存了 $N(1 \le N \le 1{,}000)$ 首曲子，按 $1..N$ 依次编号。至于曲子播放的顺序，则是按一个 FarmerJohn 自己设计的算法来决定：

- 第 $i$ 首曲子有一个初始权值 $R_i\ (1 \le R_i \le 10{,}000)$。
-  当一首曲子播放完毕，接下来播放的将是所有曲子中权值最大的那首（如果有两首或多首曲子的权值相同，那么这些曲子中编号最小的那首会被选中）。
- 一首曲子在播放结束后，它的权值会被平均地分给其他 $N-1$ 首曲子，它本身的权值清零。
- 如果一首曲子的权值无法被平均分配（也就是说，无法被 $N-1$ 整除），那么被 $N-1$ 除的余数部分将会以 $1$ 为单位，顺次分配给排名靠前的曲子（也就是说，顺序为曲目 $1$ 、曲目 $2 \cdots $ 依次下去。当然，刚播放过的那首曲子需要被跳过），直到多出的部分被分配完。

在选定的下一首曲子播放完毕后，这个算法再次被执行，调整曲子的权值，并选出再接下来播放的曲目。

请你计算一下，按 FJ 的算法，最先播放的 $T\ (1 \le T \le 1000)$ 首曲子分别是哪些。

inputFormat:
第 $1$ 行有两个用空格隔开的整数：$N$ 和 $T$。

第 $2$ 至第 $N+1$ 行，第 $i+1$ 行为 $1$ 个整数 $R_i$。

outputFormat: 输出共 $T$ 行，第 $i$ 行输出一个整数，表示 iCow 播放的第 $i$ 首曲子。


title: [COCI2008-2009 #2] PERKET

description:
Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 $n$ 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 $s$ 和苦度 $b$。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。

众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。

另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。

inputFormat:
第一行一个整数 $n$，表示可供选用的食材种类数。

接下来 $n$ 行，每行 $2$ 个整数 $s_i$ 和 $b_i$，表示第 $i$ 种食材的酸度和苦度。

outputFormat: 一行一个整数，表示可能的总酸度和总苦度的最小绝对差。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，有 $1 \leq n \leq 10$，且将所有可用食材全部使用产生的总酸度和总苦度小于 $1 \times 10^9$，酸度和苦度不同时为 $1$ 和 $0$。
#### 说明
- 本题满分 $70$ 分。
- 题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) PERKET，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。


title: 电话号码

description:
一串由长长的数字组成的电话号码通常很难记忆。为了方便记忆，有种方法是用单词来方便记忆。例如用 `Three Tens` 来记忆电话 `3-10-10-10`。

电话号码的标准形式是七位数字，中间用连字号分成前三个和后四个数字（例如：`888-1200`）。电话号码可以用字母来表示。以下是字母与数字的对应：

 - `A`，`B` 和 `C` 对应 `2`；
 - `D`，`E` 和 `F` 对应 `3`；
 - `G`，`H` 和 `I` 对应 `4`；
 - `J`，`K` 和 `L` 对应 `5`；
 - `M`，`N` 和 `O` 对应 `6`；
 - `P`，`R` 和 `S` 对应 `7`；
 - `T`，`U` 和 `V` 对应 `8`；
 - `W`，`X` 和 `Y` 对应 `9`。

你会发现其中没有字母 `Q` 和 `Z`。电话中的连字号是可以忽略。例如 `TUT-GLOP` 的标准形式是 `888-4567`，`310-GINO` 的标准形式是 `310-4466`，`3-10-10-10` 的标准形式是 `310-1010`。

如果两个电话号码的标准形式是一样的，那么这两个电话号码就是一样的。

现在有一本电话簿，请从中找出哪些电话号码是重复的。

inputFormat:
第一行一个正整数 $N$，表示有多少个电话号码。

以下 $N$ 行，每行一个电话号码，电话号码由数字、大写字母（除 `Q`、`Z`）和连字符组成。电话号码长度不会超过 $1000$。所有电话号码都合法。

outputFormat:
将所有重复的电话号码按字典序以标准形式输出，并且在每个电话号码后跟一个整数，表示该电话号码共出现了多少次，电话号码和整数间用一个空格隔开。不要输出多余空行。

如果没有重复的电话号码，则输出：`No duplicates.`（注意最后一个字母 `s` 有一个点。）


title: [NOIP2014 提高组] 无线网络发射器选址

background: NOIP2014 提高组 D2T1

description:
随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。

假设该城市的布局为由严格平行的 $129$ 条东西向街道和 $129$ 条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值 $1$。东西向街道从北到南依次编号为 $0,1,2 \dots 128$，南北向街道从西到东依次编号为 $0,1,2 \dots 128$。

东西向街道和南北向街道相交形成路口，规定编号为 $x$ 的南北向街道和编号为 $y$ 的东西向街道形成的路口的坐标是 $(x, y)$。在某些路口存在一定数量的公共场所。

由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心，边长为 $2d$ 的正方形。传播范围包括正方形边界。

现在政府有关部门准备安装一个传播参数为 $d$ 的无线网络发射器，希望你帮助他们在城市内找出合适的路口作为安装地点，使得覆盖的公共场所最多。

inputFormat:
第一行包含一个整数 $d$，表示无线网络发射器的传播距离。

第二行包含一个整数 $n$，表示有公共场所的路口数目。

接下来 $n$ 行，每行给出三个整数 $x, y, k$，中间用一个空格隔开，分别代表路口的坐标 $(x, y)$ 以及该路口公共场所的数量。同一坐标只会给出一次。

outputFormat: 输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。


title: [AHOI2009] 跳棋

description:
在一个 $1$ 行 $N$ 列（$N$ 是奇数）的棋盘上，有 $K$ 个格子是红色的。这种情况下，你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子，在开始移动之间，你可以在棋盘的任意空位上放棋子。在游戏开始后 你只可以随时在一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子被吃掉，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。

请回答以下两个问题：

1. 移动开始前至少要放多少棋子才能完成任务。
2. 如果要使开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务。

关于规则的补充说明：

1. 只能往空位上放棋子，不管是移动开始前还是移动过程中。
2. 移动前棋盘最左端的那个原始棋子绝对不能被吃掉。

inputFormat:
第一行一个正奇数 $N$。

第二行有 $N$ 个整数，如果第 $i$ 个整数是 $1$，说明第 $i$ 个格子是红棋，否则为白棋。

数字间用空格分开。

outputFormat: 两行，每行一个整数分别代表第一问和第二问的结果。

hint:
在游戏开始前，可以在第二个格子上放上一个棋子，游戏开始后可用最左边的棋子吃掉它，从而移动到第三格。然后由于第四格是个红色的格子，在游戏中可以在那放一个棋子，然后用已经移动第三格的棋子把它吃掉，从而达到终点。

$100\%$ 的数据中，$1\le N\le  1000$，输出中的数字不超过 $10^ {15}$。

$30\%$ 的数据中，$N\le 20$。

Source: [Ahoi2009] checker


title: 打开所有的灯

background: pmshz在玩一个益(ruo)智(zhi)的小游戏，目的是打开九盏灯所有的灯，这样的游戏难倒了pmshz。。。

description:
这个灯很奇(fan)怪(ren)，点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务就是就是告诉pmshz要全部打开这些灯。

例如
```
0  1  1
1  0  0
1  0  1
```

点一下最中间的灯【2,2】就变成了
```
0  0  1
0  1  1
1  1  1
```

再点一下左上角的灯【1,1】就变成了

```
1  1  1
1  1  1
1  1  1
```

达成目标。最少需要2步。

输出2即可。

inputFormat: 九个数字，3\*3的格式输入，每两个数字中间只有一个空格，表示灯初始的开关状态。（0表示关，1表示开）

outputFormat: 1个整数，表示最少打开所有灯所需要的步数。

hint: 这个题水不水，就看你怎么考虑了。。。。


title: 分裂游戏

description:
有一个无限大的棋盘，棋盘左下角有一个大小为 $n$ 的阶梯形区域，其中最左下角的那个格子里有一枚棋子。你每次可以把一枚棋子“分裂”成两枚棋子，分别放在原位置的上边一格和右边一格。（但如果目标位置已有棋子，则不能这样做）你的目的是通过有限次的操作，让整个阶梯里不再有任何棋子。下图所示的是 $n = 2$ 时的一种解法。

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

我们用从下往上数的方式标记行，从左往右数的方式标记列，以 (行,列) 来标记棋子，并且都从 $1$ 开始。

例如，第三步中的三个棋子坐标分别为 $(3,1),(2,2),(1,2)$。

现在已知 $n$，你需要做的是给出合适的操作序列。

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

outputFormat:
如果有解，第一行应包含一个正整数 $m$，表示总共需要的操作步数。

以下 $m$ 行，每行包括两个正整数 $x_i,y_i$，表示第 $i$ 步操作分裂的是处于第 $x_i$ 行第 $y_i$ 列的棋子。

如果无解，只需在第一行输出 $-1$。


title: [NOI2005] 维护数列

description:
请写一个程序，要求维护一个数列，支持以下 $6$ 种操作：

| 编号 | 名称 | 格式 | 说明 |
| :-----------: | :-----------: | :-----------: | :----------- |
| 1 | 插入 | $\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}$ | 在当前数列的第 $posi$ 个数字后插入 $tot$ 个数字：$c_1, c_2 \cdots c_{tot}$；若在数列首插入，则 $posi$ 为 $0$ |
| 2 | 删除 | $\operatorname{DELETE} \ posi \ tot$ | 从当前数列的第 $posi$ 个数字开始连续删除 $tot$ 个数字 |
| 3 | 修改 | $\operatorname{MAKE-SAME} \ posi \ tot \ c$ | 从当前数列的第 $posi$ 个数字开始的连续 $tot$ 个数字统一修改为 $c$ |
| 4 | 翻转 | $\operatorname{REVERSE} \ posi \ tot$ | 取出从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字，翻转后放入原来的位置 |
| 5 | 求和 | $\operatorname{GET-SUM} \ posi \ tot$ | 计算从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字的和并输出 |
| 6 | 求最大子列和 | $\operatorname{MAX-SUM}$ | 求出当前数列中和最大的一段子列，并输出最大和 |

inputFormat:
第一行包含两个整数 $N$ 和 $M$，$N$ 表示初始时数列中数的个数，$M$ 表示要进行的操作数目。

第二行包含 $N$ 个数字，描述初始时的数列。以下 $M$ 行，每行一条命令，格式参见问题描述中的表格。

outputFormat: 对于输入数据中的 $\operatorname{GET-SUM}$ 和 $\operatorname{MAX-SUM}$ 操作，向输出文件依次打印结果，每个答案（数字）占一行。

samples:
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

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

- 你可以认为在任何时刻，数列中至少有 $1$ 个数。
- 输入数据一定是正确的，即指定位置的数在数列中一定存在。
- 对于 $50\%$ 的数据，任何时刻数列中最多含有 $3 \times 10^4$ 个数。
- 对于 $100\%$ 的数据，任何时刻数列中最多含有 $5 \times 10^5$ 个数，任何时刻数列中任何一个数字均在 $[-10^3, 10^3]$ 内，$1 \le M \le 2 \times 10^4$，插入的数字总数不超过 $4 \times 10^6$。

题面由 @syksykCCC 提供。


title: 质因子分解

description: 对 $N!$ 进行质因子分解。

inputFormat: 输入数据仅有一行包含一个正整数 $N$，$N \leq 10000$。

outputFormat: 输出数据包含若干行，每行两个正整数 $p,a$，中间用一个空格隔开。表示 $N!$ 包含 $a$ 个质因子 $p$，要求按 $p$ 的值从小到大输出。


title: [NOI2012] 随机数生成器

description:
栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 $m,a,c,X_0$，按照下面的公式生成出一系列随机数 $\{X_n\}$：
$$X_{n+1}=(aX_n +c)\bmod m$$

其中 $\bmod m$ 表示前面的数除以 $m$ 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。

用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的 C++ 和 Pascal 的产生随机数的库函数使用的也是这种方法。

栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 $X_n$ 是多少。由于栋栋需要的随机数是 $0,1,\dots,g-1$ 之间的，他需要将 $X_n$ 除以 $g$ 取余得到他想要的数，即 $X_n \bmod g$，你只需要告诉栋栋他想要的数 $X_n \bmod g$ 是多少就可以了。

inputFormat: 一行 $6$ 个用空格分割的整数 $m,a,c,X_0,n$ 和 $g$，其中 $a,c,X_0$ 是非负整数，$m,n,g$ 是正整数。

outputFormat: 输出一个数，即 $X_n \bmod g$。


title: 方格取数加强版

description: 给出一个 $n\times n$ 的矩阵,每一格有一个非负整数 $A_{i,j}$（$A_{i,j} \le 10^3$），现在从 $(1,1)$ 出发，可以往右或者往下走，最后到达 $(n,n)$，每达到一格，把该格子的数取出来，该格子的数就变成 $0$，这样一共走 $K$ 次，现在要求 $K$ 次所达到的方格的数的和最大。

inputFormat:
第一行两个数 $n,K$（$1 \le n \le 50$，$0 \le K \le 10$）。

接下来 $n$ 行，每行 $n$ 个数，分别表示矩阵的每个格子的数。

outputFormat: 一个数，为最大和。

hint: 每个格子中的数不超过 $1000$。


title: [NOI2010] 海拔

description:
YT 市是一个规划良好的城市，城市被东西向和南北向的主干道划分为 $n \times n$ 个区域。简单起见，可以将 YT 市看作 一个正方形，每一个区域也可看作一个正方形。从而，YT 城市中包括 $(n+1) \times (n+1)$ 个交叉路口和 $2n \times (n+1)$ 条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张 YT 市的地图（$n = 2$），城市被划分为 $2 \times 2$ 个区域，包括 $3 \times 3$ 个交叉路口和 $12$ 条双向道路。

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

小 Z 作为该市的市长，他根据统计信息得到了每天上班高峰期间 YT 市每条道路两个方向的人流量，即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值，YT 市市民认为爬坡是一件非常累的事情，每向上爬 $h$ 的高度，就需要消耗 $h$ 的体力。如果是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为 $h$（注意 $h$ 可能是负数），那么一个人经过这段路所消耗的体力是 $\max\{0, h\}$。

小 Z 还测量得到这个城市西北角的交叉路口海拔为 $0$，东南角的交叉路口海拔为 $1$（如上图所示），但其它交叉路口的海拔高度都无法得知。小 Z 想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡消耗的总体力和的最小值。

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

接下来 $4n(n + 1)$ 行，每行包含一个非负整数分别表示每一条道路每一个方向的人流量信息。

输入顺序：$n(n + 1)$个数表示所有从西到东方向的人流量，然后 $n(n + 1)$ 个数表示所有从北到南方向的人流量，$n(n + 1)$ 个数表示所有从东到西方向的人流量，最后是 $n(n + 1)$ 个数表示所有从南到北方向的人流量。对于每一个方向，输入顺序按照起点由北向南，若南北方向相同时由西到东的顺序给出（参见样例输入）。

outputFormat: 仅包含一个数，表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的总体力和（即总体力和的最小值），结果四舍五入到整数。

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

### 数据范围

- 对于 $20\%$ 的数据：$n \leq 3$；
- 对于 $50\%$ 的数据：$n \leq 15$；
- 对于 $80\%$ 的数据：$n \leq 40$；
- 对于 $100\%$ 的数据：$1 \leq n \leq 500$，$0 \leq \text{流量} \leq 10^6$ 且所有流量均为整数。


title: [NOI2007] 社交网络

description:
在社交网络 ( Social Network ) 的研究中，我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题:
在一个社交圈子里有 $n$ 个人，人与人之间有不同程度的关系。我们将这个关系网络对应到一个 $n$ 个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值 $c$ ，$c$ 越小，表示两个人之间的关系越密切。我们可以用对应结点之间的最短路长度来衡量两个人 $s$ 和 $t$ 之间的关系密切程度，注意到最短路径上的其他结点为 $s$ 和 $t$ 的联系提供了某种便利，即这些结点对于 $s$ 和 $t$ 之间的联系有一定的重要程度。我们可以通过统计经过一个结点 $v$ 的最短路径的数目来衡量该结点在社交网络中的重要程度。考虑到两个结点 $A$ 和 $B$ 之间可能会有多条最短路径。我们修改重要程度的定义如下：令 $C_{s,t}$ 表示从s到t的不同的最短路的数目，$C_{s,t}(v)$ 表示经过 $v$ 从 $s$ 到 $t$ 的最短路的数目；则定义：

$$ I(v)=\sum_{s \ne v,t\ne v} \frac{C_{s,t}(v)}{C_{s,t}}$$

为结点 $v$ 在社交网络中的重要程度。为了使 $I(v)$ 和 $C_{s,t}(v)$ 有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。现在给出这样一幅描述社交网络的加权无向图，请你求出每一个结点的重要程度。

inputFormat:
输入第一行有两个整数 $n$ 和 $m$ ，表示社交网络中结点和无向边的数目。
在无向图中，我们将所有结点从 $1$ 到 $n$ 进行编号。

接下来 $m$ 行，每行用三个整数 $a , b , c$ 描述一条连接结点 $a$ 和 $b$ ，权值为 $c$ 的无向边。
注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

outputFormat: 输出包括 $n$ 行，每行一个实数，精确到小数点后 $3$ 位。第 $i$ 行的实数表示结点 $i$ 在社交网络中的重要程度。

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

对于1号结点而言，只有2号到4号结点和4号到2号结点的最短路经过1号结点，而2号结点和4号结点之间的最短路又有2条。因而根据定义，1号结点的重要程度计算为1/2+1/2=1。由于图的对称性，其他三个结点的重要程度也都是1。

对于 $50\%$ 的数据， $n \le 10 , m \le 45$。
对于 $100\%$ 的数据， $n \le 100 , m \le 4500$ ，任意一条边的权值 $c$ 是正整数且 $1 \leqslant c \leqslant 1000$ 。
所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过 $10^{10}$。


title: [NOI2010] 超级钢琴

description:
小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出 $n$ 个音符，编号为 $1$ 至 $n$。第 $i$ 个音符的美妙度为 $A_i$，其中 $A_i$ 可正可负。

一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 $L$ 且不多于 $R$。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。

小 Z 决定创作一首由 $k$ 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 $k$ 个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小 Z 想知道他能够创作出来的乐曲美妙度最大值是多少。

inputFormat:
输入第一行包含四个正整数 $n, k, L, R$。其中 $n$ 为音符的个数，$k$ 为乐曲所包含的超级和弦个数，$L$ 和 $R$ 分别是超级和弦所包含音符个数的下限和上限。

接下来 $n$ 行，每行包含一个整数 $A_i$，表示按编号从小到大每个音符的美妙度。

outputFormat: 输出只有一个整数，表示乐曲美妙度的最大值。

hint:
### 样例解释

共有 $5$ 种不同的超级和弦：

1. 音符 $1 \sim 2$，美妙度为 $3+2=5$；
2. 音符 $2 \sim 3$，美妙度为 $2+(-6)=-4$；
3. 音符 $3 \sim 4$，美妙度为 $(-6)+8=2$；
4. 音符 $1 \sim 3$，美妙度为 $3+2+(-6)=-1$；
5. 音符 $2 \sim 4$，美妙度为 $2+(-6)+8=4$。

最优方案为：乐曲由和弦 $1,3,5$ 组成，美妙度为 $5+2+4=11$。

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

所有数据满足：$-1000 \leq A_i \leq 1000$，$1 \leq L \leq R \leq n$ 且保证一定存在满足要求的乐曲。


title: 魔术棋子

description:
在一个 $M \times N$ 的魔术棋盘中，每个格子中均有一个整数，当棋子走进这个格子中，则此棋子上的数会被乘以此格子中的数。一个棋子从左上角走到右下角，只能向右或向下行动，请问此棋子走到右下角后，模（mod）$K$ 可以为几？

如以下 $2 \times 3$ 棋盘：

```
3    4    4
5    6    6
```
棋子初始数为 $1$，开始从左上角进入棋盘，走到右下角，上图中，最后棋子上的数可能为 $288,432$ 或 $540$。所以当 $K = 5$ 时，可求得最后的结果为：$0,2,3$。

inputFormat: 第一行为三个数，分别为 $M,N,K (1 \leq M,N,K \leq 100)$。以下 $M$ 行，每行 $N$ 个数，分别为此方阵中的数。

outputFormat:
第一行为可能的结果个数。

第二行为所有可能的结果（按升序输出）。


title: [NOI2012] 美食节

description:
CZ 市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。

作为一个喜欢尝鲜的美食客，小 M 自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小 M 仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小 M 开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。

小 M 发现，美食节共有 $n$ 种不同的菜品。每次点餐，每个同学可以选择其中的**一个菜品**。总共有 $m$ 个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。**厨师们会按照要求的顺序进行制作，并且每次只能制作一人份**。

此外，小 M 还发现了另一件有意思的事情——虽然这 $m$ 个厨师都会制作全部的 $n$ 种菜品，但**对于同一菜品，不同厨师的制作时间未必相同**。他将菜品用 $1, 2, \ldots, n$ 依次编号，厨师用 $1, 2, \ldots, m$ 依次编号，将第 $j$ 个厨师制作第 $i$ 种菜品的时间记为 $t_{i,j}$。

小 M 认为：每个同学的等待时间为**所有厨师开始做菜起，到自己那份菜品完成为止**的时间总长度。换句话说，如果一个同学点的菜是某个厨师做的第 $k$ 道菜，则他的等待时间就是这个厨师制作前 $k$ 道菜的时间之和。而**总等待时间**为**所有同学的等待时间之和**。

现在，小 M 找到了所有同学的点菜信息——有 $p_i$ 个同学点了第 $i$ 种菜品（$i=1, 2, \ldots, n$）。他想知道的是最小的总等待时间是多少。

inputFormat:
输入文件的第 $1$ 行包含两个正整数 $n$ 和 $m$，表示菜品的种数和厨师的数量。

第 $2$ 行包含 $n$ 个正整数，其中第 $i$ 个数为 $p_i$，表示点第 $i$ 种菜品的人数。

接下来有 $n$ 行，每行包含 $m$ 个非负整数，这 $n$ 行中的第 $i$ 行的第 $j$ 个数为 $t_{i,j}$，表示第 $j$ 个厨师制作第 $i$ 种菜品所需的时间。

输入文件中每行相邻的两个数之间均由一个空格隔开，行末均没有多余空格。

outputFormat: 输出仅一行包含一个整数，为总等待时间的最小值。


title: [AHOI2009] 中国象棋

description: 这次小可可想解决的难题和中国象棋有关，在一个 $n$ 行 $m$ 列的棋盘上，让你放若干个炮（可以是 $0$ 个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

inputFormat: 一行包含两个整数 $n,m$，之间由一个空格隔开。

outputFormat: 总共的方案数，由于该值可能很大，只需给出方案数模 $9999973$ 的结果。

hint:
**样例说明**

除了 $3$ 个格子里都塞满了炮以外，其它方案都是可行的，所以一共有 $2 \times 2 \times 2-1=7$ 种方案。

**数据规模与约定**

- 对于 $30\%$ 的数据，$n$ 和 $m$ 均不超过 $6$。
- 对于 $50\%$ 的数据，$n$ 和 $m$ 至少有一个数不超过 $8$。
- 对于 $100\%$ 的数据，$1 \leq n,m \leq 100$。

题面修改：@syksykCCC。


title: [NOI2011] 道路修建

description:
在 W 星球上有 $n$ 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 $n - 1$ 条双向道路。

每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 $2$ 个、$4$ 个国家，如果该道路长度为 $1$，则费用为 $1×|2 - 4|=2$。图中圆圈里的数字表示国家的编号。

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

由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计算出所需要的费用。请你帮助国王们设计一个这样的软件。

inputFormat:
输入的第一行包含一个整数 $n$，表示 W 星球上的国家的数量，国家从 $1$ 到 $n$ 编号。

接下来 $n–1$ 行描述道路建设情况，其中第 $i$ 行包含三个整数 $a_i,b_i$ 和 $c_i$，表示第 $i$ 条双向道路修建在 $a_i$ 与 $b_i$ 两个国家之间，长度为 $c_i$。

outputFormat: 输出一个整数，表示修建所有道路所需要的总费用。


title: [SCOI2007] 修车

description:
同一时刻有 $N$ 位车主带着他们的爱车来到了汽车维修中心。

维修中心共有 $M$ 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。

现在需要安排这 $M$ 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。

说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

inputFormat:
第一行有两个数 $M,N$，表示技术人员数与顾客数。

接下来 $N$ 行，每行 $M$ 个整数。第 $i+1$ 行第 $j$ 个数表示第 $j$ 位技术人员维修第 $i$ 辆车需要用的时间 $T_{i,j}$。

outputFormat: 最小平均等待时间，答案精确到小数点后 $2$ 位。


title: [AHOI2005] 洗牌

description:
为了表彰小联为 Samuel 星球的探险所做出的贡献，小联被邀请参加 Samuel 星球近距离载人探险活动。

由于 Samuel 星球相当遥远，科学家们要在飞船中度过相当长的一段时间，小联提议用扑克牌打发长途旅行中的无聊时间。玩了几局之后，大家觉得单纯玩扑克牌对于像他们这样的高智商人才来说太简单了。有人提出了扑克牌的一种新的玩法。

对于扑克牌的一次洗牌是这样定义的，将一叠 $N$（$N$为偶数）张扑克牌平均分成上下两叠，取下面一叠的第一张作为新的一叠的第一张，然后取上面一叠的第一张作为新的一叠的第二张，再取下面一叠的第二张作为新的一叠的第三张……如此交替直到所有的牌取完。

如果对一叠 $6$ 张的扑克牌 ${1,2,3,4,5,6}$，进行一次洗牌的过程如下图所示：

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

从图中可以看出经过一次洗牌，序列 $1,2,3,4,5,6$ 变为 $4,1,5,2,6,3$。当然，再对得到的序列进行一次洗牌，又会变为 $2,4,6,1,3,5$。

游戏是这样的，如果给定长度为 $N$ 的一叠扑克牌，并且牌面大小从 $1$ 开始连续增加到 $N$（不考虑花色），对这样的一叠扑克牌，进行 $M$ 次洗牌。最先说出经过洗牌后的扑克牌序列中第 $L$ 张扑克牌的牌面大小是多少的科学家得胜。小联想赢取游戏的胜利，你能帮助他吗？

inputFormat:
输入文件中有三个用空格间隔的整数，分别表示 $N,M,L$。

（其中 $1\le N\le 10^{10},0 \le M\le 10^{10}$，且 $N$ 为偶数）。

outputFormat: 单行输出指定的扑克牌的牌面大小。


title: [ZJOI2009] 假期的宿舍

description:
学校放假了……有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。

比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床。而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。

我们已知一共有 $n$ 个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

inputFormat:
第一行一个数 $T$ 表示数据组数。接下来 $T$ 组数据，每组数据第一行一个数 $n$ 表示涉及到的总人数。

接下来一行 $n$ 个数，第 $i$ 个数表示第 $i$ 个人是否是在校学生 ($0$ 表示不是，$1$ 表示是)。再接下来一行 $n$ 个数，第 $i$ 个数表示第 $i$ 个人是否回家 ($0$ 表示不回家，$1$ 表示回家，注意如果第 $i$ 个人不是在校学生，那么这个位置上的数是一个随机的数，你应该在读入以后忽略它)。

接下来 $n$ 行每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $i$ 和 $j$ 是否认识 ($1$ 表示认识，$0$ 表示不认识，第 $i$ 行 $i$ 个的值为 $0$，但是显然自己还是可以睡自己的床)，认识的关系是相互的。

outputFormat: 对于每组数据，如果存在一个方案则输出 `^_^`，否则输出`T_T`。（注意输出的都是半角字符，即三个符号的 ASCII 码分别为 $94,84,95$）


title: [ZJOI2007] 捉迷藏

description:
Jiajia 和 Wind 是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind 和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 $N$ 个屋子和 $N-1$ 条双向走廊组成，这 $N-1$ 条走廊的分布使得任意两个屋子都互相可达。

游戏是这样进行的，孩子们负责躲藏，Jiajia 负责找，而 Wind 负责操纵这 $N$ 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia 希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。

我们将以如下形式定义每一种操作：

- C(hange) i 改变第 $i$ 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
- G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。

inputFormat:
第一行包含一个整数 $N$，表示房间的个数，房间将被编号为 $1,2,3…N$ 的整数。

接下来 $N-1$ 行每行两个整数 $a$, $b$，表示房间 $a$ 与房间 $b$ 之间有一条走廊相连。

接下来一行包含一个整数 $Q$，表示操作次数。接着 $Q$ 行，每行一个操作，如上文所示。

outputFormat: 对于每一个操作 Game，输出一个非负整数，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出 `0`；若所有房间的灯都开着，输出 `-1`。


title: [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

description:
幼儿园里有 $n$ 个小朋友打算通过投票来决定睡不睡午觉。

对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。

虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。

我们定义一次投票的冲突数为下面两者相加：

* 实际投票不同的好朋友对数。

* 自己实际投票和自己本来意愿不同的人数。

我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？

inputFormat:
第一行两个整数 $n,m$。其中 $n$ 代表总人数，$m$ 代表好朋友的对数。

第二行 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个小朋友的意愿：当它为 $1$ 时表示同意睡觉，当它为 $0$ 时表示反对睡觉。

接下来 $m$ 行，每行有两个整数 $i,j$，表示 $i,j$ 是一对好朋友，我们保证任何两对 $i,j$ 不会重复。

outputFormat: 一行一个整数，即可能的最小冲突数。


title: [NOIP2016 普及组] 海港

background: NOIP2016 普及组 T3

description:
小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 $i$ 艘到达的船，他记录了这艘船到达的时间 $t_i$ (单位：秒)，船上的乘客数 $k_i$，以及每名乘客的国籍 $x_{i,1}, x_{i,2},\dots,x_{i,k}$。

小K统计了 $n$ 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 $24$ 小时（$24$ 小时 $=86400$ 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 $n$ 条信息。对于输出的第 $i$ 条信息，你需要统计满足 $t_i-86400<t_p \le t_i$ 的船只 $p$，在所有的 $x_{p,j}$ 中，总共有多少个不同的数。

inputFormat:
第一行输入一个正整数 $n$，表示小 K 统计了 $n$ 艘船的信息。

接下来 $n$ 行，每行描述一艘船的信息：前两个整数 $t_i$ 和 $k_i$ 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 $k_i$ 个整数 $x_{i,j}$ 表示船上乘客的国籍。

保证输入的 $t_i$ 是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 $t_i$ 秒到达海港。

保证 $1 \le n \le 10^5$，$\sum{k_i} \le 3\times 10^5 $ ，$1\le x_{i,j} \le 10^5$， $1 \le t_{i-1}\le  t_i    \le  10^9$。

其中 $\sum{k_i}$ 表示所有的 $k_i$ 的和。

outputFormat: 输出 $n$ 行，第 $i$ 行输出一个整数表示第 $i$ 艘船到达后的统计信息。

hint:
【样例解释 1】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $4,1,2,2$，共来自 $3$ 个不同的国家；

第二艘船在第 $2$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4 + 2 = 6$ 个乘客，分别是来自国家 $4,1,2,2,2,3$，共来自 $4$ 个不同的国家；

第三艘船在第 $10$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船、第二艘船和第三艘船，共有 $4+2+1=7$ 个乘客，分别是来自国家 $4,1,2,2,2,3,3$，共来自 $4$ 个不同的国家。

【样例解释 2】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $1,2,2,3$，共来自 $3$ 个不同的国家。

第二艘船在第 $3$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4+2=6$ 个乘客，分别是来自国家 $1,2,2,3,2,3$，共来自 $3$ 个不同的国家。

第三艘船在第 $86401$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船和第三艘船，共有 $2+2=4$ 个乘客，分别是来自国家 $2,3,3,4$，共来自 $3$ 个不同的国家。

第四艘船在第 $86402$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船、第三艘船和第四艘船，共有 $2+2+1=5$ 个乘客，分别是来自国家 $2,3,3,4,5$，共来自 $4$个 不同的国家。

【数据范围】

- 对于 $10\%$ 的测试点，$n=1,\sum k_i \leq 10,1 \leq x_{i,j} \leq 10, 1 \leq t_i \leq 10$。
- 对于 $20\%$ 的测试点，$1 \leq n \leq 10, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 32767$。
- 对于 $40\%$ 的测试点，$1 \leq n \leq 100, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 86400$。
- 对于 $70\%$ 的测试点，$1 \leq n \leq 1000, \sum k_i \leq 3000,1 \leq x_{i,j} \leq 1000,1 \leq t_i \leq 10^9$。
- 对于 $100\%$ 的测试点，$1 \leq n \leq 10^5,\sum k_i \leq 3\times 10^5, 1 \leq x_{i,j} \leq 10^5,1\leq t_i \leq 10^9$。


title: [JLOI2013] 卡牌游戏

description:
$N$ 个人坐成一圈玩游戏。一开始我们把所有玩家按顺时针从 $1$ 到 $N$ 编号。首先第一回合是玩家 $1$ 作为庄家。每个回合庄家都会随机（即按相等的概率）从卡牌堆里选择一张卡片，假设卡片上的数字为 $X$，则庄家首先把卡片上的数字向所有玩家展示，然后按顺时针从庄家位置数第 $X$ 个人将被处决(即退出游戏)。然后卡片将会被放回卡牌堆里并重新洗牌。被处决的人按顺时针的下一个人将会作为下一轮的庄家。那么经过 $N-1$ 轮后最后只会剩下一个人，即为本次游戏的胜者。现在你预先知道了总共有 $M$ 张卡片，也知道每张卡片上的数字。现在你需要确定每个玩家胜出的概率。

这里有一个简单的例子：

例如一共有 $4$ 个玩家，有四张卡片分别写着`3,4,5,6`.

第一回合，庄家是玩家 $1$ ，假设他选择了一张写着数字 $5$ 的卡片。那么按顺时针数 `1,2,3,4,1`，最后玩家 $1$ 被踢出游戏。

第二回合，庄家就是玩家 $1$ 的下一个人，即玩家 $2$.假设玩家 $2$ 这次选择了一张数字 $6$，那么 `2,3,4,2,3,4`，玩家 $4$ 被踢出游戏。

第三回合，玩家 $2$ 再一次成为庄家。如果这一次玩家 $2$ 再次选了 $6$，则玩家 $3$ 被踢出游戏，最后的胜者就是玩家 $2$。

inputFormat:
第一行包括两个整数 $N,M$ 分别表示玩家个数和卡牌总数。

接下来一行包含 $M$ 个整数，分别给出每张卡片上写的数字。

outputFormat: 输出一行包含 $N$ 个百分比形式给出的实数，四舍五入到两位小数。分别给出从玩家 $1$ 到玩家 $N$ 的胜出概率，每个概率之间用空格隔开，最后不要有空格。


title: [HNOI2006] 马步距离

description:
在国际象棋和中国象棋中，马的移动规则相同，都是走“日”字，我们将这种移动方式称为马步移动。

如下图所示，从标号为 $0$ 的点出发，可以经过一步马步移动达到标号为 $1$ 的点，经过两步马步移动达到标号为 $2$ 的点。

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

任给平面上的两点 $p$ 和 $s$，它们的坐标分别为 $(x_p,y_p)$ 和 $(x_s,y_s)$，从 $(x,y)$ 出发经过一步马步移动可以达到 $(x+1,y+2)$，$(x+2,y+1)$，$(x+1,y-2)$，$(x+2,y-1)$，$(x-1,y+2)$，$(x-2,y+1)$，$(x-1,y-2)$、$(x-2,y-1)$。

假设棋盘充分大，并且坐标可以为负数。现在请你求出从点 $p$ 到点 $s$ 至少需要经过多少次马步移动？

inputFormat: 输入只有一行四个用空格隔开的整数，分别代表 $x_p,y_p,x_s,y_s$。

outputFormat: 含一个整数，表示从点 $p$ 到点 $s$ 至少需要经过的马步移动次数。

hint:
#### 数据规模与约定
对于 $100\%$ 的数据，保证 $1 \leq x_p,y_p,x_s,y_s \leq 10^7$。


title: [USACO07OPEN] City Horizon S

description:
Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.

The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,000) buildings. Building i's silhouette has a base that spans locations Ai through Bi along the horizon (1 ≤ Ai < Bi ≤ 1,000,000,000) and has height Hi (1 ≤ Hi ≤ 1,000,000,000). Determine the area, in square units, of the aggregate silhouette formed by all N buildings.

有一个数列，初始值均为0，他进行N次操作，每次将数列[ai,bi)这个区间中所有比Hi小的数改为Hi，他想知道N次操作后数列中所有元素的和。

inputFormat: 第一行一个整数N，然后有N行，每行三个正整数ai、bi、Hi。

outputFormat: 一个数，数列中所有元素的和。

translation:
约翰带着奶牛去都市观光。在落日的余晖里，他们看到了一幢接一幢的摩天高楼的轮廓在地平线 上形成美丽的图案。以地平线为 X 轴，每幢高楼的轮廓是一个位于地平线上的矩形，彼此间可能有 重叠的部分。奶牛一共看到了 N 幢高楼，第 i 幢楼的高度是 Hi，两条边界轮廓在地平线上的坐标是 Ai 到 Bi。请帮助奶牛们计算一下，所有摩天高楼的轮廓覆盖的总面积是多少。

感谢@klzz 提供的翻译


title: 分队问题

description:
给定 $n$ 个选手，将他们分成若干只队伍。其中第 $i$ 个选手要求自己所属的队伍的人数大等于 $a_i$ 人。

在满足所有选手的要求的前提下，最大化队伍的总数。

注：每个选手属于且仅属于一支队伍。

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

以下 $n$ 行，每行一个整数表示 $a_i$。

outputFormat: 输出队伍总数的最大值。数据保证有解。


title: 奇妙的汽车

description:
你有着一辆奇妙的汽车，这辆汽车有着自动加速的功能。打个比方吧，第1天你驾驶着它可以行驶a路程，那么第2天你可以让它所走的路程增加到第1天的2~9倍（必须是其中一个整数），也就是2a~9a，第3天它所行驶的路程就将达到第2天的2~9倍……也就是说，这辆车在第i天所走的路程一定是第i-1天的2~9倍，而且还必须是它的整数倍。

现在你迫不及待地开着这辆车要从A城市出发到B城市旅游，顺便在路上展示一下这辆旷世奇车。你已经知道你需要行驶的里程S，现在请你合理安排第1天的里程和接下来每天需要增加路程的倍数，好让你能够在最短的天数内，恰好到达B城市。

不过，因为你想要好好展示一下你的车，而且也是为了交通安全，你被要求至少要花2天时间，如果不能找到这样的方案请输出-1。

inputFormat: 一个正整数S，代表A城市到B城市的里程。

outputFormat: 一个数，代表最少需要行驶的天数，如果无解输出-1。

hint:
数据规模

对于30%数据，有 $S\leqslant 100$；

对于70%数据，有 $S\leqslant 10^7$；

对于100%数据，有 $9<S\leqslant 10^8$。


title: [TJOI2011] 卡片

description: 桌子上有 $m$ 张蓝色卡片与 $n$ 张红色卡片，每张卡片上有一个大于 $1$ 的整数。现在你要从桌子上拿走一些卡片，分若干次拿。每次只能拿走一组卡片：这组卡片颜色不同，并且两张卡片上面的数字的最大公约数大于 $1$。问：最多可以从桌上拿走多少组卡片。

inputFormat:
每个输入文件中包含多组测试数据，每个文件中测试数据的数目不超过 $100$。

文件的第一行读入一个整数 $T$，为数据组数。

每组数据的格式如下：

```
m n

b1 b2 … bm

r1 r2 … rn
```

第二行给出每张蓝色卡片上面的数字，第三行给出每张红色卡片上的数字。

outputFormat: 对每组测试数据，输出最多可以拿走多少组卡片。


title: 机器分配

description: 总公司拥有高效设备 $M$ 台，准备分给下属的 $N$ 个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这 $M$ 台设备才能使国家得到的盈利最大？求出最大盈利值。其中 $M \le 15$，$N \le 10$。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 $M$。

inputFormat:
第一行有两个数，第一个数是分公司数 $N$，第二个数是设备台数 $M$。

接下来是一个 $N \times M$ 的矩阵，表明了第 $i$ 个公司分配 $j$ 台机器的盈利。

最大盈利值相同时，要求编号小的公司分得设备尽可能少。

outputFormat:
第一行为最大盈利值。

接下来 $N$ 行为第 $i$ 分公司分 $x$ 台。


title: Cytus-Holyknight

background:
本人最初作

以此纪念伟大的ios、安卓、PSV平台音乐游戏《cytus》

后续将不断更新。

-------------Chapter V-1-------------

话说两位战士整天靠在一起好无聊啊，于是她们打算——玩游戏！（？）

她们就用剑画了一个十字架，然后开始抛石子，好好玩啊（？？？）

两个人每人有一个石子，当她们丢完后，正在自学数学的小蓝大叫：把他们连起来不就是一次函数吗！！

于是乎，她们就连了起来，然后她们开始计算。此时她们发现一个严重的问题——没有草稿纸！（这什么破问题= =）

由于脑补能力太低，她们只好让你来帮帮忙啦~

description: 给出图形（十字架可以视为x轴和y轴），请计算出函数解析式。

inputFormat:
第一行，一个正整数n，表示该图形大小是n\*n；

接下来n行，每行n个字符，1表示坐标轴，x表示石子，0表示空地。

横行的1是x轴，竖列的1是y轴。

上下两行，左右两列的距离恒为1。

outputFormat:
输出一行，即y=kx+b，或y=kx，y=b，x=b；（k,b为常数）

常数始终保留四位小数

hint:
切记要分类

数据不需判错

100%的数据，3<=n<=16（够水吧）

没学过函数的自己百度


title: 统计和

description: 给定一个长度为 $n(n\leq 100000)$，初始值都为 $0$ 的序列，$x(x\leq 100000)$ 次的修改某些位置上的数字，每次加上一个数，然后提出 $y(y\leq 100000)$ 个问题，求每段区间的和。

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

第二行 $1$ 个整数，表示操作的次数 $w$。

后面依次是 $w$ 行，分别表示加入和询问操作。

其中，加入用 `x` 表示，询问用 `y` 表示。

$x$的格式为 `x a b` 表示在序列上第 $a$ 个数加上 $b$。保证 $1 \leq a \leq n$，$1 \leq b \leq 10^9$。

$y$ 的格式为 `y a b` 表示询问 $a$ 到 $b$ 区间的加和。保证 $1 \leq a \leq b \leq n$。

outputFormat: 每行一个正整数，分别是每次询问的结果


title: 松鼠吃果子

description:
有 $n$ 个一种松鼠喜欢吃的果子由下向上串排成一列，并标号 $1\sim n$。一只松鼠从最下果子开始向上跳，并且第 $i$ 次跳可以一次跳过 $(i^3 \bmod 5 + 1)$ 个果子，并把脚下的果子吃了，如果上面有果子，在重力作用下，都将向下掉下一格。如第 $1$ 次跳从第一个果子上跳过 $(1^3 \bmod 5 + 1 = ) 2$ 个果子，可跳到第 $3$ 个果子上，并把第 $3$ 个果子吃了；第 $2$ 次从第 $4$ 个果子上(落在原来第三个果子位置)跳过 $(2^3\bmod 5 + 1 = ) 4$ 个到第 $8$ 个果子上，并把第 $8$ 个吃了；如此反复。

当然，总有一次松鼠会跳出这串果子的最前面，设为每 $k$ 次，它吃不到任何果子了。这时它回到最下面的果子上，重做它的第 $k$ 次跳，以求吃到果子。如此，问它吃的第 $m$ 只果子(即第 $m$ 跳吃到的果子)的标号是什么？

inputFormat: 一共两行，分别为 $n$ 和 $m$（$1\le m\le n\le 200$，并且满足能够跳到第 $m$ 次）。

outputFormat: 一个数，即它吃的第 $m$ 只果子的标号。

hint: 注：吃掉的果子依次为 $3$，$8$，$4$（回到下面重做第 $3$ 跳），$9$（回到下面重做第 $4$ 跳）。


title: 刷墙

description:
Farmer John已经设计了一种方法来装饰谷仓旁边的长栅栏（把栅栏认为是一根一维的线）。他把一只画刷绑在他最喜爱的奶牛Bessie身上，之后就去喝一杯冰水，而Bessie隔着栅栏来回走，当她走过某个地方，这里的一段栅栏就被刷上了涂料。

Bessie从栅栏上的位置0开始，并且遵循着一个N次移动的次序(1 <= N <= 100,000)。例如“10 L”表示Bessie向左移动了10个单位长度，“15 R”表示Bessie向右移动了15个单位长度。现给出Bessie所有移动的列表，Farmer John想要知道哪些区域的栅栏至少涂了两层涂料（只涂一层涂料的区域可能在大雨中被洗掉）。Bessie在她的行走中最远到达距起始点1,000,000,000个单位长度。

inputFormat:
第1行：一个整型数N。

第2..N+1行：每行描述了Bessie的N次移动中的一次，例如“15 L”。

outputFormat: 1行：被至少涂了两层涂料的区域总数。

hint:
【样例解释】

Bessie从位置0开始，向右移动2个单位长度，向左移动6个单位长度，向右移动1个单位长度，向左移动8个单位长度，最后向右移动3个单位长度。

6个单位区域至少被涂了两层涂料，是 [-11,-8], [-4,-3], [0,2]这些区域。


title: 座位安排

background: 公元二零一四年四月十七日，小明参加了省赛，在一路上，他遇到了许多问题，请你帮他解决。

description: 已知车上有 $N$ 排座位，有 $2N$ 个人参加省赛，每排座位只能坐两人，且每个人都有自己想坐的排数，问最多使多少人坐到自己想坐的位置。

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

第二行至第 $2N+1$ 行，每行两个正整数 $S_{i, 1},S_{i, 2}$，为每个人想坐的排数。

outputFormat: 一个非负整数，为最多使得多少人满意。


title: 宗教问题

background: 在一个地区有许多种宗教，不同信仰的教徒经常发生矛盾，最为治安管理的人需要把这些人分开，以免矛盾激化。

description:
已知一个地方有M种宗教(编号为1—M)，有N个教徒(编号为1—N)，每个教徒信且只信一种宗教。现在要按顺序把这N个教徒分成一些集体，每个集体的危险值定义为这个集体中的宗教种数，且一个集体的宗教种类不能超过K种，否则就会无限危险，

问：
1.这N个教徒至少要分为几个集体，

2.这些集体的危险值总和至少为多少。

inputFormat:
第一行三个正整数N  M  K，以空格隔开

第二行N个正整数，为每个教徒信的宗教编号

outputFormat:
第一行 一个正整数，为最少集体数

第二行 一个正整数，为最小危险值。


title: 送花

background: 小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。

description:
这些花都很漂亮，每朵花有一个美丽值 $W$，价格为 $C$。

小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：

- $1\ W\ C$：添加一朵美丽值为 $W$，价格为 $C$ 的花。
**如果此时花束中已经有了相等价格的花，那么这朵花不能加入花束。**
- $2$：删除当前花束里最贵的一朵花。
- $3$：删除当前花束里最便宜的一朵花。
- $-1$：完成添加与删除，开始包装花束。

**当花束为空时，忽略操作 $2$ 和 $3$。**

请你写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。

inputFormat: 若干行，每行一个操作，以 $-1$ 结束。

outputFormat: 一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。


title: 危险区域

background: 一个恐怖组织在一座城市中安放了定时炸弹，其威力巨大，现在这里的警长想知道最坏的情况下会有多少街区受威胁。

description:
在一个城市有 $N \times M$ 个街区，每个街区由坐标描述，如图所示：

|  | $1$ | $2$ | $3$ | $\cdots$ | $M$ |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| $1$ | $(1,1)$ | $(1,2)$ | $(1,3)$ | $\cdots$ | $(1,M)$ |
| $2$ | $(2,1)$ | $(2,2)$ | $(2,3)$ | $\cdots$ | $(2,M)$ |
| $3$ | $(3,1)$ | $(3,2)$ | $(3,3)$ | $\cdots$ | $(3,M)$ |
| $\vdots$ |  |  |  | $\ddots$ |  |
| $N$ | $(N,1)$ | $(N,2)$ | $(N,3)$ | $\cdots$ | $(N,M)$ |

现在已知有一个恐怖组织在其中的一个街区安放了定时炸弹，其威力为 $t$，即所有到这个街区的直线距离小于等于 $t$ 的街区都会受威胁，已知有 $k$ 个可能的炸弹安放位置，现在这里的警长想知道最坏的情况下会有多少街区受威胁。

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

接下来 $k$ 行每行两个正整数 $x_i,y_i$，描述每个可能安放炸弹的街区。

outputFormat: 一个正整数为在最坏情况下有多少街区会受威胁。

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

对于$20\%$的数据 $k=1$。

对于 $50\%$ 的数据 $1 \le n,m \le 1000$，$1 \le k \le 20$，$1\le t \le 100$。

对于 $100\%$ 的数据 $1 \le n,m \le 10^5$，$1 \le k \le 50$，$t \le 300$。

fixed by @[$\color{#5EB95E}{\textsf{Cppsteve}}$](https://www.luogu.com.cn/user/479296)


title: 红绿灯

description: 在一个城市，有一条笔直的公路，在这条公路上有 $N$ 个十字路口，每个路口都设有一个红绿灯，已知相邻的两个路口距离为 $A_i$ 千米 $(1\le i < N)$，每个路口的红灯时间为 $R_i$，绿灯时间为 $G_i$，没有黄灯，现在有一辆车从距离 $1$ 号十字路口 $M$ 千米的位置出发，且此时所有路口的红绿灯刚好从红灯跳到绿灯，问这辆车通过每个路口的时间(不能闯红灯，这辆车的速度为 $1$ 千米每分钟)。

inputFormat:
第一行两个正整数 $N$ 和 $M$

第二行 $N-1$ 个正整数 $A_i$

第三行 $N$ 个正整数 $R_i$，为红灯时间（分钟）

第四行 $N$ 个正整数 $G_i$，为绿灯时间（分钟）

outputFormat: 共 $N$ 行，每行一个正整数，为这辆车通过每个十字路口的最早时间。


title: 朋友

background: 小明在 A 公司工作，小红在 B 公司工作。

description:
这两个公司的员工有一个特点：一个公司的员工都是同性。

A 公司有 $N$ 名员工，其中有 $P$ 对朋友关系。B 公司有 $M$ 名员工，其中有 $Q$ 对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数 $(X_i,Y_i)$ 组成，表示朋友的编号分别为 $X_i,Y_i$。男人的编号是正数，女人的编号是负数。小明的编号是 $1$，小红的编号是 $-1$。

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。

inputFormat:
输入的第一行，包含 $4$ 个空格隔开的正整数 $N,M,P,Q$。

之后 $P$ 行，每行两个正整数 $X_i,Y_i$。

之后 $Q$ 行，每行两个负整数 $X_i,Y_i$。

outputFormat: 输出一行一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。


title: 烛光晚餐

background: 小明准备请小红去一家咖啡厅，共进烛光晚餐。小红高兴地和他一起去了咖啡厅。

description:
小红说：“小明，你点菜吧。”小明看到菜单上有 $N$ 道菜，每道菜的价格是 $C_i$。小明对每道菜的喜爱程度是 $X_i$，小红对每道菜的喜爱程度是 $Y_i$。（喜爱程度可能为负数）（小明：以我对她的了解，我给你的数据不会错的）

小明带了 $V$ 元钱，他点的菜的总价格不能超过 $V$（小明：当然得我请客啦，显得我大方。）

小明希望让小红吃得开心，所以当然要让她的总喜爱程度尽量大。当然，小明也要考虑自己的感受，点的所有菜的总喜爱程度需要大于等于 $0$。（小明：要是我吃得不好，她看见我会难过的）

请你帮小明写一个程序，计算出他的总喜爱程度大于等于 $0$ 的前提下，小红的喜爱程度的最大值。（小明：你的程序一定要靠谱啊，我得给她一个好印象）

inputFormat:
第一行，两个正整数 $N$，$V$。

之后 $N$ 行，每行 $3$ 个空格隔开的正整数 $C_i$，整数 $X_i$，$Y_i$。

outputFormat: 一行，一个正整数，表示他的总喜爱程度大于等于 $0$ 的前提下，小红的喜爱程度的最大值。如果这个最大值小于 $0$，输出 $-1$.


title: 增进感情

background: 小明和小红的感情，是慢慢发展起来的。

description:
他们对对方分别有一个好感值。定义两人的亲密程度为两人的好感值之和。

如果他们的亲密程度达到 $v$，则他们将走到一起。他们以后的生活将取决于两人的好感值之差的绝对值，这个值越小，他们的生活将越幸福。

现在，他们对对方的好感值都为 $0$，小明有 $n$ 件事可以干，每件事可以增加他对小红的好感 $a_i$ 点，并且增加小红对他的好感 $b_i$ 点。（可能为负数）

小明可以任选一些事做，请你帮小明求出怎样才能让他们的生活更加幸福（求出两人在一起的前提下，好感值之差的最小绝对值即可）。

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

之后 $n$ 行，每行两个空格隔开的整数 $a_i,b_i$。

outputFormat: 一行，一个非负整数，表示两人在一起的前提下，好感值之差的最小绝对值。如果无论如何两人也无法在一起，输出 `-1`。

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

- 对于 $20\%$ 数据，保证 $n  \le 10$。
- 对于 $100\%$ 数据，保证 $1 \le n \le 30$，$1 \le \left\vert a_i\right\vert,\left\vert b_i\right\vert \le 100$。


title: [NOI2012] 迷失游乐园

description:
放假了，小 Z 觉得呆在家里特别无聊，于是决定一个人去游乐园玩。

进入游乐园后，小 Z 看了看游乐园的地图，发现可以将游乐园抽象成有 $n$ 个景点、$m$ 条道路的无向连通图，且该图中至多有一个环（即 $m$ 只可能等于 $n$ 或者 $n-1$）。

小 Z 现在所在的大门也正好是一个景点。小 Z 不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小 Z 会一直游玩，直到当前景点的相邻景点都已经访问过为止。

小 Z 所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？

小 Z 把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

inputFormat:
第一行是两个整数 $n$ 和 $m$ ，分别表示景点数和道路数。

接下来 $m$ 行，每行三个整数 $X_i, Y_i, W_i$，分别表示第 $i$ 条路径的两个景点为 $X_i, Y_i$，路径长 $W_i$。所有景点的编号从 $1$ 至 $n$，两个景点之间至多只有一条道路。

outputFormat: 共一行，包含一个实数，即路径的期望长度，保留五位小数。


title: 区间覆盖（加强版）

description: 已知有 $N$ 个区间，每个区间的范围是 $[s_i,t_i]$，请求出区间覆盖后的总长。

inputFormat:
第一行一个正整数 $N$，表示区间个数。

接下来 $N$ 行，每行两个正整数，表示 $s_i$ 和 $t_i$。

outputFormat: 共一行，一个正整数，为覆盖后的区间总长。


title: 找人

description:
小明要到他的同学家玩，可他只知道他住在某一单元，却不知住在哪个房间。那个单元有 $n$ 层（$1,2,\ldots,n$），每层有 $m$（$1,2,\ldots,m$）个房间。

小明会从第一层的某个房间开始找，他找的方式也很特别，每次到了一个房间，如果不是他的同学，他就会询问这个人，然后他就会去那人告诉他的房间号，如果还不是，他就会继续按这个方法找下去，直到找到。当然，他也有可能找不到同学。他的体力也是有限的，他每爬一层楼梯就会消耗 $v$ 体力值。你的任务就是求找到同学耗费的最少体力值，如果找不到，就输出 `impossible` 。

inputFormat:
第一行有五个整数，分别代表 $n$，$m$，$v$，$x$，$y$（$x$，$y$ 表示同学只在 $x$ 层 $y$ 房间）。

$2\sim n+1$ 行，每行 $m\times 2$ 个数字，第 $i+1$ 行 $j\times2-1$ 个数 $a_k$ 和第 $j\times2$ 个数 $a_{k+1} $表示住在 $i$ 层 $j$ 房间的人提供的信息是 $a_k$ 层和 $a_{k+1}$ 房间。（同学的信息就是自己的房间号。）

outputFormat: 一个数，即答案。


title: 进制转换

description:
今天小明学会了进制转换，比如 $(10101)_2$，那么它的十进制表示的式子就是 :

$$1\times 2^4+0\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0$$

那么请你编程实现，将一个 $M$ 进制的数 $N$ 转换成十进制表示的式子。

注意：当系数为 $0$ 时，该单项式要省略。

inputFormat: 两个整数，$M$ 和 $N$，中间用空格隔开。

outputFormat: 共一行，一个十进制表示的式子。

hint: 对于 $100\%$ 的数据，$1<M<10$，$N$ 的位数不超过 $1000$ 且均为正整数。


title: 最小函数值

description: 有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。

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

以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。

outputFormat: 输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。

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

对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10,B_i\le100,C_i\le10^4$。