title: [USACO09OPEN] Cow Line S

description:
Farmer John's N cows (conveniently numbered 1..N) are forming a line. The line begins with no cows and then, as time progresses, one by one, the cows join the line on the left or right side. Every once in a while, some number of cows on the left or right side of the line all leave the line to go graze in their favorite pasture.

FJ has trouble keeping track of all the cows in the line. Please help him.

The cows enter the line in numerical order 1..N, and once a cow leaves the line she never re-enters it. Your program will be given S (1 <= S <= 100,000) input specifications; each appears on a single line and is one of two types:

\* A cow enters the line (a parameter indicates whether on the left or right).

\* K cows leave the line from the left or right side (supplied parameters define both the number of cows and which side).

Input lines never request an operation that can not be performed.

After all the input lines have been processed, your program should print the cows in the line in order from left to right. The final line is guaranteed to be non-empty at the end of the input specifications.

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

\* Lines 2..S+1: Line i+1 contains specification i in one of four formats:

\* A L -- a cow arrives on the Left of the line

\* A R -- a cow arrives on the Right of the line

\* D L K -- K cows depart the Left side of the line

\* D R K -- K cows depart the Right side of the line

outputFormat: \* Lines 1..??: Print the numbers of the cows in the line in order from left to right, one number per line.

translation:
Farmer John（以下简称 FJ）的 $N$ 头奶牛（用 $1 \dots N$ 编号）在直线上排队。一开始，这条线上没有任何奶牛，随着时间的推移，奶牛们会一个接一个地站到队伍的左边或右边。又过了一会儿，某些奶牛会从队伍里离开，去吃自己最喜欢的草料。

FJ 无法跟踪每一头奶牛，于是，他想让你来帮助他。

奶牛以 $1 \dots N$ 的顺序排队，并且离开的奶牛不会再次回来。数据将会给出 $S$（$1 \le S \le 100000$） 条指令，各占一行，分两种：

- $A$ 头奶牛加入了队列（还有一个参数，表示从左加入还是从右加入）；
- $K$ 头奶牛从左边或者右边离开了队列（还有两个参数，分别表示从左离开还是从右离开和离开多少头奶牛）。

输入的命令一定是可以执行的。

所有的操作结束后，你的程序应该以从左到右的顺序输出这个奶牛队列。数据保证最后的队列不空。

**【输入格式】**

- 第 $1$ 行：单独一个整数 $S$。
- 第 $2 \dots S+1$ 行：第 $i+1$ 行会有一条命令，有以下几种：
  - `A L`：一头奶牛从队列左边加入；
  - `A R`：一头奶牛从队列右边加入；
  - `D L K`：$K$ 头奶牛从队伍左边离开；
  - `D R K`：$K$ 头奶牛从队伍右边离开。

**【输出格式】**

- 第 $1 \dots ??$ 行：从左到右输出最后的奶牛队列，一个奶牛编号占一行。

**【样例解释】**

以下为输入的命令及对应的队列：

- `A L`：$1$；
- `A L`：$2,1$；
- `A R`：$2,1,3$；
- `A L`：$4,2,1,3$；
- `D R 2`：$4,2$；
- `A R`：$4,2,5$；
- `A R`：$4,2,5,6$；
- `D L 1`：$2,5,6$；
- `A L`：$7,2,5,6$；
- `A R`（最终序列）：$7,2,5,6,8$。

samples:
10
A L
A L
A R
A L
D R 2
A R
A R
D L 1
A L
A R

hint:
Input    Resulting Cow Line

A L      1

A L      2 1

A R      2 1 3

A L      4 2 1 3

D R 2    4 2

A R      4 2 5

A R      4 2 5 6

D L 1    2 5 6

A L      7 2 5 6

A R      7 2 5 6 8

感谢@ ws\_fuweidong  提供翻译。


title: [USACO09OPEN] Cow Digit Game S

type: P

description:
Bessie is playing a number game against Farmer John, and she wants you to help her achieve victory.

Game i starts with an integer N\_i (1 <= N\_i <= 1,000,000). Bessie goes first, and then the two players alternate turns. On each turn, a player can subtract either the largest digit or the smallest non-zero digit from the current number to obtain a new number. For example, from 3014 we may subtract either 1 or 4 to obtain either 3013 or 3010, respectively. The game continues until the number becomes 0, at which point the last player to have taken a turn is the winner.

Bessie and FJ play G (1 <= G <= 100) games. Determine, for each game, whether Bessie or FJ will win, assuming that both play perfectly (that is, on each turn, if the current player has a move that will guarantee his or her win, he or she will take it).

Consider a sample game where N\_i = 13. Bessie goes first and takes 3, leaving 10. FJ is forced to take 1, leaving 9. Bessie takes the remainder and wins the game.

贝茜和约翰在玩一个数字游戏．贝茜需要你帮助她．

游戏一共进行了G(1≤G≤100)场．第i场游戏开始于一个正整数Ni(l≤Ni≤1,000,000)．游

戏规则是这样的：双方轮流操作，将当前的数字减去一个数，这个数可以是当前数字的最大数码，也可以是最小的非0数码．比如当前的数是3014，操作者可以减去1变成3013，也可以减去4变成3010．若干次操作之后，这个数字会变成0．这时候不能再操作的一方为输家．    贝茜总是先开始操作．如果贝茜和约翰都足够聪明，执行最好的策略．请你计算最后的赢家．

比如，一场游戏开始于13.贝茜将13减去3变成10．约翰只能将10减去1变成9．贝茜再将9减去9变成0．最后贝茜赢．

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

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

outputFormat: \* Lines 1..G: Line i contains 'YES' if Bessie can win game i, and 'NO' otherwise.

hint: For the first game, Bessie simply takes the number 9 and wins. For the second game, Bessie must take 1 (since she cannot take 0), and then FJ can win by taking 9.


title: [USACO09OPEN] Grazing2 S

description:
Farmer John has N (2 <= N <= 1,500) prize milk cows conveniently numbered 1..N. His newly-painted barn has S (N <= S <= 1,000,000) stalls (conveniently numbered 1..S) in a single long line; each stall is a unit distance from its neighboring stall(s).

The cows have made their way to the stalls for a rest; cow i is in stall P\_i. Antisocial as they are, the cows get grumpy if they are situated in stalls very close to each other, so Farmer John wants to move the cows to be as spread out as possible.

FJ wants to make sure that the N - 1 distances between adjacent cows are as large as possible, and he would also like them to be similar to each other (i.e., close to equi-distant spacing).

In particular, FJ would like all distances between adjacent cows to be at most 1 different from (S - 1) / (N - 1), where integer division is used. Moreover, he would like as many of these distances as possible to be exactly equal to (S - 1) / (N - 1) [integer

division]. Thus, with four cows and eight stalls, one can place the cows at positions 1, 3, 5, 8 or 1, 3, 6, 8 but not at 1, 2, 4, 7 or 1, 2, 4, 8.

Help FJ spread the cows as efficiently as possible by calculating and reporting the minimum total distance that the cows have to move in order to achieve proper spacing. Ignore the distance it takes for a cow to enter or exit a stall.

约翰有N(2≤N≤1500)头奶牛，S(N≤S≤1,000,000)个一字排开的牛棚．相邻牛棚间的距离恰好为1．

奶牛们已经回棚休息，第i只奶牛现在待在牛棚Pi．如果两只奶牛离得太近，会让奶牛们变得很暴躁．所以约翰想给一些奶牛换一个棚，让她们之间的距离变得尽量大，并且尽管接近．令d=Trunc((s-1)/(n-1))

所以约翰希望最终的奶牛的状态是：两只相邻奶牛间的距离与d之差不超过1，而且让尽量多的间距等于d．因此，对于4只奶牛8个棚的情况，1，3，5，8或1，3，6，8这样的安置情况是允许的，而1，2，4，7或1，2，4，8这样的情况是不允许的．    帮助约翰移动奶牛，让所有奶牛的移动距离之和最小，同时让最终的安置情况符合约翰心意．

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

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

outputFormat: \* Line 1: A single integer: the minimum total distance the cows have to travel. This number is guaranteed to be under 1,000,000,000 (thus fitting easily into a signed 32-bit integer).

hint:
1   2   3   4   5   6   7   8   9  10

Cow Locs     | A | B | C | . | . | . | . | D | E | . |

Cows move from stall 2 to 3, 3 to 5, and 9 to 10. The total distance moved is 1 + 2 + 1 = 4. The final positions of the cows are in stalls 1, 3, 5, 8, and 10.

1   2   3   4   5   6   7   8   9  10

Init Stall     | A | B | C | . | . | . | . | D | E | . |
Final Stall    | A | . | B | . | C | . | . | D | . | E |
Distance moved | 0 | . | 1 | . | 2 | . | . | 0 | . | 1 |


title: [USACO09OCT] Even? Odd? G

description:
Bessie's cruel second grade teacher has assigned a list of N (1 <= N <= 100) positive integers I (1 <= I <= 10^60) for which Bessie must determine their parity (explained in second grade as 'Even... or odd?'). Bessie is overwhelmed by the size of the list and by the size of the numbers. After all, she only learned to count recently.

Write a program to read in the N integers and print 'even' on a single line for even numbers and likewise 'odd' for odd numbers.

POINTS: 25

Bessie那惨无人道的二年级老师搞了一个有 N 个正整数 I 的表叫Bessie去判断“奇偶性”（这个词语意思向二年级的学生解释，就是“这个数是单数，还是双数啊？”）。Bessie被那个表的长度深深地震惊到了，竟然跟栋栋的泛做表格一样多道题！！！毕竟她才刚刚学会数数啊。

写一个程序读入N个整数，如果是双数，那么在单立的一行内输出"even"，如果是单数则类似地输出"odd".

数据范围：每个正整数不超过 ${10}^{60}$。

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

\* Lines 2..N+1: Line j+1 contains I\_j, the j-th integer to determine even/odd

outputFormat: \* Lines 1..N: Line j contains the word 'even' or 'odd', depending on the parity of I\_j

hint:
Two integers: 1024 and 5931

1024 is eminently divisible by 2; 5931 is not


title: [USACO09OCT] The Robot Plow G

description:
Farmer John has purchased a new robotic plow in order to relieve him from the drudgery of plowing field after field after field. It achieves this goal but at a slight disadvantage: the robotic plow can only plow in a perfect rectangle with sides of integer length.

Because FJ's field has trees and other obstacles, FJ sets up the plow to plow many different rectangles, which might end up overlapping. He's curious as to just how many squares in his field are actually plowed after he programs the plow with various plow instructions, each of which describes a rectangle by giving its lower left and upper right x,y coordinates.

As usual, the field is partitioned into squares whose sides are parallel to the x and y axes. The field is X squares wide and Y squares high (1 <= X <= 240; 1 <= Y <= 240). Each of the I (1 <= I <= 200) plow instructions comprises four integers: Xll, Yll, Xur, and Yur (1 <= Xll <= Xur; Xll <= Xur <= X; 1 <= Yll <= Yur; Yll <= Yur <= Y) which are the lower left and upper right coordinates of the rectangle to be plowed. The plow will plow all the field's squares in the range (Xll..Xur, Yll..Yur) which might be one more row and column than would initially be assumed (depending on how you go about your assumptions, of course).

Consider a field that is 6 squares wide and 4 squares high. As FJ issues a pair of plowing instructions (shown), the field gets plowed as shown by '\*' and '#' (normally plowed field all looks the same, but '#' shows which were most recently plowed):

```cpp
......             **....             #####.
......  (1,1)(2,4) **....  (1,3)(5,4) #####.
......             **....             **....
......             **....             **....
```
A total of 14 squares are plowed.

POINTS: 25

Farmer John为了让自己从无穷无尽的犁田工作中解放出来，于是买了个新机器人帮助他犁田。这个机器人可以完成犁田的任务，可惜有一个小小的缺点：这个犁田机器人一次只能犁一个边的长度是整数的长方形的田地。

因为FJ的田地有树和其它障碍物，所以FJ设定机器人去犁很多不同的长方形。这些长方形允许重叠。他给机器人下了P个指令，每个指令包含一个要犁长方形的地。这片田地由长方形的左下角和右上角坐标决定。他很好奇最后到底有多少个方格的地被犁过了。

一般来说，田地被分割为很多小方格。这些方格的边和x轴或y轴平行。田地的宽度为X个方格，高度为Y个方格 (1 <= X <= 240; 1 <= Y <= 240). FJ执行了I (1 <= I <= 200)个指令，每个指令包含4个整数：Xll, Yll, Xur, Yur (1 <= Xll <= Xur; Xll <= Xur <=X; 1 <= Yll <= Yur; Yll <= Yur <= Y), 分别是要犁的长方形的左下角坐标和右上角坐标。机器人会犁所有的横坐标在Xll..Xur并且纵坐标在Yll..Yur范围内的所有方格的地。可能这个长方形会比你想象的多一行一列（就是说从第Xll列到第Xur列一共有Xur - Xll + 1列而不是Xur - Xll列）。

考虑一个6方格宽4方格高的田地。FJ进行了2个操作（如下），田地就被犁成"\*"和"#"了。虽然一般被犁过的地看起来都是一样的。但是标成"#"可以更清晰地看出最近一次被犁的长方形。

一共14个方格的地被犁过了。

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

\* Lines 2..I+1: Line i+1 contains plowing instruction i which is described by four integers: Xll, Yll, Xur, and Yur

outputFormat: \* Line 1: A single integer that is the total number of squares plowed

hint: As in the task's example.


title: [USACO09OCT] Barn Echoes G

description:
The cows enjoy mooing at the barn because their moos echo back, although sometimes not completely. Bessie, ever the excellent

secretary, has been recording the exact wording of the moo as it goes out and returns. She is curious as to just how much overlap there is.

Given two lines of input (letters from the set a..z, total length in the range 1..80), each of which has the wording of a moo on it, determine the greatest number of characters of overlap between one string and the other. A string is an overlap between two other strings if it is a prefix of one string and a suffix of the other string.

By way of example, consider two moos:

```
moyooyoxyzooo
yzoooqyasdfljkamo
```
The last part of the first string overlaps 'yzooo' with the first part of the second string. The last part of the second string

overlaps 'mo' with the first part of the first string. The largest overlap is 'yzooo' whose length is 5.

POINTS: 50

