春季函授A层次测试题.doc

2011江苏省信息学奥赛集训队第一轮集训暨春季函授A层次测试题江苏省金湖中学 张厚林考试说明：1、 共4个题目，每题100分，满分400分。2、 考试时间：3个小时。3、 如无特殊说明，每个题目的时限都是1秒。4、 请严格按照题目的要求书写程序名、输入输出文件名。采用NOIP自动评测系统测试。5、 每人提交一个文件夹，名字为：A+自己的姓名。里面只能有最多4个源程序。1.月月的自然数 (natural.pas/c/cpp)问题描述：同学们一直盼望的JSOI2011夏令营即将于7月13日在江苏省金湖中学开营了，最近因忙于文化课期末考试复习，不少同学好久没巩固信息学奥赛内容了。月月为了检测自己的水平是否退步，她用计算机产生了n个随机自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在她很想知道一共产生了多少个不相同的自然数且这些自然数各出现的次数，并按照自然数从小到大的顺序输出统计结果。输入文件（natural.in）： 输入文件包含n+1行： 第1行是整数n，表示产生的自然数的个数。第2n+1行每行一个自然数。输出文件(natural.out)：输出文件包含m+1行（m为n个自然数中不相同数的个数），第1行是一个整数m。第2m+1行，按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。样例：输入：8242451002100输出：42 34 25 1100 2数据说明：40%的数据满足：1=n=100080%的数据满足：1=n=50000100%的数据满足：1=n=200000，每个数均不超过1 500 000 000（1.5*109）2.CBC流感病毒（virus.pas/c/c+）问题描述：印度的不少山区最近因为连续的暴雨导致山体滑坡和泥石流，这还不是最糟糕的事情。让印度联邦政府更为头疼的是因为连续的阴雨天气和自然灾害，导致印度出现一种叫做CBC的流感病毒。这种病毒类似于SAS，但它的传播速度更快，传播途径也更为广泛，但是感染上这种流感病毒的人会在次日痊愈。 在灾区有一所中学，这所小学一共有n个学生。这n个学生里一共有m对朋友关系。在CBC病毒发作期，每个健康学生都要看望当天他生病的朋友（如果有的话），并在第二天被传染上CBC病毒（除非他在免疫期内）；每个生病的学生在第二天都会痊愈，并在这一天具有免疫性。从第三天起，看望生病的朋友将再次使他染上流感。初始时（第一天），只有一个学生患有CBC流感病毒。试问多少天后CBC流感病毒会自动结束。输入文件（virus.in）： 第一行输入两个正整数n和m。 接下来m行每行两个正整数x,y，表示编号为x的学生和编号为y的学生是一对朋友。输入数据保证每一对朋友关系只描述一次。 最后一行输入一个正整数，代表初始时患有CBC流感病毒的学生的编号。输出文件(virus.out)： 如果CBC流感病毒永远不会结束，请输出-1，否则输出多少天后流感病毒会结束。 答案保证不超过2 000 000 000。样例：输入：4 41 22 33 42 41输出：3样例说明： 第一天1号学生生病，2号学生访问他； 第二天2号学生生病，其它三个学生访问他，由于1号处于免疫期，未患CBC流感病毒； 第三天3、4号学生生病，2号学生访问他们。第四天3、4号学生痊愈，流感病毒结束。数据说明：n,m=100 000。3.麻烦的干草打包机（baler.pas/c/c+）问题描述：ZHL新买的干草打包机的内部结构大概算世界上最混乱的了，它不象普通的机器一样有明确的内部传动装置，而是，N (2 = N = 1050)个齿轮互相作用，每个齿轮都可能驱动着多个齿轮。ZHL记录了对于每个齿轮i，记录了它的3个参数：X_i，Y_i表示齿轮中心的位置坐标(-5000 = X_i = 5000; -5000 = Y_i = 5000)；R_i表示该齿轮的半径(3 = R_i = 800)。驱动齿轮的位置为0,0，并且ZHL也知道最终的工作齿轮位于X_t,Y_t。驱动齿轮顺时针转动，转速为10,000转/小时。你的任务是，确定传动序列中所有齿轮的转速。传动序列的定义为，能量由驱动齿轮传送到工作齿轮的过程中用到的所有齿轮的集合。对能量传送无意义的齿轮都应当被忽略。在一个半径为Rd，转速为S转/每小时的齿轮的带动下，与它相接的半径为Rx的齿轮的转速将为-S*Rd/Rx转/小时。S前的负号的意思是，一个齿轮带动的另一个齿轮的转向会与它的转向相反。ZHL只对整个传动序列中所有齿轮速度的绝对值之和感兴趣，你的任务也就相应转化成求这个值。机器中除了驱动齿轮以外的所有齿轮都被另外某个齿轮带动，并且不会出现2个不同的齿轮带动同一个齿轮的情况。输入文件（baler.in）：第1行有3个用空格隔开的整数：N，X_t，Y_t第2n+1行: 第i+1描述了齿轮i的位置及半径：X_i，Y_i，以及R_i输出文件(baler.out)：输出仅一行，为所有在传动中起到作用的齿轮转速的绝对值，包括驱动齿轮和工作齿轮。只需要输出答案的整数部分。样例：输入:4 32 540 0 100 30 2032 54 20-40 30 20输入说明:机器里一共有4个齿轮，位于0,0的是半径为10的驱动齿轮，它带动了位于0,30的，半径为20的某个齿轮。这个齿轮又间接带动了位于32,54，半径为20的工作齿轮，以及一个位于-40,30，半径同样为20的冗余的齿轮。输出:20000输出说明:齿轮 位置 半径 转速1 (0,0) 10 10,0002 (0,30) 20 -5,0003 (32,54) 20 5,000 -齿轮转速绝对值之和:20,0004.打砖块(game.pas/c/cpp)问题描述：萱萱很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下： 在刚开始的时候，有n行*m列的砖块，萱萱有k发子弹。萱萱每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。 如图所示： 某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者萱萱没有子弹了，游戏结束。 萱萱在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。萱萱想知道在这次游戏中她可能的最大得分，可是这个问题对于她来说太难了，你能帮帮她吗？输入文件（game.in）： 第一行有3个正整数，n，m，k。表示开始的时候，有n行*m列的砖块，萱萱有k发子弹。 接下来有n行，每行的格式如下： f1 c1 f2 c2 f3 c3 fm cm 其中fi为正整数，表示这一行的第i列的砖，在打碎以后的得分。ci为一个字符，只有两种可能，Y或者N。Y表示有一发奖励的子弹，N表示没有。 所有的数与字符之间用一个空格隔开，行末没有多余的空格。输出文件(game.out)： 仅一个正整数，表示最大的得分。样例：输入：3 4 29 N 5 N 1 N 8 N5 N 5 Y 5 N 5 N6 N 2 N 4 N