2012年安联杯安徽省青少年信息学奥林匹克竞赛小学组试题

2012年安联杯安徽省青少年信息学奥林匹克竞赛小学组试题AOI2012比赛时间：2012年5月26日08:00至11:00比赛地点：安徽安庆题目名称统分大作战超市排排看挑战算周长源文件名statistics.pas/c/cppmarket.pas/c/cppperimeter.pas/c/cpp输入文件名statistics.inmarket.inperimeter.in输出文件名statistics.outmarket.outperimeter.out满分100100100是否有部分分否否否时限1秒1秒1秒内存限制128M128M128M注意事项1.务必看清题目，严格按照所要求的格式输入、输出。2.在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。测试有严格的时间限制，请尽可能优化算法。3.命名规则：(1)每题都规定了该题的英文名称。(2)程序文件和数据文件的主文件名都是该题的英文名字。(3)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。4.要求提交源程序的文件名一律采用小写。不同程序设计语言的源文件其扩展名请使用默认的扩展名。例如，PASCAL语言编写的源程序文件的扩展名应该为.pas；C语言编写的源程序文件的扩展名应该为.c；C++语言编写的源程序文件的扩展名应该为.cpp。注意：扩展名也应为小写。5.选手在桌面上建立以选手的参赛号为名的目录，并由选手为每道试题再单独建立一个子目录，子目录名与对应的试题英文名相同（英文小写，参见试题封面页）。选手提交的每道试题的源程序必须存放在相应的子目录下。未按规定建立子目录、建立的子目录名出现错误、或提交的源程序没有存放在相应的子目录下等都会导致选手成绩为0分，责任由选手承担。请注意参赛号前缀AH为大写的半角英文字符。6.所有的输入输出文件最后一行均无回车换行符。题目1.统分大作战（statistics）卡卡西是纽瑞滋小学五年级一班的学习委员，今天是暑假的第一天，卡卡西还没起床就一直在想：这个暑假一定要做一些有意义的事情，不如从今天开始吧！随后她一骨碌爬了起来美美的吃了个早饭，然后打开电脑，登录QQ。别看卡卡西年纪小，她可是班上的电脑高手呢，同学们平日里一有问题，都愿意向她请教。突然，她看到Semanda老师的头像闪了起来，心想：老师这么早又开始工作了啊……果然不出她所料，原来是班上刚考完期末考试，Semanda老师要根据成绩评选学习积极分子，正准备给卡卡西布置任务呢。Semanda老师说：“这个统计可不简单哦！”，“没问题！保证尽快完成！”，卡卡西愉快的接受了任务，还发了一个笑脸给Semanda老师，亲爱的小朋友们，你们可以帮助卡卡西一起解决这个问题么？班级要根据语文、数学、英语和计算机这四科成绩，评选学习积极分子。评选规则如下：设：Y、S、E、J分别代表语文、数学、英语、计算机。1、四科平均成绩高于90分，可判定学生等级为A。2、若不符合等级A，且Y、S、E三科平均成绩高于80分，而且J不低于90分，可判定学生等级为B。3、若不符合等级B，且四科中最高分为100分，最低分不低于60分，则判定学生等级为C。4、若不符合A、B、C任何等级，则判定学生等级为D。5、一个学生只能被评为符合条件的最高等级（A最高、D最低）。现在输入某些学生的四科成绩，请判断这些学生能被评为哪一等级。输入：共N+1行，第一行为正整数N（1≤N≤1000）,表示学生人数；后面N行每行有4个正整数（中间用空格隔开），分别表示学生的语文、数学、英语、计算机4科成绩。输出：共N行，每行输出一个学生的等级。样例：输入：（statistics.in）29092949550806040输出：（statistics.out）AD限制：80%的数据1≤N≤100100%的数据1≤N≤10002.超市排排看（market）经过仔细思考，卡卡西终于编程完成了Semanda老师布置的任务，心里可高兴了，心想：嗯，今天一开始就做了一件有意义的事情呢。卡卡西伸了一个大大的懒腰，看看时间，快11点了，妈妈要烧饭了，这时妈妈的声音从厨房里传来，“卡卡西，快帮妈妈去买袋糖，家里糖没啦……”，卡卡西拿了5美元，快步跑下楼，去了楼下的超市，从货架上找到了糖，来到收银台前准备付账，抬头一看，哎呀，只有一个收银台开放，卡卡西的前面已经排了很多人呢，都是熟悉的邻居叔叔阿姨。每个人手里的东西都不一样多，有人手里只有一瓶果汁，有人买了满满一推车物品，“天啊，这要排到什么时候啊？”，小朋友们，为了让所有人平均等待最小，卡卡西可以早点到家，你们有办法解决这个问题吗？在超市的收银处有N位顾客在排队等着付款，他们的编号依次为1,2，…，N。由于每个顾客所购的商品不同，因此付款时所需的等待时间也就不一样。假设给出这N个人每个人单独付款所需的时间，请编程找出这N个人排队的一种顺序，使得所有人平均等待时间最少。输入：共N+1行，第一行为正整数N（1≤N≤50000），表示排队的人数；后面N行每行一个正整数，分别为这N个人单独付款所需的时间（N个人单独付款所需的时间互不相同），时间最长为50000。输出：共N行，依次输出排好序的顾客编号（第一行输出的编号表示最先付款的顾客编号，…，第N行输出的编号为最后付款的顾客编号）样例：输入：（market.in）3746输出：（market.out）231限制：70%的数据1≤N≤1000100%的数据1≤N≤500003.挑战算周长（perimeter）卡卡西快速的解决了超市排队的问题，受到邻居们的赞许，高兴的回到家，把糖给了妈妈，吃了香喷喷的午饭，又睡了一个甜甜的午觉，感觉人生真美好。下午爸爸回到家，听说了卡卡西帮老师及邻居们解决了难题，准备带她去游乐场玩她平日最喜欢玩的跳舞机作为奖励，卡卡西听了，兴奋的一蹦三尺高。游乐场里人头攒动，每台跳舞机前都围满了人，怎么办呢？人这么多，想玩上估计要等好久了，卡卡西左顾右盼，突然发现一台跳舞机前面没人，“哈哈，被我发现一台没人的，赶快去……”，结果到了面前才发现这台新机器的玩法与众不同，脚下的格子随机位置显示出很多的“X”，踩到一个格子，就要根据规则先算出它对应的周长，然后把正确周长输入机器，最后的胜利者还可以获得游乐城的免费游戏券一张，卡卡西心动了，小朋友们，你们可以帮助卡卡西顺利拿到游戏券么？游戏规则如下：新跳舞机踏板上有许多要分析的目标，由脚踩确定一个目标。目标边界的周长是一个有用的测量参数。编程任务：确定选中目标的周长。新跳舞机的踏板是一个矩形的网格，里面有点'.'，表示空的地方；有大写字母'X'，表示目标的一部分。简单网格如下图所示：方格中的一个X是指一个完整的网格方形区域，包括其边界和目标本身。网格中心的X与其边界上8个方向的X都是相邻的。任何两个相邻的X，其网格方形区域在边界或拐角处是重叠的，所以它们的网格方形区域是相邻的。一个目标是由一系列相邻X的网格方形区域连接起来构成的。在网格1中，一个目标填充了全部网格；在网格2中有两个目标，其中一个目标只占左下角的一个网格方形区域，其余的X属于另一个目标。卡卡西总是能踩到一个X，以选中包含该X的目标，记录脚踩时的坐标。行列号是从左上角开始，从1开始编号的。在网格1中，卡卡西可以行2和列2选择目标；在网格2中，脚踩行2和列3就可以选中较大的目标，脚踩行4和列3就不能选中任何目标。一个有用的统计参数是目标的周长。假定每个X的每条边上有一个方形的单元。在网格1中的目标的周长是8（4个边，每个边上有2个方形的单元）；在网格2中，较大目标的周长是18。如图1所示。目标中不会包含任何完全封闭的孔，所以图2这样的网格是不会出现的。输入：共M+1行，第一行为四个正整数M（1≤M≤20）,N（1≤N≤20）,X（1≤X≤M）,Y（1≤Y≤N）（中间用空格隔开），表示网格的大小为M行，N列，且踩中网格的第X行第Y列方格。后面就是M行，由字符'.'和'X'构成输出：共一行，表示选中目标的周长。样例1：输入：(perimeter.in)2222XXXX输出：(perimeter.out)8样例2：输入：(perimeter.in)6423.XXX.XXX.XXX...X..X.X...输出：(perimeter.out)18限制：30%的数据1≤N≤10，1≤M≤10100%的数据1≤N≤20，1≤M≤20