奶牛们非常享受在牛栏中哞叫，因为她们可以听到她们哞声的回音。虽然有时候并不能完全听到完整的回音。Bessie 曾经是一个出色的秘书，所以她精确地纪录了所有的哞叫声及其回声。她很好奇到底两个声音的重复部份有多长。

输入两个字符串（长度为 $1$ 到 $80$ 个字母），表示两个哞叫声。你要确定最长的重复部份的长度。两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串。

我们通过一个例子来理解题目。考虑下面的两个哞声：

```
moyooyoxyzooo
yzoooqyasdfljkamo
```

第一个串的最后的部份 `yzooo` 跟第二个串的第一部份重复。第二个串的最后的部份 `mo` 跟第一个串的第一部份重复。所以 `yzooo` 跟 `mo` 都是这 $2$ 个串的重复部份。其中，`yzooo` 比较长，所以最长的重复部份的长度就是 $5$。

inputFormat: \* Lines 1..2: Each line has the text of a moo or its echo

outputFormat: \* Line 1: A single line with a single integer that is the length of the longest overlap between the front of one string and end of the other.

hint: 'abcxxxxabcx' is a prefix of the first string and a suffix of the second string.


title: [USACO09OCT] Papaya Jungle G

description:
Bessie has wandered off the farm into the adjoining farmer's land. He raises delicious papaya fruit, which is a delicacy for cows. The papaya jungle is partitioned into a grid of squares with R rows and C columns (1 <= R <= 40, 1 <= C <= 40), as is popular in Wisconsin. Bessie can travel from a given square to any existing adjacent square whose route is parallel to the X or Y axis.  So in the

following diagram, if Bessie is at the square labeled 'B', she can travel to any of the squares labeled 'T':

.T.
TBT
.T.
Bessie always starts out by munching the papayas in square

(row=1,col=1).  After she's done with one square, Bessie always uses her trusty binoculars to count the low-hanging fruit in each of the adjacent squares. She then always moves to the square with the most visible uneaten fruit (a square that happily is always unique).

Sooner or later, following this rule, Bessie always ends up in square (R,C) and eats the fruit there.

Given the dimensions of the papaya jungle and the amount of fruit F\_ij in each square (1 <= F\_ij <= 100), determine the total number of fruit Bessie consumes for a given papaya jungle.

POINTS: 80

Bessie不小心游荡出Farmer John的田地，而走进了相邻的农民的地里。她举起一个木瓜，木瓜对奶牛来说可是不可多得得美味。这个木瓜林像一般的威斯康星州的田地一样被分割成一个R行C列的网格(1 <= R <= 40, 1 <= C <= 40)。Bessie可以从一个格沿着一条跟X轴或Y轴平行的直线走到邻接的另一个格。Bessie发现一开始她自己在木瓜林的(1,1)，也就是第一行第一列慢悠悠地咀嚼着木瓜。

Bessie总是用她最信赖地双筒望远镜去数每一个邻接的格里挂着的木瓜的数目。然后她就游荡到那个有最多没有被吃掉的木瓜的邻接的格子（保证这样的格子只有一个）。

按照这种移动方法，最终Bessie总是会在(R,C)停止然后吃掉那里的木瓜。

给定这个木瓜林的大小及每个格的木瓜数F\_ij(1 <= F\_ij <= 100), 要求Bessie一共吃了多少个木瓜。

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

\* Lines 2..R+1: Line i+1 describes row i of the jungle with C

space-separated integers that tell how many fruit are in each square: F\_i1, F\_i2, ..., F\_iC

outputFormat: \* Line 1: A single integer that is the total number of papayas that Bessie eats by the time she finishes off the papayas at the barn in the lower right corner at coordinate (R,C).

hint:
Three rows; four columns. Bessie starts in upper left corner at the '3'.

Bessie eats the papayas in the order given by the letters next to the numbers below:

(1,1) ---> (1,C)

(1,1) 3a  3   4g  5h  (1,C)

|   4b  5c  3f  2i    |

(R,1) 1   7d  4e  2j  (R,C)

(R,1) ---> (R,C)

She declines to eat 4 of the papayas but consumes 39 (visiting all but two squares of the grid).


title: [USACO09OCT] The Leisurely Stroll G

description:
Bessie looks out the barn door at the beautiful spring day and thinks to herself, 'I'd really like to enjoy my walk out to the pastures for the tender spring grass.' She knows that once she leaves the barn, she will traverse a path for a while, take one of two choices that lead to other paths, follow one of them, take one of two other choices, and continue on until the path leads to a verdant pasture.

She decides to make the set of path choices that enables her to walk over the greatest number of cow paths on her way to breakfast. Given the description of these paths, determine how many cow paths she traverses, presuming that she commences choosing various paths as soon as she leaves the barn.

The farm has P (1 <= P <= 1,000) pastures that are lead to by P-1 choice-nodes (range 1..P-1) connected by paths. From the barn (which is node 1), only one set of path traversals exists to reach any choice-node or pasture.

Consider this set of paths (lines), pastures ('%'), and the highlighted ('#') route to a pasture on the right:

```cpp

                 %                             %
                /                             /
      2----%   7----8----%          2----%   7####8----%
     / \      /      \             # #      #      #
    1   5----6        9----%      1   5####6        9----%
     \   \    \        \           \   \    \        #
      \   %    %        %           \   %    %        %
       \                             \
        3-----%                       3-----%
         \                             \
          4----%                        4----%
           \                             \
            %                             %
```
The pasture reached from choice-node 9 is one of two that enable Bessie to traverse seven different cowpaths on the way to breakfast. These are the 'furthest' pastures from node 1, the barn.

Three integers describe each node: Cn, D1, and D2. Cn is the

nodenumber (1 <= Cn <= P-1); D1 and D2 are the destinations from that node (0 <= D1 <= P-1; 0 <= D2 <= P-1). If D1 is 0, the node leads to a pasture in that direction; D2 has the same property.

POINTS: 100

Bessie透过牛棚的大门向外望去。发现今天是一个美丽的春季早晨。她想，“我真的好想好想沐浴着春风，走在草地之中，感受嫩草温柔地抚摸四蹄地的感觉。”她知道一旦她离开了牛棚，她将沿着一条小径走一段路，然后就会出现一个三岔路口，她必须在两条小径中选择一条继续走下去。然后她又会遇到更多的三岔路口，进行更多的选择，知道她到达一个青翠的牧场为止。

她决定作一个选择使得她在去吃早草的路途中可以走过最多的小径。给你这些小径的描述，求出Bessie最多可以走过多少条小径。假定Bessie一出牛棚就有2条路径，Bessie需要从中选择一条。

农场中有P-1 (1 <= P <= 1,000) 个分岔节点（范围是1..P），引向P片草地，它们之间由小径连接。对任意一个节点来说，只有一条从牛棚（被标记为节点1）开始的路径可以到达。

考虑下面的图。线段表示小径，"%"表示草地。右边的图中的"#"表示一条到达草地的高亮的路径。

从分岔节点9到达的草地是两个可以让Bessie走过最多小径的草地之一。在去吃早草的路上Bessie将走过7条不同的小径。这些草地是离牛棚也就是节点1最“远”的。

由3个整数来表示每一个节点：Cn, D1和D2，Cn是节点的编号(1 <= Cn <= P-1); D1和D2是由该节点引出的两条小径的终点(0 <= D1 <= P-1; 0 <= D2 <= P-1)。如果D1为0，表示这条小径引向的是一片牧草地；D2也一样。

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

\* Lines 2..P: Line i+1 contains three space-separated integeres that describe a choice-node: Cn, D1, and D2

outputFormat: \* Line 1: A single integer that is the largest number of paths Bessie can traverse on the way to the furthest pasture.

hint:
This input describes the example farm layout in the task description.

1-2-5-6-7-8-9-P is one of the longest routes.


title: [USACO09OCT] Invasion of the Milkweed G

description:
Farmer John has always done his best to keep the pastures full of luscious, delicious healthy grass for the cows. He has lost the battle, though, as the evil milkweed has attained a foothold in the northwest part of his farm.

The pasture, as usual, is partitioned into a rectilinear grid of height Y (1 <= Y <= 100) and width X (1 <= X <= 100) with (1,1) being in the lower left corner (i.e., arranged as a normal X,Y coordinate grid). The milkweed has initially begun growing at square (Mx,My). Each week the milkweed propagates to all non-rocky squares that surround any square it already occupies, as many as eight more squares (both the rectilinear squares and the diagonals). After only one week in those squares, it is ready to move on to more squares.

Bessie wants to enjoy all the grass she can before the pastures are taken over by milkweed. She wonders how long it can last. If the milkweed is in square (Mx,My) at time zero, at what time does it complete its invasion of the pasture (which, for the given input data, will always happen)?

The pasture is described by a picture with '.'s for grass and '\*'s for boulders, like this example with X=4 and Y=3:

```
....
..*.
.**.
```

If the milkweed started in the lower left corner (row=1, column=1), then the map would progress like this:

```
    ....  ....  MMM.  MMMM  MMMM
    ..*.  MM*.  MM*.  MM*M  MM*M
    M**.  M**.  M**.  M**.  M**M
week  0    1    2    3    4
```

The milkweed has taken over the entire field after 4 weeks.

inputFormat:
\* Line 1: Four space-separated integers: X, Y, Mx, and My

\* Lines 2..Y+1: Line y+1 describes row (Y+2-y) of the field with X characters ('.' for grass and '\*' for a boulder)

outputFormat: \* Line 1: A single integer that is the week number when the milkweed takes over the last remaining non-boulder square of the pasture.

translation:
Farmer John 一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿，他在植物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

草地像往常一样，被分割成一个高度为 $Y\,(1 \le Y \le 100)$, 宽度为 $X\,(1 \le X \le 100)$ 的直角网格。$(1,1)$ 是左下角的格（也就是说坐标排布跟一般的 $X$，$Y$ 坐标相同）。乳草一开始占领了格 $(M_x,M_y)$。每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格（包括垂直与水平相邻的和对角在线相邻的格）。1 周之后，这些新占领的格又可以把乳草传播到更多的格里面了。

Bessie 想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能占领整个草地。如果乳草在 0 时刻处于格 $(M_x,M_y)$，那么会在哪个时刻它们可以完全占领入侵整片草地呢？对给定的数据总是会发生。


title: [USACO09NOV] Who Brings the Cookies? G

description:
Farmer John's N (1 <= N <= 1,000) cows conveniently numbered 1..N decided to form M (1 <= M <= 100) study groups. A total of S\_i (1 <= S\_i <= 19) cows study in group G\_i (namely cows G\_i1, G\_i2, ...). A cow might study in more than one study group.

For each study group, one cow in the group must be chosen to bring cookies to the meeting. Cookies are costly and require time to acquire, so the cows want to divide the work of bringing cookies as fairly as possible.

They decided that if a cow attends meetings with size c\_1, c\_2, ..., c\_K, she is only willing to bring cookies to at most ceil(1/c\_1 + 1/c\_2 + ... + 1/c\_K) meetings.

Figure out which cow brings cookies to each meeting. If this isn't possible, just output '-1'. Choose any solution if more than one is possible.

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

\* Lines 2..M+1: Line i+1 contains many space-separated integers: S\_i, G\_i1, G\_i2, ...

outputFormat: \* Lines 1..M: If a mapping is possible, line i contains the number of the cow who brings cookies to study group i. Otherwise, line 1 contains just the integer -1.

translation:
农夫约翰的 $N(1 \le N \le 1000)$ 只奶牛（编号为 $1$ 到 $N$）决定成立 $M(1 \le M \le 100)$ 个学习小组。在学习小组 $G_i$ 中有 $S_i$ 只牛，分别为牛$G_{i1},G_{i2},\cdots$，一头牛可能会参加多个小组。

对于每个学习小组，有一只牛必须在每次聚会的时候带饼乾饮料请大家吃（衰～）。因为买这些零食会消耗牛们那为数不多的零花钱，还会花费牛们宝贵的时间，所以牛们希望尽可能公平地分摊带零食的责任。 牛们决定。如果一只牛参加了 $K$ 个学习小组，$K$ 个学习小组的大小分别为 $c_1,c_2, \cdots c_K$，那麽她最多负责为 $\lceil \frac{1}{c_1} + \frac {1}{c_2} + \cdots + \frac{1}{c_K} \rceil$ 个学习小组的聚会带零食。其中 $\lceil \rceil$为上取整函数。 请计算出一个方案，决定每个学习小组的聚会由哪一头牛负责带零食。如果没有一种方案可行，输出 `-1`。

hint: Cow1 can bring cookies to at most 2 meetings, cow2 can bring 2, cow3 can bring 2, cow4 can bring 1, and cow5 can bring 1.


title: [USACO09NOV] Lights G

background: [English Edition](/paste/410oq6t5)

description:
给出一张 $n$ 个点 $m$ 条边的无向图，每个点的初始状态都为 $0$。

你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 $0$ 变成 $1$ 或由 $1$ 变成 $0$。

你需要求出最少的操作次数，使得在所有操作完成之后所有 $n$ 个点的状态都是 $1$。

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

之后 $m$ 行，每行两个整数 $a, b$，表示在点 $a, b$ 之间有一条边。

outputFormat:
一行一个整数，表示最少需要的操作次数。

本题保证有解。

hint: 对于 $100\%$ 的数据，$1\le n\le35,1\le m\le595, 1\le a,b\le n$。保证没有重边和自环。


title: [USACO09NOV] Cow Rescue G

description:
Bessie is trapped in a triangular maze with N rows (1 <= N <= 1,000,000). A three row maze is shown below:

The i'th row of the maze contains 2\*i-1 triangles. Numbering from the left, the triangles are named (i,1), (i,2), and so on.

Bessie can travel to the (often three) triangles which share an edge with her current triangle. For example, if she is at (3, 3), she can travel to (3, 2), (3, 4) and (4, 4). Bessie takes one minute to travel from one triangle to the next.

FJ has learned the Bessie is trapped and knows by tracking her iPhone that she starts her exit trek at triangle (Si,Sj). FJ's love for Bessie knows no bounds so he wants her back in the minimum possible time.

The maze has M (1 <= M <= 10,000) exits found in locations throughout the set of triangles. Any one of these will enable Bessie to escape. Once she enters an exit triangle, she leaves the maze in just one more minute.

Find the minimum time in minutes, T, required for Bessie to exit the maze and report the optimal exit location she uses, (OUTi, OUTj). If more than one location requires only T minutes, output the location with the smallest row. If two optimal rows are the same, output the one with smaller column.

