title: [USACO11NOV] Tile Exchanging S

description:
Farmer John wants to remodel the floor of his barn using a collection of square tiles he recently purchased from the local square mart store (which of course, only sells square objects).  Unfortunately, he didn't measure the size of the barn properly before making his purchase, so now he needs to exchange some of his tiles for new square tiles of different sizes.

The N square tiles previously purchased by FJ have side lengths A\_1...A\_N. He would like to exchange some of these with new square tiles so that the total sum of the areas of the his tiles is exactly M.  Square mart is currently offering a special deal: a tile of side length A\_i can be exchanged for a new tile of side length B\_i for a cost of

|A\_i-B\_i|\*|A\_i-B\_i| units. However, this deal only applies to
previously-purchased tiles -- FJ is not allowed to exchange a tile that he has already obtained via exchanging some other tile (i.e., a size-3 tile cannot be exchanged for a size-2 tile, which is then exchanged for a size-1 tile).

Please determine the minimum amount of money required to exchange tiles so that the sum of the areas of the tiles becomes M.  Output -1 if it is impossible to obtain an area of M.

inputFormat:
\* Line 1: Two space-separated integers, N (1<=N<=10) and M

(1<=M<=10,000).

\* Lines 2..1+N: Each line contains one of the integers A\_1 through A\_N, describing the side length of an input square

(1<=A\_i<=100).

outputFormat: \* Line 1: The minimum cost of exchanging tiles to obtain M units of total area, or -1 if this is impossible.

translation: 有 $N$ 个正方形，依次给出它们的边长，要求可以换掉一些正方形：如果边长为 $A_i$ 的正方形换成边长为 $B_i$ 的正方形所需代价为：$|A_i-B_i| \times |A_i-B_i|$。问至少花费多少代价使得这 $N$ 个正方形面积总和为 $M$？若无论如何也不可能使这 $N$ 个正方形面积总和为 $M$ 则输出 $-1$。

hint:
There are 3 tiles.  Two are squares of side length 3, and one is a square with side length 1.  We would like to exchange these to make a total area of 6.

Exchange one of the side-3 squares for a side-2 square, and another side-3 square for a side-1 square.  This gives the desired area of 4+1+1=6 and costs 4+1=5 units.

感谢 wjcwinmt 提供翻译


title: [USACO11NOV] Above the Median G

type: P

description:
Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height H\_i (1 <= H\_i <= 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair.

The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000).

For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.

Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.

给出一串数字，问中位数大于等于X的连续子串有几个。（这里如果有偶数个数，定义为偏大的那一个而非中间取平均）

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

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

outputFormat: \* Line 1: The number of subsequences of FJ's cows that have median at least X. Note this may not fit into a 32-bit integer.

hint:
FJ's four cows have heights 10, 5, 6, 2. We want to know how many contiguous subsequences have median at least 6.

There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.


title: [USACO11NOV] Binary Sudoku G

description:
Farmer John's cows like to play an interesting variant of the popular game of "Sudoku".  Their version involves a 9 x 9 grid of 3 x 3 subgrids, just like regular Sudoku.  The cows' version, however, uses only binary digits:

000 000 000

001 000 100

000 000 000

000 110 000

000 111 000

000 000 000

000 000 000

000 000 000

000 000 000

The goal of binary Sudoku is to toggle as few bits as possible so that each of the nine rows, each of the nine columns, and each of the nine 3 x 3 subgrids has even parity (i.e., contains an even number of 1s).  For the example above, a set of 3 toggles gives a valid solution:

000 000 000

001 000 100

001 000 100

000 110 000

000 110 000

000 000 000

000 000 000

000 000 000

000 000 000

Given the initial state of a binary Sudoku board, please help the cows determine the minimum number of toggles required to solve it.

给出一个9\*9的01矩阵，问最少修改几个数能使每行、每列以及每个九宫格中1的个数均为偶数。

inputFormat: \* Lines 1..9: Each line contains a 9-digit binary string corresponding to one row of the initial game board.

outputFormat: \* Line 1: The minimum number of toggles required to make every row, column, and subgrid have even parity.

hint:
The Sudoku board in the sample input is the same as in the problem text above.

Three toggles suffice to solve the puzzle.


title: [USACO11NOV] Cow Steeplechase G

description:
Farmer John has a brilliant idea for the next great spectator sport: Cow Steeplechase! As everyone knows, regular steeplechase involves a group of horses that race around a course filled with obstacles they must jump over. FJ figures the same contest should work with highly-trained cows, as long as the obstacles are made short enough.

In order to design his course, FJ makes a diagram of all the N (1 <= N <= 250) possible obstacles he could potentially build. Each one is represented by a line segment in the 2D plane that is parallel to the horizontal or vertical axis. Obstacle i has distinct endpoints (X1\_i, Y1\_i) and (X2\_i, Y2\_i) (1 <= X1\_i, Y1\_i, X2\_i, Y2\_i <= 1,000,000,000). An example is as follows:

```cpp

   --+-------
-----+-----
  ---+---     |
     |     |  |
   --+-----+--+-   |
     |     |  |  | |
     |   --+--+--+-+-
           |  |  | |
              |
```
FJ would like to build as many of these obstacles as possible, subject to the constraint that no two of them intersect. Starting with the diagram above, FJ can build 7 obstacles:

```cpp

   ----------
-----------
  -------     |
           |  |
           |  |    |
           |  |  | |
           |  |  | |
           |  |  | |
              |

```
Two segments are said to intersect if they share any point in common, even an endpoint of one or both of the segments.  FJ is certain that no two horizontal segments in the original input diagram will intersect, and that similarly no two vertical segments in the input diagram will intersect.

Please help FJ determine the maximum number of obstacles he can build.

给出 $N$ 条**平行于坐标轴**的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算）。横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段。

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

\* Lines 2..N+1: Line i+1 contains four space-separated integers representing an obstacle: X1\_i, Y1\_i, X2\_i, and Y2\_i.

outputFormat: \* Line 1: The maximum number of non-crossing segments FJ can choose.

hint:
There are three potential obstacles. The first is a horizontal segment connecting (4, 5) to (10, 5); the second and third are vertical segments connecting (6, 2) to (6, 12) and (8, 3) to (8, 5).

The optimal solution is to choose both vertical segments.


title: [USACO11DEC] Cow Photography G/S

description:
The cows are in a particularly mischievous mood today!  All Farmer John wants to do is take a photograph of the cows standing in a line, but they keep moving right before he has a chance to snap the picture.

Specifically, each of FJ's N (1 <= N <= 20,000) cows has a unique integer ID number.  FJ wants to take a picture of the cows standing in a line in a very specific ordering, represented by the contents of an array A[1...N], where A[j] gives the ID number of the jth cow in the ordering.  He arranges the cows in this order, but just before he can press the button on his camera to snap the picture, a group of zero or more cows (not necessarily a contiguous group) moves to a set of new positions in the lineup.  More precisely, a group of zero or more cows steps away from the line, with the remaining cows shifting over to close the resulting gaps in the lineup.  The cows who stepped away then re-insert themselves at different positions in the lineup (not necessarily at the locations they originally occupied).  Frustrated but not deterred, FJ again arranges his cows according to the ordering in A, but again, right before he can snap a picture, a different group of zero or more cows moves to a set of new positions in the lineup.

The process above repeats for a total of five photographs before FJ gives up.  Given the contents of each photograph, see if you can reconstruct the original intended ordering A.  Each photograph shows an ordering of the cows that differs from A in that some group of zero or more cows has moved. However, a cow only moves in at most one photograph: if a cow is part of the group that moves in one photograph, she will not actively move in any of the other four photographs (although she could end up at a different index as a consequence of other cows around her moving, of course).

Farmer John居然拍了五张照片，每张表示初始化牛位置的移动后的状态。然后求出FJ这五头牛初始化的样子。

inputFormat:
\* Line 1: The number of cows, N (1 <= N <= 20,000).

\* Lines 2..5N+1: The next 5N lines describe five orderings, each one a block of N contiguous lines.  Each line contains the ID of a cow, an integer in the range 0...1,000,000,000.

outputFormat: \* Lines 1..N: The intended ordering A, one ID per line.

translation:
## 题目描述

今天的奶牛们特别调皮！Farmer John 想做的只是给排成一排的奶牛拍照，但是在他拍下照片之前，奶牛们一直在移动。

具体地说，FJ 有 $N$ 头奶牛（$1 \leq N \leq 20\,000$），每头奶牛都有一个唯一确定的编号。FJ 想要以一个特定的顺序拍下一张奶牛排成一排的照片，这个顺序用数组 $A[1 \ldots N]$ 表示，其中 $A[i]$ 代表排在 $i$ 位置的奶牛的编号。

他按照这样的顺序将奶牛们排列好，但在他按下快门之前，有些奶牛（可能是零头或任意多头奶牛，位置也不一定连续）将移到一个新的位置。更准确地说，一些奶牛离开队列，剩下的奶牛靠拢，这些离开的奶牛再将自己重新插入到队列中的任意位置（不一定是他们之前的位置）。FJ 感到非常沮丧，他再次按照 $A$ 数组的顺序重新安排了队列。但在他再次按下快门之前，又有一些奶牛移动到了新的位置。

就这样，FJ 拍了五张照片。给出每张照片拍摄的内容（即 FJ 按下快门时奶牛的顺序），请你尝试推算出 FJ 最初为奶牛们排的顺序（即 $A$ 数组）。由于可能有奶牛移动，照片显示的顺序与原来的顺序可能有所不同。但是，一头奶牛最多只会移动一次：即如果一头奶牛在拍其中一张照片时移动了，它在拍其他四张照片的时候都不会移动。当然，由于其他奶牛也在移动，它在不同照片中的顺序并不一定相同。

## 输入格式

第一行包含一个整数 $N$。

接下来 $5N$ 行，每 $N$ 行描述了一张照片中各奶牛的顺序。每行包含一个奶牛的编号，保证所有编号都是不超过 $1\,000\,000\,000$ 的非负整数。

## 输出格式

输出 $N$ 行，每行一个整数 $A[i]$，即 FJ 最初为奶牛排好的顺序。

## 样例解释

FJ 拍的五张照片分别为：

- `10 20 30 40 50`
- `20 10 30 40 50`
- `30 10 20 40 50`
- `40 10 20 30 50`
- `50 10 20 30 40`

hint:
There are 5 cows, with IDs 10, 20, 30, 40, and 50.  In each of the 5 photos, a different cow moves to the front of the line (at most one cow moves in each photo here, but it is possible in other inputs that multiple cows could move in a particular photo).

The correct original ordering A[1..5] is 10, 20, 30, 40, 50.


title: [USACO11DEC] Umbrellas for Cows S

description:
Today is a rainy day! Farmer John's N (1 <= N <= 5,000) cows, numbered 1..N, are not particularly fond of getting wet. The cows are standing in roofless stalls arranged on a number line. The stalls span X-coordinates from 1 to M (1 <= M <= 100,000). Cow i stands at a stall on coordinate X\_i (1 <= X\_i <= M). No two cows share stalls.

In order to protect the cows from the rain, Farmer John wants to buy them umbrellas. An umbrella that spans coordinates X\_i to X\_j (X\_i <= X\_j) has a width of X\_j - X\_i + 1. It costs C\_W (1 <= C\_W <= 1,000,000) to buy an umbrella of width W.  Larger umbrellas do not necessarily cost more than smaller umbrellas.

Help Farmer John find the minimum cost it takes to purchase a set of umbrellas that will protect every cow from the rain.  Note that the set of umbrellas in an optimal solution might overlap to some extent.

在 X 数轴上有 M 个整数点，点的坐标分别是 1 至 M。有 N（1<= N<= 5000）只奶牛，编号为 1.. N，第 i 只奶牛所在的整数点坐标是 Xi（1<= Xi <= M <= 100,000）, 没有两头奶牛在相同的点上。现在正在下雨，为了保护奶牛，FJ 需要购买很多把雨伞，把所有的奶牛都遮住。如果一把雨伞能遮住坐标是 a 到坐标是 b 的这一段（a<=b），那么这把雨伞的宽度就是 b-a+1。现在我们给出购买宽度是 1 的雨伞的价格，购买宽度是 2 的雨伞的价格，…购买宽度是 M 的雨伞的价格。

这里特别需要注意：宽度更大的雨伞的价格不一定超过宽度较小的雨伞，这完全取决于读入数据。你的任务是帮助 FJ 找到购买雨伞最低的成本，使得这些雨伞能把所有的奶牛遮住，从而不淋雨。需要注意的是最佳的解决方案雨伞可能会重叠。

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

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

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

第 1 行：两个空间分隔的整数：N 和 M。

下来有 N 行，包含一个整数：Xi，表示第 i 头奶牛所在的点的坐标值。

接下来有 M 行：每行包含一个整数 Ci，表示购买宽度是 i 的雨伞的价格是 Ci 元。

outputFormat:
\* Line 1: A single integer that is the minimum cost needed to purchase umbrellas for all the cows.

一个整数，是最低的成本。

hint:
There are 12 stalls, and stalls 1, 2, 4, 8, 11, and 12 contain cows. An umbrella covering one stall costs 2, an umbrella covering two stalls costs 3, and so on.

By purchasing a size 4 umbrella, a size 1 umbrella, and a size 2 umbrella, it is possible to cover all the cows at a cost of 4+2+3=9:

UUUUUUUUUU           U        UUUU

C  C     C           C        C  C

|--|--|--|--|--|--|--|--|--|--|--|
1  2  3  4  5  6  7  8  9  10 11 12

