L3-024 Oriol和David
Statement
Metadata
- 作者: 李文新
- 单位: 北京大学
- 代码长度限制: 16 KB
- 时间限制: 2000 ms
- 内存限制: 256 MB
Oriol 和 David 在一个边长为 16 单位长度的正方形区域内，初始位置分别为（7, 7）和（8, 8）。现在有 20 组、每组包含 20 个位置需要他们访问，位置以坐标（x, y）的形式给出，要求在时间 120 秒内访问尽可能多的点。（x和y均为正整数，且0 ≤ x < 16，0 ≤ y < 16）
注意事项： * 针对任意一个位置，Oriol或David中的一人到达即视为访问成功； * Oriol和David必须从第 1 组位置开始访问，且必须访问完第 i 组全部20个位置之后，才可以开始第 i + 1 组 20 个位置的访问。同组间各位置的访问顺序可自由决定； * Oriol和David在完成当前组位置的访问后，无需返回开始位置、可以立即开始下一组位置的访问； * Oriol和David可以向任意方向移动，移动时速率为 2 单位长度/秒；移动过程中，无任何障碍物阻拦。
输入格式
输入第一行是一个正整数 T (T ≤ 10)，表示数据组数。接下来给出 T 组数据。
对于每组数据，输入包含 20 组，每组 1 行，每行由 20 个坐标组成，每个坐标由 2 个整数 x 和 y 组成，代表 Oriol 和 David 要访问的 20 组 20 个位置的坐标；0 ≤ x < 16，0 ≤ y < 16，均用一个空格隔开。
输出格式
每组数据输出的第一行是一个整数N，代表分配方案访问过的位置组数；
接下来的N组每组的第一行包含两个整数 Ba 和 Bb，分别代表每组分配方案中 Oriol 和 David 负责访问的位置数，第二行和第三行分别包含 Ba 和 Bb 个整数 i，分别代表 Oriol 和 David 负责访问的位置在组内的序号（从0开始计数）。
0 ≤ N ≤ 20，0 ≤ Ba ≤ 20，0 ≤ Bb ≤ 20，0 ≤ i ≤ 19。
输入样例
1
5 5 3 13 8 7 13 6 6 11 2 0 1 14 9 15 8 9 3 12 4 6 2 10 2 5 4 9 4 1 15 0 11 4 10 0 15 5 10 14
1 0 14 8 0 7 6 8 4 12 12 8 9 8 10 14 9 4 13 4 9 1 2 1 0 2 11 10 7 15 9 6 13 11 3 5 4 5 10 7
7 3 8 13 15 0 5 4 2 8 7 14 4 13 11 1 8 15 4 5 4 7 7 10 6 7 13 4 6 2 9 13 1 12 10 7 10 5 5 11
5 8 12 12 11 5 12 9 2 2 11 15 5 14 0 0 14 0 2 5 7 3 10 1 2 8 4 2 4 8 9 14 1 11 1 9 15 7 3 3
1 9 10 14 7 3 15 5 5 15 3 2 12 11 8 10 3 3 11 5 7 4 6 11 6 1 4 10 11 13 12 4 3 4 1 3 7 5 13 11
3 11 9 8 12 9 14 10 11 13 5 5 4 11 1 12 13 2 10 14 5 15 10 15 11 0 3 6 7 11 4 9 15 0 12 14 10 10 13 11
10 4 9 12 0 13 6 6 7 10 11 15 6 14 1 2 4 9 8 5 4 0 13 11 5 3 13 3 9 8 2 4 13 14 12 12 14 2 8 15
2 8 4 9 13 10 8 5 2 13 12 6 4 4 10 6 14 13 11 5 12 1 6 0 11 2 8 15 12 4 13 8 8 2 9 7 7 13 0 9
0 0 4 0 2 3 10 2 7 3 9 4 2 13 11 11 1 8 11 15 11 2 8 11 10 15 7 9 13 15 15 10 1 2 11 9 14 6 5 5
2 13 6 8 7 14 8 5 15 14 5 6 4 10 14 12 3 14 0 5 4 1 0 14 13 14 12 5 5 9 1 2 2 12 4 8 1 15 7 11
10 5 15 7 6 8 11 10 7 13 14 0 12 2 9 12 4 5 3 8 8 13 7 12 15 15 12 9 15 6 14 3 9 6 15 12 7 9 4 15
0 10 6 2 3 2 6 3 14 6 10 13 3 10 15 9 10 0 7 0 14 15 1 2 13 9 11 11 10 3 6 13 0 14 11 2 9 8 15 5
3 9 13 11 1 1 0 9 5 4 4 9 4 13 10 1 12 11 4 2 0 4 1 7 4 10 4 0 2 1 2 0 13 2 11 10 0 5 15 3
15 11 8 1 12 5 8 5 7 5 7 7 2 4 0 4 7 3 12 6 9 15 5 12 14 11 15 10 8 11 4 10 4 14 13 10 4 4 2 12
9 12 15 13 0 12 0 14 3 1 10 15 15 11 1 12 3 0 5 2 15 10 8 4 9 1 8 0 1 13 2 7 12 13 14 10 6 0 13 15
13 7 14 15 9 4 8 2 7 3 7 11 2 13 5 0 13 5 4 0 12 2 3 2 11 15 9 2 9 7 3 7 4 5 14 5 14 12 9 13
12 11 2 14 2 6 6 12 5 15 13 11 2 0 9 13 7 1 7 11 4 4 2 10 0 8 5 3 6 13 2 7 2 15 6 8 3 5 8 11
12 5 9 9 4 14 3 2 14 2 2 1 9 11 8 10 2 14 12 15 0 13 4 7 0 0 0 6 0 1 4 13 4 3 3 10 15 2 10 10
11 15 8 5 6 15 9 8 2 7 15 14 1 10 14 6 13 6 0 15 4 1 3 12 7 8 12 4 0 10 7 10 0 14 13 5 11 1 15 6
1 12 13 14 6 12 9 0 6 8 3 15 5 4 4 2 15 10 3 6 13 12 8 4 15 3 1 5 7 1 6 14 8 6 2 6 11 3 4 4
输出样例
2
10 10
1 2 3 4 5 6 7 8 9 0
11 12 13 14 15 16 17 18 19 10
1 19
1
0 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 10
注意：样例只代表格式，不具有特别含义。
评分方式
本题按照你给出的方案的优良程度评定分数。
具体评分规则如下：
- 本题所有数据点输入均为一样的数据；
- 评分时，假定输入有 X 组数据，则你的评分答案为你的程序在所有 X 组数据中答案的平均值；
- 例如，你对 3 组数据，分别访问了 3 个、5 个、8 个点，则你的评分答案为 5.33333…
- 特别的，如果你输出的答案中有任意一组不合法，则你的评分答案恒定为 0；
- 输出方案行走超过 120 秒仍然合法，答案计算时只计算 120 秒内的部分；
- 评测时，从 0 开始的测试点的标准答案依次增大，只有评分答案超过标准答案时，你才可以得到对应测试点的分数。
不合法的情况如下： * 输出格式不正确； * 重复访问自己已访问的点；（但可以经过） * 访问不存在的点。
部分评分标准答案如下： * 第 0 号点：20；（即需要访问平均 20 个点才可以获得该点分数） * 第 1 号点：70；（同上） * 第 2 号点：90； * 第 7 号点：150。