2015年合肥市瑶海区信息学竞赛(小学组)试题

第1页共5页2015年合肥市瑶海区信息学竞赛小学组（请选手务必仔细阅读本页内容）一、题目概况中文题目名称子集问题祭祀打鼹鼠分糖游戏英文题目与子目录名subsetsacmolecandy可执行文件名subsetsacmolecandy输入文件名subset.insac.inmole.incandy.in输出文件名subset.outsac.outmole.outcandy.out每个测试点时限1秒1秒1秒1秒测试点数目10101010每个测试点分值10101010附加样例文件有有有有结果比较方式全文比较（过滤行末空格及文本回车）题目类型传统传统传统传统二、提交源程序文件名对于C++语言subset.cppsac.cppmole.cppcandy.cpp对于C语言subset.csac.cmole.ccandy.c对于pascal语言subset.passac.pasmole.pascandy.pas三、运行内存限制内存上限128M128M128M128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。第2页共5页1.子集问题(subset.cpp/c/pas)【问题描述】设集合Sn={1,2,…,n}.它的子集就是不重复地取其中任意个数所构成的集合.空集={}和Sn本身也都是Sn的子集.（事实上空集是任意集合的子集.）若X是Sn的子集,把X中所有数的和称为子集X的”容量”.（规定空集的容量为0.)若X的容量为奇数,则称X为Sn的奇子集.现在我们需要对某个特定的n求出Sn的奇子集的个数.【输入】输入文件名为subset.in.输入仅有一行,包括一个正整数n.【输出】输出文件名为subset.out.输出也仅有一行,只有一个正整数,代表Sn的奇子集的个数.由于这个数可能比较大,你只要输出该数模32749的结果作为答案即可.【输入输出样例1】subset.insubset.out22【输入输出样例2】subset.insubset.out34【数据范围】30%的输入数据满足151n.100%的输入数据满足100001n.第3页共5页2.祭祀(sac.cpp/c/pas)【问题描述】遥远的西方有一个神秘国家叫作巫人国.巫人国的神庙里供奉着天空神、大地神和山岳神三位神明.这个国家的人祭祀方式很奇特,他们不用拿牲口去献祭.他们的祭品是巫人国特产的一种珍贵的宝珠.为了表现对神明的虔诚,他们必须将祭品按价值等分为三份献给三位神明.由于献祭的人数和祭品数量都相当庞大,因此仅靠人力很难去进行平分祭品的工作.国师发明了一台机器,可以对每个人的每颗祭品宝珠进行价值衡量,但却无法完成平分工作.因此他希望请你帮忙改进机器使其能判断祭品能否平分,如果可以机器会自动对祭品按价值分为三等份.【输入】输入文件名为sac.in.输入第一行是一个正整数n,表示本次献祭的人数.接下来n行是这n个人献祭的信息.每行开始有一个正整数m,表示这个人献祭的宝珠数目.之后有m个正整数表示每颗宝珠的价值.【输出】输出文件名为sac.out.输出文件共有m行,每行为一个判断信息”Yes”或者”No”,按先后顺序对应于m个人.如果那个人的宝珠是可以被平分献祭的,那么就输出”Yes”,否则输出”No”.【输入输出样例1】sac.insac.out33111412439331112223YesNoYes【数据范围】30%的输入数据满足101n,123m.100%的输入数据满足2001n,213m.且保证每颗宝珠价值不超过1000.第4页共5页3.打鼹鼠(mole.cpp/c/pas)【问题描述】鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的.根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气.你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死.而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为（i,j）的网格移向(i-1,j),(i+1,j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个nn的网格.游戏开始时你可以自由选定机器人的初始位置.现在你知道在一段时间内,鼹鼠出现的时间和地点,希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠.【输入】输入文件名为mole.in.第一行为两个正整数n,m(其中m表示在这一段时间内出现的鼹鼠的个数).接下来的m行每行有三个数据t,x,y表示有一只鼹鼠在游戏开始后t个时刻,在第x行第y个网格里出现了一只鼹鼠.t按递增的顺序给出.注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠.【输出】输出文件名为mole.out.输出文件仅包含一个正整数,表示能打死鼹鼠的最大数目.【输入输出样例】【数据范围】30%的输入数据满足1001mn，.100%的输入数据满足10001n,100001m.mole.inmole.out221112221第5页共5页4.分糖游戏(candy.cpp/c/pas)【问题描述】一群学生围成一圈,他们的老师坐在中间.每个学生开始都有一些糖果.当老师吹响口哨,每个学生都同时将自己的糖果分一半给他右边的人.如果有学生糖果的数目是奇数,那么老师就会给他补上一块糖果.游戏结束时,所有的学生拥有的糖果数目应该是相同的.试编程计算老师吹哨的次数和结束时学生拥有的糖果数目.如果游戏无法结束,那么应该给予提示.【输入】输入文件名为candy.in.输入文件包括若干组测试,每一组的第一行仅有一个正整数表示参与游戏的学生人数.接下来一行有n个正整数,对应表示1~n号学生的初始糖果数(保证为偶数).输入文件以0为结束标志.【输出】输出文件名为candy.out.输出有若干行,每一行代表一组测试信息的结果.对于每一组测试,如果无法结束则输出”NoEnd!”;如果可以结束则一行两个正整数,分别表示老师吹哨的次数和结束时每个人的糖果数.【输入输出样例】candy.incandy.out42468636222220481514【数据范围】40%的输入数据满足201n.100%的输入数据满足401n.且每个人的初始糖果数一定小于1000.