Problem

【SCOI2010】传送带

Description

在一个维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段和线段。
在上的移动速度为，在上的移动速度为，在平面上的移动速度。
现在想从点走到点，他想知道最少需要走多长时间。

Input

输入数据第一行是个整数，表示和的坐标，分别为。
第二行是个整数，表示和的坐标，分别为。
第三行是个整数，分别是。

Output

输出数据为一行，表示从点走到点的最短时间，保留到小数点后位。

Problem

【SCOI2007】压缩

Description

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母与，其中标记重复串的开始，重复从上一个（如果当前位置左边没有，则从串的开始算起）开始的解压结果（称为缓冲串）。 可以压缩为，下面是解压缩的过程：

另一个例子是可以被压缩为。

Input

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为。

Output

输出仅一行，即压缩后字符串的最短长度。

Problem

【SCOI2014】方伯伯运椰子

Description

Input

第一行包含二个整数,。
接下来行代表条边，表示这个交通网络。
每行六个整数，表示。
接下来一行包含一条边，表示连接起点的边。

Output

一个浮点数，保留二位小数。表示答案，数据保证答案大于。

Problem

【SCOI2015】小凸玩矩阵

Description

小凸和小方是好朋友，小方给小凸一个的矩阵,要求小秃从其中选出个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的个数中第大的数字的最小值是多少。

Input

第一行给出三个整数
接下来行，每行个数字，用来描述这个矩阵

Output

输出一个整数，表示第大数字的最小值

Problem

【SCOI2014】方伯伯的玉米田

Description

方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。
这排玉米一共有株，它们的高度参差不齐。
方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。
方伯伯可以选择一个区间，把这个区间的玉米全部拔高单位高度，他可以进行最多次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米，来构成一排美丽的玉米。

Input

第行包含个整数，分别表示这排玉米的数目以及最多可进行多少次操作。
第行包含个整数，第个数表示这排玉米，从左到右第株玉米的高度。

Output

输出个整数，最多剩下的玉米数。

Problem

【SHOI2016】生成魔咒

Description

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 , 拼凑起来形成一个魔咒串 。
一个魔咒串 的非空字串被称为魔咒串 的生成魔咒。例如 时，它的生成魔咒有 ,,,, 五种。 时，它的生成魔咒有 ,, 三种。
最初 为空串。共进行 次操作，每次操作是在 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 共有多少种生成魔咒。

Input

第一行一个整数 。
第二行 个数，第 个数表示第 次操作加入的魔咒字符
，用来表示魔咒字符的数字 满足

Output

输出 行，每行一个数。第 行的数表示第 次操作后 的生成魔咒数量

Problem

【TJOI2015】弦论

Description

对于一个给定长度为的字符串，求它的第小子串是什么。

Input

第一行是一个仅由小写英文字母构成的字符串。
第二行为两个整数和，为则表示不同位置的相同子串算作一个，则表示不同位置的相同子串算作多个。的意义如题所述。

Output

输出仅一行，为一个数字串，为第小的子串。如果子串数目不足个，则输出。

Problem

【SCOI2016】萌萌哒

Description

一个长度为的大数，用表示，其中表示数的第位，是数的最高位，告诉你一些限制条件，每个条件表示为四个数，，，，，即两个长度相同的区间，表示子串与完全相同。比如时，某限制条件，，，，那么，均满足条件，但是，不满足条件，前者数的长度不为，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

Input

第一行两个数和，分别表示大数的长度，以及限制条件的个数。接下来行，对于第行，有个数，，，，分别表示该限制条件对应的两个区间。
，，；并且保证。

Output

一个数，表示满足所有条件且长度为的大数的个数，答案可能很大，因此输出答案模的结果即可。

Problem

于神之怒加强版

Description

给下，计算的值。

Input

输入有多组数据，输入数据的第一行两个正整数，代表有组数据，的意义如上所示，下面第行到第行，每行为两个正整数，其意义如上式所示。

Output

对于每一个询问，输出一行一个数作为回答。

Problem

DZY Loves Math

Description

对于正整数，定义为所含质因子的最大幂指数。例如, , 。
给定正整数，求。

Input

第一行一个数，表示询问数。
接下来行，每行两个数，表示一个询问。

Output

对于每一个询问，输出一行一个非负整数作为回答。