2010年NOIP第二次模拟赛.doc

描述 Description ? 【问题描述】在一个夜黑风高，伸手不见五指的深夜，睡梦中的林月如突然听到房外一阵躁动。她出去一看，发现一个女飞贼抢了一个古董商的包袱。站住！那你为什么不来追我？因为程序设计，在李大哥来之前，我不能追你。那李逍遥为什么不来呢？大概程序出bug了吧……………………………………………… 终于，在等了一个又一个时辰后，林月如终于忍不住了，开始向女飞贼发起进攻。喂！你为什么可以动？？？这大概也是一个bug吧！不公平啊！废话少说。已知林月如和女飞贼站在一个矩阵中，矩阵中有某些障碍物不可穿越。月如使出的铜钱镖可攻击8个方向，但不可穿越障碍物（可视为不能穿墙的重狙）。每个单位时间，月如可向上下左右4个方向移动一格，攻击不浪费时间。当然，月如想尽快结束这场无聊的战斗，所以她想在最短的时间内消灭女飞贼。【输入格式】第一行为2个数N,M表示矩阵的规模(N为高,M为宽)。接下来是N*M的矩阵,O表示空地,X表示障碍物。下面是若干行数据，每行为一对数据，分别是女飞贼的位置和林月如的位置，显然她们都不可能在障碍物上。以0 0 0 0为输入结束标志。【输出格式】每一组数据输出一行，仅一个整数，表示能消灭掉女飞贼的最短时间。显然若能直接打到女飞贼，则时间为0。若无法消灭，则输出Impossible!。（不含引号）【输入样例】3 4OXXOXXOOXOOO3 2 2 43 3 1 10 0 0 0【输出样例】1Impossible!【数据规模】对于30%的数据,有N*M=100对于50%的数据,有N*M=400对于100%的数据,有N*M=20000对于100%的数据,测试数据组数不超过20组【时间限制】1s【来源】经典问题 描述 Description ? 【问题描述】今年是虎年，小老虎一年来过得可充实了，一有时间就往电脑室跑，因为他要在“在线测试”系统上拿第一名，成为做题最多的牛人。可小老虎也有烦恼的时候。一天放学，小老虎正走出课室想去电脑室，班主任过来了，因刚中段考完，小老虎知道自己的总分不是全级第一也有第二的那种，就大摇大摆的迎了上去。这时，班主任截住了小老虎，说：“小老虎，作业呢？”咦……半天，小老虎才说：“昨天去奥电班了……”，这时班主任瞪了一眼说：“有时间去奥电班就没有时间做我的作业？去“抽机”了吧？！”小老虎无语，不过还是对老师说：“老师，我对天发誓天天在编程，从不玩游戏，越来越聪明了，你看，我这次月测又……”，心里却在想：“切……你的作业这么没有挑战性，有时间我也不做的啦！”这时班主任看出了小考虑的心思，知道作业是追不回来的啦，便想杀杀小老虎的威风。“哦，是啊，你越来越聪明了啊，听说你在奥电班也是拿第一第二的那种，中段考完了，帮老师个忙啊，那数据分析之类的事就你搞掂啦，还有啊，就体艺节了，你想几个游戏给大家活动活动，搞不好啊，以后都别去电脑室编程了，每天老老实实把作业做完”。小老虎……【输入文件】第一行是一个正整数n接下来是n行，每行为一个同学的成绩，格式如下：先是一个字符串，表示这个同学的名字（长度小于等于20，由大小写字母构成），然后是他的4位学号（数据保证是4位，但是可能以0开头），接下来是4个数，分别表示他的语文、数学、英语、综合成绩（这个数在0到150之间，一定是0.5的倍数），最后是一个字符串和一个数（这个数在0到150之间，一定是0.5的倍数），字符串表示他的X科（一定是physics、chemistry、biology中的一个），那个数为他这科的成绩。以上的数据都由一个空格隔开，末尾没有多余的空格。具体请看样例。【输出文件】输出文件一共3行，分别表示选考physics、chemistry、biology中总分最高的同学。每行的输出格式为：先是一个字符串，表示这个同学的名字，然后是他的4位学号，最后是他的总分。如果总分相同，则输出4位学号最小的。数据保证4位学号互不相同。以上的数据都由一个空格隔开，末尾没有多余的空格。具体请看样例。【输入样例】5apple 0101 150 150 150 150 physics 150egg 0202 140 130.5 130 150 chemistry 150banana 0102 130 140 130.5 150 chemistry 150cat 0103 100.5 100 100 100 biology 100dog 0288 89.5 89.5 89.5 89.5 physics 91.5【输出样例】apple 0101 750banana 0102 700.5cat 010