北京101中学信息学竞赛阶段性测试1

北京101中学信息学竞赛阶段性测试1第一次测试前的提示：1、先抓会做的题目写，题目的难度级别和序号对你来说可不一定相符哦；2、注意数据范围；3、不要盲目地开始做一道题或者结束做一道题，有思路了才能开始做、确定能得分才能停止检查；4、当你觉得题目中的逻辑复杂时，不妨用笔和纸模拟程序进行演算，这样往往能很好地梳理思路；5、这只是一个阶段性测试，好的成绩代表你过去的努力；不理想的成绩可能仅仅是因为你对题目细节的忽视或者平时的偷懒，无需气馁，只要你肯，在暑假的训练中你一定可以“后来居上”；6、liyuchen6随时欢迎大家的提问人_人（6月6日之前我可能看不到邮件）；7、最后，祝大家考试愉快。、题目概览中文题目名称嘟嘟吉祥数嘟嘟打工嘟嘟死理性嘟嘟闯迷宫英文题目名称ghillieincomeunimodalcity可执行文件名ghillieincomeunimodalcity输入文件名ghillie.inincomeinunimodal.incity.in输出文件名ghillie.outincome.outunimodal.outcity.out每个测试点时限1秒1秒1秒1秒测试点数目10101010每个测试点分值10101010比较方式全文比较全文比较全文比较全文比较题目类型传统传统传统传统、提交源程序文件名对于Pascal语言ghillie.pasincome.pasunimodal.pascity.pas对于C语言ghillie.cincome.cunimodal.ccity.c对于C+语言ghillie.cppincome.cppunimodal.cppcity.cpp三、编译命令（不包含任何优化开关）对于Pascal语言fpcghillie.pasfpcincome.pasfpcunimodal.pasfpccity.pas对于C语言gcc-oghillieghillie.cgcc-oincomeincome.cgcc-ounimodalunimodal.cgcc-ocitycity.c对于C+语言g+-oghillieghillie.cppg+-oincomeincome.cppg+-ounimodalunimodal.cppg+-ocitycity.cpp四、运行内存限制运行内存上限32M32M32M32M注意事项：1.文件名(程序名和输入输出文件名)必须使用大写。2.C/C+中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。1.嘟嘟吉祥数(ghillie.pas/c/cpp)【问题描述】嘟嘟在暑假就要过18岁生日了最近嘟嘟正在兴奋地筹备着自己的生日party。嘟嘟觉得party要有活动才够火爆，而且活动最好要有点意义于是，嘟嘟想出了一个有趣的游戏：“猜嘟嘟吉祥数”！嘟嘟设计了这样的规则：第一轮，每个参与者将自己卡片上编号的各位数字进行平方后再相加得到一组新数，编号在这些数组中出现的参与者淘汰出局；第二轮，余下的参与者再将编号的各位数字进行立方相加得到一组新数，编号在这组数中出现的参与者再淘汰出局；第三轮，余下的参与者再将编号的各位数字进行4次相加得到一组新数，编号在这组数中出现的参与者再淘汰出局，依此类推，经过1轮后，仍留下来的参与者将获得圣诞特别礼物，卡片上的数即嘟嘟的专有吉祥数(假定party人数不超过200人)某嘟嘟的死党从嘟嘟处事先知道了这一繁琐的游戏，还被嘟嘟抓去当该游戏的最终裁判他觉得那些计算太可怕了，于是他想让你给他编个程序求出n轮后的吉祥数。【输入】输入文件ghillie.in有两行，第1行为1个正整数n(n8)，表示有n轮游戏，第二行是卡片上互不相同的编号。【输出】输出文件ghillie.out是1行，为剩下来的所有吉祥数，按从小到大顺数输出，每两个数之间有一个空格。输入输出样例】ghillie.inghillie.out1261224721232412321220144636722.嘟嘟打工(income.pas/c/cpp)【问题描述】这个暑假，嘟嘟终于年满18，可以打工挣钱啦(原谅嘟嘟这个无知的娃吧，其实满16岁就不算童工了)于是从暑假的某一天起，嘟嘟将连续工作N天(lv=Nv=100000)。每一天末嘟嘟都可以领取当天及前面若干天里没有领取的工资，但嘟嘟总共只有M(1v=Mv=N)次领取工资的机会。嘟嘟已经知道了在接下来的这N天里每一天自己可以赚多少钱。为了避免自己滥用零花钱，嘟嘟希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意：嘟嘟必须恰好领工资M次，且需要将所有的工资全部领走(即最后一天末需要领一次工资)。【输入】输入文件incomein有N+1行：第一行输入两个用空格隔开的正整数N和M，之下N行每行一个不超过10000正整数，依次表示每一天的薪水。【输出】输出文件income.out包含一个整数，即领取到的工资的最大值最小是多少。输入输出样例】income.inincome.out75500100400300100500101400输入输出样例说明】采取下面的方案可以使每次领到的工资不会多于500。这个答案不能再少了100400300100500101400每一天的薪水1234_Ax+l.An。例如，对于9的全排列，125798643是一个单峰排列，123456789也是一个单峰排列，但356298741就不是。嘟嘟觉得有点道理，毕竟在一个群体中有某种特点的事物都会有比较个性的性质。呃，可是吧，嘟嘟很怀疑“单峰排列”是否真的够“独特”，1n自然数的全排列中有几个是单峰排列呢？嘟嘟非常好奇。【输入】输入文件unimodal.in包含一个正整数n(nv=2000000000)。【输出】输出文件unimodal.out包含一个整数，即n的全排列中单峰排列的个数。由于这个数可能很大，因此你只需要输出它mod1234567的值。输入输出样例】unimodalinunimodalout34【输入输出样例说明】共有以下4种方案：1231322313214嘟嘟闯迷宫（city.pas/c/cpp）【问题描述】仙剑奇侠传五就要在暑假开卖啦！为此，仙剑的忠实粉丝嘟嘟打算在有仙剑5玩之前，重温一下仙剑的其它版本，最近，嘟嘟悲摧地正好重温到仙剑3外传-问情篇，即仙剑问路篇，其中的迷宫要多坑爹有多坑爹（唔，坑爹就是“十分不给力”的意思）今天嘟嘟又卡在迷宫的最后一重大门处：大门前的空中悬浮着许多长条型的银制烛台，按照坐标来划分的话，每个烛台上每隔一米有一根蜡烛。烛台的长度、漂浮的高度不等。但它们都平行于水平方向，而且两个端点都在整数米处。仙剑3问路篇的npc（一个路人）好心提醒说：“只要把每个烛台点亮至少两根蜡烛，那么迷宫的最后一重大门就可以打开了。（T_T游戏开发人员还有点良心。）于是嘟嘟开始念起咒语，点亮蜡烛。嘟嘟的祝福魔法一次可以点亮嘟嘟所在的那条垂直水平方向的直线上的所有蜡烛。可是由于烛台太多了，嘟嘟请你告诉她“最少点亮几颗蜡烛，就可以打开大门”。嘟嘟：“姚仙啊！仙5可不可以改改存档规则？！没方向感的走迷宫娃你伤不起啊！每次迷宫走不下去了都要回到起点记录处重来啊，有木有有木有啊”（姚仙是仙剑之父。唔这段其实可以无视）【输入】输入文件city.in有N+1行。第1行一个整数N表示烛台的数目，第2N+1行每行2个整数表示该烛台水平方向的起始坐标ai,bi（aivbi）。（Nv=10000Ov=ai,biv=1OOOO）【输出】输出文件city.out包含一个整数，即最少需要点亮的蜡烛数。输入输出样例】city.incity.out4436240247