C represents a cow and U represents a part of an umbrella.

1、 买一把长度是 4 的雨伞去遮住坐标在 1、2、4 的三头奶牛，费用是 4；

2、 买一把长度是 1 的雨伞遮住坐标在 8 的奶牛，费用是 2；

3、 买一把长度是 2 的雨伞遮住坐标在 11、12 的两头奶牛，费用是 3。

总费用是 4 +2+ 3 = 9。


title: [USACO16DEC] Lasers and Mirrors G

description:
For some reason, Farmer John's cows always seem to be running laser light shows.

出于某种原因，农夫约翰的牛总是在举行激光表演。

For their latest show, the cows have procured a large powerful laser -- so large,in fact, that they cannot seem to move it easily from the location where it was delivered. They would like to somehow send the light from the laser to the barn on the other side of FJ's property.  Both the laser and the barn can be considered to be located at points in the 2D plane on a map of FJ's farm.  The cows plan to point the laser so that it sends a beam of light out either horizontally or vertically (i.e.,  aligned with the x or y axes).  They will then bounce this beam off a number of mirrors to direct it to the barn.

对于他们的最新展会，奶牛已经购买了一个大功率的激光器 - 这么大，事实上，他们似乎不能轻易地从它交付的位置移动。他们想以某种方式将激光的光发送到FJ物业另一侧的谷仓。激光器和谷仓都可以被认为位于FJ农场的地图上的2D平面中的点上。牛计划指挥激光器，使得它发出水平或竖直（即，与x或y轴平行）的光束。他们会将这个光束从一些镜子反射回去，直接到谷仓。

On the farm there are $N$ fence posts ($1 \leq N \leq 100,000$) located at distinct 2D points (also distinct from the laser and the barn) at which the cows can mount mirrors.  The cows can choose not to mount a mirror on a fence post, in which case the laser would simply pass straight over the top of the post without changing direction.  If the cows do mount a mirror on a fence post, they align it diagonally like / or \ so that it will re-direct a horizontal beam of light in a vertical direction or vice versa.

在农场上有$N$个栅栏($1 \leq N \leq 100,000$)，位于不同的二维点（也不同于激光和谷仓），牛可以安装镜子。可以选择不在护栏柱上安装镜子，在这种情况下，激光器将简单地直接通过柱子的顶部而不改变方向。如果母牛确实在栅栏柱上安装了一个镜子，它们会像/或\对齐，使得它将在垂直方向上重定向光束，反之亦然。

Please compute the minimum possible number of mirrors the cows need to use in order to re-direct the laser to the barn.

请计算牛需要使用的镜子的最小可能数量，以便将激光重新导向谷仓。

inputFormat:
The first line of input contains 5 space-separated integers:

$N, x_L, y_L, x_B, y_B$, where $(x_L, y_L)$ is the location of the laser and $(x_B, y_B)$ is the location of the barn.  All coordinates are between $0$ and $1,000,000,000$.

第一行输入包含5个空格分隔的整数：$N, x_L, y_L, x_B, y_B$，其中$(x_L, y_L)$是激光器的位置，$(x_B, y_B)$是谷仓的位置。 所有坐标都在$0$和$1,000,000,000$之间。

The next $N$ lines each contain the $x$ and $y$ locations of a fence post, both integers in the range $0 \ldots 1,000,000,000$.

接下来的N行每行包含围栏柱的$x$和$y$位置，两个整数在$0 \ldots 1,000,000,000$的范围内。

outputFormat:
Please output the minimum number of mirrors needed to direct the laser to the barn, or -1 if this is impossible to do.

请输出将激光引导到谷仓所需的最小反射镜数，如果不可能，则输出-1。

hint: 感谢@huzhaoyang 提供翻译


title: [USACO11DEC] Simplifying the Farm G

description:
Farmer John has been taking an evening algorithms course at his local university, and he has just learned about minimum spanning trees.  However, Farmer John now realizes that the design of his farm is not as efficient as it could be, and he wants to simplify the layout of his farm.

The farm is currently arranged like a graph, with vertices representing fields and edges representing pathways between these fields, each having an associated length.  Farmer John notes that for each distinct length, at most three pathways on his farm share this length.  FJ would like to remove some of the pathways on his farm so that it becomes a tree -- that is, so that there is one unique route between any pair of fields.  Moreover, Farmer John would like this to be a minimum spanning tree -- a tree having the smallest possible sum of edge lengths.

Help Farmer John compute not only the sum of edge lengths in a minimum spanning tree derived from his farm graph, but also the number of different possible minimum spanning trees he can create.

农夫约翰在一所夜校学习算法课程，他刚刚学会了最小生成树。现在约翰意识到他的农场设计得不够高效，他想简化农场的布局。

约翰的农场可以看做一个图，农田代表图中顶点，田间小路代表图中的边，每条边有一定的长度。约翰注意到，农场中最多有三条小路有着相同的长度。约翰想删除一些小路使得农场成为一棵树，使得两块农田间只有一条路径。但是约翰想把农场设计成最小生成树，也就是农场道路的总长度最短。

请帮助约翰找出最小生成树的总长度，同时请计算出总共有多少种最小生成树？

inputFormat:
\* Line 1: Two integers N and M (1 <= N <= 40,000; 1 <= M <= 100,000), representing  the number of vertices and edges in the farm graph, respectively.  Vertices are numbered as 1..N.

\* Lines 2..M+1: Three integers a\_i, b\_i and n\_i (1 <= a\_i, b\_i <= N; 1 <= n\_i <= 1,000,000)  representing an edge from vertex a\_i to b\_i with length n\_i.  No edge length n\_i will occur more than three times.

outputFormat:
\* Line 1: Two integers representing the length of the minimal spanning tree and the number of minimal spanning trees (mod

1,000,000,007).

hint: Picking both edges with length 1 and any edge with length 2 yields a minimum spanning tree of length 4.


title: [USACO11DEC] Grass Planting G

description:
Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 bidirectional roads, such that there is exactly one path between any two pastures.  Bessie, a cow who loves her grazing time, often complains about how there is no grass on the roads between pastures.  Farmer John loves Bessie very much, and today he is finally going to plant grass on the roads.  He will do so using a procedure consisting of M steps (1 <= M <= 100,000).

At each step one of two things will happen:

- FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or,

- Bessie will ask about how many patches of grass on a particular road, and Farmer John must answer her question.

Farmer John is a very poor counter -- help him answer Bessie's questions!

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

\* Lines 2..N: Two space-separated integers describing the endpoints of a road.

\* Lines N+1..N+M: Line i+1 describes step i. The first character of the line is either P or Q, which describes whether or not FJ is planting grass or simply querying. This is followed by two space-separated integers A\_i and B\_i (1 <= A\_i, B\_i <= N) which describe FJ's action or query.

outputFormat: \* Lines 1..???: Each line has the answer to a query, appearing in the same order as the queries appear in the input.

translation:
给出一棵有 $n$ 个节点的树，有 $m$ 个如下所示的操作：

- 将两个节点之间的 **路径上的边** 的权值均加一。

- 查询两个节点之间的 **那一条边** 的权值，保证两个节点直接相连。

初始边权均为 0。

**【输入格式】**

第一行两个整数 $n,m$，含义如上。

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

接下来 $m$ 行，每行格式为 `op u v`，$op=\texttt{P}$ 代表第一个操作，$op=\texttt{Q}$ 代表第二个操作。

**【输出格式】**

若干行。对于每个查询操作，输出一行整数，代表查询的答案。

**【数据范围】**

对于 $100\%$ 的数据，$2\le n\le 10^5$，$1\le m\le 10^5$。


title: [USACO12JAN] Delivery Route S

description:
After several years of record milk production, Farmer John now operates an entire network of N farms (1 <= N <= 100).  Farm i is located at position (x\_i, y\_i) in the 2D plane, distinct from all other farms, with both x\_i and y\_i being integers.

FJ needs your help planning his daily delivery route to bring supplies to the N farms.  Starting from farm 1, he plans to visit the farms sequentially (farm 1, then farm 2, then farm 3, etc.), finally returning to farm 1 after visiting farm N.  It tames FJ one minute to make a single step either north, south, east, or west.  Furthermore, FJ wants to visit each farm exactly once during his entire journey (except farm 1, which he visits twice of course).

Please help FJ determine the minimum amount of time it will take him to complete his entire delivery route.

FJ有N (1 <= N <= 100)个农场，每个农场具有独立的整数坐标(x\_i, y\_i)。他需要一个物资配送路线，从第1个农场出发，依次经过农场1，农场2，农场3…，最后从农场N回到农场1.

FJ每次只能朝东南西北四个方向行走，每行走一个单位长度需要1分钟，除了农场1，其他农场能且仅能到达一次。

请计算FJ的最小时间花费。

inputFormat:
\* Line 1: The number of farms, N.

\* Lines 2..1+N: Line i+1 contains two space-separated integers, x\_i and y\_i  (1 <= x\_i, y\_i <= 1,000,000).

outputFormat: \* Line 1: The minimum number of minutes FJ needs to complete his delivery route, or -1 if it is impossible to find a feasible delivery route that visits every farm exactly once (except farm 1).

hint: FJ can complete his delivery route in 12 minutes: 2 minutes to go from farm 1 to farm 2, 5 minutes to go from farm 2 to farm 3 (circumventing farm 1), 3 minutes to go from farm 3 to farm 4, and then 2 minutes to return to farm 1.


title: [USACO12JAN] Bale Share S

description:
FJ 有 $n$ 包干草，第 $i$ 干草的重量是 $s_i$，他想尽可能平均地将干草分给三个农场。

他希望分配后的干草重量最大值尽可能地小，比如，$b_1,b_2,b_3$ 是分配后的三个值，假设 $b_1 \ge b_2 \ge b_3$，则他希望 $b_1$ 的值尽可能地小。

请计算 $b_1$ 的最小值。

inputFormat:
第一行一个正整数 $n$。
接下来 $n$ 行，每行一个正整数表示重量。

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


title: [USACO12JAN] Video Game G

description:
Bessie 在玩一款游戏，该游戏只有三个技能键 `A`，`B`，`C` 可用，但这些键可用形成 $n$ 种特定的组合技。第 $i$ 个组合技用一个字符串 $s_i$ 表示。

Bessie 会输入一个长度为 $k$ 的字符串 $t$，而一个组合技每在 $t$ 中出现一次，Bessie 就会获得一分。$s_i$ 在 $t$ 中出现一次指的是 $s_i$ 是 $t$ 从某个位置起的连续子串。如果 $s_i$ 从 $t$ 的多个位置起都是连续子串，那么算作 $s_i$ 出现了多次。

若 Bessie 输入了恰好 $k$ 个字符，则她最多能获得多少分？

inputFormat:
输入的第一行是两个整数，分别表示组合技个数 $n$ 和 Bessie 输入的字符数 $k$。

接下来 $n$ 行，每行一个字符串 $s_i$，表示一种组合技。

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

hint:
#### 样例 1 解释

Bessie 如果输入 `ABACBCB`，则 `ABA` 出现了一次，`ABACB` 出现了一次，`CB` 出现了两次，共得到 $4$ 分。可以证明这是最优的输入。

#### 数据规模与约定

对于全部的测试点，保证：

- $1 \leq n \leq 20$，$1 \leq k \leq 10^3$。
- $1 \leq |s_i| \leq 15$。其中 $|s_i|$ 表示字符串 $s_i$ 的长度。
- $s$ 中只含大写字母 `A`，`B`，`C`。


title: [USACO12JAN] Cow Run G

description:
Farmer John and Bessie have devised a new exercise game for the cows.  The cows are running on a circular track of length M (2 <= M <= 1,000,000,000) starting from the same position.  The game proceeds in N (1 <= N <= 14) rounds using a deck of 8N cards each with a number X\_i (0 <= X\_i < M) written on it.

Each round FJ moves the top 8 cards into a separate pile and selects either the top 4 or bottom 4 cards for Bessie to play with.  Bessie then chooses either the top 2 cards or bottom 2 cards of the 4 cards FJ selected.  After this FJ calls out the number on the top card, X\_top, and the cows run a distance of R \* X\_top, where R is the total distance the cows have run so far.  Bessie then calls out the number on the bottom card, X\_bottom, and the cows run a distance of X\_bottom.

FJ is concerned that after the exercise the cows will be too tired to get back to the beginning of the track if they end up too far away.  He believes if the cows end up more than a distance of K (0 <= K <= floor(M/2)) from their starting position they won't be able to get back home.

It is guaranteed that if FJ plays correctly, he will always be able to ensure the cows can come home, irrespective of the moves made by Bessie! For each round, your task is to determine which half of the cards FJ should choose such that no matter what Bessie does from that point on, FJ can always get the cows home.  Bessie will then make the move provided in the input and you can then continue onto the next round.  Note that even though Bessie's moves are provided to you in the input, you are to specify moves for FJ that would have worked no matter what Bessie chooses (so it is effectively as if FJ does not really know what Bessie will do during her moves).

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

\* Line 2: A string N characters.  If the ith character is 'T' it means Bessie will select the top 2 cards in the ith round.  Otherwise the ith character will be 'B' to indicate Bessie will select the bottom 2 cards in the ith round.

\* Lines 3..2+N: Each line contains eight integers representing the 8 cards to be used that round from top to bottom.

outputFormat: \* Line 1: A string of N characters where the ith character is 'T' if FJ should choose the top 4 cards or 'B' if FJ should choose the bottom 4 cards in the ith round.  If there are multiple ways to get the cows home, choose the lexicographically first (that is, the string that is alphabetically smallest).

