宿州第九届中小学生信息学竞赛 中学组试卷
一、芝麻开门（open）
话说丁丁终于到了一年一次的休假，他决定好好利用这个假期。很久以前他就发现了一个神秘的山洞，一直没有机会去探险，这次终于可以去探个究竟了。
当他来到山洞前却被一扇石门拦住了，上面有一个数字，和两个按钮分别“Yes”和“No”，有个多次冒险经验的他一眼就看出来，这两个按钮就是开启石门的关键，按对了石门打开，按错了会触发机关将遇到空前的危险。经过仔细推敲，他发现原来那个数字是素数就按“Yes“，否则按“No”。面对一个如此庞大的数字，丁丁想起了会编程的你，请你帮忙写个程序，判断他该按哪个按钮。
输入文件（open.in）
一个整数n，即石门上的数字。
输出文件（open.out）
丁丁应该按的按钮（注意大小写）。
样例输入：
17
样例输出：
Yes
数据范围：
0<=n<=2^31-1
二、疯狂的数列（crazy）
在你的帮助下，丁丁终于打开了石门，进去后发现里面有个面目狰狞的妖怪。这只妖怪正怒视着丁丁，然后一言不发的在地上写了一串数字：1，12，123，1234，12345，…………，1234567010，123456701011………………。然后告诉丁丁：“你要是能知道这个数列的前n项里有多少项能被3整除，我就放你过去，否则，嘿嘿……吃了你！”看来这个妖怪的数学不错，不过数学更是丁丁的强项，很快就算出了答案。你知道怎么算的吗？
输入文件（crazy.in）
一个整数n
输出文件(crazy.out)
一个整数，表示这个数列的前n项里有多少项能被3整除。
样例输入：
5
样例输出：
2
数据范围：
30% n<=10
100% n<=2^31-1
三、武器（weapon）
妖怪看到丁丁的数学非常好，于是厚着脸皮找丁丁帮忙。他拿出了n件武器（编号依次为1—N）和M只相同的盒子，每件武器的重量分别为w[i]，每只盒子最大的承重为t。丁丁要做的是在妖怪的要求范围内，把尽量多的武器放进盒子里。
妖怪的要求是：
1.一件武器不能拆开放在两个或更多的盒子里。
2.武器必须按编号顺序放进盒子里，也就是说如果丁丁把第i件武器放进某个盒子后，他就不能再把编号小于i的武器放进任何盒子。
输入文件：（weapon.in）
第一行，三个数字：n,t,m
第二行，n个整数，按编号给出每件武器的重量w[i]
输出文件：(weapon.out)
一个整数，表示最多可以装进m个盒子里的武器数量。
样例输入：
4 5 2
4 3 4 2
样例输出：
3
数据范围：
50%的数据 0<=n,t,m,w[i]<=20
100%的数据 0<=n,t,m,w[i]<=200
四、基地（base）
顺利的解决了武器的问题之后，妖怪终于放丁丁进入山洞。由于山洞内道路复杂，丁丁不得不借助于自己设计的导航系统。这套导航系统有自己的特点，必须在一个平整的矩形区域内架设设备，而且矩形区域面积越大，导航精度越高。
山洞内的地形正好呈一个矩形，大部分区域也平整，只是p个区域有一些水坑。如下图所示，山洞呈一个3*4的矩形，在（1，3）和（2，1）位置有两个水坑（黑色区域）那么，最大只能找出面积为6的平整矩形。
为了导航系统更精确，请你找出最大的平整矩形供丁丁使用。
输入文件（base.in）
第一行，三个整数n,m,p，分别表示山洞有n行，m列，其中有p个水坑
第二行至第P+1行，每行两个整数，表示水坑的行号和列号
输出文件（base.out）
一个整数，能够找到的最大矩形面积
样例输入
3 4 2
1 3
2 1
样例输出
6
数据范围：
30%的数据 1<=n,m<=20 1<=p<=20
60%的数据 1<=n,m<=300 1<=p<=3000
100%的数据 1<=n,m<=3000 1<=p<=30000
五、怪兽(monster)
在导航仪的指引下，丁丁很快来到了宝库。宝库前的唯一通道上布满了各种各样的小怪兽（每种怪兽用一个字母代替），摆出了长方陈阻止着丁丁的前进。不用怕，丁丁有强大的病毒消灭他们，而且这种强大的病毒每次投放不仅会消灭某个位置的怪兽，而且会消灭它周围（周围指的是上，下，左，右四个方向相邻的位置）与它相同的怪兽，以及周围的周围的相同的怪兽。
例如：怪兽的阵型如下：
AABBCCD
AFFBGGD
IIJBKKD
MNNOOPD
QQRRSST
如果在（1，4）位置投放病毒，会消灭与它相邻的所有的怪兽如下：
AA CCD
AFF GGD
IIJ KKD
MNNOOPD
QQRRSST
武器虽然强大，但每次投放需要许多的体力，为了节省更多的体力拿宝藏，丁丁决定尽可能少的投放病毒，只要能从上到下打通一条差距就行了。请问如何设计才能使投放病毒的位置只能是丁丁的周围的位置，第一次能投放病毒的位置是第一行的任意位置，最后一行的任意位置被炸开即可。
输入文件(monster.in)
第一行，两个整数n,m,表示怪兽阵型的行数n和列数m;
第二行至第n+1行，每行m个字符，表示怪兽的类型。所有字符只可能是”A”~”Z”,每行字符与字符之间没有空格。
输出文件(monster.out)
一个整数，最少投放病毒的次数。
样例输入：
5 7
AABBCCD
AFFBGGD
IIJBKKD
MNNOOPD
QQRRSST
样例输出：
2
数据范围：
30%的数据 1<=n,m<=20
70% 的数据 1<=n,m<=100
100%的数据 1<=n,m<=500
六‘封路(road)
最终丁丁取得了宝藏，但是他不想有人知道这里的宝藏已被取走，最好的办法就是让别人无法到达定期所在地。经过一番探查，他统计出整个山洞里有n个洞穴并给他们分别编号，有些洞穴之间有一条或多条通道，共m条。请你帮丁丁计算出，至少炸毁多少个洞穴，别人才不能从外面进入到宝藏所在地。
输入文件(road.in)
第一行，四个整数n,m,k,t,表示有n个洞穴，m个通道，洞口编号，宝藏所在洞穴编号。
第二行至第m+1行，每行两个整数，表示两个连通的洞穴的编号。
输出文件(road.out)
共两行：第一行，最少炸毁洞穴的数目
第二行，编号从小到大的输出被炸毁的洞穴编号。
注意：1和n号洞穴不能炸毁。如果有多种可能情况，输出 第一个数最小的一种，如果第一个数相同，则输出第二个数最小的一种，依此类推。
样例输入：
3 2 1 2
1 2
2 3
样例输出：
1
2
数据范围：
30%的数据 1<=n<=10,1<=m<,=30
100%的数据 1<=n<=100,1<=m<=600