腾讯马拉松编程赛题.doc

《腾讯马拉松编程赛题.doc》由会员分享，可在线阅读，更多相关《腾讯马拉松编程赛题.doc（21页珍藏版）》请在沃文网上搜索。

1、4500小Q系列故事屌丝的逆袭 Time Limit:0.1 Seconds Memory Limit:65536K一段时间以后，随着对工作环境以及同事的熟悉，小Q逐渐放松下来，在工作间隙，他细细观察了自己的工作环境，发现整个工作室是一个N行M列的矩形布局，或者是因为屌丝的本性逐步暴露，他还暗自给每个同事在心里进行了魅力值评分（为区别男女，男生一律用负整数表示，女生一律用正整数表示）。现在，小Q把所有人的数据记录下来，并且这样定义一个位置的价值：一个位置的价值只和其上下左右四个邻居的魅力值有关（对于靠边的位置，只考虑其存在的邻居）；如果某位置的邻居和该位置主人性别不同，则总分加上邻居魅力值的绝

2、对值，否则减去；对周围所有邻居的数据处理后，最终的得分即为这个位置的最终得分，得分越高，则该位置越好；现在你能帮助小Q计算一下哪里才是最佳位置吗？Input 输入包含多组测试数据；每组测试数据的第一行包含2个整数N和M，表示工作室的布局是N行M列；接下来的N行，每行有M个整数，分别表示对应位置员工的魅力值数据Ki，正整数表示女生的魅力值，负整数表示男生的魅力值；N和M为0的时候表示输入数据结束。Technical SpecificationN=20M=20-100=Ki=100Output 请计算并输出最佳位置的行列号以及对应的得分，如果得分最高的位置有多个，则请输出行号最小的那个，行号还相同

3、的话，再比较列号，只输出列号最小的那个即可。Sample InputSample Output2 31 2 1110025 -4 3-6 3 74501小明系列故事买年货 Time Limit:2.0 Seconds Memory Limit:65536K还没看完通知，小明就高兴的要死，因为他就是都尚的会员啊。迫不及待的小明在超市逛了一圈发现超市里有n件他想要的商品。小明顺便对这n件商品打了分，表示商品的实际价值。小明发现身上带了v1的人民币，会员卡里面有v2的积分。他想知道他最多能买多大价值的商品。Input 输入包含多组测试用例。每组数据的第一行是四个整数n，v1，v2，k；然后是n行，每

4、行三个整数a，b，val，分别表示每个商品的价钱，兑换所需积分，实际价值。Technical Specification1 = n = 1000 = v1, v2 = 1000 = k = 50 = a, b, val = 100Ps. 只要钱或者积分满足购买一件商品的要求，那么就可以买下这件商品。Output对于每组数据，输出能买的最大价值。详细信息见Sample。 Sample InputSample Output5 1 6 14 2 5 0124 3 30 1 040 3 24 4 12 3 33 3 43 3 23 4 41 0 24502吉哥系列故事临时工计划 Time Limit:

5、1.0 Seconds Memory Limit:32768K已知吉哥一共有m天的假期，每天的编号从1到m，一共有n份可以做的工作，每份工作都知道起始时间s，终止时间e和对应的工资c，每份工作的起始和终止时间以天为单位(即天数编号)，每份工作必须从起始时间做到终止时间才能得到总工资c，且不能存在时间重叠的工作。比如，第1天起始第2天结束的工作不能和第2天起始，第4天结束的工作一起被选定，因为第2天吉哥只能在一个地方工作。现在，吉哥想知道怎么安排才能在假期的m天内获得最大的工资数（第m+1天吉哥必须返回学校，m天以后起始或终止的工作是不能完成的）。Input 第一行是数据的组数T； 每组数据的第