translation:
FJ 和贝茜为奶牛们设计了一个新的跑步游戏。跑道是环行的，长度为 $(2 \le M \le 1,000,000,000)$ 的环行，奶牛们在相同的起跑位置。这个游戏一共要进行 $N\ (1 \le N \le 14)$ 轮，通过一副 $8N$ 张的纸牌来控制每一轮的跑步距离，每张纸牌都有一个数字 $X_i\ (0 \le X_i<M)$。

每一轮，FJ 取出最上面的 $8$ 张纸牌，然后再取出这 $8$ 张的上面或者底下的 $4$ 张。接着，贝茜从这 $4$ 张牌中取出上面或者底下的 $2$ 张，上面一张的数字为 $X_{\mathrm{top}}$，下面一张的数字是 $X_{\mathrm{bottom}}$，则牛先跑 $R\times X_{\mathrm{top}}$ 的距离（$R$ 表示奶牛们已经跑过的距离），再跑 $X_{\mathrm{bottom}}$ 的距离。

FJ 担心奶牛们太累而回不到起点，游戏结束时，若奶牛们离开起点距离超过 $K\ (0 \le K \le \lfloor M/2\rfloor)$，则他们就回不了起点了。

问题保证，当 FJ 选择正确的取牌策略，不论贝西如何取牌，奶牛们都能够回到起点。对于每一轮，你的任务是决定取哪 $4$ 张纸牌。在输入数据中，贝西的每次选择都是已知的，但 FJ 的每次取牌时，贝西接着的选择应该被假定为是未知的，即不论贝西怎么选，FJ 的选择都是能保证奶牛们能够回到起点。

hint: The cows must end up exactly where they started to be able to come home. Note that FJ is not aware of what choices Bessie is going to make beforehand.  If FJ did know, he could have chosen the bottom half each time.


title: [USACO12JAN] Bovine Alliance G

description:
Bessie and her bovine pals from nearby farms have finally decided that they are going to start connecting their farms together by trails in an effort to form an alliance against the farmers.  The cows in each of the N (1 <= N <= 100,000) farms were initially instructed to build a trail to exactly one other farm, for a total of N trails.  However months into the project only M (1 <= M < N) of these trails had actually been built.

Arguments between the farms over which farms already built a trail now threaten to split apart the cow alliance.  To ease tension, Bessie wishes to calculate how many ways the M trails that exist so far could have been built.  For example, if there is a trail connecting farms 3 and 4, then one possibility is that farm 3 built the trail, and the other possibility is that farm 4 built the trail.  Help Bessie by calculating the number of different assignments of trails to the farms that built them, modulo 1,000,000,007.  Two assignments are considered different if there is at least one trail built by a different farm in each assignment.

给出 n 个点 m 条边的无向图，现把点和边分组，每条边只能和相邻两点之一分在一组，点也可以单独一组。每个点只能被选择一次，求总方案数。

答案对 1e9+7 取模。

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

\* Lines 2..1+M: Line i+1 describes the ith trail.  Each line contains two space-separated integers u\_i and v\_i (1 <= u\_i, v\_i <= N, u\_i != v\_i) describing the pair of farms connected by the trail.

outputFormat: \* Line 1: A single line containing the number of assignments of trails to farms, taken modulo 1,000,000,007.  If no assignment satisfies the above conditions output 0.

hint:
Note that there can be two trails between the same pair of farms.

There are 6 possible assignments.  Letting {a,b,c,d} mean that farm 1 builds trail a, farm 2 builds trail b, farm 3 builds trail c, and farm 4 builds trail d, the assignments are:

```cpp
{2, 3, 4, 5}
{2, 3, 5, 4}
{1, 3, 4, 5}
{1, 3, 5, 4}
{1, 2, 4, 5}
{1, 2, 5, 4}

```


title: [USACO12FEB] Relocation S

description:
Farmer John is moving!  He is trying to find the best place to build a new farm so as to minimize the amount of travel he needs to do each day.

The region to which FJ plans to move has N towns (1 <= N <= 10,000).  There are M bi-directional roads (1 <= M <= 50,000) connecting certain pairs of towns.  All towns are reachable from each-other via some combination of roads.  FJ needs your help selecting the best town as the home for his new farm.

There are markets in K of the towns (1 <= K <= 5) that FJ wants to visit every day.  In particular, every day he plans to leave his new farm, visit the K towns with markets, and then return to his farm.  FJ can visit the markets in any order he wishes.  When selecting a town in which to build his new farm, FJ wants to choose only from the N-K towns that do not have markets, since housing prices are lower in those towns.

Please help FJ compute the minimum distance he will need to travel during his daily schedule, if he builds his farm in an optimal location and chooses his travel schedule to the markets as smartly as possible.

FJ决定搬家，重新建设农场，以便最小化他每天的行程。

FJ搬往的区域有N(1 <= N <= 10,000)个城镇，共有M (1 <= M <= 50,000)条双向道路连接某些城镇，所有城镇都能找到互通路线。

有K (1 <= K <= 5)个城镇建有市场，FJ每天离开新农场后，都要光顾这K个城镇，并返回农场。FJ希望建设农场的城镇不包含市场。

请帮助FJ选择最佳城镇建设农场，使得他每天的行程最小。

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

\* Lines 2..1+K: Line i+1 contains an integer in the range 1...N identifying the town containing the ith market.  Each market is in a different town.

\* Lines 2+K..1+K+M: Each line contains 3 space-separated integers, i, j (1 <= i,j <= N), and L (1 <= L <= 1000), indicating the presence of a road of length L from town i to town j.

outputFormat: \* Line 1: The minimum distance FJ needs to travel during his daily routine, if he builds his farm in an optimal location.

hint:
There are 5 towns, with towns 1, 2, and 3 having markets.  There are 6 roads.

FJ builds his farm in town 5.  His daily schedule takes him through towns 5-1-2-3-2-1-5, for a total distance of 12.


title: [USACO12FEB] Cow Coupons G

background: Subtask 0 为原数据，Subtask 1,2 为 hack 数据。

description:
Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000), and FJ has to spend no more than his budget of M units of money (1 <= M <= 10^14).  Cow i costs P\_i money (1 <= P\_i <= 10^9), but FJ has K coupons (1 <= K <= N), and when he uses a coupon on cow i, the cow costs C\_i instead (1 <= C\_i <= P\_i). FJ can only use one coupon per cow, of course.

What is the maximum number of cows FJ can afford?

FJ 准备买一些新奶牛。市场上有 $N$ 头奶牛，第 $i$ 头奶牛价格为 $P_i$。FJ 有 $K$ 张优惠券，使用优惠券购买第 $i$ 头奶牛时价格会降为 $C_i$，当然每头奶牛只能使用一次优惠券。FJ 想知道花不超过 $M$ 的钱最多可以买多少奶牛？

- $1 \le K \le N \le 5 \times 10^4$
- $1 \le C_i \le P_i \le 10^9$
- $1 \le M \le 10^{14}$

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

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

outputFormat: \* Line 1: A single integer, the maximum number of cows FJ can afford.

hint:
FJ has 4 cows, 1 coupon, and a budget of 7.

FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.


title: [USACO12FEB] Symmetry G

description:
After taking a modern art class, Farmer John has become interested in finding geometric patterns in everything around his farm.  He carefully plots the locations of his N cows (2 <= N <= 1000), each one occupying a distinct point in the 2D plane, and he wonders how many different lines of symmetry exist for this set of points.  A line of symmetry, of course, is a line across which the points on both sides are mirror images of each-other.

Please help FJ answer this most pressing geometric question.

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

\* Lines 2..1+N: Line i+1 contains two space-separated integers representing the x and y coordinates of the ith cow (-10,000 <= x,y <= 10,000).

outputFormat: \* Line 1: The number of different lines of symmetry of the point set.

translation: 上过现代艺术课后，FJ开始感兴趣于在他农场中的几何图样。他计划将奶牛放置在二维平面上的N个互不相同的点(2<=N<=1000),他希望找出这个点集有多少条对称轴。他急切地需要你帮忙解决这个几何问题。

hint:
The 4 cows form the corners of a square.

There are 4 lines of symmetry -- one vertical, one horizontal, and two diagonal.


title: [USACO12FEB] Nearby Cows G

description:
Farmer John has noticed that his cows often move between nearby fields. Taking this into account, he wants to plant enough grass in each of his fields not only for the cows situated initially in that field, but also for cows visiting from nearby fields.

Specifically, FJ's farm consists of N fields (1 <= N <= 100,000), where some pairs of fields are connected with bi-directional trails (N-1 of them in total).  FJ has designed the farm so that between any two fields i and j, there is a unique path made up of trails connecting between i and j. Field i is home to C(i) cows, although cows sometimes move to a different field by crossing up to K trails (1 <= K <= 20).

FJ wants to plant enough grass in each field i to feed the maximum number of cows, M(i), that could possibly end up in that field -- that is, the number of cows that can potentially reach field i by following at most K trails.  Given the structure of FJ's farm and the value of C(i) for each field i, please help FJ compute M(i) for every field i.

给你一棵 $n$ 个点的树，点带权，对于每个节点求出距离它不超过 $k$ 的所有节点权值和 $m_i$。

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

\* Lines 2..N: Each line contains two space-separated integers, i and j (1 <= i,j <= N) indicating that fields i and j are directly connected by a trail.

\* Lines N+1..2N: Line N+i contains the integer C(i). (0 <= C(i) <= 1000)

第一行两个正整数 $n,k$。
接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u,v$ 之间有一条边。
最后 $n$ 行，每行一个非负整数 $c_i$，表示点权。

outputFormat:
\* Lines 1..N: Line i should contain the value of M(i).

输出 $n$ 行，第 $i$ 行一个整数表示 $m_i$。

hint:
There are 6 fields, with trails connecting (5,1), (3,6), (2,4), (2,1), and (3,2).  Field i has C(i) = i cows.

Field 1 has M(1) = 15 cows within a distance of 2 trails, etc.

【数据范围】
对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le k \le 20$，$0 \le c_i \le 1000$


title: [USACO12FEB] Cow IDs S

description:
Being a secret computer geek, Farmer John labels all of his cows with binary numbers. However, he is a bit superstitious, and only labels cows with binary numbers that have exactly K "1" bits $(1 \le K \le 10)$. The leading bit of each label is always a "1" bit, of course. FJ assigns labels in increasing numeric order, starting from the smallest possible valid label -- a K-bit number consisting of all "1" bits. Unfortunately, he loses track of his labeling and needs your help: please determine the Nth label he should assign $(1 \le N \le 10^7)$.

FJ 给他的奶牛用二进制进行编号，每个编号恰好包含 $K$ 个 $1$（$1 \le K \le 10$），且必须是 $1$ 开头。FJ 按升序编号，第一个编号是由 $K$ 个 $1$ 组成。

请问第 $N$（$1 \le N \le 10^7$）个编号是什么。

inputFormat: * Line $1$: Two space-separated integers, $N$ and $K$.


title: [USACO12MAR] Landscaping S

background: *本题与 [2016 年公开赛白金组同名题目](/problem/P2748) 在题意上一致，唯一的差别是数据范围。*

description:
Farmer John 打算修建一座花园，他需要移动不少泥土。

花园由 $N$ 个花坛组成（$1 \leq N \leq 100$），其中花坛 $i$ 包含 $A_i$ 单位的泥土。FJ 希望花坛 $i$ 包含 $B_i$ 单位的泥土，保证 $0 \leq A_i,B_i \leq 10$。

为了达到这个目标，他可以做这几件事情：

- 购买一单位的泥土，放在指定的花坛中，费用为 $X$。
- 从任意一个花坛中移走一单位泥土，费用为 $Y$。
- 从花坛 $i$ 运送一单位泥土到花坛 $j$，费用为 $Z|i-j|$。

请你帮 FJ 计算移动泥土的最小开销。

inputFormat:
第一行四个整数 $N,X,Y,Z$（$0 \leq X,Y,Z \leq 1000$）。

接下来 $N$ 行，第 $i$ 行两个整数 $A_i,B_i$。

outputFormat: 输出移动泥土的最小开销。

hint:
按下面的方案，最小花费为 $210$，可以证明不存在开销更小的方案。

- 移除 $4$ 号花坛的一单位泥土，花费 $200$。
- 将 $4$ 号花坛的三单位泥土移到 $1$ 号花坛，花费 $3 \times 3=9$。
- 将 $3$ 号花坛的一单位泥土移到 $2$ 号花坛，花费 $1 \times 1=1$。


title: [USACO12MAR] Large Banner G

description:
Bessie is returning from a long trip abroad to the Isle of Guernsey, and Farmer John wants to mount a nice "Welcome Home" banner for her arrival. Farmer John's field has integer dimensions M x N (1 <= M, N <= 100,000), and he has installed a post at every possible point in the field with integer coordinates (if we assign a coordinate system to the field so that (0,0) is in the lower-left corner and (M,N) is in the upper-right corner). Of these (M+1) \* (N+1) points, Farmer John must pick two as the endpoints of the banner.

Farmer John, being the perfectionist that he is, insists that the banner must be completely straight.  This means that, for the two posts he chooses, there cannot be any other post on the line segment that the banner will form between them.  Additionally, Farmer John wants the banner to have length at least L and at most H (1 <= L <= H <= 150,000).  Farmer John needs your help to figure out how many possible ways he can hang the banner. The banner is reversible, so switching the two endpoints of the banner counts as the same way to hang the banner. As this number may be very large, Farmer John simply wants to know what it is modulo B (1 <= B <= 1,000,000,000).

