下载文档原格式
2013年安徽省青少年信息学奥林匹克竞赛
小学组试题
AOI 2013
比赛时间：2013年5月18日08:00至11:00
注意事项
1.务必看清题目，严格按照所要求的格式输入、输出。
2.在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据行调试。测试
有严格的时间限制，请尽可能优化算法。
3.命名规则：
(1)每题都规定了该题的英文名称。
(2)程序文件和数据文件的主文件名都是该题的英文名字。
(3)数据文件都是文本文件，输入和输出文件的扩展名分别是.in 和.out。
4.要求提交源程序的文件名一律采用小写。不同程序设计语言的源文件其扩展名请使用默
认的扩展名。例如，PASCAL 语言编写的源程序文件的扩展名应该为.pas；C 语言编写的源程序文件的扩展名应该为.c；C++语言编写的源程序文件的扩展名应该为.cpp。注意：扩展名也应为小写。
5.选手在桌面上建立以选手的参赛号为名的目录，并由选手为每道试题再单独建立一个子
目录，子目录名与对应的试题英文名相同（英文小写，参见试题封面页）。选手提交的每道试题的源程序必须存放在相应的子目录下。未按规定建立子目录、建立的子目录名出现错误、或提交的源程序没有存放在相应的子目录下等都会导致选手成绩为0 分，责任由选手承担。请注意参赛号前缀AH 为大写的半角英文字符。
6.所有的输入输出文件最后一行均无回车换行符。
题目
1.序列数字个数（seqnum）
最近正在上映电影“魔境仙踪”，爱魔幻故事的卡卡西特别想去看，于是央求着妈妈带她去影院。卡卡西的妈妈对她微微一笑，说：“那好吧，卡卡西，让我来考考你，如果你能解决我出的难题，就可以带你去影院哦！你想要试试吗？”“当然啦，尽管出题吧……”，卡卡西信心满满，于是妈妈开始出题。
题目是这样的：现连续写下从整数1开始到某个整数N（十进制）之间的所有整数时，能得到如下的数字序列：1234567891122…，当N为20时，得到的数字序列为：12345678910111281920。
请编写一个程序，计算这个序列中的数字字符的个数。小朋友们，你们能帮助卡卡西获得观看电影“魔境仙踪”的影券吗？
输入：一行，一个正整数N（1≤N≤10000）。
输出：一个正整数，表示由给定的整数所产生的序列的数字个数。
样例：
输入：（seqnum.in）
15
输出：（seqnum.out）
21
样例解释：当N=15时，得到的数字序列为：1234567891，这个数字序列包含的数字字符个数为21个。
限制：
40％的数据1≤N≤100。
90％的数据1≤N≤1000。
100％的数据1≤N≤10000。
2.上座数（order）
卡卡西终于如愿以偿的破解难题，获得了“魔境仙踪”的电影券。晚上，卡卡西迫不及待的跟着妈妈早早的去了影院。这个影院真是大，上下100层，每一层又有很多的放映厅。忽然，卡卡西发现有一位叔叔正在放映厅门口来回踱步，眉头紧皱着，像是有难题要解决。卡卡西向前询问情况。那位叔叔说：“小朋友，我是这家影院的经理。我们这个影院有很多个放映厅，每个放映厅观众坐满时能容下100人，不开放或没有观众时相当于观众数为0。现在想统计一下，当前时间，影院中所有放映厅的上座数（即观众数的多少），并且计算排名倒数第N位的放映厅的上座人数，以及有多少个放映厅并列排名倒数第N位。”卡卡西想了想，对叔叔笑了笑，拍拍胸脯说：“叔叔，你别急，我来帮你解决这个问题。”亲爱的同学们，你们能帮助卡卡西，让她尽早解决问题，观看电影吗？
输入：共三行，第一行共一个数N（0 输出：共一行，共有两个数，分别表示上座数排名倒数第N位放映厅的上座数和具有该上座数的放映厅的个数（中间用空格隔开）。 样例： 输入：(order.in) 3 8 8 7 4 90 18 86 99 86 输出：(order.out) 8 1 样例解释：输入第一行为3，表示现在想知道上座数排名倒数第3位的放映厅的上座数，输入第二行为8，表示该影院共有8个放映厅，输入第三行表示这8个放映厅的上座数分别为8 7 4 90 18 86 99 86。输出一行，8表示上座数排名倒数第3名的放映厅的上座数为8，而上座数同为8（即并列排名倒数第3位的）放映厅共1个。 40％的数据1≤N≤100。 60％的数据1≤N≤1000。 100％的数据1≤N≤100000。 3.糖果盒（candybox） 卡卡西帮影院经理解决了难题，终于可以和妈妈安心的观看了电影。电影太精彩了，卡卡西在电影放映过程中，多次拍手叫好。放映结束后，卡卡西正准备和妈妈牵手回家，被影院经理拦住了。那位和蔼的叔叔满脸笑容的对卡卡西说：“小朋友，谢谢你之前帮我解决了难题，这可帮了我一个大忙啊！作为对你的感谢，我想赠送你这个糖果盒。这个糖果盒可不一般哦，只有足够聪慧，回答对问题并完成任务的小朋友，才能从中取出糖果”。 卡卡西痴迷的望着这个金光闪闪的糖果盒，瞪大的双眼里充满了好奇。这是一个被分为N*M个格子的飘着芳香的糖果盒，第i行第j列位置的格子里面有a[i][j]颗糖。但是经理告诉卡卡西，不幸的是，前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。为了让糖果盒保持美观，必须从这个糖果盒里面切割出一个新的不能有洞的矩形糖果盒，并且卡卡西希望保留在新糖果盒内的糖的总数尽量多，这样她就能吃到尽可能多的糖。 小朋友们，请你们帮卡卡西设计一个程序，计算一下新糖果盒里最多能够保留多少糖果，从而使卡卡西获得这个糖果礼盒。 输入：共N+1行，第一行有两个正整数N和M（1≤N≤300，1≤M≤300）。后面N行每行M 个正整数，第i+1行的第j个正整数a[i][j]（0≤a[i][j]≤255），表示糖果盒的第i行第j 个格子里的糖果个数，如果这个数为0，则表示这个位置的格子被老鼠洗劫过，即该位置是个洞。 输出：输出一个正整数，即能得到的最大糖果数。