6、一行是2个正整数：假期时间m和可做的工作数n；接下来n行分别有3个正整数描述对应的n个工作的起始时间s，终止时间e，总工资c。Technical Specification1=T=10009m=1000n=1000s=100, e=100, s=ec=10000Output对于每组数据，输出吉哥可获得的最高工资数。Sample InputSample Output110210 51 5 1003 10 105 10 1001 4 26 12 2664503 湫湫系列故事植树节 Time Limit:0.5 Seconds Memory Limit:32768K湫湫老师的班里要选出3个小朋友。已

7、知湫湫的班里共有n个孩子，每个孩子有Bi个朋友(i从1到n)，且朋友关系是相互的，如果a小朋友和b小朋友是朋友，那么b小朋友和a小朋友也一定是好朋友。为了选择的公平性，湫湫老师会随机抽取3个小朋友出来(每个人被抽到的概率相同)，但是她很希望这3个小朋友之间的关系完全相同，湫湫老师想请你帮她算算抽到的3个小朋友正好关系相同的概率是多少？PS. 关系相同就是指要么3个人互相是好朋友，要么3个人互相都不是好朋友。Input 输入数据第一行是一个整数T(1=T=1000)，表示输入数据的组数；每组数据的第一行是一正整数n表示孩子的总数(2n=1000)，第二行有n个数Bi (i从1到n)，分别代表每个

8、小朋友的朋友的个数。Output 对于每组数据，请输出抽到的3个小朋友关系相同的概率，结果保留3位小数。Sample InputSample Output10.40053 3 3 3 44504 威威猫系列故事篮球梦 Time Limit:0.1 Seconds Memory Limit:32768K一场NBA篮球比赛总共48分钟，假如我们现在已经知道当前比分 A:B，A代表我方的比分，B代表对方的比分，现在比赛还剩下t秒时间。我们简单的认为双方各自进攻一次的时间皆固定为15秒（不到15秒则进攻不得分），且为交替进攻，即我方进攻一次，接着对方进攻，依次循环。进攻有三种选择方式：（这里不考虑命中

9、率） 造犯规，（假设都两罚一中）得1分；中距离投篮 得2分；三分球 得3分。为了简化问题，假设在对方回合，由于我方防守比较好，只让对手得1分，且为固定，即对方的进攻回合就为每回合得1分。现在比赛进入最后关头，接下来第一个回合是我方进攻，现在威威猫想要知道教练有多少种不同的选择能使我方可能赢得比赛（可能的意思就是不考虑命中率的情况）。Input 输入有多组数据（不超过250组）；每组数据包含3个整数A，B和t，其中A和B 表示当前的比分（0 = A, B = 200），t表示还剩多少时间（单位秒 0 = t = 600）。Output请输出可行的方案数，每组数据输出占一行。Sample Inpu

10、tSample Output88 90 506Hint：样例解析：当前比分是88：90，还剩50秒则对方还最多有一次进攻机会（最后5秒进攻不成功），我方有两次，对方的最终得分将是91，我方至少在两回合中拿到4分才能胜利，所以所有方案数是6种，即：第一球 第二球1 32 22 33 13 23 34505 小Q系列故事电梯里的爱情Time Limit:0.1 Seconds Memory Limit:65536K于是，小便在陪伴女神的同时，也关注着电梯中显示的楼层数字，并且他注意到电梯每向上运行一层需要秒钟，向下运行一层需要4秒钟，每开门一次需要秒（如果有人到达才开门），并且每下一个人需要加秒。

11、特别指出，电梯最开始在层，并且最后必须再回到层才算一趟任务结束。假设在开始的时候已知电梯内的每个人要去的楼层，你能计算出完成本趟任务需要的总时间吗?这是个很简单的问题，要知道，小Q已经修炼到快速心算出结果的境界，现在你来编程试试吧！Input输入首先包含一个正整数C，表示有C组测试用例。接下来C行每行包含一组数据，每组数据首先是一个正整数N，表示本次乘坐电梯的人数，然后是N个正整数Ai，分别表示大家要去的楼层。C=100 N=15 Ai=100Output请计算并输出完成一趟任务需要的时间，每组数据输出占一行。Sample Input Sample Output2 594 2 4 3 2 10