Consider the example below, with M = 2 and N = 2:

\* \* \*
\* \* \*
\* \* \*
Farmer John wants the length of the banner to be between 1 and 3 inclusive. Any choice of posts satisfies this length requirement, but note that eight pairs cannot be picked:

(0, 0) and (2, 0): (1, 0) is on the line segment between them

(0, 1) and (2, 1): (1, 1) is on the line segment between them

(0, 2) and (2, 2): (1, 2) is on the line segment between them

(0, 0) and (2, 2): (1, 1) is on the line segment between them

(0, 0) and (0, 2): (0, 1) is on the line segment between them

(1, 0) and (1, 2): (1, 1) is on the line segment between them

(2, 0) and (2, 2): (2, 1) is on the line segment between them

(0, 2) and (2, 0): (1, 1) is on the line segment between them

Therefore, there are a total of (9 choose 2) - 8 = 28 possible locations.

给出n,m,l,h，问有多少点A(ax,ay),B(bx,by)满足：ax,bx∈[0,n], ay,by∈[0,m]，l<=AB<=h，且线段AB上除A,B外无整点。

inputFormat: \* Line 1: Five space-separated integers: M, N, L, H and B.

outputFormat: \* Line 1: One integer denoting the number of possible banners (modulo B).


title: [USACO12MAR] Haybale Restacking G

description:
Farmer John has just ordered a large number of bales of hay.  He would like to organize these into N piles (1 <= N <= 100,000) arranged in a circle, where pile i contains B\_i bales of hay.  Unfortunately, the truck driver delivering the hay was not listening carefully when Farmer John provided this information, and only remembered to leave the hay in N piles arranged in a circle.  After delivery, Farmer John notes that pile i contains A\_i bales of hay.  Of course, the A\_i's and the B\_i's have the same sum.

Farmer John would like to move the bales of hay from their current configuration (described by the A\_i's) into his desired target configuration (described by the B\_i's).  It takes him x units of work to move one hay bale from one pile to a pile that is x steps away around the circle.  Please help him compute the minimum amount of work he will need to spend.

给出n块土地，现有泥土A[i]，需要改造成B[i]，但这次土地排列成环，且不可买进买出，只能运，且∑A[i]=∑B[i]，问最小花费。

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

\* Lines 2..1+N: Line i+1 contains the two integers A\_i and B\_i (1 <= A\_i, B\_i <= 1000).

hint:
There are 4 piles around a circle.  Initially, the piles contain 7, 3, 9, and 1 bales of hay.  Farmer John would like to move them so the piles contain 1, 4, 2, and 13 bales of hay.

A minimum of 13 units of work is required (move 6 bales from pile 1 to pile 4, move 1 bale from pile 3 to pile 2, and move 6 bales from pile 3 to pile 4).


title: [USACO12MAR] Cows in a Skyscraper G

description:
A little known fact about Bessie and friends is that they love stair climbing races.  A better known fact is that cows really don't like going down stairs.  So after the cows finish racing to the top of their favorite skyscraper, they had a problem.  Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C\_i (1 <= C\_i <= W) pounds.  Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides.  The sum of the weights of the cows on each elevator ride must be no larger than W.

inputFormat:
\* Line 1: N and W separated by a space.

\* Lines 2..1+N: Line i+1 contains the integer C\_i, giving the weight of one of the cows.

outputFormat:
\* A single integer, R, indicating the minimum number of elevator rides needed.

one of the R trips down the elevator.

translation:
给出 $n$ 个物品，体积为 $w _ 1, w _ 2, \cdots, w _ n$，现把其分成若干组，要求每组总体积小于等于 $W$，问最小分组数量。

$n\le 18,1\le c_i\le W\le 10^8$。

hint:
There are four cows weighing 5, 6, 3, and 7 pounds.  The elevator has a maximum weight capacity of 10 pounds.

We can put the cow weighing 3 on the same elevator as any other cow but the other three cows are too heavy to be combined.  For the solution above, elevator ride 1 involves cow #1 and #3, elevator ride 2 involves cow #2, and elevator ride 3 involves cow #4.  Several other solutions are possible for this input.


title: [USACO12OPEN] Unlocking Blocks S

description:
A little-known fact about cows is that they love puzzles! For Bessie's birthday, Farmer John gives her an interesting mechanical puzzle for her to solve.  The puzzle consists of three solid objects, each of which is built from 1x1 unit squares glued together.  Each of these objects is a "connected" shape,  in the sense that you can get from one square on the object to any other square on the object by stepping north, south, east, or west, through squares on the object.

An object can be moved by repeatedly sliding it either north, south, east, or west one unit.  The goal of the puzzle is to move the objects so that they are separated -- where their bounding boxes no longer share any positive overlap with each-other.  Given the shapes and locations of the three objects, your task is to help Bessie decide what is the minimum number of individual slides required to separate the objects.

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

inputFormat:
\* Line 1: Three space-separated integers: N1, N2, and N3, describing respectively the number of unit squares making up objects 1, 2, and 3.

\* Lines 2..1+N1: Each of these lines describes the (x,y) location of the south-west corner of single square that is part of object 1.  All coordinates lie in the range 0..9.

\* Lines 2+N1..1+N1+N2: Each of these lines describes the (x,y) location of the south-west corner of single square that is part of object 2.  All coordinates lie in the range 0..9.

\* Lines 2+N1+N2..1+N1+N2+N3: Each of these lines describes the (x,y) location of the south-west corner of single square that is part of object 3.  All coordinates lie in the range 0..9.

第1行：三个整数N1,N2,N3，表示组成模块1,2,3的小正方体数目。

第2行到第N1+1行：读入一对坐标（x，y），每对坐标表示组成模块1的一个小正方体西南角落的位置。所有坐标在0..9之间。

第N1+2行到第N1+N2+1行：读入一对坐标（x，y），每对坐标表示组成模块2的一个小正方体西南角落的位置。所有坐标在0..9之间。

第N1+N2+2行到第N1+N2+N3+…

outputFormat: \* Line 1: The minimum number of moves necessary to separate the three objects, or -1 if the objects cannot be separated.

translation:
奶牛们一个鲜为人知的事实是它们爱解谜！Bessie生日时农夫约翰给了她一个有趣的机械锁给她解决。锁由三个模块构成，每一个模块都由1x1的小立方体粘连而成。每一个模块都是一个“连通”的模型，那么，你就可以通过在模型上的小正方体间向北、南、东或西走而从模型的一个小正方形到达模型上的任何其他小正方形。

一个模块可以多次向东西南北滑动一个单位。拼图的目标是滑动模块使其分离——即使它们的边界框不再有任何重叠。给定三个模块的形状与位置，请你帮助Bessie找到达到目标需要的最小滑动次数。

hint:
Object 1 is made from 12 squares, object 2 is made from 3 squares, and object 3 is made from 5 squares.  The shapes of the objects are those in the figure above.

If we slide object 3 to the east by one position, then slide object 2 north by one position, then slide object 1 west by three positions, then the bounding boxes of the three objects will no longer share any overlap in common.

模块1由12块小正方体制造，模块2由3块小正方体制造，模块3由5块小正方体制造。最后的图像在如上。（吃图？！）

```cpp
A：模块1方块 B：模块2方块 C：模块3方块 *：啥都木有
A A A A C
A * C C C
A B B * C
A * B A *
A A A A *
```
假如我们把模块3向东移一个单位，然后把模块2向北移一个单位，然后把模块1向西移三个单位，就满足了条件。

感谢 @姚起龙 提供翻译


title: [USACO12OPEN] Running Laps S

description:
Bored with horse racing, Farmer John decides to investigate the feasibility of cow racing as a sport.  He sets up his N cows (1 <= N <= 100,000) to run a race of L laps around a circular track of length C.  The cows all start at the same point on the track and run at different speeds, with the race ending when the fastest cow has run the total distance of LC.

FJ notices several occurrences of one cow overtaking another, and wonders how many times this sort of "crossing event" happens during the entire race.  More specifically, a crossing event is defined by a pair of cows (x,y) and a time t (less than or equal to the ending time of the race), where cow x crosses in front of cow y at time t.  Please help FJ count the total number of crossing events during the entire race.

有n头牛要在长为c的跑道上跑l圈，每头牛有一个速度s\_i. 某头牛跑完时，所有的牛都停下来，问此之前发生了多少次超越。

inputFormat:
\* Line 1: Three space-separated integers: N, L, and C.  (1 <= L,C <= 25,000).

\* Lines 2..1+N: Line i+1 contains the speed of cow i, an integer in the range 1..1,000,000.

outputFormat: \* Line 1: The total number of crossing events during the entire race.

translation:
# 题目描述
 农夫约翰让他的 n （1 <= n <= 100,000） 头牛在长度为 c 的跑道上进行跑 l 圈的比赛，所有牛从同一起点，以不同的速度开始跑。直到当跑得最快的那一头牛跑完 l 圈时，所有牛才同时停下。

  约翰发现在跑圈过程中发生了几次“超越事件”。其定义是：在比赛结束前某时刻，奶牛 x 已经超越了奶牛 y **整整一圈**，则称做一次“超越事件”。（注： **至少一圈** ，超越了1/2圈，或者超越了1/4圈等等都不算。且对于同一对奶牛（x，y）不会重复计算次数。）

 约翰想知道比赛过程中发生了多少次“超越事件”。

 （注：可能原文章表达有误或某些其他原因，各种翻译方式过来的题意都有问题，给人误导很大，这里是根据题目数据和样例解释写的正确的题意，而不是原文）

## 输入格式：
第一行：三个整数：n，l，c（1 <= l,c <= 25,000)

第二行到第 n+1 行：每行一个整数 vi ，表示奶牛i的速度（1 <= vi <= 1,000,000）

## 输出格式：
第一行：一个整数，表示总共发生的“超越事件”的次数

感谢@远藤沙椰 提供的翻译

hint:
There are 4 cows running 2 laps on a circular track of length 100.  The speeds of the cows are 20, 100, 70, and 1.

The race lasts 2 units of time, since this is the time it takes the fastest cow (cow 2) to finish.  Within that time, there are 4 crossing events: cow 2 overtakes cows 1 and 4, and cow 3 overtakes cows 1 and 4.


title: [USACO12OPEN] Tied Down G

description:
As we all know, Bessie the cow likes nothing more than causing mischief on the farm.  To keep her from causing too much trouble, Farmer John decides to tie Bessie down to a fence with a long rope.  When viewed from above, the fence consists of N posts (1 <= N <= 10) that are arranged along vertical line, with Bessie's position (bx, by) located to the right of this vertical line.  The rope FJ uses to tie down Bessie is described by a sequence of M line segments (3 <= M <= 10,000), where the first segment starts at Bessie's position and the last ends at Bessie's position. No fence post lies on any of these line segments.  However, line segments may cross, and multiple line segments may overlap at their endpoints.

Here is an example of the scene, viewed from above:

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

To help Bessie escape, the rest of the cows have stolen a saw from the barn.  Please determine the minimum number of fence posts they must cut through and remove in order for Bessie to be able to pull free (meaning she can run away to the right without the rope catching on any of the fence posts).

All (x,y) coordinates in the input (fence posts, Bessie, and line segment endpoints) lie in the range 0..10,000.  All fence posts have the same x coordinate, and bx is larger than this value.

牛被拴着。平面上有n个柱子，x坐标相等，且都小于牛的x坐标。牛在由m条边形成的闭合多边形组成的绳子上。问最少要锯掉几个柱子牛才能逃脱。

inputFormat:
\* Line 1: Four space-separated integers: N, M, bx, by.

\* Lines 2..1+N: Line i+1 contains the space-separated x and y

coordinates of fence post i.

\* Lines 2+N..2+N+M: Each of these M+1 lines contains, in sequence, the space-separated x and y coordinates of a point along the rope. The first and last points are always the same as Bessie's location (bx, by).

outputFormat: \* Line 1: The minimum number of posts that need to be removed in order for Bessie to escape by running to the right.

hint:
There are two posts at (2,3) and (2,1).  Bessie is at (6,1).  The rope goes from (6,1) to (2,4) to (1,1), and so on, ending finally at (6,1). The shape of the rope is the same as in the figure above.

Removing either post 1 or post 2 will allow Bessie to escape.


title: [USACO12NOV] Clumsy Cows S

description:
Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters.  Please help her by computing the minimum number of characters in the string that one must reverse (e.g., changing a left parenthesis to a right parenthesis, or vice versa) so that the string would become balanced.

There are several ways to define what it means for a string of parentheses to be "balanced".  Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s.  For example, the following strings are all balanced:

()
(())
()(()())

while these are not:

)(
())(
((())))

给出一个偶数长度的括号序列，问最少修改多少个括号可以使其平衡。

inputFormat: \* Line 1: A string of parentheses of even length at most 100,000 characters.

outputFormat: \* Line 1: A single integer giving the minimum number of parentheses that must be toggled to convert the string into a balanced string.

hint: The last parenthesis must be toggled, and so must one of the two middle right parentheses.


title: [USACO12NOV] Distant Pastures S

description:
Farmer John's farm is made up of an N x N grid of pastures, where each pasture contains one of two different types of grass.  To specify these two types of grass, we use the characters ( and ), so for example FJ's farm might look like the following grid:

