USACO 2014 JAN
一、题目概览
|
中文题目名称 |
队伍平衡 |
滑雪录像 |
滑雪场建设 |
|
英文题目名称 |
bteams |
recording |
skicourse |
|
可执行文件名 |
bteams |
recording |
skicourse |
|
输入文件名 |
bteams.in |
recording.in |
skicourse.in |
|
输出文件名 |
bteams.out |
recording.out |
skicourse.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
比较方式 |
全文比较 |
全文比较 |
全文比较 |
二、运行内存限制
|
运行内存上限 |
256 M |
256 M |
256 M |
1.队伍平衡{Bronze题3}
【问题描述】
农民约翰将参赛的12头牛分成4组，每组3头，每头牛的技能值是1 到 1,000,000之间的一个整数。他希望每组的技能总和值尽量平衡，即技能总和最大的组和技能总和最小的组的差距尽量地小。请计算这个最小差距的绝对值。
【文件输入】
第1..12行，每行一个整数，表示牛的技能值。
【文件输出】
输出共一行，一个整数，表示最小差距的绝对值。
【输入样例】
1
2
3
4
5
6
7
8
9
10
11
12
【输出样例】
1
【样例说明】
(12,1,7), (9,8,3),(10,5,4), (11,2,6)。最大20，最小19。
2. 滑雪录像{silver题3}
【问题描述】
冬奥会的电视时刻表包含N (1 <= N <= 150)个节目，每个节目都有开始和结束时间。农民约翰有两台录像机，请计算他最多可以录制多少个节目。
【文件输入】
第一行，一个整数N。
接下来N行每行两个整数，表示一个节目的开始和结束时间，范围为0..1,000,000,000。
【文件输出】
一个整数，表示最多可以录制的节目数量。
【输入样例】
6
0 3
6 7
3 10
1 5
2 8
1 9
【输出样例】
4
【样例说明】
第1台录制节目1和3，第2台录制节目2和4。
3. 滑雪场建设{ Gold题2}
【问题描述】
滑雪场的设计图是一个M*NM x N (1 <= M,N <= 100)的矩阵，每个格子里用一个字母R（表示粗糙）或者S（表示平整）。
比如：
RSRSSS
RSRSSS
RSRSSS
农民约翰的拖拉机每次可以将一块B*B (B <= M, B <= N)的区域全部标记B*B (B <= M, B <= N)的R或者S，他希望B能够尽量地大。一个格子可以被多次标记，下一次标记能够覆盖前一次标记，每个格子可以都至少被标记一次。
【文件输入】
第一行，两个用空格隔开的整数，分别表示M，N。
接下来2.. M+1行，每行一个M个符号，R或者S。表示用标记成的目标状态。
【文件输出】
共一行，一个整数，表示B的最大值。
【输入样例】
3 6
RSRSSS
RSRSSS
RSRSSS
【输出样例】
3
【样例说明】
首先将第1到第3列全部标记为R,然后第2到第4列全部标记为S，接下来将第3到5列全部标记为R，最后将第4到6列全部标记为S。