12、83 10 10 104506小明系列故事师兄帮帮忙Time Limit:1.0 Seconds Memory Limit:32768K题目是这样的：给你n个数字，分别是a1,a2,a3,a4,a5an，这些数字每过一个单位时间就会改变，假设上一个单位时间的数字为a1,a2,a3an，那么这个单位时间的数字ai = ai - 1 * K(i = 1的时候a1 = an * K)，其中K为给定的系数。现在的问题就是求第t单位时间的时候这n个数字变成了什么了？由于数字可能会很大，所以只要你输出数字对109 + 7取余以后的结果。Input输入数据第一行是一个正整数T，表示有T组测试数据；每组数据有

13、两行，第一行包含输入三个整数n,t,k，其中n代表数字个数，t代表第t个单位时间，k代表系数；第二行输入n个数字ai，代表每个数字开始的时候是多少。T = 100,1 = n = 10 4,0 = t = 10 9,其中 t = 0 表示初始状态,1 = k = 10 9,1 = ai= 10 9Output 对于每组数据请输出第t单位时间后这n个数字变成了什么，输出的时候每两个数字之间输出一个空格，行末不要输出多余的空格，具体见样例。Sample Input Sample Output2 50 75 253 2 5 3 0 5 1 2 31 2 3 1 2 34507 吉哥系列故事恨7不成妻

14、 Time Limit:0.5 Seconds Memory Limit:65536K吉哥观察了214和77这两个数，发现：2+1+4=77+7=7*277=7*11最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！什么样的数和7有关呢？如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关整数中某一位是7；整数的每一位加起来的和是7的整数倍；这个整数是7的整数倍；现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。Input 输入数据的第一行是case数T(1 = T = 50)，然后接下来的T行表示T个case;每个case在一行内包含两

15、个正整数L, R(1 = L = R = 1018)。Output 请计算L,R中和7无关的数字的平方和，并将结果对109 + 7 求模后输出。Sample Input Sample Output3 2361 9 22110 11 017 174508 湫湫系列故事减肥记I Time Limit:1.0 Seconds Memory Limit:65536K为了方便你制作食谱，湫湫给了你每日食物清单，上面描述了当天她想吃的每种食物能带给她的幸福程度，以及会增加的卡路里量。Input 输入包含多组测试用例。每组数据以一个整数n开始，表示每天的食物清单有n种食物。 接下来n行，每行两个整数a和b，

16、其中a表示这种食物可以带给湫湫的幸福值（数值越大，越幸福），b表示湫湫吃这种食物会吸收的卡路里量。最后是一个整数m，表示湫湫一天吸收的卡路里不能超过m。11 = n = 100 0 = a,b = 100000 1 = m = 100000Output对每份清单，输出一个整数，即满足卡路里吸收量的同时，湫湫可获得的最大幸福值。Sample Input Sample Output3 5 103 3 1 1 207 7 5 39 9 10 310 6 8 7 5 64509 湫湫系列故事减肥记II Time Limit:2.0 Seconds Memory Limit:65536K湫湫实在太忙了，

17、所以没时间去算一天有多少时间可以用于锻炼，现在她把每日行程告诉你，拜托你帮忙算算吧皮埃斯：一天是24小时，每小时60分钟Input输入数据包括多组测试用例。每组测试数据首先是一个整数n，表示当天有n件事要做。 接下来n行，第i行是第i件事的开始时间和结束时间，时间格式为HH:MM。1 = n = 500000 00 = HH = 23 00 = MM = 59Output 请输出一个整数，即湫湫当天可以用于锻炼的时间（单位分钟）Sample Input Sample Output1 4 125615:36 18:40 01:35 10:36 179 04:54 22:36 10:18 18:4

