title: 最接近神的人

description:
破解了符文之语，小 FF 开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小 FF 猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……。

仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。

小 FF 发现门上同样有着 $n$ 个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小 FF 不会……只好又找到了你，并答应事成之后与你三七分……

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

第二行为 $n$ 个整数，表示序列中每个元素。

outputFormat: 一个整数 $\mathit{ans}$，即最少操作次数。


title: 石子合并（弱化版）

type: P

description: 设有 $N(N \le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots,N$。每堆石子有一定的质量 $m_i\ (m_i \le 1000)$。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

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

第二行，$N$ 个整数 $m_i$。

outputFormat: 输出文件仅一个整数，也就是最小代价。


title: 宝物筛选

description:
终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$，重量为 $w_i$，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

inputFormat:
第一行为一个整数 $n$ 和 $W$，分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。

outputFormat: 输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

hint:
对于 $30\%$ 的数据，$n\leq \sum m_i\leq 10^4$，$0\le W\leq 10^3$。

对于 $100\%$ 的数据，$n\leq \sum m_i \leq 10^5$，$0\le W\leq 4\times 10^4$，$1\leq n\le 100$。


title: 帮助

description:
Bubu 的书架乱成一团了！帮他一下吧！

他的书架上一共有 $n$ 本书。我们定义混乱值是连续相同高度书本的段数。例如，如果书的高度是 $[30,30,31,31,32]$，那么混乱值为 $3$；$[30,32,32,31]$ 的混乱度也是 $3$，但 $[31,32,31,32,31]$ 的混乱度是 $5$，这实在是太乱了。

Bubu 想尽可能地减少混乱度，但他有点累了，所以他决定最多取出 $k$ 本书，再随意将它们放到书架上。你能帮助他吗？

inputFormat:
每个输入文件包含最多 $20$ 组测试数据。

每组测试数据开头为两个整数 $n,k\ (1 \le k \le n \le 100)$，表示总共有 $n$ 本书，最多可以进行 $k$ 次搬书操作。

接下来一行有 $n$ 个整数，表示每本书的高度，从左到右。每本书的高度是 $25$ 到 $32$ 间的整数。

最后一组数据后有一行 $n=k=0$，表示输入结束。

outputFormat: 对于每一组数据，输出 $\text{Case}$ 标号和最终最小的混乱度。在每组数据后输出一个空行。


title: 万圣节后的早晨

description:
要求你写一个程序，在一个地图中，找到最小步数将每个鬼移动到他们指定的位置。地图包含一些小方格。每格要么是墙（鬼不能进入），要么是走廊（鬼能进入）。

每一步里，你可以同时移动任意数量的鬼。每个鬼要么待在原地不动，要么移动到相邻的格子里（相邻的格子有公共边），如果移动满足下列条件，则移动是可行的。

1. 没有一个以上的鬼在同一个格子里；
2. 没有一对鬼在一步里交换了位置。

例如，假设鬼的位置是如右上图所示的，其中sharp(#)表示墙，空格表示走廊，a,b,c表示鬼：

```plain
####
 ab#
#c##
####
```
经过一步移动后，地图可以变成如下的样子：

```plain
####     ####     ####       ####
 ab#     a b#     acb#       ab #
#c##     #c##     # ##       #c##
####     ####     ####       ####
```

inputFormat:
输入包括最多 $10$ 组数据，每组数据包含一幅地图。输入格式如下：

$$\begin{matrix}
w & h & n \\
c_{1,1} & c_{1,2} & \cdots & c_{1,w} \\
c_{2,1} & c_{2,2} & \cdots & c_{2,w} \\
\vdots & \vdots & \ddots & \vdots \\
c_{h,1} & c_{h,2} & \cdots & c_{h,w} \\
\end{matrix}$$

第一行的 $w，h$ 和 $n$ 表示地图的宽度和高度，$n$ 表示鬼的数目，他们满足 $4 \le w \le 16$，$4 \le h \le 16$，$1 \le n \le 3$。

接下来 $h$ 行，每行 $w$ 个字符：

- 一个 `#` 表示墙。
- 一个小写字母表示鬼的初始位置（该位置也是走廊）。
- 一个大写字母表示鬼的目标位置（该位置也是走廊）。
- 一个空格表示空的走廊。

在每幅地图里，前 $n$ 个小写字母和前 $n$ 个大写字母表示鬼的初始位置及鬼的目标位置。我们需要将小写字母表示的鬼移动到对应的大写字母的位置里。

最后一组数据后一行有三个 $0$。

outputFormat: 对每组数据输出一行一个整数，表示最小的移动步数。


title: 魔鬼杀手

description:
你生活在一个怪兽世界里。你需要用魔法反抗这些怪兽。

每个怪兽都有一定的 hit points，表示他们的生命值。你可以靠施魔法，降低怪兽的 hit points。每个魔法都会有一定的 damage，表示会减少被攻击者 damage 的 hit point。一个怪兽被击败了当前仅当它的 hitpoint 小于等于 0。另一方面，魔法是要消耗魔力的。因为你的魔力是有限的，你希望用最少的魔力击败所有的怪兽。写一个程序完成这个任务。

inputFormat:
输入按如下的格式给出：

| | | | |
| :-: | :-: | :-: | :-: |
| $N$ | | | |
| $HP_1$ | | | |
| $HP_2$ | | | |
| ... | | | |
| $HP_N$ | | | |
| $M$ | | | |
| $Name_1$ | $MP_1$ | $Target_1$ | $Damage_1$ |
| $Name_2$ | $MP_2$ | $Target_2$ | $Damage_2$ |
| ... | | | |
| $Name_M$ | $MP_M$ | $Target_M$ | $Damage_M$ |

$N$ 是怪兽的数量（$1\le N\le 100$），$HP_{i}$ 表示第 $i$ 个怪兽的 hit point（$l\le HP_i\le 100000$），$M$ 表示可用的魔法数量（$1\le M\le 100$），$Name_j$ 是第 $j$ 种魔法的名字，最长会有 $30$ 个大写或小写字母，$MP_j$ 是这种魔法需要消耗的魔力（$0\le MP_j\le 99$），$Target_j$ 要么是 "Single"，要么是 "All"，表示该魔法只攻击单个怪兽或对全体怪兽同时有效。$Damage_j$ 表示对于所有玫击对象，可以减少攻击对象 $Damage_j$ 的 hit point（$0\le Damage_j\le 999999$）。

所有数字都是整数。最少有一种魔法的 $Damage$ 是非零的。

outputFormat: 输出一行，包含一个整数，表示最小需要消耗的魔力。


title: 染色的立方体

description: 小胖最近迷上了3D物体，尤其是立方体。他手里有很多个立方体，他想让所有的立方体全都长得一样，所以他决定给某些立方体的表面重涂颜色，使得所有的立方体完全相同。但是小胖是很懒的，他想知道最少涂多少次颜色，可以让所有立方体完全相同。

inputFormat:
每个测试点包含至多 $200$ 组数据。

每组数据第一行 $n\ (1≤n≤4)$，表示立方体的数量，接下来 $n$ 行，每行 $6$ 个字符串 $\mathit{color}_1,\allowbreak\mathit{color}_2,\allowbreak\mathit{color}_3,\allowbreak\mathit{color}_4,\allowbreak\mathit{color}_5,\allowbreak\mathit{color}_6$，表示立方体 $6$ 个面的颜色。

其中，面的标号如下：

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

两个立方体被视为相同，当且仅当它们可以在某种摆放方式下，每个面的颜色都对应相同。

如下图所示的两个立方体是相同的。

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

如下图所示的两个立方体是不同的。

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

一种涂色的方案如下：

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

outputFormat: 每组数据，输出一行一个整数，表示最少的涂色数。（涂一个面算一次涂色）

samples:
3
scarlet green blue yellow magenta cyan
blue pink green magenta cyan lemon
purple red blue yellow cyan green
2
red green blue yellow magenta cyan
cyan green blue yellow magenta red
2
red green gray gray magenta cyan
cyan green gray gray magenta red
2
red green blue yellow magenta cyan
magenta red blue yellow cyan green
3
red green blue yellow magenta cyan
cyan green hlue yellow magenta red
magenta red blue yellow cyan green
3
blue green green green green blue
green blue blue green green green
green green green green green sea-green
3
red yellow red yellow red yellow
red red yellow yellow red yellow
red red red red red red
4
violet violet salmon salmon salmon salmon
violet salmon salmon salmon salmon violet
violet violet salmon salmon violet violet
violet violet violet violet salmon salmon
1
red green hlue yellow magenta cyan
4
magenta pink red scarlet vermilion wine-red
aquamarine blue cyan indigo sky-blue turciuoise-blue
blond cream chrome-yellow lemon olive yellow
chrome-green emerald-green green olive vilidian sky-blue
0


title: 宇宙总统

description: 地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

inputFormat:
第一行为一个整数 $n$，代表竞选总统的人数。

接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。

outputFormat:
共两行，第一行是一个整数 $m$，为当上总统的人的号数。

第二行是当上总统的人的选票。

hint:
票数可能会很大，可能会到 $100$ 位数字。

$1 \leq n \leq 20$。


title: 旅行商的背包

description:
小 S 坚信任何问题都可以在多项式时间内解决，于是他准备亲自去当一回旅行商。在出发之前，他购进了一些物品。这些物品共有 $n$ 种，第 $i$ 种体积为 $V_i$，价值为 $W_i$，共有 $D_i$ 件。他的背包体积是 $C$。怎样装才能获得尽量多的收益呢？作为一名大神犇，他轻而易举的解决了这个问题。

然而，就在他出发前，他又收到了一批奇货。这些货共有 $m$ 件，第 $i$ 件的价值 $Y_i$ 与分配的体积 $X_i$ 之间的关系为：$Y_i=a_iX_i^2+b_iX_i+c_i$。这是件好事，但小 S 却不知道怎么处理了，于是他找到了一位超级神犇（也就是你），请你帮他解决这个问题。

inputFormat:
第一行三个数 $n,m,C$，如题中所述；

以下 $n$ 行，每行有三个数 $V_i,W_i,D_i$，如题中所述；

以下 $m$ 行，每行有三个数 $a_i,b_i,c_i$，如题中所述。

outputFormat: 仅一行，为最大的价值。


title: 海滩防御

description:
WLP 同学最近迷上了一款网络联机对战游戏（终于知道为毛 JOHNKRAM 每天刷洛谷效率那么低了），但是他却为了这个游戏很苦恼，因为他在海边的造船厂和仓库总是被敌方派人偷袭。于是，WLP 动用了他那丰满且充实的大脑（或许更偏向前者），想出了一个好主意，他把海滩分成垂直于海岸线的若干列，在其中的几列上放置几个信号塔，试图来监视整个海滩。然而，WLP 是一个非常心急的人，他把信号塔建好后才发现还需给信号塔供能，它们才能投入使用（这不是废话么），它们都有一个工作半径，一个圆形区域里的所有敌人都逃不过它们的监视，不过，WLP 发现，敌人们非常狡猾，除非他将道路完全封死，否则 WLP 的敌人可以走过一条任意弯曲的路（不一定走整点，但是不会出第 $0$ 列和第 $N$ 列构成的边界）来偷他的东西。

于是，WLP 就思考了：到底需要给每个信号塔多大的工作半径，才能将从海滩到内地的路径完全封死呢？他再次动用了他那丰满且充实的大脑，想了一堂数学课，终于，还是没想出来。于是，他向 LZZ 神犇求助（额…… CSUNSHINE 的身份是不是暴露了）。

终于，在 WLP：“ %^!\*@#!\*(\*^!\*#@\$^&（此处省略无数卖萌场景）”的哀求下，LZZ 神犇写了一个程序，在一秒内就解决了问题。但是，邪恶的 LZZ 神犇决定要将这个难题共享给无数无辜的 OIer，所以，现在轮到你了。

inputFormat:
第一行两个整数 $N$ 和 $M$，表示海滩被 WLP 分成的列数 $0,1,2,\cdots,N$ 和信号塔个数。

第 $2$ 至第 $M+1$ 行，每行两个数 $X_i$，$Y_i$ 表示 $1,2,3,\cdots,M$ 号信号塔所在的列数和离开海滩的距离。

outputFormat: 一行一个实数，表示最小的工作半径，保留两位小数。

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

- 对于 $10\%$ 的数据：$1 \le M \le 10$，$1 \le Y_i \le 100$；
- 对于 $30\%$ 的数据：$1 \le M \le 50$，$1 \le Y_i \le 1,000$；
- 对于 $80\%$ 的数据：$1 \le M \le 500$，$1 \le Y_i \le 1,000$；
- 对于 $100\%$ 的数据：$1 \le M \le 800$，$1 \le N \le 1000$，$1 \le X_i \le N$，$1 \le Y_i \le 100,000$。

### 提示

注意，封锁海滩是指，敌人的深入程度是有限制的，若敌人绕过了所有的信号塔，并且可以长驱直入，那么就说明道路没有完全封锁。


title: 数独

description:
数独是根据 $9 \times 9$ 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 $1 - 9$ ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

inputFormat: 一个未填的数独。

outputFormat: 填好的数独。


title: 漂亮的绝杀

background:
话说 absi2011 的企鹅在和斗神塔第 $60$ 层的 Boss 战斗。

不好，这局要输了，企鹅还剩 $4$ 血了 Boss 还有 $392$ 呢，哇，漂亮——红缨枪连击，$280$，$343$（暴击），绝杀！嗜血（$4$ 星，嗜血 $50\%$），完胜（absi2011 的 $60$ 级企鹅贫血，就 $315$，玩过乐斗的别黑）！

description:
别说这是个巧合，这类绝杀还真不少。

现在假设 Boss 还剩下的血为 $x$，absi2011 的企鹅剩 $y$ 血，它拿出的武器的伤害最高是 $z$。它的武器有几率连击。

他问你有无可能绝杀（可连击）。如果能，请先输出一行 `Yes`，否则输出 `No`。如果他给你的数据是错的，请输出 `Wrong Data`。

数据有这么几种情况算错：$y\leq 0$ 或 $y>315$ 或 $y\geq x$ 或    $x>1800$（当前斗神塔 Boss 好像没有超过 $1800$ 血的）或 $z\geq 1000$（红缨枪+天马流星拳+会心一击+残影+武器好手好像都达不到）或 $z\leq 100$（absi2011 认为小于等于 $100$ 就不算绝杀了）。

（输出 `Yes` 后）接下来，他还想问绝杀（就算最高伤害后）如果触发他的 $3$ 星嗜血 / $4$ 星嗜血 / $5$ 星吸星大法各能不能完胜。三星每次的嗜血嗜血量为 $33\%\times$ 伤害（下取整），四星每次的嗜血嗜血量为 $50\%\times$ 伤害（下取整），五星吸星大法嗜血量为 $100\%\times$ 伤害（这还真不用下取整）。两次要分开算。如果超过血上限就不再回血了。

如果三星能就输出一行 `Great`，四星能就输出一行 `Eh..` 和一行 `OK`，五星能就输出两行 `Oh..` 和一行 `Yes , If he can get 5-star.`。

如果都不行，那么输出三行 `No` 和他 $4$ 星嗜血后的血量。

注意，有可能打一下 Boss 就死了，那么不能连击嗜血了。只能算打死 Boss 那下的嗜血。

Boss 死掉当且仅当 Boss 血 $\leq 0$（其实 $<0$ 会自动当成 $0$）。

inputFormat: 一行三个整数，$x,y,z$。

outputFormat: 如题目描述。

hint:
### 提示

Boss 死掉当且仅当 Boss 血 $ \le 0$（其实 $<0$ 会自动当成 $=0$）

### 数据规模

对于 $30\%$ 的数据，保证结果为 `Wrong Data` 或 `No` 或 `Yes`（回车）`Great`。

对于另外 $30\%$ 的数据，保证结果不为 `Wrong Data`。

对于 $100\%$ 的数据，保证 $-10000\leq x\leq 10000,-10000\leq y\leq 10000,-10000\leq z\leq 10000$，即使 `Wrong Data` 了

### 题目来源

fight.pet.qq.com

absi2011 授权原创题目。


title: 帮贡排序

background: 在 absi2011 的帮派里，死号偏多。现在 absi2011 和帮主等人联合决定，要清除一些死号，加进一些新号，同时还要鼓励帮贡多的人，对帮派进行一番休整。

description:
目前帮派内共最多有一位帮主，两位副帮主，两位护法，四位长老，七位堂主，二十五名精英，帮众若干。

现在 absi2011 要对帮派内几乎所有人的职位全部调整一番。他发现这是个很难的事情。于是要求你帮他调整。

他给你每个人的以下数据：

他的名字（长度不会超过 $30$），他的原来职位，他的帮贡，他的等级。

他要给帮贡最多的护法的职位，其次长老，以此类推。

可是，乐斗的显示并不按帮贡排序而按职位和等级排序。

他要你求出最后乐斗显示的列表(在他调整过职位后)：职位第一关键字，等级第二关键字。

注意：absi2011 无权调整帮主、副帮主的职位，包括他自己的（这不是废话么..）

他按原来的顺序给你（所以，等级相同的，原来靠前的现在也要靠前，因为经验高低的原因，但此处为了简单点省去经验。）

inputFormat:
第一行一个正整数 $n$，表示星月家园内帮友的人数。

下面 $n$ 行每行两个字符串两个整数，表示每个人的名字、职位、帮贡、等级。

outputFormat: 一共输出 $n$ 行，每行包括排序后乐斗显示的名字、职位、等级。

samples:
9
DrangonflyKang BangZhu 100000 66
RenZaiJiangHu FuBangZhu 80000 60
absi2011 FuBangZhu 90000 60
BingQiLingDeYanLei HuFa 89000 58
Lcey HuFa 30000 49
BangYou3 ZhangLao 1000 1
BangYou1 TangZhu 100 40
BangYou2 JingYing 40000 10
BangYou4 BangZhong 400 1

samples:
DrangonflyKang BangZhu 66
RenZaiJiangHu FuBangZhu 60
absi2011 FuBangZhu 60
BingQiLingDeYanLei HuFa 58
BangYou2 HuFa 10
Lcey ZhangLao 49
BangYou1 ZhangLao 40
BangYou3 ZhangLao 1
BangYou4 ZhangLao 1

hint:
各种职位用汉语拼音代替。

如果职位剩 $1$ 个，而有 $2$ 个帮贡相同的人，则选择原来在前的现在当选此职位。

另：
帮派名号：星月家园

帮主尊号：Dragonfly Kang

帮派ID：2685023

帮派等级：4

帮派人数：101/110

帮派技能：

星月家园资料，欢迎各位豆油加入^\_^

【数据范围】

对于 $10\%$ 的数据，保证 $n=3$。

对于 $40\%$ 的数据，保证各个人的帮贡均为 $0$。

对于 $100\%$ 的数据，保证 $3\leq n\leq 110$，各个名字长度$\leq30$，$0\leq$ 各个人的帮贡 $\leq1000000000$，
$1\leq$ 各个人等级 $\leq 150$。

保证职位必定为 $\texttt{BangZhu}$，$\texttt{FuBangZhu}$，$\texttt{HuFa}$，$\texttt{ZhangLao}$，$\texttt{TangZhu}$，$\texttt{JingYing}$，$\texttt{BangZhong}$ 之中的一个

保证有一名帮主，保证有两名副帮主，保证有一名副帮主叫 absi2011

不保证一开始帮派里所有职位都是满人的，但排序后分配职务请先分配高级职位。例如原来设一名护法现在设两名。

保证名字不重复。

【题目来源】

fight.pet.qq.com

absi2011 授权题目


title: 【Mc生存】插火把

description:
话说有一天 linyorson 在“我的世界”开了一个 $n \times n$ 的方阵，现在他有 $m$ 个火把和 $k$ 个萤石，分别放在 $(x_1, y_1) \sim (x_m, y_m)$ 和 $(o_1, p_1) \sim (o_k, p_k)$ 的位置，没有光并且没放东西的地方会生成怪物。请问在这个方阵中有几个点会生成怪物？

P.S. 火把的照亮范围是：

```
    |暗|暗| 光 |暗|暗|
    |暗|光| 光 |光|暗|
    |光|光|火把|光|光|
    |暗|光| 光 |光|暗|
    |暗|暗| 光 |暗|暗|
```

萤石：

```
    |光|光| 光 |光|光|
    |光|光| 光 |光|光|
    |光|光|萤石|光|光|
    |光|光| 光 |光|光|
    |光|光| 光 |光|光|
```

inputFormat:
输入共 $m + k + 1$ 行。
第一行为 $n, m, k$。
第 $2$ 到第 $m + 1$ 行分别是火把的位置 $x_i, y_i$。
第 $m + 2$ 到第 $m + k + 1$ 行分别是萤石的位置 $o_i, p_i$。

注：可能没有萤石，但一定有火把。

outputFormat: 有几个点会生出怪物。

hint: 数据保证，$1 \le n \le 100$，$1 \leq m+k \leq 25$，$1 \leq m \leq 25$，$0 \leq k \leq 5$。


title: 矩形分割

description:
有一个长为 $a$，宽为 $b$ 的矩形（$1 \le a \le 6$，$2 \le b \le 6$）。可以把这个矩形看作是 $a\times b$ 个小方格。

我们现在接到了这样的一个任务：请你计算出，把这个矩形分割成两个部分的方法总数。

你不是可以任意地分割这个大的矩形，必须满足：

分割后，每个部分，至少各自均有一个方格是在大矩形的最外边上（即大矩形最外面一环的方格）。

inputFormat: 输入文件仅包含两个数字，$a$ 和 $b$。

outputFormat: 输出仅有一行一个整数，表示分割的方案总数。


title: [国家集训队] 人员雇佣

background: 原《线段覆盖》请做P1803

description:
作为一个富有经营头脑的富翁，小 $L$ 决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数，（我们用 $E_{i,j}$ 表示 $i$ 经理对 $j$ 经理的了解程度），即当经理 $i$ 和经理 $j$ 同时被雇佣时，经理 $i$ 会对经理 $j$ 做出贡献，使得所赚得的利润增加 $E_{i,j}$。

当然，雇佣每一个经理都需要花费一定的金钱 $A_i$，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小 $L$ 当然不会雇佣他。然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少 $E_{i,j}$（注意：这里的 $E_{i,j}$ 与上面的 $E_{i,j}$ 是同一个）。

作为一个效率优先的人，小 $L$ 想雇佣一些人使得净利润最大。你可以帮助小 $L$ 解决这个问题吗？

inputFormat:
第一行有一个整数，表示经理的个数。

第二行有 $N$ 个整数 $A_i$ 表示雇佣每个经理需要花费的金钱。

接下来的 $N$ 行中一行包含 $N$ 个数，表示 $E_{i,j}$，即经理 $i$ 对经理 $j$ 的了解程度。满足 $E_{i,j}=E_{j,i}$。

outputFormat: 第一行包含一个整数，即所求出的最大值。


title: [国家集训队] 种树

description:
A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。

园林部门得到指令后，初步规划出 $n$ 个种树的位置，顺时针编号 $1$ 到 $n$。并且每个位置都有一个美观度 $A_i$，如果在这里种树就可以得到这 $A_i$ 的美观度。但由于 $A$ 城市土壤肥力欠佳，两棵树决不能种在相邻的位置（$i$ 号位置和 $i+1$ 号位置叫相邻位置。值得注意的是 $1$ 号和 $n$ 号也算相邻位置）。

最终市政府给园林部门提供了 $m$ 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将 $m$ 棵树苗全部种上，给出无解信息。

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

第二行 $n$ 个整数，第 $i$ 个代表 $A_i$。

outputFormat: 输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出 `Error!`。


title: 跑步

description: 新牛到部队，CG 要求它们每天早上搞晨跑，从 $A$ 农场跑到 $B$ 农场。从 $A$ 农场到 $B$ 农场中有 $n-2$ 个路口，分别标上号，$A$ 农场为 $1$ 号，$B$ 农场为 $n$ 号，路口分别为 $2,3,4,\cdots,n-1$ 号，从 $A$ 农场到 $B$ 农场有很多条路径可以到达，而 CG 发现有的路口是必须经过的，即每条路径都经过的路口，CG 要把它们记录下来，这样 CG 就可以先到那个路口，观察新牛们有没有偷懒，而你的任务就是找出所有必经路口。

inputFormat:
第一行两个用空格隔开的整数 $n\ (3 \le n \le 2000)$ 和 $e\ (1 \le e \le 8000)$。

接下来从第 $2$ 到第 $e+1$ 行，每行两个用空格隔开的整数 $p$ 和 $q$，表示路口 $p$ 和 $q$ 之间有路径直达。

输入数据保证必经路口一定存在，并且每个路口都和 $A$ 农场、$B$ 农场相连通。

outputFormat:
第一行一个整数 $m$，表示必经路口的数目。

第二行按从小到大的顺序依次输出每个必经路口的编号，每两个数之间用一个空格隔开。


title: 装备运输

description: 德国放松对英国的进攻后，把矛头指向了东边——苏联。$1943$ 年初，东线的战斗进行到白热化阶段。据可靠情报，$90$ 余万德国军队在库尔斯克准备发动浩大攻势。因此，朱可夫元帅要求你立即从远东的军工厂运输大量装备支援库尔斯克前线。列车司机告诉你，一趟列车最多可以容纳 $V$ 体积的武器装备，但是你可能不能装满，因为列车承受不了那么大的重量，一趟列车最多可以承载 $G$ 单位的重量。同时，军工厂仓库提供给你一份装备清单，详细记录了每件装备的体积、重量和火力。为了有效支援朱可夫元帅，你要找到一种方案，使得总火力值最大。

inputFormat:
第一行两个整数 $V$ 和 $G$，表示最大体积和重量。

第二行一个整数 $N$，表示仓库有 $N$ 件装备。

第三到 $N+2$ 行，每行 $3$ 个数 $T_i,V_i,G_i$，表示各装备的火力值、体积和重量。

outputFormat: 输出一个数，表示可能获得的最大火力值。


title: 无穷的序列

description:
有一个无穷序列如下：

$\texttt{110100100010000100000}$…

请你找出这个无穷序列中指定位置上的数字。

inputFormat:
第一行一个正整数 $N$ ，表示询问次数；

接下来的 $N$ 行每行一个正整数 $A_i$，$A_i$ 表示在序列中的位置。

outputFormat: 输出为 $N$ 行，每行为 $0$ 或 $1$ ，表示序列第  $A_i$ 位上的数字。


title: 汤姆斯的天堂梦

description:
汤姆斯生活在一个等级为 $0$ 的星球上。那里的环境极其恶劣，每天 $12$ 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 $N$ 的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。

汤姆斯预先知道了从 $0$ 等级星球去 $N$ 等级星球所有的航线和需要支付（或者可以得到）的金钱，他想寻找一条价格最低（甚至获得金钱最多）的航线。

inputFormat:
第一行一个正整数 $N$（$N \le 100$），接下来的数据可分为 $N$ 个段落，每段的第一行一个整数 $K_i$（$K_i \le 100$），表示等级为 $i$ 的星球有 $K_i$ 个。

接下来的 $K_i$ 行中第 $j$ 行依次表示与等级为 $i$，编号为 $j$ 的星球相连的等级为 $i - 1$ 的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过 $1000$）。

每行以 $0$ 结束，每行的航线数 $\le 100$。

outputFormat: 输出所需（或所得）费用。正数表示支出，负数表示收益。

hint:
对于 $100 \%$ 的数据，$1 \le N \le 100$，$1 \le K_i \le 100$。

样例解释：

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


title: 小明搬家

description:
小明要搬家了，大家都来帮忙。

小明现在住在第 $N$ 楼，总共 $K$ 个人要把 $M$ 个大箱子搬上 $N$ 楼。

最开始 $M$ 个箱子都在 $1$ 楼，但是经过一段混乱的搬运已经乱掉了。最后大家发现这样混乱地搬运过程效率太低了，于是总结出了提高效率的方法。

大家的速度都是每分钟上（或下）一层楼。所有向上走的人手中都拿一个箱子，所有向下走的人手中都不拿箱子。到达第 $N$ 层立刻放下箱子向下走，到达第 $1$ 层立刻拿起箱子向上走。当一个人向上走，另一人向下走而在楼道里相遇时，向上走的人将手中的箱子交给另一人，两人同时反向。即原来拿箱子向上走的人不拿箱子向下走，原来不拿箱子向下走的人现拿着箱子向上走。

求将所有箱子搬完所需的最短时间。

inputFormat:
第一行 $N, K, M$，分别表示楼层数、人数、还放在一楼地上的箱子数。

接下来 $K$ 行，每行两个数 $A_i,B_i$。

$A_i$ 表示第 $i$ 人现所在的楼层数，$B_i$ 为 $0$ 或 $1$，为 $0$ 表示第 $i$ 人正拿着箱子向上走，为 $1$ 表示第 $i$ 人不拿箱子向下走。

输入满足没有任意两人正在同一楼层，在第 $1$ 层的人一定正拿着箱子向上走，在第 $N$ 层的人一定正不拿箱子向下走。

outputFormat: 仅包含一个整数，为搬完箱子的时间。


title: 数列

description: 虽然 msh 长大了，但她还是很喜欢找点游戏自娱自乐。有一天，她在纸上写了一串数字：$1, 1, 2, 5, 4$。接着她擦掉了一个 $1$，结果发现剩下 $1, 2, 4$ 都在自己所在的位置上，即 $1$ 在第 $1$ 位，$2$ 在第 $2$ 位，$4$ 在第 $4$ 位。她希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个游戏很好玩，于是开始乐此不疲地玩起来……不过她不能确定最多能有多少个数在自己的位置上，所以找到你，请你帮忙计算一下！

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

接下来一行为 $n$个用空格隔开的正整数，第 $i$ 行表示数 $A_i$。

outputFormat: 一行一个整数，表示擦掉某些数后，最后剩下的数列中最多能有多少个数在自己的位置上，即 $A_i=i$ 最多能有多少。


title: software

description: 一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成 $m$ 个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。

inputFormat: 输入文件第一行包含两个由空格隔开的整数 $n$ 和 $m$，其中 $1 \le n \le 100$，$1 \le m \le 100$，接下来的 $n$ 行每行包含两个用空格隔开的整数 $d_1$ 和 $d_2$，$d_1$ 表示该技术人员完成第一个软件中的一个模块所需的天数，$d_2$ 表示该技术人员完成第二个软件中的一个模块所需的天数，其中 $1 \le d_1,d_2 \le 100$。

outputFormat: 输出文件仅有一行包含一个整数 $d$，表示公司最早能于 $d$ 天后交付软件。

hint:
### 样例解释

最快的方案是第一个技术人员完成第二个软件的 $18$ 个模块，用时 $18$ 天，第三个技术人员完成第一个软件的 $18$ 个模块，用时 $18$ 天，其余的模块由第二个技术人员完成，用时 $12$ 天，做完所有模块需要 $18$ 天。如果第一个技术人员完成第二个软件的 $17$ 个模块，第三个技术人员完成第一个软件的 $17$ 个模块，其余的模块由第二个技术人员完成，需要用时 $18$ 天，做完所有模块仍然需要 $18$ 天，所以少于 $18$ 天不可能做完所有模块。


title: 黑匣子

description:
Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 $i$。最开始的时候 Black Box 是空的．而 $i=0$。这个 Black Box 要处理一串命令。

命令只有两种：

- `ADD(x)`：把 $x$ 元素放进 Black Box;

- `GET`：$i$ 加 $1$，然后输出 Black Box 中第 $i$ 小的数。

记住：第 $i$ 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 $i$ 个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

| 序号 | 操作 | $i$ | 数据库 | 输出 |
| :--: | :--- | :------: | ------ | :----: |
|   1  | `ADD(3)`     |   $0$    |  $3$  | / |
|   2  | `GET` |   $1$    |  $3$  | $3$ |
|   3  |`ADD(1)`|$1$|$1,3$|/|
|   4  |`GET`|$2$|$1,3$|$3$|
|   5  |`ADD(-4)`|$2$|$-4,1,3$|/|
|   6  |`ADD(2)`|$2$|$-4,1,2,3$|/|
|   7  |`ADD(8)`|$2$|$-4,1,2,3,8$|/|
|   8  |`ADD(-1000)`|$2$|$-1000,-4,1,2,3,8$|/|
|   9  |`GET`|$3$|$-1000,-4,1,2,3,8$|$1$|
|  10  |`GET`|$4$|$-1000,-4,1,2,3,8$|$2$|
|  11  |`ADD(2)`|$4$|$-1000,-4,1,2,2,3,8$|/|

现在要求找出对于给定的命令串的最好的处理方法。`ADD` 命令共有 $m$ 个，`GET` 命令共有 $n$ 个。现在用两个整数数组来表示命令串：

1. $a_1,a_2,\cdots,a_m$：一串将要被放进 Black Box 的元素。例如上面的例子中 $a=[3,1,-4,2,8,-1000,2]$。

2. $u_1,u_2,\cdots,u_n$：表示第 $u_i$ 个元素被放进了 Black Box 里后就出现一个 `GET` 命令。例如上面的例子中 $u=[1,2,6,6]$ 。输入数据不用判错。

inputFormat:
第一行两个整数 $m$ 和 $n$，表示元素的个数和 `GET` 命令的个数。

第二行共 $m$ 个整数，从左至右第 $i$ 个整数为 $a_i$，用空格隔开。

第三行共 $n$ 个整数，从左至右第 $i$ 个整数为 $u_i$，用空格隔开。

outputFormat: 输出 Black Box 根据命令串所得出的输出串，一个数字一行。


title: 5 倍经验日

background: 现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。

description:
现在 absi2011 拿出了 $x$ 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。

由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 $2$ 个药去打别人，别人却表明 $3$ 个药才能打过，那么相当于你输了并且这两个属性药浪费了。

现在有 $n$ 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。

要求求出最大经验 $s$，输出 $5s$。

inputFormat:
第一行两个数，$n$ 和 $x$。

后面 $n$ 行每行三个数，分别表示失败时获得的经验 $\mathit{lose}_i$，胜利时获得的经验 $\mathit{win}_i$ 和打过要至少使用的药数量 $\mathit{use}_i$。

outputFormat: 一个整数，最多获得的经验的五倍。

hint:
**【Hint】**

五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。

**【数据范围】**

- 对于 $10\%$ 的数据，保证 $x=0$。
- 对于 $30\%$ 的数据，保证 $0\le n\le 10$，$0\le x\le 20$。
- 对于 $60\%$ 的数据，保证 $0\le n,x\le 100$， $10<lose_i,win_i\le 100$，$0\le use_i\le 5$。
- 对于 $100\%$ 的数据，保证 $0\le n,x\le 10^3$，$0<lose_i\le win_i\le 10^6$，$0\le use_i\le 10^3$。

**【题目来源】**

fight.pet.qq.com

absi2011 授权题目


title: 凌乱的yyy / 线段覆盖

background: 快 noip 了，yyy 很紧张！

description:
现在各大 oj 上有 $n$ 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 $2$ 个及以上的比赛。

inputFormat: 第一行是一个整数 $n$，接下来 $n$ 行每行是 $2$ 个整数 $a_{i},b_{i}\ (a_{i}<b_{i})$，表示比赛开始、结束的时间。

outputFormat: 一个整数最多参加的比赛数目。


title: 关灯

description:
在某条道路上，有 $n$ 盏灯排成一排，它们有的是开着的，有的是关着的。

由于天马上就要亮了，上级给了你一个任务：把所有的灯都关掉。

只不过，这些灯都比较智能，不会被轻易关掉。它们的开或关遵循如下规则：

- 每一步只能开或关一盏灯。
- 编号为 $1$ 的灯可以随意开或关。
- 如果编号为 $1, 2, \cdots,k-1$ 的灯都关上了了，并且编号为 $k$ 的灯在开着，我们可以随意开或关第 $k+1$ 盏灯。

在关灯之前，请你计算：至少要多少步才能关上所有灯？

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

第 $2$ 行有 $n$ 个整数，如果第 $i$ 个整数 $O_i=0$，表示第 $i$ 个盏灯初始的时候是关着的；如果 $O_i=1$，表示第 $i$ 盏灯初始的时候是开着的。

outputFormat: 共一行一个整数，表示最少需要多少步才能关上所有灯。


title: 跑步

description:
路人甲准备跑 $n$ 圈来锻炼自己的身体，他准备分多次（$\gt1$）跑完，每次都跑正整数圈，然后休息下再继续跑。

为了有效地提高自己的体能，他决定每次跑的圈数都必须比上次跑的多。

可以假设他刚开始跑了 $0$ 圈，那么请问他可以有多少种跑完这 $n$ 圈的方案？

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

outputFormat: 一个整数表示跑完这 $n$ 圈的方案数。

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

对于 $100\%$ 的数据，保证 $5\le n\le 500$。


title: 最长路

description: 设 $G$ 为有 $n$ 个顶点的带权有向无环图，$G$ 中各顶点的编号为 $1$ 到 $n$，请设计算法，计算图 $G$ 中 $1, n$ 间的最长路径。

inputFormat:
输入的第一行有两个整数，分别代表图的点数 $n$ 和边数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行 $3$ 个整数 $u, v, w$（$u<v$），代表存在一条从 $u$ 到  $v$ 边权为 $w$ 的边。

outputFormat:
输出一行一个整数，代表 $1$ 到 $n$ 的最长路。

若 $1$ 无法到达 $n$，请输出 $-1$。


title: 单词分类

description:
Oliver 为了学好英语决定苦背单词，但很快他发现要直接记住杂乱无章的单词非常困难，他决定对单词进行分类。

两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。

例如 $\verb!AABAC!$，它和 $\verb!CBAAA!$ 就可以归为一类，而和 $\verb!AAABB!$ 就不是一类。

现在Oliver有 $N$ 个单词，所有单词均由大写字母组成，每个单词的长度不超过 $100$。你要告诉 Oliver 这些单词会被分成几类。

inputFormat: 输入文件的第一行为单词个数 $N$，以下 $N$ 行每行为一个单词。

outputFormat: 输出文件仅包含一个数，表示这 $N$ 个单词分成的类数。


title: 过河问题

description:
有一个大晴天，Oliver 与同学们一共 $N$ 人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。

船太小了，一次只能乘坐两人。每个人都有一个渡河时间 $T$，船划到对岸的时间等于船上渡河时间较长的人所用时间。

现在已知 $N$ 个人的渡河时间 $T$，Oliver 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。

注意，只有船在东岸（西岸）的人才能坐上船划到对岸。

inputFormat:
输入文件第一行为人数 $N$，以下有 $N$ 行，每行一个数。

第 $i+1$ 行的数为第 $i$ 个人的渡河时间。

outputFormat: 输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间。


title: 集合分组【征集 spj】

description:
现有 $k$ 个整数集合，第 $i$ 个集合有 $s_i$ 个元素。

集合中的数都为正数，且不大于 $n$。现定义集合 $A$ 与集合 $B$ 相似，当且仅当满足如下条件之一：

1. $B$ 与 $A$ 相似；
2. 将 $A$ 集合删去一个元素，或更改一个元素的值之后 $A$ 集合与 $B$ 集合相等。

现要将 $K$ 个集合分成至多 $M$ 组（$M>N$），使得每一组内的集合互不相似。要求你给出一种合法的方案。如果无解请输出 `impossible`。

inputFormat:
输入文件第一行有三个数 $n, k, m$，意义如题目所述。

接下来有 $k$ 行，每行第一数 $s_i$ 表示序列长度。之后 $s_i$ 个数为些集合的元素。

outputFormat: 如果存在合法方案，输出 $k$ 个数，表示每个集合（按输入顺序）被分到的组的编号（$1\sim m$）。否则，若不存在合法方案则输出 `impossible`。


title: 最短路

description:
给定一个包含 $N$ 个点，$M$ 条边的无向图，每条边的边权均为 $1$。

再给定 $K$ 个三元组 $(A,B,C)$，表示从 $A$ 点走到 $B$ 点后不能往 $C$ 点走。注意三元组是有序的，如可以从 $B$ 点走到 $A$ 点再走到 $C$。

现在你要在 $K$ 个三元组的限制下，找出 $1$ 号点到 $N$ 号点的最短路径，并输出任意一条合法路径，会有 Check 检查你的输出。

inputFormat:
输入文件第一行有三个数 $N$，$M$，$K$，意义如题目所述。

接下来 $M$ 行每行两个数 $A$，$B$，表示 $A$，$B$ 间有一条边。

再下面 $K$ 行，每行三个数 $(A,B,C)$ 描述一个三元组。

outputFormat:
输出文件共两行数，第一行一个数 $S$ 表示最短路径长度。 。

第二行 $S+1$ 个数，表示从 $1$ 到 $N$ 所经过的节点。 。


title: 区间运算

description:
区间运算是数学的一个领域。在区间运算中，常量和变量并不表示为一个单独、精确的值，而是表示为一个有着上界和下界的区间或范围。在普通的运算中，一个数量可以表示为数轴上的一个点；而在区间运算中，一个数量表示数轴上的一段，例如 $[3,5]$ 表示数轴上从 $3$ 到 $5$ 的一段。当精确的数值表示为区间时，上界与下界是相同的，如 $5$ 表示为区间即为 $[5,5]$。

两个区间的运算，是指一个区间中的每个点与另一个区间中的每个点所做的运算，通过运算所得的所有点的集合即为运算的结果。例如，$[3,5]+[-10,1]=[-7,6]$。你的任务是写一个可以根据单行表达式进行取相反数、加、减、乘、除等基本的区间运算的程序。下面是一些运算的例子：

- 取相反数：$-[-3,5]=[-5,3]$；
- 加法：$[3,5]+[-10,1]=[-7,6]$；
- 减法：$[3,5]-[-10,1]=[2,15]$；
- 乘法：$[3,5]\times [-10,1]=[-50,5]$；
- 除法：$[3,5]\div [-10,-0.1]=[-50,-0.3]$。

inputFormat:
程序的输入包含一行或多行区间运算的中缀表达式，每个区间都表示为 $[\min,\max]$，表达式中包括括号、负号（$\verb!-!$）、加号（$\verb!+!$）、减号（$\verb!-!$）、乘号（$\verb!*!$）和除号（$\verb!/!$），括号可能是嵌套的。每一行中都有可能有空格，但空格不会在表示区间的括号 $[\min,\max]$ 中间或负号后出现。程序不需要处理科学记数法，如 $\verb!2E6!=2\times 10^6$。每一行都不超过 $80$ 个字符。运算采用标准的优先级规则。下面按优先级递减的顺序给出各个算符：

- $\verb!(!,\verb!)!$ 括号；
- $\verb!-!$ 取相反数；
- $\verb!*!,\verb!/!$，乘法和除法，同级运算按从左到右的顺序；
- $\verb!+!,\verb!-!$，加法和减法，同级运算按从左到右的顺序。

outputFormat: 对于输入文件中每一行的表达式，以 $[\min,\max]$（均保留 $3$ 位小数）的形式输出运算结果。每个结果占一行。结果中不应有空格。在运算中，如果将一个包含 $0$ 的区间用作除数，则输出 `Division by zero`。


title: 拯救小 tim

description:
小 tim 在游乐场，有一天终于逃了出来！但是不小心又被游乐场的工作人员发现了…所以你的任务是安全地把小 tim 护送回家。但是，A 市复杂的交通状况给你出了一大难题。

A 市一共有 $n$ 个路口，$m$ 条单行马路。但是，每条马路都只有一段时间是开放的。为了安全，你必须选择一条护送路线，使得小 tim 在路上的时间最短，即到家的时刻减去离开游乐场的时刻最短。

inputFormat:
第一行 $4$ 个数，分别是 $n,m,s,t$。基地在路口 $s$，码头在路口 $t$。

接下来 $m$ 行每行 $5$ 个数 $x,y,b,e,c$ 表示一条 $x$ 路口到 $y$ 路口的单行线，在 $b$ 时刻到 $e$ 时刻之间开放，需要 $c$ 的时间通过这条路（必须保证行进在路中间时，路一直开放，否则小 tim 会被捉住）。两个路口之间可能会有多条道路。一开始的时刻是 $0$（当然，你可以不用马上出发，在基地多呆一段时间）。

如果不存在任何一种方案使得小 tim 能成功到达码头，输出 `Impossible`。

outputFormat: 一行，为小 tim 在路上停留的最短时间。

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

最优方案应该是，在 $1$ 号点停留至时刻 $1$，然后走到 $3$ 号点，然后走到 $4$ 号点。到达时刻为时刻 $4$。tim 在路上的时间为 $4-1=3$。

### 数据范围

对于所有测试数据：
- $2\leqslant n\leqslant100$，$0\leqslant m\leqslant1000$，$1\leqslant s,t\leqslant n$，$s\not=t$；
- $1\leqslant x,y\leqslant n$，$0\leqslant b,e,c\leqslant10000$，$b<e$。


title: 数的序号

description:
我们可以用下面的方案给二叉树标号：

- 空树的序号为 $0$。
- 只有一个根结点的树序号为 $1$。
- 所有包含 $m$ 个结点的二叉树的序号一定比任何一个包含 $m+1$ 个结点的二叉树的序号小。
- 对于任何一棵二叉树，设其左子树序号为 $L$，右子树序号为 $R$，且它有 $m$ 个结点，若它的序号为 $n$，则所有序号大于 $n$ 的 $m$ 个结点的二叉树，要么左子树序号大于 $L$，要么左子树序号等于 $L$ 且右子树序号大于 $R$。

例如，编号为 $0$ 到 $5$ 的六棵树形状如下：

```plain
0   1   2       3   4       5
    X   X       X   X       X
         \     /     \       \
          X   X       X       X
                       \     /
                        X   X
```

你的任务就是对给定的序号，输出该序号所对应的二叉树。

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

输入的每行有一个非负整数 $n$，$n=0$ 表示输入结束，此时**不需要**输出 $n=0$ 的空树。

outputFormat:
对于每组数据，输出一行，代表序号 $n$ 对应的树。

一棵二叉树的表示为 `(L)X(R)`，其中 $L,R$ 分别是左子树和右子树的表示，如一侧为空则省略，例如只有左子树则表示为 `(L)X`。

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

对于所有测试点，保证 $1\le n\le 5\times10^8$，数据组数不超过 $50$。


title: 蠕虫游戏

description:
蠕虫是一个古老的电脑游戏，它有许多版本。但所有版本都有一个共同的规则：操纵一条蠕虫在屏幕上转圈，并试着去避免撞到自己或障碍物。

这里我们将模拟一个简单的版本。游戏将在 $50 \times 50$ 的棋盘上进行，棋盘的左上角为 $(1,1)$，蠕虫在初始时是一串 $20$ 个相连的方格。所谓相连是指方格在水平或垂直方向上相接。蠕虫开始时是水平地伸展开的，从 $(25,11)$ 到 $(25,30)$。其中 $(25,30)$ 是它的头。蠕虫只能向东 $\verb!E!$、西 $\verb!W!$、南 $\verb!S!$、北 $\verb!N!$ 四个方向移动，但不能向自己移动，因此在开始时向西 $\verb!W!$ 是不允许的。每次移动时，蠕虫向给定的方向移动，一次只移一格，并且保持它的长度不变。因此只有蠕虫的头和尾所占据的方格在移动一步后被改变。注意：蠕虫的头能移动到虫尾刚刚让出的空格。

你将被给定一系列移动指令并模拟虫的移动，直到蠕虫撞上了自己，或者蠕虫越出了棋盘，或者蠕虫成功地完成了这些指令。在前两种情况下你应当忽略剩下的指令。

inputFormat:
每个输入文件包含了多组数据，每个数据占两行。

第一行是一个整数 $n\ (n<100)$，表示移动指令的指令数（以 $n=0$ 表示输入结束）；

第二行包括了 $n$ 个字符，只有可能是 $\verb!ESWN!$ 中的一种，字符之间没有空格，表示移动的指令。

outputFormat:
每个数据输出一行，格式为以下 $3$ 种中的一种：

- $\texttt{The worm ran into itself on move \textrm{\it m}.}$
- $\texttt{The worm ran off the board on move \textrm{\it m}.}$
- $\texttt{The worm successfully made all \textrm{\it m} moves.}$

其中，$m$ 是你要决定输出的步数。

samples:
18
NWWWWWWWWWWSESSSWS
20
SSSWWNENNNNNWWWWSSSS
30
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
13
SWWWWWWWWWNEE
0

samples:
The worm successfully made all 18 moves.
The worm ran into itself on move 9.
The worm ran off the board on move 21.
The worm successfully made all 13 moves.


title: 忠诚

description: 老管家是一个聪明能干的人。他为财主工作了整整  $10$ 年。财主为了让自已账目更加清楚，要求管家每天记  $k$ 次账。由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按  $1, 2, 3 \ldots$ 编号，然后不定时的问管家问题，问题是这样的：在   $a$ 到  $b$ 号账中最少的一笔是多少？为了让管家没时间作假，他总是一次问多个问题。

inputFormat:
输入中第一行有两个数  $m, n$，表示有  $m$ 笔账  $n$ 表示有  $n$ 个问题。

第二行为  $m$ 个数，分别是账目的钱数。

后面  $n$ 行分别是  $n$ 个问题，每行有   $2$ 个数字说明开始结束的账目编号。

outputFormat: 在一行中输出每个问题的答案，以一个空格分割。


title: 棋盘染色

description: 给定一个 $N \times M$ 的网格，每个格子可以染成黑色或者白色，要求所有黑色格子连通，所有白色格子连通，并且至少有一个黑色格子贴边，至少有一个白色格子贴边。问有多少种染色方法？

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

outputFormat: 只有一个正整数表示答案。


title: 电影投票

description: 有一个投票系统可以给电影评分，规定每票都必须投 $1$ 到 $10$ 的整数。现在希望投尽量少的票让一个电影的平均分数低于某个值。

inputFormat: 多组数据，对于每组数据只有一行，有两个带 $1$ 位小数的实数 $X$ 、 $Y$ 和一个正整数 $N$，表示一部电影的平均得分保留 $1$ 位小数后的结果和 XP 期望的平均得分保留一位小数后的结果，并且该电影已经被投了 $N$ 次票了。保证 $Y$ 小于等于 $X$。

outputFormat: 对于每组数据，输出一个正整数 $\mathit{ans}$，表示最坏情况下只要 XP 投 $\mathit{ans}$ 张票，一定能让这部电影的平均得分保留一位小数后小于等于 $Y$。

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

- 对于 $30\%$ 的数据，$1\le N \le 100$，$1\le T \le 100$；
- 对于 $100\%$ 的数据，$1\le T \le 10^4$，$X,Y\in[1,10]$，$1\le N \le 10^6$。

### 注意事项

保留一位小数采取四舍五入保留法。实数可能会有精度误差。


title: 公共子序列

description: 求 $3$ 个字符序列有多少个不同的公共子序列，不包括空序列。

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

接下来 $3$ 行，每行一个无空格长度为 $n$ 的字符序列。只包含小写字母 `a` 到 `z`。

outputFormat: 一行一个正整数 $ans$，对 $10^8$ 取模。

hint:
#### 样例 1解释

对于唯一的一个样例，有 $5$ 种子序列，分别是 `a`，`ab`，`aa`，`bb`，`b`。

#### 数据范围与约定

- 对于 $30\%$ 的数据，保证 $1 \le n \le 10$；
- 对于 $70\%$ 的数据，保证 $1 \le n \le 50$；
- 对于 $100\%$ 的数据，保证 $1 \le n \le 150$。


title: [USACO07FEB] Cow Party S

description:
寒假到了，$n$ 头牛都要去参加一场在编号为 $x$ 的牛的农场举行的派对，农场之间有 $m$ 条有向路，每条路都有一定的长度。

每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 $n$ 头牛的最短路径（一个来回）中最长的一条路径长度。

inputFormat:
第一行有三个整数，分别表示牛的数量 $n$，道路数 $m$ 和派对农场编号 $x$。
接下来 $m$ 行，每行三个整数 $u, v, w$，表示存在一条由 $u$ 通向 $v$ 的长度为 $w$ 的道路。

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

hint:
### 样例 1 解释
![](https://cdn.luogu.com.cn/upload/image_hosting/rl3com2y.png)

### 数据规模与约定

对于全部的测试点，保证 $1 \leq x \leq n \leq 10^3$，$1 \leq m \leq 10^5$，$1 \leq u,v \leq n$，$1 \leq w \leq 10^2$，保证从任何一个结点出发都能到达 $x$ 号结点，且从 $x$ 出发可以到达其他所有节点。


title: 魔法指纹

description:
对于任意一个至少两位的正整数 $n$，按如下方式定义 $\mathrm{magic}(n)$：将 $n$ 按十进制顺序写下来，依次对相邻两个数写下差的绝对值。这样，得到了一个新数，去掉前导 $0$，则定义为 $\mathrm{magic}(n)$。特别地，若 $n$ 为一位数，则 $mag_ic(n)=n$。

例如：$\mathrm{magic}(5913)=482$，$\mathrm{magic}(1198)=081=81$，$\mathrm{magic}(666)=00=0$。

对任意一个数 $n$，反复迭代计算 $\mathrm{magic}$ 值直到 $n$ 变成一个一位数，可以得到一个序列 $[n,\mathrm{magic}(n),\mathrm{magic}(\mathrm{magic}(n)),\cdots]$。最后的这个值称为数 $n$ 的 $\mathrm{magic}$ 指纹。

例如，对于 $n=5913$，我们得到序列：$[5913,482,46,2]$。所以 $5913$ 的 $\mathrm{magic}$ 指纹为 $2$。

若一个数的 $\mathrm{magic}$ 指纹为 $7$，则认为这个数是个幸运数。

现在，给定 $A,B$，计算出 $[A,B]$ 中有多少个数是幸运数。

inputFormat: 输入两行，每行一个数。第一行是 $A$，第二行表示 $B$。

outputFormat: 输出 $[A,B]$ 中有多少个数是幸运数。


title: [COI2007] Patrik 音乐会的等待

description:
$n$ 个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。

队列中任意两个人 $a$ 和 $b$，如果他们是相邻或他们之间没有人比 $a$ 或 $b$ 高，那么他们是可以互相看得见的。

写一个程序计算出有多少对人可以互相看见。

inputFormat:
输入的第一行包含一个整数 $n$，表示队伍中共有 $n$ 个人。

接下来的 $n$ 行中，每行包含一个整数，表示人的高度，以毫微米(等于 $10^{-9}$ 米)为单位，这些高度分别表示队伍中人的身高。

outputFormat: 输出仅有一行，包含一个数 $s$，表示队伍中共有 $s$ 对人可以互相看见。

hint:
#### 数据规模与约定
对于全部的测试点，保证 $1\le$ 每个人的高度 $< 2^{31}$，$1 \le n \le 5\times 10^5$。


title: 进击的奶牛

description:
Farmer John 建造了一个有 $N$（$2 \leq N \leq 10 ^ 5$) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 $x _ 1, x _ 2, \cdots, x _ N$（$0 \leq x _ i \leq 10 ^ 9$）。

他的 $C$（$2 \leq C \leq N$）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

inputFormat:
第 $1$ 行：两个用空格隔开的数字 $N$ 和 $C$。

第 $2 \sim N+1$ 行：每行一个整数，表示每个隔间的坐标。

outputFormat: 输出只有一行，即相邻两头牛最大的最近距离。


title: [USACO11OPEN] Corn Maze S

description:
This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide's start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.

The outside of the corn maze is entirely corn except for a single exit.

The maze can be represented by an N x M (2 <= N <= 300; 2 <= M <= 300) grid. Each grid element contains one of these items:

\* Corn (corn grid elements are impassable)

\* Grass (easy to pass through!)

\* A slide endpoint (which will transport a cow to the other endpoint)

\* The exit

A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.

Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).

Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the 'at' symbol (@). What is the minimum time she needs to move to the exit space?

inputFormat:
第一行：两个用空格隔开的整数 $N$ 和 $M$。

第 $2\sim N+1$ 行：第 $i+1$ 行描述了迷宫中的第 $i$ 行的情况（共有$M$个字符，每个字符中间没有空格）。

outputFormat: 一个整数，表示起点到出口所需的最短时间。

translation:
奶牛们去一个 $N\times M$ 玉米迷宫，$2 \leq N \leq 300,2 \leq M \leq300$。

迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。

如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置，奶牛在传送过后不会立刻进行第二次传送，即不会卡在传送装置的起点和终点之间来回传送。

玉米迷宫除了唯一的一个出口都被玉米包围。

迷宫中的每个元素都由以下项目中的一项组成：

1. 玉米，`#` 表示，这些格子是不可以通过的。
1. 草地，`.` 表示，可以简单的通过。
1. 传送装置，每一对大写字母 $\tt{A}$ 到 $\tt{Z}$ 表示。
1. 出口，`=` 表示。
1. 起点， `@` 表示

奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 $1$ 个单位时间。从装置的一个结点到另一个结点不花时间。

hint:
例如以下矩阵，$N=5,M=6$。

```plain
###=##
#.W.##
#.####
#.@W##
######
```

唯一的一个装置的结点用大写字母 $\tt{W}$ 表示。

最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费 $0$ 个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了 $3$ 个单位时间。


title: 猴子选大王数据再加强版

description:
有 $n$ 只猴子围成一圈，顺时针编号依次为 $1, 2, 3,\cdots, n$。从第一只猴子开始，不断进行如下操作：顺时针数恰好 $m$ 只猴子，使其出列，再从下一只猴子开始重新计数，如此循环，直到最后只剩下一只猴子。最后剩下来的猴子是这局游戏的获胜者。

现在你需要对于 $n=a,a+1,\cdots,b$ 计算出哪只猴子成为获胜者的次数最多，输出对应的编号。如果有多只猴子成为获胜者的次数均最多，将它们的编号从小到大输出。

inputFormat: 输入共一行三个数 $a, b, m$，如题。

outputFormat:
输出共两行。

第一行输出获胜次数最多的猴子获胜的次数。

第二行输出若干个数，为猴子的编号。


title: [USACO3.4] 美国血统 American Heritage

description:
农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。

你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多于 $26$ 个的顶点。

这是在样例输入和样例输出中的树的图形表达方式：

```plain
　　　　　　　　 C
　　　　　　   /  \
　　　　　　  /　　\
　　　　　　 B　　  G
　　　　　　/ \　　/
　　　　   A   D  H
　　　　　　  / \
　　　　　　 E   F

```

附注：

- 树的中序遍历是按照左子树，根，右子树的顺序访问节点；
- 树的前序遍历是按照根，左子树，右子树的顺序访问节点；
- 树的后序遍历是按照左子树，右子树，根的顺序访问节点。

inputFormat:
第一行一个字符串，表示该树的中序遍历。

第二行一个字符串，表示该树的前序遍历。

outputFormat: 单独的一行表示该树的后序遍历。

hint:
题目翻译来自NOCOW。

USACO Training Section 3.4


title: [USACO3.2] 香甜的黄油 Sweet Butter

description:
Farmer John 发现了做出全威斯康辛州最甜的黄油的方法：糖。

把糖放在一片牧场上，他知道 $N$ 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

Farmer John 很狡猾。像以前的 Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

Farmer John 知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

inputFormat:
第一行包含三个整数 $N,P,C$，分别表示奶牛数、牧场数和牧场间道路数。

第二行到第 $N+1$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i-1$ 头奶牛所在的牧场号。

第 $N+2$ 行到第 $N+C+1$ 行，每行包含三个整数 $A,B,D$，表示牧场号为 $A$ 和 $B$ 的两个牧场之间有一条长度为 $D$ 的双向道路相连。

outputFormat: 输出一行一个整数，表示奶牛必须行走的最小的距离和。


title: [国家集训队] Crash的数字表格 / JZPTAB

description:
今天的数学课上，Crash 小朋友学习了最小公倍数（Least Common Multiple）。对于两个正整数 $a$ 和 $b$，$\text{lcm}(a,b)$ 表示能同时被 $a$ 和 $b$ 整除的最小正整数。例如，$\text{lcm}(6, 8) = 24$。

回到家后，Crash 还在想着课上学的东西，为了研究最小公倍数，他画了一张 $ n \times m$ 的表格。每个格子里写了一个数字，其中第 $i$ 行第 $j$ 列的那个格子里写着数为 $\text{lcm}(i, j)$。

看着这个表格，Crash 想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题：这个表格中所有数的和是多少。当 $n$ 和 $m$ 很大时，Crash 就束手无策了，因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大，Crash 只想知道表格里所有数的和对 $20101009$ 取模后的值。

inputFormat: 输入包含一行两个整数，分别表示 $n$ 和 $m$。

outputFormat: 输出一个正整数，表示表格中所有数的和对 $20101009$ 取模后的值。


title: 轰炸III

background: 一个大小为 $n\times m$ 的城市遭到了 $x$ 次轰炸，每次都炸了一个每条边都与边界平行的矩形。

description: 在轰炸后，有 $y$ 个关键点，指挥官想知道，它们有没有受到过轰炸，如果有，被炸了几次，最后一次是第几轮。

inputFormat:
第一行共四个整数，分别为 $n,m,x,y$。

接下来 $x$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，表示被轰炸的矩形的左上角坐标和右下角坐标（比如 $1,3,7,10$ 就表示被轰炸的地方是从 $(1,3)$ 到 $(7,10)$ 的矩形）。

接下来 $y$ 行，每行两个整数，表示这个关键点的坐标。

outputFormat: 输出共 $y$ 行，每行第一个字符为 `Y` 或 `N`，表示是否被轰炸；若为 `Y`，在一个空格后为两个整数，表示被炸了几次和最后一次是第几轮。


title: 杠杆数

description:
如果把一个数的某一位当成支点，且左边的数字到这个点的力矩和等于右边的数字到这个点的力矩和，那么这个数就可以被叫成杠杆数。

比如 $4139$ 就是杠杆数，把 $3$ 当成支点，我们有这样的等式：$4\times 2+1\times 1=9\times 1$。

给定区间 $[x,y]$，求出在 $[x,y]$ 中有几个杠杆数。

inputFormat: 两个数，表示 $x,y$。

outputFormat: 一个输出，表示区间 $[x,y]$ 中杠杆数的个数。


title: A+B Problem（再升级）

background:
题目名称是吸引你点进来的。

实际上该题还是很水的。

description:
- $1+1=?$ 显然是 $2$。
- $a+b=?$ P1001 回看不谢。
- 哥德巴赫猜想 似乎已呈泛滥趋势。

_以上纯属个人吐槽_

给定一个正整数 $n$，求将其分解成若干个素数之和的方案总数。

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

outputFormat: 一行一个整数表示方案总数。


title: 樱花

background: 《爱与愁的故事第四弹·plant》第一章。

description: 爱与愁大神后院里种了 $n$ 棵樱花树，每棵都有美学值 $C_i(0 \le C_i \le 200)$。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 $P_i(0 \le P_i \le 100)$ 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 $T_i(0 \le T_i \le 100)$。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

inputFormat:
共 $n+1$行：

第 $1$ 行：现在时间 $T_s$（几时：几分），去上学的时间 $T_e$（几时：几分），爱与愁大神院子里有几棵樱花树 $n$。这里的 $T_s$，$T_e$ 格式为：`hh:mm`，其中 $0 \leq hh \leq 23$，$0 \leq mm \leq 59$，且 $hh,mm,n$ 均为正整数。

第 $2$ 行到第 $n+1$ 行，每行三个正整数：看完第 $i$ 棵树的耗费时间 $T_i$，第 $i$ 棵树的美学值 $C_i$，看第 $i$ 棵树的次数 $P_i$（$P_i=0$ 表示无数次，$P_i$ 是其他数字表示最多可看的次数 $P_i$）。

outputFormat: 只有一个整数，表示最大美学值。

hint:
$100\%$ 数据：$T_e-T_s \leq 1000$（即开始时间距离结束时间不超过 $1000$ 分钟），$n \leq 10000$。保证 $T_e,T_s$ 为同一天内的时间。

样例解释：赏第一棵樱花树一次，赏第三棵樱花树 $2$ 次。


title: 速算游戏

description:
jyx 和 cyy 打赌，比谁 $24$ 点算得快，算得慢的那个人请客。$24$ 点的规则是这样的：给定 $4$ 个 $1\sim 9$ 的整数，用括号改变运算顺序，通过加、减、乘、除中的一系列运算，得到整数 $24$。

注意所有中间结果必须是整数（例如 $(2\times 2)/4$ 是允许的，而 $2\times (2/4)$ 是不允许的）。

为了赢得这个比赛，请写一个程序帮助我作弊，快速地计算出 $24$ 点。

inputFormat: 一行 $4$ 个整数，为给定的 $4$ 个数字。输入数据保证有解。

outputFormat: 一行，以字符串的形式输出结果。注意将每一步的运算的括号补齐（例如 $(3+5)+6$ 和 $3\times(5+6)$）。如果有多种解答，输出字典顺序最小的一个。


title: 素数密度

background:
UPD:

- 2024.8.12：加入一组 Hack 数据。

description:
 给定 $L,R$，请计算区间 $[L,R]$ 中素数的个数。

   $1\leq L\leq R < 2^{31}$，$R-L\leq 10^6$。

inputFormat: 第一行，两个正整数 $L$ 和 $R$。

outputFormat: 一行，一个整数，表示区间中素数的个数。


title: 数页码

description: 一本书的页码是从 $1\sim n$ 编号的连续整数：$1,2,3,\cdots,n$。请你求出全部页码中所有单个数字的和，例如第 $123$ 页，它的和就是 $ 1+2+3=6$。

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

outputFormat: 一行，代表所有单个数字的和。


title: 单人纸牌

description:
单人纸牌游戏，共 $36$ 张牌分成 $9$ 叠，每叠 $4$ 张牌面向上。每次，游戏者可以从某两个不同的牌堆最顶上取出两张牌面相同的牌（如黑桃 $10$ 和梅花 $10$）并且一起拿走。如果最后所有纸牌都被取走，则游戏者就赢了，否则游戏者就输了。

George 很热衷于玩这个游戏，但是一旦有时有多种选择的方法，George 就不知道取哪一种好了，George 会从中随机地选择一种走，例如：顶上的 $9$ 张牌为 $\tt KS,\tt KH,\tt KD,\tt 9H,\tt 8S,\tt 8D,\tt 7C,\tt 7D,\tt 6H$，显然有 $5$ 种取法：$\tt (KS,KH),(KS,KD),(KH,KD),(8S,8D),(7C,7D)$，当然 George 取到每一种取法的概率都是 $1/5$。

有一次，George 的朋友 Andrew 告诉他，这样做是很愚蠢的，不过 George 不相信，他认为如此玩最后成功的概率是非常大的。请写一个程序帮助 George 证明他的结论：计算按照他的策略，最后胜利的概率。

inputFormat: 输入共 $9$ 行，每行 $4$ 组用空格分开的字串，每个字串两个字符，分别表示牌面和花色，按照从堆底到堆顶的顺序给出。

outputFormat: 一行，最后胜利的概率，精确到小数点后 $6$ 位。

samples:
AS 9S 6C KS
JC QH AC KH
7S QD JD KD
QS TS JS 9H
6D TD AD 8S
QC TH KC 8D
8C 9D TC 7C
9C 7H JH 7D
8H 6S AH 6H


title: 三子棋I

description:
小 a 和 uim 喜欢互相切磋三子棋。三子棋大家都玩过是吗？就是在九宫格里面 OOXX（别想歪了），谁连成 $3$ 个就赢了。

由于小 a 比较愚蠢，uim 总是让他先。

我们用 $9$ 个数字表示棋盘位置：

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
1 & 2 & 3 \\\hline
4 & 5 & 6 \\\hline
7 & 8 & 9 \\\hline
\end{array}$$

所有的棋谱都是已经结束的棋局，要么一方获胜，要么平局。

今天，他们下了一下午的棋，小 a 为了提高技术，录下了很多棋谱。他想知道，一盘棋结束时，到底是谁赢。

inputFormat: 一行，一串数字，表示落子的地点。小 a 总是先下。

outputFormat: 一行，如果小 a 赢，输出 `xiaoa wins.`。如果 uim 赢，输出 `uim wins.`。如果平局，输出 `drew.`。


title: Play with Power

description:
Masha 和 Stas 正在玩一个游戏。在游戏的开始，给出一个数  $n$，同时有两个正整数  $a,b$，初始时满足 $a^b\le n$。

Masha 先手。每一回合，玩家要将 $a,b$ 的其中一个数加上  $1$，但不能使 $a^b>n$，否则该玩家输。

现在，Masha 想知道，假如两人都使用最优策略，对于同一个 $n$ 和不同的 $a,b$，谁将获胜呢？

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

第二行一个数  $t$，表示数据组数。

接下来  $t$ 行，每行两个数  $a,b$，描述每组数据。

outputFormat:
共  $t$ 行，对于每组数据：

- 若 Masha 获胜，输出 `Masha`。
- 若 Stas 获胜，输出 `Stas`。
- 若平手，输出 `Missing`。


title: Color the Axis

description: 在一条数轴上有 $n$ 个点，分别是 $1,2,\ldots,n$。一开始所有的点都被染成黑色。接着我们进行 $m$ 次操作，第 $i$ 次操作将 $[l_i,r_i]$ 这些点染成白色。请输出每个操作执行后剩余黑色点的个数。

inputFormat: 输入一行为 $n$ 和 $m$。下面 $m$ 行每行两个数 $l_i$，$r_i$。

outputFormat: 输出 $m$ 行，为每次操作后剩余黑色点的个数。


title: [JSOI2007] 重要的城市

description:
参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。

同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。

他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市c是重要的。

jsoi冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。

inputFormat:
第一行两个整数N,M,N为城市数，M为道路数

接下来M行，每行三个整数，表示两个城市之间的无向边，以及之间的路的长度

outputFormat: 一行，按递增次序输出若干的数，表示重要的城市。

hint:
30%的数据：$N\le 20$；

60%的数据：$N\le 100$；

100%的数据：$N\le 200,M\le \frac{N\times (N-1)}{2},0<c\le 10000$。c即路的长度。

保证不出现重边和自环

感谢@赵昕鹏 和@qq2477259579 提供程序

如果没有点的话需要输出一行

“No important cities.”

去掉引号


title: [USACO05NOV] 奶牛玩杂技

background: Farmer John 养了 $N$ 头牛，她们已经按 $1\sim N$ 依次编上了号。FJ 所不知道的是，他的所有牛都梦想着从农场逃走，去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳（她们还尝试过把自己装在大炮里发射出去，但可想而知，结果是悲惨的） 。最终，她们决定练习一种最简单的杂技：把所有牛都摞在一起， 比如说， 第一头牛站在第二头的身上， 同时第二头牛又站在第三头牛的身上...最底下的是第 $N$ 头牛。

description:
每头牛都有自己的体重以及力量，编号为 $i$ 的奶牛的体重为 $W_i$，力量为 $S_i$。

当某头牛身上站着另一些牛时它就会在一定程度上被压扁，我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去它的力量。奶牛们按照一定的顺序摞在一起后， 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。

你的任务就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。

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

接下来 $N$ 行，每行两个整数 $W_i$ 和 $S_i$。

outputFormat: 一行一个整数表示最小总压扁指数。


title: 奶牛晒衣服

background: 熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。

description: 一件衣服在自然条件下用一秒的时间可以晒干 $a$ 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 $b$ 点湿度（一秒晒干 $a+b$ 湿度），但在同一时间内只能烘一件衣服。现在有 $n$ 件衣服，第 $i$ 衣服的湿度为 $w_i$（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 $0$ 为干 ）。

inputFormat:
第一行三个整数，分别为 $n,a,b$。
接下来 $2$ 到 $n+1$ 行，第 $i$ 行输入 $w_i$。

outputFormat: 一行，弄干所有衣服的最少时间。

hint:
### 样例解释

让机器烘第三件衣服即可一秒完成。

### 数据范围

$1 \le w_i,a,b,n \le 5 \times 10^5$


title: 阅览室

description:
一个阅览室每天都要接待大批读者。阅览室开门时间是 $O$，关门时间是 $T$。每位读者的到达时间都不一样，并且想要阅读的刊物不超过 $5$ 本。

每位读者心里对自己想看的刊物都有一个排位，到达之后他会先去找自己最想看的刊物，如果找不到则去找其次想看的刊物。如果找不到任何他想看的刊物，他会开始等待，直到有一本以上的他想看的刊物被人放回原处。当然，他会先去拿其中自己最想看的刊物。当他看完某一本刊物后，就把它放回原处，接着去找自己没看过的最想看的刊物。如此下去，直到看完所有他想看的刊物为止。

矛盾出现在两个人同时想要拿同一本刊物的时候。阅览室为了避免读者之间出现争执，作了一个规定，读者每次在开始等待时先去服务台做一次登记。如果两个人都同时想要一本刊物，那么先登记的读者将得到这本刊物。如果两个人同时登记，那么先到达阅览室的读者将得到刊物。没得到的人就只能去找其他的刊物看。

阅览室关门时，所有读者都将被强迫离开阅览室，不再允许继续阅读。

现在阅览室想做一个统计调查，你被要求写一个程序来模拟这个过程计算出所有刊物被阅读的总次数。当某个读者开始阅读某本刊物时，该刊物的被阅读次数就加 $1$，无论这本刊物最后有没有被读完。

inputFormat:
输入包含多组测试数据。

每个测试数据开头是两个整数 $T$ 和 $n\ (1 \le n \le 100)$，分别表示图书馆关门时间和读者总数。接下来按照读者的到达时间先后依次给出了每位读者的具体描述。

每个读者描述开头是一个整数 $t\ (0 \le t<T)$，表示该读者到达时间。接下来一行开头是一个整数 $k\ (1 \le k \le 5)$，表示该读者想要看的刊物数目。之后跟着 $2k$ 个整数按照读者想要阅读的刊物的顺序依次给出了刊物的描述。其中第 $2i-1$ 个整数表示刊物的编号 $s\ (0 \le s<1000)$，第 $2i$ 个整数表示该读者读完这本刊物所需的时间。

outputFormat: 对于每个测试数据，在单独一行里输出所有刊物被阅读的总次数。


title: 影像之结构化特征

description:
在影像比对中，有一种方法是利用影像中的边缘（edge）信息，计算每个边缘资讯中具有代表性的结构化特征，以作为比对两张影像是否相似的判断标准。Water-filling 方法是从每个边缘图的一个端点开始，绕着相连的边缘点走并依序编号。若走到某一步时，遇到一个以上不同的连接点，则分成不同路径同时继续走，直到没有任何连接点为止。如果一个点和另一个点为上下左右相邻，就称为连接。

例如，在图 $1$ 的影像中包含三个边缘图，每个边缘图由一些互相连接的边缘点构成。图中以黑色的方块代表边缘点，白色的方块代表背景。在 Water-filling 方法中，首先，从第一行（row）开始，由左至右，由上至下，先找到第一个黑点并编号为 $1$。接着，找 $1$ 的下一个尚未编号的连接点并编号为 $2$。依此方法继续往下一个点前进依次编号。在编号 $6$ 的点之后有两个尚未编号的连接点，此时，则分为两条路线，并同时编号为 $7$ 继续往下走。当走到没有任何的相连点时，则结束现有边缘图的编号，并继续对影像中的其它边缘图编号。走完图 $1$ 所有边缘图后所得到的编号如图 $2$ 所示。所以，走完这三个边缘图所需要的步数分别为 $12$、 $7$ 及 $3$；所以，$12$、$7$ 及 $3$ 可以作为代表此张影像的结构化特征。请注意：位于斜对角上的两点不能算做连接，如：

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

请写一个程序计算每个影像中，以 Water-filling 方法走完其中所有的边缘图后，将每个边缘图需走的步数依走访的顺序列出。

inputFormat: 输入文件包含一个正方形的影像。每组影像以图的宽度 $n$ 开头 $(l \le n \le 1000)$。接下来的 $n$ 行代表影像的内容：$0$ 表示背景的白点，$1$ 表示黑色的边缘点。

outputFormat: 对每一个输入的影像，以 Water-filling 方法走完所有的边缘图后，先印出此张影像中共有几个边缘图。接着，将每个边缘图需走的步数按升序列出。


title: 游戏

description:
给定两个正整数数列，你要用它们来做一个游戏：你需要对数列进行若干次操作，每一次操作，应选择两个正整数 $k_1$ 和 $k_2$，并删除第一个数列的最后 $k_1$ 个数，计算出它们的和 $s_1$；删除第二个数列的最后 $k_2$ 个数，计算出它们的和 $s_2$。这一次操作的得分就是 $(s_2-k_2)\times(s_1-k_1)$。两个数列应同时被清空，不允许一个数列空了，而另一个数列中还有数。游戏的总得分就是每一次操作的得分总和。

求最小的总得分。

inputFormat:
第一行是两个整数 $n$ 和 $m$，分别表示第一个数列和第二个数列的初始长度。

第二行有 $n$ 个正整数，是第一个数列的数。

第三行有 $m$ 个正整数，是第二个数列的数。

数列中的数都不超过 $1000$。

outputFormat: 一个整数，表示最小的总得分。


title: 轰炸II

description:
一个城市遭到了 $M$ 次轰炸，每次都炸了一个每条边都与边界平行的矩形。

在轰炸后，有 $N$ 个关键点，指挥官想知道，它们有没有受到过轰炸，如果有，被炸了几次，最后一次是第几轮。

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

以下 $M$ 行，每行四个整数：$x_1$、$y_1$、$x_2$、$y_2$，表示被轰炸的矩形的左上角坐标和右下角坐标（比如`1 3 7 10`就表示被轰炸的地方是从$(1,3)$到$(7,10)$ 的矩形）。

再以下 $N$ 行，每行两个整数，表示这个关键点的坐标。

outputFormat:
共 $N$ 行，

每行第一个字符为 `YES` 或 `NO`，表示是否被轰炸，若为 `YES`，在一个空格后为两个整数，表示被炸了几次和最后一次是第几轮。


title: [USACO12OPEN] Bookshelf G

description:
When Farmer John isn't milking cows, stacking haybales, lining up his cows, or building fences, he enjoys sitting down with a good book.  Over the years, he has collected N books (1 <= N <= 100,000), and he wants to build a new set of bookshelves to hold them all.

Each book i has a width W(i) and height H(i).  The books need to be added to a set of shelves in order; for example, the first shelf should contain books 1...k for some k, the second shelf should start with book k+1, and so on.  Each shelf can have a total width of at most L (1 <= L <= 1,000,000,000).  The height of a shelf is equal to the height of the tallest book on that shelf, and the height of the entire set of bookshelves is the sum of the heights of all the individual shelves, since they are all stacked vertically.

Please help FJ compute the minimum possible height for the entire set of bookshelves.

inputFormat:
第一行：两个数 $N$ 和 $L$ 。

接下来 $N$ 行每行两个数 $H_i$ 和 $W_i$ 。

outputFormat: 一个数，书架高度的最小值。

translation:
当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 $N$ 本书 $(1 \le N \le 100,000)$ ， 他想造一个新的书架来装所有书。

每本书 $i$ 都有宽度 $W_i$ 和高度 $H_i$ 。书需要按顺序添加到一组书架上；比如说，第一层架子应该包含书籍 $1  ... k$ ，第二层架子应该以第 $k + 1$ 本书开始，以下如此。每层架子的总宽度最大为 $L(1 \le L \le 1,000,000,000)$ 。每层的高度等于该层上最高的书的高度，并且整个书架的高度是所有层的高度的总和，因为它们都垂直堆叠。

请帮助农夫约翰计算整个书架的最小可能高度。

有 $N(1 \le N \le 100,000)$ 本书，每本书有一个宽度 $W_i$ ，高度 $H_i$ ，$(1 \le H_i \le 1,000,000; 1 \le W_i \le L)$ 。

现在有足够多的书架，书架宽度最多是 $L (1 \le L \le 1,000,000,000)$ ，把书按顺序 $($先放 $1$ ，再放 $2.....)$ 放入书架。某个书架的高度是该书架中所放的最高的书的高度。

将所有书放入书架后，求所有书架的高度和的最小值。


title: [USACO12MAR] Tractor S

description:
经过一天漫长的工作，农场主 John 完全忘记了他的拖拉机还在场地中央。他的奶牛们总喜欢和他搞些恶作剧，它们在场地的不同位置丢下 $n$ 堆干草。这样 John 就必须先移走一些干草堆才能将拖拉机开走。

拖拉机和干草堆都可以看作是二维平面上的点，它们的坐标都是整数，没有哪堆干草的坐标和拖拉机的初始坐标一致。John 驾驶拖拉机只能沿着坐标轴的方向移动若干单位长度，比如说，他可以先朝北移动 $2$ 个单位长度，再向东移动 $3$ 个单位长度等等。拖拉机不能移动到干草堆所占据的点。

请你帮助 John 计算一下，最少要移动多少堆干草才能将拖拉机开回坐标原点。

inputFormat:
输入的第一行是三个用空格隔开的整数，依次代表干草的堆数 $n$ 和拖拉机的起始坐标 $(x_0, y_0)$。

第 $2$ 行到第 $(n+1)$ 行，每行有两个用空格隔开的整数，第 $(i + 1)$ 行的整数 $x_i, y_i$ 代表第 $i$ 堆干草的坐标为 $(x_i, y_i)$。

outputFormat: 一行一个整数，表示最少要移动多少堆干草 John 才能将拖拉机开回坐标原点。

hint: 对于 $100\%$ 的数据，保证 $1 \leq n \leq 5 \times 10^4$，$1 \leq x_i, y_i \leq 10^3$。


title: [NOIP2016 提高组] 换教室

background: NOIP2016 提高组 D1T3

description:
对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 $2n$ 节课程安排在 $n$ 个时间段上。在第 $i$（$1 \leq i \leq n$）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 $c_i$ 上课，而另一节课程在教室 $d_i$ 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 $n$ 节安排好的课程。如果学生想更换第 $i$ 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 $i$ 个时间段去教室 $d_i$ 上课，否则仍然在教室 $c_i$ 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 $i$ 节课程的教室时，申请被通过的概率是一个已知的实数 $k_i$，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 $m$ 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 $m$ 门课程，也可以不用完这 $m$ 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 $v$ 个教室，有 $e$ 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。 当第 $i$（$1 \leq i \leq n-1$）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

inputFormat:
第一行四个整数 $n,m,v,e$。$n$ 表示这个学期内的时间段的数量；$m$ 表示牛牛最多可以申请更换多少节课程的教室；$v$ 表示牛牛学校里教室的数量；$e$ 表示牛牛的学校里道路的数量。

第二行 $n$ 个正整数，第 $i$（$1 \leq i \leq n$）个正整数表示 $c_i$，即第 $i$ 个时间段牛牛被安排上课的教室；保证 $1 \le c_i \le v$。

第三行 $n$ 个正整数，第 $i$（$1 \leq i \leq n$）个正整数表示 $d_i$，即第 $i$ 个时间段另一间上同样课程的教室；保证 $1 \le d_i \le v$。

第四行 $n$ 个实数，第 $i$（$1 \leq i \leq n$）个实数表示 $k_i$，即牛牛申请在第 $i$ 个时间段更换教室获得通过的概率。保证 $0 \le k_i \le 1$。

接下来 $e$ 行，每行三个正整数 $a_j, b_j, w_j$，表示有一条双向道路连接教室 $a_j, b_j$，通过这条道路需要耗费的体力值是 $w_j$；保证 $1 \le a_j, b_j \le v$，$1 \le w_j \le 100$。

保证 $1 \leq n \leq 2000$，$0 \leq m \leq 2000$，$1 \leq v \leq 300$，$0 \leq e \leq 90000$。

保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。

保证输入的实数最多包含 $3$ 位小数。

outputFormat:
输出一行，包含一个实数，四舍五入精确到小数点后恰好 $2$ 位，表示答案。你的输出必须和标准输出完全一样才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 $4 \times 10^{-3}$。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）


title: 好朋友

background: 小可可和所有其他同学的手腕上都戴有一个射频识别序列号码牌，这样老师就可以方便的计算出他们的人数。很多同学都有一个“好朋友” 。如果 $A$ 的序列号的约数之和恰好等于 $B$ 的序列号，那么 $A$ 的好朋友就是 $B$。在这里，一个数的约数不包括这个数本身。因为一些同学的号码约数和大于其他任何同学的号码，所以这些同学没有好朋友。一些同学有一个“非常好友” 。当两个同学互为“好朋友”时，他们就是一对“非常好友” 。注意在这道题中，忽略那些自己是自己的“非常好友”的情况。

description: 给定一个序列号 $s$，找出序列号不小于 $s$ 的第一对“非常好友” 。

inputFormat: 只有一行一个整数 $s$，即给定的序列号下界。

outputFormat:
输出一行两个用空格隔开的整数 $a$ 和 $b$。

$a$ 表示第一个序列号不小于 $s$ 的有“非常好友”的同学，$b$ 是 $a$ 的“非常好友” 。（注：允许 $b<s$）

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

- 对于 $100\%$ 的数据，保证 $6\le s\le1.8\times10^4$。


title: 跳跳棋

description:
跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。

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

我们用跳跳棋来做一个简单的游戏：棋盘上有 $3$ 颗棋子，分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$。（棋子是没有区别的）

跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过 $1$ 颗棋子。

写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。

inputFormat:
第一行包含三个整数，表示当前棋子的位置 $a,b,c$。（互不相同）

第二行包含三个整数，表示目标位置 $x,y,z$。（互不相同）

outputFormat:
如果无解，输出一行 `NO`。

如果可以到达，第一行输出 `YES`，第二行输出最少步数。


title: 投资的最大效益

background: 约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。

description:
例如：有如下两种不同的债券：

1. 投资额 $\$4000$，年利息 $\$400$；
2. 投资额 $\$3000$，年利息 $\$250$。

初始时，有 $\$10000$ 的总资产，可以投资两份债券 1 债券，一年获得 $\$800$ 的利息；而投资一份债券 1 和两份债券 2，一年可获得 $\$900$ 的利息，两年后，可获得 $\$1800$ 的利息；而所有的资产达到 $\$11800$，然后将卖掉一份债券 2，换购债券 1，年利息可达到 $\$1050$；第三年后，总资产达到 $\$12850$，可以购买三份债券 1，年利息可达到 $\$1200$，第四年后，总资产可达到 $\$14050$。

现给定若干种债券、最初的总资产，帮助约翰先生计算，经过 $n$ 年的投资，总资产的最大值。

inputFormat:
第一行为三个正整数 $s, n, d$，分别表示最初的总资产、年数和债券的种类。

接下来 $d$ 行，每行表示一种债券，两个正整数 $a, b$ 分别表示债券的投资额和年利息。

outputFormat: 仅一个整数，表示 $n$ 年后的最大总资产。


title: 花店橱窗布置

description:
某花店现有 $F$ 束花，每一束花的品种都不一样。至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，从左到右按 $1\sim V$ 顺序编号，$V$ 是花瓶的数目。

花束可以移动，并且每束花用 $1\sim F$ 的整数标识。所有花束在放入花瓶时必须保持其标识数的顺序。例如，假设杜鹃花的标识数为 $1$，秋海棠的标识数为 $2$，康乃馨的标识数为 $3$，即杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。每个花瓶只能放一束花。

每个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数 $a_{i,j}$）来表示，空置花瓶的美学值为 $0$。在上述的例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下的表格来表示：

|        | 花瓶 1 | 花瓶 2 | 花瓶 3 | 花瓶 4 | 花瓶 5 |
| ------ | ----- | ----- | ----- | ----- | ----- |
| 杜鹃花 | $7$     | $23$    | $-5$    | $-24$   | $16$    |
| 秋海棠 | $5$     | $21$    | $-4$    | $10$    | $23$    |
| 康乃馨 | $-21$   | $5$     | $-4$    | $-20$   | $20$    |

根据表格，杜鹃花放在花瓶 $2$ 中，会显得非常好看，但若放在花瓶 $4$ 中，则显得很难看。

为了取得最佳的美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。

inputFormat:
输入文件的第一行是两个整数 $F$ 和 $V$，分别为花束数和花瓶数。

接下来是矩阵 $a_{i,j}$，共 $F$ 行，每行 $V$ 个整数，$a_{i,j}$ 表示花束 $i$ 摆放在花瓶 $j$ 中的美学值。

outputFormat: 输出文件的第一行是一个整数，为最大的美学值；接下来一行 $F$ 个整数，为那束花放入那个花瓶的编号。

hint:
对于 $100\%$ 的数据，$1\le F\le V\le 100$。

感谢 @罗恺 提供 SPJ


title: [IOI1998] [USACO5.5] 矩形周长Picture

background: 墙上贴着许多形状相同的海报、照片。它们的边都是水平和垂直的。每个矩形图片可能部分或全部的覆盖了其他图片。所有矩形合并后的边长称为周长。

description:
编写一个程序计算周长。

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

如图 $1$ 所示 $7$ 个矩形。

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

如图 $2$ 所示，所有矩形的边界。所有矩形顶点的坐标都是整数。

inputFormat: 输入文件的第一行是一个整数 $N$，表示有多少个矩形。接下来 $N$ 行给出了每一个矩形左下角坐标和右上角坐标。

outputFormat: 输出文件只有一个正整数，表示所有矩形的周长。

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

对于全部数据，$1 \le N<5000$，所有坐标的数值范围都在 $-10^4$ 到 $10^4$ 之间。


title: 质数取石子

description: 桌上有若干个石子，每次可以取质数个。谁先取不了，谁就输。问最少几步能赢？（一个人取一次算一步）假设双方都使用最优策略，且必胜方会尽量快地取胜，必败方会尽可能拖延步数。

inputFormat:
第一行 $N$，表示有 $N$ 组数据

接下来 $N$ 行为石子数

outputFormat: 每组数据一个数，若必胜，则输出最少步数，否则输出 $-1$。


title: 多人背包

description:
求01背包前k优解的价值和

DD 和好朋友们要去爬山啦！

他们一共有 K 个人，每个人都会背一个包。这些包 的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都有 给定的体积和价值。

在 DD 看来，合理的背包安排方案是这样的： 每个人背包里装的物品的总体积恰等于包的容量。 每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。

任意两个人，他们包里的物品清单不能完全相同。 在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？

inputFormat:
第一行三个数K、V、N

接下来每行两个数，表示体积和价值

outputFormat: 前k优解的价值和


title: 不听话的机器人

description:
机器人收到 $N$ 条指令，但它不想走到障碍物上或走出边界，所以决定拒绝一些指令。求最少拒绝多少条指令？

`FORWARD` 前进 $1$

`BACK` 后退 $1$

`LEFT` 左转 $90$ 度

`RIGHT` 右转 $90$ 度

初始时，机器人是面对着上方的。

inputFormat:
第一行 $M,N,X_0,Y_0$ ($M\le 100,N\le 1000$)，表示场地大小为 $M\times M$，共有 $N$ 条指令，起点 $(X_0,Y_0)$。

接下来一个 $M\times M$ 矩阵，表示场地。其中 `.` 为场地，`*`为障碍物。

接下来 $N$ 行，表示 $N$ 条命令。

outputFormat: 一个数，表示最少拒绝多少条命令。

samples:
4 7 3 3
.***
..**
*..*
****
LEFT
FORWARD
LEFT
BACK
FORWARD
RIGHT
FORWARD


title: 新魔法药水

description: 商店里有 $N$ 种药水，每种药水都有一个售价和回收价。小 $S$ 攒了 $V$ 元钱，还会 $M$ 种魔法，可以把一些药水合成另一种药水。他一天可以使用 $K$ 次魔法，问他一天最多赚多少钱？

inputFormat:
第一行四个数N、M、V、K

接下来N行，每行两个数，表示药水的售价和回收价。

接下来M行，每行若干个数，第一个数表示魔法的成品，第二个数是原料的种数，接下来为各种原料的编号

outputFormat:
第一行四个数 $N,M,V,K$。

接下来 $N$ 行，每行两个数，表示药水的售价和回收价。

接下来 $M$ 行，每行若干个数，第一个数表示魔法的成品，第二个数是原料的种数，接下来为各种原料的编号。

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

对于全部数据，$N \le 60$，$M \le 240$，$V \le 1000$，$k \le 30$。


title: 星之器

background:
Magic Land 上的时间又过了若干世纪…

现在，人们谈论着一个传说：从前，他们的祖先来到了一个位于东方的岛屿，那里简直就是另外一个世界。善于分析与构造的 Magic Land 上的人们总是不明白那里的人们是如何不借助精确的实验与计算驱动和操纵魔法。

description:
偶然地，一个魔法使（Magician）来到了 Magic Land，在临走的时候留下了一个神奇的盒子，叫做星之器（Casket of star）。

虽然不知道这个盒子是做什么的，但是经过了大量的实验和计算后，人们已经清楚它的一些事实：

1. 星之器之中有 $N\times M$ 个区域，可看作分成 $N$ 行和 $M$ 列的格子，每个区域之中有若干单位的称为“星”的对象，这个对象的最小单位已经被确定，所以，这个数量总是整数。
2. 魔法使可以驱动星之器中位于同一行或同一列的不相邻（有公共边的区域称为相邻的）两个区域中各 $1$ 单位的“星”，使得它们分别向中心移动 $1$ 格。
3. 每一次使用 2 中的方法驱动“星”，将会产生魔力，魔法使会得到这一部分魔力。魔力的量等于这个两个区域之间所间隔的区域数。

这样，我们可以用一个 $N\times M$ 的数表来表示星之器的状态，比如 $N=2,M=3$ 时：

```plain
2 0 1                                     1 2 0
5 1 4                                     5 1 4
```

当星之器为左侧的状态时，通过操纵第一行的第 $1$ 和 $3$ 个区域中的“星”，变为右侧所示的状态，同时，将产生 $1$ 单位的魔力（因为这两个区域之间恰好隔了 $1$ 个区域）。

在经过了进一步的研究之后，人们知道了这个星之器最初的状态（Ini）以及最终被他们得到时的状态（Fin）。

你希望知道，星之器最多帮助它的拥有者提供了多少的魔力。即：经过一系列上述操作由初态（Ini）变为终态（Fin），至多产生多少魔力。

需要注意的是，显然操作过程中每个区域内“星”的数量不能是负的，即：如果那个区域已经没有“星”了，当然就不能继续操作了。

inputFormat:
第一行包含两个正整数 $N,M$ 表示星之器的大小。

接下来的 $N$ 行，每行包含 $M$ 个自然数：$\mathit{Ini}_{i,j}$，描绘了初态（Ini）。

在一个空行后的 $N$ 行，每行包含 $M$ 个自然数：$\mathit{Fin}_{i,j}$，描绘了终态（Fin）。

outputFormat: 输出一个正整数，表示至多产生的魔力。

hint:
对于 $100\%$ 的数据，$1\le N,M\le200$，$\mathit{Ini}_{i,j},\mathit{Fin}_{i,j}\le1000$。

所有数据保证了至少存在一个操作方法使得星之器由初态变为终态，同时保证了初态与终态不是完全相同的。


title: 输油管道问题

background:
听说最近石油危机。

所以想到了这题。

description:
某石油公司计划建造一条由东向西的主要输油管道。

该管道要穿过一个有 $n$ 口油井的油田。从每口油井都要有一条输油管道沿最短路径（或南或北）与主管道相连。

如果给定 $n$ 口油井的位置，及它们的 $x$ 坐标（东西向）和 $y$ 坐标（南北向），应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置？证明可规定时间内确定主管道的最优位置。

inputFormat:
第一行是油井数 $n$。

接下来 $n$ 行是油井的位置，每行 $2$ 个整数 $x$ 和 $y$。

outputFormat: 只有一行，表示油井到主管道之间的输油管道最小长度总和。

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

对于全部数据，$1 \le n \le 10000$，$-10^4 \le x,y \le 10^4$。


title: 独眼兔

description: 太郎有一只特殊的兔子，它只有一只左眼，所以当它移动时是不能向右转弯的。一天，太郎跟独眼兔做一个游戏，太郎在平面内放了 $n$ 个萝卜，每个萝卜有个位置 $(x_i,y_i)$，且任意两个萝卜的 $x_i$，$y_i$ 都是不相同的，独眼兔要去吃这些萝卜。设萝卜 $A(x_i,y_i)$ 是所有萝卜中最小的，那独眼兔会从 $(0,y_i)$ 出发，走向萝卜 $A$，然后开始吃萝卜。当它吃完一个萝卜后，独眼兔会确定下一个萝卜作为目标，然后径直向萝卜走去，当然当它移动的时候是不能向右转弯的。独眼兔还有一个特点，它走过的路径上会留下特殊的气味，所以独眼兔不希望它将要走的路与前面它走过的路相交。太郎想知道独眼兔如何才能吃到最多的萝卜。

inputFormat:
第一行是个整数 $n$；

接下来 $n$ 行，每行两个整数。第 $i+1$ 行表示第 $i$ 号萝卜的位置 $(x_i,y_i)$。

outputFormat: 一行，输出最多能吃到的萝卜数，后面输出吃萝卜的顺序。


title: [NOI2009] 二叉查找树

description:
已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值都比它左儿子结点的数据值大，而比它右儿子结点的数据值小。

另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的儿子结点的权值要小。

已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插入结点所得到的、按照数据值排序的二叉查找树。

一个结点在树中的深度定义为它到树根的距离加 $1$。因此树的根结点的深度为 $1$。

每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为所有结点在树中的访问代价之和。

现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些结点的权值，但每次修改你会付出 $K$ 的额外修改代价。你可以把结点的权值改为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的问题是，整棵树的访问代价与额外修改代价的和最小是多少？

inputFormat:
输入文件中的第一行为两个正整数 $N,K$。其中 $N$ 表示结点的个数，$K$ 表示每次修改所需的额外修改代价。

接下来的一行为 $N$ 个非负整数，表示每个结点的数据值。

再接下来的一行为 $N$ 个非负整数，表示每个结点的权值。

再接下来的一行为 $N$ 个非负整数，表示每个结点的访问频度。

其中：所有的数据值、权值、访问频度均不超过 $4 \times 10^5$。

outputFormat: 输出文件中仅一行为一个数，即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。

hint:
### 样例解释

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

输入的原图是左图，它的访问代价是 $1 \times 1+2 \times 2+3 \times 3+4 \times 4=30$。

最佳的修改方案是把输入中的第 $3$ 个结点的权值改成 $0$，得到右图，访问代价是：$1 \times 2+2 \times 3+3 \times 1+4 \times 2=19$，加上额外修改代价 $10$，一共是 $29$。

### 数据范围

- 对于 $40\%$ 的数据，满足 $N \leq 30$；
- 对于 $70\%$ 的数据，满足 $N \leq 50$；
- 对于 $100\%$ 的数据，满足：$1 \leq N \leq 70$，$1 \leq K \leq 3 \times 10^7$。


title: A % B Problem

background:
题目名称是吸引你点进来的。
实际上该题还是很水的。

description: 给定 $l, r$，求区间 $[l, r]$ 内质数的个数。

inputFormat:
第一行有两个整数，分别代表询问次数 $n$ 和 给定区间的右端点最大值 $m$。

接下来 $n$ 行，每行两个整数 $l, r$，代表一次查询。

outputFormat: 对于每次查询输出一行，若 $l, r \in [1, m]$，则输出区间质数个数，否则输出 `Crossing the line`。


title: 编号

description:
太郎有 $N$ 只兔子，现在为了方便识别它们，太郎要给他们编号。兔子们向太郎表达了它们对号码的喜好，每个兔子 $i$ 想要一个整数，介于 $1$ 和 $M_i$ 之间（可以为 $1$ 或 $M_i$）。当然，每个兔子的编号是不同的。现在太郎想知道一共有多少种编号的方法。

你只用输出答案对 $10^9+7$ 取余的结果即可。如果这是不可能的，就输出 $0$。

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

第二行 $N$ 个整数 $M_i$。

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

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

对于全部数据，$1 \le N \le 50$，$1\le M_i\le 1000$。


title: 【Mc生存】经验值

background: 初一福利第2弹。。。

description:
话说 clearman 在 MC 世界开了个祥艺奶牛场，用岩浆、TNT 等丧心病狂的折磨牛，获取牛肉、牛奶等刷经验。他想知道他到底达到什么层次。

他总共进行了 $n$ 项操作，每次操作要付出 $x$ 生命值（初始生命是 $10$ 点，初一党都知道！并且要先计算付出的生命值，如果小于等于 $0$，则死亡，本次及以下操作都无效。但切记：付出生命值可以是负数，也就是说可以回复 $−x$ 点生命值，但上限只能是 $10$！切记！），每次操作可以获得 $a$ 经验值（不能为负），他最后能达到 $m$ 级 $t$ 经验。

P.S. 关于等级

初始等级为 $0$。每加 $2^m$（$m$ 为当前等级）点经验可升一级。

1、假设 clearman 一共得到 $15$ 点经验，那么他应该为 $4$ 级（ $15-1-2-4-8=0$）加 $0$ 点经验。
2、假设 clearman 一共获得 $39$ 点经验，那么他应该为 $5$ 级（ $39-1-2-4-8-16=8$）加 $8$ 点经验。

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

接下来 $n$ 行，每行两个数，为 clearman 的一次操作。

outputFormat: 一行，为等级和经验值。

hint:
数据很弱，人肉输的，但是很坑。。。

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 20$。


title: 饥饿的奶牛

description:
有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。

现用汉语翻译为：

有 $N$ 个区间，每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。

对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。

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

接下来 $N$ 行，每行两个数 $x,y$，描述一个区间。

outputFormat: 输出最多能吃到的牧草堆数。

hint: $1 \leq n \leq 1.5 \times 10^5$，$0 \leq x \leq y \leq 3 \times 10^6$。


title: 愚蠢的组合数

description:
最近老师教了狗狗怎么算组合数，狗狗又想到了一个问题。。。

狗狗定义 $C(N,K)$ 表示从 $N$ 个元素中不重复地选取 $K$ 个元素的方案数。

狗狗想知道的是 $C(N,K)$ 的奇偶性。

当然，这个整天都老是用竖式算 $123456789 \times 987654321=?$ 的人不会让你那么让自己那么轻松，它说：“ $N$ 和 $K$ 都可能相当大”。

但是狗狗也犯难了，所以它就找到了你，想请你帮他解决这个问题。

inputFormat:
第一行一个正整数 $t$，表示数据的组数。

第 $2$ 至第 $2+t-1$ 行，每行有两个非负整数 $N$ 和 $K$，描述每组数据。数据保证 $k\le n$。

outputFormat: 每一组输入，如果 $C(N,K)$ 是奇数则输出 $1$，否则输出 $0$。


title: 公交车

description:
某城市有个能容纳 $n$ 辆公交车的停车场。每一天，这些公交车都要依次有序离开停车库去另一个终点站。这终点站距离停车场有 $d$ 米的路程。当然第 $i$ 辆公交车离开停车场的时间是 $t_i$ 秒，并以最大速度不超过 $v_i$ 米/秒行驶，加速度最大值为 $a$。一辆公交车能瞬间减速，也能瞬间改变它的加速度。当然每辆车的最大加速度都一样为 $a$。

不管有多大的马力，一辆公交车都不能超过其他另外的公交车，如果一辆公交车追上另一辆公交车，那么后面追上的车跟前面被追的车一起并排行驶同时到达终点站。当然司机都是尽可能快的驾车到达终点站的。

作为公交公司老板的你，希望每辆公交车都尽可能快的到达终点站。当然，公交车到达终点站时，速度可以没必要达到 $0$。当一辆公交车离开停车场时，它的起始速度等于 $0$。通过物理的观点解释的话，公交车可以看成是抽象的一个物体而已，除了能加速和减速，其他对速度的影响都可以忽略掉。

inputFormat:
第一行三个空格隔开的整数 $n, a, d$（$1 \leq n \leq 10^5$，$1 \leq a, d \leq 10^6$），分别表示公交车的数量，最大加速度。离终点站的距离。

接下来 $n$ 行，每行有一对整数 $t_i, v_i$（$0 \leq t_1 < t_2 < \cdots < t_{n-1} < tn \leq 10^6$，$1 \leq v_i \leq 10^6$），分别表示每辆车离开停车场的时刻和能够行驶的最大速度。

outputFormat: 输出每辆公交车到达终点站的时刻。一行表示一辆公交车的到达时刻，输出时刻的公交车顺序按照输入的公交车顺序。输出答案的相对或绝对误差不能超过 $10^{-4}$（即末尾保留 $4$ 位小数）。

hint:
【样例解释】

第二辆公交车能追上第一辆公交车，在行驶到距离终点 $510.5$ 公里处。然后还剩 $9489.5$ 公里的路程，两辆车都以 $10$ km/h 的速度，一起到达终点的，它们到达终点的时刻是 $1000.5$ 秒，第三辆公交车不能赶上其他的公交车，他到达终点的时刻是 $11000.05$ 秒。


title: 对撞机

description:
在2312年，宇宙中发现了 $n$ 台巨型对撞机，这些对撞机分别用 $1 \sim n$ 的自然数标识。科学家们不知道启动这些对撞机会发生什么危险事故，所以这些机器，刚开始都是出于关闭的状态。

随着科学家们的研究发现，第 $i$ 台对撞机启动是安全的，当且仅当其他已经启动的对撞机的标识数都跟这台对撞机标识数互质。（例如假设前面启动的对撞机标识数是 $j$，如果 $i$ 能启动，那么 $i,j$ 互质，即 $\gcd(i,j) = 1$）。如果两台对撞机的标识数不为互质数就启动，那么就会发生爆炸事故。

基于前面的研究，科学家们准备做各种启动和关闭对撞机的实验。为了确保科学家们的生命安全，你要设计一个远程遥控的软件。

刚开始，所有的对撞机都是关闭状态。你的程序将会收到许多询问，格式为“启动、关闭第 $i$ 台对撞机”。这个程序应该能处理这些询问（根据收到询问的先后顺序处理）。程序按照如下的格式输出处理结果。

如果询问为 `+ i`（表示启动第 $i$ 台对撞机），程序应该按照下面三种情况之一输出结果。

- `Success`，表示启动第 $i$ 台是安全的。
- `Already on`，表示第 $i$ 台在询问之前就已经启动了。
- `Conflict with j`，表示第 $i$ 台与前面已经启动的第 $j$ 台冲突。如果前面有多台对撞机跟 $i$ 冲突，那么只输出其中任何一台即可。

如果询问为 `- i`（表示关闭第 $i$ 台对撞机），程序应该按照下面两种情况之一输出结果。

- `Success`，表示关闭第 $i$ 台对撞机。
- `Already off`，表示第 $i$ 台对撞机在询问之前就已经关闭了。

inputFormat:
第一行输入两个以空格隔开的整数 $n$ 和 $m$，分别表示对撞机的数量和询问数。

接下来 $m$ 行，表示询问，每行仅可能是 `+ i` 或 `- i`，表示开启或关闭第 $i$ 台对撞机。

outputFormat: 输出 $m$ 行，输出结果按照上面题目给定格式输出。

samples:
Success
Conflict with 6
Success
Already off
Success
Success
Success
Success
Conflict with 3
Already on

hint:
**数据范围**

$1 \le n,m \le 10^5$，$1 \le i \le n$。

---

感谢 @cn：苏卿念 提供 Special Judge


title: 回文串计数

description:
小 $a$ 虽然是一名理科生，但他常常称自己是一名真正的文科生。不知为何，他对于背诵总有一种莫名其妙的热爱，这也促使他走向了以记忆量大而闻名的生物竞赛。然而，他很快发现这并不能满足他热爱背诵的心，但是作为一名强大的 OIER，他找到了这么一个方法——背诵基因序列。然而这实在是太困难了，小啊感觉有些招架不住。

不过他发现，如果他能事先知道这个序列里有多少对互不相交的回文串，他或许可以找到记忆的妙法。为了进一步验证这个想法，小 $a$ 决定选取一个由小写字母构成的字符串 $SS$ 来实验。由于互不相关的回文串实在过多，他很快就数晕了。不过他相信，在你的面前这个问题不过是小菜一碟。

1. 对于字符串 $SS$，设其长度为 Len，那么下文用 $S_i$ 表示 $SS$ 中第 $i$ 个字符（$1 \le i \le Le_n$）。

2. $S[i,j]$ 表示 $SS$ 的一个子串，$S[i,j]=S_i S_{i+1}S_{i+2} \cdots S_{j-2}S_{j-1}S_{j}$，比如当 $SS$ 为 `abcgfd` 时，$S[2,5]$ 就是 `bcgf`，$S[1,5]$ 是 `abcgf`。

3. 当一个串被称为一个回文串当且仅当将这个串反写后与原串相同，如`abcba`。

4. 考虑一个四元组 $(l,r,L,R)$，当 $S[l,r]$ 和 $S[L,R]$ 均为回文串时，且满足 $1 \le l \le r<L \le R \le \text{Len}$ 时，我们称 $S[l,r]$ 和 $S[L,R]$ 为一对互不相交的回文串。即本题所求，也即为这种四元组的个数。两个四元组相同当且仅当对应的 $l,r,L,R$ 都相同。

inputFormat:
输入仅一行，为字符串 $SS$，保证全部由小写字母构成，由换行符标志结束。

$50$ ％的数据满足 $SS$ 的长度不超过 $200$；

$100$ ％的数据满足 $SS$ 的长度不超过 $2000$。

outputFormat: 仅一行，为一个整数，表示互不相关的回文串的对数。

hint:
【样例数据说明】

SS="aaa"，SS 的任意一个字符串均为回文串，其中总计有 5 对互不相关的回文串：

(1,1,2,2)，(1,1,2,3)，(1,1,3,3)，(1,2,3,3)，(2,2,3,3)。


title: [COCI 2011/2012 #5] EKO / 砍树

description:
伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$（米），伐木机升起一个巨大的锯片到高度 $H$，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。

inputFormat:
第 $1$ 行 $2$ 个整数 $N$ 和 $M$，$N$ 表示树木的数量，$M$ 表示需要的木材总长度。

第 $2$ 行 $N$ 个整数表示每棵树的高度。

outputFormat: $1$ 个整数，表示锯片的最高高度。

hint: 对于 $100\%$ 的测试数据，$1\le N\le10^6$，$1\le M\le2\times10^9$，树的高度 $\le 4\times 10^5$，所有树的高度总和 $>M$。


title: 快速求和

background:
2023-10-08 update: 新增两组 hack。

2023-12-16 update: 新增两组 hack。

description:
给定一个数字字符串，用最小次数的加法让字符串等于一个给定的目标数字。每次加法就是在字符串的某个位置插入一个加号。在里面要的所有加号都插入后，就像做普通加法那样来求值。

例如，考虑字符串`12`，做 $0$ 次加法，我们得到数字 $12$。如果插入 $1$ 个加号，我们得到 $3$，因此，这个例子中，最少用 $1$ 次加法就得到数字 $3$。

再举一例，考虑字符串`303`和目标数字 $6$，最佳方法不是`3+0+3`。而是`3+03`。能这样做是因为一个数的前导 $0$ 不会改变它的大小。

inputFormat:
第一行：一个字符串 $s$。

第二行：一个整数 $n$。

outputFormat: 一行一个整数表示最少的加法次数让 $s$ 等于 $n$。如果怎么做都不能让 $s$ 等于 $n$ ，则输出 $-1$。

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

对于 $100\%$ 的数据，保证 $1\le \operatorname{len}(s)\le40$，$1 \leq n\le10^5$。


title: 佳佳的魔法药水

background: 发完了 $k$ 张照片，佳佳却得到了一个坏消息：他的 MM 得病了！佳佳和大家一样焦急万分！治好 MM 的病只有一种办法，那就是传说中的 $0$ 号药水…… 怎么样才能得到 $0$ 号药水呢？你要知道佳佳的家境也不是很好，成本得足够低才行……

description:
**存在 ab 相同 c 不同的情况，与题意相悖**。题还是可以做，但数据待修正。

得到一种药水有两种方法：可以按照魔法书上的指导自己配置，也可以到魔法商店里去买——那里对于每种药水都有供应，虽然有可能价格很贵。在魔法书上有很多这样的记载：

$1$ 份 A 药水混合 $1$ 份 B 药水就可以得到 $1$ 份 C 药水。（至于为什么 $1 + 1 = 1$，因为……这是魔法世界）好了，现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及魔法书上所有的配置方法，现在要问的就是：

1. 最少花多少钱可以配制成功这种珍贵的药水；

2. 共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为不同的）。假定初始时你手中并没有任何可以用的药水。

inputFormat:
第一行有一个整数 $N$（$N \le 1000$），表示一共涉及到的药水总数。药水从 $0 \sim N-1$ 顺序编号，$0$ 号药水就是最终要配制的药水。

第二行有 $N$ 个整数，分别表示从 $0 \sim N-1$ 顺序编号的所有药水在魔法商店的价格（都表示 $1$ 份的价格）。

第三行开始，每行有三个整数 A、B、C，表示 $1$ 份 A 药水混合 $1$ 份 B 药水就可以得到 $1$ 份 C 药水。注意，某两种特定的药水搭配如果能配成新药水的话，那么结果是唯一的。也就是说不会出现某两行的 A、B 相同但 C 不同的情况。

输入以一个空行结束。

outputFormat:
输出两个用空格隔开的整数，分别表示得到 $0$ 号药水的最小花费以及花费最少的方案的个数。

保证方案数不超过 $2^{63} - 1$。

hint:
数据范围：

每一种药水的价格均 $\ge 1$ 且 $\le 2.8\times 10^4$。

样例说明：

最优方案有 $3$ 种，分别是：

- 直接买 $0$ 号药水；
- 买 $4$ 号药水、$5$ 号药水配制成 $1$ 号药水，直接买 $2$ 号药水，然后配制成 $0$ 号药水；
- 买 $4$ 号药水、$5$ 号药水配制成 $1$ 号药水，买 $3$ 号药水、$6$ 号药水配制成 $2$ 号药水，然后配制成 $0$ 号药水。


title: 开灯

background:
该题的题目是不是感到很眼熟呢?

事实上，如果你懂的方法，该题的代码简直不能再短。

但是如果你不懂得呢？那。。。（自己去想）

description:
首先所有的灯都是关的（注意是关！），编号为 $1$ 的人走过来，把是 $1$ 的倍数的灯全部打开，编号为 $2$ 的人把是 $2$ 的倍数的灯全部关上，编号为 $3$ 的人又把是 $3$ 的倍数的灯开的关上，关的开起来……直到第 $N$ 个人为止。

给定 $N$，求 $N$ 轮之后，还有哪几盏是开着的。

inputFormat: 一个数 $N$，表示灯的个数和操作的轮数。

outputFormat: 若干数，表示开着的电灯编号。

hint:
**【数据范围】**

对于 $100 \%$ 的数据，$1 \le N \le 2^{40}$。

**【其他说明】**

数学题！


title: [HAOI2012] 音量调节

description:
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。输入文件中整数 $beginLevel$，代表吉他刚开始的音量，整数 $maxLevel$，代表吉他的最大音量。音量不能小于 $0$ 也不能大于 $maxLevel$。输入中还给定了 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

inputFormat:
第一行依次为三个整数 $n$，$beginLevel$ 和 $maxLevel$。

第二行依次为 $n$ 个整数 $c_1,c_2,c_3,\cdots,c_n$。

outputFormat: 输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 $0$ 或者高于 $maxLevel$，输出 `-1`。

hint: $1\le n\le 50$，$1\le c_i\le beginLevel$，$1\le maxLevel\le 1000$，$0\le beginLevel\le maxLevel$。


title: 舞蹈课

description:
有 $n$ 个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为 `ABCD`，那么 `BC` 出列之后队伍变为 `AD`）。舞蹈技术相差最小即是 $a_i$ 的绝对值最小。

任务是模拟以上过程，确定跳舞的配对及顺序。

inputFormat:
第一行一个正整数 $n$ 表示队伍中的人数。

第二行包含 $n$ 个字符 `B` 或者 `G`，`B` 代表男，`G` 代表女。

第三行为 $n$ 个整数 $a_i$。所有信息按照从左到右的顺序给出。

outputFormat:
第一行一个整数表示出列的总对数 $k$。

接下来 $k$ 行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右 $1$ 至 $n$ 编号）。请先输出较小的整数，再输出较大的整数。


title: [USACO06NOV] Corn Fields G

description:
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12, 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

农场主 $\rm John$ 新买了一块长方形的新牧场，这块牧场被划分成 $M$ 行 $N$ 列 $(1 \le M \le 12, 1 \le  N \le 12)$，每一格都是一块正方形的土地。 $\rm John$ 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 $\rm John$ 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

$\rm John$ 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

inputFormat:
第一行：两个整数 $M$ 和 $N$，用空格隔开。

第 $2$ 到第 $M+1$ 行：每行包含 $N$ 个用空格隔开的整数，描述了每块土地的状态。第 $i+1$ 行描述了第 $i$ 行的土地，所有整数均为 $0$ 或 $1$ ，是 $1$ 的话，表示这块土地足够肥沃，$0$ 则表示这块土地不适合种草。

outputFormat: 一个整数，即牧场分配总方案数除以 $100,000,000$ 的余数。


title: [NOI1995] 石子合并

description:
在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 $N$ 堆石子合并成 $1$ 堆的最小得分和最大得分。

inputFormat:
数据的第 $1$ 行是正整数 $N$，表示有 $N$ 堆石子。

第 $2$ 行有 $N$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆石子的个数。

outputFormat: 输出共 $2$ 行，第 $1$ 行为最小得分，第 $2$ 行为最大得分。

hint: $1\leq N\leq 100$，$0\leq a_i\leq 20$。


title: 绳子对折

description:
FJ 有一个长度为 $L$（$1 \le L \le 10,000$）的绳子。这个绳子上有 $N$（$1 \le N \le 100$）个结，包括两个端点。$FJ$ 想将绳子对折，并使较短一边的绳子上的结与较长一边绳子上的结完全重合，如图所示：

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

找出FJ有多少种可行的折叠方案。

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

第 $2$ 至 $N+1$ 行：每一行包含一个整数表示一个结所在的位置，总有两个数为 $0$ 和 $L$。

outputFormat: 第一行： 一个整数表示FJ可折叠的方案数。


title: 接力赛跑

description:
$N (1\le N\le 1000)$ 只奶牛（编号为 $1$ 到 $N$）在进行一个特别的接力赛跑，这个比赛特别之处在于，若干只奶牛可以同时跑。

在 $t=0$ 时刻，牛 $1$ 开始沿着跑道跑。

通常，牛 $i$ 跑完一圈需要的时间为 $L_i (1\le L_i\le 1000)$ 秒。当它重新越过起点线的瞬间，它会通知另外 $M_i (1\le M_i\le N)$ 只奶牛 $A_{ij} (1\le j\le M_i)$ 起跑。注意可能出现 $M_i=0$ 并且 $A_i$ 不存在的情况。

每一只开始赛跑的奶牛，等到它回到起点时，都会通知其他奶牛起跑。可能出现多只奶牛通知同一只奶牛起跑的情况，但是每一只奶牛只愿意跑一圈，所以它被第二次叫到的时候就不愿意再跑了。

农场主希望你帮他确定总的赛跑时间（也就是从比赛开始到最后一只奶牛越过终点的时间）。

inputFormat:
第一行一个整数 $N$，表示参赛的牛的数量。

第 $2$ 行到第 $N+1$ 行：第 $i+1$ 行包含多个用空格隔开的整数：$L_i$、$M_i$ 和 $M_i$ 个整数 $A_{ij}$。

outputFormat: 一个整数，表示整个比赛结束的时间。


title: 【模板】三分 | 函数

description: 给定 $n$ 个二次函数 $f_1(x),f_2(x),\dots,f_n(x)$（均形如 $ax^2+bx+c$），设 $F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}$，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

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

每组数据第一行一个正整数 $n$，接着 $n$ 行，每行 $3$ 个整数 $a,b,c$，用来表示每个二次函数的 $3$ 个系数，注意二次函数有可能退化成一次。

outputFormat: 每组数据输出一行，表示 $F(x)$ 的在区间 $[0,1000]$ 上的最小值。答案精确到小数点后四位，四舍五入。


title: [USACO12FEB] Overplanting S

description:
Farmer John has purchased a new machine that is capable of planting grass within any rectangular region of his farm that is "axially aligned" (i.e., with vertical and horizontal sides).  Unfortunately, the machine malfunctions one day and plants grass in not one, but N (1 <= N <= 1000) different rectangular regions, some of which may even overlap.

Given the rectangular regions planted with grass, please help FJ compute the total area in his farm that is now covered with grass.

在一个笛卡尔平面坐标系里（则 $X$ 轴向右是正方向，$Y$ 轴向上是正方向），有 $N\ (1 \le N \le 1000)$ 个矩形，第 $i$ 个矩形的左上角坐标是 $(x_1,y_1)$，右下角坐标是 $(x_2,y_2)$。问这 $N$ 个矩形所覆盖的面积是多少？

注意：被重复覆盖的区域的面积只算一次。

inputFormat:
第一行，一个整数 $N\ (1 \le N \le 1000)$。

接下来有 $N$ 行，每行描述一个矩形的信息，分别是矩形的 $x_1,y_1,x_2,y_2(-10^8 \le x_1,y_1,x_2,y_2 \le 10^8)$。

outputFormat: 一个整数，被 $N$ 个矩形覆盖的区域的面积。


title: Moo

description:
奶牛 Bessie 最近在学习字符串操作，它用如下的规则逐一的构造出新的字符串：

$S(0) =$ `moo`

$S(1) = S(0) +$ `m` $+$ `ooo` $+ S(0) =$ `moo` $+$ `m` $+$ `ooo` $+$ `moo` $=$ `moomooomoo`

$S(2) = S(1) +$ `m` $+$ `oooo` $+ S(1) =$ `moomooomoo` $+$ `m` $+$ `oooo` $+$  `moomooomoo` $=$ `moomooomoomoooomoomooomoo`

$\dots$

Bessie 就这样产生字符串，直到最后产生的那个字符串长度不小于读入的整数 $N$ 才停止。

通过上面观察，可以发现第 $k$ 个字符串是由：第 $k-1$ 个字符串 $+$ `m` $+$  $(k+2$ 个 $o) +$ 第 $k-1$ 个字符串连接起来的。

现在的问题是：给出一个整数 $N (1 \leq N \leq 10^9)$，问第 $N$ 个字符是字母 `m` 还是 `o`？

inputFormat: 一个正整数 $N$。

outputFormat: 一个字符，`m` 或者 `o`。

hint:
样例解释：

由题目所知：字符串 $S(0)$ 是 `moo`, 现在要求第 $11$ 个字符，显然字符串 $S(0)$ 不够长；

同样 $S(1)$ 的长度是 $10$，也不够长；$S(2)$ 的长度是 $25$，够长了，$S(2)$ 的第 $11$ 个字符是 `m`，所以答案就输出 `m`。


title: 滑动窗口 /【模板】单调队列

description:
有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 $[1,3,-1,-3,5,3,6,7]$ 以及 $k = 3$，有如下过程：

$$\def\arraystretch{1.2}
\begin{array}{|c|c|c|}\hline
\textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline
\verb![1   3  -1] -3   5   3   6   7 ! & -1 & 3 \\ \hline
\verb! 1  [3  -1  -3]  5   3   6   7 ! & -3 & 3 \\ \hline
\verb! 1   3 [-1  -3   5]  3   6   7 ! & -3 & 5 \\ \hline
\verb! 1   3  -1 [-3   5   3]  6   7 ! & -3 & 5 \\ \hline
\verb! 1   3  -1  -3  [5   3   6]  7 ! & 3 & 6 \\ \hline
\verb! 1   3  -1  -3   5  [3   6   7]! & 3 & 7 \\ \hline
\end{array}
$$

inputFormat:
输入一共有两行，第一行有两个正整数 $n,k$。
第二行 $n$ 个整数，表示序列 $a$

outputFormat:
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值


title: 三角函数

description: 输入一组勾股数 $a,b,c（a\neq b\neq c）$，用分数格式输出其较小锐角的正弦值。（要求约分。）

inputFormat: 一行，包含三个正整数，即勾股数 $a,b,c$（无大小顺序）。

outputFormat: 一行，包含一个分数，即较小锐角的正弦值

hint: 数据保证：$a,b,c$ 为正整数且 $\in [1,10^9]$。


title: 士兵站队

description:
在一个划分成网格的操场上，$n$ 个士兵散乱地站在网格点上，由整数坐标 $(x,y)$ 表示。

士兵们可以沿网格边上、下左右移动一步，但在同时刻任一网格点上只能有 1 名士兵。

按照军官的命令，他们要整齐地列成一个水平队列，即排成队列，即排成 $(x,y),(x+1,y),\ldots,(x+n-1,y)$。请求出如何选择 $x$ 和 $y$ 的值才能使士兵们以最少的总移动步数排成一列。

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

第 $2$ 到 $(n + 1)$ 行，每行 $2$ 个整数，第 $(i + 1)$ 行的整数 $x_i, y_i$ 代表第 $i$ 个士兵的坐标。

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


title: gcd区间

description:
给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

$m$ 次询问，每次询问给定一个区间 $[l,r]$，输出 $a_l,a_{l+1},\dots,a_r$ 的最大公因数。

inputFormat:
第一行两个整数 $n,m$。
第二行 $n$ 个整数表示 $a_1,a_2,\dots,a_n$。
以下 $m$ 行，每行两个整数 $l, r$ 表示询问区间的左右端点。

outputFormat: 共 $m$ 行，每行表示一个询问的答案。


title: 疯狂 LCM

background: 众所周知，czmppppp 是数学大神犇。一天，他给众蒟蒻们出了一道数论题，蒟蒻们都惊呆了。

description:
给定 $n$，求

$$\sum_{i = 1}^n \operatorname{lcm}(i, n)$$

其中 $\operatorname{lcm}(i, j)$ 表示 $i$ 和 $j$ 的最小公倍数。

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

输入的第一行是一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行一个整数，表示一组数据的 $n$。

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

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

- 对于 $30\%$ 的数据，保证 $T \leq 5$，$n \leq 10^5$。
- 对于 $100\%$ 的数据，$1 \leq T \leq 3 \times 10^5$，$1 \leq n \leq 10^6$。


title: [BOI2003] 团伙

description:
现在有 $n$ 个人，他们之间有两种关系：朋友和敌人。我们知道：

- 一个人的朋友的朋友是朋友
- 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

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

第二行输入一个整数 $m$ 表示接下来要列出 $m$ 个关系。

接下来 $m$ 行，每行一个字符 $opt$ 和两个整数 $p,q$，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 $opt$ 有两种可能：

- 如果 $opt$ 为 `F`，则表明 $p$ 和 $q$ 是朋友。
- 如果 $opt$ 为 `E`，则表明 $p$ 和 $q$ 是敌人。

outputFormat: 一行一个整数代表最多的团体数。


title: 山峰暸望

description:
一天，Bessie 在眺望美丽的威斯康星的群山的时候，她突然产生了疑问：哪座山是最宽的？

她决定在地平线上，利用她的新式大量程山峰高度测量仪依次做 $N$（$1 \le N \le 10,000$）次高度测量，每次的高度值为 $H_i$（$1 \le H_i \le 1,000,000,000$）。

一座山定义为一段连续的高度序列，序列中的高度一开始单调上升（或者不变），然后单调下降（或者不变）。举例来说，$2, 3, 3, 5, 4, 4, 1$ 这一段高度序列就是一座山。如果在她的视线范围内有一段单调上升或者单调下降的序列，也算是一座山。注意，两座山之间可能会有部分重叠。

山的宽度定义为在这个山上进行的测量的次数（也就是序列的长度）。例如序列 $2, 3, 3, 5, 4, 4, 1$ 的宽度为 $7$。

请帮 Bessie 找到最宽的山。

下图是一个比较典型的的例子：

```plain
           *******                   *
          *********                  ***
          **********                *****
          ***********            *********               *
*      *****************       ***********             *** *
**    *******************     *************   * *     *******      *
**********************************************************************  山的形状
3211112333677777776543332111112344456765432111212111112343232111111211  高度值
aaaaa                    ccccccccccccccccccccc eeeeeee ggggggggg
  bbbbbbbbbbbbbbbbbbbbbbbbbbbb             ddddd          ffffffffff
                                                             hhhhhhhhh  山的编号
```

山标记为 `a`、`b` 等等。显然，山 `b` 有着最大的宽度，宽度为 $28$。

inputFormat:
第一行包含一个单独的整数 $N$，表示高度测量的次数。

接下来的 $N$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次测量的高度值 $H_i$。

outputFormat: 仅一行，包含一个单独的整数，表示最宽的山的宽度。

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

在最宽的山处测量到的高度为 $2, 3, 5, 4, 1$。其他的山包括 $3, 2$ 和 $1, 6$。

---

**【提示】**

如果你知道一座山的最高的部分（也就是山峰），你会发现，找到这座山的宽度是很容易的哦。


title: [USACO4.2] 完美的牛栏The Perfect Stall

description:
农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。

不幸的是，由于工程问题，每个牛栏都不一样。

第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。

上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。

一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。

给出奶牛们的爱好的信息，计算最大分配方案。

inputFormat:
第一行为两个整数，$n$ 和 $m$。$n$ 是农夫约翰的奶牛数量，$m$ 是新牛棚的牛栏数量。

第二行到第 $n+1$ 行 一共 $n$ 行，每行对应若干个整数一只奶牛。第一个数字 $s_i$ 是这头奶牛愿意在其中产奶的牛栏的数目。后面的 $s_i$ 个数表示这些牛栏的编号。牛栏的编号限定在区间 $[1,m]$ 中，在同一行，一个牛栏不会被列出两次。

outputFormat: 只有一行，为一个整数，表示最多能分配到的牛栏的数量。

hint: $0\le n,m\le 200$，$0\le s_i\le m$。


title: 数字序列

description:
定义函数 $\mathrm{tostring}(n)$ 表示将数字 $n$ 按照 $10$ 进制写成字符串。例如，$\mathrm{tostring}(12345)={\tt 12345}$。由此，

- 定义字符串 $S_n={\tt 1+2+3+4+\cdots}+\mathrm{tostring}(n)$；
- 定义字符串 $S_{\infin}=S_1+S_2+S_3+S_4+\cdots$

例如，$S_{\infty}$ 的前若干项为：

$$\tt 112123123412345123456123456712345678123456789123456789101234567891011\cdots$$

现在询问 $S_{\infin}$ 的第 $i$ 位是什么字符。

inputFormat:
第一行为正整数 $t\ (1 \le t \le 10)$，表示测试数据组数。

接下来 $t$ 行，每行一个正整数 $i\ (1 \le i \le 2^{31}-1)$，表示一次询问。

outputFormat: 对于每一个 $i$，输出对应位置上的数字。


title: [SCOI2005] 互不侵犯

description: 在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

inputFormat: 只有一行，包含两个数 $N,K$。

outputFormat: 所得的方案数

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

对于全部数据，$1 \le N \le 9$，$0 \le K \le N\times N$。

---

$\text{upd 2018.4.25}$：数据有加强。


title: 电梯里的尴尬

background: 木有……

description:
细心的同学发现，小W最近喜欢乘电梯上上下下，究其原因，也许只有小W自己知道：在电梯里经常可以遇到他心中的OI大神 lxl。

电梯其实是个很神奇的地方，只有在电梯里，小W才有勇气如此近距离接近大神，虽然觉得有点不自在，但次数多了，大神也习惯了小W的存在，甚至熟悉到仿佛不说上句话自己也都觉得不合适了。可是，他们的谈话也仅仅限于今天天气不错啊或是你吃了吗之类的，往往在对方微笑点头后就再次陷入难堪的沉默之中。 于是，小W便在搭讪大神的同时，也关注着电梯中显示的楼层数字，并且他注意到电梯每向上运行一层需要 $6$ 秒钟，向下运行一层需要 $4$ 秒钟，每开门一次需要 $5$ 秒（如果有人到达才开门），并且每下一个人需要加 $1$ 秒。

特别指出，电梯最开始在 $0$ 层，并且最后必须再回到 $0$ 层才算一趟任务结束。假设在开始的时候已知电梯内的每个人要去的楼层，你能计算出完成本趟任务需要的总时间吗?

这是个很简单的问题，要知道，小W已经修炼到快速心算出结果的境界，现在你来编程试试吧！

inputFormat:
共 $2$ 行

第 $1$ 行，一个正整数 $n$，表示乘坐电梯的人数。

第 $2$ 行，$n$ 个正整数，$a_{i}$ 表示第 $i$ 个人要去的楼层。

outputFormat: 仅 $1$ 行，一个正整数，表示完成这趟任务需要的时间。


title: 缘分计算

background:
缘分是一个外国人难以理解的中文名词。大致说来，缘分是一种冥冥中将两人（通常是情人）结合的力量。仅管这是种迷信，很多人——特别是女生——喜欢去计算它。

不幸的是，644 也是这样。有天，她问 DL：“甜心，可以算一下我们的缘分吗？”唉，DL 真的很讨厌这问题，但他无法拒绝。还好，DL 是个程序设计师，所以他只要找到一个看来不错的算法并写成一个缘分计算器就可以了。在网络上搜寻了几个小时后，他决定采用以下的缘分算法：

description:
第一步：取出姓名的缩写（abbreviation）并接在一起。例如，如果这对恋人叫 JiangYunFan 和 TangYuRou，他们的缩写就是 JYFTYR。第二步：将每个字母用数字字符串取代。用 $\mathrm{ST}$ 来取代 $\tt A$，$\mathrm{ST}+1$ 来取代 $\tt B$，$\mathrm{ST}+2$ 来取代 $\tt C$，……，$\mathrm{ST}+25$ 来取代 $Z$，其中 $\mathrm{ST}$ 为一个已知的正整数。例如，如果 $\mathrm{ST}=81$，$\tt A$ 就被 $81$ 取代，$\tt B$ 就被 $82$ 取代，……，$\tt Z$ 则被 $106$ 取代。上面的例子 JYFTYR 则被 $901058610010598$ 取代。

第三步：重复以下操作：将相邻的两位数相加，并写下和的个位数。不难发现这个操作每进行一次，这个数字字符串就会少一位数。当这个数字变成 $100$ 或不超过两位数（第一位是 $0$ 也算两位数）时，这个程序便停止。所得的数字就是两人的缘分。用上面的例子来说，处理的过程如下：

- $901058610010598$；
- $91153471011547$；
- $0268718112691$；
- ……
- $374$；
- $01$。

所以如果 $\mathrm{ST}=81$，JiangYunFan 和 TangYuRou 的缘分便只有 $1$。

惨了！DL 很了解 644。他知道即使这个程序计算出的缘分高达 $99$ 她仍然会不高兴。更何况 644 还对其余很多对恋人间的缘分感兴趣，要是他一个个计算会太繁琐。如果告诉你一对恋人的姓名和一个 $\mathrm{ST}$ 值，你能编一个程序算出他们的缘分吗？

inputFormat:
第一行包含一个仅含大写字母且长度为 $L$ 的字符串。

第二行包含一个正整数 $\mathrm{ST}$，含义如题目所述。

outputFormat: 输出仅一行，包含一个整数，表示两人的缘分。

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

对于 $100\%$ 的数据，$4 ≤ L ≤ 10$，$1 ≤ \mathrm{ST} ≤ 10000$。

### 注意

如果你和你的恋人的缘分不是 $100$，不要伤心。这没有什么大不了的。


title: 魔法物品

description:
有两种类型的物品：普通物品和魔法物品。普通物品没有魔法属性，而魔法物品拥有一些魔法属性。每种普通物品有一个价值 $P$，但每种魔法物品有两种价值：鉴定前的价值 $P_1$ 和鉴定后的价值 $P_2$（当然，$P_2$ 总是大于 $P_1$）。

为了鉴定一个魔法物品，你需要购买一个鉴定卷轴，用它来鉴定魔法物品。鉴定完一件魔法物品以后，鉴定卷轴便会消失。每个鉴定卷轴将会消耗 $P_i$ 元钱。如果没有足够的钱，你将无法购买任何鉴定卷轴。
现在，你正在一个集市中，同时拥有很多物品。你知道每件物品的价值并且想要出售全部物品。那么，你最多能够获得多少钱呢？

你可以假定：

- 开始的时候你没有钱。
- 所有的魔法物品都还没有被鉴定。
- 只要你有足够的钱，你可以购买任意多的鉴定卷轴。

inputFormat:
第一行有两个整数 $N$ 和 $P_i$（$1 \le P_i \le 5000$），表示你拥有的物品数和一个鉴定卷轴的价格。
接下来 $N$ 行，每行给出一件物品的价格。
对于每件普通物品行仅有一个整数 $P$（$1 \le P \le 10000$）。
对于每件魔法物品,那一行将会有两个整数 $P_1$ 和 $P_2$（$1 \le P_1 < P_2 \le 10000$）。

outputFormat: 输出一个整数表示你最多能够获得多少钱。


title: 自我数

background: #题目有加强

description: 在 1949 年印度数学家 D. R. Daprekar 发现了一类称作 Self-Numbers 的数。对于每一个正整数 $n$，我们定义 $d(n)$ 为 $n$ 加上它每一位数字的和。例如， $d(75) = 75 + 7 + 5 = 87$。给定任意正整数 $n$ 作为一个起点，都能构造出一个无限递增的序列：$n, d(n), d(d(n)), d(d(d(n))), \ldots$ 例如，如果你从 $33$ 开始，下一个数是 $33 + 3 + 3 = 39$，再下一个为 $39 + 3 + 9 = 51$，再再下一个为 $51 + 5 + 1 = 57$，因此你所产生的序列就像这样：$33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, \ldots$。数字 $n$ 被称作 $d(n)$ 的发生器。在上面的这个序列中，$33$ 是 $39$ 的发生器，$39$ 是 $51$ 的发生器，$51$ 是 $57$ 的发生器等等。有一些数有超过一个发生器，如 $101$ 的发生器可以是 $91$ 和 $100$。一个没有发生器的数被称作 Self-Number。如前 $13$ 个 Self-Number 为 $1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97$。我们将第 $i$ 个 Self-Number 表示为 $a_i$，所以 $a_1 = 1, a_2 = 3, a_3 = 5, \ldots$。

inputFormat: 输入包含整数 $N, K, s_1, \ldots, s_K$，其中 $1 \le N \le {10}^7$、$1 \le K \le 5000$，以空格和换行分割。

outputFormat: 在第一行你需要输出一个数，这个数表示在闭区间 $[1, N]$ 中 Self-Number 的数量。第二行必须包含以空格划分的 $K$ 个数，表示 $a_{s_1}, \ldots, a_{s_K}$，这里保证所有的 $a_{s_1}, \ldots, a_{s_K}$ 都小于 $N$。（例如，如果 $N = 100$，$s_k$ 可以为 $1 \sim 13$，但不能为 $14$，因为 $a_{14} = 108 > 100$）


title: 发射站

description:
某地有 $N$ 个能量发射站排成一行，每个发射站 $i$ 都有不相同的高度 $H_i$，并能向两边（两端的发射站只能向一边）同时发射能量值为 $V_i$ 的能量，发出的能量只被两边**最近的且比它高**的发射站接收。显然，每个发射站发来的能量有可能被 $0$ 或 $1$ 或 $2$ 个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

inputFormat:
第 $1$ 行一个整数 $N$。

第 $2$ 到 $N+1$ 行，第 $i+1$ 行有两个整数 $H_i$ 和 $V_i$，表示第 $i$ 个发射站的高度和发射的能量值。

outputFormat: 输出仅一行，表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。


title: 刺杀大使

description:
某组织正在策划一起对某大使的刺杀行动。他们来到了使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前的防御迷阵。

迷阵由 $n\times m$ 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 $n$ 行的 $m$ 个房间里有 $m$ 个机关，这些机关必须全部打开才可以进入大使馆。而第 $1$ 行的 $m$ 个房间有 $m$ 扇向外打开的门，是迷阵的入口。除了第 $1$ 行和第 $n$ 行的房间外，每个房间都被使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 $i$ 行第 $j$ 列 造成的伤害值为 $p_{i,j}$（第 $1$ 行和第 $n$ 行的 $p$ 值全部为 $0$）。

现在某组织打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选 择任意多的人从任意的门进入，但必须到达第 $n$ 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。

inputFormat:
第一行有两个整数 $n,m$，表示迷阵的大小。

接下来 $n$ 行，每行 $m$ 个数，第 $i$ 行第 $j$ 列的数表示 $p_{i,j}$。

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


title: [国家集训队] 数颜色 / 维护队列

description:
墨墨购买了一套 $N$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

1. $Q\ L\ R$ 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。

2. $R\ P\ C$ 把第 $P$ 支画笔替换为颜色 $C$。

为了满足墨墨的要求，你知道你需要干什么了吗？

inputFormat:
第 $1$ 行两个整数 $N$，$M$，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第 $2$ 行 $N$ 个整数，分别代表初始画笔排中第 $i$ 支画笔的颜色。

第 $3$ 行到第 $2+M$ 行，每行分别代表墨墨会做的一件事情，格式见题干部分。

outputFormat: 对于每一个 Query 的询问，你需要在对应的行中给出一个数字，代表第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。

hint:
对于30%的数据，$n,m \leq 10000$

对于60%的数据，$n,m \leq 50000$

对于所有数据，$n,m \leq 133333$

所有的输入数据中出现的所有整数均大于等于 $1$ 且不超过 $10^6$。

本题可能轻微卡常数

来源：bzoj2120

本题数据为洛谷自造数据，使用 [CYaRon](https://github.com/luogu-dev/cyaron) 耗时5分钟完成数据制作。


title: 天际线

description:
Latium 省的 Genoa 是亚平宁半岛西海岸北端的一片土地，自然资源丰富，却无人居住。你受到罗马执政官 Caesar 的委任，前往 Genoa 建立新的城市。Caesar 对这次任务的要求是在 Genoa 这片土地上建立起一座繁荣的城市，他将以此作为衡量你的表现的标准。

正在你大刀阔斧地进行城市建设的时候，Caesar 突然写信给你，说他要检查 Genoa 的建设情况。Caesar 希望知道你的城市是什么样子，但是他又非常的忙，所以他只要你描述一下城市的轮廓就可以了，他将依照城市的轮廓决定你的薪水。

怎样描述一个城市的轮廓呢？我们知道 Genoa 所有的建筑共享一个地面，你可以认为它是水平的。所有的建筑用一个三元组 $(L_i,H_i,R_i)$，其中 $L_i$ 和 $R_i$ 分别是建筑的左坐标和右坐标，$H_i$ 就是建筑的高度。在下方所示的图表中左边建筑物描述如下 $(1,11,5)$，$(2,6,7)$，$(3,13,9)$，$(12,7,16)$，$(14,3,25)$，$(19,18,22)$，$(23,13,29)$，$(24,4,28)$，右边用轮廓线的顺序$(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)$ 表示：

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

inputFormat: 在输入数据中，你将得到一系列表示建筑的三元组。在输入数据中所有建筑的坐标中的数值都是小于 $10000$ 的正整数，且至少有 $1$ 幢建筑，最多有 $5000$ 幢建筑。在输入输入中每幢建筑的三元组各占一行。三元组中的所有整数应由一个或多个空格分开。

outputFormat: 在输出数据中，你被要求给出城市的轮廓线。你可以这样来描述：对于所有轮廓线上的折点，按顺序排好，第奇数个点输出 $x$ 坐标，第偶数个点输出 $y$ 坐标，两个数之间用空格分开。


title: 堆放货物

background:
Caesar 看了你建设的城市后非常满意，提拔你担任 Genoa 的地方总督，并加薪 $50$ 第纳尔。最近他又写信给你说：Genoa 不能只靠 Rome 的财政扶持，你必须开展城市贸易增加财政收入。

在花费 $500$ 第纳尔开通了至 Capua 的商路后，来自 Capua 的船只源源不断地驶来，Genoa 急需建立一个仓库来临时存放送往 Capua 的货物。

description:
Genoa 的货物有三种：陶器，家具，大理石，共有 $n$ 个。他们的重量分别为 $1$，$2$，$3$ 个单位。现在，有 $p$ 艘 Capua 的船只在等待着仓库的货物，你应该将仓库里的货物分成 $p$ 堆，堆放规则如下：

- 同一堆中，重量从下至上应该是递减的（显然不能把大理石堆放在陶器或家具上）。
- 任意两堆重量之差不能超过 $3$ 个单位，否则会因分配过于不均发生船只间的冲突。

请你完成这个任务，给出一种可行的方案。

inputFormat:
第一行有一个整数，表示货物的个数 $n$。
第二行有一个整数，表示堆数 $p$。
第三行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个货物的重量 $a_i$。

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

输出 $p$ 行，每行若干个整数描述一堆货物，按照每堆**从下到上**的顺序列出该堆中每个货物的数量。

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

对于全部的测试点，保证 $2 \leq n \leq 10^3$，$1 \leq p \leq \lfloor\frac n 2 \rfloor$，$1 \leq a_i \leq 3$。

#### 说明

感谢 @cn：苏卿念 提供spj。

spj说明：

```
score:ouo：你的输出里面有不是'1','2','3',' ','\n','\r'的东西，具体以ASCII的第X号字符
score:pvp：你在第x组的时候装下了超过规定数量的'3'|'2'|'1'。
score:TAT：蛇皮judge没能读入到想要读入的东东(类似于你直接提交了一个puts(" / 特别特别多的空格/"))
score:qaq：你把重量为w1的货物放到了w2上面(w1>w2)在第i组的第j个货物
score:ovo：你没有装足够的x
score:qwq：你第i组和第j组的差的绝对值>3了，(要打架了)，第i组的重量和为x，第j组的重量和为y。
score:pwp：答案正确，恭喜你嘤嘤嘤
```


title: 凯撒密码

description:
在元老院的支持下，Caesar率领罗马军团进攻高卢地区。但是他的军事行动并不顺利，他急需你的支持。

一天，你突然受到Caesar从前线写来的信。为了防止敌军偷窃情报，Caesar决定用自创的密码来写这封信。但是面对满纸的乱码，你也无从下手。于是你前往元老院询问这种密码的玄机。

元老们告诉你，这是凯撒移位密码（世界上最早的加密术——编者注），解读它非常的简单：

对于明文中的每个字母，Caesar会用它后面的第t个字母代替。例如，当t=3时，字母A将变成C，字母B将变成D，……，字母Y将变成A，字母Z将变成B（假设字母表是循环的）。

这样一来，字母表：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

将变成： C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

明文：  I Need Soldiers  将加密为

密文：  K Pggf Uqnfkgtu

如此一来，需要传达的信息在外人看来就如同天书了。加上Caesar会不时更换t的值，使得密码变得更加难以捉摸。

你的任务是将Caesar的密码翻译为明文。

inputFormat:
你将得到若干段Caesar的密码，我们保证这是一句成文的英文句子。输入文件将保证小于50KB。

每个句子以一行“START”开始，下一行描述这个句子，再下一行以“END”结束。整个输入文件以“ENDOFINPUT”结束。

outputFormat:
对于每个句子，输出翻译后的明文

输出全部转为大写！

samples:
START
NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
END
START
N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ
END
START
IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ
END
ENDOFINPUT

samples:
IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME
DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

hint:
1.如果你有看过《福尔摩斯探案集》的话，请回忆“跳舞娃娃”密码破译第一步；

2.我想这些可能会对你有帮助：

e 0.1268

t 0.0978

a 0.0788

o 0.0766

i 0.0707

n 0.0706

s 0.0634

r 0.0594


title: 设计道路

description:
Caesar远征高卢回来后，对你大加赞赏，他亲自来到Genoa视察。

Genoa在你的建设下变得无比繁荣，由于财政收入的增加，你为城市修建了交通系统。古罗马的交通系统由两部分组成——Dirt Road和Rome Road。两个路口间只可能是其中一种道路。在Rome Road上可以驾驶马车，而在Dirt Road上则不行。由于修建道路是一项浩大的工程，使得你无法将整个城市用Rome Road连接起来。

现在Caesar已经到达码头，他要求去你家参观。Caesar由一个癖好，喜欢坐车而不喜欢走路。所以Caesar走Dirt Road时的不满值要比走Rome Road时大。

为了不让Caesar过于不满而罢免你的职位，请设计路线使得Caesar的不满值最小。

inputFormat: 输入数据第一行有两个实数，分别表示走Dirt Road和Rome Road一个单位长度时Caesar的不满值。接下来是一个整数N（N<=1000），代表路口总数。接下来有N行，每行一组实数(x,y)分别描述这N个路口的坐标。接下来有若干行，每行一组整数（i,j），表示第i个路口与第j个路口间为Rome Road，以0 0结束。最后两行，每行一对实数，分别描述码头和你家的坐标。

outputFormat: 输出Caesar从码头到你家的最小不满值，保留4位小数


title: 逆序对

description:
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

**Update:数据已加强。**

inputFormat:
第一行，一个数 $n$，表示序列中有 $n$个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

outputFormat: 输出序列中逆序对的数目。

hint:
对于 $25\%$ 的数据，$n \leq 2500$

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$n \leq 5 \times 10^5$

请使用较快的输入输出

应该不会 $O(n^2)$ 过 50 万吧 by chen_zhe


title: [NOIP2016 普及组] 买铅笔

background: NOIP2016 普及组 T1

description:
P 老师需要去商店买 $n$ 支铅笔作为小朋友们参加 NOIP 的礼物。她发现商店一共有 $3$ 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P 老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开，因此 P 老师可能需要购买超过 $n$ 支铅笔才够给小朋友们发礼物。

现在 P 老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 $n$ 支铅笔最少需要花费多少钱。

inputFormat:
第一行包含一个正整数 $n$，表示需要的铅笔数量。

接下来三行，每行用 $2$ 个正整数描述一种包装的铅笔：其中第 $1$ 个整数表示这种包装内铅笔的数量，第 $2$ 个整数表示这种包装的价格。

保证所有的 $7$ 个数都是不超过 $10000$ 的正整数。

outputFormat: $1$ 个整数，表示 P 老师最少需要花费的钱。

hint:
铅笔的三种包装分别是：

- $2$ 支装，价格为 $2$;
- $50$ 支装，价格为 $30$;
- $30$ 支装，价格为 $27$。

P 老师需要购买至少 $57$ 支铅笔。

如果她选择购买第一种包装，那么她需要购买 $29$ 份，共计 $2 \times 29 = 58$ 支，需要花费的钱为 $2 \times 29 = 58$。

实际上，P 老师会选择购买第三种包装，这样需要买 $2$ 份。虽然最后买到的铅笔数量更多了，为 $30 \times 2 = 60$ 支，但花费却减少为 $27 \times 2 = 54$，比第一种少。

对于第二种包装，虽然每支铅笔的价格是最低的，但要够发必须买 $2$ 份，实际的花费达到了 $30  \times 2 = 60$，因此 P 老师也不会选择。

所以最后输出的答案是 $54$。

**数据范围**

保证所有的 $7$ 个数都是不超过 $10000$ 的正整数。

**子任务**

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表：

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

上表中“整倍数”的意义为：若为 $K$，表示对应数据所需要的铅笔数量 $n$ —定是每种包装铅笔数量的整倍数（这意味着一定可以不用多买铅笔）。

于 2022 年 12 月 23 日新加 Hack 数据三组。


title: L 国的战斗之间谍

background: L 国即将与 I 国发动战争！！

description:
俗话说的好：“知己知彼，百战不殆”。L 国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

你现在有 $N$ 个人选，每个人都有这样一些数据：$A$（能得到多少资料）、$B$（伪装能力有多差）、$C$（要多少工资）。已知敌人的探查间谍能力为 $M$（即去的所有人 $B$ 的和要小于等于 $M$）和手头有 $X$ 元钱，请问能拿到多少资料？

inputFormat:
第一行三个整数 $N, M, X$ 代表总人数，敌国侦察能力和总钱数。

第二行至第 $N + 1$ 行，每行三个整数 $A_i, B_i, C_i$ 分别表示第 $i$ 个人能得到的资料，他的伪装能力有多差和他要的工资。

outputFormat: 一行一个整数表示能得到的资料总数。


title: L 国的战斗之排兵布阵

background: L 国即将与 I 国发动战争！！

description: L 国的指挥官想让他的每一个军营都呈现出国徽形——L 形（方向无所谓）。当然，他的指挥营除外（这叫做个性），他想不出该怎么排，就这样，这任务又变成了你的······

inputFormat: 一行三个数：$n$，$x$，$y$ 表示军营大小为  $2^n$，指挥营在 $(x,y)$ 的位置上。

outputFormat: $2^n$ 行，每行 $2^n$ 个数，表示军营号（按先行后列顺序）指挥营用 $0$ 表示。


title: [NOI2009] 诗人小G

description:
小 G 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方，而一个排版的不协调度为所有行不协调度的总和。

小 G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。

inputFormat:
输入文件中的第一行为一个整数 $T$，表示诗的数量。

接下来为 $T$ 首诗，这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数 $N,L,P$，其中：$N$ 表示这首诗句子的数目，$L$ 表示这首诗的行标准长度，$P$ 的含义见问题描述。

从第二行开始，每行为一个句子，句子由英文字母、数字、标点符号等符号组成（ASCII 码 $33 \sim 127$，但不包含 `-`）。

outputFormat:
于每组测试数据，若最小的不协调度不超过 $10^{18}$，则第一行为一个数，表示不协调度。接下来若干行，表示你排版之后的诗。注意：在同一行的相邻两个句子之间需要用一个空格分开。

如果有多个可行解，它们的不协调度都是最小值，则输出任意一个解均可。若最小的不协调度超过 $10^{18}$，则输出 `Too hard to arrange`。每组测试数据结束后输出 `--------------------`，共 20 个 `-`，`-` 的 ASCII 码为 45，请勿输出多余的空行或者空格。

samples:
4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet


title: L国的战斗之伞兵

background: L 国即将与 I 国发动战争！！

description: 为了在敌国渗透作战，指挥官决定：派出伞兵前往敌国！然而敌国的风十分强烈，能让伞兵在同一高度不停转悠，直到被刮到一个无风区……（可怜的小兵）

inputFormat:
第一行：$n,m$ 两个正整数，表示敌国的大小。

以下 $n$ 行，每行 $m$ 个字符，`u` 表示风向北吹；`d` 表示风向南吹；`l` 表示风向西吹；`r` 表示风向东吹；`o` 表示无风。（上北下南，左西右东)

outputFormat: 一个数：表示有几个点可以放下伞兵。

hint:
数据范围：

$1 \leq n \leq 1000$，$1 \leq m \leq 1000$。


title: 小书童——凯撒密码

background: 某蒟蒻迷上了 “小书童”，有一天登陆时忘记密码了（他没绑定邮箱 or 手机），于是便把问题抛给了神犇你。

description: 蒟蒻虽然忘记密码，但他还记得密码是由一个字符串组成。密码是由原文字符串（由不超过 50 个小写字母组成）中每个字母向后移动 $n$ 位形成的。`z` 的下一个字母是 `a`，如此循环。他现在找到了移动前的原文字符串及 $n$，请你求出密码。

inputFormat: 第一行：$n$。第二行：未移动前的一串字母。

outputFormat: 一行，是此蒟蒻的密码。

hint: 字符串长度 $\le 50$，$1 \leq n \leq 26$。


title: [NOI2010] 成长快乐

description:
Nemo 是一条无忧无虑的小鱼，它的初始体重为 $w_0$。可爱的 Nemo 希望自己能够尽快地成长，因此需要吃尽量多的食物。Nemo 最喜爱的食物是海里的小虾。

已知 Nemo 对食物的情况了解如下：大海里共有 $n$ 只小虾，从 $1$ 到 $n$ 编号，其中编号为 $i$ 的小虾的重量为 $w_i$。将大海看作一个 X-Y 坐标系，在 $0$ 时刻编号为 $i$ 的小虾所在的位置为 $(x_i, y_i)$。小虾在大海中作匀速直线运动，其中编号为 $i$ 的小虾的速度向量为 $(p_i, q_i)$，即在时刻 $t$，它的位置为 $(x_i+p_i \cdot t,y_i+q_i \cdot t)$。

Nemo 在 $0$ 时刻的位置为 $(x_0, y_0)$，它可以在海中随意移动，但速度不超过 $V$。Nemo 希望通过自己的努力，在 $T$ 个单位时间内（含 $T$ 时刻）吃到的小虾重量总和尽量大。

当 Nemo 与某只小虾同时移动到同一个位置上，且小虾的重量小于 Nemo 当时的重量，则 Nemo 可以将该小虾吃掉。当 Nemo 吃掉重量为 $w_i$ 的小虾之后，它的体重将增加 $w_i$。注意，小虾不会吃 Nemo，且小虾之间也不会自相残杀。

Nemo 希望你来帮助它制定一个成长计划，使得它吃掉的小虾重量总和尽量大。

inputFormat:
该题为提交答案型试题，所有输入数据 `nemo1.in` $\sim$ `nemo10.in` 已在试题目录下。

**[数据以及checker下载](http://pan.baidu.com/s/1dEDLQud)**

对于每个数据，输入文件中第一行为五个实数 $w_0, V, T, x_0, y_0$。分别表示 Nemo 的初始体重、最大移动速度、时间限制以及 Nemo 在 $0$ 时刻的位置。

第二行为一个整数 $n$，表示大海中小虾的只数。

接下来 $n$ 行，每行 $5$ 个实数，包括 $w_i, x_i, y_i, p_i, q_i$，分别表示编号为 $i$ 的小虾的重量、在 $0$ 时刻的位置和速度向量。

outputFormat:
针对给定的 $10$ 个输入文件 `nemo1.in` $\sim$ `nemo10.in`，你需要分别提交你的输出文件 `nemo1.in` $\sim$ `nemo10.in`。

输出文件第一行包含一个整数 $k$。表示在你的成长计划中，Nemo 将吃到 $k$ 只小虾。

第二行包含一个实数 $w$，表示在你的成长计划中，Nemo 吃到的小虾的重量总和。

接下来 $k$ 行，每行 $4$ 个数 $t, x, y, s$。表示在时刻 $t$，Nemo 在位置 $(x, y)$ 处吃掉了编号为 $s$ 的小虾。其中 $t, x, y$ 为实数，$s$ 为整数。

为保证验证程序的精度，所有实数建议至少输出到小数点后 $6$ 位。在验证程序中，两个实数绝对误差不超过 $10^{-4}$ 时，即视为相等。

hint:
### 样例解释

在这个样例中，Nemo 在时刻 $5$ 在位置 $(2, 2)$ 吃掉了 $1$ 号小虾。其实 Nemo 到达 $(2, 2)$ 的时间可以更早，但题中仅要求速度不超过 $V$ 即可。

### 评分方法

对于每组数据，我们设置了 $9$ 个评分参数 $a_{10},a_9, \ldots ,a_2$。如果选手的输出不合法，则得零分。否则，设在你的方案中，Nemo 体重的增加量为 $w_{user}$，你的分数将会由下表给出：

| 得分 |          条件          | 得分 |        条件         |
| :--: | :--------------------: | :--: | :-----------------: |
|  10  | $w_{user} \geq a_{10}$ |  5   | $w_{user} \geq a_5$ |
|  9   |  $w_{user} \geq a_9$   |  4   | $w_{user} \geq a_4$ |
|  8   |  $w_{user} \geq a_8$   |  3   | $w_{user} \geq a_3$ |
|  7   |  $w_{user} \geq a_7$   |  2   | $w_{user} \geq a_2$ |
|  6   |  $w_{user} \geq a_6$   |  1   |  $w_{user} \gt 0$   |

### checker 使用方法

在 checker 目录下，在终端输入 `./checker in out`。

其中 in 为题目提供的输入文件，out 为你对于该输入文件给出的答案文件。

校验器将只检查你的答案的合法性，结果以在线评测为准。

感谢 @FlierKing 提供 spj 以及 @虞皓翔 帮助完善 spj。


title: 三子棋II

description:
小 a 和 uim 喜欢互相切磋三子棋。三子棋大家都玩过是吗？就是在九宫格里面 $\verb!OOXX!$（别想歪了），谁连成 $3$ 个就赢了。

虽然小 a 很努力地记录棋谱，可还是下不过 uim。

由于小 a 比较愚蠢，uim 总是让他先。小 a 下的第一个子一定是在中心。

这回小 a 希望使用计策。目前棋局刚开始，棋盘上不到 $3$ 颗棋子，小 a 想知道，根据目前的局势，他有没有必胜策略（也就是自己以最佳方案下棋，无论对手怎么下，自己必胜）。

inputFormat: 共三行，表示棋局，$\verb!O!$ 表示小 a，$\verb!X!$ 表示uim，$\verb!-!$ 表示没有落子。保证棋子数不超过三个。

outputFormat:
共两行。

第一行，如果小 a 赢，输出 `xiaoa will win.`。如果小 a 必败，输出 `uim will win.`。如果不知道，输出 `Dont know.`。

第二行，输出他们已经下了几个棋子。


title: 保龄球

description:
DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。

DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。

1. $\bigcirc \bigcirc \bigcirc$

2. $\bigcirc \bigcirc \bigcirc\ \bigcirc$

3. $\bigcirc$

4. $\bigcirc\ \bigcirc$

如上图，每个 “$\bigcirc$” 代表一个瓶子。如果 DL 想要打倒 $3$ 个瓶子就在 $1$ 位置发球，想要打倒 $4$ 个瓶子就在 $2$ 位置发球。

现在他想要打倒 $m$ 个瓶子。他告诉你每个位置的瓶子数，请你给他一个发球位置。

inputFormat:
第一行包含一个正整数 $n$，表示位置数。

第二行包含 $n$ 个正整数 $a_i$ ，表示第 $i$ 个位置的瓶子数，保证各个位置的瓶子数不同。

第三行包含一个正整数 $Q$，表示 DL 发球的次数。

第四行至文件末尾，每行包含一个正整数 $m$，表示 DL 需要打倒 $m$ 个瓶子。

outputFormat: 共 $Q$ 行。每行包含一个整数，第 $i$ 行的整数表示 DL 第 $i$ 次的发球位置。若无解，则输出 $0$。


title: 【模板】高精度乘法 | A*B Problem 升级版

background: 本题数据已加强，请使用 FFT 或分治乘法。

description: 给你两个正整数 $a,b$，求 $a \times b$。

inputFormat:
第一行一个正整数，表示 $a$；
第二行一个正整数，表示 $b$。

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

hint:
【数据范围】
$1\le a,b \le 10^{1000000}$

可能需要一定程度的常数优化。
数据由 NaCly_Fish 重造


title: 成功密码

description:
void\_rank匪别人的书来看，原本想看杂志颓废的，结果不小心拿错拿成了被导师称作旁门左道的高中数学杂志《成功密码》。数学差得不行的void\_rank实在不会用数学方法处理这些奇怪的题目，于是来问你了。

求
$\sum_{i=1}^{N}\frac{x^{i}}{i}$

inputFormat: 只有一行x和N

outputFormat: 只有一行，即题面所求，保留四位小数

hint:
数据规模:

对于30%的数据：

$N\le10^{6},0<x \le 1$

对于100%的数据：

$N\le10^{18},0<x\le1$，x最多仅有4位小数位


title: 赌博游戏【数据有误】

background: 赌场是暴利的。大赌场通过游戏规则控制游戏的公平来赚钱。虽然规则看似很公平，但实际上是稍微有点不公平的，而大赌场由于客流量大，资金流量大，这点稍微的不公平就被放大到能让赌场得到很可观的收入。同时，这些个不公平有时并不是规则的不公平，而是道具不公平。比如说灌铅的骰子，它和正常骰子不一样，它投出 $Q$ 种点数的概率并不一样。有时，为了不让顾客察觉，他们每一次游戏结束后都有可能更换骰子。

description:
作弊的赌场有 $N$ 个骰子，在这个赌场可能发生了 $M$ 次游戏，每次游戏包括一个骰子投出的点数，我们并不知道这个骰子的编号，但知道第 $i$ 次游戏投出的点数 $O(i)$。

第 $i$ 个骰子投出点数 $j$ 的概率是 $A(i,j)$，用完第 $i$ 个骰子，下一次用第 $j$ 个骰子的概率为 $B(i,j)$。特别地，对于第一次游戏，用第 $i$ 个骰子的概率为 $\pi(i)$。

好奇的小 $v$ 来问你，在这个赌场发生这 $M$ 次游戏的概率。

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

第二行 $N$ 个浮点数，表示 $\pi(i)$。

第三行至 $2+N$ 行有 $N\times Q$ 个浮点数，第 $i+2$ 行 $j$ 列表示 $A(i,j)$。

第 $N+3$ 至 $2\times N+2$ 行有 $N\times N$ 个浮点数，第 $N+2+i$ 行 $j$ 列表示 $B(i,j)$。

第 $2\times N+3$ 行有 $M$ 个正整数，表示 $M$ 次游戏的结果 $O_i$，也就是每次游戏投出的点数。

outputFormat: 表示所求概率，保留四位位小数。

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

- 对于 $30\%$ 的数据：$M \le 100$，$1 \le N$，$Q \le 10$；
- 对于 $100\%$ 的数据：$1 \le M \le 1000$，$1 \le N$，$Q \le 50$。

对于矩阵 $A,B$，向量 $\pi$ 都具备概率转移的特征条件。


title: 女仆咖啡厅桌游吧

background:
小 v 带萌萌的妹妹去玩，妹妹想去女仆咖啡馆，小 v 想去桌游吧。

妹妹：“我问你个问题，答不对你就做我一天的奴隶，答对了就今天我就全部听你的。”

小 v ：“全部都听!?”

妹妹：“嘻嘻嘻，你还是回答问题吧！”

于是小 v 为了自己一天的幸福，来向你求助。

description:
小 v 所在的世界被规划成了树形结构，每一个节点上都可以建一个女仆咖啡厅或者桌游吧或者什么都不建。在确定点 $1$ 为根节点之后，规划局要求：对于每一个非叶子的节点 $i$，设它子树（包括自己）中所有的女仆咖啡厅的数量为 $cafe_i$，桌游吧数目为 $table_i$，都有 $cafe_i=table_i$。

妹妹的问题是：这颗树最多能放多少个女仆咖啡厅。

inputFormat:
输入的第一行是，一个正整数 $n$，表示世界节点数。

第 $2$ 至 $n$ 行，每行两个正整数 $u$，$v$，表示 $u$ 与 $v$ 间有一条边。

outputFormat: 只有一行，最多能放的女仆咖啡厅的个数。

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

- 对于 $30\%$ 的数据，保证 $n\le20$。
- 对于 $100\%$ 的数据，保证 $1\le n\le10^5$，$1 \leq u, v \le n$。


title: 最大划分乘积

background: 欧拉工程183题 有改动

description:
Let $N$ be a positive integer and let $N$ be split into $k$ equal parts, $r = N/k$, so that $N = r + r + ... + r$.

Let $P$ be the product of these parts, $P = r ×r × ... × r = rk$.

For example, if $11$ is split into five equal parts, $11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2$, then $P = 2.2^5 = 51.53632$.

Let $M(N) = P_{\max}$ for a given value of $N$.

It turns out that the maximum for $N = 11$ is found by splitting eleven into four equal parts which leads to $P_{max} = (11/4)^4$; that is, $M(11) = 14641/256 = 57.19140625$, which is a terminating decimal.

However, for $N = 8$ the maximum is achieved by splitting it into three equal parts, so $M(8) = 512/27$, which is a non-terminating decimal.

Let $D(N) = N$ if $M(N)$ is a non-terminating decimal and $D(N) = -N$ if $M(N)$ is a terminating decimal.

inputFormat: 输入文件仅一行为正整数 $a(5≤a≤32767)$.

translation:
将正整数 $n$ 分为 $k$ 个相等的部分 $r$，有 $r=n/k$。

令 $p=r×r×...×r=r^k$（共有 $k$ 个 $r$）。例如，将 $11$ 分为五等份，则 $p=2.2^5$。

令 $M(n)$ 为满足要求的对应 $n$ 的最大的 $p$。

当 $n=11$ 时，$M(n)=14641/256=57.19140625$，是有限小数；当 $n=8$ 时，$M(n)=512/27$，是无限小数。

若当 $M(n)$ 为无限小数时，$D(n)=n$，否则 $D(n)=-n$，求 $D(5)+D(6)+\dots +D(a)$ 的值。

输入文件仅一行，为正整数 $a(5 \le a \le 32767)$。

输出文件仅一行，表示 $D(5)+D(6)+\dots +D(a)$ 的值。


title: 小书童——刷题大军

background:
数学是火，点亮物理的灯；物理是灯，照亮化学的路；化学是路，通向生物的坑；生物是坑，埋葬学理的人。
文言是火，点亮历史宫灯；历史是灯，照亮社会之路；社会是路，通向哲学大坑；哲学是坑，埋葬文科生。——小 A

description: 小 A “刷题”十分猖狂，明目张胆地“刷题”。他现在在小书童里发现了 $n$ 样他喜欢的“题目”，每“题”都有他的需要时间，而老师布置了 $m$ 项作业，每项作业都有它的需要时间及分值，老师规定 $k$ 分以上算及格。小 A 只剩 $r$ 个单位时间，他想在及格的基础上更多地“刷题”。

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

第二行有 $n$ 个数，代表每“题”他的需要时间。

第三行有 $m$ 个数，表示每项作业它的需要时间。

第四行有 $m$ 个数，代表每项作业它的分值。

outputFormat: 一个数，代表小 A 能刷几道题。

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

对于 $100\%$ 的数据，$n\le 10$，$m\le 10$，$k\le 50$，$r\le 150$。数据保证没有不能及格的情况。


title: 防护伞

description: 据说 $2012$ 的灾难和太阳黑子的爆发有关。于是地球防卫小队决定制造一个特殊防护伞，挡住太阳黑子爆发的区域，减少其对地球的影响。由于太阳相对于地球来说实在是太大了，我们可以把太阳表面看作一个平面，中心定为 $(0,0)$。根据情报，在 $2012$ 年时，太阳表面上会产生 $N$ 个黑子区域，每个黑子视为一个点。特殊防护伞可以看作一个巨大的圆面，现在地球防卫小队决定将它的中心定位于某个黑子，然后用伞面挡住其他黑子。因为制造防护伞的材料成本特别高，所以我们希望伞面尽可能的小。

inputFormat:
第一行：一个整数 $N$，表示黑子个数。

第 $2$ 到 $N+1$ 行：每行两个整数，表示黑子的坐标 $(x,y)$。

outputFormat: 第一行：一个实数，表示伞的面积。


title: 外星密码

description: 有了防护伞，并不能完全避免 2012 的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力，小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码，才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码，外星人对于连续的若干个相同的子串 $\texttt{X}$ 会压缩为 $\texttt{[DX]}$ 的形式（$D$ 是一个整数且 $1\leq D\leq99$），比如说字符串 $\texttt{CBCBCBCB}$ 就压缩为 $\texttt{[4CB]}$ 或者$\texttt{[2[2CB]]}$，类似于后面这种压缩之后再压缩的称为二重压缩。如果是 $\texttt{[2[2[2CB]]]}$ 则是三重的。现在我们给你外星人发送的密码，请你对其进行解压缩。

inputFormat: 输入一行，一个字符串，表示外星人发送的密码。

outputFormat: 输出一行，一个字符串，表示解压缩后的结果。

hint:
【数据范围】

对于 $50\%$ 的数据：解压后的字符串长度在 $1000$ 以内，最多只有三重压缩。

对于 $100\%$ 的数据：解压后的字符串长度在 $20000$ 以内，最多只有十重压缩。保证只包含数字、大写字母、`[` 和 `]`。


title: 迷之阶梯

description:
在经过地球防卫小队的数学家连续多日的工作后，外星人发的密码终于得以破解。它 告诉我们在地球某一处的古老遗迹中，存在有对抗这次灾难的秘密武器。防卫小队立即赶 到这处遗迹。要进入遗迹，需要通过一段迷之阶梯。登上阶梯必须要按照它要求的方法， 否则就无法登上阶梯。它要求的方法有以下三个限制：

1. 如果下一步阶梯的高度只比当前阶梯高 1，则可以直接登上。

2. 除了第一步阶梯外，都可以从当前阶梯退到前一步阶梯。

3. 当你连续退下 k 后，你可以一次跳上不超过当前阶梯高度 $2^{k}$的阶梯。比如说你现 在位于第 j 步阶梯，并且是从第 j+k 步阶梯退下来的，那么你可以跳到高度不超过当前阶 梯高度+$2^{k}$的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯，由于时间紧迫，我们需要用最少的移动次数登上迷之阶梯。 请你计算出最少的移动步数。

inputFormat:
第一行：一个整数 N，表示阶梯步数。

第二行：N 个整数，依次为每层阶梯的高度，保证递增。

outputFormat: 第一行：一个整数，如果能登上阶梯，输出最小步数，否则输出-1。

hint:
【样例解释】

连续登 3 步，再后退 3 步，然后直接跳上去。

【数据范围】

对于 50%的数据：1≤N≤20。

对于 100%的数据：1≤N≤200。

对于 100%的数据：每步阶梯高度不超过 2^31-1


title: [USACO3.3] 亚瑟王的宫殿

description:
很久以前，亚瑟王和他的骑士习惯每年元旦去庆祝他们的友谊。为了纪念上述事件， 我们把这些故事看作是一个棋盘游戏。有一个国王和若干个骑士被放置在一个由许多方格 组成的棋盘上，没有两个骑士在同一个方格内。

这个例子是标准的 $8\times 8$ 棋盘。

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

国王可以移动到任何一个相邻的方格，从下图中黑子位置到下图中白子位置前提是他 不掉出棋盘之外。

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

一个骑士可以从下图中黑子位置移动到下图中白子位置(走“日”字形） 但前提是他 不掉出棋盘之外。

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

在游戏中，玩家可在每个方格上放不止一个棋子，假定方格足够大，任何棋子都不会 阻碍到其他棋子正常行动。

玩家的任务就是把所有的棋子移动到同一个方格里——用最小的步数。为了完成这个 任务，他必须按照上面所说的规则去移动棋子。另外，玩家可以选择一个骑士跟国王从他们两个相遇的那个点开始一起行动，这时他们按照骑士的行动规则行动，其他的单独骑士则自己一直走到集中点。骑士和国王一起走的时候，只算一个人走的步数。

请计算他们集中在一起的最小步数，而且玩家必须自己找出这个集中点。当然，这些 棋子可以在棋盘的任何地方集合。

inputFormat:
第一行：两个用空格隔开的整数：$R,C$ 分别为棋盘行和列的长。不超过 $26$ 列，$40$ 行。

第二行到结尾：输入文件包含了一些有空格隔开的字母 / 数字对，一行有一个或以上。第一对为国王的位置，接下来是骑士的位置。可能没有骑士，也可能整个棋盘都是骑士。行从 $1$ 开始，列从大写字母 $A$ 开始。

outputFormat: 单独一行表示棋子集中在一个方格的最小步数。

hint:
### 样例解释

他们集中在 $\tt B5$。

- 骑士 $1$：$\tt A3\to B5$（$1$ 步）。
- 骑士 $2$：$\tt A8\to C7\to B5$（$2$ 步）。
- 骑士 $3$：$\tt H1\to G3\to F5\to D4$，此时国王开始与这个骑士一起走，$\to \tt B5$（$4$ 步）
- 骑士 $4$：$\tt H8\to F7\to D6\to B5$（$3$ 步）。

$1+2+4+3=10$ 步。

题目翻译来自 NOCOW。

USACO Training Section 3.3


title: 套利

description:
套利是利用汇率差异实现货币增值。例如，1美元可以兑换0.5英镑、1英镑可以兑换10法郎、1法郎可以兑换0.21美元。接下来，一个聪明的交易商就可以从1美元开始，0.5 \* 10.0 \* 0.21 =1.05美元，获得了5%的利润。

你的任务是写一个程序，从输入文件读入汇率清单，然后决定套利是有可能的或没有可能的。

inputFormat: 输入文件包含多组数据，每组数据的第一行是一个整数n( 1<=n<=30 )。代表有多少种货币。接下来n行字符串，每行表示一种货币的名称（名称中不会出现空格）。下一行是一个整数m，约定了汇率表的长度。随后的m行中，每行有三部分组成。The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible. 每组数据之间空一行。当n=0时表示输入数据结束。

outputFormat: 第i组数据，输出Case i: 后，如果可以套利，输出Yes,否则输出No。

samples:
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0


title: A+B  A-B  A*B  A/B A%B Problem

background: 这个题目很新颖吧！！！

description:
求 $A$ 与 $B$ 的和、差、积、商、余。

**由于数据有修改，减法运算结果可能带负号**

inputFormat: 两行，每行一个数，为参与运算的两个数。

outputFormat: 五行，每行一个数，分别为 $A$ 与 $B$ 的和、差、积、商、余。

hint:
$|A|,|B| \leq 10^4$，这里表示数字的位数而不是绝对值

$ A,B > 0 $


title: [NOI2010] 旅行路线

description:
2010 年，世博会在中国上海举办，吸引了数以千万计的中外游客前来参观。暑假期间小 Z 也来到了上海世博园， 她对世博园的拥挤早有所闻，对有的展馆甚至要排上好几个小时的队才能进入也做好了充分准备，但为了使得自己的世博之旅更加顺利舒畅，小 Z 决定在游玩之前先制定一份详细的旅行路线。

小 Z 搜集到了世博园的地图，她发现从整体上看世博园是一块非常狭长的区域，而每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看成一个 $n \times m$ 的矩阵（$n \leq 3$），其中每一个格子为一个主题展馆。

由于不同展馆受到的关注度会有一些差别，因此排队时间的长短也不尽相同。小 Z 根据统计信息给每一个展馆 $(x, y)$ 标记了 $T_{x,y} = 0$ 或 $1$，如果 $T_{x,y} = 1$，表示这个展馆非常热门，需要排很长时间的队；如果 $T_{x,y} = 0$，表示这个展馆相对比较普通，几乎不需要排队即可进入参观。小 Z 希望能够制定一份合理的路线，使得能交替参观热门馆和普通馆，既不会因为总是参观热门馆而长时间在排队，也不会因为总是参观普通馆而使得游览过于平淡。同时，小 Z 办事很讲究效率，她希望在游遍所有展馆的同时，又不会走冤枉路浪费体力。因此她希望旅行路线满足以下几个限制：

1. 在参观完位于 $(x, y)$ 的展馆后，下一个参观的是一个相邻的且未被参观过的展馆 $(x^\prime, y^\prime)$，即 $|x-x^\prime|+|y-y^\prime|=1$；
2. 路线的起点位于整个矩阵的边界上，即 $x = 1$ 或 $x = n$ 或 $y = 1$ 或 $y = m$；

她制定了一个长度为 $n \times m$ 的 01 序列 $L$，她希望第 $i$ 个参观的展馆 $(x,y)$ 满足 $T_{x,y}=L_i$。

小 Z 想知道有多少条不同的旅行路线能够满足她的要求。由于最终的结果可能很大，小 Z 只想知道可行的旅行路线总数 $\bmod\space 11\,192\,869$ 的值。

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

第 2 行至第 $n+1$ 行，每行有 $m$ 个 01 整数，其中第 $i+1$ 行第 $j$ 个数表示 $T_{i,j}$。

第 $n+2$ 行有 $n \times m$ 个 01 整数，其中第 $i$ 个数表示 $L_i$ 的值。

outputFormat: 仅包含一个整数，表示可行的旅行路线总数 $\bmod \space 11\,192\,869$ 的值。