贝希被困在一个三角形的迷宫之中。这个迷宫有 $N$ 行（$1 \le N \le 1000000$）。比如下图是一个 $3$ 行的迷宫。  迷宫的第 $i$ 行有 $2i-1$ 个三角形，从左到右分别编号为 $(i, 1)$、$(i, 2)$ 等等。

贝希每次可以从一个三角形走到任意一个一个跟当前的三角形有邻边的三角形。

比如说，如果她目前处于三角形 $(3, 3)$，那么，她可以走到三角形 $(3, 2)$、$(3, 4)$ 和 $(4, 4)$。贝希每次需要一分钟的时间来移动到下一个三角形。

农夫约翰发现贝希被困了！于是她跟踪贝希的iPhone手机（可怜的触摸屏～），得知贝希目前处于三角形 $(S_i, S_j)$。

因为约翰对贝希有著无穷无尽的浓浓爱意，所以他希望贝希能尽可能快地回到他的身边。 在迷宫的三角形之中，有 $M$（$1 \le M \le 10000$）个是出口。在任何一个出口都可以让贝希逃离迷宫。一旦贝希进入一个作为出口的三角形，她用多一分钟就可以逃离这个迷宫。 找到一个可以让贝希逃离迷宫最小时间 $T$，并输出她应该从哪一个出口逃离迷宫，这个出口记为 $(\text{OUT}_i, \text{OUT}_j)$。

如果有多个出口同时需要时间 $T$，输出那个行的编号小的出口，如果仍然有多个出口，输出那个列的编号小的。

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

\* Line 2: Two space-separated integers: Si and Sj

\* Lines 3..M+2: Line i+2 contains two space-separated integers that are the triangle location of exit i: Ei and Ej

outputFormat:
\* Line 1: Two space-separated integers: OUTi and OUTj

\* Line 2: A single integer: T


title: [USACO09NOV] A Coin Game S