18、0 11:47 17:53 hint 大量输入，建议用scanf读数据。4510 小Q系列故事为什么时光不能倒流Time Limit:0.1 Seconds Memory Limit:65536K假设现在已知当前的时间，让时间倒退回若干，你能计算出钟表显示的时间吗？Input输入首先包含一个整数N，表示有N组测试用例。接下来的N行表示N个测试用例，每行包括2个时间HH:MM:SS hh:mm:ssHH:MM:SS表示当前的时间，hh:mm:ss表示希望倒退回去的时间。Technical Specification00=HH=1100=hh=9900=MM, SS, mm, ss 2 - 3，那

19、么就要求小明来的时候走过的路径不能包含有1 - 2 - 3这部分，但是1 - 3 或者1 - 2都是可以的，这样的限制路径可能有多条。特别说明，如果1 2 3这三个点共线，但是小明是直接从1到3然后再从3继续，那么此种情况是不认为小明经过了2这个点的。Input输入包含多组样例，每组样例首先包含两个整数n和m，其中n代表有n个点，小明在1号点，女朋友在n号点，m代表小明的女朋友有m个要求；接下来n行每行输入2个整数x 和y（x和y均在int范围），代表这n个点的位置（点的编号从1到n）；再接着是m个要求，每个要求2行，首先一行是一个k，表示这个要求和k个点有关，然后是顺序给出的k个点编号，代表

20、小明不能走k1 - k2 - k3 - ki这个顺序的路径；n 和 m等于0的时候输入结束。Technical Specification2 = n = 501 = m = 1002 = k = 5Output对于每个样例，如果存在满足要求的最短路径，请输出这个最短路径，结果保留两位小数；否则，请输出”Can not be reached!” （引号不用输出）。Sample InputSample Output3 12 15 32.001 10 00 0Can not be reached!2 11 15 321.653 12 1 221 21 221 25 2131 2 32 4 521 5

21、4512 吉哥系列故事完美队形ITime Limit:1.0 Seconds Memory Limit:65536K有一天，有n个人按顺序站在他的面前，他们的身高分别是h1, h2 . hn，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则称之为完美队形：1.挑出的人保持他们在原队形的相对顺序不变；2.左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然，如果m是奇数，中间那个人可以任意；3.从左到中间那个人，身高需保证递增，如果用H表示新队形的高度，则H1 H2 H3 . Hmid。最多能选出多少人组

22、成完美队形？ Input第一行输入T，表示总共有T组数据(T = 20)；每组数据先输入原先队形的人数n(1=n = 200)，接下来一行输入n个整数，表示按顺序从左到右原先队形位置站的人的身高（50 = h = 250，不排除特别矮小和高大的）。Output请输出能组成完美队形的最多人数，每组数据输出占一行。Sample InputSample Output233441 2 11 2 2 14513 吉哥系列故事完美队形IITime Limit:1.0 Seconds Memory Limit:65536K假设有n个人按顺序站在他的面前，他们的身高分别是h1, h2 . hn，吉哥希望从中挑

23、出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形：1.挑出的人保持原队形的相对顺序不变，且必须都是在原队形中连续的；2.左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然如果m是奇数，中间那个人可以任意；3.从左到中间那个人，身高需保证不下降，如果用H表示新队形的高度，则H1 = H2 = H3 . = Hmid。最多能选出多少人组成新的完美队形呢？ Input输入数据第一行包含一个整数T，表示总共有T组测试数据(T = 20)；每组数据首先是一个整数n(1 = n = 100000)，表示原先队形

24、的人数，接下来一行输入n个整数，表示原队形从左到右站的人的身高（50 = h = 250，不排除特别矮小和高大的）。Output请输出能组成完美队形的最多人数，每组输出占一行。Sample InputSample Output233441 2 11 2 2 14514湫湫系列故事设计风景线Time Limit:3 Seconds Memory Limit:65536K新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？其中

25、，可以兴建的路线均是双向的，他们之间的长度均大于0。Input测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。Technical Specificationn=100000 m = 10000001= u, v = n w = 1000Output对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。Sample InputSample Output3 3YES1 2 12 3 13 1 14515 小Q系列故事世界上最遥远的距

