为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
CTSC2007
来自NOCOW
| 本文应该包括一些关于这项活动的具体内容，而不只是发题目。题目应该用子页面。 |
== IOI2007中国国家队选拔赛北京 ==
2007-5-14
IOI 2007中国国家队选拔赛
CTSC 2007
竞赛时间：2007年5月14日上午 8:15-13:15
题目名称 矩阵 挂缀 激光坦克
目录 matrix pendant tank
可执行文件名 matrix pendant tank
输入文件名 matrix.in pendant.in tank1.in~tank10.out
输出文件名 matrix.out pendant.out tank1.out~tank10.out
每个测试点时限 3s 4s N/A
测试点数目 10 10 10
每个测试点分值 10 10 10
是否有部分分 有 有 有
题目类型 传统 传统 提交答案
提交源程序须加后缀
对于
Pascal语言 matrix.pas pendant.pas N/A
对于
C 语言 matrix.c pendant.c N/A
对于
C++ 语言 matrix.cpp pendant.cpp N/A
注意：最终测试时，所有编译命令均不打开任何优化开关
矩阵
【问题描述】
给定一个整数 D，n行 m列的实数矩阵 A，其第 i行第 j列的元素是 aij，且 0
≤ aij ≤ D (1≤i≤n, 1≤j≤m）。希望你能够由此提供一个 n行 m列的 01矩阵
B，第 i行第 j列的元素是 bij(1≤i≤n, 1≤j≤m），bij非 0即 1。
对于给定的 A矩阵和你提供的 B矩阵，可以求出
.
.
..
.
..
.
a
ij
D
n
∑
(bij
.
)
.
.
.
.
max
1≤
j≤m
i
.
1
=
.
p
1
=
max
；
..
.
..
.
D
m
.
.
.
.
a
ij
=
Σ1
(bij
)
.
max
1≤i≤n
..
..
.
.
j
..
.
(
D
)
+
+
+
a
a
a
a
i, j
i
j
i, j
i
j
..
.
.
..
.
1, 11,1
1, 11,1
.
在不同的测试例子中，我们希望提供的 B矩阵能使 p1或者 p2尽量小。
【输入文件】
输入文件 matrix.in第一行有一个整数 c，有两种取值： c = 1表示我们的最小化目标是 p1，c = 2则表示希望 p2尽量小。
第二行有 3个整数 D, n, m，相邻的两个数字间用一个空格隔开， D的含义如上文所述，n和 m分别表示 A矩阵的行数和列数。
以下有 n行，每行 m个实数，描述 A矩阵。其中第 i行第 j列的实数表示 aij，相邻的数字用一个空格隔开。
【输出文件】
输出文件 matrix.out中仅包含一个 n行 m列的 01矩阵 B，表示你求出的使pc尽量小的答案。其中第 i行第 j列的数字表示 bij。相邻的整数之间用一个空格
隔开。
【样例输入1】
7 3 4
1 6 4 6
7 0 3 3
2 5 1 5
b
bi
b
bi
.
+
+
+
p
=
max
j
j
2
i, j
i, j
1<i≤n,1<j≤m
..
.
第 2页共 8页
�
IOI2007中国国家队选拔赛北京 2007-5-14
【样例输出1】
0 1 0 1
1 0 1 0
0 1 0 1
【样例输入2】
2
7 3 4
1 6 4 6
7 0 3 3
2 5 1 5
【样例输出2】
0 1 0 1
1 0 1 0
0 1 0 1
【样例说明】
在样例 1中 p1 = 37 ≈0.4286，而在样例 2中，p2 = 57 ≈ 0.7143。
【评分标准】
如果你的程序输出非法（不是一个合法的 n行 m列的 01矩阵），则在该测试
点你的得分为 0。否则我们将计算出和你的程序输出相对应的 pc，设 Total是测
试点的总分，而你在该点的得分是 YourScore。
若 c = 1，有 YourScore =
Round [max{1.5 .max{ p1,1},0}*2* Total ]
若 c = 2，有 YourScore =
Round [max{2 .max{ p2,1.5},0}*2* Total ]
其中 Round[x]表示距离 x最近的整数（即四舍五入）。
【数据规模】
100%的数据中，2 ≤ n, m ≤ 700，1 ≤ D ≤ 1 000 000 000；
40%的数据中，c = 1；
60%的数据中，c = 2。
第 3页共 8页
�
IOI2007中国国家队选拔赛北京 2007-5-14
挂缀
【问题描述】
“珠缀花蕊，人间几多酸泪”……
挂缀在很早就被人们作为一种装饰品，垂坠的风韵，华丽摇曳的摆动，展现出一种与众不同的优雅与高贵。而我们的主人公小 Q，正想买一条漂亮的挂缀放在寝室里作为装饰。
挂坠的构成，是由若干粒缀珠相互连接而成。每一个缀珠由三部分组成：分别是珠子、珠子上方的连接环与珠子下方的挂钩（如下图）。我们可以简单的认为从上往下数的第i个缀珠是将它的连接环套在其上方（也就是第i-1个）缀珠的挂钩之上（第一个除外）。小Q想买一根足够长的挂缀，这样显得更有韵味.
然而商店的老板告诉小 Q，挂缀是不可能做到任意长的，因为每一个珠子都受到重力作用，对其上方的挂钩有一定的拉力，而挂钩的承受能力是有限的。老板还告诉小
Q，他一共拥有N个珠缀（假设每一个珠缀都很漂亮，小Q都很喜欢），每个珠缀都有其各自的重量与承受能力。一个挂缀是稳定的，当且仅当对于其上的每一个珠缀，它下方所有珠缀的重量和（不包含自身）不超过其挂钩的承受能力。
小Q希望她的挂缀尽量长，你能帮她计算出最长可能的稳定挂缀么？当然，如果有多个可选方案，小Q希望总重量最小的。
【输入文件】
输入文件
pendant.in第一行包含一个正整数N，表示商店拥有的珠缀数目。
接下来N行，每行两个整数(Ci , Wi)，分别表示第i个珠缀的承受能力与重量。
【输出文件】
输出文件
pendant.out包行两行。第一行包含一个整数
L，表示可以找到的最
长稳定挂缀长度。第二行包含一个整数
W，表示可以找到的长度为
L的稳定挂
缀中的最小重量和。
第
4页共
8页
�
IOI2007中国国家队选拔赛北京 2007-5-14
【样例输入】
4
3 5
5 1
3 2
4 6
【样例输出】
3
8
【评分标准】
每一个测试点单独评分，对于每一个测试点：
..如果挂缀长度
L与答案一致，且最小重量和W也正确，则得10分。
..如果挂缀长度L与答案一致，而最小重量和W与答案不一致，该测试点则得4分。
..否则得0分。
【数据规模】
对于30%的数据，N ≤ 10000；
对于100%的数据，N ≤ 200000；
对于所有的数据，Wi, Ci不超过231。
第5页共8页
�
IOI2007中国国家队选拔赛北京 2007-5-14
激光坦克
【问题描述】
刘刘小朋友最近迷上一款PC上的益智小游戏，名叫激光坦克。有些关卡实在是太难了，他在鏖战了若干个小时之后，决定来请教作为编程高手的你。刘刘希望你能帮他写一个程序来通关。
原游戏太复杂，你在这里只需要解决简化了的版本。在游戏的战场上（可以看作一个平面），有N个敌方的坦克，我们可以认为单个坦克的大小相对于整个战场很小，是一个点。同时战场上还有M个栅栏一样的障碍物，每个都可以看作是一条线段，这些线段不会相交，也不会有公共端点。你的任务自然是要摧毁所有的敌方坦克，而你手上所拥有的武器就是一个激光发射器。
激光发射器可以放置在战场的任何位置（但不能放置在障碍物所在的线段上），一旦放置之后就不能再移动。它可以向任何方向发射激光，激光沿直线运动，不能横穿栅栏（但是可以紧贴着栅栏经过）。当激光碰到栅栏的时候会发生反射，此时可以把栅栏看作镜子，反射规则和镜面反射相同。
经过一次反射的效果特殊情况：紧贴栅栏而过
任何被激光打到（即在激光的运动路径上）的敌方坦克都会被立即摧毁，我们称从发射源开始，沿着这条激光运动直到目标坦克的路径为激光攻击路径。但激光在每次被栅栏反射的时候都会有能量的衰减，如果被反射的次数超过K次，激光就不会再具有摧毁敌方坦克的能力了。
现在刘刘希望你能够找到一个合适的位置安放激光发射器来摧毁所有的坦克，并且设计摧毁每个敌方坦克需要的激光方向。同时，他希望在满足摧毁所有敌方坦克的前提下，最长的激光攻击路径长度尽量短，因为只有这样才能拿到比较高的通关分数。
本题是提交答案式题目，分为10个测试数据，分别存储在：tank1.in~tank10.in，选手不需要提交程序，只需要针对每个数据给出相应的输出文件，
tank1.out~tank10.out即可。
【输入文件】
每个输入文件第一行包含两个实数
C1，C2。它们仅仅参与该测试点的分数计算，与题目本身无关。
第二行包含三个整数，分别为N、M和K。他们的意义已经在题目中说明了接下来N行，每行两个实数Xi，Yi，表示每个敌方坦克i的X坐标值和Y坐标值。
随后的M行，每行四个实数X1i，Y1i，X2i，Y2i。表示每条栅栏障碍物的两个端点的坐标。
【输出文件】
输出文件第一行为Ans，表示最长的激光路径的长度。
第二行为两个实数AnsX，AnsY。表示激光源摆放的位置。
以下N行，每行两个实数Sxi，Syi。表示为了摧毁敌方坦克i，需要从激光源发出一条射向点(Sxi, Syi)的直线。即激光的方向为(AnsX,AnsY)..(Sxi,Syi)，要求输出点(AnsX, AnsY)与点(Sxi, Syi)的距离要超过0.1。
【样例输入】
1 2 2 1
-4 -4
4 0
1 1 1 -1
-2 2 4 2
【样例输出】
5.6569
0 0
-4 -4
2 2
（上面的例子中，两条攻击路径长度都是42 ）
【评分标准】
每个数据的满分是10分。
对于每个数据，如果出现下列情况，则程序得0分：
1．没有输出文件
2．输出不合法
3．有敌方坦克没有被摧毁，即给出的不是可行解。
否则你的得分将按照下面的公式计算
10 Ans ≤
Best
.
.
Score =.
C1 Ans ×C2 >
Best
..(Best .
C ×
Ans ) (10 .
C ) .
C2×
Ans ≤
Best <
Ans
.
21
C1 +.
×.
..
(1.
C2) ×
Ans .
.
【调试工具】
本题提供了一个检测程序（check）来帮助选手调试，具体使用方法是：
./check X
X表示测试点的编号，为1~10。
如果你的输出文件给出的答案正确，你会得到如下信息：
Your output is correct with striking distance Ans, given in the file!
Ans是你的输出中给出的答案。
如果你的答案错误，会得到这样的信息：
our output is not correct!
The tank No.I is not destroyed!
并提示你，输入中第I个坦克并没有被摧毁。
如果你的输出文件的格式不正确，或者输入文件被更改，则不保证check输出的信息有意义。
注意：我们保证在调试中被check通过的输出，能够在正式测试时被认为是正确的输出文件。
为了避免可能发生的误差问题，check中使用的误差级别在10-3左右。即只要坦克足够接近激光路径，就会被认为能够被摧毁。
