title: [USACO08OPEN] Word Power S

description:
Farmer John wants to evaluate the quality of the names of his N (1 <= N <= 1000) cows. Each name is a string with no more than 1000 characters, all of which are non-blank.

He has created a set of M (1 <= M <= 100) 'good' strings (no

longer than 30 characters and fully non-blank). If the sequence letters of a cow's name contains the letters of a 'good' string in the correct order as a subsequence (i.e., not necessarily all next to each other), the cow's name gets 1 quality point.

All strings is case-insensitive, i.e., capital letters and lower case letters are considered equivalent.  For example, the name 'Bessie' contains the letters of 'Be', 'sI', 'EE', and 'Es' in the correct order, but not 'is' or 'eB'. Help Farmer John determine the number of quality points in each of his cow's names.

约翰想要计算他那N(l < =N <= 1000)只奶牛的名字的能量.每只奶牛的名字由不超过1000个字 符构成，没有一个名字是空字体串.

约翰有一张“能量字符串表”，上面有M(1 < =M < =100)个代表能量的字符串.每个字符串 由不超过30个字体构成，同样不存在空字符串.一个奶牛的名字蕴含多少个能量字符串，这个名 字就有多少能量.所谓“蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现（不 一定一个紧接着一个）.

所有的大写字母和小写字母都是等价的.比如，在贝茜的名字“Bessie”里，蕴含有“Be” “si” “EE”以及“Es”等等字符串，但不蕴含“Ls”或“eB” .请帮约翰计算他的奶牛的名字 的能量.

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 contains a string that is the name of the ith cow

\* Lines N+2..N+M+1: Line N+i+1 contains the ith good string

outputFormat: \* Lines 1..N+1: Line i+1 contains the number of quality points of the ith name

samples:
5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont

hint:
There are 5 cows, and their names are "Bessie", "Jonathan", "Montgomery", "Alicia", and "Angola". The 3 good strings are "se", "nGo", and "Ont".

"Bessie" contains "se", "Jonathan" contains "Ont", "Montgomery" contains both "nGo" and "Ont", Alicia contains none of the good strings, and "Angola" contains "nGo".


title: [USACO08OPEN] Cow Cars S

type: P

description:
N (1 <= N <= 50,000) cows conveniently numbered 1..N are driving in separate cars along a highway in Cowtopia. Cow i can drive in any of M different high lanes (1 <= M <= N) and can travel at a maximum speed of S\_i (1 <= S\_i <= 1,000,000) km/hour.

After their other bad driving experience, the cows hate collisions and take extraordinary measures to avoid them. On this highway, cow i reduces its speed by D (0 <= D <= 5,000) km/hour for each cow in front of it on the highway (though never below 0 km/hour). Thus, if there are K cows in front of cow i, the cow will travel at a speed of max[S\_i - D \* K, 0]. While a cow might actually travel faster than a cow directly in front of it, the cows are spaced far enough apart so crashes will not occur once cows slow down as

described,

Cowtopia has a minimum speed law which requires everyone on the highway to travel at a a minimum speed of L (1 <= L <= 1,000,000) km/hour so sometimes some of the cows will be unable to take the highway if they follow the rules above. Write a program that will find the maximum number of cows that can drive on the highway while obeying the minimum speed limit law.

inputFormat:
\* Line 1: Four space-separated integers: N, M, D, and L

\* Lines 2..N+1: Line i+1 describes cow i's initial speed with a single integer: S\_i

outputFormat: \* Line 1: A single integer representing the maximum number of cows that can use the highway

translation:
有 $N$ 头奶牛 $(1 \le N \le 50000)$，编号 $1 \sim N$。它们正各自驾着车打算在高速公路上飞驰．高速公路有 $M(1\leq M\leq N)$ 条车道。奶牛 $i$ 有一个自己的车速上限 $S_i  \ (1\leq S_i\leq 10^6)$。

在经历过糟糕的驾驶事故之后，奶牛们变得十分小心，避免碰撞的发生。每条车道上，如果某一只奶牛 $i$ 的前面有 $k$ 只奶牛驾车行驶，那奶牛 $i$ 的速度上限就会下降 $k\times D$ 个单位，也就是说，她的速度不会超过 $S_i - k \times D(0\leq D\leq 5000)$，当然如果这个数是负的，那她的速度将是 $0$。高速公路法规定，在高速公路上行驶的车辆时速不得低于 $L \ (1 \le L \le 10 ^ 6)$。

求：最多有多少奶牛可以在高速公路上行驶。

hint:
There are three cows with one lane to drive on, a speed decrease of 1, and a minimum speed limit of 5.

Two cows are possible, by putting either cow with speed 5 first and the cow with speed 7 second.


title: [USACO08OPEN] Clear And Present Danger S

description:
Farmer John is on a boat seeking fabled treasure on one of the N (1 <= N <= 100) islands conveniently labeled 1..N in the Cowribbean Sea.

The treasure map tells him that he must travel through a certain sequence A\_1, A\_2, ..., A\_M of M (2 <= M <= 10,000) islands, starting on island 1 and ending on island N before the treasure will appear to him. He can visit these and other islands out of order and even more than once, but his trip must include the A\_i sequence in the order specified by the map.

FJ wants to avoid pirates and knows the pirate-danger rating (0 <= danger <= 100,000) between each pair of islands. The total danger rating of his mission is the sum of the danger ratings of all the paths he traverses.

Help Farmer John find the least dangerous route to the treasure that satisfies the treasure map's requirement.

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: Line i+1 describes the i\_th island FJ must visit with a single integer: A\_i

\* Lines M+2..N+M+1: Line i+M+1 contains N space-separated integers that are the respective danger rating of the path between island i and islands 1, 2, ..., and N, respectively. The ith integer is always zero.

outputFormat: \* Line 1: The minimum danger that Farmer John can encounter while obtaining the treasure.

translation:
农夫约翰正驾驶一条小艇在牛勒比海上航行．

海上有 $N(1\leq N\leq 100)$ 个岛屿，用 $1$ 到 $N$ 编号．约翰从 $1$ 号小岛出发，最后到达 $N$ 号小岛．

一张藏宝图上说，如果他的路程上经过的小岛依次出现了  $A_1,A_2,\dots ,A_M(2\leq M\leq 10000)$ 这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数 $D_{i,j}(0\leq D_{i,j}\leq 100000)$ 来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

输入输出格式

输入格式：

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

第二到第 $M+1$ 行：第 $i+1$ 行用一个整数 $A_i$ 表示 FJ 必须经过的第 $i$ 个岛屿

第 $M+2$ 到第 $N+M+1$ 行：第 $i+M+1$ 行包含 $N$ 个用空格隔开的非负整数分别表示 $i$ 号小岛到第 $1\dots N$ 号小岛的航线各自的危险指数。保证第 $i$ 个数是 $0$。

输出格式
第一行：FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。

说明
这组数据中有三个岛屿，藏宝图要求 FJ 按顺序经过四个岛屿：$1$ 号岛屿、$2$ 号岛屿、回到 $1$ 号岛屿、最后到 $3$ 号岛屿。每条航线的危险指数也给出了：航路$(1,2),(2,3),(3,1)$ 和它们的反向路径的危险指数分别是 $5,2,1$。

FJ 可以通过依次经过 $1,3,2,3,1,3$ 号岛屿以 $7$ 的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求 $(1,2,1,3)$。我们避开了 $1$ 号和 $2$ 号岛屿之间的航线，因为它的危险指数太大了。

注意：测试数据中 $a$ 到 $b$ 的危险指数不一定等于 $b$ 到 $a$ 的危险指数！

Translated by @LJC00125

hint:
There are 3 islands and the treasure map requires Farmer John to visit a sequence of 4 islands in order: island 1, island 2, island 1 again, and finally island 3. The danger ratings of the paths are given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have danger ratings of 5, 2, and 1, respectively.

He can get the treasure with a total danger of 7 by traveling in the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement (1, 2, 1, and 3) is satisfied by this route. We avoid the path between islands 1 and 2 because it has a large danger rating.

输入输出格式

输入格式：

第一行：两个用空格隔开的正整数N和M

第二到第M+1行：第i+1行用一个整数Ai表示FJ必须经过的第i个岛屿

第M+2到第N+M+1行：第i+M+1行包含N个用空格隔开的非负整数分别表示i号小岛到第1...N号小岛的航线各自的危险指数。保证第i个数是0。

输出格式

第一行：FJ在找到宝藏的前提下经过的航线的危险指数之和的最小值。

说明

这组数据中有三个岛屿，藏宝图要求FJ按顺序经过四个岛屿：1号岛屿、2号岛屿、回到1号岛屿、最后到3号岛屿。每条航线的危险指数也给出了：航路(1，2)、(2，3)、(3，1)和它们的反向路径的危险指数分别是5、2、1。

FJ可以通过依次经过1、3、2、3、1、3号岛屿以7的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求（1，2，1，3）。我们避开了1号和2号岛屿之间的航线，因为它的危险指数太大了。

注意：测试数据中a到b的危险指数不一定等于b到a的危险指数！


title: [USACO08OCT] Bovine Bones G

description:
Bessie loves board games and role-playing games so she persuaded Farmer John to drive her to the hobby shop where she purchased three dice for rolling. These fair dice have S1, S2, and S3 sides

respectively (2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40).

Bessie rolls and rolls and rolls trying to figure out which three-dice sum appears most often.

Given the number of sides on each of the three dice, determine which three-dice sum appears most frequently. If more than one sum can appear most frequently, report the smallest such sum.

POINTS: 70

inputFormat: \* Line 1: Three space-separated integers: S1, S2, and S3

outputFormat: \* Line 1: The smallest integer sum that appears most frequently when the dice are rolled in every possible combination.

translation:
贝茜喜欢玩棋盘游戏和角色扮演游戏，所以她说服了约翰开车带她去小商店.在那里她买了三个骰子。这三个不同的骰子的面数分别为 $s_1,s_2,s_3$。

对于一个有 $S$ 个面的骰子每个面上的数字是 $1,2,3,\ldots,S$。每个面（上的数字）出现的概率均等。贝茜希望找出在所有“三个面上的数字的和”中，哪个和的值出现的概率最大。

现在给出每个骰子的面数，需要求出哪个所有“三个面上的数字的和”出现得最频繁。如果有很多个和出现的概率相同，那么只需要输出最小的那个。

数据范围： $2\le s_1\leq 20$，$2 \leq s_2\leq 20$，$2 \leq s_3\leq 40$。


title: [USACO08OCT] Pasture Walking G

description:
The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing among the N pastures also conveniently numbered 1..N. Most conveniently of all, cow i is grazing in pasture i.

Some pairs of pastures are connected by one of N-1 bidirectional walkways that the cows can traverse. Walkway i connects pastures A\_i and B\_i (1 <= A\_i <= N; 1 <= B\_i <= N) and has a length of L\_i (1 <= L\_i <= 10,000).

The walkways are set up in such a way that between any two distinct pastures, there is exactly one path of walkways that travels between them. Thus, the walkways form a tree.