26、离Time Limit:0.2 Seconds Memory Limit:65536K在腾讯第二届编程马拉松大赛进行到第5天的时候（即2013年3月24日），假设已知现在的日期和穿越的天数D，你能计算出小Q和女友各自到达的年代吗？Input输入首先包含一个整数N，表示有N组测试用例；接下来N行是N组数据，每一行包含一个正整数D（D=10,0000），D表示向前穿越的天数。Output请计算并输出小Q和女友分别到达的日期，日期格式为YYYY/MM/DD，两个日期中间用一个空格隔开，每组数据占一行，具体输出格式请参见样例。Sample InputSample Output22013/03/30 2

27、013/03/1862013/04/23 2013/02/22304516威威猫系列故事因式分解Time Limit:0.2 Seconds Memory Limit:65536K在我们学习数学的过程中，经常需要把一个多项式进行因式分解，也就是把它写成乘积的形式，比如多项式x2+3x+2分解因式的结果就是(x+1)(x+2)。这个因式一眼就能看出来，但是当x的指数更高时，就不太容易分解了。现在，威威猫就是在研究如何编写程序来实现对多项式的因式分解。Input输入第一行是一个整数T(T=50)，表示测试数据的组数；接下来是T行字符串表示T个测试用例，每行1个数学多项式，多项式长度不会超过100个

28、字符，每个多项式表示形式如下：A1xP1+A2xP2+.+AmxPm其中0=Pi=5，Ai表示xPi的系数，Ai=0时直接简写为0,Ai=1和-1时分别简写为xPi与-xPi，Pi=0和1时分别简写为Ai与Aix，且同一指数r的对应项系数之和的绝对值不超过1000, 每行中没有多余空格，具体格式可参考Sample Input。Output对于每组测试数据，首先输出Case #X: ，X代表多项式编号，从1开始计数，然后输出因式分解的结果，分解结果的表示形式规定如下：(x+B1)(x+B2).(x+Bm)其中，B1=B2=.=Bm,若Bi=0则不加括号直接简写为x，如果无法表现成上述格式，则输出

29、-1。具体可参考Sample Output。Sample InputSample Output4Case #1: xxCase #2: (x+1)x+1Case #3: (x-1)xx-2x2+x2+x3Case #4: -12x+24517小小明系列故事游戏的烦恼Time Limit:1.0 Seconds Memory Limit:32768K小小明最近在玩一款游戏，它由n*m大小的矩阵构成，矩阵上会随机产生一些黑色的点，这些点它们可能会连在一起也可能会分开，这些点的个数没有限制，但是每个1*1方格中最多只可能有一个黑点产生。游戏要求玩家以最短的时间用x*y的小矩阵覆盖这个大矩阵，覆盖的要

30、求有以下2点：1. x*y大小的小矩阵内必须有x*y个黑点。2. 多个小矩阵可以重叠，但是每个小矩阵放置的位置必须是独一无二的，即不同的小矩阵内的黑点不能完全相同。例如1*2的矩阵可以横着放，也可以竖着放，这两种方法是不同的，即使它们可能共用黑点。能不能告诉烦恼中的小小明这个大矩阵里有多少个满足要求的小矩阵呢？Input题目有多组测试数据（不多于100个）；每组测试数据的第一行包含2个正整数n和m，然后第二行是x和y（n，m，x，y的意思如题），接下来n行，每行m个字符，其中 * 表示黑点， . 表示空白。n和m为0则结束输入。Technical Specification0 n, m = 2

31、0000 x, y = 1000Output 请计算并输出一共有多少个满足要求的小矩阵，每组输出占一行。Sample InputSample output2 331 2*.*0 04518吉哥系列故事最终数Time Limit:0.2 Seconds Memory Limit:65536K假如我们现在已知斐波那契数是1，1，2，3，5，8，13，21，34，55，89.由于吉哥特别喜欢斐波那契数，它希望每个数中都包含斐波那契数，比如说130，其中包含了13，或者5534包含了55和34，只要数位中含有至少一个斐波那契数就是吉哥想要的数。但是这种数实在太多了，于是它去掉那些仅仅含有小于10的斐波