(())
)()(
)(((
))))
When Bessie the cow travels around the farm, it takes her A units of time to move from a pasture to an adjacent pasture (one step north, south, east, or west) with the same grass type, or B units of time to move to an adjacent pasture with a different grass type.  Whenever Bessie travels from one pasture to a distant pasture, she always uses a sequence of steps that takes the minimum amount of time.  Please compute the greatest amount of time Bessie will ever need to take while traveling between some pair of pastures on the farm.

给出一个n\*n的括号矩阵，从一个点走到相邻的同字符点需付出A的代价，到不同字符点需付出B的代价。求所有点对之间最短路的最大值。

inputFormat:
\* Line 1: Three integers: N (1 <= N <= 30), A (0 <= A <= 1,000,000), and B (0 <= B <= 1,000,000).

\* Lines 1..N+1: Each line contains a string of parentheses of length N.  Collectively, these N lines form an N x N grid of

parentheses.

outputFormat: \* Line 1: A single integer specifying the maximum amount of time Bessie can spend traveling between a pair of pastures (given that she always follows a route that takes a minimum amount of time).

hint: It takes Bessie 5 units of time to travel between the upper-left corner and the lower-right corner of the grid.  No other pair of pastures causes her to travel for more time than this.


title: [USACO12NOV] Balanced Cow Breeds G/S

description:
Farmer John usually brands his cows with a circular mark, but his branding iron is broken, so he instead must settle for branding each cow with a mark in the shape of a parenthesis -- (.  He has two breeds of cows on his farm: Holsteins and Guernseys.  He brands each of his cows with a

parenthesis-shaped mark.  Depending on which direction the cow is facing, this might look like either a left parenthesis or a right parenthesis.

FJ's N cows are all standing in a row, each facing an arbitrary direction, so the marks on the cows look like a string of parentheses of length N. Looking at this lineup, FJ sees a remarkable pattern: if he scans from left to right through just the Holsteins (in the order they appear in the sequence), this gives a balanced string of parentheses; moreover, the same is true for the Guernseys!  To see if this is truly a rare event, please help FJ compute the number of possible ways he could assign breeds to his N cows so that this property holds.

There are several ways to define what it means for a string of parentheses to be "balanced".  Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s.  For example, the following strings are all balanced:

()
(())
()(()())

while these are not:

)(
())(
((())))

给一个只有左右括号的字符串，然后用 `H`、`G` 两种字符来标记这个序列，所有标记 `H` 的括号可以组成一个正确的括号序列，所有 `G` 标记的括号也组成一个正确的括号序列，然后输出这种标记方案的总数 $\operatorname{mod} 2012$ 的值。

inputFormat: \* Line 1: A string of parentheses of length N (1 <= N <= 1000).

outputFormat: \* Line 1: A single integer, specifying the number of ways FJ can assign breeds to cows so that the Holsteins form a balanced subsequence of parentheses, and likewise for the Guernseys. Since the answer might be a very large number, please print the remainder of this number when divided by 2012 (i.e., print the number mod 2012).  Breed assignments involving only one breed type are valid.

hint:
The following breed assignments work:

(())
HHHH
(())
GGGG
(())
HGGH
(())
GHHG
(())
HGHG
(())
GHGH

感谢@CREEPER\_ 提供翻译


title: [USACO12NOV] Concurrently Balanced Strings G

description:
Farmer John's cows are all of a very peculiar breed known for its distinctive appearance -- each cow is marked with a giant spot on its hide in the shape of a parenthesis (depending on the direction the cow is facing, this could look like either a left or a right parenthesis).

One morning, Farmer John arranges his cows into K lines each of N cows (1 <= K <= 10, 1 <= N <= 50,000).  The cows are facing rather arbitrary directions, so this lineup can be described by K length-N strings of parentheses S\_1,..., S\_k.  Farmer John notes with great excitement that some ranges of his cows are "concurrently balanced", where a range i...j of cows is concurrently balanced only if each of the strings S\_1,..., S\_k is balanced in that range (we define what it means for a single string of parentheses to be balanced below). For instance, if K = 3, and we have

S\_1 = )()((())))(())

S\_2 = ()(()()()((())

S\_3 = )))(()()))(())

1111
01234567890123

Then the range [3...8] is concurrently balanced because S\_1[3...8] = ((())), S\_2[3...8] = ()()(), and S\_3[3...8] = (()()). The ranges [10...13] and [11...12] are also concurrently balanced.

Given K length-N strings of parentheses, help Farmer John count the number of pairs (i,j) such that the range i...j is concurrently balanced.

There are several ways to define what it means for a single string of parentheses to be "balanced".  Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s.  For example, the following strings are all balanced:

()
(())
()(()())

while these are not:

)(
())(
((())))

给出k个长度为n的括号序列，问有多少个区间在k个序列中对应的子串均平衡。

inputFormat:
\* Line 1: Two integers, K and N.

\* Lines 2..K+1: Each line contains a length-N string of parentheses.

outputFormat: \* Line 1: A single integer, the number of concurrently balanced ranges.


title: [USACO12NOV] Balanced Trees G

description:
Fascinated by his experience with balanced parentheses so far, Farmer John is curious if you can help him solve one final problem.  As it turns out, FJ's farm is in the shape of a giant tree of N pastures (1 <= N <= 40,000), each of which he has labeled with either ( or ).  For example:

'('--'('--')'--'('--')'

|         |

')'       ')'--'('--'('

|              |

')'            '('--')'--')'--')'--'('

