Problem 1: Bovine Bones [Rob Kolstad, 2008]
Bessie十分喜欢角色扮演游戏，所以他说服了Farmer John带她到Hobby Shop去，现在Bessie有三颗骰子，这些骰子分别有S1,S2,S3面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40)
Bessie不停的扔啊扔，试图找出这三枚骰子最常出现的和是多少。
现在给出这三枚骰子各有几面，请你计算出这三个骰子最常出现的和是多少，如果不止一个和出现同样的次数，输出最小的那个和。
输入格式：
仅一行，S1,S2,S3用空格分隔
输出格式
仅一行，出现几率最高的和中最小的一个。
样例输入：
3 2 3
样例输出：
5
样例说明：
一下是所有可能出现的情况：
1 1 1 -> 3 1 2 1 -> 4 2 1 1 -> 4 2 2 1 -> 5 3 1 1 -> 5 3 2 1 -> 6
1 1 2 -> 4 1 2 2 -> 5 2 1 2 -> 5 2 2 2 -> 6 3 1 2 -> 6 3 2 2 -> 7
1 1 3 -> 5 1 2 3 -> 6 2 1 3 -> 6 2 2 3 -> 7 3 1 3 -> 7 3 2 3 -> 8
5和6都出现了5次，所以最终的答案是5。
Problem 2: Building A Fence [Jeffrey Wang, 2007]
勤奋的Farmer John想要建造一个由四面围成的栅栏来关住那些奶牛。他现在有一块长度为N(4 <= N <=2,500)的长木板，他需要把这块长木板切成边长均为正整数的四块，使得他能建造一个栅栏。
请问他有多少种不同的切割方式能使切割出来的木板围成一个四面的栅栏。
注意：
1. 不要考虑对称性的问题，不需要去除对称的方案和类似的复杂问题。
2. 栅栏围成的面积必须大于0
3. 结果可以用32位整数存储
输入格式：
仅一行，整数N
输出格式：
仅一行，Farmer John能将木板分割开来并能围成四边形的方案数。
样例输入：
6
样例输出：
6
样例解释：
Farmer John有10中方法将木板分成四块：(1, 1, 1,3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,1, 1); (2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1);(3, 1, 1, 1).
其中有四种情况是不能围成一个四边形的：(1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), (3,1, 1, 1)
Problem 3: Watering Hole [Paul Christiano, 2007]
Farmer John决定给他分别用1到N(1 <= N <= 300)分别编号的牧草浇水，他可以直接在一颗牧草旁边直接挖一口井来获得水，也可以用管子从任意有水的牧草那里来获得水。
在第i颗牧草旁边挖一口井的代价为Wi(1 <= W_i <= 100,000)，用管子连接第i与第j颗牧草的代价为Pij(1 <= Pij <=100,000; Pij = Pji; Pii=0)
请求出Farmer John浇灌这些牧草花费的最小代价。
输入格式：
第一行，一个整数N
第二行到第N+1行，行i+1表示Wi
第N+2行到第2N+1行，行N+1+i包含N个用空格分隔开来的整数，每行第j个数字即是Pij
输出格式：
仅一行，Farmer John浇灌这些牧草的最小代价。
样例输入：
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
样例输出：
9
样例解释：
总共有4颗牧草，在每个牧草旁边挖一口井的代价分别为1,4,4,3，每个点连接一根管子的价格用邻接矩阵给出。最优解为在第4颗牧草旁边挖一口井并把所有的牧草用连接起来，总代价为：3 + 2 + 2 + 2 = 9。
Problem 4: Pasture Walking [Neal Wu, 2007]
有N (2 <= N <= 1,000)头奶牛，分别编号为1到N。还有N颗牧草分别编号为1到N。简单起见，第i头奶牛都盯着第i颗牧草。
有几对牧草分别用一些小路连接了起来，总共有N-1条双向的小路，小路i连接了Ai及Bi颗牧草(1 <= Ai <= N; 1 <= Bi <= N)，小路的长度为Li (1 <= Li <= 10,000)
保证任意两颗牧草总能通过小路走到，也就是说这些小路构成了一棵树。
奶牛是群居性的动物，很喜欢串门。奶牛们会问你Q次问题(1 <= Q <= 1,000)，每次询问的内容很简单，就是从p1颗牧草到p2颗牧草最短的距离是多少。(1 <= p1 <= N; 1 <=p2 <= N)
输入格式：
第一行，两个用空格分隔的整数：N和Q
第二行到第N行，第i+1行包含三个用空格分隔的整数Ai,Bi,Li
第N+1行到第N+Q行，每行包含两个用空格分隔的整数p1,p2
输出格式：
共Q行，每行包含每次询问的最短距离的值。
输入样例：
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
输出样例：
2
7
样例解释：
询问1：1->2 总代价为2
询问2：3->4->1->2 总代价为7
Problem 5: Wheel Rotation [Fatih Gelgi, 2008]
Farmer John有一台老式的打谷机，需要在不同的齿轮上安装皮带来带动它工作。这个打谷机的引擎是1号滑轮顺时针转动，通过一根皮带带动2号滑轮转动，2号滑轮也通过皮带带动3号滑轮转动，依次类推，总共有N个滑轮，N-1根皮带(2 <= N <= 1,000)。
上面的这个图示给出了皮带的两种不同的连接方式，第一种成为直接连接，会被动滑轮与主动滑轮同向旋转，第二种成为交错连接，会使得被动滑轮反向旋转。
给出所有皮带的连接方式，已知1号滑轮是顺时针旋转的，请问第N号滑轮是怎么旋转的。
每条皮带用三个整数描述：
Si：皮带的主动轮编号
Di：皮带的被动轮编号
Ci：连接方式（0代表直接连接，1代表交错连接）
很不幸，Farmer John并不是按照序号依次给出这些数据的。
下面是一个N=4的例子，2与3之间使用直接连接，所以2和3都是顺时针旋转，3和4之间使用交错连接，所以4号滑轮是逆时针旋转的。
输入格式：
第一行，一个整数N
第二行到第N行，每行分别用三个整数Si,Di,Ci描述一条皮带。
输出格式：
仅一行，一个整数表示第N个滑轮的旋转方向，0代表顺时针，1代表逆时针。
样例输入：
4
2 3 0
3 4 1
1 2 0
样例输出：
1
Problem 6: Power Failure [Rob Kolstad, 2008]
一次严重的暴风雨破坏了一些农场电力网络的一些线路！Farmer John有一张包含(2 <= N <=
1,000)所有N个电线杆的地图，分别用1到N标号，每个电线杆都用一个有序数对(xi,yi)来表示(-100,000 <= x_i <=100000; -100,000 <= y_i <= 100,000)
有W (1 <= W <= 10,000)条电力线连接电线杆Pi与Pj (1 <= Pi <= N; 1 <= Pj <= N)
他需要从1号电线杆往N号电线杆输送电力（因为电力线路的损坏，可能需要通过一些中转的电线杆）
给出这N个电线杆和暴风雨后依然可用的电力线，请求出如果要恢复从1号电线杆到N号电线杆，所需要的连接的电力线长度的最小值，所有的电力线长度都可以用实数M (0.0 < M
<= 200,000.0)来表示。
下面左图是一个有9个电线杆和3条电力线的电力网，对于这个任务M=2.0，最好的恢复方案是连接4号与6号电线杆以及6号与9号电线杆。
After the storm Optimally reconnected
1
2
3
4
5
6
7
8
9
| 3 . . . 7 9 . . . . . 3 . . . 7 9 . . . . .
/
2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . .
/
1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . .
| |
0 1 . . . . . . . . . 0 1 . . . . . . . . .
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 |
总长度： 1.414213562 + 1.414213562 = 2.828427124 .
输入格式：
第一行，用空格分隔的两个整数N,W
第二行，一个实数M
第三行到第N+2行，每行包含两个用空格分隔的整数xi,yi
第N+3行到第N+2+W行，每行包含两个用空格分隔的整数Pi,Pj
输出格式：
仅一行，一个整数，为最小电力线长度1000倍的整数部分，如果恢复方案不存在，输出-1。
样例输入：
9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4
样例输出：
2828