The cows are very social and wish to visit each other often. Ever in a hurry, they want you to help them schedule their visits by computing the lengths of the paths between 1 <= L\_i <= 10,000 pairs of pastures (each pair given as a query p1,p2 (1 <= p1 <= N; 1 <= p2 <= N).

POINTS: 200

有N(2<=N<=1000)头奶牛，编号为1到W，它们正在同样编号为1到N的牧场上行走.为了方 便，我们假设编号为i的牛恰好在第i号牧场上.

有一些牧场间每两个牧场用一条双向道路相连，道路总共有N - 1条，奶牛可以在这些道路 上行走.第i条道路把第Ai个牧场和第Bi个牧场连了起来(1 <= A\_i <= N; 1 <= B\_i <= N)，而它的长度 是 1 <= L\_i <= 10,000.在任意两个牧场间，有且仅有一条由若干道路组成的路径相连.也就是说，所有的道路构成了一棵树.

奶牛们十分希望经常互相见面.它们十分着急，所以希望你帮助它们计划它们的行程，你只 需要计算出Q(1 < Q < 1000)对点之间的路径长度•每对点以一个询问p1,p2 (1 <= p1 <= N; 1 <= p2 <= N). 的形式给出.

inputFormat:
\* Line 1: Two space-separated integers: N and Q

\* Lines 2..N: Line i+1 contains three space-separated integers: A\_i, B\_i, and L\_i

\* Lines N+1..N+Q: Each line contains two space-separated integers representing two distinct pastures between which the cows wish to travel: p1 and p2

outputFormat: \* Lines 1..Q: Line i contains the length of the path between the two pastures in query i.

hint:
Query 1: The walkway between pastures 1 and 2 has length 2.

Query 2: Travel through the walkway between pastures 3 and 4, then the one between 4 and 1, and finally the one between 1 and 2, for a total length of 7.


title: [USACO08OCT] Wheel Rotation G

description:
Farmer John has an old-time thresher (wheat harvester) that requires belts to be installed on various gears to turn the parts. The engine drives pulley 1 in a clockwise direction which attaches via a belt to pulley 2. Pulley 2 attaches via a belt to pulley 3 and so on through a total of N (2 <= N <= 1,000) pulleys (and N-1 belts).

The diagram above depicts the two ways a belt can be installed between two gears. In this illustration, pulley 1's belt directly drives pulley 2 (a 'straight' connection) and thus they will rotate in the same direction. Pulley 3 drives pulley 4 via a 'crossed belt' that reverses the direction of the rotation.

Given a list of the belt types that connect the pulleys along with the fact that pulley 1 is driven in a clockwise direction by the engine, determine the drive direction of pulley N. Each belt is described by three integers:

```cpp
* S_i -- the driving (source) pulley
* D_i -- the driven (destination) pulley
* C_i -- the connection type (0=straight, 1=crossed)
Unfortunately, FJ lists the belts in random order.
By way of example, consider the illustration below. N = 4, and pulley 1 is driven clockwise by the thresher engine. Straight
belts drive pulley 2 and then pulley 3, so they rotate clockwise. The crosswise belt reverses the rotation direction so pulley 4 (pulley N) rotates counterclockwise.
```
POINTS: 70
约翰有一个过时的收割机，需要在它的各种滑轮上装配皮带才能让收割机的各个部分运作起 来.引擎能够驱动滑轮1向顺时针方向转动，滑轮1通过一条皮带又连接到滑轮2.滑轮2又通过一 条皮带连接到滑轮3，等等，总共有N(2 <= N <= 1000)个滑轮和N - 1条皮带.

皮带连接两个滑轮有两种方式：直接连接和交叉连接.直接连接的两个滑轮旋转方向相同， 即同为顺时针或同为逆时针.交叉连接的两个滑轮旋转方向相反.

现在给出一个列表，里面列出所有皮带的连接方式.已经知道滑轮1被引擎驱动着向顺时针方 向转动.每一条皮带由下面三个数定义：

•驱动滑轮S，输入驱动力的滑轮.

•被驱动滑轮D;，被驱使转动的滑轮.

•连接类型C，0表示直接连接，1表示交叉连接.

不幸的是，约翰的这个列表中，皮带的顺序是混乱的.所以请你写一个程序来求出滑轮N的 转动方向.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N: Each line describes a belt with three integers: S\_i, D\_i, and C\_i

outputFormat: \* Line 1: A single integer that is the rotation direction for pulley N (0=clockwise, 1=counterclockwise)

hint: As in the example illustration.


title: [USACO08OCT] Power Failure G

description:
A vicious thunderstorm has destroyed some of the wires of the farm's electrical power grid! Farmer John has a map of all $N$ ($2\le N \le 1000$) of the powerpoles, which are conveniently numbered $1\ldots N$ and located on integer plane coordinates $(x_i,y_i)$ ($-100000 \le x_i \le 100000, -100000 \le y_i \le 100000$).

Some $W$ ($1 \le W \le 10000$) power wires connect pairs of power poles $P_i$ and $P_j$ ($1 \le Pi \le N, 1 \le Pj \le N$).

He needs to get power from pole $1$ to pole $N$ (which means that some series of wires can traverse from pole $1$ to pole $N$, probably through some intermediate set of poles).

Given the locations of the $N$ poles and the list of remaining power wires, determine the minimum length of power wire required to restore the electrical connection so that electricity can flow from pole $1$ to pole $N$.  No wire can be longer than some real number $M$ ($0.0 < M \le 200000.0$).

As an example, below on the left is a map of the $9$ poles and $3$ wires after the storm. For this task, $M = 2.0$. The best set of wires to add would connect poles $4$ and $6$ and also poles $6$ and $9$.

```cpp
   After the storm              Optimally reconnected
3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9
```

The total length is then $1.414213562 + 1.414213562 = 2.828427124$.

POINTS: 350

inputFormat:
Line $1$: Two space-separated integers: $N$ and $W$.

Line $2$: A single real number: $M$.

Lines $3\ldots N+2$: Each line contains two space-separated integers: $x_i$ and $y_i$.

Lines $N+3\ldots N+2+W$: Two space-separated integers: $P_i$ and $P_j$.

outputFormat: Line 1: A single integer on a single line. If restoring connection is impossible, output `-1`. Otherwise, output a single integer that is $1000$ times the total minimum cost to restoreelectricity. Do not perform any rounding; truncate the resulting product.

translation:
一场邪恶的暴风雨毁坏了农夫约翰的输电网中的一些电线！农夫约翰有一张包含了所有 $n$（$2\le n\le 1000$）个电能中转点的地图，中转点编号为 $1\ldots n$，第 $i$ 个点的坐标为 $(x_i,y_i)$（$-100000\le x_i\le 100000,-100000\le y_i\le 100000$）。

有 $w$（$1<=w<=10000$）条电线仍然保存着没被暴风雨破坏，每条电线连接着两个电能中转点 $p_i,p_j$（$1\le p_i\le n,1\le p_j\le n$）。

他希望从第一个电能中转点把电导入第 $n$ 个（可能通过一些中间的电能中转点，应当有一组电线连接 $1$ 和 $n$ ）。

给出 $n$ 个电能中转点的坐标和幸存的电线，请确定最少需要架设的电线总长度，但请注意，架设过程中，对于单条电线而言，其长度不应超过$m$（$0.0\le m\le 200000.0$）

给出一个例子，在下面，左边是一个包含 $9$ 个电能中转电和 $3$ 条幸存电线的地图。在这个任务中，规定 $m=2.0$。最佳的架设方案是连接 $6$ 和 $4$，以及 $6$ 和 $9$。

```plain
   After the storm              Optimally reconnected
3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9
```
总长度是 $1.414213562 + 1.414213562 = 2.828427124$。

hint:
Just as in the diagram above.

As above.


title: [USACO08NOV] Mixed Up Cows G

description:
Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S\_i (1 <= S\_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 200

约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍， 而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？

inputFormat:
\* Line 1: Two space-separated integers: N and K

\* Lines 2..N+1: Line i+1 contains a single integer that is the serial number of cow i: S\_i

outputFormat: \* Line 1: A single integer that is the number of ways that N cows can be 'Mixed Up'. The answer is guaranteed to fit in a 64 bit integer.

hint:
The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3


title: [USACO08NOV] Cheering up the Cow G

description:
Farmer John has grown so lazy that he no longer wants to continue maintaining the cow paths that currently provide a way to visit each of his N (5 <= N <= 10,000) pastures (conveniently numbered 1..N). Each and every pasture is home to one cow. FJ plans to remove as many of the P (N-1 <= P <= 100,000) paths as possible while keeping the pastures connected. You must determine which N-1 paths to keep.

Bidirectional path j connects pastures S\_j and E\_j (1 <= S\_j <= N; 1 <= E\_j <= N; S\_j != E\_j) and requires L\_j (0 <= L\_j <= 1,000) time to traverse. No pair of pastures is directly connected by more than one path.

The cows are sad that their transportation system is being reduced. You must visit each cow at least once every day to cheer her up. Every time you visit pasture i (even if you're just traveling

through), you must talk to the cow for time C\_i (1 <= C\_i <= 1,000).

You will spend each night in the same pasture (which you will choose) until the cows have recovered from their sadness. You will end up talking to the cow in the sleeping pasture at least in the morning when you wake up and in the evening after you have returned to sleep.

Assuming that Farmer John follows your suggestions of which paths to keep and you pick the optimal pasture to sleep in, determine the minimal amount of time it will take you to visit each cow at least once in a day.

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 300

约翰有N个牧场，编号依次为1到N。每个牧场里住着一头奶牛。连接这些牧场的有P条道路，每条道路都是双向的。第j条道路连接的是牧场Sj和Ej，通行需要Lj的时间。两牧场之间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。

约翰知道，在道路被强拆后，奶牛会非常伤心，所以他计划拆除道路之后就去忽悠她们。约翰可以选择从任意一个牧场出发开始他维稳工作。当他走访完所有的奶牛之后，还要回到他的出发地。每次路过牧场i的时候，他必须花Ci的时间和奶牛交谈，即使之前已经做过工作了，也要留下来再谈一次。注意约翰在出发和回去的时候，都要和出发地的奶牛谈一次话。请你计算一下，约翰要拆除哪些道路，才能让忽悠奶牛的时间变得最少？

inputFormat:
\* Line 1: Two space-separated integers: N and P

\* Lines 2..N+1: Line i+1 contains a single integer: C\_i

\* Lines N+2..N+P+1: Line N+j+1 contains three space-separated

integers: S\_j, E\_j, and L\_j

outputFormat:
\* Line 1: A single integer, the total time it takes to visit all the cows (including the two visits to the cow in your

sleeping-pasture)


title: [USACO08NOV] Toys G

description:
Bessie's birthday is coming up, and she wishes to celebrate for the next D (1 <= D <= 100,000; 70% of testdata has 1 <= D <= 500) days. Cows have short attention spans so Bessie wants to provide toys to entertain them. She has calculated that she will require T\_i (1 <= T\_i <= 50) toys on day i.

Bessie's kindergarten provides many services to its aspiring bovine programmers, including a toy shop which sells toys for Tc (1 <= Tc <= 60) dollars. Bessie wishes to save money by reusing toys, but Farmer John is worried about transmitting diseases and requires toys to be disinfected before use. (The toy shop disinfects the toys when it sells them.)

The two disinfectant services near the farm provide handy complete services. The first one charges C1 dollars and requires N1 nights to complete; the second charges C2 dollars and requires N2 nights to complete (1 <= N1 <= D; 1 <= N2 <= D; 1 <= C1 <= 60; 1 <= C2 <= 60). Bessie takes the toys to the disinfecters after the party and can pay and pick them back up the next morning if one night service is rendered, or on later mornings if more nights are required for disinfecting.

Being an educated cow, Bessie has already learned the value of saving her money. Help her find the cheapest way she can provide toys for her party.

POINTS: 400

inputFormat:
\* Line 1: Six space-separated integers: D, N1, N2, C1, C2, Tc

\* Lines 2..D+1: Line i+1 contains a single integer: T\_i

outputFormat: \* Line 1: The minimum cost to provide safe and sanitary toys for Bessie's birthday parties.

translation:
Bessie 的生日快到了，她希望用 $D$（$1 \le D \le 100000$）天来庆祝。奶牛们的注意力不会太集中，因此 Bessie 想通过提供玩具的方式来使它们高兴。她已经计算出了第 $i$ 天需要的玩具数 $T_i$（$1 \le T_i \le 50$）。

Bessie 的幼儿园给它们的奶牛程序员们提供了许多服务，包括一个每天以 $T_c\ (1 \le T_c \le 60)$ 美元卖出商品的玩具店。Bessie 想尽可能地节省钱。但是 FarmerJohn 担心没有经过消毒的玩具会带来传染病。（玩具店卖出的玩具是经过消毒的）

有两种消毒的方式。

- 第 $1$ 种方式需要收费 $C_1$ 美元，需要 $N_1$ 个晚上的时间；
- 第 $2$ 种方式需要收费 $C_2$ 美元，需要 $N_2$ 个晚上的时间（$1 \le N_1,N_2 \le D$，$1 \le C_1,C_2 \le 60$）。

Bessie 在派对结束之后把她的玩具带去消毒。如果消毒只需要一天，那么第二天就可以拿到；如果还需要一天，那么第三天才可以拿到。

作为一个受过教育的奶牛，Bessie 已经了解到节约的意义。帮助她找到提供玩具的最便宜的方法。

hint:
Bessie wishes to party for 4 days, and requires 8 toys the first day, 2 toys the second, 1 toy the third, and 6 toys on the fourth day. The first disinfectant service takes 1 day and charges $2, and the second takes 2 days and charges $1. Buying a new toy costs $3.

Day 1   Purchase 8 toys in the morning for $24; party in the

afternoon. Take 2 toys to the fast cleaner (overnight) and

the other 6 toys to the slow cleaner (two nights).

Day 2   Pick up the two toys at the fast cleaner; pay $4. Party in the afternoon. Take 1 toy to the slow cleaner.

Day 3   Pick up 6 toys from the slow cleaner and pay $6. Party in the afternoon.

Day 4   Pick up the final remaining toy from the slow cleaner

(bringing the number of toys onsite back to 6); pay $1. Party hearty with the realization that a minimum amount of money was spent.


title: [USACO08NOV] Buying Hay S

description:
Farmer John is running out of supplies and needs to purchase H (1 <= H <= 50,000) pounds of hay for his cows.

He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N. Supplier i sells packages that contain P\_i (1 <= P\_i <= 5,000) pounds of hay at a cost of C\_i (1 <= C\_i <= 5,000) dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.

Help FJ by finding the minimum cost necessary to purchase at least H pounds of hay.

约翰的干草库存已经告罄，他打算为奶牛们采购 $H(1 \leq H \leq 50000)$ 磅干草。

他知道 $N(1 \leq N\leq 100)$ 个干草公司，现在用 $1$ 到 $N$ 给它们编号。第 $i$ 公司卖的干草包重量为 $P_i (1 \leq P_i \leq 5,000)$ 磅，需要的开销为 $C_i (1 \leq C_i \leq 5,000)$ 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。

帮助约翰找到最小的开销来满足需要，即采购到至少 $H$ 磅干草。

inputFormat:
\* Line 1: Two space-separated integers: N and H

\* Lines 2..N+1: Line i+1 contains two space-separated integers: P\_i and C\_i

outputFormat: \* Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.

hint: FJ can buy three packages from the second supplier for a total cost of 9.


title: [USACO08NOV] Guarding the Farm S

description:
The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.

He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H\_ij (0 <= H\_ij <= 10,000). Help him determine the number of hilltops on the map.

A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 describes row i of the matrix with M

space-separated integers: H\_ij

outputFormat: \* Line 1: A single integer that specifies the number of hilltops

translation:
农夫 John 的农场里有很多小山丘，他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。

他想知道如果在一座小山丘上布置一名保镖的话，他最少总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有 $N$ 行和 $M$ 列。矩阵中的每个元素都有一个值 $H_{ij}$ 来表示该地区的海拔高度。

小山丘的定义是：若地图中一个元素所邻接的所有元素都小于等于这个元素的高度（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个位置的横纵坐标与另一个位置的横纵坐标相差不超过 $1$，则称这两个元素邻接，比如某个非边界点的位置有 $8$ 个相邻点：上、下、左、右、左上、右上、左下、右下。

请你帮助他统计出地图上最少且尽量高的小山丘数量。

hint: There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.


title: [USACO08NOV] Time Management S

description:
Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on).

To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T\_i (1 <= T\_i <= 1,000) to complete and furthermore must be finished by time S\_i (1 <= S\_i <= 1,000,000). Farmer John starts his day at time t=0 and can only work on one job at a time until it is finished.

Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.

作为一名忙碌的商人，约翰知道必须高效地安排他的时间。他有 $N(1\le N\le 1000)$ 个工作要做，比如给奶牛挤奶，清洗牛棚，修理栅栏之类的。

为了高效，约翰列出了所有工作的清单。第 $i(1\le i\le N)$ 个工作需要 $T_i(1\le T_i\le 1000)$ 单位的时间来完成，而且必须在 $1\le S_i\le 10^6$ 或之前完成。现在是 $0$ 时刻。约翰做一份工作必须直到做完才能停止。

所有的商人都喜欢睡懒觉。请帮约翰计算他最迟什么时候开始工作，可以让所有工作按时完成。（如果始终无法完成全部任务，输出 $-1$）

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains two space-separated integers: T\_i and S\_i

outputFormat: \* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.

hint:
Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of time, respectively, and must be completed by time 5, 14, 20, and 16, respectively.

Farmer John must start the first job at time 2. Then he can do the second, fourth, and third jobs in that order to finish on time.


title: [USACO08DEC] Trick or Treat on the Farm G

description:
Every year in Wisconsin the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N (1 <= N <= 100,000) stalls conveniently numbered 1..N.

Because the barn is not so large, FJ makes sure the cows extend their fun by specifying a traversal route the cows must follow.  To implement this scheme for traveling back and forth through the barn, FJ has posted a 'next stall number' next\_i (1 <= next\_i <= N) on stall i that tells the cows which stall to visit next; the cows thus might travel the length of the barn many times in order to collect their candy.

FJ mandates that cow i should start collecting candy at stall i. A cow stops her candy collection if she arrives back at any stall she has already visited.

Calculate the number of unique stalls each cow visits before being forced to stop her candy collection.

POINTS: 100

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains a single integer: next\_i

outputFormat: \* Lines 1..N: Line i contains a single integer that is the total number of unique stalls visited by cow i before she returns to a stall  she has previously visited.

translation:
#### 题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在 $N(1\le N\le 100,000)$ 个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ 通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ 在第 $i$ 号隔间上张贴了一个 “下一个隔间：$next_i(1\le next_i\le N)$” 的标语，告诉奶牛要去的下一个隔间。这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ 命令奶牛 $i$ 应该从 $i$ 号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

#### 输入格式

第一行一个整数 $n$，表示牛棚隔间的数量。

第 $2$ 至 $n+1$ 行，每行包含一个整数 $next_i$，表示 $i$ 号隔间的下一个隔间。

#### 输出格式

输出共 $n$ 行，第 $i$ 行包含一个整数，表示第 $i$ 只奶牛要前往的隔间数。

#### 样例解释

有 $4$ 个隔间。

- 隔间 $1$ 要求牛到隔间 $1$，

- 隔间 $2$ 要求牛到隔间 $3$，

- 隔间 $3$ 要求牛到隔间 $2$，

- 隔间 $4$ 要求牛到隔间 $3$。

牛 $1$：从 $1\rightarrow 1$，总共访问 $1$ 个隔间；

牛 $2$：$2\rightarrow 3\rightarrow 2$，总共访问 $2$ 个隔间；

牛 $3$：$3\rightarrow 2\rightarrow 3$，总共访问 $2$ 个隔间；

牛 $4$：$4\rightarrow 3\rightarrow 2\rightarrow 3$，总共访问 $3$ 个隔间。

翻译提供者：[busy_programmer](https://www.luogu.com.cn/user/649315)。

hint:
Four stalls.

\* Stall 1 directs the cow back to stall 1.

\* Stall 2 directs the cow to stall 3

\* Stall 3 directs the cow to stall 2

\* Stall 4 directs the cow to stall 3

Cow 1:  Start at 1, next is 1.  Total stalls visited: 1.

Cow 2:  Start at 2, next is 3, next is 2.  Total stalls visited: 2. Cow 3:  Start at 3, next is 2, next is 3.  Total stalls visited: 2. Cow 4:  Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.


title: [USACO08DEC] Secret Message G

description:
Bessie is leading the cows in an attempt to escape! To do this, the cows are sending secret binary messages to each other.

Ever the clever counterspy, Farmer John has intercepted the first $b_i$ ($1 \le b_i \le 10,000$) bits of each of $M$ ($1 \le M \le 50,000$) of these secret binary messages.

He has compiled a list of $N$ ($1 \le N \le 50,000$) partial codewords that he thinks the cows are using. Sadly, he only knows the first $c_j$ ($1 \le c_j \le 10,000$) bits of codeword $j$.

For each codeword $j$, he wants to know how many of the intercepted messages match that codeword (i.e., for codeword $j$, how many times does a message and the codeword have the same initial bits). Your job is to compute this number.

The total number of bits in the input (i.e., the sum of the $b_i$ and the $c_j$) will not exceed  $500,000$.

贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．

信息是二进制的，共有 $M$（$1 \le M \le 50000$）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第  $i$ 条二进制信息的前 $b_i$（$1 \le b_i \le 10000$）位，他同时知道，奶牛使用 $N$（$1 \le N \le 50000$）条暗号．但是，他仅仅知道第 $j$ 条暗号的前 $c_j$（$1 \le c_j \le 10000$）位。

对于每条暗号 $j$，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中，位的总数（即 $\sum b_i + \sum c_i$）不会超过 $500000$。

inputFormat:
Line $1$: Two integers: $M$ and $N$.

Lines $2 \ldots M+1$: Line $i+1$ describes intercepted code $i$ with an integer $b_i$ followed by $b_i$ space-separated `0`'s and `1`'s.

Lines $M+2 \ldots M+N+1$: Line $M+j+1$ describes codeword $j$ with an integer $c_j$ followed by $c_j$ space-separated `0`'s and `1`'s.

outputFormat: Lines $1 \ldots N$: Line $j$: The number of messages that the $j$-th codeword could match.

hint:
Four messages; five codewords.

The intercepted messages start with 010, 1, 100, and 110.

The possible codewords start with 0, 1, 01, 01001, and 11.

0 matches only 010: 1 match

1 matches 1, 100, and 110: 3 matches

01 matches only 010: 1 match

01001 matches 010: 1 match

11 matches 1 and 110: 2 matches


title: [USACO08DEC] Winning Checkers G

description:
The cows have taken up the game of checkers with a vengeance.

Unfortunately, despite their unlimited enjoyment of playing, they are terrible at the endgame and want your help.

Given an NxN (4 <= N <= 500) checkboard, determine the optimal set of moves (i.e., smallest number of moves) to end the game on the next move. Checkers move only on the '+' squares and capture by jumping 'over' an opponent's piece in the traditional way. The piece is removed as soon as it is jumped.  See the example below where N=8:

```cpp
- + - + - + - +  The K's mark Bessie's kings; the o's represent the
+ - + - + - + -  opponent's checkers. Bessie always moves next. The
- + - K - + - +  Kings jump opponent's checkers successively in any
+ - + - + - + -  diagonal direction (and removes pieces when jumped).
- o - o - + - +
+ - K - + - + -  For this board, the best solution requires the lower
- o - + - + - +  left King to jump successively across all three of the
+ - K - + - K -  opponents' checkers, thus ending the game (moving K marked as >K<):
Original          After move 1       After move 2        After move 3
- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -
- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +
+ - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + -
- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +
+ - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + -
- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ ->K<- + - K -     + - + - + - K -    + - K - + - K -     + - K - + - K -

The moves traversed these squares:
1 2 3 4 5 6 7 8           R C
1 - + - + - + - +    start: 8 3
2 + - + - + - + -    move:  6 1
3 - + - K - + - +    move:  4 3
4 + - * - + - + -    move:  6 5
5 - o - o - + - +
6 * - K - * - + -
7 - o - + - + - +
8 + - K - + - K -
```
Write a program to determine the game-ending sequence for an NxN input board if it exists. There is at least a king and at least one opponent piece on the board. The king can jump a piece on every move of the optimal solution.

POINTS: 330

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains N characters (each one of: '-', '+', 'K', or 'o') that represent row i of a proper checkboard. Line 2 always begins with '-'.

outputFormat:
\* Lines 1..?: If there is no winning sequence of jump, output

'impossible' on a line by itself. If such a sequence exists, each line contains two space-separated integers that represent successive locations of a king whose moves will win the game. Any such sequence is acceptable.

translation:
## 题目描述

奶牛在激烈地下跳棋。

不幸的是，尽管他们玩得很开心，但他们在最后阶段很艰难，需要你的帮助。

给定一个 $N \times N(4 \le N \le 500)$ 的棋盘，确定帮助贝西“吃”掉**所有对方棋子**的移动次数最少的路径。

移动规则：

1. 沿对角线方向移动。

1. 必须越过对方棋子到达下一个位子。

1. 被越过的对方棋子视为“吃”掉。

1. 贝西只能操控她的其中**1**个国王**连续**移动。

请看下面的例子，其中 $N=8$ ：

1. 对手棋子标记为 o

1. 贝西的国王标记为 K

1. 正在移动的国王标记为 >K<

```
初始状态             移动一次后          移动两次后           移动三次后
- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -
- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +
+ - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + -
- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +
+ - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + -
- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ ->K<- + - K -     + - + - + - K -    + - K - + - K -     + - K - + - K -

这次移动的路径（标记为 * ）：

  1 2 3 4 5 6 7 8          行 列
1 - + - + - + - +    起点:  8  3
2 + - + - + - + -    路径:  6  1
3 - + - K - + - +    路径:  4  3
4 + - * - + - + -    路径:  6  5
5 - o - o - + - +
6 * - K - * - + -
7 - o - + - + - +
8 + - K - + - K -
```

编写一个程序来确定贝西的国王的移动路径。棋盘上至少有一个国王和一个对手棋子。

### 输入格式

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

接下来 $N$ 行是一个 $N \times N$ 的矩阵，每个字符之间没有空格。

### 输出格式

若有一条路径，输出每行包含两个空格分隔的整数，表示一位国王的连续位置。

若没有这样的路径,则一行输出"impossible"。


title: [USACO08DEC] Largest Fence G

description:
Farmer John has purchased N (5 <= N <= 250) fence posts in order to build a very nice-looking fence. Everyone knows the best fences are convex polygons where fence posts form vertices of a polygon. The pasture is represented as a rectilinear grid; fencepost i is at integer coordinates (x\_i, y\_i) (1 <= x\_i <= 1,000; 1 <= y\_i <= 1000).

Given the locations of N fence posts (which, intriguingly, feature no set of three points which are collinear), what is the largest number of fence posts FJ can use to create a fence that is convex?

For test cases worth 45% of the points for this problem, N <= 65.

Time limit: 1.2 seconds

POINTS: 400

Farmer John的农场里有N（5<=N<=250）个篱笆桩，每个都有独一无二的坐标(xi,yi)（1<=xi,yi<=1000）。他想选择尽量多的篱笆桩来构建他的围栏。这个围栏要美观，所以必须是凸多边形的。那他最多能选多少个呢？

所有的篱笆桩中不存在三点共线。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 describes fence post i's location with two space-separated integers: x\_i and y\_i

outputFormat: \* Line 1: A single integer, the maximum possible number of fence posts that form a convex polygon.

hint:
A square with two points inside.

The largest convex polygon is the pentagon (2,3), (3,2), (5,1), (5,5), (1,5).


title: [USACO08DEC] Hay For Sale S

description:
Farmer John suffered a terrible loss when giant Australian cockroaches ate the entirety of his hay inventory, leaving him with nothing to feed the cows. He hitched up his wagon with capacity C (1 <= C <= 50,000) cubic units and sauntered over to Farmer Don's to get some hay before the cows miss a meal.

Farmer Don had a wide variety of H (1 <= H <= 5,000) hay bales for sale, each with its own volume (1 <= V\_i <= C). Bales of hay, you know, are somewhat flexible and can be jammed into the oddest of spaces in a wagon.

FJ carefully evaluates the volumes so that he can figure out the largest amount of hay he can purchase for his cows.

Given the volume constraint and a list of bales to buy, what is the greatest volume of hay FJ can purchase?  He can't purchase partial bales, of course. Each input line (after the first) lists a single bale FJ can buy.

约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草．  顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，

他最多可以运回多少体积的干草呢？

inputFormat:
\* Line 1: Two space-separated integers: C and H

\* Lines 2..H+1: Each line describes the volume of a single bale: V\_i

outputFormat: \* Line 1: A single integer which is the greatest volume of hay FJ can purchase given the list of bales for sale and constraints.

translation:
## 题目描述
农民 John 面临一个很可怕的事，因为防范力度不大所以他存储的所有稻草都被蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，John 拉着他的马车到农民 Don 的农场中买一些稻草给奶牛过冬。已知 John 的马车可以装的下 $C(1\le C\le5\times10^4)$ 立方的稻草。

农民 Don 有 $H(1\le H\le5\times10^3)$ 捆体积不同的稻草可供购买，每一捆稻草有它自己的体积 $V_i(1\le V_i\le C)$。面对这些稻草 John 认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。

现在给定马车的最大容积 $C$ 和每一捆稻草的体积 $V_i$，John 如何在不超过马车最大容积的情况下买到最大体积的稻草？他不可以把一捆稻草分开来买。

## 输入格式：
第一行两个整数，分别为 $C$ 和 $H$。
第 $2$ 到 $H+1$ 行:每一行一个整数代表第 $i$ 捆稻草的体积 $V_i$。

## 输出格式：

一个整数，为 John 能买到的稻草的体积。

###### 修改 by zhangsenhao6728

hint:
The wagon holds 7 volumetric units; three bales are offered for sale with volumes of 2, 6, and 5 units, respectively.

Buying the two smaller bales fills the wagon.


title: [USACO08DEC] Patting Heads S

description:
It's Bessie's birthday and time for party games! Bessie has instructed the N (1 <= N <= 100,000) cows conveniently numbered 1..N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1..1,000,000.

Each cow i then draws a number A\_i (1 <= A\_i <= 1,000,000) (which is not necessarily unique, of course) from the giant barrel.  Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number A\_i is exactly

divisible by cow j's number A\_j; she then sits again back in her original position.

The cows would like you to help them determine, for each cow, the number of other cows she should pat.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains a single integer: A\_i

outputFormat: \* Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.

translation:
今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。

贝茜让 $N$ ($1\leq N\leq 10^5$) 头奶牛坐成一个圈。除了 $1$ 号与 $N$ 号奶牛外，$i$ 号奶牛与 $i-1$ 号和 $i+1$ 号奶牛相邻。$N$ 号奶牛与 $1$ 号奶牛相邻。农夫约翰用很多纸条装满了一个桶，每一张包含了一个不一定是独一无二的 $1$ 到 $10^6$ 的数字。

接着每一头奶牛 $i$ 从桶中取出一张纸条 $A_i$。每头奶牛轮流走上一圈，同时拍打所有手上数字能整除在自己纸条上的数字的牛的头，然后坐回到原来的位置。牛们希望你帮助他们确定，每一头奶牛需要拍打的牛的数量。

hint:
The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.

The first cow pats the second and third cows; the second cows pats no cows; etc.


title: [USACO08DEC] Jigsaw Puzzles S

description:
The cows have taken up alphabetical jigsaw puzzles. In these puzzles with R (1 <= R <= 10) rows and C (1 <= C <= 10) columns, the edges are not funny-shaped cardboard shapes but rather are letters.

Each piece has a serial number and 4 letters (or borders) that must be aligned as in a regular jigsaw puzzle. The pseudo-letter '0' (the digit 0) will represent a border (and a piece can have several borders if it is a corner piece or even the top of column in a, e.g., 4x1 puzzle).  Below is a set of six pieces (the borders are marked with lines instead of '0's) assembled in one way (of many) that completes the puzzle:

+---+  +---+  +---+

| 1 c  c 3 d  d 5 |
+-d-+  + a +  +-e-+

+-d-+  +-a-+  +-e-+

| 2 b  b 4 b  b 6 |
+---+  +---+  +---+

Note that each edge letter of each piece matches the border letter of the piece adjacent to it; the borders appear properly on the top, bottom, and sides.

Pieces are represented by a serial number and a clockwise list of their four edges (where edges are the letters a..z and 0). Pieces might require rotation when placed in the puzzle.

Given a set of pieces, find at least one way to assemble them into a puzzle. Test data for puzzles with larger R and C are easier to solve because they have a more varied set of edge letters.

奶牛们在玩按字母表顺序排列的拼图谜题.每道谜题有R(1≤R≤10)列C(1≤C≤10)行的拼图块,它们边缘是由字母或封闭边界组成,完成后的整副拼图外围是边界线,中间的边界是字母.

每块拼图块都有一个序列号和4个字母或者数字表示边界线(顺序为上右下左),在输入中,数字充当边界线.

拼图可以换位和旋转,完成后的拼图在边缘的块上靠近外围的是边界线,拼图完成后,一块拼图若与另一块相邻,它们的边界字母必须相同,以下是一系列已经成功完成的拼图谜题共6块.

inputFormat:
\* Line 1: Two space-separated integers: R and C

\* Lines 2..R\*C+1: Each line contains five space-separated entities: an integer serial number and four edge identifiers

outputFormat: \* Lines 1..R\*C: Line R\*(i-1)+j describes the puzzle piece placed a row i, column j with an integer and five space-separated entities: the serial number of the puzzle piece and the four piece edge identifiers in the order top, right, bottom, left.

hint:
Describes the input puzzle although with some of the pieces rotated compared to the sample solution.

As shown in the diagram in the task text. Other solutions (like reflections) are possible; a grading program will check your answer.


title: [USACO09HOL] Cattle Bruisers G

description:
Canmuu is out for revenge after being utterly defeated by Bessie in paintball and has challenged Bessie to a video game.

In this game, Bessie starts out at point (BX, BY) in the coordinate grid (-1,000 <= BX <= 1,000; -1000 <= BY <= 1,000), and tries to escape, starting at time 0. She moves continuously at a velocity of (BVX, BVY) units/second (-100 <= BVX <= 100; -100 <= BVY <= 100). Thus, at time 1 she will be at point (BX + BVX, BY + BVY); at time 1.5 she will be at (BX + 1.5\*BVX, BY + 1.5\*BVY).

Unfortunately, Canmuu has sent N (1 <= N <= 50,000) cattle bruisers to pursue Bessie.  At time t=0, cattle bruiser i is at position (X\_i, Y\_i) (-1,000 <= X\_i <= 1,000; -1,000 <= Y\_i <= 1,000) with velocity (VX\_i, VY\_i) units/second (-1,000 <= VX\_i <= 1,000; -1,000 <= VY\_i <= 1,000).

Each cattle bruiser carries a 'proximity' weapon to fire at Bessie; the weapon can hurt Bessie when the cattle bruiser is no further than R (1 <= R <= 2,500) units from her.

Bessie has a shield to protect herself from these attacks. However, she does not want to waste any of her shield's power, so she would like to know the maximum number of cattle bruisers within firing range for any (potentially non-integer) time t >= 0.

In order to avoid precision errors with real numbers, it is guaranteed that the answer produced will be the same whether the attack range is decreased to R-0.0001 or increased to R+0.0001.

FEEDBACK: Your first 50  submissions for this problem will be run on some of the official test data, and you will receive a summary of the results.

自从卡门在弹珠游戏中被贝茜彻底击败，他一直在想找机会复仇.这会儿，他邀贝茜去玩一 个电脑游戏.

游戏中，贝茜在（BX,BY）处开始行动，这时时刻为0.她要试图 逃离.她的速度为(BVX，BVY)每秒.

不幸的是，卡门为了复仇，放出N(l<=N< =50000)个杀手追击贝茜.在t = 0时，杀手i的位置 是Xi, Yi他的速度是Vxi,Vyi每秒.

由于每个杀手配备了手枪，手枪的射程是R，也就是说贝茜要与这个杀手的距 离保持超过R，否则有性命之虞.

然而，贝茜还有一件秘密武器，盾.但是，她不想过多地消耗盾的能量.所以，她想知道在 逃脱过程中，某一个时刻她在最多为多少个杀手的射程内.当然这个时刻不一定是整数.

为了防止出现精度误差，数据保证在R 土 0.0001时也能得出正确结果.

inputFormat:
\* Line 1: Six space-separated integers: N, R, BX, BY, BVX, and BVY

\* Lines 2..N+1: Line i+1 contains four space-separated integers: X\_i, Y\_i, VX\_i, and VY\_i

outputFormat: \* Line 1: Print a single integer denoting the maximum number of cattle bruisers within attack range at any point in time.

hint:
Bessie starts at point (0, 0) and is moving at 2 units per second in the (positive) y-direction. There are 3 cattle bruisers, the first of which starts at point (0, -3) and travels 4 units per second in the y-direction. The maximum distance for a cattle bruiser to be in range of Bessie is 1 unit.

At time 1.5, Bessie is at point (0, 3), and the three bruisers are at points (0, 3), (-0.5, 3.5), and (4, -3.5). The first two cattle bruisers are within 1 unit of Bessie, while the third will never be within 1 unit of Bessie, so 2 is the most achievable.


title: [USACO09HOL] Transmission Delay G

description:
Farmer John has taken to yodeling from the top of the barn in order to communicate with the cows out in the pastures. Being bovine and all, cows can hear binary messages (0's and 1's) but have trouble with perfect communications because FJ's yodeling echoes off the silo. In fact, in a sequence of N (1 <= N <= 2,000) bits, Bessie will always receive a sequence of N bits, with the same number of 0s and 1s, but each 0 or 1 might be delayed.

Precisely speaking, for a given number D (0 <= D < N), the i-th bit might be heard as the j-th one as long as |i - j| <= D (in other words, no bit appears in a position farther than distance D from its original position).
Consider the following message as an example: 0110. Four possible messages might be heard if D = 1: 0101, 0110, 1001, and 1010.

Given the message to be yodeled by FJ, along with two numbers D and K (1 <= K <= 100,000,000), determine the number of different messages that might be heard by Bessie, modulo 100,000,000. Also determine the K-th smallest such message in lexicographical order (in binary representation, with 0 coming before 1). It is guaranteed that K will be no larger than the number of different possible messages.

MEMORY LIMIT: 32 MB

TIME LIMIT: 2 seconds

FEEDBACK: Your first 50 submissions for this problem will be run on some of the official test data, and you will receive a summary of the results.

约翰在屋顶上唱歌，以此来与奶牛们交流。但是奶牛们的听力很奇怪，她们只能听到约翰的歌声变成 $0$ 和 $1$ 构成的信息串时的样子。约翰的声音里有 $N  (1 \leq N \leq 2000)$ 个 $0$ 或 $1$，奶牛听到的也是 $N$ 个，而且 $0$ 和 $1$ 的数量不会变化，但是一部分 $0$ 或 $1$ 可能偏离原来的位置，这就是约翰的歌声在传输时发生的“传输延迟”现象。$0$ 或 $1$ 的偏离距离不会超过 $D(O \leq D < N)$，也就是说某一个码的原本位置和现在的位置之差的绝对值不大于 $D$。

比如，对于 `0110`，$D = 1$，传输延迟发生后可能出现 `0101`，`0110`，`1001`，`1010` 这四种串．

给出约翰歌声的 $01$ 串形式和一个整数 $K(1 \leq K \leq10^8)$，请计算传输延迟发生后一共有多少种可能的 $01$ 串，以及其中第 $K$ 大的串是什么。

inputFormat:
\* Line 1: Three space-separated integers: N, D, and K

\* Line 2: FJ's binary message, containing exactly N bits

outputFormat:
\* Line 1: The number of different possible messages that can heard by Bessie, mod 100,000,000

\* Line 2: The K-th smallest such message (in binary representation)

Note that if your program's first line of output is correct but the second line of output is either missing or wrong, you will receive 40% of the points for that test case.


title: [USACO09HOL] Holiday Painting G

description:
To show their spirit for the holidays, the cows would like to paint a picture! Their picture will be represented as an R x C (1 <= R <= 50,000; 1 <= C <= 15) grid of unit squares, each of which is either 0 or 1. The grid rows are conveniently numbered 1..R; the columns are numbered 1..C.

Being pressed for time, the cows have asked their neighbors north of the border for help. Under the very helpful supervision of Canmuu the moose, they constructed a machine to throw paint at the picture in entire buckets! Beginning with all 0's in the picture grid, the machine splashes a certain paint color (either 0 or 1) over a

rectangle in the grid. In particular, Canmuu suggested that they perform Q (1 <= Q <= 10,000) operations; operation i consists of five integers R1\_i, R2\_i, C1\_i, C2\_i, and X\_i (1 <= R1\_i <= R2\_i <= R; 1 <= C1\_i <= C2\_i <= C; 0 <= X\_i <= 1), meaning that the cows will paint each unit square with a row index between R1\_i and R2\_i, inclusive, and a column index between C1\_i and C2\_i, inclusive, with color X\_i.

However, painting a picture like this is quite prone to mistakes. So Canmuu has enlisted you to determine, after each operation, the number of unit squares in the grid which are the correct color.

MEMORY LIMIT: 64 MB

TIME LIMIT: 1.5 seconds

为了表达假日的激情，奶牛们要画一幅巨大的画。

画布可以分成$R\times C$个方格，从上到下编为 $1$ 到 $R$ 行，从左到右编为 $1$ 到 $C$ 列。作画的颜色有两种，白色（用 $0$ 表示）或者黑色（用 $1$ 表示）。

由于时间紧迫，奶牛们不得不请教北面的邻居，卡门。卡门送给它们一台机器，一次操作只输入5个参数 $R1_i,R2_i,C1_i,C2_i,X_i$ $(1 \le R1_i \le R2_i \le R;1 \le C1_i \le C2_i \le C;0 \le X_i \le 1)$，把 $R1_i$ 行到 $R2_i$ 行，$C1_i$ 列到 $C2_i$ 列的一个大长方形涂成 $X_i$ 色。在所有操作还未进行的时候，画布是白色的。

奶牛们一共要进行 $Q$ 次操作。

因为这样的画法总要出些差错，所以奶牛们想请你算算，每一次操作过后，一共有多少个方格与它们的目标画里对应的方格是同色的。

inputFormat:
\* Line 1: Three space-separated integers: R, C, and Q

\* Lines 2..R+1: Line i+1 contains C characters, each '0' or '1', denoting the i-th row of the grid in the obvious way.

\* Lines R+2..R+Q+1: Line R+i+1 contains five space-separated integers representing a paint operation: R1\_i, R2\_i, C1\_i, C2\_i, and X\_i

outputFormat: \* Lines 1..Q: On line i+1, print a single integer representing the number of matching unit squares after the i-th operation.


title: [USACO09HOL] Pearl Bracelet G【征集 SPJ】

description:
Bessie received a magic bracelet of a set of the rarest black pearls for her favorite holiday. Bessie loved the bracelet and marveled that each pearl contained a small number engraved on it. She noticed that if you align the the bracelet's pearls in all the possible ways by bending it around some point (see below), the 'progressive' sums of the pearls' numbers that have corresponding numbers on the top and bottom sides of the bracelet never, everatch when compared using mod M (2 <= M <= 100). 'Progressive' sums are exemplified below.

Suppose the mod M is 3. Consider a bracelet with N=6 pearls, etched sequentially with the numbers 0, 1, 0, 2, 1, 0. We'll illustrate this bracelet with its clasps like this:

>0-1-0-2-1-0<
The six-pearl bracelet can be laid out on the ground in five different ways so that some pearls 'correspond' to each other (see below). We can 'progressively' sum-mod-M those pearls that correspond on the top and also sum-mod-M the corresponding pearls on the bottom, as shown with ONE-sums, TWO-sums, THREE-sums (and so on when N > 6).

```cpp
               |     THREE-sums         |     TWO-sums      | ONE-sums
 --------------+------------------------+-------------------+---------
    >0-1-0-2-1 |                        |                   | => 1 |
               |                        |                   |
            >0 |                        |                   | => 0
 --------------+------------------------+-------------------+---------
      >0-1-0-2 |                        | => 0+2 = 2        | => 2 |
               |                        |                   |
          >0-1 |                        | => 0+1 = 1        | => 1
 --------------+------------------------+-------------------+---------
        >0-1-0 | => 0+1+0 = 1           | => 1+0 = 1        | => 0 |
               |                        |                   |
        >0-1-2 | => 0+1+2 = 3 mod 3 = 0 | => 1+2 mod 3 = 0  | => 2
 --------------+------------------------+-------------------+---------
          >0-1 |                        | => 0+1 = 1        | => 1 |
               |                        |                   |
      >0-1-2-0 |                        | => 2+0 = 2        | => 0
 --------------+------------------------+-------------------+---------
            >0 |                        |                   | => 0 |
               |                        |                   |
    >0-1-2-0-1 |                        |                   | => 1
```

Bessie notes that all the pairs of sums contain different numbers and has heard this is true for all the magic bracelets. Bessie wondered what is longest possible bracelet that has this unique-sum property.

Given M, find a really long (but no longer than 20,000) set of numbers can be etched on the black pearls to maintain this unique sum property for a bracelet.

This is an output-only problem, the 15 input files can be downloaded at: http://ace.delos.com/perlbrac.zip

SCORING: Scoring for this problem will be relative; your integer score (out of 10) for each test case will be int (10 \* sqrt (YOURS / BEST)), where YOURS is the length of your solution, and BEST is the length of the best solution among all contestants.

FEEDBACK: When you submit a file for grading, it will be checked for both correct format and validity (i.e., whether it satisfies the required numerical properties), and you will be informed of the results.

inputFormat: \* Line 1: Two space-separated integers: the case number and M

outputFormat:
\* Line 1: A single line containing the task name and case number: #FILE perlbrac CASENUM

\* Line 2: A single line with a single integer, N (which must be no larger than 20,000)

\* Lines 3..N+1: Line i+2 contains a single integer that is the integer etched onto the i-th pearl on the bracelet; this number should be between 0 and M - 1, inclusive

translation:
给出模数 $m$，构造一个尽可能长的的序列 $a_i$（但长度不要超过 $20000$），满足其任意两个相邻的长度相等的子区间的和在模 $m$ 意义下均不同。

对于每个测试点，你的得分为该测试点的总分值乘上 $\dfrac{YOURS}{BEST}$。其中 $YOURS$ 表示你构造的长度，$BEST$ 表示最优解的长度。


title: [USACO09JAN] Earthquake Damage G

description:
Wisconsin has had an earthquake that has struck Farmer John's farm! The earthquake has damaged some of the pastures so that they are unpassable. Remarkably, none of the cowpaths was damaged.

As usual, the farm is modeled as a set of $P(1 \le P \le 30,000)$ pastures conveniently numbered $1\ldots P$ which are connected by a set of $C (1 \le C \le 100,000)$ non-directional cowpaths conveniently numbered $1\ldots C$. Cowpath $i$ connects pastures $a_i$ and $b_i (1 \le a_i \le P; 1 \le b_i \le P)$. Cowpaths might connect $a_i$ to itself or perhaps might connect two pastures more than once.  The barn is located in pasture $1$.

A total of $N (1 \le N \le P)$ cows (in different pastures) sequentially contact Farmer John via moobile phone with an integer message $report_j (2 \le report_j \le P)$ that indicates that pasture $report_j$ is undamaged but that the calling cow is unable to return to the barn from pasture $report_j$ because she could not find a path that does not go through damaged pastures.

After all the cows report in, determine the minimum number of pastures (including ones that are uncrossable) from which it is not possible to return to the barn.

Note: Feedback on some of the test data will be provided on the first $50$ submissions.

inputFormat:
Line $1$: Three space-separated integers: $P$,$C$,and $N$.

Lines $2\ldots C+1$: Line $i+1$ describes cowpath $i$ with two integers: $a_i$ and $b_i$.

Lines $C+2\ldots C+N+1$: Line $C+1+j$ contains a single integer: $report_j$.

outputFormat: Line $1$: A single integer that is the minimum count of pastures from which a cow can not return to the barn (including the damaged pastures themselves)

translation:
### 题目描述

农夫 John 的农场遭受了一场地震。有一些牛棚遭到了损坏，但幸运地，所有牛棚间的路经都还能使用。FJ 的农场有 $P(1 \le P \le 3\times 10^4)$ 个牛棚，编号 $1\ldots P$。$C(1 \le C \le 1\times 10^5)$ 条双向路径连接这些牛棚,编号为 $1\ldots C$，路经 $i$ 连接牛棚 $a_i$ 和 $b_i (1 \le a_i \le P;1 \le b\_i \le P)$。$a_i$ 与 $b_i$ 可能相同，两个牛棚之间可能有多条路经。农庄在编号为 $1$ 的牛棚。$N (1
\le N \le P)$ 头在不同牛棚的牛通过手机短信告诉 FJ 它们的牛棚 $report_j(2 \le report_j \le P)$ 没有损坏，但是它们无法通过路径和没有损坏的牛棚回到到农场。当 FJ 接到所有短信之后，找出最小的不可能回到农庄的牛棚数目。这个数目包括损坏的牛棚。注意：前 $50$ 次提交将提供在一些测试数据上的运行结果。

hint: Pasture $2$ is damaged, resulting in cows in pastures $2, 3, 4$ not being able to return to the barn.


title: [USACO09JAN] The Baric Bovine G

description:
Following up on a journal article about increasing milk production, Bessie has become the Baric Bovine by studying atmospheric pressure in order to curry favor with Farmer John.

She takes N (1 <= N <= 100) measurements conveniently named M\_1 through M\_N during the day (1 <= M\_i <= 1,000,000); these measurements are numbered in the order in which Bessie observed them.

In order to characterize the day's atmospheric pressure readings, she is interested in finding a subset of the measurements (given by the K (1 <= K <= N) indices s\_j where 1 <= s\_1 < s\_2 < ... < s\_K <= N) that accurately reflects the entire set, i.e., limits the error as described below.

In any subset of measurements, an error is incurred for each

measurement (1) before the first member of the subset, (2) between two consecutive measurements in the subset, and (3) after the last member of the subset. The total error value for a given set of s\_j values is the sum of each of the individual errors.

Specifically, for all measurements whose index i is not one of the s\_j values:

```cpp
* if i is less than s_1, then the sample error is:
2 * | M_i - M_(s_1) |
* if i is between s_j and s_(j+1), then the sample error is
| 2 * M_i - Sum(s_j, s_(j+1)) |
where Sum(x, y) = M_x + M_y;
* if i is greater than s_K, then the sample error is
2 * | M_i - M_(s_K) |
Given a maximum error value E (1 <= E <= 1,000,000), determine the size of the smallest subset of measurements that produces an error of at most E.
```

inputFormat:
\* Line 1: Two space-separated integers: N and E

\* Lines 2..N+1: Line i+1 contains a single integer: M\_i

outputFormat: \* Line 1: Two space-separated integers: the size of the smallest subset of measurements that produces an error of at most E and the least possible error for the subset of that size.

translation:
## 题目描述

为了研究农场的气候，Bessie 帮助农夫 John 做了  $N$ 次气压测量并按顺序记录了结果  $M_1 \cdots M_n$。Bessie 想找出一部分测量结果来总结一整天的气压分布。她想用  $K(1 \leq K \leq N)$ 个数  $s_j (1 \leq s_1 < s_2 < \cdots < s_K \leq N)$ 来概括所有测量结果。她想限制如下的误差: 对于任何测量结果子集，每一个非此子集中的结果都会产生误差。总误差是所有测量结果的误差之和。更明确地说，对于每一个和所有  $s_j$ 都不同的  $i$：

- 如果  $i$ 小于  $s_1$, 误差是： $2 \times | M_i - M_{(s_1)} |$；
- 如果  $i$ 在  $s_j$ 和  $s_{(j+1)}$ 之间，误差是： $| 2 \times M_i - \operatorname{Sum}(s_j, s_{(j+1)}) |$。注： $\operatorname{Sum}(x, y) = M_x + M_y$  ( $M_x$ 和  $M_y$ 之和)；
- 如果  $i$ 大于  $s_K$ ,误差为： $2 \times | M_i - M_{(s_K)} |$ 给出最大允许的误差  $E$，找出最小的一部分结果使得误差最多为  $E$。

## 输入格式

- 第  $1$ 行：两个用空格分开的正整数  $N$ 和  $E$。

- 第  $2\cdots N+1$ 行：第  $i+1$ 行包含单独的一个正整数  $M_i$。

## 输出格式

- 第  $1$ 行：两个用空格分开的整数，分别代表着最小的使得误差小于等于  $E$ 的测量结果子集元素的数量和其能达到的最小误差值。

## 说明/提示

### 数据范围

对于所有数据， $1 \leq N \leq 100$， $1 \leq M_i \leq 1,000,000$， $1 \leq E \leq 1,000,000$。

### 样例说明

Bessie 做了 4 次测量，最大允许的误差是 20。测量的结果分别为 10，3，20 和 40。

选择第二次和第四次测量结果是最佳的，误差为 17。第一个结果的误差为  $2\times|10-3|=14$，第三个的为  $|2\times20-(3+40)|=3$。

hint:
Bessie takes four measurements; the maximum error is 20. The

measurements are, in sequence: 10, 3, 20, and 40.

Choosing the second and fourth measurements is the best option, giving an error of 17. The first term's error is 2\*|10-3| = 14; the third term's error is |2\*20 - (3+40)| = 3.


title: [USACO09JAN] Safe Travel G

description:
Gremlins have infested the farm. These nasty, ugly fairy-like

creatures thwart the cows as each one walks from the barn (conveniently located at pasture\_1) to the other fields, with cow\_i traveling to from pasture\_1 to pasture\_i. Each gremlin is personalized and knows the quickest path that cow\_i normally takes to pasture\_i. Gremlin\_i waits for cow\_i in the middle of the final cowpath of the quickest route to pasture\_i, hoping to harass cow\_i.

Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly  different route from pasture\_1 (the barn) to pasture\_i.

Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow\_i that avoid gremlin\_i who is located on the final cowpath of the quickest route from pasture\_1 to

pasture\_i.

As usual, the M (2 <= M <= 200,000) cowpaths conveniently numbered 1..M are bidirectional and enable travel to all N (3 <= N <= 100,000) pastures conveniently numbered 1..N. Cowpath i connects pastures a\_i (1 <= a\_i <= N) and b\_i (1 <= b\_i <= N) and requires t\_i (1 <= t\_i <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (a\_i != b\_i). Best of all, the shortest path regularly taken by cow\_i from pasture\_1 to pasture\_i is unique in all the test data supplied to your program.

By way of example, consider these pastures, cowpaths, and [times]:

```cpp
1--[2]--2-------+
|       |       |
[2]     [1]     [3]
|       |       |
+-------3--[4]--4
```
```
TRAVEL     BEST ROUTE   BEST TIME   LAST PATH
p_1 to p_2       1->2          2         1->2
p_1 to p_3       1->3          2         1->3
p_1 to p_4      1->2->4        5         2->4
```
When gremlins are present:

```cpp
TRAVEL     BEST ROUTE   BEST TIME    AVOID
p_1 to p_2     1->3->2         3         1->2
p_1 to p_3     1->2->3         3         1->3
p_1 to p_4     1->3->4         6         2->4
```
For 20% of the test data, N <= 200.

For 50% of the test data, N <= 3000.

TIME LIMIT: 3 Seconds

MEMORY LIMIT: 64 MB

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: Three space-separated integers: a\_i, b\_i, and t\_i

outputFormat: \* Lines 1..N-1: Line i contains the smallest time required to travel from pasture\_1 to pasture\_i+1 while avoiding the final cowpath of the shortest path from pasture\_1 to pasture\_i+1. If no such path exists from pasture\_1 to pasture\_i+1, output -1 alone on the line.

translation:
**【题目描述】**

给定一张有 $n$ 个节点，$m$ 条边的无向图，对于任意的 $i$（$2\le i\le n$），请求出在不经过原来 $1$ 节点到 $i$ 节点最短路上最后一条边的前提下，$1$ 节点到 $i$ 节点的最短路。

特别地，保证 $1$ 到任何一个点 $i$ 的最短路都是唯一的。

**【输入格式】**

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

之后 $m$ 行，每行三个整数 $a_i,b_i,t_i$ 表示有一条 $a_i$ 到 $b_i$，边权为 $t_i$ 的无向边。

**【输出格式】**

共 $n-1$ 行，第 $i$ 行表示 $1$ 到 $i+1$ 在不经过原来 $1$ 节点到 $i+1$ 节点最短路上最后一条边的前提下的最短路。如果最短路不存在，则在对应行输出 `-1`。

翻译贡献者：@[cryozwq](/user/282751)。

hint: 感谢 karlven 提供翻译。


title: [USACO09JAN] Best Spot S

description:
Bessie, always wishing to optimize her life, has realized that she really enjoys visiting F (1 <= F <= P) favorite pastures F\_i of the P (1 <= P <= 500; 1 <= F\_i <= P) total pastures (conveniently

numbered 1..P) that compose Farmer John's holdings.

Bessie knows that she can navigate the C (1 <= C <= 8,000) bidirectional cowpaths (conveniently numbered 1..C) that connect various pastures to travel to any pasture on the entire farm. Associated with each path P\_i is a time T\_i (1 <= T\_i <= 892) to traverse that path (in either direction) and two path endpoints a\_i and b\_i (1 <= a\_i <= P; 1 <= b\_i <= P).

Bessie wants to find the number of the best pasture to sleep in so that when she awakes, the average time to travel to any of her F favorite pastures is minimized.

By way of example, consider a farm laid out as the map below shows, where \*'d pasture numbers are favorites. The bracketed numbers are times to traverse the cowpaths.

```cpp

            1*--[4]--2--[2]--3
                     |       |
                    [3]     [4]
                     |       |
                     4--[3]--5--[1]---6---[6]---7--[7]--8*
                     |       |        |         |
                    [3]     [2]      [1]       [3]
                     |       |        |         |
                    13*      9--[3]--10*--[1]--11*--[3]--12*
```
The following table shows distances for potential 'best place' of pastures 4, 5, 6, 7, 9, 10, 11, and 12:

```cpp
      * * * * * * Favorites * * * * * *
 Potential      Pasture Pasture Pasture Pasture Pasture Pasture     Average
Best Pasture       1       8      10      11      12      13        Distance
------------      --      --      --      --      --      --      -----------
    4              7      16       5       6       9       3      46/6 = 7.67
    5             10      13       2       3       6       6      40/6 = 6.67
    6             11      12       1       2       5       7      38/6 = 6.33
    7             16       7       4       3       6      12      48/6 = 8.00
    9             12      14       3       4       7       8      48/6 = 8.00
   10             12      11       0       1       4       8      36/6 = 6.00 ** BEST
   11             13      10       1       0       3       9      36/6 = 6.00
   12             16      13       4       3       0      12      48/6 = 8.00

```
Thus, presuming these choices were the best ones (a program would have to check all of them somehow), the best place to sleep is pasture 10.

约翰拥有 $P(1 \leq P \leq 500)$ 个牧场，贝茜特别喜欢其中的 $F$ 个。所有的牧场由 $C(1 < C \leq 8000)$条双向路连接，第 $i$ 条路连接着 $a_i,b_i$，需要 $T_i(1 \leq T_i < 892)$ 个单位时间来通过。

作为一只总想优化自己生活方式的奶牛，贝茜喜欢自己某一天醒来，到达所有那 $F$ 个她喜欢的牧场的平均需时最小。那她前一天应该睡在哪个牧场呢？请帮助贝茜找到这个最佳牧场。

由样例解释可见，在样例环境下，牧场 $10$ 到所有贝茜喜欢的牧场的平均距离最小，为最佳牧场。

inputFormat:
\* Line 1: Three space-separated integers: P, F, and C

\* Lines 2..F+1: Line i+2 contains a single integer: F\_i

\* Lines F+2..C+F+1: Line i+F+1 describes cowpath i with three

space-separated integers: a\_i, b\_i, and T\_i

outputFormat: \* Line 1: A single line with a single integer that is the best pasture in which to sleep. If more than one pasture is best, choose the smallest one.

hint:
As the problem statement

As the problem statement.


title: [USACO09JAN] Total Flow S

description:
Farmer John always wants his cows to have enough water and thus has made a map of the N (1 <= N <= 700) water pipes on the farm that connect the well to the barn. He was surprised to find a wild mess of different size pipes connected in an apparently haphazard way. He wants to calculate the flow through the pipes.

Two pipes connected in a row allow water flow that is the minimum of the values of the two pipe's flow values. The example of a pipe with flow capacity 5 connecting to a pipe of flow capacity 3 can be reduced logically to a single pipe of flow capacity 3:

```plain
+---5---+---3---+    ->    +---3---+
```

Similarly, pipes in parallel let through water that is the sum of their flow capacities:

```plain
   +---5---+
---+       +---    ->    +---8---+
   +---3---+
```

Finally, a pipe that connects to nothing else can be removed; it contributes no flow to the final overall capacity:

```plain
   +---5---+
---+               ->    +---3---+
   +---3---+--
```

All the pipes in the many mazes of plumbing can be reduced using these ideas into a single total flow capacity.

Given a map of the pipes, determine the flow capacity between the well (A) and the barn (Z).

Consider this example where node names are labeled with letters:

```plain
         +-----------6-----------+
A+---3---+B                      +Z
         +---3---+---5---+---4---+
                 C       D
```

Pipe BC and CD can be combined:

```plain
         +-----------6-----------+
A+---3---+B                      +Z
         +-----3-----+-----4-----+
                     D
```

Then BD and DZ can be combined:

```plain
         +-----------6-----------+
A+---3---+B                      +Z
         +-----------3-----------+
```

Then two legs of BZ can be combined:

```plain
         B
A+---3---+---9---+Z
```

Then AB and BZ can be combined to yield a net capacity of 3:

```plain
A+---3---+Z
```

Write a program to read in a set of pipes described as two endpoints and then calculate the net flow capacity from 'A' to 'Z'. All

networks in the test data can be reduced using the rules here.

Pipe i connects two different nodes a\_i and b\_i (a\_i in range

'A-Za-z'; b\_i in range 'A-Za-z') and has flow F\_i (1 <= F\_i <= 1,000). Note that lower- and upper-case node names are intended to be treated as different.

The system will provide extra test case feedback for your first 50 submissions.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N + 1: Line i+1 describes pipe i with two letters and an integer, all space-separated: a\_i, b\_i, and F\_i

outputFormat: \* Line 1: A single integer that the maximum flow from the well ('A') to the barn ('Z')

translation:
约翰总希望他的奶牛有足够的水喝，因此他找来了农场的水管地图，想算算牛棚得到的水的总流量。农场里一共有 $N$ 根水管。约翰发现水管网络混乱不堪，他试图对其进行简化。他简化的方式是这样的：

- 两根水管串联，则可以用较小流量的那根水管代替总流量。
- 两根水管并联，则可以用流量为两根水管流量和的一根水管代替它们。

当然，如果存在一根水管一端什么也没有连接，可以将它移除 。

请写个程序算出从水井 $\verb!A!$ 到牛棚 $\verb!Z!$ 的总流量。数据保证所有输入的水管网络都可以用上述方法简化 。

**注意**：输入数据中每个顶点用大写字母**或者**小写字母表示。也就是说，输入里可能出现用小写字母命名的节点。


title: [USACO09JAN] Laserphones S

description:
The cows have a new laser-based system so they can have casual conversations while out in the pasture which is modeled as a W x H grid of points (1 <= W <= 100; 1 <= H <= 100).

The system requires a sort of line-of-sight connectivity in order to sustain communication. The pasture, of course, has rocks and trees that disrupt the communication but the cows have purchased diagonal mirrors ('/' and '\' below) that deflect the laser beam through a 90 degree turn. Below is a map that illustrates the

problem.

H is 8 and W is 7 for this map.  The two communicating cows are notated as 'C's; rocks and other blocking elements are notated as '\*'s:

```plain
7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
0 1 2 3 4 5 6           0 1 2 3 4 5 6
```
Determine the minimum number of mirrors M that must be installed to maintain laser communication between the two cows, a feat which is always possible in the given test data.

inputFormat:
\* Line 1: Two space separated integers: W and H

\* Lines 2..H+1: The entire pasture.

outputFormat: \* Line 1: A single integer: M


title: [USACO09FEB] Stock Market G

description:
Despite their innate prudence, the cows took a beating in the home mortgage market and now are trying their hand at stocks. Happily, Bessie is prescient and knows not only today's S (2 <= S <= 50) stock prices but also the future stock prices for a total of D days (2 <= D <= 10).

Given the matrix of current and future stock prices on various days (1 <= PR\_sd <= 1,000) and an initial M (1 <= M <= 200,000) units of money, determine an optimal buying and selling strategy in order to maximize the gain realized by selling stock on the final day. Shares must be purchased in integer multiples, and you need not spend all the money (or any money). It is guaranteed that you will not be able to earn a profit of more than 500,000 units of money.

Consider the example below of a bull (i.e., improving) market, the kind Bessie likes most. In this case, S=2 stocks and D=3 days. The cows have 10 units of money to invest.

| Stock | Today's price | Tomorrow's price |    Two days hence Stock   |
| :---: | :-----------: | :--------------: | :--: |
|  $A$  |      10       |        15        |  15  |
|  $B$  |      13       |        11        |  20  |

If money is to be made, the cows must purchase stock 1 on day 1. Selling stock 1 on day 2 and quickly buying stock 2 yields 4 money in the bank and one share of 2. Selling stock 2 on the final day brings in 20 money for a total of 24 money when the 20 is added to the bank.

inputFormat:
\* Line 1: Three space-separated integers: S, D, and M

\* Lines 2..S+1: Line s+1 contains the D prices for stock s on days 1..D: PR\_sd

outputFormat: \* Line 1: The maximum amount of money possible to have after selling on day D.

translation:
# 题目描述
尽管奶牛天生谨慎，它们仍然在住房抵押信贷市场中大受打击，现在它们准备在股市上碰碰运气。贝西有内部消息，她知道 $S$ 只股票在今后 $D$ 天内的价格。

假设在一开始，她筹集了 $M$ 元钱，那么她该怎样操作才能赚到最多的钱呢？贝西在每天可以买卖多只股票，也可以多次买卖同一只股票，交易单位必须是整数，数量不限。举一个牛市的例子：

假设贝西有 10 元本金，股票价格如下：

| 股票 |  今天的价格 |  明天的价格 | 后天的价格  |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $A$ | 10 | 15 | 15 |
|$B$  | 13|  11|20  |

最赚钱的做法是：今天买入 $A$ 股 1 张，到明天把它卖掉并且买入 B 股 1 张，在后天卖掉 B股，这样贝西就有 24 元了。

# 输入格式
第一行：三个整数 S， D 和 M，$ 2 ≤ S ≤ 50$ ; $ 2 ≤ D ≤ 10$ ; $ 1 ≤ M ≤ 200000$

第二行到第 S + 1 行：第 i + 1 行有 D 个整数： $P_{i;1}$ 到 $P_{i;D}$，表示第 $i$ 种股票在第一天到最后一天的售价，对所有$ 1 ≤ j ≤ D$，$ 1 ≤ Pi$;$j ≤ 1000$
# 输出格式
 单个整数：表示奶牛可以获得的最大钱数，保证这个数不会超过 $500000$


title: [USACO09FEB] Revamping Trails G

description:
Farmer John dutifully checks on the cows every day. He traverses some of the M (1 <= M <= 50,000) trails conveniently numbered 1..M from pasture 1 all the way out to pasture N (a journey which is always possible for trail maps given in the test data). The N (1 <= N <= 10,000) pastures conveniently numbered 1..N on Farmer John's farm are currently connected by bidirectional dirt trails.  Each trail i connects pastures P1\_i and P2\_i (1 <= P1\_i <= N; 1 <= P2\_i <= N) and requires T\_i (1 <= T\_i <= 1,000,000) units of time to traverse.

He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose K (1 <= K <= 20) trails to turn into highways, which will effectively reduce the trail's traversal time to 0. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1 to N.

TIME LIMIT: 2 seconds

inputFormat:
\* Line 1: Three space-separated integers: N, M, and K

\* Lines 2..M+1: Line i+1 describes trail i with three space-separated integers: P1\_i, P2\_i, and T\_i

outputFormat: \* Line 1: The length of the shortest path after revamping no more than K edges

translation:
约翰一共有 $N$ 个牧场.由 $M$ 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 $1$ 出发到牧场 $N$ 去给奶牛检查身体。

通过每条小径都需要消耗一定的时间。约翰打算升级其中 $K$ 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 $0$。

请帮助约翰决定对哪些小径进行升级，使他每天从 $1$ 号牧场到第 $N$ 号牧场所花的时间最短。输出这一最短时间即可。

hint: K is 1; revamp trail 3->4 to take time 0 instead of 100. The new shortest path is 1->3->4, total traversal time now 1.


title: [USACO09FEB] The Leprechaun S

description:
Imagine Bessie's surprise as she spied a leprechaun prancing through the north pasture. Being no one's fool, she charged at the leprechaun at captured him with her prehensile hooves.

'One wish, bovine one. That's all I have for cows,' he said.

'Riches,' Bessie said dreamily. 'The opportunity for riches.'

Leprechauns never grant precisely the easiest form of their captor's wishes. As the smoke cleared from the location of a loud explosion, a shimmering donut spun slowly over the verdant green fields.

'I have made you a torus,' the leprechaun cooed. 'And on that torus is an N x N matrix (1 <= N <= 200) of integers in the range

-1,000,000..1,000,000 that will determine the magnitude of your riches. You must find the sequence of contiguous integers all in one row, one column, or on one diagonal that yields the largest sum from among all the possible sequences on the torus.'

Bessie pondered for a moment and realized that the torus was a device for 'wrapping' the columns, rows, and diagonals of a matrix so that one could choose contiguous elements that 'wrapped around' the side or top edge.

Bessie will share the matrix with you.  Determine the value of the largest possible sum (which requires choosing at least one matrix element).

By way of example, consider the 4 x 4 matrix on the left below that has all the elements from one exemplary 'wrapped' diagonal marked:

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

The marked diagonal of the right-hand matrix includes two nines (the highest available number) and a six for a total of 24. This is the best possible sum for this matrix and includes only three of the four possible elements on its diagonal.

你难以想象贝茜看到一只妖精在牧场出现时是多么的惊讶．她不是傻瓜，立即猛扑过去，用她那灵活的牛蹄抓住了那只妖精．

“你可以许一个愿望，傻大个儿！”妖精说．

“财富，”贝茜用梦游般的声音回答道，  “我要获得财富的机会．”

妖精从来没有碰到过这么简单的愿望．他在地方划出一大块N×N(1≤N≤200)的方格，每个格子上写上\_1,000,000到1,000,000之间的数字．他说：  “在方格上朝一个方向行走，可以是行的方向，列的方向，斜对角的方向，一步只能走一格，所有你踩过的数字的和就是你的财富．”

贝茜请你来帮忙，找到一行、一列或一条对角线上找一段连续的数字，它们的和最大．由于妖精方格的神奇特性，沿着一个方向走，走到了边际，再一步跨过去可以“绕”到方格的对边出现．一行两端的格子是相邻的，一列两端的格子也是相邻的，甚至相邻两行的分别两端的格子也是相邻的（斜对角方向）．

对于下图左边的方格，所有标记过的数字都在一条对角线上．

对于这个方格，能踩出来的最大的和是24，踩过的数字在右图中标记出来了

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains N space-separated integers that compose row i of the matrix

outputFormat: \* Line 1: A single integer that is the largest possible sum computable using the rules above


title: [USACO09FEB] Surround the Islands S

description:
Farmer John has bought property in the Caribbean and is going to try to raise dairy cows on a big farm composed of islands. Set in his ways, he wants to surround all the islands with fence.

Each island in the farm has the shape of a polygon. He fences the islands one side at a time (between a consecutive pair of vertices) and proceeds clockwise around a given island with his fencing

operations. Since he wants to fence all the islands, he must at some point travel to any other islands using a boat.

He can start fencing at any vertex and, at any vertex he encounters, travel to some vertex on another island, fence all the way around it, and then IMMEDIATELY return back to the same vertex on the original island using the same path he traveled before. Each boat trip has a cost defined by a supplied matrix.

The islands are described by a set of N (3 <= N <= 500) pairs of vertices V1,V2 (1 <= V1 <= N; 1 <= V2 <= N) although you must figure out how to assemble them into islands. The vertices are conveniently numbered 1..N.

The cost of traveling by boat between each pair of vertices is given by a symmetric cost matrix whose elements fall in the range 0..1000.

What is the minimum cost of surrounding the islands with the fence?

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Each line describes an island's border with two space-separated integers: V1 and V2

\* Lines N+2..2\*N+1: Line i-N-1 contains N integers that describe row i of the cost matrix: Row\_i

outputFormat: \* Line 1: A single integer that specifies the minimum cost of building the fence

translation:
**【题目描述】**

Farmer John 在加勒比海购置了一片地产，准备在由一系列岛屿组成的农场上养奶牛。 出于他的意愿，他要把所有的岛屿都用篱笆围上。
每个岛都是多边形的。每一次，FJ 会给多边形的一个边（即相邻的两个顶点之间）装上篱笆。对于整个岛屿，他会按照顺时针顺序装上篱笆。由于他想要给所有的岛屿都装上篱笆，某些时候，他必须从一个岛屿坐船到另一个岛屿去。
FJ 可以从任何一个顶点开始装篱笆，也可以从任何一个顶点坐船到另一个岛的某个顶点上，从这个顶点开始把该岛屿的篱笆全都装好，然后**马上**坐船原路返回。保证任意两个顶点间都有航线。在任意两个顶点之间坐船的费用会在一个矩阵中给出。
所有的岛屿由给定的 $N$ 对顶点 $V_1$，$V_2$ 描述（即：给定顶点 $V_1$ 与 $V_2$ 相邻）。每个顶点具体属于哪个岛屿**不会**在输入中给出。所有顶点由 $1$ 到 $N$ 标号。
在顶点间坐船旅行的费用由一个 $N \times N$ 的矩阵给出。保证两个岛屿间两个方向的旅行费用相等且不会超过 $1000$。
请求出 FJ 把篱笆装完所需要的最小花费。

**【输入格式】**

第 $1$ 行：包含一个整数 $N$，含义见题目描述。
第 $2$ 至第 $N+1$ 行：每行包含两个整数 $V_1$ 和 $V_2$，表示这两个顶点在同一个岛屿上且相邻。
第 $N+2$ 行至第 $2N+1$ 行：每行包含 $N$ 个整数，第 $i-N-1$ 行的第 $j$ 个整数表示从 $i$ 号顶点坐船到第 $j$ 号顶点的花费。

**【输出格式】**

一行一个整数，表示 FJ 把篱笆装完所需要的最小花费。

**【说明/提示】**

对于所有数据，保证：

+ $3 \leq n \leq 500$
+ $1 \leq V_1,V_2 \leq N$
+ 任意两个顶点之间的旅行花费 $\leq 1000$

hint:
1        10            4

xxxxxxx              x

xxxxxxxxx            xxxx

7 xxxxxxxxxxx 6        xxxxxxx

xxxxxxxxxxx       11 xxxxxxxxxx 5

xxxxxxx

xxx
3         12 xxxxxxx 2

xxxxxxxx

xxxxxxxx

xxxxxxxxx

xxxxxxxxx

xxxxxxxxxx

xxxxxxxxxx

8 xxxxxxxxxx 9

The example describes three islands: {1,7,3,6,10}, {4,5,11} and {2,9,8,12}. The travel costs are provided as a matrix. For example, the travel cost from vertex 1 to 2 is 15.

There is more than one solution. One is: FJ starts from vertex 3 then 7 and stops at 1, travels to 11 followed by 4,5,11. He then returns back to 1, and travels to 12 followed by 2,9,8,12. Finally, he returns back to 1 and continues with 10,6,3,7. The costs are 8 \* 2 = 16 for traveling from 1 to 11 and returning back, and 7 \* 2 = 14 for traveling from 1 to 12 and back -- a total cost of 30.


title: [USACO09MAR] Moon Mooing G

description:
A full moon casts some sort of spell on the cows and, like their cousins the wolves and coyotes, they bay at the moon -- mooing instead of howling, of course.

Each 'moo' lasts a certain amount of time. A short 'moo' might last time 1; a longer one might last time 24 or even 1,000,000,000 or longer (cows can really moo when they want to). No 'moo' will last more than or equal to 2^63.

It should come as no surprise that the cows have a pattern to their moos.  Bessie will choose an integer c (1 <= c <= 100) that is the initial length of a moo.

After Bessie moos for length c, the cows calculate times for

subsequent moos. They apply two formulae to each moo time to yield even more moo times. The two formulae are:

```cpp
f1(c)=a1*c/d1+b1 (integer divide, of course) and
f2(c)=a2*c/d2+b2.
They then successively use the two new times created by evaluating f1(c) and f2(c) to create even more mooing times. They keep a sorted list of all the possible mooing times (discarding duplicates).
They are allowed to moo a total of N times (1 <= N <= 4,000,000). Please determine the length of the longest moo before they must quit.
The constants in the formulae have these constraints: 1 <= d1 < a1; d1 < a1 <= 20; 0 <= b1 <= 20; 1 <= d2 < a2; d2 < a2 <= 20; 0 <= b2 <= 20.
Consider an example where c=3 and N=10. The constants are:
a1=4    b1=3     d1=3
a2=17   b2=8     d2=2
```
The first mooing time is 3, given by the value of c. The total list of mooing times is:
```cpp
1. c=3             ->  3       6. f2(3)=17*3/2+8  -> 33
2. f1(3)=4*3/3+3   ->  7       7. f1(28)=4*28/3+3 -> 40
3. f1(7)=4*7/3+3   -> 12       8. f1(33)=4*33/3+3 -> 47
4. f1(12)=4*12/3+3 -> 19       9. f1(40)=4*40/3+3 -> 56
5. f1(19)=4*19/3+3 -> 28      10. f1(47)=4*47/3+3 -> 65
The tenth time is 65, which would be the proper answer for this set of inputs.
```
Partial feedback will be provided on the first 50 submissions.
MEMORY LIMIT: 64MB

满月的时候，和狼一样，牛们也在月光下叫，他们从不嚎叫，而是哞叫。

每次哞叫都有一个时长，可能是 $1$ 秒，可能是 $10^9$ 秒或更久，牛们真的非常能叫.当然，没有哞叫时长会超过或等于 $2^{63}$。

牛们的哞叫可以找到规律，这并不奇怪。贝茜会选择一个整数 $c(c\le100)$ 来作为初始时长之后，牛们根据两条公式确定更多的时长：

$f_1(c)=\lfloor a_1c/d_1\rfloor+b_1$

$f_2(c)=\lfloor a_2c/d_2\rfloor+b_2$

牛们用这两条公式不断地迭代、计算，算得大量的时长.然后她们将这些时长排序，剔除重复的时长，最后取前 $N(1<N< 4000000)$ 个整数为她们 $N$ 次哞叫的时长.请你计算，第 $N$ 次哞叫的时长是多少。公式中的常量均为整数，满足下列关系：

$1 \le d_1 < a_1 \le 20$; $0\le b_1 \le 20$;

$1 \le d_2 < a_2 \le 20$; $0\le b_2\le 20$。

inputFormat:
\* Line 1: Two space-separated integers: c and N

\* Line 2: Three space-separated integers: a1, b1, and d1

\* Line 3: Three space-separated integers: a2, b2, and d2

outputFormat: \* Line 1: A single line which contains a single integer which is the length of the Nth moo


title: [USACO09MAR] Cleaning Up G

description:
In the good old days, Farmer John served a boring cuisine comprising but a single type of cow food to his N (1 <= N <= 40000) prize dairy cows. Times change. Today he serves the herd a total of M (1 <= M <= N) different types of food (conveniently numbered 1..M).

The cows are picky. Cow i has a single food preference P\_i (1 <= P\_i <= M) and will eat only that favorite food.

Each day at feeding time FJ converts the barn into a tastefully lit cafeteria. The cows line up outside to enter the cafeteria in order of their previously-mentioned convenient index number.

Unfortunately, with so many types of food, cleaning up afterwards is very time-consuming. If Farmer John is serving K different types of food, it takes him K\*K units of time to clean the barn.

To save time, FJ serves the cows in contiguous groups from the line. After each group, he cleans up the barn and sets out the food for the next group (of course, he only sets out food that cows in the any given group will eat). Determine the minimum amount of total time FJ must spend cleaning the barn. Each group consists of the next contiguous group of cows from the line; each cow belongs to exactly one group; and the barn must be cleaned up after every group, including the last one.

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 contains a single integer: P\_i

outputFormat: \* Line 1: A single integer: the minimum amount of time FJ must spend cleaning the  barn.

translation:
很久很久以前，约翰只会做一种食品；而现在约翰能给他的$N$ $(1 \leq N \leq 40000)$头奶牛供应$M$ $(1 \leq M \leq N)$种不同的食品。但奶牛们非常挑剔，$i$号奶牛只吃食品$P_i$ $(1 \leq P_i \leq M) $

每天，奶牛们按一定编号排队进自助餐厅用餐。不幸的是，这么多各类的食品会让清扫工作变得非常不方便。如果约翰在一次用餐中供应了$K$种食品，他之后就需要$K^2$的时间进行清扫。

为了减少清扫的时间，约翰决定把排好队的奶牛划分成若干组。每一组包含一段连续的奶牛。每一次，只让一组奶牛进入餐厅。这样，他可以让清扫所需的总用时变得最小。请计算这个最小用时。

### 样例解释：

如此划分：1\2\1\3\22\34343\1\4```

hint:
There are four types of food and thirteen cows in line. The first cow prefers type 1, the second type 2, the third type 1, etc.

The first four groups contain one cow each. The fifth group contains two cows who prefer food #2 (requiring one unit of time). The sixth group contains cows preferring foods 3, 4, 3, 4, 3 (and requires four units of time to clean). The last two groups contain one cow each. The total time is 11.


title: [USACO09MAR] Earthquake Damage 2 G

description:
Wisconsin has had an earthquake that has struck Farmer John's farm! The earthquake has damaged some of the pastures so that they are unpassable. Remarkably, none of the cowpaths was damaged.

As usual, the farm is modeled as a set of P (1 <= P <= 3,000)

pastures conveniently numbered 1..P which are connected by a set of C (1 <= C <= 20,000) non-directional cowpaths conveniently

numbered 1..C. Cowpath i connects pastures a\_i and b\_i (1 <= a\_i <= P; 1 <= b\_i <= P). Cowpaths might connect a\_i to itself or perhaps might connect two pastures more than once.  The barn is located in pasture 1.

A total of N (1 <= N <= P) cows (in different pastures) sequentially contacts Farmer John via moobile phone with an integer message report\_j (2 <= report\_j <= P) that indicates that pasture report\_j is undamaged but that the calling cow is unable to return to the barn from pasture report\_j because she could not find a path that does not go through damaged pastures.

After all the cows report in, determine the minimum number of

pastures that are damaged.

地震袭击了威斯康星州，一些牧场被摧毁了.

一共有P个牧场.由C条双向路连接.两个牧场间可能有多条路.一条路也可能连接相同的牧场.牛棚坐落在牧场1.

N (1 <= N <= P) 只奶牛打来了求救电话，说她们的农场没有被摧毁，但是已经无法到达牛棚. 求出最少可能有多少牧场被摧毁.

inputFormat:
\* Line 1: Three space-separated integers: P, C, and N

\* Lines 2..C+1: Line i+1 describes cowpath i with two integers: a\_i and b\_i

\* Lines C+2..C+N+1: Line C+1+j contains a single integer: report\_j

outputFormat: \* Line 1: One number, the minimum number of damaged pastures.

hint: Only pasture 2 being damaged gives such a scenario.


title: [USACO09MAR] Sand Castle S

description:
Farmer John has built a sand castle! Like all good castles, the walls have crennelations, that nifty pattern of embrasures (gaps) and merlons (filled spaces); see the diagram below. The N (1 <= N <= 25,000) merlons of his castle wall are conveniently numbered 1..N; merlon i has height M\_i (1 <= M\_i <= 100,000); his merlons often have varying heights, unlike so many.

He wishes to modify the castle design in the following fashion: he has a list of numbers B\_1 through B\_N (1 <= B\_i <= 100,000), and wants to change the merlon heights to those heights B\_1, ..., B\_N in some order (not necessarily the order given or any other order derived from the data).

To do this, he has hired some bovine craftsmen to raise and lower the merlons' heights. Craftsmen, of course, cost a lot of money. In particular, they charge FJ a total X (1 <= X <= 100) money per unit height added and Y (1 <= Y <= 100) money per unit height

reduced.

FJ would like to know the cheapest possible cost of modifying his sand castle if he picks the best permutation of heights. The answer is guaranteed to fit within a 32-bit signed integer.

Note: about 40% of the test data will have N <= 9, and about 60% will have N <= 18.

约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻枪眼中间那部分叫作“城齿”．    城墙上一共有N(1≤N≤25000)个城齿，每一个都有一个高度Mi.(1≤Mi≤100000)．现在约翰想把城齿的高度调成某种顺序下的Bi，B2，…，BN(1≤Bi≤100000). -个城齿每提高一个单位的高度，约翰需要X(1≤X≤100)元；每降低一个单位的高度，约翰需要Y(1≤y≤100)元．    问约翰最少可用多少钱达到目的．数据保证答案不超过2^31-1．

inputFormat:
\* Line 1: Three space-separated integers: N, X, and Y

\* Lines 2..N+1: Line i+1 contains the two space-separated integers: M\_i and B\_i

outputFormat: \* Line 1: A single integer, the minimum cost needed to rebuild the castle

hint:
FJ's castle starts with heights of 3, 1, and 1. He would like to change them so that their heights are 1, 2, and 2, in some order. It costs 6 to add a unit of height and 5 to remove a unit of height.

FJ reduces the first merlon's height by 1, for a cost of 5 (yielding merlons of heights 2, 1, and 1). He then adds one unit of height to the second merlon for a cost of 6 (yielding merlons of heights 2, 2, and 1).


title: [USACO09MAR] Cow Frisbee Team S

description:
老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $N$ 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 $i$ 头奶牛的能力为 $R_i$。飞盘队的队员数量不能少于 $1$、大于 $N$。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信，他的幸运数字是 $F$，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 $10^8$ 取模的值。

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

第二行到 $N+1$ 行：第 $i+1$ 行有一个整数 $R_i$，表示第 $i$ 头奶牛的能力。

outputFormat: 第一行：单个整数，表示方案数对 $10^8$ 取模的值。


title: [USACO09MAR] Look Up S

description:
Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once again standing in a row. Cow i has height H\_i (1 <= H\_i <= 1,000,000).

Each cow is looking to her left toward those with higher index numbers. We say that cow i 'looks up' to cow j if i < j and H\_i < H\_j. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.

Note: about 50% of the test data will have N <= 1,000.

约翰的 $N(1\le N\le10^5)$ 头奶牛站成一排，奶牛 $i$ 的身高是 $H_i(1\le H_i\le10^6)$。现在，每只奶牛都在向右看齐。对于奶牛 $i$，如果奶牛 $j$ 满足 $i<j$ 且 $H_i<H_j$，我们可以说奶牛 $i$ 可以仰望奶牛 $j$。 求出每只奶牛离她最近的仰望对象。

Input

inputFormat:
1. \* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains the single integer: H\_i

第 $1$ 行输入 $N$，之后每行输入一个身高 $H_i$。

outputFormat:
\* Lines 1..N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.

共 $N$ 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 $0$。

hint:
FJ has six cows of heights 3, 2, 6, 1, 1, and 2.

Cows 1 and 2 both look up to cow 3; cows 4 and 5 both look up to cow 6; and cows 3 and 6 do not look up to any cow.

【输入说明】$6$ 头奶牛的身高分别为 3,2,6,1,1,2。

【输出说明】奶牛 #1,#2 仰望奶牛 #3，奶牛 #4,#5 仰望奶牛 #6，奶牛 #3 和 #6 没有仰望对象。

【数据规模】

对于 $20\%$ 的数据：$1\le N\le10$；

对于 $50\%$ 的数据：$1\le N\le10^3$；

对于 $100\%$ 的数据：$1\le N\le10^5,1\le H_i\le10^6$。


title: [USACO09OPEN] Ski Lessons G

description:
Farmer John wants to take Bessie skiing in Colorado. Sadly, Bessie is not really a very good skier.

Bessie has learned that the ski resort is offering S (0 <= S <= 100) ski classes throughout the day. Lesson i starts at time M\_i (1 <= M\_i <= 10,000) and lasts for time L\_i (1 <= L\_i <= 10,000). After lesson i, Bessie's ski ability becomes A\_i (1 <= A\_i <= 100). Note: this ability is an absolute, not an incremental change.

Bessie has purchased a map which shows all N (1 <= N <= 10,000) ski slopes along with the time D\_i (1 <= D\_i <= 10,000) required to ski down slope i and the skill level C\_i (1 <= C\_i <= 100) required to get down the slope safely. Bessie's skill level must be greater than or equal to the skill level of the slope in order for her to ski down it.

Bessie can devote her time to skiing, taking lessons, or sipping hot cocoa but must leave the ski resort by time T (1 <= T <= 10,000), and that means she must complete the descent of her last slope without exceeding that time limit.

Find the maximum number of runs Bessie can complete within the time limit. She starts the day at skill level 1.

Extra feedback will be provided on the first 50 submissions.

inputFormat:
\* Line 1: Three space-separated integers: T, S, and N

\* Lines 2..S+1: Line i+1 describes ski lesson i with three

space-separated integers: M\_i, L\_i, and A\_i

\* Lines S+2..S+N+1: Line S+i+1 describes ski slope i with two

space-separated integers: C\_i and D\_i.

outputFormat: A single integer on a line by itself, the maximum number of runs that Bessie may ski within the time limit.

translation:
Farmer John 想要带着 Bessie 一起在科罗拉多州一起滑雪。很不幸，Bessie 滑雪技术并不精湛。Bessie了解到，在滑雪场里，每天会提供 $S(0 \le S \le 100)$ 门滑雪课。第 $i$ 节课始于 $M_i(1 \le M_i \le 10000)$ 上的时间为 $L_i(1 \le L_i \le 10000)$。

上完第 $i$ 节课后，Bessie 的滑雪能力会变成 $A_i(1 \le A_i \le 100)$. 注意：这个能力是绝对的，不是能力的增长值。

Bessie 买了一张地图，地图上显示了 $N(1 \le N \le 10,000)$ 个可供滑雪的斜坡，从第i个斜坡的顶端滑至底部所需的时长 $D_i(1 \le D_i \le 10000)$，以及每个斜坡所需要的滑雪能力 $C_i(1 \le C_i \le 100)$，以保证滑雪的安全性。Bessie 的能力必须大于等于这个等级，以使得她能够安全滑下。

Bessie 可以用她的时间来滑雪，上课，或者美美地喝上一杯可可汁，但是她必须在 $T(1 \le T \le 10000)$ 时刻离开滑雪场。这意味着她必须在 $T$ 时刻之前完成最后一次滑雪。 求 Bessie 在实现内最多可以完成多少次滑雪。这一天开始的时候，她的滑雪能力为 $1$.

hint: Ski the second slope once, take the lesson, and ski the first slope 5 times before time is up: a total of 6 slopes.


title: [USACO09OPEN] Work Scheduling G

description:
Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!).  He currently can choose from any of N (1 <= N <= 100,000) jobs

conveniently numbered 1..N for work to do. It is possible but

extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D\_i (1 <= D\_i <= 1,000,000,000). If he finishes job i by then, he makes a profit of P\_i (1 <= P\_i <= 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines?  The answer might not fit into a 32-bit integer.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains two space-separated integers: D\_i and P\_i

outputFormat: \* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

translation: 约翰有太多的工作要做。为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。 他的工作日从 $0$ 时刻开始，有 $10^9$ 个单位时间。在任一时刻，他都可以选择编号 $1$ 到 $N$ 的 $N(1 \leq N \leq 10^5)$ 项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。 对于第 $i$ 个工作，有一个截止时间 $D_i(1 \leq D_i \leq 10^9)$，如果他可以完成这个工作，那么他可以获利 $P_i( 1\leq P_i\leq 10^9 )$. 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少.

hint: Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).


title: [USACO09OPEN] Bovine Embroidery G

description:
Bessie has taken up the detailed art of bovine embroidery. Cows embroider a cloth mounted in a circular hoop of integer radius d (1 <= d <= 50,000). They sew N (2 <= N <= 50,000) threads, each in a straight line from one point on the edge of the hoop to another point on the edge of the hoop (no two embroidered points share a location on the hoop's edge).

Being mathematically inclined, Bessie knows a formula of the form ax + by + c = 0 for each straight line piece of thread. Conveniently, a, b, and c are integers (-1,000,000 <= a <= 1,000,000; -1,000,000 <= b <= 1,000,000; -1,000,000 <= c <= 1,000,000). Even more

conveniently, no two threads coincide exactly.

Perhaps less conveniently, Bessie knows that her set of formula coefficients also includes a number of formulae for threads that do not appear to pass inside the hoop's circle. She regrets this greatly.

The origin (0,0) is in the precise middle of the hoop, so all points on the hoop's edge are distance d from the origin. At least one of the coefficients a and b is non-zero for each thread's formula.

Bovine embroidery is more highly regarded when the number of thread intersections is maximized. Help Bessie: count the number of pairs of threads that intersect on the cloth (i.e., within distance d of the origin). Note that if three threads happen to coincide at the same point, that would be three pairs of intersections. Four threads at the same point -> six pairs of intersections, etc.

Bessie学会了刺绣这种精细的工作。牛们在一片半径为d(1 <= d <= 50000)的圆形布上绣花. 它们一共绣了N (2 <= N <= 50000)条直线，每条直线连接布的边缘上的两个点(没有两条线通过边上同一个点)。

作为一只热爱数学的牛，Bessie 知道每条线的公式, ax + by + c = 0. a, b, 和 c 为整数(-1000000 <= a <= 1000000; -1000000 <= b <= 1000000; -1000000 <= c <= 1000000).没有两条线完全重合。

不幸的是, 一部分线不通过圆布的内部. 原点(0,0)在布的正中央, 所有边上的点离原点距离为d. 每条线的公式满足至少a,b中的一个非零. 对于牛来说，刺绣作品中线的交点越多，便越有价值。帮助Bessie计算在圆中相交的线的对数，也就是说交点与原点的距离小于d。注意如果三条线在圆内同一点相交,这算3对线。4线共点->6对线.

inputFormat:
\* Line 1: Two space-separated integers: N and d

\* Lines 2..N+1: Line i+1 describes thread i with three integers: a, b, and c

outputFormat: \* Line 1: One integer, on a line by itself, that is the count of pairs of threads that intersect.

hint:
The two lines are x=0 and y=0.

The two lines intersect at (0,0), which is clearly with 1 of the origin.


title: [USACO09OPEN] Hide and Seek S

description:
Bessie is playing hide and seek (a game in which a number of players hide and a single player (the seeker) attempts to find them after which various penalties and rewards are assessed; much fun usually ensues).

She is trying to figure out in which of N (2 <= N <= 20,000) barns conveniently numbered 1..N she should hide. She knows that FJ (the seeker) starts out in barn 1. All the barns are connected by M (1 <= M <= 50,000) bidirectional paths with endpoints A\_i and B\_i (1 <= A\_i <= N; 1 <= B\_i <= N; A\_i != B\_i); it is possible to reach any barn from any other through the paths.

Bessie decides that it will be safest to hide in the barn that has the greatest distance from barn 1 (the distance between two barns is the smallest number of paths that one must traverse to get from one to the other). Help Bessie figure out the best barn in which to hide.

奶牛贝西和农夫约翰（FJ）玩捉迷藏，现在有N个谷仓，FJ开始在第一个谷仓，贝西为了不让FJ找到她，当然要藏在距离第一个谷仓最远的那个谷仓了。现在告诉你N个谷仓，和M个两两谷仓间的“无向边”。每两个仓谷间当然会有最短路径，现在要求距离第一个谷仓（FJ那里）最远的谷仓是哪个（所谓最远就是距离第一个谷仓最大的最短路径）？如有多个则输出编号最小的。以及求这最远距离是多少，和有几个这样的谷仓距离第一个谷仓那么远。

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: Line i+1 contains the endpoints for path i: A\_i and B\_i

第一行：两个整数N,M；

第2-M+1行：每行两个整数，表示端点A\_i 和 B\_i 间有一条无向边。

outputFormat:
\* Line 1: On a single line, print three space-separated integers: the index of the barn farthest from barn 1 (if there are multiple such barns, print the smallest such index), the smallest number of paths needed to reach this barn from barn 1, and the number of barns with this number of paths.

仅一行，三个整数，两两中间空格隔开。表示：距离第一个谷仓最远的谷仓编号（如有多个则输出编号最小的。），以及最远的距离，和有几个谷仓距离第一个谷仓那么远。

hint:
The farm layout is as follows:

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

Barns 4, 5, and 6 are all a distance of 2 from barn 1. We choose barn 4 because it has the smallest index.

这里谷仓4，5，6距离1号谷仓都是2，但是4编号最小所以输出4.因此最远距离是2且有3个谷仓，依次输出：2和3。

感谢 wjcwinmt 的贡献翻译