Recall that since his farm is a tree, this means that certain pairs of pastures are connected by corridors so that there is one unique path between any given pair of pastures.  FJ believes that some of these paths represent balanced strings of parentheses.  In particular, he would like to know, among all such balanced strings represented by paths through the tree, what is the maximum nesting depth one can find.  The nesting depth of a balanced string of parentheses is the maximum, over all prefixes of the string, of the excess number of ('s within the prefix.  For example, the string ()()() has nesting depth 1, but the string ((()))() has nesting depth 3, as we can see clearly if we count excess ('s for every prefix of the string:

((()))()

12321010

For the example farm above, the deepest string is ((())) with a depth of 3, and can be obtained by taking the path from A to B below:

```cpp
'('--'('--')'--'('--')'
|         |
')'       ')'--'('--'(' < A
|              |
')'            '('--')'--')'--')'--'('
^C                            ^B
```
Note that this is different than the longest balanced string; for instance (())(()), starting at A and ending at C, has length 8.

Your task is to output the nesting depth of the deepest balanced path in the tree.

给出一棵树，每个结点上有一个括号。问在所有括号平衡的路径中，最大嵌套层数为多少。

inputFormat:
\* Line 1: A single integer N, the number of nodes in the tree.

\* Lines 2..N: Line i+1: A single integer p\_(i+1) (1 <= p\_(i+1) <= i), denoting an edge between nodes i+1 and p\_{i+1} in the tree.

\* Lines N+1..2N: Line N+i: Either ( or ), the label of node i.

outputFormat: \* Line 1: A single integer, giving the maximum nesting depth of a balanced path.


title: [USACO12DEC] Crazy Fences S

description:
After visiting a modern art museum, Farmer John decides to re-design his farm by moving all of the N (1 <= N <= 1000) fences between his pastures! Each fence is describe by a line segment in the 2D plane.  If two fences meet, they do so only at their endpoints.  Each fence touches exactly two other fences, one at both endpoints.

FJ has C cows (1 <= C <= 1000) on his farm.  Each cow resides at a point in the 2D plane that is not on any fence, and no two cows reside at the same point.  Two cows are said to be in the same community if one could walk to the other without touching any fences.  Please help FJ determine the size of the largest community.

在访问了一个现代美术馆后，约翰农夫决定移动n个在他的牧场之间的栅栏来

重新设计他的农场。每个栅栏用一个2D平面的线段来描述。两个栅栏只有在他们的端点才会相遇。每个栅栏在两个端点接触其他的两个栅栏。

约翰农夫有c头牛在他的农场。每头牛住在2D平面的不在任何栅栏的一个点，并且没有两头牛在同一个点。如果两头牛可以不接触任何栅栏地走到一起，他们就是在同一个社区。请确定最大的社区的牛的数量。

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

\* Lines 2..1+N: Each line contains four integers: x1, y1, x2, y2, indicating a fence from point (x1,y1) to point (x2,y2).  All coordinates are integers in the range 0..1,000,000.

\* Lines 2+N..1+N+C: Each line contains two integers x and y describing the location of a cow.  All coordinates are integers in the range 0..1,000,000.

outputFormat: \* Line 1: The number of cows in the largest community.

hint:
There are 10 fences and 4 cows.  The fences form a square containing two triangles.

Cows #2 and #4 belong to the same community.  Cows #1 and #3 are each members of a community of size 1.

感谢@kczno1 提供翻译


title: [USACO12DEC] Wifi Setup S

description:
Farmer John's N cows (1 <= N <= 2000) are all standing at various positions along the straight path from the barn to the pasture, which we can think of as a one-dimensional number line.  Since his cows like to stay in email contact with each-other, FJ wants to install Wifi base stations at various positions so that all of the cows have wireless coverage.

After shopping around, FJ learns that the cost of a Wifi base station depends on distance it can transmit: a base station of power r costs A + B\*r, where A is a fixed cost for installing the base station and B is a cost per unit of transmission distance.  If FJ installs such a device at position x, then it can transmit data to any cow located in the range x-r ... x+r.  A base station with transmission power of r=0 is allowed, but this only provides coverage to a cow located at the same position as the transmitter.

Given the values of A and B, as well as the locations of FJ's cows, please determine the least expensive way FJ can provide wireless coverage for all his cows.

给出在同一条直线上的n个点和两个数A，B，现在要在这条直线上放置若干个信号塔，每个信号塔有一个r值，假设它的位置是x，则它能覆盖的范围是x-r~x+r，放置一个信号塔的花费是A+B\*r，问要覆盖所有的点最小的花费是多少。

inputFormat:
\* Line 1: Three space-separated integers: N A B (0 <= A, B <= 1000).

\* Lines 2..1+N: Each line contains an integer in the range

0..1,000,000 describing the location of one of FJ's cows.

outputFormat: \* Line 1: The minimum cost of providing wireless coverage to all cows.

hint:
There are 3 cows at positions 7, 0, and 100.  Installation of a base station of power r costs 20 + 5\*r.

The optimal solution is to build a base station at position 3.5 (with power 3.5) and another at position 100 (with power 0).  The first base station covers cows 1 and 2, and the second covers cow 3.


title: [USACO12DEC] Milk Routing S

description:
Farmer John's farm has an outdated network of M pipes (1 <= M <= 500) for pumping milk from the barn to his milk storage tank.  He wants to remove and update most of these over the next year, but he wants to leave exactly one path worth of pipes intact, so that he can still pump milk from the barn to the storage tank.

The pipe network is described by N junction points (1 <= N <= 500), each of which can serve as the endpoint of a set of pipes.  Junction point 1 is the barn, and junction point N is the storage tank.  Each of the M bi-directional pipes runs between a pair of junction points, and has an associated latency (the amount of time it takes milk to reach one end of the pipe from the other) and capacity (the amount of milk per unit time that can be pumped through the pipe in steady state).  Multiple pipes can connect between the same pair of junction points.

For a path of pipes connecting from the barn to the tank, the latency of the path is the sum of the latencies of the pipes along the path, and the capacity of the path is the minimum of the capacities of the pipes along the path (since this is the "bottleneck" constraining the overall rate at which milk can be pumped through the path).  If FJ wants to send a total of X units of milk through a path of pipes with latency L and capacity C, the time this takes is therefore L + X/C.

Given the structure of FJ's pipe network, please help him select a single path from the barn to the storage tank that will allow him to pump X units of milk in a minimum amount of total time.

inputFormat:
\* Line 1: Three space-separated integers: N M X (1 <= X <= 1,000,000).

\* Lines 2..1+M: Each line describes a pipe using 4 integers: I J L C. I and J (1 <= I,J <= N) are the junction points at both ends of the pipe.  L and C (1 <= L,C <= 1,000,000) give the latency and capacity of the pipe.

第1行：三个空格分隔的整数:N M X(1<=X<=1000000)。

第2行到第M+1行：每一行描述一条管道，有4个整数：I J L C。I和J(1<=I,J<=N)是这条管道连接的两个点。L和C(1<=L，C<=1000000)是这条管道的延迟和容量。

outputFormat:
\* Line 1: The minimum amount of time it will take FJ to send milk along a single path, rounded down to the nearest integer.

第1行:约翰沿着一条路径送牛奶花费的最少的时间，向下取整到最近的整数。

translation:
农民约翰的农场有一套老旧的管网，管网由M条管道(1<=M<=500)构成，用于将牛奶从谷仓运到储奶罐。 他想在明年移除和更新大部分管道，但他想原封不动地保留一条完整的路径，这样他仍然可以把牛奶从谷仓输送到储罐。

管网由N个节点(1<=N<=500)组成，每个点都可以作为一组管道的端点。结点1是谷仓，结点N是储罐。M条双向管道中的每一条都连接一对节点，并且都有一个延迟值(牛奶达到管的另一端的用时)和容量值(单位时间内可以稳定通过管道的牛奶量)。多条管道可以连接同一对节点。

对于一条连接谷仓与储罐的路径，路径的延迟等于沿途所有管道的延迟之和，路径的容量等于沿途管道最小的容量(因为这是制约牛奶运送的“瓶颈”)。如果约翰通过一条延迟为L、容量为C的管道运送X个单位的牛奶，需要的时间为L+X/C。

给出约翰的管网结构，请帮助他选择一条路径，使得他从谷仓到储罐运送X个单位牛奶的总时间最少。

hint:
FJ wants to send 15 units of milk through his pipe network.  Pipe #1 connects junction point 1 (the barn) to junction point 2, and has a latency of 10 and a capacity of 3.  Pipes #2 and #3 are similarly defined.

The path 1->3 takes 14 + 15/1 = 29 units of time.  The path 1->2->3 takes 20 + 15/2 = 27.5 units of time, and is therefore optimal.

约翰想要通过管网运送15个单位的牛奶。管道1连接节点1（谷仓）和节点2，延迟为10，容量为3。管道2和管道3也以相似的方式来定义。

路径1->3花费14+15/1=29个单位的时间。路径1->2->3花费20+15/2=27.5个单位的时间，用时最少。


title: [USACO12DEC] Gangs of Istanbull/Cowstantinople G

description:
Life is tough on the farm, and when life is tough you have to get tough. The cows have formed gangs (conveniently numbered 1 to M).  The gangs coexisted in peace for a while, but now things are really getting out of control!

The cows are competing over control of a great grazing field.  This conflict happens over a series of minutes.  Each minute a single cow walks into the field.  If the field is empty the new cow's gang is considered to take control of the field.  If the field is already controlled by the new cow's gang then the cow just starts grazing.  Otherwise, a single cow from the controlling gang that is grazing confronts the new cow.

These confrontations between two cows start with some arguing and inevitably end up with the pair coming to realize how much more more alike than different they are.  The cows, seeing the error in their ways, leave the gang and the field and get a cold glass of soy milk at FJ's tavern.  If after this confrontation the field is empty than no gang controls the field.

Bessie realizes how these confrontations will occur.  She knows how many cows are in each gang.  Bessie really wants her gang to control the field after the conflict is over and all cows are either on the field or at FJ's tavern.  Help Bessie determine if it is possible for her gang, labeled 1, to control the field in the end.

If it is possible, Bessie wants to know the maximum number of cows from her gang that could be on the field at the end.  Output this number and the lexicographically earliest ordering of cows that results in this number of cows from Bessie's gang at the end.  An ordering X is said to be lexicographically earlier than Y if there is some k such that X[k] < Y[k] and X[i] = Y[i] for i < k.

n头牛结成了m个帮派，现在它们争夺一块草地。每个单位时间内会有一头牛来。如果草地上还没有牛或者只有自己帮派的牛，他会留在这里。但如果已经有别的帮派的牛，它们会打一架，这使得当前牛和草地上的一头牛去找农夫思考人生。问如何安排来的牛的编号顺序，能使一  号帮派最后有最多的牛留在草地上，如果不为0，还要输出字典序最小的一组方案。

inputFormat:
\* Line 1: N (1 <= N <= 100) and M (1 <= M <= N) separated by a space. The total number of cows in all the gangs will be N.  The total number of gangs is M.

\* Lines 2..1+M: The (1+i)th line indicates how many members are in gang i.  Each gang has at least 1 member.

outputFormat:
\* Line 1: Output YES on a single line if Bessie's gang can control the field after the conflict.  Otherwise output NO on a single line.

\* Line 2: If Bessie's gang can control the field after the conflict output the maximum number of cows that could be on the field on a single line.

\* Lines 3..2+N: On the (i+2)th line output the index of the gang of the cow that appears in the ith minute in the

lexicographically earliest ordering that leaves the maximum number of cows on the field after the conflict.

hint:
There are 5 cows and 3 gangs.  Bessie's gang (gang 1) has 2 members, gang 2 has 1 member, and gang 3 has 2 members.

Only one cow from Bessie's gang can end up on the field.


title: [USACO12DEC] First! G

description:
Bessie has been playing with strings again. She found that by

changing the order of the alphabet she could make some strings come before all the others lexicographically (dictionary ordering).

For instance Bessie found that for the strings "omm", "moo", "mom", and "ommnom" she could make "mom" appear first using the standard alphabet and that she could make "omm" appear first using the alphabet

"abcdefghijklonmpqrstuvwxyz".  However, Bessie couldn't figure out any way to make "moo" or "ommnom" appear first.

Help Bessie by computing which strings in the input could be

lexicographically first by rearranging the order of the alphabet.  To compute if string X is lexicographically before string Y find the index of the first character in which they differ, j.  If no such index exists then X is lexicographically before Y if X is shorter than Y.  Otherwise X is lexicographically before Y if X[j] occurs earlier in the alphabet than Y[j].

Bessie一直在研究字符串。她发现，通过改变字母表的顺序，她可以按改变后的字母表来排列字符串（字典序大小排列）。

例如，Bessie发现，对于字符串串“omm”，“moo”，“mom”和“ommnom”，她可以使用标准字母表使“mom”排在第一个（即字典序最小），她也可以使用字母表“abcdefghijklonmpqrstuvwxyz”使得“omm”排在第一个。然而，Bessie想不出任何方法（改变字母表顺序）使得“moo”或“ommnom”排在第一个。

接下来让我们通过重新排列字母表的顺序来计算输入中有哪些字符串可以排在第一个（即字典序最小），从而帮助Bessie。

要计算字符串X和字符串Y按照重新排列过的字母表顺序来排列的顺序，先找到它们第一个不同的字母X[i]与Y[i]，按重排后的字母表顺序比较，若X[i]比Y[i]先，则X的字典序比Y小，即X排在Y前；若没有不同的字母，则比较X与Y长度，若X比Y短，则X的字典序比Y小，即X排在Y前。

inputFormat:
\* Line 1: A single line containing N (1 <= N <= 30,000), the number of strings Bessie is playing with.

\* Lines 2..1+N: Each line contains a non-empty string.  The total number of characters in all strings will be no more than 300,000.  All characters in input will be lowercase characters 'a' through 'z'.  Input will contain no duplicate strings.

第1行：一个数字N（1 <= N <= 30,000），Bessie正在研究的字符串的数量。

第2~N+1行：每行包含一个非空字符串。所有字符串包含的字符总数不会超过300,000。 输入中的所有字符都是小写字母，即a~z。 输入不包含重复的字符串。

outputFormat:
\* Line 1: A single line containing K, the number of strings that could be lexicographically first.

\* Lines 2..1+K: The (1+i)th line should contain the ith string that could be lexicographically first.  Strings should be output in the same order they were given in the input.

第1行：一个数字K，表示按重排后的字母表顺序排列的字符串有多少可以排在第一个数量。

第2~K+1行：第i+1行包含第i个按重排后的字母表顺序排列后可以排在第一个的字符串。字符串应该按照它们在输入中的顺序来输出。

hint:
The example from the problem statement.

Only "omm" and "mom" can be ordered first.

样例即是题目描述中的例子，只有“omm”和“mom”在各自特定的字典序下可以被排列在第一个。


title: [USACO12DEC] Running Away From the Barn G

description:
给定一颗 $n$ 个点的有根树，边有边权，节点从 $1$ 至 $n$ 编号，$1$ 号节点是这棵树的根。

再给出一个参数 $t$，对于树上的每个节点 $u$，请求出 $u$ 的子树中有多少节点满足该节点到 $u$ 的距离不大于 $t$。

inputFormat:
输入的第一行是两个整数，分别表示节点数 $n$ 和给出的参数 $t$。

第 $2$ 到第 $n$ 行，每行两个整数，第 $i$ 行的整数 $p_i, w_i$ 表示节点 $i$ 的父节点为 $p_i$，连结 $i$ 与 $p_i$ 的边的边权为 $w_i$。

outputFormat: 输出 $n$ 行，每行一个整数，第 $i$ 行的整数表示 $i$ 的子树内到 $i$ 的距离不大于 $t$ 的节点个数。

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

对于全部的测试点，保证：

- $1 \leq n \leq 2 \times 10^5$，$1 \leq t \leq 10^{18}$。
- $1 \leq p_i \lt i$，$1 \leq w_i \leq 10^{12}$。


title: [USACO12OPEN] Balanced Cow Subsets G

description:
Farmer John's owns N cows (2 <= N <= 20), where cow i produces M(i) units of milk each day (1 <= M(i) <= 100,000,000).  FJ wants to streamline the process of milking his cows every day, so he installs a brand new milking machine in his barn.  Unfortunately, the machine turns out to be far too sensitive: it only works properly if the cows on the left side of the barn have the exact same total milk output as the cows on the right side of the barn!

Let us call a subset of cows "balanced" if it can be partitioned into two groups having equal milk output.  Since only a balanced subset of cows can make the milking machine work, FJ wonders how many subsets of his N cows are balanced.  Please help him compute this quantity.

inputFormat:
\* Line 1: The integer N.

\* Lines 2..1+N: Line i+1 contains M(i).

outputFormat: \* Line 1: The number of balanced subsets of cows.

translation:
我们定义一个奶牛集合 $S$ 是平衡的，当且仅当满足以下两个条件：

- $S$ 非空。
- $S$ 可以被**划分**成两个集合 $A,B$，满足 $A$ 里的奶牛产奶量之和等于 $B$ 里的奶牛产奶量之和。划分的含义是，$A\cup B=S$ 且 $A\cap B=\varnothing$。

现在给定大小为 $n$ 的奶牛集合 $S$，询问它有多少个子集是平衡的。请注意，奶牛之间是互不相同的，但是它们的产奶量可能出现相同。

### 输入格式

第一行一个整数 $n$，表示奶牛的数目。

第 $2$ 至 $n+1$ 行，每行一个数 $a_i$，表示每头奶牛的产奶量。

### 输出格式

输出一个数表示方案总数。

### 样例解释

共存在三种方案。集合 $\{1,2,3\}$ 可以划分为 $\{1,2\}$ 与 $\{3\}$；集合 $\{1,3,4\}$ 可以划分为 $\{1,3\}$ 与 $\{4\}$；集合 $\{1,2,3,4\}$ 可以划分为 $\{1,4\}$ 与 $\{2,3\}$，共 $3$ 种子集。

### 数据范围及约定

对于全部数据，保证 $1\le n\le 20$，$1\le a_i\le 10^8$。

hint:
There are 4 cows, with milk outputs 1, 2, 3, and 4.

There are three balanced subsets: the subset {1,2,3}, which can be partitioned into {1,2} and {3}, the subset {1,3,4}, which can be partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be partitioned into {1,4} and {2,3}.


title: [USACO13JAN] Party Invitations S

description:
Farmer John is throwing a party and wants to invite some of his cows to show them how much he cares about his herd.  However, he also wants to invite the smallest possible number of cows, remembering all too well the disaster that resulted the last time he invited too many cows to a party.

Among FJ's cows, there are certain groups of friends that are hard to separate.  For any such group (say, of size k), if FJ invites at least k-1 of the cows in the group to the party, then he must invite the final cow as well, thereby including the entire group.  Groups can be of any size and may even overlap with each-other, although no two groups contain exactly the same set of members.  The sum of all group sizes is at most 250,000.

Given the groups among FJ's cows, please determine the minimum number of cows FJ can invite to his party, if he decides that he must definitely start by inviting cow #1 (his cows are conveniently numbered 1..N, with N at most 1,000,000).

inputFormat:
\* Line 1: Two space-separated integers: N (the number of cows), and G (the number of groups).

\* Lines 2..1+G: Each line describes a group of cows.  It starts with an integer giving the size S of the group, followed by the S cows in the group (each an integer in the range 1..N).

outputFormat: \* Line 1: The minimum number of cows FJ can invite to his party.

translation:
农夫约翰要举办一个聚会，他要邀请一些奶牛来参加。在约翰的奶牛朋友圈中，有一些奶牛是好基友，对于每一个奶牛朋友圈，没有一个完全与之相同的，假设这个奶牛朋友圈有 $k$ 头奶牛，如果约翰已经邀请了 $k-1$ 头，那么剩下的那头牛也得邀请。约翰想让你告诉他，他最少需要邀请多少头奶牛？我们假设 $1$ 号奶牛已经被邀请了。

**【输入格式】**

第一行 $N$ 和 $G$ 表示共有 $N$ 头奶牛和 $G$ 个朋友圈。

接下来 $G$ 行，每行开头输入一个整数 $k$，表示朋友圈里有 $k$ 头牛，接着输入 $k$ 个整数，表示朋友圈里的牛。

**【输出格式】**

一行，一个整数，表示约翰最少需要邀请的牛的头数。

**【数据范围】**

$1 \leq  N\leq1000000$。

设所有的奶牛朋友圈的大小之和为 $M$，则 $1 \leq  M\leq250000$。

hint:
There are 10 cows and 4 groups.  The first group contains cows 1 and 3, and so on.

In addition to cow #1, FJ must invite cow #3 (due to the first group constraint), cow #4 (due to the second group constraint), and also cow #2 (due to the final group constraint).


title: [USACO13JAN] Cow Lineup G

description:
Farmer John's N cows (1 <= N <= 100,000) are lined up in a row.  Each cow is identified by an integer "breed ID" in the range 0...1,000,000,000; the breed ID of the ith cow in the lineup is B(i).  Multiple cows can share the same breed ID.

FJ thinks that his line of cows will look much more impressive if there is a large contiguous block of cows that all have the same breed ID.  In order to create such a block, FJ chooses up to K breed IDs and removes from his lineup all the cows having those IDs.  Please help FJ figure out the length of the largest consecutive block of cows with the same breed ID that he can create by doing this.

农夫约翰的N(1 <= N <= 100,000)只奶牛排成了一队，每只牛都用编上了一个“血统编号”，该编号为范围0...1,000,000,000的整数。血统相同的奶牛有相同的编号，也就是可能有多头奶牛是相同的"血统编号"。

约翰觉得如果连续排列的一段奶牛有相同的血统编号的话，奶牛们看起来会更具有威猛。为了创造这样的连续段，约翰最多能选出k种血统的奶牛，并把他们全部从队列中赶走。

请帮助约翰计算这样做能得到的由相同血统编号的牛构成的连续段的长度最大是多少？

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

\* Lines 2..1+N: Line i+1 contains the breed ID B(i).

outputFormat:
\* Line 1: The largest size of a contiguous block of cows with

identical breed IDs that FJ can create.

hint:
There are 9 cows in the lineup, with breed IDs 2, 7, 3, 7, 7, 3, 7, 5, 7. FJ would like to remove up to 1 breed ID from this lineup.

By removing all cows with breed ID 3, the lineup reduces to 2, 7, 7, 7, 7, 5, 7.  In this new lineup, there is a contiguous block of 4 cows with the same breed ID (7).


title: [USACO13JAN] Island Travels G

description:
Farmer John has taken the cows to a vacation out on the ocean! The cows are living on N (1 <= N <= 15) islands, which are located on an R x C grid (1 <= R, C <= 50). An island is a maximal connected group of squares on the grid that are marked as 'X', where two 'X's are connected if they share a side. (Thus, two 'X's sharing a corner are not necessarily connected.)

Bessie, however, is arriving late, so she is coming in with FJ by helicopter. Thus, she can first land on any of the islands she chooses. She wants to visit all the cows at least once, so she will travel between islands until she has visited all N of the islands at least once.

FJ's helicopter doesn't have much fuel left, so he doesn't want to use it until the cows decide to go home. Fortunately, some of the squares in the grid are shallow water, which is denoted by 'S'. Bessie can swim through these squares in the four cardinal directions (north, east, south, west) in order to travel between the islands. She can also travel (in the four cardinal directions) between an island and shallow water, and vice versa.

Find the minimum distance Bessie will have to swim in order to visit all of the islands. (The distance Bessie will have to swim is the number of distinct times she is on a square marked 'S'.) After looking at a map of the area, Bessie knows this will be possible.

给你一张r\*c的地图，有’S’,’X’,’.’三种地形，所有判定相邻与行走都是四连通的。我们设’X’为陆地，一个’X’连通块为一个岛屿，’S’为浅水，’.’为深水。刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。Q：你最少要经过几个浅水区？保证有解。

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

\* Lines 2..R+1: Line i+1 contains C characters giving row i of the grid. Deep water squares are marked as '.', island squares are marked as 'X', and shallow water squares are marked as 'S'.

outputFormat: \* Line 1: A single integer representing the minimum distance Bessie has to swim to visit all islands.

hint:
There are three islands with shallow water paths connecting some of them.

Bessie can travel from the island in the top left to the one in the middle, swimming 1 unit, and then travel from the middle island to the one in the bottom right, swimming 2 units, for a total of 3 units.


title: [USACO13JAN] Seating G

description:
To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes.  The restaurant has N seats (1 <= N <= 500,000) in a row. Initially, they are all empty.

Throughout the day, there are M different events that happen in sequence at the restaurant (1 <= M <= 300,000).  The two types of events that can happen are:

1. A party of size p arrives (1 <= p <= N). Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats.  If it is impossible, the party is turned away.

2. A range [a,b] is given (1 <= a <= b <= N), and everybody in that range of seats leaves.

Please help Bessie count the total number of parties that are turned away over the course of the day.

有一排n个座位，m次操作。A操作：将a名客人安置到最左的连续a个空位中，没有则不操作。L操作：[a,b]的客人离开。

求A操作的失败次数。

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

\* Lines 2..M+1: Each line describes a single event.  It is either a line of the form "A p" (meaning a party of size p arrives) or "L a b" (meaning that all cows in the range [a, b] leave).

outputFormat: \* Line 1: The number of parties that are turned away.

hint:
There are 10 seats, and 4 events.  First, a party of 6 cows arrives.  Then all cows in seats 2..4 depart.  Next, a party of 5 arrives, followed by a party of 2.

Party #3 is turned away.  All other parties are seated.


title: [USACO13FEB] Perimeter S

background: 征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

description:
Farmer John has arranged N hay bales (1 <= N <= 50,000) in the middle of one of his fields.  If we think of the field as a 1,000,000 x 1,000,000 grid of 1 x 1 square cells, each hay bale occupies exactly one of these cells (no two hay bales occupy the same cell, of course).

FJ notices that his hay bales all form one large connected region, meaning that starting from any bale, one can reach any other bale by taking a series of steps either north, south, east, or west onto directly adjacent bales.  The connected region of hay bales may however contain "holes" -- empty regions that are completely surrounded by hay bales.

Please help FJ determine the perimeter of the region formed by his hay bales.  Note that holes do not contribute to the perimeter.

inputFormat:
\* Line 1: The number of hay bales, N.

\* Lines 2..1+N: Each line contains the (x,y) location of a single hay bale, where x and y are integers both in the range

1..1,000,000. Position (1,1) is the lower-left cell in FJ's field, and position (1000000,1000000) is the upper-right cell.

outputFormat: \* Line 1: The perimeter of the connected region of hay bales.

translation:
农夫约翰已经在他的一片田地中间放置了n（1<=n<=50000）个干草堆。我们可以认为这片田地是由1000000*1000000 个小方格组成的矩阵，每个干草堆占据一个小方格（当然，没有两堆干草占据同一个格子）

FJ 注意到他的干草堆组成了一个大的连通块，这就意味着从任何一个草堆走起，可以通过相邻草堆走若干步到达其他任意的草堆。这个连通块的内部可能包含若干个“洞”——被干草堆完全包围的空白格子。

请帮助FJ计算整个连通块的周长。计算周长时请不要考虑“洞”。

##   输入格式

第一行：干草堆的数量 n

第2~n+1行：每行两个数，表示干草堆的坐标（x，y），满足1<=x,y<=1000000

## 输出格式
连通块的周长p

hint:
The connected region consisting of hay bales looks like this:

XX
X XX
XXX

The length of the perimeter of the connected region is 14 (for example, the left side of the region contributes a length of 3 to this total).  Observe that the hole in the middle does not contribute to this number.


title: [USACO13FEB] Tractor S

description:
One of Farmer John's fields is particularly hilly, and he wants to purchase a new tractor to drive around on it.  The field is described by an N x N grid of non-negative integer elevations (1 <= N <= 500).  A tractor capable of moving from one grid cell to an adjacent cell (one step north, east, south, or west) of height difference D costs exactly D units of money.

FJ would like to pay enough for his tractor so that, starting from some grid cell in his field, he can successfully drive the tractor around to visit at least half the grid cells in the field (if the number of total cells in the field is odd, he wants to visit at least half the cells rounded up).  Please help him compute the minimum cost necessary for buying a tractor capable of this task.

inputFormat:
\* Line 1: The value of N.

\* Lines 2..1+N: Each line contains N space-separated non-negative integers (each at most 1 million) specifying a row of FJ's field.

outputFormat: \* Line 1: The minimum cost of a tractor that is capable of driving around at least half of FJ's field.

translation:
题目描述

FJ有块农田太崎岖了，他要买一辆新拖拉机才能在这里巡视。这块农田由N x N个格子的非负整数表示高度(1<=N<=500)。拖拉机从当前格子走到相邻格子（东、南、西、北四个方向）的代价为高度差D，则FJ驶过这两个格子的拖拉机最少也要值D块钱。

FJ愿意花足够的钱买一辆新的拖拉机使得他能以最小的高度差走遍所有格子的一半(如果格子总数是奇数，那么一半的值为四舍五入的值)。因为FJ很懒，所以他找到你帮他编程计算他最小需要花多少钱买到符合这些要求的拖拉机。

输入输出格式

输入格式：

第一行为一个整数N

第2到N+1行每行包含N个非负整数（不超过1,000,000），表示当前格子的高度。

输出格式：

共一行，表示FJ买拖拉机要花的最小价钱。


title: [USACO13FEB] Milk Scheduling S

description:
Farmer John's N cows (1 <= N <= 10,000) are conveniently numbered 1..N. Each cow i takes T(i) units of time to milk.  Unfortunately, some cows must be milked before others, owing to the layout of FJ's barn.  If cow A must be milked before cow B, then FJ needs to completely finish milking A before he can start milking B.

In order to milk his cows as quickly as possible, FJ has hired a large number of farmhands to help with the task -- enough to milk any number of cows at the same time.  However, even though cows can be milked at the same time, there is a limit to how quickly the entire process can proceed due to the constraints requiring certain cows to be milked before others.  Please help FJ compute the minimum total time the milking process must take.

农民约翰有N头奶牛(1<=N<=10,000)，编号为1...N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是，由于FJ的仓库布局，一些奶牛要在别的牛之前挤奶。比如说，如果奶牛A必须在奶牛B前挤奶，FJ就需要在给奶牛B挤奶前结束给奶牛A的挤奶。

为了尽量完成挤奶任务，FJ聘请了一大批雇工协助任务——同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请帮助FJ计算挤奶过程中的最小总时间。

inputFormat:
\* Line 1: Two space-separated integers: N (the number of cows) and M (the number of milking constraints; 1 <= M <= 50,000).

\* Lines 2..1+N: Line i+1 contains the value of T(i) (1 <= T(i) <= 100,000).

\* Lines 2+N..1+N+M: Each line contains two space-separated integers A and B, indicating that cow A must be fully milked before one can start milking cow B.  These constraints will never form a cycle, so a solution is always possible.

outputFormat: \* Line 1: The minimum amount of time required to milk all cows.

hint:
There are 3 cows.  The time required to milk each cow is 10, 5, and 6, respectively.  Cow 3 must be fully milked before we can start milking cow 2.

Cows 1 and 3 can initially be milked at the same time.  When cow 3 is finished with milking, cow 2 can then begin.  All cows are finished milking after 11 units of time have elapsed.


title: [USACO13FEB] Partitioning the Farm G

description:
Farmer John's farm is divided into an N x N square grid of pastures (2 <= N <= 15). Right now, there is a fence around the outside of the farm, but cows can move freely from pasture to pasture.

Farmer John has decided to build fences to separate the cows from each other. Because of zoning laws, each fence must be a horizontal or vertical line going across the entire farm and fences cannot go through pastures. Farmer John only has enough money to build at most K fences (1 <= K <= 2N - 2).

Farmer John wants to build the fences in order to minimize the size of the largest resulting group of cows (two cows are in the same group if they can reach each other without going through any fences). Given the current number of cows in each pasture, help Farmer John compute the size of the largest group of cows if he builds the fences optimally.

给出一个n\*n的矩阵，用k条水平或竖直直线分割矩阵，最小化区域和最大值。

inputFormat:
\* Line 1: Two integers, N and K

\* Lines 2..1+N: There are N numbers per line, describing the cows in each pasture for one row of the farm (there are at least 0 and at most 1000 cows in each pasture)

outputFormat: \* Line 1: The minimum possible size of the largest group of cows.

hint: Farmer John should build fences between columns 2 and 3 and between rows 2 and 3, which creates 4 groups each with 4 cows.


title: [USACO13FEB] Taxi G

description:
Bessie is running a taxi service for the other cows on the farm.  The cows have been gathering at different locations along a fence of length M (1 <= M <= 1,000,000,000).  Unfortunately, they have grown bored with their current locations and each wish to go somewhere else along the fence.  Bessie must pick up each of her friends at their starting positions and drive them to their destinations.  Bessie's car is small so she can only transport one cow in her car at a time.  Cows can enter and exit the car instantaneously.

To save gas, Bessie would like to minimize the amount she has to drive.  Given the starting and ending positions of each of the N cows (1 <= N <= 100,000), determine the least amount of driving Bessie has to do.  Bessie realizes that to save the most gas she may need to occasionally drop a cow off at a position other than her destination.

Bessie starts at the leftmost point of the fence, position 0, and must finish her journey at the rightmost point on the fence, position M.

长度为m的栅栏上，有n头牛需要坐车前往别的地方，起点和终点分别为a\_i和b\_i。现在一辆出租车从最左端0出发，要运送完所有牛，最后到达最右端m，求最小路程。出租车只能一次载一只牛。

inputFormat:
\* Line 1: N and M separated by a space.

\* Lines 2..1+N: The (i+1)th line contains two space separated

integers, s\_i and t\_i (0 <= s\_i, t\_i <= M), indicating the starting position and destination position of the ith cow.

outputFormat: \* Line 1: A single integer indicating the total amount of driving Bessie must do.  Note that the result may not fit into a 32 bit integer.

hint:
There are two cows waiting to be transported along a fence of length 10. The first cow wants to go from position 0 (where Bessie starts) to position 9.  The second cow wishes to go from position 6 to position 5.

Bessie picks up the first cow at position 0 and drives to position 6. There she drops off the first cow, delivers the second cow to her destination and returns to pick up the first cow.  She drops off the first cow and then drives the remainder of the way to the right side of the fence.


title: [USACO13FEB] Route Design G

description:
After escaping from the farm, Bessie has decided to start a travel agency along the Amoozon river.  There are several tourist sites located on both sides of the river, each with an integer value indicating how interesting the tourist site is.

Tourist sites are connected by routes that cross the river (i.e., there are no routes connecting a site with a site on the same side of the river).  Bessie wants to design a tour for her customers and needs your help.  A tour is a sequence of tourist sites with adjacent sites connected by a route. In order to best serve her customers she wants to find the route that maximizes the sum of the values associated with each visited site.

However, Bessie may be running several of these tours at the same time.  Therefore it's important that no two routes on a tour

intersect.  Two routes (a <-> x) and (b <-> y) intersect if and only if (a < b and y < x) or (b < a and x < y) or (a = b and x = y).

Help Bessie find the best tour for her agency.  Bessie may start and end at any site on either side of the Amoozon.

河左岸有n个点，右岸有m个点，各有权值。有R条跨河的桥，求一条不交叉的路径使得点权和最大。

(a <-> b) 与 (x <-> y) 交叉指(a < b and y < x) or (b < a and x < y) or (a = b and x = y)。

inputFormat:
\* Line 1: Three space separated integers N (1 <= N <= 40,000), M (1 <= M <= 40,000), and R (0 <= R <= 100,000) indicating

respectively the number of sites on the left side of the river, the number of sites on the right side of the river, and the number of routes.

\* Lines 2..N+1: The (i+1)th line has a single integer, L\_i (0 <= L\_i <= 40,000), indicating the value of the ith tourist site on the left side of the river.

\* Lines N+2..N+M+1: The (i+N+1)th line has a single integer, R\_i (0 <= R\_i <= 40,000), indicating the value of the ith tourist site on the right side of the river.

\* Lines N+M+2..N+M+R+1: Each line contains two space separated integers I (1 <= I <= N) and J (1 <= J <= M) indicating there is a bidirectional route between site I on the left side of the river and site J on the right side of the river.

outputFormat: \* Line 1: A single integer indicating the maximum sum of values attainable on a tour.

hint:
There are three sites on the left side of the Amoozon with values 1, 1, and 5.  There are two sites on the right side of the Amoozon with values 2 and 2.  There are four routes connecting sites on both sides of the river.

The optimal tour goes from site 1 on the left, site 1 on the right, and ends at site 3 on the left.  These respectively have values 1, 2, and 5 giving a total value of the trip of 8.


title: [USACO13MAR] Poker Hands S

description:
Bessie and her friends are playing a unique version of poker involving a deck with N (1 <= N <= 100,000) different ranks, conveniently numbered 1..N (a normal deck has N = 13). In this game, there is only one type of hand the cows can play: one may choose a card labeled i and a card labeled j and play one card of every value from i to j.  This type of hand is called a "straight".

Bessie's hand currently holds a\_i cards of rank i (0 <= a\_i <= 100000). Help her find the minimum number of hands she must play to get rid of all her cards.

inputFormat:
\* Line 1: The integer N.

\* Lines 2..1+N: Line i+1 contains the value of a\_i.

outputFormat: \* Line 1: The minimum number of straights Bessie must play to get rid of all her cards.

translation:
Bessie 有 $n$ 堆牌，每堆牌有 $a_i$ 张。她一次可以将第 $i$ 堆到第 $j$ 堆里打一张出去，求打完 $n$ 堆牌最少的次数。

对于 $100\%$ 的数据，$1\le n\le10^5,0\le a_i\le10^5$。

hint: Bessie can play a straight from 1 to 5, a straight from 1 to 2, a straight from 4 to 5, two straights from 2 to 2, and a straight from 5 to 5, for a total of 6 rounds necessary to get rid of all her cards.


title: [USACO13MAR] Farm Painting S

description:
After several harsh winters, Farmer John has decided it is time to re-paint his farm.  The farm consists of N fenced enclosures (1 <= N <= 50,000), each of which can be described by a rectangle in the 2D plane whose sides are parallel to the x and y axes.  Enclosures may be contained within other enclosures, but no two fences intersect, so if two enclosures cover the same area of the 2D plane, one must be contained within the other.

FJ figures that an enclosure contained within another enclosure will not be visible to the outside world, so he only wants to re-paint enclosures that are themselves not contained within any other enclosures.  Please help FJ determine the total number of enclosures he needs to paint.

经过几个严冬，农场主约翰决定是重新粉刷农场的时候了。该农场由$n$个围栏围成（$1<=n=50000$），每一个都可以用二维平面上的矩形来描述，其两侧平行于x和y轴。牛圈可能包含在其他牛圈中，但没有两个栅栏相交（不同牛圈的边不会有接触）。因此如果两个牛圈覆盖了二维平面的同一区域，那么一个必须包含在另一个内。

FJ知道，被其他牛圈包含的牛圈是不会被外面的人看到的。众所周知，FJ非常懒，所以他只想刷露在外面的牛圈，请帮助他求出总共需要刷的牛圈的个数。

inputFormat:
\* Line 1: The number of enclosures, N.

\* Lines 2..1+N: Each line describes an enclosure by 4 space-separated integers x1, y1, x2, and y2, where (x1,y1) is the lower-left corner of the enclosure and (x2,y2) is the upper-right corner. All coordinates are in the range 0..1,000,000.

第一行 一个数，牛圈的总数$n$

第二到$n+1$行 每行四个数，起点坐标$x1,y1$和终点坐标$x2,y2$

outputFormat:
\* Line 1: The number of enclosures that are not contained within other enclosures.

FJ总共需要刷的牛圈的个数

hint:
There are three enclosures.  The first has corners (2,0) and (8,9), and so on.

Enclosure 3 is contained within enclosure 1, so there are two enclosures not contained within other enclosures.


title: [USACO13MAR] The Cow Run G/S

description:
Farmer John has forgotten to repair a hole in the fence on his farm, and his N cows (1 <= N <= 1,000) have escaped and gone on a rampage! Each minute a cow is outside the fence, she causes one dollar worth of damage. FJ must visit each cow to install a halter that will calm the cow and stop the damage.

Fortunately, the cows are positioned at distinct locations along a straight line on a road outside the farm. FJ knows the location P\_i of each cow i (-500,000 <= P\_i <= 500,000, P\_i != 0) relative to the gate (position 0) where FJ starts.

FJ moves at one unit of distance per minute and can install a halter instantly. Please determine the order that FJ should visit the cows so he can minimize the total cost of the damage; you should compute the minimum total damage cost in this case.

农夫约翰的牧场围栏上出现了一个洞，有 $N$（$1\le N\le 1000$）只牛从这个洞逃出了牧场。这些出逃的奶牛很狂躁，他们在外面到处搞破坏，每分钟每头牛都会给约翰带来 $1$ 美元的损失。约翰必须用缰绳套住所有的牛，以停止他们搞破坏。

幸运的是，奶牛们都在牧场外一条笔直的公路上，牧场的大门恰好位于公里的 $0$ 点处。约翰知道每头牛距离牧场大门的距离 $P_i$（$-5\times10^5\le P_i\le5\times 10^5$，$P_i\ne0$）。

约翰从农场大门出发，每分钟移动一个单位距离，每到一头牛所在的地点，约翰就会给它套上缰绳，套缰绳不花时间。按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少？

inputFormat:
\* Line 1: The number of cows, N.

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

outputFormat: \* Line 1: The minimum total cost of the damage.

hint:
Four cows placed in positions: -2, -12, 3, and 7.

The optimal visit order is -2, 3, 7, -12. FJ arrives at position -2 in 2 minutes for a total of 2 dollars in damage for that cow.

He then travels to position 3 (distance: 5) where the cumulative damage is 2 + 5 = 7 dollars for that cow.

He spends 4 more minutes to get to 7 at a cost of 7 + 4 = 11 dollars for that cow.

Finally, he spends 19 minutes to go to -12 with a cost of 11 + 19 = 30 dollars.

The total damage is 2 + 7 + 11 + 30 = 50 dollars.


title: [USACO13MAR] Hill Walk G

description:
There are N hills (1 <= N <= 100,000). Each hill takes the form of a line segment from (x1, y1) to (x2, y2) where x1 < x2 and y1 < y2. None of these segments intersect or touch, even at their endpoints, and furthermore, the first hill satisfies (x1, y1) = (0,0).

Bessie the cow starts at (0,0) on the first hill. Whenever Bessie is on a hill, she climbs up until she reaches the end. Then she jumps off the edge. If she lands on another hill, she continues walking on that hill; otherwise, she falls very far until she lands safely on a cushion of pillows at y = -infinity.  Each hill (x1, y1) -> (x2, y2) should be regarded as containing the point (x1, y1) but not containing the point (x2, y2), so that Bessie will land on the hill if she falls on it from above at a position with x = x1, but she will not land on the hill if she falls on it from above at x = x2.

Please count the total number of hills that Bessie touches at some point during her walk.

有 $N(1 \le N \le 10 ^ 5)$座小山，每座山所占的区域用直线 $(x1, y1)$ 到 $(x2, y2)$ 来表示（$x1 < x2$ 并且 $y1 < y2$）。也就是说这些山用笛卡尔坐标系里的线段来表示，这些用于表示小山的线段都没有任何交点，第一座山的一端位于 $(x1, y1) = (0,0)$。

贝西从 $(0,0)$ 开始在第一座山上漫步，一旦贝西到了一座山，她会一直走到该山的终点，这时，她会从边缘处起跳，如果她降落到另一座山上，她会继续在新的山上漫步。贝西起跳后沿 $y$ 轴方向下落，如果贝西不能降落到一座山上，她会一直下落，直到到达 $y$ 轴的负无穷大位置（$y = -\infin$）。

每座用线段表示的山 $(x1, y1) \to (x2, y2)$ 包含 $(x1, y1)$ 这个点，但不包含 $(x2, y2)$，请计算出贝西总共在多少座山上漫步了。

inputFormat:
\* Line 1: The number of hills, N.

\* Lines 2..1+N: Line i+1 contains four integers (x1,y1,x2,y2)

describing hill i.  Each integer is in the range

0..1,000,000,000.

outputFormat: \* Line 1: The number of hills Bessie touches on her journey.

hint:
There are four hills.  The first hill runs from (0,0) to (5,6), and so on.

Bessie walks on hills #1, #4, and finally #3.


title: [USACO13MAR] Necklace G

description:
Bessie the cow has arranged a string of N rocks, each containing a single letter of the alphabet, that she wants to build into a fashionable necklace.

Being protective of her belongings, Bessie does not want to share her necklace with the other cow currently living on her side of the barn.  The other cow has a name that is a string of M characters, and Bessie wants to be sure that this length-M string does not occur as a contiguous substring anywhere within the string representing her necklace (otherwise, the other cow might mistakenly think the necklace is for her).  Bessie decides to remove some of the rocks in her necklace so that the other cow's name does not appear as a substring.  Please help Bessie determine the minimum number of rocks she must remove.

贝西收集了N颗石头，每颗石头上都有一个字母，贝西想把这些石头做成项链。

贝西的身边有另一只奶牛，这只奶牛的名字是一个长度为M的字符串，贝西不希望这只牛的名字出现在她的项链上(项链的子串)，她想知道，最少删掉几颗石头就可以避免这种情况发生。

inputFormat:
\* Line 1: The first line is a length-N string describing Bessie's initial necklace; each character is in the range "a" through "z".

\* Line 2: The second line is the length-M name of the other cow in the barn, also made of characters from "a" to "z".

outputFormat: \* Line 1: The minimum number of stones that need to be removed from Bessie's necklace so that it does not contain the name of the other cow as a substring.

hint:
```cpp
For at least 20% of test cases, N <= 20.
For at least 60% of test cases, N <= 1000, M <= 100.
For all test cases, N <= 10000, M <= 1000.
For all test cases, M <= N.
```
The modified necklace should be "abbaa".

---

$\text{upd 2022.7.29}$：新增加一组 Hack 数据。


title: [USACO13OPEN] Luxury River Cruise S

description:
Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1 <= N <= 1,000) labeled 1..N, and Bessie starts at port 1. Each port has exactly two rivers leading out of it which lead directly to other ports, and rivers can only be sailed one way.

