安徽省2013年“京胜杯”大学生程序设计竞赛题目及解题报告

2013安徽省省赛题解2013.05.302013安徽省省赛裁判出题组安徽省2013年“京胜杯”大学生程序设计竞赛Ａ．单词反转Timelimit1sＰｒｏｂｌｅｍＤｅｓｃｒｉｐｔｉｏｎ给你一些英文句子，请将这些句子中的每个英语单词反转，然后再将其输出．这里听说的英语单词仅由大小写英文字母组成．Ｉｎｐｕｔ多个英文句子，每句占一行，且每句不超过８０个字符．Ｏｕｔｐｕｔ按题目要求输出ＳａｍｐｌｅＩｎｐｕｔＨｅｌｌｏｗｏｒｌｄ！Ｈａｐｐｙｐｒｏｇｒａｍｍｉｎｇ，ｈａｐｐｙｌｉｆｅ！ＳａｍｐｌｅＯｕｔｐｕｔｏｌｌｅＨｄｌｒｏｗ！ｙｐｐａＨｇｎｉｍｍａｒｇｏｒｐ，ｙｐｐａｈｅｆｉｌ！Ｂ．等差数列ｔｉｍｅｌｉｍｉｔ１ｓＰｒｏｂｌｅｍＤｅｓｃｒｉｐｔｉｏｎ有一个长度为Ｎ（１＜＝Ｎ＜＝１０００００）的整数序列ｓ［］，在这个序列上定义了两种操作：ＡｄｄＬＲＡＤ：对于每一个ｉ（Ｌ＜＝ｉ＜＝Ｒ），Ｓ［ｉ］＋＝Ａ＋（ｉ－Ｌ）＊Ｄ，也就是在子序列Ｓ［Ｌ，Ｒ］加上首项Ａ，公差为Ｄ的等差数列：ＱｕｅｒｙＬＲ：询问［Ｌ，Ｒ］区间内最长的等差数列的长度，亦即寻找最大的ｌｅｎ，使Ｓ［ｉ］，Ｓ［ｉ＋１］，．．．，Ｓ［ｉ＋ｌｅｎ－１］（Ｌ＜＝ｉ＜＝Ｒ，Ｌ＜＝ｉ＋ｌｅｎ－１＜＝Ｒ）构成等差数列。Ｉｎｐｕｔ多组测试数据。每组测试数据的第一行为两个正整数Ｎ（１＜＝Ｎ＜＝１０００００）和Ｍ（１＜＝Ｍ＜＝１００００），分别代表序列的长度和操作个数，接下来有Ｍ行，每行代表一个操作，操作具体含义见题目描述。其中，０＜＝Ｌ＜＝Ｒ＜Ｎ，０＜＝Ａ＜＝１０００００，０＜＝Ｄ＜＝１０．Ｏｕｔｐｕｔ对于每组测试数据，首先输出组号。然后对于每次询问，输出所求结果。详见样例输出。ＳａｍｐｌｅＩｎｐｕｔ５３Ａｄｄ１４１１Ｑｕｅｒｙ０４Ｑｕｅｒｙ２３１０４Ａｄｄ０９１１Ａｄｄ４９１１Ｑｕｅｒｙ０９Ｑｕｅｒｙ５５ＳａｍｐｌｅＯｕｔｐｕｔＣａｓｅ＃１：５２Ｃａｓｅ＃２：７１Ｃ．进程调度ｔｉｍｅＬｉｍｉｔ１ｓＰｒｏｂｌｅＤｅｓｃｒｉｐｔｉｏｎ操作系统的一个重要功能是进行进程调度，其进程调度的算法有多种，其中最简单的调度算法是先进先出服务（ＦＣＦＳ）算法，该算法的思想是：先进入就绪队列的先执行，后进入的后执行，同一时刻进入就绪队列的执行时间少的先执行。我们认为某一进程一旦开始执行，就一直占用处理机，直到执行结束。而一旦处理机被其它进程占用，就绪队列中的进程就必须等待。当某一进程执行结束后，队列中排在最前面的进程就会立即执行。一个进程从进入就绪队列到执行完毕所用的时间为其周转时间，即周转时间＝等待时间＋执行时间。现在给你若干进程到达就绪队列的时间以及每个队列的执行时间，请编程计算这些进程的平均周转时间。Ｉｎｐｕｔ多组测试数据。每组测试数据的第一行为一个正整数Ｎ（Ｎ＜＝１０００），表示要处理的进程数目。接下来有Ｎ行，每行有两个正整数Ａｉ（Ａｉ＜＝１０００）和Ｅｉ（Ｅｉ＜＝１０００），分别表示一个进程到达就绪队列的时刻和执行该进程所需的时间。Ｏｕｔｐｕｔ对于每组测试数据，输出平均周转时间，结果保留４位小数。ＳａｍｐｌｅＩｎｐｕｔ４１１３３２２４４ＳａｍｐｌｅＯｕｔｐｕｔ３.５００Ｈｉｎｔ进程１等待时间为０，执行时间为１，其周转时间为０＋１＝１进程３等待时间为０，执行时间为２，其周转时间为０＋２＝２进程２等待时间为１，执行时间为３，其周转时间为１＋３＝４进程４等待时间为３，执行时间为４，其周转时间为３＋４＝７故平均周转时间为（１＋２＋４＋７）／４＝３．５００Ｄ．进击的巨人题目描述：艾伦作为第１０４期训练兵团卒业生于的ＮＯ．５，其它他还有一个特殊能力（主角光环）在艾伦怀有强烈意志时进行自我伤害，就能变身为最大１５米级的巨人，现在巨人已经突破了赛罗之墙，如果不用巨大的石头堵上这堵墙的缺口的话，人类的领地就会进一步缩小，我们用一个二维坐标（Ｘ０，Ｙ０）表示巨人化的艾伦的初始位置，然后用（ｘ１，ｙ１）以及Ｒ表示石块的以及（我们假设这个石块是圆形的），然后用２个点（ｘ２，ｙ２），（ｘ３，ｙ３）表示罗塞之墙的缺口（一条线段），现在当务之急就是要把石块尽快搬到缺口处才行。也就是要求所走的路径是从初始点到石块再到缺口处的距离之和最小。缺口肯定在石块外输入：多组数据输入，每组数据先是２个实数（ｘ０，ｙ０），然后再是ｘ１，ｙ１，Ｒ，接着再是ｘ２，ｙ２，ｘ３，ｙ３.输出：对于每组数据，输出最短的路径的长度（结果保留２位小数）样例输入：１１００１１０２０１１００１１－１１－２样例输出：１.００２.００Ｅ．巨人的进击题目描述：悠长的历史之中，人类层一度因被巨人捕食而崩溃。面临着生存危机而残存下来的人类建造了三重巨大防护墙，这在１００年内防止了巨人的入侵。不过，作为“和平”的代价，人类也失去了到墙壁外面去的“自由”。正在人们安逸了１００年之际，一个前所未有的超大型巨人出现了！那一天，人类终于回想起了，曾经一度被我们所支配的恐怖，还有被囚禁于鸟笼中那份屈辱，五年前，艾伦－耶格尔目睹母亲遭巨人吞食后，立誓要消灭所有的巨人。而现在超大型巨人又再次出现在艾伦的面前，并破坏了罗塞之墙，现在必须要尽快堵上这个缺口，现在我们已知缺口是一个凸多边形，（不要在意这些细节），我们必须要尽可能的把缺口堵上，那么得用多大的石块（石块假设是圆形的）。输入：多组测试数据，每组给出一个ｎ表示凸多边形的定点个数，然后再给出这些凸多边形的顶点的位置（ｘｉ，ｙｉ）。（逆时针给出）输出：对于每组数据，给出最大的石块的半径（结束保留２位小数）样例输入：４００１０１１０１样例输出：０.５０Ｆ．闪光的指压师题目描述：桐奈是未来道具研究所的研究员No.005，有重度的手机依存症，她沉默寡言到了与别人的交流全部都要通过手机短信的地步（就算对方在眼前），她打字的速度是连眼睛都跟不上的杰出的特技。她对手机的操作可谓是了如指掌（不是现在的智能机。。），我们已知手机的每个按键有不同的含义：按键1：，。！按键2：abc按键3：def按键4：ghI按键5：jkl按键6：mno按键7：pqrs按键8：tuv按键9：wxyz按键0：空格按键#：数字和拼音切换按键ok：（仅对一个按键下有多个字符含义时才会用到，按键0用到因为它在拼音模式下只有空格这个含义而在数字含义下仅代表0，按键#用不到，以及数字输入法下的0到9键）最初是拼音输入法，我们知道这个手机每次只能输入单个字符，如果要输入数字9997，就要按下按键#，然后我们按下按键9三次和按键7一次，如果要输入cd，先按下按键2三次，然后按下ok键，接着按下按键3一次，再按下按键ok即可，也可以先按下按键2三次，然后再按下按键3（因为按下其他按键就表示你已经确定了要输入按键2下的第几个字符了，这里表示按键2下的第三个字符），这样就输入了c，最后按下按键ok就输入了d，很明显后者需要的操作要少一些，现在桐奈要发送一系列的信息，她想要尽可能快的输入这些信息（就是操作尽可能少），那么该怎么办呢？还要注意在切换输入法的时候，例如a1，只需按下按键2一次，然后按下#键一次（因为切换了输入法，故接下来的按键内容与上次肯定不同，所以判定你已经确定了按键2下的第几个字符了），然后按下按键1即可；也可以按下按键2一次，然后按下ok键，然后再按下按键#一次，接着按下按键1即可，不过后者操作要多一次。输入：多组测试数据，每组输入只有一行字符，字符仅包含，。！a到z0到9以及空格。输出：每一行输出相应的按键。样例输入：21412fsf3223jkljsfj32样例输出：#21412#033377770333#32#0#23#5ok55ok555ok5777733305#32G．Alice&MarisaProblemDescriptionAlice和Marisa是一对好CP。Alice和Marisa都要向同一个商人Reimu购买节操。Reimu手中有N份节操，她会将它们一份份地卖给他们，Alice和Marisa通过竞价的方式来决定节操的归属。具体的过程如下：Reimu首先指定其中一个人开始报价，之后两人轮流报价，要求是一定要比对方报的价格更高。任何时候，如果一个人不愿出价或者出不起价时，可以宣布弃权，则对手以最后一次报的价格将节操买下。当然，如果两个人都没钱，Reimu是不会卖节操的。首先报价至少为1，并且只能报整数的价钱。Alice和Marisa特别爱攀比，因此她们都希望能比对方买到更多的节操。Alice和Marisa各自带了CA和CM的钱用于竞拍节操。此外，Marisa和Reimu有很不错的私人关系，因此Reimu总会让Marisa先报价。现在请问，在Alice和Marisa都用最优策略的情况下，谁能买到更多的节操？假设双方都知道对方手中的现金数量，以及Reimu将要拍卖的节操数量N。Input本题有多组数据。每组数据为一行三个用空格隔开的整数N，CM，CA，表示节操的数量，以及双方带的现金。0=N=100000,0CM,CA=1000000Output对于每组测试数据，输出一行X，X的取值为{-1,0，1}，-1表示Alice买到的节操会比Marisa多，0表示两个人能买到一样多，1表示Marisa能买到更多的节操。SampleInput435747SampleOutput01H．排列的前后ProblemDescription学霸向你讨教了全排列之后又自己仔细研究了一番信心满满又去面试另一家公司，这次面试官得知了上次全排列的经历后，决定再次测试下不过这次的测试有点好玩，考官表示只能手算，要计算出给定的排列之后或者之前若干位置的排列是什么。Input本题有多组输入数据。每组数据两行，每一行一个字符串s（1=s的长度=26）第二行一个整数n（|n|=2^90。s是给定的前若干的大写字母组成的一排列。Output输出一行表示相对s位置为n的排列，若不存在这样的排列则输出“Areyoukiddingme.”这个字符串。SampleBACD2BACD0BACD-2BACD9999SampleOutputBCADBACDADBCAreyoukiddingme.I.散步ProblemDescription@每天吃完晚饭后都会从家出发到雾之湖及其周围去散步下，最终到达魔方森林的入口，并尽可能尝试不同的路径。雾之湖及其周围可以抽象为一个矩形，划分为n*m块区域，@家为（1,1），散步时@在某个区域会逗留一段时间，然后移动到东西南北相邻的其中一个格子（移动时间忽略不计），经过若干次移动最终到达魔法森林（n，m）。因为是散步，所以起点和终点@都会逗留一段时间。@表示虽然是闲逛，但是也不能太浪费时间，还是得去终点（n，m）的，所以至少存在一条从B到终点的时间比从A到终点的所有路径所花费的时间更少时才可以从A到B。现在@想知道自己一共有多少种路径可以选择，因为@的至少只有@，她自己肯定没法算出来啦。你能帮帮@吗？？Input本题有多组数据。每组数据第一行为n，m（2=n，m=50）接下来为n行m列的矩阵，表示在每个区域@逗留的时间t（0=t=1000）.Output每组数据输出一行，表示路径总数（保证小于2^63）.SampleInput3312312312333111111111SampleOutput16J．IQtest？ProblemDescription猜数游戏在XXX国非常流行游戏过程大概是这样的……一个裁判，三个路人，路人足够聪明\\你可以认为路人是petr，acrush，tourist之类的生物……每次裁判会选出三个正整数，其中某两个相加等于第三个然后分别把这数写在三个路人的脸上\\--|||不要在意这下细节也就是说，每个路人都知道另外两个路人的数字但不知道自己脸上的数是什么游戏开始，裁判每一轮都会问他们三个能否猜出自己脸上是什么，为了体现游戏的公正性，路人们必须同时给出回答。直到有一个路人猜出自己的数时游戏停止那么，如果告诉你这三个数a，b，c，为了证明你比路人厉害，你能预测出游戏会在第几轮停止吗？Input每行三个正整数a，b，c，（1=a，b，c