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

2015年合肥市瑶海区信息学竞赛

小学组

（请选手务必仔细阅读本页内容）

一、题目概况

中文题目名称子集问题祭祀打鼹鼠分糖游戏

英文题目与子目录名subset sac mole candy 可执行文件名subset sac mole candy 输入文件名subset.in sac.in mole.in candy.in 输出文件名subset.out sac.out mole.out candy.out 每个测试点时限1秒1秒1秒1秒测试点数目10 10 10 10 每个测试点分值10 10 10 10

附加样例文件有有有有

结果比较方式全文比较（过滤行末空格及文本回车）题目类型传统传统传统传统二、提交源程序文件名

对于C++语言subset.cpp sac.cpp mole.cpp candy.cpp 对于C语言subset.c sac.c mole.c candy.c 对于pascal语言subset.pas sac.pas mole.pas candy.pas 三、运行内存限制

内存上限128M 128M 128M 128M

注意事项：

1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

1.子集问题

(subset.cpp/c/pas)

【问题描述】

设集合S n={1,2,…,n}.它的子集就是不重复地取其中任意个数所构成的集合.空集∅={}和S n本身也都是S n的子集.（事实上空集是任意集合的子集.）若X是S n的子集,把X中所有数的和称为子集X的”容量”.（规定空集的容量为0.)若X的容量为奇数,则称X为S n的奇子集.现在我们需要对某个特定的n求出S n的奇子集的个数.

【输入】

输入文件名为subset.in.

输入仅有一行,包括一个正整数n.

【输出】

输出文件名为subset.out.

输出也仅有一行,只有一个正整数,代表S n的奇子集的个数.由于这个数可能比较大,你只要输出该数模32749的结果作为答案即可.

【输入输出样例1】

subset.in subset.out

2 2

【输入输出样例2】

subset.in subset.out

3 4

【数据范围】

30%的输入数据满足15

≤n.

1≤

100%的输入数据满足10000

≤n.

1≤

2.祭祀

(sac.cpp/c/pas)

【问题描述】

遥远的西方有一个神秘国家叫作巫人国.巫人国的神庙里供奉着天空神、大地神和山岳神三位神明.这个国家的人祭祀方式很奇特,他们不用拿牲口去献祭.他们的祭品是巫人国特产的一种珍贵的宝珠.为了表现对神明的虔诚,他们必须将祭品按价值等分为三份献给三位神明.

由于献祭的人数和祭品数量都相当庞大,因此仅靠人力很难去进行平分祭品的工作.国师发明了一台机器,可以对每个人的每颗祭品宝珠进行价值衡量,但却无法完成平分工作.因此他希望请你帮忙改进机器使其能判断祭品能否平分,如果可以机器会自动对祭品按价值分为三等份.

【输入】

输入文件名为sac.in.

输入第一行是一个正整数n,表示本次献祭的人数.接下来n行是这n个人献祭的信息.每行开始有一个正整数m,表示这个人献祭的宝珠数目.之后有m个正整数表示每颗宝珠的价值.

【输出】

输出文件名为sac.out.

输出文件共有m行,每行为一个判断信息”Yes”或者”No”,按先后顺序对应于m个人.如果那个人的宝珠是可以被平分献祭的,那么就输出”Yes”,否则输出”No”.

【输入输出样例1】

sac.in sac.out

3

3 1 1 1

4 1 2 4 3

9 3 3 1 1 1 2 2 2 3 Yes No Yes

【数据范围】

30%的输入数据满足10

1≤

≤n,12

3≤

≤m.

100%的输入数据满足200

1≤

≤n,21

3≤

≤m.且保证每颗宝珠价值不超过1000.

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≤≤m n ，.

100%的输入数据满足10001≤≤n ,100001≤≤m .

mole.in mole.out

2 2 1 1 1

2 2 2

1