32、那契数的数，比如说1，仅仅含有1，所以被去掉；或者335只含有3和5，都是小于10的斐波那契数，所以也去掉；但是131是留下的，因为它含有13，我们暂且称这类数为F数,不难得到前几个F数是 13 ，21， 34， 55， 89，113，121，130，131.霸气的吉哥觉得这样还不够，它想将斐波那契进行到底在前面F数的基础上，吉哥要得到那些是第斐波那契数个的F数！就是说，我们假设F数从1开始标号，那么13是第1个F数，吉哥想要那些在F数中的排列或者说下标也要是斐波那契数的数，吉哥称之为最终数，如13，21，34，89，130.现在给你一个数n，吉哥想知道离n最近的最终数与n的差的绝对值是多少。

33、Input输入包含多组测试数据。每组测试数据包含一个整数n ( 1 = n = 1011)；若n = -1，表示输入结束。Output对于每个n，请输出离n最近的最终数与n的差的绝对值。Sample InputSample Output11210011-14519郑厂长系列故事体检Time Limit:1.0 Seconds Memory Limit:32768K这次总共有N位员工接受体检，并且每个员工都需要做K个项目的检查才算完成整个体检的流程。现在来了M个医生为员工做身体检查，并且每一位医生都带齐了检查这K个项目的器材来(也就是说每个医生都能进行这K个项目中的任意一项检查)。体检的详细流程

34、是这样的：公司事先制定好了M份体检单，每个医生手上都各自拿到一份体检单，上面已经安排好了检查的次序，以及每一次检查所对应的员工和项目。每个医生按照体检单上的次序为相应的员工做相应的项目检查。医生拿到的体检单上的名单也可以是空的，就是这个医生不需要检查任何员工的任何项目。当然，制定出的这M份体检单不能有问题存在，否则就会有混乱的情况发生。按照常理来说，同一个医生在同一时间只能为一个员工做一个项目的检查。另外，同一个员工在同一时间也只能进行一个项目的检查，当然，不同的医生或不同的员工可以在同一时间进行项目检查。现在假设每个员工的每个项目的检查时间都是一分钟（其它时间花费忽略不计，只考虑项目检查工作

35、所花费的一分钟)。公司希望体检的工作越快完成越好，由于郑厂长大学期间曾经是一个ACMer，所以公司就将体检的安排工作交给了他，他需要计算出最快需要多少分钟能完成所有员工的体检工作。Input输入的第一行为一个正整数T，表示有T组测试数据；接下去有T组测试数据，每组测试数据占一行，包含三个整数N，K，M，N表示员工的人数，K表示体检的项目数，M表示医生的人数。Technical SpecificationT=1000,1=N=100,1=K=10,1=M=100Output对于每组数据，输出一个整数，表示最快需要多少分钟才能完成所有员工的体检工作。Sample InputSample Outpu

36、t222 1 133 2 2Hint：对于第二组数据体检单的安排可以是如下情况：第1个医生的体检单：员工A的项目1、员工A的项目2、员工B的项目2；第2个医生的体检单：员工B的项目1、员工C的项目1、员工C的项目2。第一分钟：第1个医生检查员工A的项目1，而第2个医生检查员工B的项目1；第二分钟：第1个医生检查员工A的项目2，而第2个医生检查员工C的项目1；第三分钟：第1个医生检查员工B的项目2，而第2个医生检查员工C的项目2；这样就只需要3分钟即可完成体检工作。4520 小Q系列故事最佳裁判Time Limit:0.2 Seconds Memory Limit:65536K其中，最终得分是这

