USACO 2014 DEC SILVER
一、题目概览
|
中文题目名称 |
回程 |
马拉松 |
奶牛慢跑 |
|
英文题目名称 |
piggyback |
marathon |
cowjog |
|
可执行文件名 |
piggyback |
marathon |
cowjog |
|
输入文件名 |
piggyback.in |
marathon.in |
cowjog.in |
|
输出文件名 |
piggyback.out |
marathon.out |
cowjog.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
比较方式 |
全文比较 |
全文比较 |
全文比较 |
二、运行内存限制
|
运行内存上限 |
128 M |
128 M |
128 M |
1.回程{piggyback}
【问题描述】
Bessie 和 Elsie在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie要花费B单位的能量，Elsie要花费E单位的能量。
如果某次他们两走到同一个区域，Bessie 可以背着 Elsie走路，花费P单位的能量走到另外一个相连的区域，满足P<B+E。
相遇后，他们可以一直背着走，也可以独立分开。
【文件输入】
第一行，五个不超过40,000的正整数B, E, P, N和M。其中N表示区域的个数（区域分别用1..N编号，N>=3）,M表示各个区域之间连接的双向边的边数。一开始Bessie在区域1， Elsie在区域2，谷仓在区域N。
接下来M行，每行二个整数表示一条双向边连接两个区域，输入保证从区域1和区域2都能走到区域N。
【文件输出】
一行，一个整数，最小花费的单位能量。
【输入样例】
4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
【输出样例】
22
【样例说明】
Bessie从1到4，Elsie从2到3到4，然后一起从4到7到8。
2. 马拉松{marathon}
【问题描述】
Bessie参加城市马拉松比赛，要顺序经过N (3 <= N <= 500)个检查点，其中检查点1是起点，检查点N是终点。 Bessie尝试略过K(K < N)个检查点，以减少总路程，检查点1和检查点N不能被略过。两个检查点的距离是|x1-x2| + |y1-y2|。
【文件输入】
一行，两个整数N 和 K。
接下来N行，每行两个整数X和Y，(-1000 <= x <= 1000, -1000 <= y <= 1000)，表示N个检查点的坐标，这N个检查点是按顺序给出的，所以必须被按顺序经过。注意，同一个检查点可能会多次出现，当某次Bessie略过该检查点时，他只能略过当前的一次，而不是同时略过该检查点的所有出现次数。
【文件输出】
一行，一个整数，表示Bessie经过的总路程。
【输入样例】
5 2
0 0
8 3
1 1
10 -5
2 2
【输出样例】
4
【样例说明】
略过检查点(8, 3) and (10, -5)。
3.奶牛慢跑{ cowjog}
【问题描述】
有N (1 <= N <= 100,000)头奶牛在一个单人的超长跑道上慢跑，每头牛的起点位置都不同。由于是单人跑道，所有他们之间不能相互超越。当一头速度快的奶牛追上另外一头奶牛的时候，他必须降速成同等速度。我们把这些跑走同一个位置而且同等速度的牛看成一个小组。
请计算T (1 <= T <= 1,000,000,000)时间后，奶牛们将分为多少小组。
【文件输入】
第一行，两个整数N和T。
接下来N行，每行两个数，分别表示每头牛的初始位置P和初始速度S。其中（0<=P<=1000,000,000）、（1<=S<=1000,000,000）。输入数据按初始位置从小到大的顺序给出。
【文件输出】
一行，一个整数，表示小组数量。
【输入样例】
5 3
0 1
1 2
2 3
3 2
6 1
【输出样例】
3