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