《2013腾讯编程马拉松初赛(3月25)赛题.pdf》由会员分享，可在线阅读，更多相关《2013腾讯编程马拉松初赛(3月25)赛题.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1001 威威猫系列故事吃鸡腿Time Limit:1.0 SecondsMemoryLimit:32768K威威猫不是一只普通的猫，普通的猫喜欢吃鱼，但威威猫最喜欢吃鸡腿。他每天都在不停的吃啊吃，吃了一只又一只鸡腿。现在他遇到了一个难题，如果他的体重太胖那么他的主人就不给他吃鸡腿了，所以他需要你的帮助。威威猫的身体由 n 个器官构成，由于他的身体很特殊所以他的增长也很特殊（不要问为什么，喜欢吃鸡腿的猫已经够奇怪了）。他的增长有个 k1 和 k2 系数，而且每天的增长量和前一天有关，我们假设这 n 个器官在第 i 天的数值分别是 a(i,1),a(i,2),a(i,3)a(i,n)，那么，第
2、i+1 天他每个器官的数值就会变成:a(i+1,1)=k1*a(i,1)+k2*a(i,2)a(i+1,2)=k1*a(i,2)+k2*a(i,3).a(i+1,n)=k1*a(i,n)+k2*a(i,1)威威猫的体重等于他的所有器官的数值之和，并且他还拥有一个特殊的机能，就是会自动检测自己的体重，如果他的体重比 K 大，那么就会自动停止生长（为了每天都能吃到鸡腿），由于威威猫的特殊身体构造他的体重是可能会变成负数的。现在我给你 n 个器官的初始数值和他的增长系数 k1,k2，请问他几天之后会停止生长，如果他永远无法停止生长那么就输出inf。(引号不用输出)InputInputInputInp
3、ut输入数据第一行是一个正整数 T，表示有 T 组测试数据；每组数据的第一行包含 4 个数字 n,k1,k2,k，代表威威猫有 n 个器官，他的生长系数是k1,k2，当体重超过 k 的时候他就停止生长。接下来的一行是 n 个数 ai，代表威威猫每个器官第一天的数值是多少。TechnicalTechnicalTechnicalTechnicalSpecificationSpecificationSpecificationSpecificationT=1001=n=10000-100=k1,k2=1001=k=10181=ai=1000（1=i=n）OutputOutputOutputOutput
4、对于每组测试数据，请首先输出Case#X:，X 代表测试用例的编号，然后输出一个数ans，代表 ans 天之后他会停止生长，如果不会停止就输出 inf.具体可参见 sample output。SampleSampleSampleSampleInputInputInputInput251 11011 11 151 150011 11 1SampleSampleSampleSampleOutputOutputOutputOutputCase#1:2Case#2:71002 威威猫系列故事拼车记Time Limit:0.2 SecondsMemoryLimit:65536K话说威威猫有一次去参加比赛
5、，虽然学校离比赛地点不太远，但威威猫还是想坐出租车去。大学城的出租车总是比较另类，有“拼车”一说，也就是说，你一个人坐车去，还是一堆人一起，总共需要支付的钱是一样的（每辆出租上除司机外最多坐下 4 个人）。刚好那天同校的一群 Acmer 在校门口扎堆了，大家果断决定拼车去赛场。问题来了，一辆又一辆的出租车经过，但里面要么坐满了乘客，要么只剩下一两个座位，众 Acmer 都觉得坐上去太亏了，威威猫也是这么想的。假设 N 名 Acmer 准备拼车，此时为 0 时刻，从校门到目的地需要支付给出租车师傅 D元（按车次算，不管里面坐了多少 Acmer），假如 S 分钟后恰能赶上比赛，那么 S 分钟后经过
6、校门口的出租车自然可以忽略不计了。现在给出在这 S 分钟当中经过校门的所有的 K 辆出租车先后到达校门口的时间Ti及里面剩余的座位Zi(1=Zi=4)，Acmer 可以选择上车几个人（不能超过），当然，也可以选择上 0 个人，那就是不坐这辆车。俗话说，时间就是金钱，这里威威猫把每个 Acmer 在校门等待出租车的分钟数等同于花了相同多的钱（例如威威猫等待了 20 分钟，那相当于他额外花了 20 元钱）。在保证所有 Acmer 都能在比赛开始前到达比赛地点的情况下，聪明的你能计算出他们最少需要花多少元钱么？InputInputInputInput输入第一行为 T，表示有 T 组测试数据。每组数据
7、以四个整数 N,K,D,S 开始，具体含义参见题目描述，接着 K 行，表示第 i 辆出租车在第 Ti 分钟到达校门，其空余的座位数为Zi（时间按照先后顺序）。TechnicalTechnicalTechnicalTechnicalSpecificationSpecificationSpecificationSpecification T=50N=100K=100D=100S=1001=Zi=41=T(i)=T(i+1)=SOutputOutputOutputOutput对于每组测试数据，输出占一行，如果他们所有人能在比赛前到达比赛地点，则输出一个整数，代表他们最少需要花的钱（单位：元），否则请
8、输出“impossible”。SampleSampleSampleSampleInputInputInputInput12 2 10 51 12 2SampleSampleSampleSampleOutputOutputOutputOutput141003 小明系列故事玩转十滴水Time Limit:0.2 SecondsMemoryLimit:32768K小明最近喜欢上了一个名为十滴水的游戏。游戏是在一个 6*6 的方格内进行的，每个格子上有一滴水或者没有水滴。水滴分为四个等级 14。初始时你有十滴水，通过把水加入格子内的水滴，会让水滴升 1 级。你也可以把水放到空格子内，这样会在这个格子里
9、面产生一个 1 级的水滴。当水滴等级大于 4 时则会爆裂为四个小水滴，并向四个方向飞溅。每个飞溅的小水滴碰到其他水滴后会融入其中，使其升一级或者爆裂，以此类推。飞溅的小水滴互不干扰，运动速度相等(1 秒可以移动一个格子的距离)。水滴爆裂后就消失掉了。InputInputInputInput题目包含多组测试用例；对于每组数据，首先是 6 行，每行有 6 个整数数字，每个数字的范围为 04；当数字为 0 时，表示空格子，当数字为 14 时，表示 14 级的水滴；然后第七行是一个整数 m，表示有 m 个操作；接下来是 m 行，每行有两个整数 x,y，表示在(x,y)放入一滴水。特别说明：每次都是在全
10、部的水滴静止后才进行下一次操作，也就是说只有在方格内没有任何飞溅的小水滴时才能放入一滴水。TechnicalTechnicalTechnicalTechnicalSpecificationSpecificationSpecificationSpecification1=m=101=x,y=6OutputOutputOutputOutput对于每组测试数据，请输出 m 个操作之后 6*6 方格内水滴的样子，每组数据的输出后面跟着一个空行。SampleSampleSampleSampleInputInputInputInput0 0 0 4 0 40 0 0 0 0 01 0 0 4 0 40 0
11、 0 0 0 00 0 0 0 0 00 0 0 1 0 011 60 0 0 4 0 40 2 0 4 0 40 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 011 62 2 0 2 0 33 3 0 1 3 12 2 2 4 0 42 4 4 2 2 33 3 2 4 0 11 3 4 3 0 165 35 33 33 22 16 3SampleSampleSampleSampleOutputOutputOutputOutput0 0 0 0 0 00 0 0 0 0 02 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 2
12、0 00 0 0 0 0 00 3 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 4 0 2 0 30 0 0 4 3 20 0 0 0 0 00 0 0 0 4 40 0 0 0 0 44 0 0 0 0 3HintHintHintHint第一组数据：(1,6)爆裂，然后在第二秒(1,4)(2,6)爆裂，在第四秒，两滴水同时到达(3,4),(3,4)变成了 6，爆裂，然后在第七秒(3,1)(6,4)变成了 2。1004 小明系列故事捉迷藏Time Limit:0.2 SecondsMemoryLimit:32768K小明的妈妈生了三
13、个孩子，老大叫大明，老二叫二明，老三.，老三自然就叫小明了。一天，小明的妈妈带小明兄弟三人去公园玩耍，公园里面树木很多，有很多地方可以藏身，于是他们决定玩捉迷藏。经过几轮的猜拳后，第一轮是小明来找其他两个人，游戏规则很简单：只要小明可以在规定的时间内找到他们就算小明获胜，并且被发现的两个人猜拳决定谁在下一轮负责找人；如果在规定的时间内只找到一个人，那么没有被发现的人获胜，被找到的人下一轮负责找人；如果在规定的时间内一个人都没有找到，则小明失败了，下一轮还是他来找人。现在小明想知道，在规定时间内，自己是否可以找到所有的人，现在他想请你来帮忙计算一下。为了简单起见，把公园看成是 n 行 m 列的矩
14、阵，其中S表示小明，D表示大名，E表示二明，X表示障碍物，.表示通路。这里，我们把发现定义为，可以直接看到对方，也就是说两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方。并且假设，大明，二明藏好以后就不会再改变位置，小明每个单位时间可以从当前的位置走到相邻的四个位置之一，并且不会走出公园。InputInputInputInput测试数据第一行是一个正整数 T，表示有 T 组测试数据。每一组测试数据首先是三个正整数 n,m,t，分别表示行数、列数和规定的时间，接下来 n 行，每行 m 个上述的字符，并且保证有且只有一个S，一个E，一个D。TechnicalTechnica
15、lTechnicalTechnicalSpecificationSpecificationSpecificationSpecificationT 2003=n,m=1000=t=100OutputOutputOutputOutput每组先输出一行 Case c:(c 表示当前的组数，从 1 开始计数)；接下来一行，如果小明可以在规定时间内找到所有的人，则输出最少需要的时间，否则输出-1。SampleSampleSampleSampleInputInputInputInput35 6 3XXD.E.X.S.5 6 3XDX.E.S.5 6 8XXDX.XEX.S.SampleSampleSamp
16、leSampleOutputOutputOutputOutputCase 1:-1Case 2:3Case 3:-11005 郑厂长系列故事N 骑士问题Time Limit:3.0 SecondsMemoryLimit:65536K郑厂长不是正厂长也不是副厂长他根本就不是厂长还是那个腾讯公司的码农一个业余时间喜欢下棋的码农最近，郑厂长对八皇后问题很感兴趣，拿着国际象棋研究了好几天，终于研究透了。兴奋之余，坐在棋盘前的他又开始无聊了。无意间，他看见眼前的棋盘上只摆了八个皇后，感觉空荡荡的，恰好又发现身边还有几个骑士，于是，他想把这些骑士也摆到棋盘上去，当然棋盘上的一个位置只能放一个棋子。因为受八
17、皇后问题的影响，他希望自己把这些骑士摆上去之后，也要满足每 2 个骑士之间不能相互攻击。现在郑厂长想知道共有多少种摆法，你能帮助他吗？骑士的下法：每步棋先横走或直走一格，然后再往外斜走一格；或者先斜走一格，最后再往外横走或竖走一格（即走“日”字）。可以越子，没有中国象棋的蹩马腿限制。InputInputInputInput输入第一行为一个整数 T(1=T=8)，表示有 T 组测试数据；每组数据首先是一个整数 N(1=n=10)，表示要摆 N 个骑士上去；接下来是一个 8*8 的矩阵来描述一个棋盘，.表示这个位置是空的，*表示这个位置上已经放了皇后了；数据中的初始棋盘保证是一个合法的八皇后摆法。OutputOutputOutputOutput对每组数据，请在一行内输出一个整数，表示合法的方案数。SampleSampleSampleSampleInputInputInputInput21*.*.*.*.*.*.*.*.2*.*.*.*.*.*.*.*.SampleSampleSampleSampleOutputOutputOutputOutput561409