At each port, the tour guides choose either the "left" river or the "right" river to sail down next, but they keep repeating the same choices over and over. More specifically, the tour guides have chosen a short sequence of M directions (1 <= M <= 500), each either "left" or "right", and have repeated it K times (1 <= K <= 1,000,000,000). Bessie thinks she is going in circles -- help her figure out where she ends up!

农民约翰带着Bessie和奶牛在邮轮上！他们在网格上的N条河流航行（1≤N≤1000）标记为1到N，一开始他们在开始在河口1。每一个港口都有两条河流直通，直接通往其他港口，河流只能通过一条路航行。

在每一个港口，导游选择左边的河或右边的河向下航行，但他们不断重复相同的选择一遍又一遍。更具体地说，导游选择了一个m方向（1 < =m= 500），每一个向左或向右，并重复它K次（1 < = K = 1000000000）。Bessie认为她是在兜圈子，帮她找出结束的位置！

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

\* Lines 2..N+1: Line i+1 has two space-separated integers,

representing the number of the ports that port i's left and right rivers lead to, respectively.

\* Line N+2: M space-separated characters, either 'L' or 'R'. 'L' represents a choice of  'left' and 'R' represents a choice of 'right'.

outputFormat: \* Line 1: A single integer giving the number of the port where Bessie's cruise ends.

hint:
The port numbers are arranged clockwise in a circle, with 'L' being a clockwise rotation and 'R' being a counterclockwise rotation. The sequence taken is LLRLLRLLR.

After the first iteration of the sequence of directions, Bessie is at port 2 (1 -> 2 -> 3 -> 2); after the second, she is at port 3 (2 -> 3 -> 4 -> 3), and at the end she is at port 4 (3 -> 4 -> 1 -> 4).

感谢 @ SilverWolf 提供翻译