37、样计算的：N个人打分，去掉一个最高分，去掉一个最低分，然后剩余分数相加，再除以N-2即为最终得分。Input输入包含多组测试用例。每组测试用例首先是一个整数N，表示裁判的人数，然后接着是N个实数，表示N个裁判的打分Pi，N为0时结束输入。Technical Specification5 = N = 20,0=Pi=10Output请计算并输出最佳裁判的编号，每组数据输出占一行，若有多人并列最佳裁判，只要求输出编号最小的那个。特别说明：裁判编号按照打分的顺序从1开始，依次类推，最后一人编号为N。Sample InputSample Output5 8.3 9.2 8.7 8.9 9.040452

38、1小明系列问题小明序列Time Limit:1.0 Seconds Memory Limit:32768K提起小明序列，他给出的定义是这样的：首先定义S为一个有序序列，S= A1 , A2 , A3 , . , An ，n为元素个数 ；然后定义Sub为S中取出的一个子序列，Sub= Ai1 , Ai2 , Ai3 , . , Aim ，m为元素个数 ；其中Sub满足 Ai1 Ai2 Ai3 . Aij-1 Aij Aij+1 . d (1 j = m， d为给定的整数)；显然满足这样的Sub子序列会有许许多多，而在取出的这些子序列Sub中，元素个数最多的称为“小明序列”(即m最大的一个Sub子

39、序列)。例如：序列S=2,1,3,4 ，其中d=1；可得“小明序列”的m=2。即Sub=2,3或者2,4或者1,4都是“小明序列”。当小明发明了“小明序列”那一刻,情绪非常激动，以至于头脑凌乱，于是他想请你来帮他算算在给定的S序列以及整数d的情况下，“小明序列”中的元素需要多少个呢？Input输入数据多组，处理到文件结束;输入的第一行为两个正整数 n 和 d(1=n=105 , 0=d=105);输入的第二行为n个整数A1 , A2 , A3 , . , An，表示S序列的n个元素(0=Ai=105)。Output请对每组数据输出“小明序列”中的元素需要多少个，每组测试数据输出一行。Sampl

40、e InputSample Output2 05 15 221 23 4 5 1 23 4 5 1 2214522 湫湫系列故事过年回家Time Limit:0.2 Seconds Memory Limit:32768K 假设湫湫有可能经过的n个城市分别编号从1到n，湫湫要从城市A回到城市B，购票网站上列出了t辆列车行程，每辆车的行程用一个字符串表示，途径的城市间用+号相连，如1+2+3+5代表一辆从1城市分别经过2，3到达5的火车，湫湫可以从中间任意一站出发和下车（路径是单向的，即必须沿字符串从左到右来走），每个字符串对应着一个整数k，k=0表示该车只有硬座，k=1表示该车有卧铺也有硬座，在

41、整个回家的计划中，同一辆车可以坐无限次，为了中途换车的方便，如果在起点坐的是卧铺，则后面乘坐的车必须全是卧铺，同样的，如果在起点坐的是硬座，则后面乘坐的车必须全是硬座，假设一段（一辆车行程中，两相邻城市间为一段）硬座的不舒适度是D1，一段卧铺的不舒适度是D2，求湫湫回家最小的不舒适度。Input输入数据的第一行包含一个整数Q，表示测试数据的组数；每组数据的第一行是2个正整数n和t，分别表示城市数和列车数；接下来t行，每行一个字符串表示列车行程，字符串长度小于10000，每个字符串后跟一个整数k（k为0或1），之间用空格隔开；接下来一行是D1，D2，其含义见题目描述；最后一行是2个正整数A和B，表示起始和终点城市。Technical Specification1 = Q = 100,1 n = 200,1 t = 1000,0 D1 = 10000, 0 D2 = 10000，D1和D2的大小关系不确定,1 = A, B = n 且 A BOutput对于每组数据，如果湫湫可以到达目的地，则输出一个整数，表示湫湫到家所需的最小不舒适度。如果不能到达则直接输出-1。Sample InputSample Output146 52+4+3+5+1+6 15+4+2+3+1 13+2+5+1