USACO 2014 JAN
一、题目概览
|
中文题目名称 |
滑雪场设计 |
滑雪降速 |
滑雪场评级 |
|
英文题目名称 |
skidesign |
slowdown |
skilevel |
|
可执行文件名 |
skidesign |
slowdown |
skilevel |
|
输入文件名 |
skidesign.in |
slowdown.in |
skilevel.in |
|
输出文件名 |
skidesign.out |
slowdown.out |
skilevel.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
比较方式 |
全文比较 |
全文比较 |
全文比较 |
二、运行内存限制
|
运行内存上限 |
256 M |
256 M |
256 M |
1.滑雪场设计{Bronze题1}
【问题描述】
农民约翰设计的滑雪场有N (1 <= N <= 1,000)块山，每块山的高度都是一个0 .. 100范围内的整数。滑雪场设计规范要求最高的山和最低的山的高度差不可以超过17，因此他可能需要降低或者抬高某些山，花X^2的费用可以使一块山的高度改变X的值，求最小花费。
【文件输入】
第一行为一个整数N。
接下来2..N+1行，每行一个整数，表示山的高度。
【文件输出】
输出共一行，一个整数，表示最小费用。
【输入样例】
5
20
4
1
24
21
【输出样例】
18
【样例说明】
保持高度为4,2,21的不变；将高度1改为4，费用为9；将高度24改为21，费用为9，共花费18的费用。
2. 滑雪降速{silver题1}
【问题描述】
奶牛贝西参加总路程为1000米的滑雪比赛，她的初始速度是1米每秒，当她第一次降速时速度变为1/2米每秒，第二次降速时变为1/3米每秒，以此类推。
现在给出两种降速的事件点：
T 17 （在17秒时降速）
D 10 （在10米的距离时降速）
现给出N(1 <= N <= 10,000)条事件点，请计算她的完成时间。将你的答案进行四舍五入到最接近的整数（0.5四舍五入到1）。
【文件输入】
第一行，一个整数N。
接下来N行每行一条事件点。格式为"T x" 或者 "D x"。
x是一个整数，并保证在这个事件点，她至少已经滑行了1米；
若多个时间是同时发生的，她也将降速多次。
事件点可能是无序的。
【文件输出】
一个整数，表示滑行的总时间。
【输入样例】
2
T 30
D 10
【输出样例】
2970
【样例说明】
以1米每秒的速度滑行了10米后，降度为1/2米每秒，花20秒时间滑行接下来的10米，然后降速为1/3米每秒，滑行剩下的980米花费2940秒。总花费时间为10 + 20 + 2940 = 2970。
3. 滑雪场评级{ Gold题3}
【问题描述】
滑雪场用一个M*N(1 <= M,N <= 500)的数字矩阵表示海拔高度，每个数字表示一个范围在0 .. 1,000,000,000的高度。有些格子被指定为起点，组织者想对这些起点做难度评级。
如果起点P点是一个难度级别为D的起点，则D必须是满足以下条件的一个最小值：
（1）从一个格子只能滑到相邻的格子；
（2）这两个格子的海拔差不超过D；
（3）至少能够到达T（1 <= T <= M*N）个格子（包括起点本身）。
【文件输入】
第一行，三个用空格隔开的整数，分别表示M，N和T。
接下来2.. M+1行，每行一个N个整数，表示海拔。
接下来M+2.. 2M+1行，每行一个整数0或者1，其中1表示该格子是一个起点。
【文件输出】
共一行，一个整数，所有起点的难度和。
【输入样例】
3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
【输出样例】
24
【样例说明】
左上角的格子是一起点，难度为4，右下角的格子是一个起点，难度为20。