background: [原英文题面见链接](https://www.luogu.com.cn/paste/9orda6gz)。

description:
小 A 和小 B 在玩游戏。

初始时，有 $n$ 个硬币被摆成了一行，从左至右第 $i$ 个硬币的价值为 $c_i$。

游戏的规则是，两人交替从这堆硬币的**左侧**连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了 $k$ 个硬币，那么本次自己最多取出 $k \times 2$ 个硬币。当没有硬币可取时，游戏结束。

游戏开始时，由小 A 先动手取硬币，最多取出 $2$ 个硬币。

请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。

inputFormat:
输入的第一行是一个整数 $n$，代表硬币的个数。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。

outputFormat: 输出一行一个整数，代表小 A 能获得的最大累计价值。

hint:
#### 输出输出样例 $1$ 解释

初始时，硬币序列为 $\{1,~3,~1,~7,~2\}$。

由小 A 先操作，他取出了一个硬币，硬币序列变为 $\{3,~1,~7,~2\}$，小 A 的累计价值为 $1$。

再由小 B 操作，由于小 A 上回合取出了 $1$ 个硬币，所以他本回合可以取出至多 $1 \times 2 = 2$ 个硬币。他取出了一个硬币，硬币序列变为 $\{1,~7,~2\}$，小 B 的累计价值为 $3$。

再由小 A 操作，由于上回合小 B 取出了 $1$ 个硬币，所以他本回合可以取出至多 $1 \times 2 = 2$ 个硬币。他取出了两个硬币，硬币序列变为 $\{2\}$，小 A 的累计价值为 $1 + 1 + 7 = 9$。

再由小 B 操作，由于上回合小 A 取出了 $2$ 个硬币，所以他本回合可以取出至多 $2 \times 2 = 4$ 个硬币。但是只剩下了 $1$ 个硬币，因此他只能取出一个硬币，硬币序列变为空，小 B 的累计价值为 $3 + 2 = 5$，游戏结束。

#### 数据范围与约定

对于全部的测试点，保证 $5 \leq n \leq 2 \times 10^3$，$1 \leq c_i \leq 10^5$。

**提示：请注意本题的空间限制为 $20$ MiB**。


title: [USACO09NOV] The Grand Farm-off S

description:
Farmer John owns 3\*N (1 <= N <= 500,000) cows surprisingly numbered 0..3\*N-1, each of which has some associated integer weight W\_i (1 <= W\_i <= d). He is entering the Grand Farm-off, a farming competition where he shows off his cows to the greater agricultural community.

This competition allows him to enter a group of N cows. He has given each of his cows a utility rating U\_i (1 <= U\_i <= h), which

represents the usefulness he thinks that a particular cow will have in the competition, and he wants his selection of cows to have the maximal sum of utility.

There might be multiple sets of N cows that attain the maximum utility sum. FJ is afraid the competition may impose a total weight limit on the cows in the competition, so a secondary priority is to bring lighter weight competition cows.

Help FJ find a set of N cows with minimum possible total weight among the sets of N cows that maximize the utility, and print the remainder when this total weight is divided by M (10,000,000 <= M <= 1,000,000,000).

Note: to make the input phase faster, FJ has derived polynomials which will generate the weights and utility values for each cow. For each cow 0 <= i < 3\*N,

 $$W_i=(a\times i^5+b\times i^2+c)\mod d$$

 $$U_i=(e\times i^5+f\times i^3+g)\mod h$$

 $$(0\le a,b,c,d,e,f,g,h\le 10^9)$$

The formulae do sometimes generate duplicate numbers; your algorithm should handle this properly.

农夫约翰有3N(1 < N < 500000)头牛，编号依次为1..#N，每头牛都有一个整数值的体 重。约翰准备参加农场技艺大赛，向广大的农业社区展示他的奶牛.
大赛规则允许约翰带N头牛参赛.约翰给每头牛赋予了一个“有用度”Ui，它表 示了某头牛在比赛中的有用程度.约翰希望他选出的奶牛的有用度之和最大.

有可能选出很多组的N头牛都能达到有用度最大和.约翰害怕选出的N头牛的总重量会给大赛 带来震撼，所以，要考虑优先选择体重轻的奶牛.

帮助约翰选出N头总重量最轻，并且有用度之和最大的奶牛.输出体重模M后的余数.

注意：为了使输入更快，约翰使用了一个多项式来生成每头牛的体重和有用度.对每头牛/， 体重和有用度的计算公式为：

 $$W_i=(a\times i^5+b\times i^2+c)\mod d$$

 $$U_i=(e\times i^5+f\times i^3+g)\mod h$$

 $$(0\le a,b,c,d,e,f,g,h\le 10^9)$$

inputFormat: \* Line 1: Ten space-separated integers: N, a, b, c, d, e, f, g, h, and M

outputFormat: \* Line 1: A single integer representing the lowest sum of the weights of the N cows with the highest net utility.

hint:
The functions generate weights of 5, 6, 9, 14, 21, and 30 along with utilities of 0, 1, 8, 27, 64, and 125.

The two cows with the highest utility are cow 5 and 6, and their combined weight is 21+30=51.


title: [USACO09DEC] Cow Toll Paths G

description:
Like everyone else, FJ is always thinking up ways to increase his revenue. To this end, he has set up a series of tolls that the cows will pay when they traverse the cowpaths throughout the farm.

The cows move from any of the $N (1 \leq N \leq 250)$ pastures conveniently numbered $1...N$ to any other pasture over a set of $M (1 \leq M \leq 10,000) $bidirectional cowpaths that connect pairs of different pastures $A_j$ and $B_j (1 \leq A_j \leq N; 1 \leq B_j \leq N)$. FJ has assigned a toll $L_j (1 \leq L_j \leq 100,000)$ to the path connecting pastures $A_j$ and $B_j$.

While there may be multiple cowpaths connecting the same pair of pastures, a cowpath will never connect a pasture to itself. Best of all, a cow can always move from any one pasture to any other pasture by following some sequence of cowpaths.

In an act that can only be described as greedy, FJ has also assigned a toll $C_i (1 \leq C_i \leq 100,000)$ to every pasture. The cost of moving from one pasture to some different pasture is the sum of the tolls for each of the cowpaths that were traversed plus a **single additional toll** that is the maximum of all the pasture tolls encountered along the way, including the initial and destination pastures.

The patient cows wish to investigate their options. They want you to write a program that accepts $K (1 \leq K \leq 10,000)$ queries and outputs the minimum cost of trip specified by each query. Query $i$ is a pair of numbers $s_i$ and $t_i (1 \leq s_i \leq N; 1 \leq t_i \leq N; s_i \neq t_i)$ specifying a starting and ending pasture.

Consider this example diagram with five pastures:

The 'edge toll' for the path from pasture $1$ to pasture $2$ is $3$. Pasture $2$'s 'node toll' is $5$.

To travel from pasture $1$ to pasture $4$, traverse pastures $1$ to $3$ to $5$ to $4$. This incurs an edge toll of $2+1+1=4$ and a node toll of $4$ (since pasture $5$'s toll is greatest), for a total cost of $4+4=8$.

The best way to travel from pasture $2$ to pasture $3$ is to traverse pastures $2$ to $5$ to $3$. This incurs an edge toll of $3+1=4$ and a node toll of $5$, for a total cost of $4+5=9$.

给定一个 $n$ 点 $m$ 边的双向图，第 $i$ 条道路连接了 $u_i$ 与 $v_i$，边权为 $w_i$，第 $i$ 个点的点权为 $c_i$。

给定 $q$ 组询问，第 $i$ 组询问求从 $s_i$ 到 $t_i$ 的路径的边权之和与点权的最大值的和的最小值。

**可能有重边，但保证无自环。**

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

- Lines $2..N+1$: Line $i+1$ contains a single integer: $C_i$

- Lines $N+2..N+M+1$: Line $j+N+1$ contains three space separated integers: $A_j$, $B_j$, and $L_j$

- Lines $N+M+2..N+M+K+1$: Line $i+N+M+1$ specifies query $i$ using two space-separated integers: $s_i$ and $t_i$

第一行三个整数 $n,m,q$ 代表点数，边数与询问数。
接下来 $n$ 行每行一个整数 $c_i$ 代表第 $i$ 个点的点权。
接下来 $m$ 行每行三个整数 $u_i,v_i,w_i$ 代表第 $i$ 条边从 $u_i$ 连到 $v_i$ 边权为 $w_i$。
接下来 $q$ 行每行两个整数 $s_i,t_i$ 代表第 $i$ 组询问求从 $s_i$ 到 $t_i$ 的边权之和与点权的最大值的和的最小值。

outputFormat:
- Lines $1..K$: Line $i$ contains a single integer which is the lowest cost of any route from $s_i$ to $t_i$

$q$ 行每行一个整数，代表第 $i$ 组询问的结果。


title: [USACO09DEC] Video Game Troubles G

description:
Farmer John's cows love their video games! FJ noticed that after playing these games that his cows produced much more milk than usual, surely because contented cows make more milk.

The cows disagree, though, on which is the best game console. One cow wanted to buy the Xbox 360 to play Halo 3; another wanted to buy the Nintendo Wii to play Super Smash Brothers Brawl; a third wanted to play Metal Gear Solid 4 on the PlayStation 3. FJ wants to purchase the set of game consoles (no more than one each) and games (no more than one each -- and within the constraints of a given budget) that helps his cows produce the most milk and thus nourish the most children.

FJ researched N (1 <= N <= 50) consoles, each with a console price P\_i (1 <= P\_i <= 1000) and a number of console-specific games G\_i (1 <= G\_i <= 10). A cow must, of course, own a console before she can buy any game that is specific to that console. Each individual game has a game price GP\_j (1 <= GP\_j price <= 100) and a production value (1 <= PV\_j <= 1,000,000), which indicates how much milk a cow will produce after playing the game. Lastly, Farmer John has a budget V (1 <= V <= 100,000) which is the maximum amount of money he can spend. Help him maximize the sum of the production values of the games he buys.

Consider one dataset with N=3 consoles and a V=$800 budget. The first console costs $300 and has 2 games with cost $30 and $25 and production values as shown:

Game #    Cost    Production Value

1       $30          50

2       $25          80

The second console costs $600 and has only 1 game:

Game #    Cost    Production Value

1       $50          130

The third console costs $400 and has 3 games:

Game #    Cost    Production Value

1       $40         70

2       $30         40

3       $35         60

Farmer John should buy consoles 1 and 3, game 2 for console 1, and games 1 and 3 for console 3 to maximize his expected production at 210:

```cpp
                                Production Value
        Budget:     $800
        Console 1  -$300
           Game 2   -$25              80
        Console 3  -$400
           Game 1   -$40              70
           Game 3   -$35              60
      -------------------------------------------
        Total:         0 (>= 0)      210
```

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

\* Lines 2..N+1: Line i+1 describes the price of and the games

available for console i; it contains: P\_i, G\_i, and G\_i pairs of space-separated integers GP\_j, PV\_j

outputFormat: \* Line 1: The maximum production value that Farmer John can get with his budget.

translation:
农夫约翰的奶牛们打游戏上瘾了！本来约翰是想要按照调教兽的做法拿她们去电击戒瘾的，可后来他发现奶牛们玩游戏之后比原先产更多的奶。很明显，这是因为满足的牛会产更多的奶。

但是，奶牛们因何者为最好的游戏主机而吵得不可开交。约翰想要在给定的预算内购入一些游戏平台和一些游戏，使他的奶牛们生产最多的奶牛以养育最多的小牛。

约翰考察了 $N$ 种游戏主机，第 $i$ 种主机的价格是 $P_i$，该主机有 $G_i$ 个独占游戏。很明显，奶牛必须先买进一种游戏主机，才能买进在这种主机上运行的游戏。在每种主机中，游戏 $j$ 的价格为 $\mathit{GP}_j$，每头奶牛在玩了该游戏后的牛奶产量为 $\mathit{PV}_j$。

农夫约翰的预算为 $V$。请帮助他确定应该买什么游戏主机和游戏，使得他能够获得的产出值的和最大。

### 样例说明 1
假设 现在有 $N=3$ 种主机，预算为 $V=800$。第一种主机的售价为 $300$，并且有两款游戏：

|游戏编号|$GP_j$|$PV_j$|
|-|-|-|
|1|$30|50|
|2|$25|80|

第二种主机的售价为 $600$，并且只有一款游戏：

|游戏编号|$GP_j$|$PV_j$|
|-|-|-|
|1|$50|130|

第二种主机的售价为 $400$，并且有三款游戏：

|游戏编号|$GP_j$|$PV_j$|
|-|-|-|
|1|$40|70|
|2|$30|40|
|3|$35|60|

理想方案：
```cpp
                              产量
           预算:    $800
           主机 1  -$300
           游戏 2   -$25       80
           主机 3  -$400
           游戏 1   -$40       70
           游戏 3   -$35       60
      -------------------------------------------
          总和：   0 (≥ 0)     210
```


title: [USACO09DEC] Bobsledding S

description:
Bessie has entered a bobsled competition because she hopes her hefty weight will give her an advantage over the L meter course (2 <= L <= 1,000,000,000).

Bessie will push off the starting line at 1 meter per second, but her speed can change while she rides along the course. Near the middle of every meter Bessie travels, she can change her speed either by using gravity to accelerate by one meter per second or by braking to stay at the same speed or decrease her speed by one meter per second.

Naturally, Bessie must negotiate N (1 <= N <= 100,000) turns on the way down the hill. Turn i is located T\_i meters from the course start (1 <= T\_i <= L-1), and she must be enter the corner meter at a speed of at most S\_i meters per second (1 <= S\_i <= 1,000,000,000). Bessie can cross the finish line at any speed she likes.

Help Bessie learn the fastest speed she can attain without exceeding the speed limits on the turns.

Consider this course with the meter markers as integers and the turn speed limits in brackets (e.g., '[3]'):

```cpp

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
Start                         + 8
                               \
                                + 9
                                 \
                                  + 10       +++ 14 (finish)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]
```
Below is a chart of Bessie's speeds at the beginning of each meter length of the course:

````
Max:                              3               1       8
Mtrs: 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14 Spd:  1   2   3   4   5   5   4   3   4   3   2   1   2   3   4
```
Her maximum speed was 5 near the beginning of meter 4.

贝茜从山顶滑雪到山脚，山顶到山脚距离是L(2<L<10^9)米.贝茜在起点的速度是1米每 秒，但是他的速度是可以改变的，在每一米的速度可以是前一米的速度加1、减1，或者等于前一米 的速度.在滑行的过程中，贝茜会遇到N<=100000)个转弯处，第i个转弯处位于距离出发 Ti米处，为了安全，贝茜到达第i个转弯处的速度不能超过Si(1<Si<10^9)米 每秒.当然贝茜到达终点时的速度没有最大限制.请你计算贝茜在滑雪过程中最大的速度可以是多 少？

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

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

outputFormat: \* Line 1: A single integer, representing the maximum speed which Bessie can attain between the start and the finish line, inclusive.


title: [USACO09DEC] Music Notes S

description:
FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for B\_i (1 <= B\_i <= 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B\_1, note 2 from time B\_1 through just before time B\_1 + B\_2, etc.

However, recently the cows have lost interest in the song, as they feel that it is too long and boring. Thus, to make sure his cows are paying attention, he asks them Q (1 <= Q <= 50,000) questions of the form, 'In the interval from time T through just before time T+1, which note should you be playing?' The cows need your help to answer these questions which are supplied as T\_i (0 <= T\_i <=

end\_of\_song).

Consider this song with three notes of durations 2, 1, and 3 beats:

```cpp
Beat:   0    1    2    3    4    5    6    ...
        |----|----|----|----|----|----|--- ...
        1111111111     :              :
                  22222:              :
                       333333333333333:
```
Here is a set of five queries along with the resulting answer:

Query    Note

2        2

3        3

4        3

0        1

1        1

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

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

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

outputFormat: \* Lines 1..Q: For each query, print a single integer that is the index of the note that the cows should be playing.

translation:
约翰准备教他的奶牛们弹一首歌。这首歌由 $N$ 个音阶组成，第 $i$ 个音阶要敲击 $B_i$ 次。奶牛从第 $0$ 时刻开始弹，因此他从 $0$ 时刻到 $B_i-1$ 时刻都是敲第 $1$ 个音阶，然后他从 $B_1$ 时刻到 $B_1+B_2-1$ 时刻敲第 $2$ 个音阶，从 $B_1+B_2$ 到 $B_1+B_2+B_3-1$ 时刻敲第 $3$ 个音阶……现在有 $Q$ 个问题：在时间段区间 $T$，$T+1$ 内，奶牛敲的是哪个音阶?

$1\le N\le 50000$，$1\le Q\le 50000$，$1\le B_i\le 10000$。


title: [USACO09DEC] Selfish Grazing S

description:
Each of Farmer John's N (1 <= N <= 50,000) cows likes to graze in a certain part of the pasture, which can be thought of as a large one-dimeensional number line. Cow i's favorite grazing range starts at location S\_i and ends at location E\_i (1 <= S\_i < E\_i; S\_i < E\_i <= 100,000,000).

Most folks know the cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows i and j can only graze at the same time if either S\_i >= E\_j or E\_i <= S\_j. FJ would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences.

Consider a set of 5 cows with ranges shown below:

```cpp
  ... 1    2    3    4    5    6    7    8    9   10   11   12   13 ...
  ... |----|----|----|----|----|----|----|----|----|----|----|----|----
Cow 1:      <===:===>          :              :              :
Cow 2: <========:==============:==============:=============>:
Cow 3:          :     <====>   :              :              :
Cow 4:          :              :     <========:===>          :
Cow 5:          :              :     <==>     :              :
```
These ranges represent (2, 4), (1, 12), (4, 5), (7, 10), and (7, 8), respectively.

For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.

约翰有N(1≤N≤50000)头牛，约翰的草地可以认为是一条直线．每只牛只喜欢在某个特定的范围内吃草．第i头牛喜欢在区间(Si，Ei)吃草，1≤Si<Ei≤1,000,000,00.

奶牛们都很自私，他们不喜欢和其他奶牛共享自己喜欢吃草的领域，因此约翰要保证任意

两头牛都不会共享他们喜欢吃草昀领域．如果奶牛i和奶牛J想要同时吃草，那么要满足：Si>=Ej或者Ei≤Sj．约翰想知道在同一时刻，最多可以有多少头奶牛同时吃草？

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

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

outputFormat: \* Line 1: A single integer representing the maximum number of cows that can graze at once.


title: [USACO10HOL] Cow Politics G

description:
Farmer John's cows are living on N (2 <= N <= 200,000) different pastures conveniently numbered 1..N. Exactly N-1 bidirectional cow paths (of unit length) connect these pastures in various ways, and each pasture is reachable from any other cow pasture by traversing one or more of these paths (thus, the pastures and paths form a graph called a tree).

The input for a particular set of pastures will specify the parent node P\_i (0 <= P\_i <= N) for each pasture. The root node will specify parent P\_i == 0, which means it has no parent.

The cows have organized K (1 <= K <= N/2) different political parties conveniently numbered 1..K. Each cow identifies with a single

political party; cow i identifies with political party A\_i (1 <= A\_i <= K). Each political party includes at least two cows.

The political parties are feuding and would like to know how much 'range' each party covers. The range of a party is the largest distance between any two cows within that party (over cow paths).

For example, suppose political party 1 consists of cows 1, 3, and 6, political party 2 consists of cows 2, 4, and 5, and the pastures are connected as follows (party 1 members are marked as -n-):

-3-
|
-1-
/ | \
2  4  5

|
-6-
The greatest distance between any two pastures of political party 1 is 3 (between cows 3 and 6), and the greatest distance for political party 2 is 2 (between cows 2 and 4, between cows 4 and 5, and between cows 5 and 2).

Help the cows determine party ranges.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 64MB

农夫约翰的奶牛住在N (2 <= N <= 200,000)片不同的草地上，标号为1到N。恰好有N-1条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点P\_i (0 <= P\_i <= N)。根节点的P\_i == 0, 表示它没有父节点。因为奶牛建立了1到K一共K (1 <= K <= N/2)个政党。每只奶牛都要加入某一个政党，其中， 第i只奶牛属于第A\_i (1 <= A\_i <= K)个政党。而且每个政党至少有两只奶牛。 这些政党互相吵闹争。每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

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

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

outputFormat: \* Lines 1..K: Line i contains a single integer that is the range of party i.

translation:
农夫约翰的奶牛住在 $n$ 片不同的草地上，标号为 $1$ 到 $n$。

恰好有 $n-1$ 条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点 $p_i$（$0 \le p_i \le n$）。根节点的 $p_i = 0$，表示它没有父节点。

因为奶牛建立了 $1$ 到 $k$ 一共 $k$ 个政党。每只奶牛都要加入某一个政党，其中，第 $i$ 只奶牛属于第 $a_i$（$1 \le a_i \le k$）个政党。而且每个政党至少有两只奶牛。每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

数据范围：$2 \le n \le 200000$，$1 \le k \le \dfrac n2$


title: [USACO10HOL] Rocks and Trees G

background:
```
My country's bigger than most
And if asked I boast
'Cause I'm really proud
So I shout it loud
Though our numbers are few
We will welcome you
Although we don't have history
Gold medal winning teams
Heroes or prisoners
World famous volcanoes
Still what we've got's glorious
'Cause we've got
Rocks and trees
And trees and rocks
And rocks and trees
And trees and rocks
And rocks and trees
And trees and rocks
And rocks and trees
And trees and rocks
And water
-The Arrogant Worms, on Canada
（本段为诗歌，具体内容与题目无关）

description:
After moving across the 49th parallel to Canada, the land of rocks and trees, Farmer John's cows invented a game to spend their leisure time on the pasture; naturally, it involved the rocks and trees! Cowboy Ted likes this game very much, but so poor is his luck that he always loses to other cows. This time, he is going to seek your help.

The game's rules are simple. It is played with a tree that has both $N$$(2 \leqslant N \leqslant10000)$nodes conveniently numbered $1 \cdots N$ and also $N-1$ branches. Node 1 is the root of this tree; except for node 1, node $i$ has parent $P_i$ $(1 \leqslant P_i < i)$. Initially, Each node contains some rocks (except the root node, which has no rocks). In particular, non-root node $i$ has exactly $R_i (1 \leqslant R_i \leqslant 1000)$ rocks at the beginning of the game.

Two players alternate turns to play this game in turn, with Ted going first. In each turn, the current player can choose a non-root node $i$ and move at most $L (1 \leqslant L \leqslant 1000)$ rocks from this node one branch closer to the root (i.e., move these rocks to the parent node). He must move at least one rock, and, of course, he cannot exceed the current number of rocks on this node. The game ends when a player can't make a legal move (i.e., when all the rocks are on node 1); that player loses.

Ted needs your help. He has given you the initial configuration of the game, and he will then make $T (1 \leqslant T \leqslant 10000)$changes to the configuration one by one. Please help him determine, after each step, if he can win the game beginning from this configuration, assuming both he and his opponent use the best possible strategy.

Ted's changes are specified as two integers $A_j (1 < A_j \leqslant N)$ and $B_j (1 \leqslant B_j \leqslant 1000)$, meaning that Ted will change the number of rocks on node $A_j$ to $B_j$ (this is a `set` not a `subtract` or `add`), and will then ask you whether he can win. Changes accumulate; node $A_j$'s rocks stay at $B_j$ until another change for $A_j$ appears.

Consider this example with three nodes numbered as shown and the shape shown in Board 0. Initially, there are 5 rocks on node 2 and 3 rocks on node 3; see Board 1.

For the first change, Ted removes 2 rocks from node 2 (thus leaving 3); see Board 2. For the second change, Ted removes 2 rocks from node 3 (thus leaving 1). Note that node 2 still has 3 rocks; see Board 3.

Board 0 Board 1 Board 2 Board 3

（原题面并未给出链接）

Your program should determine in each case who wins.

For about 30% of the test cases, $N \leqslant 10$, and $T \leqslant 100$, and no tree node will have more than 5 rocks on it after any of Ted's changes.

Partial feedback will be provided for your first $50$ submissions.

inputFormat:
Line $1$: Three space-separated integers: $N$, $T$, and $L$.
Lines $2 \cdots N$: Line i contains two space-separted integers: $P_i$ and $R_i$.
Lines $N+1 \cdots N+T$: Line $j+N$ describes Ted's next change using two space-separated integers: $A_j$ and $B_j$.

outputFormat: Lines $1 \cdots T$: Line $i$ contains `Yes` if Ted can win the game after change $i$; and `No` otherwise.

hint: 数据来源：bzoj。


title: [USACO10HOL] Driving Out the Piggies G

description:
The Cows have constructed a randomized stink bomb for the purpose of driving away the Piggies. The Piggy civilization consists of N (2 <= N <= 300) Piggy cities conveniently numbered 1..N connected by M (1 <= M <= 44,850) bidirectional roads specified by their distinct endpoints A\_j and B\_j (1 <= A\_j <= N; 1 <= B\_j <= N). Piggy city 1 is always connected to at least one other city.

The stink bomb is deployed in Piggy city 1. Each hour (including the first one), it has a P/Q (1 <= P <= 1,000,000; 1 <= Q <=

1,000,000; P <= Q) chance of polluting the city it occupies. If it does not go off, it chooses a random road out of the city and follows it until it reaches a new city.  All roads out of a city are equally likely to be chosen.

Because of the random nature of the stink bomb, the Cows are wondering which cities are most likely to be polluted. Given a map of the Piggy civilization and the probability that the stink bomb detonates in a given hour, compute for each city the probability that it will be polluted.

For example, suppose that the Piggie civilization consists of two cities connected together and that the stink bomb, which starts in city 1, has a probability of 1/2 of detonating each time it enters a city:

1--2
We have the following possible paths for the stink bomb (where the last entry is the ending city):

1: 1
2: 1-2
3: 1-2-1

4: 1-2-1-2

5: 1-2-1-2-1

etc.
To find the probability that the stink bomb ends at city 1, we can add up the probabilities of taking the 1st, 3rd, 5th, ... paths above (specifically, every odd-numbered path in the above list). The probability of taking path number k is exactly (1/2)^k - the bomb must not remain in its city for k - 1 turns (each time with a probability of 1 - 1/2 = 1/2) and then land in the last city

(probability 1/2).

So our probability of ending in city 1 is represented by the sum 1/2 + (1/2)^3 + (1/2)^5 + ... . When we sum these terms infinitely, we will end up with exactly 2/3 as our probability, approximately 0.666666667. This means the probability of landing in city 2 is 1/3, approximately 0.333333333.

Partial feedback will be provided for your first 50 submissions.

一个无向图，节点1有一个炸弹，在每个单位时间内，有p/q的概率在这个节点炸掉，有1-p/q的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。

inputFormat:
\* Line 1: Four space separated integers: N, M, P, and Q

\* Lines 2..M+1: Line i+1 describes a road with two space separated integers: A\_j and B\_j

outputFormat: \* Lines 1..N: On line i, print the probability that city i will be destroyed as a floating point number. An answer with an absolute error of at most 10^-6 will be accepted (note that you should output at least 6 decimal places for this to take effect).

hint: 感谢 @[Alpha](https://www.luogu.com.cn/user/87058) 贡献 Special Judge。


title: [USACO10HOL] Cow War G

description:
Farmer John has long had a dispute with neighbor Farmer Tom over a group of V (1 <= V <= 1,000) pastures conveniently numbered 1..V. Both farmers currently graze their cows on the pastures; each pasture might be empty or might have a single cow which is owned by either Farmer John or Farmer Tom.

Farmer John's patience is at an end, and he wishes to settle the dispute with Farmer Tom by tipping over Tom's cows. Of course, he wants to strike first and to tip as many of Farmer Tom's cows as possible.

A total of E (1 <= E <= 5,000) bidirectional cowpaths connect pairs of pastures. No two pastures are connected by more than one cowpath; each path connects exactly two distinct pastures. Paths are described by their endpoints P1\_i and P2\_i (1 <= P1\_i <= V; 1 <= P2\_i <= V).

During his offense, each of Farmer John's cows can traverse a single cowpath if she wishes. Whether or not she chooses to traverse a cowpath, she can then (if she wishes) launch a cow tipping attack to a pasture connected to her pasture by a single cowpath, thus tipping the enemy cow on that pasture. Note that a cow can move and then attack -- but she is not able to attack and then move.

Each pasture can hold exactly one cow at a time; no cow can move to a pasture occupied by another cow, especially if it has been tipped. Of course, if a pasture is vacated, another cow can later move in to take its place. A tipped cow cannot be tipped again.

Farmer John wants to know two things:

\* How many of Farmer Tom's cows he can tip in the first salvo

of the war

\* How to command his cows to move and attack so as to tip

that maximal number of Farmer Tom's cows in that first salvo

Find the maximum number of cows that can be tipped and construct a sequence of move and attack commands to his cows that then obey the rules and tip that number of cows. Any such sequence is acceptable, as long as it tips the maximum number of Farmer Tom's cows.

Consider, for instance, a group of 5 pastures arranged in a line, with each pasture connected (via '--'; see diagram below) to its left and right neighbors (if they exist). In other words, there is a cowpath from Pasture 1 to Pasture 2, Pasture 2 to Pasture 3, etc. Farmer Tom ('T') has 2 cows, standing on pastures 1 and 4, while Farmer John ('J') has 2 cows standing on pastures 3 and 5 ('E' means empty):

1    2    3    4    5

T -- E -- J -- T -- J

In this case, Farmer John can tip both of Farmer Tom's cows by first moving his cow on Pasture 3 to Pasture 2, so that the pastures in order are now TJETJ. Farmer John can then have both of his cows attack to the left.  Note that although the cow in Pasture 3 could have attacked to the right without moving, the rightmost cow would then be unable to attack. The only valid solutions thus have the same move and attacks, although the order in which Farmer John commands his cows can vary slightly.

If you compute the correct maximum number but do not provide a sequence (or your sequence is wrong), you will get 50% of the points for that test case. A program will grade your output.

Partial feedback will be provided for your first 50 submissions.

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

\* Line 2: A string of V characters (no spaces); character #i indicates whether pasture #i is empty ('E') or has a cow owned by Farmer John ('J') or Farmer Tom ('T')

\* Lines 3..E+2: Line i+2 contains two space separated integers: P1\_i and P2\_i

outputFormat:
\* Line 1: A single integer, the maximum number of enemy cows Farmer John can have tipped

\* Lines 2.....: One of Farmer John's instructions to his cows (to be executed in the order given):

MOVE A B

or
ATTACK A B

where A is the vertex the cow occupies before taking the action and B is the vertex it is moving to or attacking, respectively. Note that when instructing a cow that has already moved to attack, the instruction specifies the location the cow is currently standing, not where it was originally.

translation:
### 题目描述

给定 $V$ 个点，$E$ 条边的无向图。
一开始每个点上有 `T` 牛，`J` 牛，或者没有（`E`）。
`J` 牛可以 `MOVE` 到一个相邻的点，也可以 `ATTACK` 相邻点上的一个 `T` 牛。不过操作有限制，只能按照 `MOVE`,`ATTACK` 或者 `MOVE` 然后 `ATTACK` 三种方式操作。
一个 `T` 牛仅能被 `ATTACK` 一次，被 `ATTACK` 后它会留在原地。
需要保证任意时刻，每个点上有且仅有一头牛。
求所有 `T` 牛被 `ATTACK` 的最大次数，并给出一个可行的操作方案。

### 输入格式

第一行两个整数 $V,E$，表示无向图的点数和边数。
接下来一行 $V$ 个字符，第 $i$ 个字符表示第 $i$ 个点的初始状态。
接下来 $E$ 行每行两个整数 $u,v$，表示存在一条连接 $u,v$ 的无向边。

### 输出格式

第一行一个整数，表示所有 `T` 牛被 `ATTACK` 的最大次数。
接下来若干行，每行以 `MOVE u v` 或 `ATTACK u v` 的形式给出，表示你的操作方案。

### 说明/提示

对于测试点 $1\sim5$，$1\leq V\leq 30,1\leq E\leq 50$。
对于测试点 $6\sim 10$，$1\leq V\leq 500,1\leq E\leq 2\times 10^3$。
对于测试点 $11\sim 15$，$1\leq V\leq 10^3,1\leq E\leq 5\times 10^3$。
注意：一个操作需要描述现在的位置，例如：点 $3$ 上的牛先 `MOVE` 到点 $2$，再 `ATTACK` 点 $4$，应该写为：

\```
MOVE 3 2
ATTACK 2 4
\```

hint:
The other valid outputs are:

2
MOVE 3 2

ATTACK 5 4

ATTACK 2 1

and
2
ATTACK 5 4

MOVE 3 2

ATTACK 2 1

which are just reorderings of the output shown.  This might not be true on other testdata.


title: [USACO10JAN] Taking Turns G

description:
Farmer John has invented a new way of feeding his cows. He lays out N (1 <= N <= 700,000) hay bales conveniently numbered 1..N in a long line in the barn. Hay bale i has weight W\_i (1 <= W\_i <=

2,000,000,000). A sequence of six weights might look something like:

17 5 9 10 3 8

A pair of cows named Bessie and Dessie walks down this line after examining all the haybales to learn their weights. Bessie is the first chooser. They take turns picking haybales to eat as they walk (once a haybale is skipped, they cannot return to it). For instance, if cows Bessie and Dessie go down the line, a possible scenario is:

\* Bessie picks the weight 17 haybale

\* Dessie skips the weight 5 haybale and picks the weight 9 haybale \* Bessie picks the weight 10 haybale

\* Dessie skips the weight 3 haybale and picks the weight 8 haybale

Diagrammatically:

Bessie   |      |
17 5 9 10 3 8

Dessie       |      |
This scenario only shows a single skipped bale; either cow can skip as many as she pleases when it's her turn.

Each cow wishes to maximize the total weight of hay she herself consumes (and each knows that the other cow has this goal).

Furthermore, a cow will choose to eat the first bale of hay that maximimizes her total weight consumed.

Given a sequence of hay weights, determine the amount of hay that a pair of cows will eat as they go down the line of hay.

两头奶牛 Bessi 和 Dessie 走过一条路吃草，共 $n(1\le n \le 7\times 10 ^ 5)$ 个格子，第 $i$ 个格子有重量为 $W_i(1 \le W_i \le 2 \times 10 ^{9})$ 的草，两牛轮流走，一旦某头牛走过了一格，那么这格的草再也不可能被任一头奶牛吃，每格的草只能被吃一次，所以两头牛只能往后走。Bessi 先走，每头牛每次都往最终自己能吃到最多草的格子走（若有多个格子则选择第一个能吃到最多草的格子），他们都知道对方也想吃到最多的草，问最后 Bessi 和 Dessie 各吃到的草的重量。

输入格式：

第一行一个正整数 $n(1\leq n\le 7\times 10 ^ 5)$，接下来有 $n$ 行，第 $i+1$ 行为 $W_i(1 \le W_i \le 2 \times 10 ^{9})$。

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

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

outputFormat: \* Line 1: Two space-separated integers, the total weight of hay consumed by Bessie and Dessie respectively


title: [USACO10JAN] Shipping Around an Island G

description:
Farmer John decided to start his own cruise ship line! He has but one ship, but is hoping for big growth. He recently acquired a map of the area of ocean where his cruise ship will operate. It looks something like the diagram below, with height H (3 <= H <= 1000) and width W (3 <= W <= 1000).

```cpp
...................
...................
.....A.............
.....A..x..........
..x..A.....AAAA....
.....A.....A..A....
.....AAAAAAAA.A....
........A.....A....
.xx...AAA...x.A....
......A............
...AAAAAAAAAAAAA...
...................
```
In this map, '.' denotes water; 'A' is an element of the main island; and 'x' are other islands.

Farmer John has decided his cruise ship will loop around the main island. However, due to trade restrictions, the path his ship takes is NOT allowed to go around any OTHER islands. For instance, the following path of length 50 is not allowed because it encloses the island denoted by 'x'.

```cpp
...................
....+--+...........
....|A.|...........
....|A.|x.+-----+..
..x.|A.+--+AAAA.|..
....|A.....A..A.|..
....|AAAAAAAA.A.|..
....|...A.....A.|..
.xx.|.AAA...x.A.|..    <--- route circumnavigates 'x' -- illegal! ..+-+.A.........|..
..|AAAAAAAAAAAAA|..
..+-------------+..
```
Given a map, help Farmer John determine the shortest path his cruise ship can take to go around the main island without going around any other islands.

Two cells are considered connected if they lie vertically or

horizontally across from one another (not diagonally). It is

guaranteed that the main island is connected and that a solution exists.

Note that FJ's path may visit the same square more than once, for instance there are three squares that are visited more than once in FJ's optimal path (of length 62) for the example:

```cpp
...................
....+--+...........
....|A.|...........
....|A.|x.+----+...
..x.|A.+--+AAAA|...
....|A.....A..A|...
....|AAAAAAAA.A|...
....|...A..+-+A|...
.xx.|.AAA..|x|A|...
..+-+.A....+-+-++..
..|AAAAAAAAAAAAA|..
..+-------------+..
```
The above diagram is somewhat unclear because of the path overlapping itself.  Drawn in two stages, FJ's optimal path is:

```cpp
...................            ...................
...................            ....+--+...........
.....A.............            ....|A.|...........
.....A..x..........            ....|A.|x.+----+...
..x..A.....AAAA....            ..x.|A.+--+AAAA|...
.....A.....A..A....  and then  ....|A.....A..A|...
.....AAAAAAAA.A....            ....|AAAAAAAA.A|...
....V...A..+>.A....            ....V...A...>+A|...
.xx.|.AAA..|x.A....            .xx...AAA...x|A|...
..+-+.A....+----+..            .....A.......+-+...
..|AAAAAAAAAAAAA|..            ...AAAAAAAAAAAAA...
..+-------------+..            ...................
```

John 得到一份地图，长 $H$（$3 \leq H\leq 1000$）宽 $W$（$3 \leq W\leq 1000$），地图中 ``.`` 表示水，`A` 表示大陆，`x` 表示其他小岛。他决定驾驶他的船绕大陆一圈，但并不想环绕其他小岛。John 可以再任意有水的格子出发，求绕一周最小路径长度（一个格子可以经过任意多次）。

输入格式：

第一行两个空格隔开正整数 $H$ 和 $W$（$3 \leq H,W\leq 1000$），接下来有 $H$ 行，每行 $W$ 个字符表示地图。

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

\* Lines 2..H+1: Line i+1 contains contains W characters that are the elements of map row i (all '.' or 'x' or 'A')

outputFormat: \* Line 1: The minimum length of a path that Farmer John's cruise ship can take


title: [USACO10JAN] Cow Telephones G

description:
The cows have set up a telephone network, which for the purposes of this problem can be considered to be an unrooted tree of unspecified degree with N (1 <= N <= 100,000) vertices conveniently numbered 1..N. Each vertex represents a telephone switchboard, and each edge represents a telephone wire between two switchboards. Edge i is specified by two integers A\_i and B\_i the are the two vertices joined by edge i (1 <= A\_i <= N; 1 <= B\_i <= N; A\_i != B\_i).

Some switchboards have only one telephone wire connecting them to another switchboard; these are the leaves of the tree, each of which is a telephone booth located in a cow field.

For two cows to communicate, their conversation passes along the unique shortest path between the two vertices where the cows are located. A switchboard can accomodate only up to K (1 <= K <= 10) simultaneous conversations, and there can be at most one conversation going through a given wire at any one time.

Given that there is a cow at each leaf of the tree, what is the maximum number of pairs of cows that can simultaneously hold

conversations? A cow can, of course, participate in at most one conversation.

```cpp
1   5          C1   C5
|   |          ||   ||
2---4   -->    |2---4|
|   |          ||   ||
3   6          C3   C6
```
Consider this six-node telephone tree with K=1:

There are four cows, located at vertices 1, 3, 5 and 6. If cow 1 talks to cow 3, and cow 5 talks to cow 6, then they do not exceed the maximum number of conversations per switchboard, so for this example the answer is 2 (for two pairs of cows talking simultaneously).

奶牛们要建立一个电话网络，它们可以被认为是一个无根树（大概是个图吧。。。），里面N (1 <= N <= 100,000)个结点可以简便的编号为1...N。每一个结点代表一个电话交换机（类似开关），每条边代表一个连接两个电话交换机的电话线。边i是用两个整数A\_i和B\_i表示的，也就是该边连接着A\_i和B\_i两个电话交换机(1 <= A\_i <= N; 1 <= B\_i <= N; A\_i != B\_i).

一些电话交换机只有一根电话线；它们是这棵树的叶子结点，每个叶子结点只有一只牛。当两头牛在通话时，它们的对话沿着唯一的在两头牛所在结点的最短路径。

一个电话交换机只能忙于K(1 <= K <= 10)个同时的对话，而且每个电话线同一时间只能传送一个对话。

给出一个每个叶子结点都有一头牛的树， 问最多有多少对奶牛能在同一时间进行它们的对话？

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

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

outputFormat: \* Line 1: The number of pairs of cows that can simultaneously hold conversations


title: [USACO10JAN] Tea Time S

description:
N (1 <= N <= 1000) cows, conveniently numbered 1..N all attend a tea time every day. M (1 <= M <= 2,000) unique pairs of those cows have already met before the first tea time. Pair i of these cows who have met is specified by two differing integers A\_i and B\_i (1 <= A\_i <= N; 1 <= B\_i <= N). The input never indicates that cows have met each other more than once.

At tea time, any cow i and cow j who have met a mutual friend cow k will meet sometime during that tea time and thus expand their circle of known cows.

Determine whether Q (1 <= Q <= 100) pairs of cows have met after tea times are held for long enough that no new cow meetings are occurring. Query j consists of a pair of different cows X\_j and Y\_j (1 <= X\_j <= N; 1 <= Y\_j <= N).

For example, suppose that out of cows 1 through 5, we know that 2 has met 5, 2 has met 3, and 4 has met 5; see (a) below.

```cpp
   2---3           2---3            2---3
    \              |\  |            |\ /|
1    \     -->  1  | \ |    -->  1  | X |
      \            |  \|            |/ \|
   4---5           4---5            4---5
    (a)             (b)              (c)
```
In the first tea time, cow 2 meets cow 4, and cow 3 meets cow 5; see (b) above. In the second tea time, cow 3 meets cow 4; see (c) above.

N(1 <= N <= 1000)头奶牛，编号为1..N，在参加一个喝茶时间活动。在喝茶时间活动开始之前，已经有M(1 <= M <= 2,000)对奶牛彼此认识（是朋友）。第i对彼此认识的奶牛通过两个不相同的整数Ai和Bi给定(1<= Ai <= N; 1 <= Bi <= N)。输入数据保证一对奶牛不会出现多次。 在喝茶时间活动中，如果奶牛i和奶牛j有一个相同的朋友奶牛k，那么他们会在某次的喝茶活动中去认识对方（成为朋友），从而扩大他们的社交圈。 请判断，在喝茶活动举办很久以后（直到没有新的奶牛彼此认识），Q(1 <= Q <= 100)对奶牛是否已经彼此认识。询问j包含一对不同的奶牛编号Xj和Yj(1 <= Xj <= N; 1 <= Yj <= N)。 例如，假设共有1..5头奶牛，我们知道2号认识5号，2号认识3号，而且4号认识5号；如下图(a)。

```cpp
   2---3           2---3            2---3
    \              |\  |            |\ /|
1    \     -->  1  | \ |    -->  1  | X |
      \            |  \|            |/ \|
   4---5           4---5            4---5
    (a)             (b)              (c)
```
在某次的喝茶活动中，2号认识4号，3号认识5号；如上图(b)所示。接下来的喝茶活动中，3号认识4号，如上图(c)所示。

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

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

\* Lines M+2..M+Q+1: Line j+M+1 contains query j as two space-separated integers: X\_j and Y\_j

行1：三个空格隔开的整数：N，M，和Q

行2..M+1：第i+1行包含两个空格隔开的整数Ai和Bi

行M+2..M+Q+1：第j+M+1行包含两个空格隔开的整数Xj和Yj，表示询问j

outputFormat:
\* Lines 1..Q: Line j should be 'Y' if the cows in the jth query have met and 'N' if they have not met.

行1..Q：如果第j个询问的两头奶牛认识， 第j行输出“Y”。如果不认识，第j行输出“N”

hint: 感谢@蒟蒻orz神犇 提供翻译。


title: [USACO10JAN] Cheese Towers S

description:
Farmer John wants to save some blocks of his cows' delicious Wisconsin cheese varieties in his cellar for the coming winter. He has room for one tower of cheese in his cellar, and that tower's height can be at most T (1 <= T <= 1,000). The cows have provided him with a virtually unlimited number of blocks of each kind of N (1 <= N <= 100) different types of cheese (conveniently numbered 1..N). He'd like to store (subject to the constraints of height) the most

valuable set of blocks he possibly can. The cows will sell the rest to support the orphan calves association.

Each block of the i-th type of cheese has some value V\_i (1 <= V\_i <= 1,000,000) and some height H\_i (5 <= H\_i <= T), which is always a multiple of 5.

Cheese compresses. A block of cheese that has height greater than or equal to K (1 <= K <= T) is considered 'large' and will crush any and all of the cheese blocks (even other large ones) located below it in the tower. A crushed block of cheese doesn't lose any value, but its height reduces to just 4/5 of its old height. Because the height of a block of cheese is always a multiple of 5, the height of a crushed block of cheese will always be an integer. A block of cheese is either crushed or not crushed; having multiple large blocks above it does not crush it more. Only tall blocks of cheese crush other blocks; aggregate height of a tower does not affect whether a block is crushed or not.

What is the total value of the best cheese tower FJ can construct?

Consider, for example, a cheese tower whose maximum height can be 53 to be build from three types of cheese blocks. Large blocks are those that are greater than or equal to 25. Below is a chart of the values and heights of the various cheese blocks he stacks:

Type    Value      Height

1      100         25

2       20          5

3       40         10

FJ constructs the following tower:

Type Height Value

top -> [1]   25    100

```cpp
[2]    4     20   <- crushed by [1] above
[3]    8     40   <- crushed by [1] above
[3]    8     40   <- crushed by [1] above
bottom -> [3]    8     40   <- crushed by [1] above
```
The topmost cheese block is so large that the blocks below it are crushed. The total height is:
```cpp
25 + 4 + 8 + 8 + 8 = 53
The total height does not exceed 53 and thus is 'legal'. The total value is:
100 + 20 + 40 + 40 + 40 = 240.
This is the best tower for this particular set of cheese blocks.
要建一个奶酪塔，高度最大为T。他有N块奶酪。第i块高度为Hi（一定是5的倍数），价值为Vi。一块高度>=K的奶酪被称为大奶酪，一个奶酪如果在它上方有大奶酪（多块只算一次），它的高度就会变成原来的4/5.。 很显然John想让他的奶酪他价值和最大。求这个最大值。
```

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

\* Lines 2..N+1: Line i+1 contains two space separated integers: V\_i and H\_i

outputFormat: \* Line 1: The value of the best tower FJ can build

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

FJ 要建一个奶酪塔，高度最大为 $T\ (1 \le T \le 10^3)$ 。他有 $N\ (1 \le N \le 10^2)$ 种奶酪。第 $i$ 种奶酪的高度为 $H_i\ (5\le H_i \le T\text{ 且 }5 \mid H_i)$ ，价值为 $V_i\ (1 \le V_i \le 10^6)$ 。一块高度 $H_i\ge K\ (1 \le K \le T)$ 的奶酪被称为大奶酪，如果一个奶酪上方有大奶酪（如果有多块就只算一次），这个奶酪的高度 $H_i$ 就会变成原来的 $\frac{4}{5}$。FJ 想让他的奶酪塔价值和最大。请你求出这个最大值。

例如，考虑一种奶酪塔，其最大高度可以是 $53$，可以用三种类型的奶酪块建造。大块是大于或等于 $25$ 的块。下面是他堆叠的各种奶酪块的值和高度的图表：

|类型|价值|高度|
| :----------: | :----------: | :----------: |
|1|100|25|
|2|20|5|
|3|40|10|

FJ建造了以下奶酪塔：

|类型|价值|高度|
| :----------: | :----------: | :----------: |
|1|100|25|
|2|20|4|
|3|40|8|
|3|40|8|
|3|40|8|

总高度是 $25 + 4 + 8 + 8 + 8 = 53$，除塔顶奶酪外，其余高度均被压低。总价值是 $100 + 20 + 40 + 40 + 40 = 240$。

**【输入格式】**

第1行为三个用空格隔开的整数 $N,T,K$。

第2至 $N+1$ 行中第 $i+1$ 行包含两个用空格隔开的整数 $V_i,H_i$。

**【输出格式】**

一行一个整数为奶酪塔的最大价值。


title: [USACO10FEB] Covering the Corral G

description:
The cows are so modest they want Farmer John to install covers around the circular corral where they occasionally gather. The corral has circumference C (1 <= C <= 1,000,000,000), and FJ can choose from a set of M (1 <= M <= 100,000) covers that have fixed starting points and sizes. At least one set of covers can surround the entire corral.

Cover i can be installed at integer location x\_i (distance from starting point around corral) (0 <= x\_i < C) and has integer length l\_i (1 <= l\_i <= C).

FJ wants to minimize the number of segments he must install. What is the minimum number of segments required to cover the entire circumference of the corral?

Consider a corral of circumference 5, shown below as a pair of connected line segments where both '0's are the same point on the corral (as are both 1's, 2's, and 3's).

Three potential covering segments are available for installation:

Start   Length

i     x\_i     l\_i

1      0       1

2      1       2

3      3       3

0   1   2   3   4   0   1   2   3  ...

corral: +---+---+---+---+--:+---+---+---+- ...

11111               1111

22222222            22222222

333333333333

|..................|
As shown, installing segments 2 and 3 cover an extent of (at least) five units around the circumference. FJ has no trouble with the overlap, so don't worry about that.

奶牛们非常羞涩，他们要求Farmer John在他们的圆形牛棚周围建造围栏。牛棚的周长为c(1 <= C <= 1,000,000,000)，现在，FJ希望从一些有固定起点和终点的栏杆的集合里选出一些栏杆。 栏杆i 的起点可以被建造在一个整数位置 x\_i(相距围栏起点i个长度) (0 <= x\_i < C),并且，这个栏杆有一个整数长度l\_i(1 <= l\_i <= C)。 FJ 希望最小化栏杆的数量，从而达到覆盖整个牛棚的外圈。

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

\* Lines 2..M+1: Line i+1 contains two space-separated integers: x\_i and l\_i

outputFormat: \* Line 1: A single integer that is the minimum number of segments required to cover all segments of the circumference of the corral


title: [USACO10FEB] Cows on Ice G

description:
Bessie is ice skating on a large frozen lake modelled as a 2-dimensional grid with coordinates in the range -1,000,000,000..1,000,000,000. N (1 <= N <= 20,000) of the lake's grid cells contain rocks

(conveniently numbered 1..N). The other cells contain slippery ice.

Since Bessie is not a very good skater, she traverses the lake's cells by pushing herself away from her current position near a rock and sliding continuously in the same direction until she hits another rock (stopping in the square before she hits the rock, of course). Never good with complicated angles, Bessie can push herself only straight north, east, south, or west. She can't push herself through the rock, of course, and thus generally has only three possible directions to move.

Sliding is not without risks. Bessie must hit a rock or might end up sliding for a very long time. She must aim her pushes carefully.

Consider the situation depicted below; Bessie wants to get to

location (x=5,y=1), which is east of her current location (. = ice, \* = rock, B = Bessie, G = goal). If she slides directly to the east, she will slide past the location since she can stop only by

encountering a rock head on. One way to get to (5,1) is the following:

(a)              (b)             (c)              (d)

4 .....\*.         .....\*.         .....\*.          .....\*.

3 ..\*....  slide  ..\*....  slide  ..\*....   slide  ..\*....

2 ......\*  north  ..B...\*  east   .....B\*   south  ......\*

1 .\*B..G. ------> .\*...G. ------> .\*...G.  ------> .\*...B.

0 \*....\*.         \*....\*.         \*....\*.          \*....\*.

0123456

Bessie could slide north, east, or south in situation (a), but only north has a rock for stopping. For situation (b), she can slide only east for the same reason.

For the input, rock i is located at cell X\_i,Y\_i (-1,000,000,000 <= X\_i <= 1,000,000,000; -1,000,000,000 <= Y\_i <= 1,000,000,000), and no two rocks occupy the same position. Bessie starts at Bx,By (which is next to a rock) (-1,000,000,000 <= Bx <= 1,000,000,000; -1,000,000,000 <= By <= 1,000,000,000). Bessie's goal is Gx,Gy (-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <= 1,000,000,000). Bessie can always reach the goal one way or another.

Bessie doesn't mind sliding. However, pushing herself away from a rock is very tiring. To prepare her, FJ would like to know the minimum number of pushes Bessie needs to do.

Bessie 在一个冰封的湖面上游泳，湖面可以表示为二维的平面，坐标范围是-1,000,000,000..1,000,000,000。湖面上的N(1 <= N <= 20,000)个位置有石块(编号分别为1到N)，其它位置是冰面。由于Bessie滑冰技术不够好，她通过推动自己旁边的石块，依靠反作用力向某一个方向前进，在碰到一个新的石块之前，Bessie是不会停下来的。(当然，最后会停留在某块石块的前一个格子里)由于Bessie无法计算复杂的角度，她只能够向东南西北四个方向前进。

很显然，Bessie不能够穿越石块，因此，Bessie仅仅可以向三个方向滑。 滑冰不是没有风险，Bessie滑向某个方向后必须能碰到某个石块，因此她必须很小心。考虑下面的一个情况，Bessie希望到达在她东面的目标位置(x=5,y=1)，(…

inputFormat:
\* Line 1: Five space separated integers: N, Bx, By, Gx, and Gy

\* Lines 2..N+1: Line i+1 describes a rock location with space

separated integers: X\_i and Y\_i

outputFormat: \* Line 1: A single integer that is the minimum number of pushes for Bessie to get to her goal


title: [USACO10FEB] Slowing down G

description:
Every day each of Farmer John's N $(1 \le N \le 100,000)$ cows conveniently numbered $1..N$ move from the barn to her private pasture. The pastures are organized as a tree, with the barn being on pasture $1$. Exactly $N-1$ cow unidirectional paths connect the pastures; directly connected pastures have exactly one path. Path $i$ connects pastures $A_i$ and $B_i$ $(1 \le A_i \le N,1 \le B_i \le N)$.

Cow $i$ has a private pasture $P_i(1 \le P_i \le N)$. The barn's small door lets only one cow exit at a time; and the patient cows wait until their predecessor arrives at her private pasture. First cow $1$ exits and moves to pasture $P_1$. Then cow $2$ exits and goes to pasture $P_2$, and so on.

While cow $i$ walks to $P_i$ she might or might not pass through a pasture that already contains an eating cow. When a cow is present in a pasture, cow $i$ walks slower than usual to prevent annoying her friend.

```cpp
Consider the following pasture network, where the number between
parentheses indicates the pastures' owner.

        1 (3)
       / \
  (1) 4   3 (5)
     / \
(2) 2   5 (4)

First, cow 1 walks to her pasture:

        1 (3)
       / \
  [1] 4*  3 (5)
     / \
(2) 2   5 (4)

When cow 2 moves to her pasture, she first passes into the barn's
pasture, pasture 1. Then she sneaks around cow 1 in pasture 4 before
arriving at her own pasture.

        1 (3)
       / \
  [1] 4*  3 (5)
     / \
[2] 2*  5 (4)

Cow 3 doesn't get far at all -- she lounges in the barn's pasture, #1.

        1* [3]
       / \
  [1] 4*  3 (5)
     / \
[2] 2*  5 (4)

Cow 4 must slow for pasture 1 and 4 on her way to pasture 5:

        1* [3]
       / \
  [1] 4*  3 (5)
     / \
[2] 2*  5* [4]

Cow 5 slows for cow 3 in pasture 1 and then enters her own private pasture:

        1* [3]
       / \
  [1] 4*  3*[5]
     / \
[2] 2*  5* [4]
```

FJ would like to know how many times each cow has to slow down.

每天 Farmer John 的 $N$ 头奶牛，编号 $1 \ldots N$，从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在 $1$ 号牧场。恰好有 $N-1$ 条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第 $i$ 条路连接着 $A_i$ 和 $B_i$。奶牛们每人有一个私人牧场 $P_i$。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛 $1$ 离开，前往 $P_1$；然后是奶牛 $2$，以此类推。

当奶牛 $i$ 走向牧场 $P_i$ 的时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛 $i$ 会放慢自己的速度，防止打扰他的朋友。

FJ 想要知道奶牛们总共要放慢多少次速度。

inputFormat:
\* Line $1$: Line $1$ contains a single integer: $N$

\* Lines $2..N$: Line $i+1$ contains two space-separated integers: $A_i$ and $B_i$

\* Lines $N+1..N+N$: line $N+i$ contains a single integer: $P_i$

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

第 $2 \sim N$ 行：第 $i+1$ 行有两个以空格隔开的整数 $A_i$ 和 $B_i$。

第 $N+1 \sim N+N$ 行：第 $N+i$ 行有一个整数 $P_i$。

outputFormat:
\* Lines $1 \sim N$：Line $i$ contains the number of times cow $i$ has to slow down.

第 $1 \sim N$ 行：第 $i$ 行包括奶牛 $i$ 需要放慢速度的次数。

hint: 数据范围：$1 \leq A_i,B_i,P_i\leq N \leq 10^5$。


title: [USACO10FEB] Chocolate Buying S

description:
Bessie and the herd love chocolate so Farmer John is buying them some.

The Bovine Chocolate Store features $N (1 \le N \le 100,000)$ kinds of chocolate in essentially unlimited quantities.  Each type i of chocolate has price $P_i (1 \le P_i \le 10^{18})$ per piece and there are $C_i (1 \le C_i \le 10^{18})$ cows that want that type of chocolate.

Farmer John has a budget of $B (1 \le B \le 10^{18})$ that he can spend on chocolates for the cows. What is the maximum number of cows that he can satisfy?  All cows only want one type of chocolate, and will be satisfied only by that type.

Consider an example where FJ has $50$ to spend on $5$ different types of chocolate. A total of eleven cows have various chocolate preferences:

|Chocolate\_Type|Per\_Chocolate\_Cost|Cows\_preferring\_this\_type|
|:-----------:|:-----------:|:-----------:|
|$1$|$5$|$3$|
|$2$|$1$|$1$|
|$3$|$10$|$4$|
|$4$|$7$|$2$|
|$5$|$60$|$1$|

Obviously, FJ can't purchase chocolate type $5$, since he doesn't have enough money. Even if it cost only $50$, it's a counterproductive purchase since only one cow would be satisfied.

Looking at the chocolates start at the less expensive ones, he can purchase $1$ chocolate of type $2$ for $1 \times 1$ leaving $50-1=49$, then purchase $3$ chocolate of type $1$ for $3 \times 5$ leaving $49-15=34$, then  purchase $2$ chocolate of type $4$ for $2 \times 7$ leaving $34-14=20$, then  purchase $2$ chocolate of type $3$ for $2 \times 10$ leaving $20-20=0$.

He would thus satisfy $1 + 3 + 2 + 2 = 8$ cows.

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

Lines $2\ldots N+1$: Line $i$ contains two space separated integers defining chocolate type $i$: $P_i$ and $C_i$.

outputFormat: Line $1$: A single integer that is the maximum number of cows that Farmer John can satisfy.

translation:
贝茜和其他奶牛们都喜欢巧克力，所以约翰准备买一些送给她们。奶牛巧克力专卖店里有 $N$ 种巧克力，每种巧克力的数量都是无限多的。

每头奶牛只喜欢一种巧克力，调查显示，有 $C_i$ 头奶牛喜欢第 $i$ 种巧克力，这种巧克力的售价是 $P_i$。

约翰手上有 $B$ 元预算，怎样用这些钱让尽量多的奶牛高兴呢？


title: [USACO10FEB] Chocolate Giving S

description:
Farmer John is distributing chocolates at the barn for Valentine's day, and B (1 <= B <= 25,000) of his bulls have a special cow in mind to receive a chocolate gift.

Each of the bulls and cows is grazing alone in one of the farm's N (2\*B <= N <= 50,000) pastures conveniently numbered 1..N and connected by M (N-1 <= M <= 100,000) bidirectional cowpaths of various lengths. Some pastures might be directly connected by more than one cowpath. Cowpath i connects pastures R\_i and S\_i (1 <= R\_i <= N; 1 <= S\_i <= N) and has length L\_i (1 <= L\_i <= 2,000).

Bull i resides in pasture P\_i (1 <= P\_i <= N) and wishes to give a chocolate to the cow in pasture Q\_i (1 <= Q\_i <= N).

Help the bulls find the shortest path from their current pasture to the barn (which is located at pasture 1) and then onward to the pasture where their special cow is grazing. The barn connects, one way or another (potentially via other cowpaths and pastures) to every pasture.

As an example, consider a farm with 6 pastures, 6 paths, and 3 bulls (in pastures 2, 3, and 5) who wish to bestow chocolates on their love-objects:

```cpp

                      *1  <-- Bull wants chocolates for pasture 1 cow
             [4]--3--[5]  <-- [5] is the pasture ID
            /  |
           /   |
          4    2          <-- 2 is the cowpath length
         /     |               between [3] and [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4
```
\* The Bull in pasture 2 can travel distance 3 (two different ways) to get to the barn then travel distance 2+1 to pastures [3] and [4] to gift his chocolate. That's 6 altogether.

\* The Bull in pasture 5 can travel to pasture 4 (distance 3), then pastures 3 and 1 (total: 3 + 2 + 1 = 6) to bestow his chocolate offer.

\* The Bull in pasture 3 can travel distance 1 to pasture 1 and then take his chocolate 9 more to pasture 6, a total distance of 10.

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

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

space-separated integers: R\_i, S\_i, and L\_i

\* Lines M+2..M+B+1: Line M+i+1 contains two space separated integers: P\_i and Q\_i

outputFormat: \* Lines 1..B: Line i should contain a single integer, the smallest distance that the bull in pasture P\_i must travel to get chocolates from the barn and then award them to the cow of his dreams in pasture Q\_i

translation:
### 题目描述

FJ 有 $B$ 头奶牛 $(1\le B\le 25000)$，有 $N(2\times B\le N\le 50000)$ 个农场，编号 $1$ 到 $N$，有 $M(N-1\le M\le 100000)$ 条双向边，第 $i$ 条边连接农场 $R_i$ 和 $S_i(1\le R_i\le N, 1\le S_i\le N)$，该边的长度是 $L_i(1\le L_i\le 2000)$。居住在农场 $P_i$ 的奶牛 A $(1\le P_i\le N)$，想送一份新年礼物给居住在农场 $Q_i(1\le Q_i\le N)$ 的奶牛 B，但是奶牛 A 必须先到 FJ（居住在编号 $1$ 的农场）那里取礼物，然后再送给奶牛 B。你的任务是：奶牛 A 至少需要走多远的路程？

### 输入格式
* 第一行三个整数 $N,M,B$。
* 第 $2$ 至 $M+1$ 行，每行 $3$ 个整数 $R_i,S_i,L_i$。

* 第 $M+2$ 至 $M+B+1$ 行，进行 $B$ 次询问，每行 $2$ 个整数 $P_i ,Q_i$。

### 输出格式
每次询问输出一个整数，即答案。


title: [USACO10FEB] Chocolate Eating S

description:
Bessie has received N (1 <= N <= 50,000) chocolates from the bulls, but doesn't want to eat them too quickly, so she wants to plan out her chocolate eating schedule for the next D (1 <= D <= 50,000) days in order to maximize her minimum happiness level over the set of those days.

Bessie's happiness level is an integer that starts at 0 and halves (rounding down if necessary) over night as she sleeps. However, when she eats chocolate i, her happiness level increases by integer H\_i (1 <= H\_i <= 1,000,000). If she eats chocolates on a day, her happiness for that day is considered the happiness level after she eats the chocolates. Bessie insists that she eat the chocolates in the order that she received them.

If more than one optimal solution exists, print any one of them.

Consider a sequence of 5 chocolates to be eaten over a period of 5 days; they respectively bring happiness (10, 40, 13, 22, 7).

If Bessie eats the first chocolate (10 happiness) on the first day and then waits to eat the others, her happiness level is 10 after the first day.

Here is the complete schedule which turns out to maximize her minimum happiness:

Day  Wakeup happiness   Happiness from eating   Bedtime happiness 1            0                10+40                  50

2           25                 ---                   25

3           12                  13                   25

4           12                  22                   34

5           17                   7                   24

The minimum bedtime happiness is 24, which turns out to be the best Bessie can do.

Bessie 拿到了 $N$（$1 \leq N \leq 5\times 10 ^ 4$）块巧克力。她决定想个办法吃掉这些巧克力，使得它在吃巧克力的这段时间里，最不开心的一天尽可能的开心。并且一共吃 $D$（$1 \leq D \leq 5\times 10 ^ 4$）天。

每块巧克力有一个开心值 $H_i$（$1 \leq H_i \leq 10 ^ 6$），当某天你吃下那块巧克力时，你将获得那块巧克力的开心值。每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上 Bessie 睡觉之后，它的开心值会减半。也就是说，比如昨天 Bessie 的开心值为 $50$，那么今天早上一醒来就会有 $25$ 点的开心值，舍去小数点后数字。另外，Bessie 还有一个怪癖，她喜欢按照巧克力本来的排列顺序吃。

Bessie 第一天的开心值为 $0$，求一个每天吃巧克力的方案，使得 Bessie 最不开心的一天尽可能的开心。

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

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

第一行：两个整数 $N$ 和 $D$，中间用空格分隔。

第 $2$ 行至第 $N + 1$ 行：每行一个整数，第 $i + 1$ 行表示 $H_i$ 的值。

outputFormat:
\* Line 1: A single integer, the highest Bessie's minimum happiness can be over the next D days

\* Lines 2..N+1: Line i+1 contains an integer that is the day on which Bessie eats chocolate i

第一行：一个整数，表示 Bessie 在 $D$ 天中最不开心的一天最大可能的开心值。

第 $2$ 至第 $n + 1$ 行，每行一个整数，第 $i + 1$ 行表示 Bessie 吃第 $i$ 块巧克力的日期。


title: [USACO10MAR] Great Cow Gathering G

description:
Bessie 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

每个奶牛居住在 $N$ 个农场中的一个，这些农场由 $N-1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 $i$ 连接农场 $A_i$ 和 $B_i$，长度为 $L_i$。集会可以在 $N$ 个农场中的任意一个举行。另外，每个牛棚中居住着 $C_i$ 只奶牛。

在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 $X$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 $i$ 到达农场 $X$ 的距离是 $20$，那么总路程就是 $C_i\times 20$）。帮助 Bessie 找出最方便的地点来举行大集会。

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

第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $C_i$。

第 $N+2$ 行到 $2N$ 行：第 $i+N+1$ 行为 $3$ 个整数：$A_i,B_i$ 和 $L_i$。

outputFormat: 一行一个整数，表示最小的不方便值。

hint: $1\leq N\leq 10^5$，$1\leq A_i\leq B_i\leq N$，$0 \leq C_i,L_i \leq 10^3$。


title: [USACO10MAR] StarCowraft G

description:
The beta version of StarCowraft II is ready! Farmer John and Bessie are testing it, trying different strategies in one-on-one battles against each other's armies. The goal in StarCowraft II is to defeat your opponent's army in a battle.

Each player's army fights in a battle. An army comprises as many as three different types of 'units' with respective strengths denoted by constant positive real numbers unknown to the players: cattlebruisers with strength S1, cow templars with strength S2, and ultracows with strength S3. The only given bounding information is that no unit is more than 100 times as strong as any another unit.

An army's total strength is the sum of the individual strengths of each of its units. An army that has, among others units, 23

cattlebruisers would gain 23\*S1 strength just from the cattlebruisers.

When two opposing armies fight in a battle, the army with a higher total strength value wins.  If the armies have exactly equal strength values, one of the players randomly wins.

Farmer John and Bessie played N (0 <= N <= 300) 'test battles'. In the i-th test battle, FJ's army had J1\_i cattlebruisers, J2\_i cow templars, and J3\_i ultracows (0 <= J1\_i + J2\_i + J3\_i <= 1,000). Similarly, Bessie's army had B1\_i cattlebruisers, B2\_i cow templars, and B3\_i ultracows (0 <= B1\_i + B2\_i + B3\_i <= 1,000). After their armies fought against each other, FJ and Bessie recorded the winner as a single 'victory letter' V\_i: 'J' if Farm John won the battle; 'B' if Bessie won.

Although these victory results are the only information that they have, they hope to predict some of the results of additional battles if they are given the unit compositions of two opposing armies. For some battles, though, they know it might not be possible to determine the winner with certainty.

Given the results of the N test battles that Farmer John and Bessie already played, write a program that decides the winner (if possible) for M (1 <= M <= 2,000) new battles.

The results reported for the test battles are correct; there exists at least one set of strength values which are consistent with the results.

For purposes of demonstrating the army strength evaluation functions, consider these test battles fought in a game where we (but neither FJ nor Bessie) know that S1=9.0, S2=7.0, and S3=4.0:

```cpp
---- Farmer John ----    ------- Bessie ------    Battle
J1  J2  J3 J_Strength    B1  B2  B3 B_Strength   Outcome
6   5   4    105         5   4   7    101          J
5   4   2     81         3   5   5     82          B
9   0  10    121         8   2   7    114          J
```
These results connote the following deduced results for the reasons shown:

---- Farmer John ----    ------- Bessie ------    Battle

J1  J2  J3 J\_Strength    B1  B2  B3 B\_Strength   Outcome

6   6   4    112         5   4   7    101          J

FJ's army is even stronger than in test battle 1 9   0  10    121         8   2   6    110          J

Bessie's army is even weaker than in test battle 3

《星际争霸2》全面公测啦！Farmer John和Bessie正在测试中——在1v1的战役中使用一些不同的策略来对抗对方的部队。《星际争霸2》的游戏目标就是在战役中打败你对手的军队。

每个选手的军队都在战役中拼杀。一支军队由若干3种不同类型的单位所组成，不同单位有着不同的由正实数表示的，且不被选手所知道的力量值：cattlebruisers 的力量是S1，cow templars 的力量是S2，ultracows的力量是S3。唯一提供的信息是，没有一个单位的力量值超过另一个单位力量值的100倍。

一支军队的总力量值，是其中各自单独的单位的力量值的总和。比如一支军队除了其他单位有23个cattlebruisers，那么这支军队单独从cattlebruisers就能获得23\*S1的力量值。

当两支对立的军队在战役中厮杀，有着更高力量值的军队将获得胜利。如果两支军队的力量值恰好相同，那么将随机产生一个获胜方。

Farmer John 和 Bessie 进行了 N (0 <= N <= 300) 局的“测试战役”。在第 i 局测试战役中，Farmer John 有 J1\_i 个 cattlebruisers，J2\_i 个 cow templars 以及 J3\_i 个 ultracows(0 <= J1\_i + J2\_i + J3\_i <= 1,000)。相似的，Bessie的军队有 B1\_i 个 cattlebruisers，B2\_i 个 cow templars 以及 B3\_i 个 ultracows (0 <= B1\_i + B2\_i + B3\_i <= 1,000)。当他们的军队战斗结束后，FJ 和 Bessie 将胜者以一个单独的“胜利字母” V\_i 记录下来："J"表示 Farmer John 赢得了战役；"B" 表示 Bessie 获胜了。

虽然这些结果是他们唯一所拥有的信息，但是他们希望预测一些额外的战役的结果——如果告知他们两支对立军队的组成。尽管，可能对于一些比赛他们是无法确定到底哪一方一定能获胜的。

给出已经结束的 N 场测试战役的结果，写一个程序来确定(如果可能的话)M (1 <=M <=2,000)场额外战役的获胜方。

所有给出的测试战役的结果都是正确的。至少存在一种合法的力量值的取值符合这些结果。

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

\* Lines 2..N+1: Line i+1 describes a test battle with seven

space-separated items -- a victory letter and six

space-separated integer unit counts: V\_i, J1\_i, J2\_i, J3\_i, B1\_i, B2\_i, and B3\_i

\* Lines N+2..N+M+1: Line i+N+1 describes a 'new battle' using six space-separated integers: J1\_i, J2\_i, J3\_i, B1\_i, B2\_i, and B3\_i

outputFormat: \* Lines 1..M: Line i contains the outcome of the i-th new battle: 'J' if Farmer John definitely wins, 'B' if Bessie definitely wins, and 'U' (undecidable) if it is impossible to decide the winner with the given information.

hint: First two games correspond to the examples in the description. The result of the last game cannot be determined with only the information that Farmer John and Bessie currently have. Specifically, both S\_1=9.0, S\_2=7.0, S\_3=4.0 and S\_1=12.0, S\_2=20.0, S\_3=10.0 are consistent with the "test battles," but they give different results when plugged in the third "new battle."


title: [USACO10MAR] Test Taking S

description:
Farmer John has to take his annual farming license test. The test comprises N (1 <= N <= 1,000,000) true/false questions. After FJ's dismal performance on last year's test Bessie wishes to help him.

Bessie has inside information that the number of questions whose answer is true will be one of t\_1, t\_2, t\_3,..., or t\_K (0 <= t\_i <= N; 0 <= K <= 10,000) -- even though Bessie has no information about any answer to any specific question. Bessie wants to know the best score that FJ is guaranteed achieve by exploiting this information carefully, even if he doesn't know the actual answers to any test questions.

To demonstrate Bessie's idea, consider a license test with N=6 questions where Bessie knows that the number of questions with the answer 'true' is either 0 or 3. FJ can always get at least 3 answers correct using logic like this: If FJ answers 'false' on every

question and there are 0 questions with the answer 'true' then he will get all 6 correct. If there are 3 questions with the answer 'true' then he will get 3 answers correct. So as long as he marks every answer as 'false' he is guaranteed to get at least 3 correct without knowing any answer to the test questions.

On the other hand, consider what happens if FJ chooses an inferior strategy: he guesses that some 3 answers are 'true' and the other 3 are 'false'. If it turns out that NO answers are 'true' then FJ will get 3 answers correct, the ones he guessed were false. If 3 answers are 'true' then FJ could get as few as 0 answers correct. If he answered incorrectly on all 3 of that answers for which he guessed 'true', and the other 3 (for which he guessed 'false') are true, then he gets 0 correct answers. Even though FJ could get 3 correct in this case by guessing 'false' every time, he can not always guarantee even 1 correct by guessing some 3 answers as 'true', so this strategy can not guarantee getting any answer correct. FJ should use the previous paragraph's strategy.

Given Bessie's inside information, determine the number of answers FJ can always get correct using this information assuming he uses it optimally.

Farmer John要参加一年一度的农民资格考试。考试很简单，只有N个 （1≤N≤1，000，000)true/false的判断题。然而FJ去年考试却“杯具”了，Bessie：希望今年能帮帮他。

Bessie得到可靠的内部消息，有可能有T\_1，T\_2，T\_3，...，或T\_K(0≤T\_i≤N；0≤K≤10，000)

道题的答案为ture：，但具体哪道题的答案是什么却不知道。Bessie希望知道在认真研究了这些内部消息后(虽然不能确定任何一道题的具体答案)，一定保证FJ考试时能获得的最高分数是多少?

为了说明Bessie的想法，考虑N=6的一次考试，Bessie知道答案为true的题的数量是0或者3。FJ可以按这样的做题策略来答对至少3题：如果FJ全部答'false'，那么当有0道题的正确答案是'true'，则FJ答对6题；而当有3道题的正确答案是'true'，则FJ答对3题。因此，只要FJ部答'false'，那么至少一定能答对3题，尽管FJ并不知道每道题的确切答案。

另一方面，考虑如果FJ选择了另一种非最优的做题策略：他猜测某3道题为'true'而另3道题为'false'。当所有题目的正确答案是'false'时，那么FJ能答对3道题。而当有3道题的正确答案是'true'时，那么FJ有可能一道题都答不对。这是因为FJ有可能把3道正确答案为'true'的题全猜成'false'!这说明这种做题策略不如前一种优秀。

给出Bessie获得的内部消息，计算出FJ采用最优做题策略保证能得到的最高分数是多少?

第1行：2个整数N，K

第2…K+1行：第i+1行包含一个整数t_i

第1行：一个整数，表示FJ一定能获得的最高分数

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

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

第1行：2个整数N，K

第2…K+1行：第i+1行包含一个整数t\_i

第1行：一个整数，表示FJ一定能获得的最高分数

outputFormat: \* Line 1: A single integer, the best score FJ is guaranteed to achieve

hint: 翻译提供： @fan404


title: [USACO10MAR] Need For Speed S

description:
Bessie is preparing her race car for the upcoming Grand Prix, but she wants to buy some extra parts to improve the car's performance. Her race car currently has mass M (1 <= M <= 1,000) and is able to push itself forward with a force of F (1 <= F <= 1,000,000). The Race Car Performance Store has N (1 <= N <= 10,000) parts

conveniently numbered 1..N. Bessie can buy as many or as few parts as she wishes though the store stocks no more than one instance of each part.

Part P\_i adds force F\_i (1 <= F\_i <= 1,000,000) and has mass

M\_i (1 <= M\_i <= 1,000). Newton's Second Law decrees that F =

MA, where F is force, M is mass, and A is acceleration. If Bessie wants to maximize the total acceleration of her race car (and

minimize the mass otherwise), which extra parts should she choose?

Consider a race car with initial F=1500 and M=100. Four parts are available for enhancement:

i  F\_i  M\_i

1  250   25

2  150    9

3  120    5

4  200    8

Adding just part 2, e.g., would result in an acceleration of

(1500+150)/(100+9) = 1650/109 = 15.13761.

Below is a chart of showing the acceleration for all possible

combinations of adding/not-adding the four parts (in column one, 1=part added, 0=part not added):

Parts   Aggregate   Aggregate

1234        F           M       F/M

0000      1500         100    15.0000

0001      1700         108    15.7407

0010      1620         105    15.4286

0011      1820         113    16.1062

0100      1650         109    15.1376

0101      1850         117    15.8120

0110      1770         114    15.5263

0111      1970         122    16.1475 <-- highest F/M

1000      1750         125    14.0000

1001      1950         133    14.6617

1010      1870         130    14.3846

1011      2070         138    15.0000

1100      1900         134    14.1791

1101      2100         142    14.7887

1110      2020         139    14.5324

1111      2220         147    15.1020

Thus, the best additional part combination is parts 2, 3, and 4.

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

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

outputFormat: \* Lines 1..P: The index values of P extra parts, one per line, that Bessie should add to her racecar. If she should not add any, output 'NONE' (without quotes). The output should be given in increasing order, so if the optimal set of parts is {2,4,6,7}, then the output should be in the order 2,4,6,7 and not, for example, 4,2,7,6. Solutions will be unique.

translation:
Bassie正在为即将到来的赛车比赛作准备。

她有一辆赛车，重为M，且可以提供F的力。

现在她想要给这辆赛车安装一些零件（总共有N个零件），每个零件具有属性$M_i$和$F_i$，表示其重量以及可以提供的力。

设$X_i = 1\text{或}0$，表示第i个零件选或不选。

最大化$\frac{F+\sum_{i=1}^{n}X_i \times F_i}{M+\sum_{i=1}^{n}X_i \times M_i}$;

在此基础上最小化$\sum_{i=1}^{n}X_i \times M_i + M$。

输入格式：

第一行是三个用空格分开的数F,M,N

接下来N行，每行一个数，第i+1行的两个数代表$F_i$和$M_i$

输出格式：

输出最终的，按照原始顺序排好序的方案$\{i | X_i = 1\}$ ，特别的，若Bassie不需要给这辆车安装零件，输出"None"（没有双引号）。

$N \le 10000 $

$M,M_i\le1000$

$F,F_i \le 1,000,000 $

感谢@tyqtyq 提供的翻译


title: [USACO10OPEN] Cow Hopscotch G

description:
The cows have reverted to their childhood and are playing a game similar to human hopscotch. Their hopscotch game features a line of N (3 <= N <= 250,000) squares conveniently labeled 1..N that are chalked onto the grass.

Like any good game, this version of hopscotch has prizes!  Square i is labeled with some integer monetary value V\_i (-2,000,000,000 <= V\_i <= 2,000,000,000). The cows play the game to see who can earn the most money.

The rules are fairly simple:

\* A cow starts at square '0' (located just before square 1; it has no monetary value).

\* She then executes a potentially empty sequence of jumps toward square N. Each square she lands on can be a maximum of K (2 <= K <= N) squares from its predecessor square (i.e., from square 1, she can jump outbound to squares 2 or 3 if K==2).

\* Whenever she wishes, the cow turns around and jumps back towards square 0, stopping when she arrives there. In addition to the restrictions above (including the K limit), two

additional restrictions apply:

\* She is not allowed to land on any square she touched on her outbound trip (except square 0, of course).

\* Except for square 0, the squares she lands on during the return trip must directly precede squares she landed on

during the outbound trip (though she might make some larger leaps that skip potential return squares altogether).

She earns an amount of money equal to the sum of the monetary values of all the squares she jumped on. Find the largest amount of cash a cow can earn.

By way of example, consider this six-box cow-hopscotch course where K has the value 3:

```cpp
Square Num:    0      1      2      3      4      5      6
+---+  +---+  +---+  +---+  +---+  +---+  +---+
|///|--|   |--|   |--|   |--|   |--|   |--|   |
+---+  +---+  +---+  +---+  +---+  +---+  +---+
Value:    -      0      1      2     -3      4      5
```
One (optimal) sequence Bessie could jump (shown with respective bracketed monetary values) is: 1[0], 3[2], 6[5], 5[4], 2[1], 0[0] would yield a monetary total of 0+2+5+4+1+0=12.

If Bessie jumped a sequence beginning with 0, 1, 2, 3, 4, ... then she would be unable to return since she could not legally jump back to an untouched square.

奶牛们正在回味童年，玩一个类似跳格子的游戏，在这个游戏里，奶

牛们在草地上画了一行N个格子，(3 <=N <= 250,000)，编号为1..N。

就像任何一个好游戏一样，这样的跳格子游戏也有奖励！第i个格子标有一个数字V\_i(-2,000,000,000 <=V\_i <= 2,000,000,000)表示这个格子的钱。奶牛们想看看最后谁能得到最多的钱。

规则很简单：

\* 每个奶牛从0号格子出发。(0号格子在1号之前，那里没钱)

\* 她向N号格子进行一系列的跳跃(也可以不跳)，每次她跳到的格子最多可以和前一个落脚的格子差K格(1 <= K <= N)(比方说，当前在1号格，K=2, 可以跳到2号和3号格子)

\*在任何时候，她都可以选择回头往0号格子跳，直到跳到0号格子。另外，除了以上规则之外，

回头跳的时候还有两条规则：

\*不可以跳到之前停留的格子。

\*除了0号格子之外，她在回来的时候，停留的格子必须是恰巧过去的时候停留的某个格子的前一格(当然，也可以跳过某些过去…

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

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

outputFormat: \* Line 1: A single line with a single integer that is the maximum amount of money a cow can earn