2010年全国青少年信息学奥林匹克联赛（阜阳
赛区选拔赛）普及组试题
竞赛时间：2010年10月23日上午8：30—11：00
题目一览
题目概况： 题目名称 程序名称 输入文件名 输出文件名 测试点数量 每测试点时限 每测试点分值 内存上限 注意事项：
1． 务必看清题目，严格按照要求的格式输入、输出。
2． 在调试程序时请先用题目中的样例数据，然后再自行设计多组测试数据进行 调试。
3． 文件的命名规则：
程序文件的扩展名采用所用的语言环境的默认扩展名。
程序文件主文件名为每题题目后括号内的文件名，输入、输出文件名为每题输入、输出文件括号内的文件名。
4． 选手在竞赛结束时D:盘上建立以参赛号命名的文件夹，并将所完成的各题的源程序和可执行文件拷贝到该文件夹中，特别注意的是不要在考号文件夹内再建立文件夹。 ．．．．．．．．．．．．．．．
一、 芝麻开门（open）
话说丁丁终于等到了一年一次的休假，他决定好好利用这个假期。很久以前他就发现了一个神秘的山洞，一直没有机会去探险，这次终于可以去探个究竟了。
当他来到山洞前却被一扇石门拦住了，上面有一个数字，和两个按钮分别“Yes”和“No”，有个多次冒险经验的他一眼就看出，这两个按钮就是开启石门的关键，按对了石门打开，按错了会触发机关将遇到空前的危险。经过仔细推敲，他发现原来那个数字是素数就按“Yes”按钮，否则按“No”按钮。面对一个如此庞大的数字，丁丁想起了会编程的你，请你帮忙写个程序，判断他该按那个按钮。
第 1 页 共 3 页
芝麻开门 open open.in open.out 10 1秒 10 128M 疯狂的数列 crazy crazy.in crazy.out 10 1秒 10 128M 武器 weapon weapon.in weapon.out 10 1秒 10 128M 基地 base base.in base.out 10 1秒 10 128M 输入文件（open.in）
一个整数n，即石门上的数字。 输出文件（open.out）
丁丁应该按的按钮（注意大小写）。 样例输入： 17
样例输出： Yes
数据范围： 0<=n<=231-1
二、 疯狂的数列（crazy）
在你的帮助下，丁丁终于打开了石门，进去后发现里面有个面目狰狞的妖怪。这只妖怪正怒视着丁丁，然后一言不发的在地上写了一串数字：1，12，123，1234，12345，„„，123456710，12345671011，„„。然后告诉丁丁：“你要是能知道这个数列的前n项里有多少项能被3整除，我就放你过去，否则，嘿嘿„„吃了你！”看来这个妖怪的数学不错，不过数学更是丁丁的强项，很快就算出了答案。你知道怎么算吗?
输入文件（crazy.in） 一个整数n
输出文件（crazy.out）
一个整数，表示这个数列的前n项里有多少项能被3整除。 样例输入： 5
样例输出： 2
数据范围：
30%的数据 n<=10 100的数据 n<=231-1
三、 武器（weapon）
妖怪看到丁丁的数学非常好，于是厚着脸皮找丁丁帮忙。他拿出了n件武器（编号依次为1~n）和m只相同的盒子，每件武器的重量分别为w[i]，每只盒子最大承重为t。丁丁要做的是在妖怪的要求范围内，把尽可能多的武器放进盒子里。
妖怪的要求是：
1. 一件武器不能拆开放在两个或更多的盒子里； 2. 武器必须编号顺序放进盒子里，也就是说如果丁丁把第i件武器放进某个盒子后，他就不能再把编号小于i的武器放进任何盒子。
输入文件（weapon.in） 第一行，三个整数:n,t,m
第二行，n个整数，按编号给出每件武器的重量w[i]
第 2 页 共 3 页
输出文件（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
第 3 页 共 3 页
