NOI2012第一试

1、第29届全国青少年信息学奥林匹克竞赛CCFNOI2012第一试竞赛时间：2012年7月30日8:00-13:00题目名称随机数生成器骑行川藏魔幻棋盘目录randombicyclingchess可执行文件名randombicyclingchess输入文件名random.inbicycling.inchess.in输出文件名random.outbicycling.outchess.out每个测试点时限1秒1秒5秒内存限制512MB512MB512MB测试点数目202010每个测试点分值5510是否有部分分否否否题目类型传统型传统型传统型是否有附加文件无无无提交源程序须加后缀对于C+语言random

2、.cppbicycling.cppchess.cpp对于C语言random.cbicycling.cchess.c对于Pascal语言random.pasbicycling.paschess.pas注意：最终测试时，所有编译命令均不打开任何优化开关。第29届全国青少年信息学奥林匹克竞赛第一试随机数生成器第 #页共7页第29届全国青少年信息学奥林匹克竞赛第一试随机数生成器第 页共7页第29届全国青少年信息学奥林匹克竞赛第一试随机数生成器第 页共7页第29届全国青少年信息学奥林匹克竞赛第一试随机数生成器第 #页共7页随机数生成器【问题描述】栋栋最近迷上了随机算法，而随机数生成是随机算法的基础。栋栋

3、准备使用线性同余法(LinearCongruentialMethod)来生成一个随机数列，这种方法需要设置四个非负整数参数皿,c,X,按照下面的公式生成出一系列随机数:X=(aXc)modm其中mod表示前面的数除以啲余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。用这种方法生成的序列具有随机序列的性质,因此这种方法被广泛地使用,包括常用的C+和Pascal的产生随机数的库函数使用的也是这种方法。栋栋知道这样产生的序列具有良好的随机性,不过心急的他仍然想尽快知道X是多少。由于栋栋需要的随机数是0,1，,Q-1之间的，他需要将X除以gnn取余得到他想要的数，即Xmod，你只需要

4、告诉栋栋他想要的数暂mod是多少就可以了。【输入格式】输入文件random.in中包含6个用空格分割的整数九和矽其中a,X0是非负整数，m,n,g是正整数。【输出格式】输出到文件random.out中，输出一个数，即Xmod。g【样例输入】1187153样例输出】2样例说明】k012345146078v的前几项依次是:因此答案为乳mod=8mod=3。数据规模与约定】测试点编号nm,a,c,X0m,a性质g1n100m,a,c,X0100m为质数2n1000m,a,c,X01000m为质数3n104m,a,c,X0104m为质数4n104m,a,c,X0104m为质数5n105m,a,c,X0

5、104m与a-1互质6n105m,a,c,X0104m与a-1互质7n105m,a,c,X0104m与a-1互质8n106m,a,c,X0104/9n106m,a,c,X0109m为质数10n106m,a,c,X0109/a10811n1012m,a,c,X0109m为质数12n1012m,a,c,X0109m为质数13n1016m,a,c,X0109m与a-1互质14n1016m,a,c,X0109m与a-1互质15n1016m,a,c,X0109/16n1018m,a,c,X0109/17n1018m,a,c,X0109/18n1018m,a,c,X01018m为质数19n1018m,a,

6、c,X01018m与a-1互质20n1018m,a,c,X01,m1,a0，c0，X00，g1。第29届全国青少年信息学奥林匹克竞赛第一试骑行川藏第 页共7页第29届全国青少年信息学奥林匹克竞赛第一试骑行川藏第 页共7页骑行川藏【问题描述】蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车

7、与地面的摩擦力影响）。某一天他打算骑殿路，每一段内的路况可视为相同：对于第段路，我们给出有关这段路况的3个参数.sk.M，其中表示这段路的长度，7表示这段路的风阻系数，M表示这段路上的风速（q0表示在这段路上他遇到了顺风，反之则意1I味着他将受逆风影响）。若某一时刻在这段路上骑车速度为，则他受到的风阻大小为=kj（u-叩2（这样若在长度为的路程内保持骑行速度不变，则他消耗能量（做功）E=kj（u一冬）2S）。设蛋蛋在这天开始时的体能值是请帮助他设计一种行车方案，使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间是多少。【输入格式】输入文件bicycling.in中的第一行包含一个正整

8、数惰口一个实数沪分别表示路段的数量以及蛋蛋的体能值。接下来布分别描述阶路段，每行有3个实数/严;，分别表示第段路的长度，风阻系数以及风速。【输出格式】输出到文件bicycling.out中，输出一个实数T表示蛋蛋到达目的地消耗的最短时间，要求至少保留到小数点后6位。【样例输入】31000010000105200001585000056【样例输出】12531.34496464【样例说明】一种可能的方案是：蛋蛋在三段路上都采用匀速骑行的方式，其速度依次为5.12939919,8.03515481,6.17837967。【评分方法】本题没有部分分，你程序的输出只有和标准答案的差距不超过0.00000

9、1时，才能获得该测试点的满分，否则不得分。【数据规模与约定】对于10%勺数据，N=1；对于40%勺数据，N2；对于60%勺数据，N100；对于80%勺数据，N1000；对于所有数据，N10000，EU108，0st100000,0k.15，-100v：100。数据保证最终的答案不会超过10（。1I【提示】必然存在一种最优勺体力方案满足：蛋蛋在每段路上都采用匀速骑行勺方式第29届全国青少年信息学奥林匹克竞赛第一试魔幻棋盘.第 页共7页第29届全国青少年信息学奥林匹克竞赛第一试骑行川藏第 #页共7页魔幻棋盘【题目描述】将要读二年级的小Q买了一款新型益智玩具一一魔幻棋盘，它是一个行妙U的网格棋盘,每

10、个格子中均有一个正整数。棋盘守护者在棋盘的第行第Y列（行与列均从开始编号）并且始终不会移动。棋盘守护者会进行两种操作：（a）询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。（b）修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对1993032次4询问后会得到一个惊喜噢！”。小Q十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证1

11、00%的正确率。为了简化问题，你的程序只需要完成棋盘守护者的次操作，并且问题保证任何时刻棋盘上的数字均为不超过62-1的正整数。【输入格式】输入文件chess.in中的第一行为两个正整数N,M,表示棋盘的大小。第二行为两个正整数境，表示棋盘守护者的位置。第三行仅有一个正整数T表示棋盘守护者将进行次操作。接下来T行，每行有Mb正整数，用来描述初始时棋盘上每个位置的数。接下来行,按操作的时间顺序给出次操作。每行描述一次操作，以一个数字0或1开头：若以数字0开头，表示此操作为询问，随后会有四个非负整数1xy1,%2,y2，表示询问的区域是以棋盘守护者的位置为基础向上扩展尤行，向下扩展2行,向左扩展，

12、向右扩展2列得到的矩形区域（详见样例）。若以数字1开头，表示此操作为修改，随后会有四个正整数1xy1,%2,y2和一个整数c表示修改区域的上、下边界分别为第样勺行，左、右边界分别为第1yy2列（详见样例），在此矩形区域内的所有数统一加上c（注意可能为负数）。【输出格式】输出到文件chess.out中。对于每次询问操作，每行输出一个数，表示该区域内所有数的最大公约数。【输入样例】221146121824TOC o 1-5 h z0001011112612122600011【输出样例】66样例说明】初始状态第一次操作后第二次操作后第三次操作后第四次操作后61261212181218121818241824182424302430对于第一、第四次操作（查询操作）后，加粗部分表示查询区域。