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