程序设计比赛试题.doc

程序设计比赛试题最少钱币数：【问题描述】这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。【要求】【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1=M=2000，整数），接着的一行中，第一个整数K（1=K=10）表示币种个数，随后是K个互不相同的钱币面值Ki(1=Ki=1000)。输入M=0时结束。【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。【样例输入】156 2 5 10 20 50 10011 20【样例输出】2ImpossibleFeli的生日礼物【问题描述】Felicia的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n=10100*_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。【要求】【数据输入】每行一个n，直到输入数据结束【数据输出】对应输入的n，每行输出一个答案【样例输入】1101【样例输出】8蛇行矩阵【问题描述】蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。【要求】【数据输入】本题有多组数据，每组数据由一个正整数N组成。（N不大于100）【数据输出】对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。【样例输入】5【样例输出】1 3 6 10 152 5 9 144 8 137 1211青蛙的约会【问题描述】两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。【要求】【数据输入】输入只包括一行5个整数x，y，m，n，L，其中xy 2000000000，0 m、n 2000000000，0 L 2100000000。【数据输出】输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行Impossible【样例输入】1 2 3 4 5【样例输出】4敲七【问题描述】输出7和7的倍数，还有包含7的数字例如（17，27，37.70，71，72，73.）【要求】【数据输入】一个整数N。(N不大于30000)【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。【样例输入】20【样例输出】71417连续邮资问题【问题描述】G国发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，使得可在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。编程任务:对于给定的正整数m和n，计算出邮票面值的最佳设计。【要求】【数据输入】输入数据每一行给出2个正整数m和n的值（1=n，m=9），最后以0 0表示文件结束。【数据输出】对于输以假定(ai, aj) = 1.输出包含一个正整数，即为Andy家至少养猪的数目。【样例输入】33 15 17 2【样例输出】16kitty猫的基因编码【问题描述】kitty 的基因编码如下定义：kitty的基因由一串长度2k（k=8)的01序列构成，为了方便研究，需要把,01序列转换为ABC编码。用T（s)来表示01序列s的ABC编码T(s)A（当S全由0组成）T(s)B（当s全由1组成）T(s)C+T（s1)+T（s2)s1,s2为把s等分为2个长度相等的子串比如 T（00)=A T(00001111)=CAB【要求】【数据输入】一行，长度为2k，为kitty猫的01基因编码，有多个数据【数据输出】一行，由ABC构成的ABC编码【样例输出】01001011【样例输出】CCCABACCBAB取石子游戏【问题描述】有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。【要求】【数据输入】输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。【数据输出】输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。【样例输入】2 18 44 7【样例输出】010勇气的挑战【问题描述】给定n个点的坐标(x,y,z),且n=50,从点1出发,怎么样才能走一条路径,访问每个点一次且仅一次,使走过的距离和最小?【要求】【数据输入】多组数据.第1行n,然后n行3个整数坐标【数据输出】每组一行,代表最小权和【样例输入】30 0 01 1 01 -1 0【样例输出】3.4统计同成绩学生人数Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1608 Accepted Submission(s): 877【问题描述】读入N名学生的成绩，将获得某一给定分数的学生人数输出。 【要求】【数据输入】测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。第3行：给定分数当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。 【数据输出】对每个测试用例，将获得给定分数的学生人数输出。 【样例输出】380 60 9060285 660560 75 90 55 75750【样例输出】102钱币兑换问题Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 494 Accepted Submission(s): 247【问题描述】在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 【要求】【数据输入】每行只有一个正整数N，N小于32768。 【数据输出】对应每个输入，输出兑换方法数。 【样例输入】293412553【样例输出】71883113137761字串数Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 405 Accepted Submission(s): 90【问题描述】一个A和两个B一共可以组成三种字符串:ABB,BAB,BBA.给定若赶字母和它们相应的个数,计算一共可以组成多少个不同的字符串. 【要求】【数据输入】每组测试数据分两行,第一行为n(1=n=26),表示不同字母的个数,第二行为n个数A1,A2,.,An(1=Ai=12),表示每种字母的个数.测试数据以n=0为结束. 【数据输出】对于每一组测试数据,输出一个m,表示一共有多少种字符串. 【样例输入】21 232 2 20【样例输出】390小希的数表Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 201 Accepted Submission(s): 48【问题描述】Gardon 昨天给小希布置了一道作业，即根据一张由不超过5000的N(3=N=100)个正整数组成的数表两两相加得到N*(N-1)/2个和，然后再将它们排序。例如，如果数表里含有四个数1，3，4，9，那么正确答案是4，5，7，10，12，13。小希做完作业以后出去玩了一阵，可是下午回家时发现原来的那张数表不见了，好在她做出的答案还在，你能帮助她根据她的答案计算出原来的数表么？ 【要求】【数据输入】包含多组数据，每组数据以一个N开头，接下来的一行有按照大小顺序排列的N*(N-1)/2个数，是小希完成的答案。文件最后以一个0结束。假设输入保证解的存在性和唯一性。 【数据输出】对于每组数据，输出原来的数表。它们也应当是按照顺序排列的。 【样例输入】44 5 7 10 12 1345 6 7 8 9 100【样例输出】1 3 4 92 3 4 6士兵队列训练问题Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 462 Accepted Submission(s): 185【问题描述】某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。 【要求】【数据输入】本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。 【数据输出】共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。 【样例输入】22040 【样例输出】1 7 191 19 37最简单的计算机Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 287 Accepted Submission(s): 192【问题描述】一个名叫是PigHeadThree的研究组织设计了一台实验用的计算机，命名为PpMm。PpMm只能执行简单的六种命令A，B，C，D，E，F；只有二个内存M1，M2；三个寄存器R1，R2，R3。六种命令的含义如下：命令A：将内存M1的数据装到寄存器R1中；命令B：将内存M2的数据装到寄存器R2中；命令C：将寄存器R3的数据装到内存M1中；命令D：将寄存器R3的数据装到内存M2中；命令E：将寄存器R1中的数据和寄存器R2中的数据相加，结果放到寄存器R3中；命令F：将寄存器R1中的数据和寄存器R2中的数据相减，结果放到寄存器R3中。你的任务是：设计一个程序模拟PpMm的运行。 【要求】【数据输入】有若干组，每组有2行，第一行是2个整数，分别表示M1和M2中的初始内容；第二行是一串长度不超过200的由大写字母A到F组成的命令串，命令串的含义如上所述。 【数据输出】对应每一组的输入，输出只有一行，二个整数，分别表示M1，M2的内容；其中M1和M2之间用逗号隔开。其他说明：R1，R2，R3的初始值为0，所有中间结果都在-231和231之间。 【样例输入】100 288ABECED876356 321456ABECAEDBECAF【数据输出】388,3882717080,1519268愚人节的礼物Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 241 Accepted Submission(s): 168【问题描述】四月一日快到了，Vayko想了个愚人的好办法送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，B表示礼物，Vayko想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。 【要求】【数据输入】本题目包含多组测试，请处理到文件结束。每组测试包含一个长度不大于1000,只包含(,)和B三种字符的字符串，代表Vayko设计的礼物透视图。你可以假设，每个透视图画的都是合法的。 【数据输出】对于每组测试，请在一行里面输出愚人指数。 【样例输入】(B)()()(B)【样例输出】41整数对Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 111 Accepted Submission(s): 29【问题描述】Gardon 和小希玩了一个游戏，Gardon随便想了一个数A（首位不能为0），把它去掉一个数字以后得到另外一个数B，他把A和B的和N告诉了小希，让小希猜想他原来想的数字。不过为了公平起见，如果小希回答的数虽然不是A，但同样能达到那个条件（去掉其中的一个数字得到B，A和B之和是N），一样算小希胜利。而且小希如果能答出多个符合条件的数字，就可以得到额外的糖果。所以现在小希希望你编写一个程序，来帮助她找到尽可能多的解。例如，Gardon想的是A=31,B=3 告诉小希N=34，小希除了回答31以外还可以回答27（27+7=34）所以小希可以因此而得到一个额外的糖果。 【要求】【数据输入】输入包含多组数据，每组数据一行，包含一个数N(1=N=109)，文件以0结尾。 【数据输出】对于每个输入的N，输出所有符合要求的解（按照大小顺序排列）如果没有这样的解，输出No solution. 【样例输入】34152210【样例输出】27 31 32126 136 139 141No solution.寒冰王座Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 875 Accepted Submission(s): 358【问题描述】不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉，他决定给自己买一些道具，于是他来到了地精商店前.死亡骑士：“我要买道具！”地精商人：“我们这里有三种道具，血瓶150块一个，魔法药200块一个，无敌药水350块一个。”死亡骑士：“好的,给我一个血瓶。”说完他掏出那张N元的大钞递给地精商人.地精商人：“我忘了提醒你了，我们这里没有找客人钱的习惯的，多的钱我们都当小费收了的，嘿嘿。”死亡骑士：“”死亡骑士想，与其把钱当小费送个他还不如自己多买一点道具，反正以后都要买的，早点买了放在家里也好，但是要尽量少让他赚小费。现在死亡骑士希望你能帮他计算一下，最少他要给地精商人多少小费。 【要求】【数据输入】输入数据的第一行是一个整数T(1=T=100),代表测试数据的数量.然后是T行测试数据,每个测试数据只包含一个正整数N(1=N=10000),N代表死亡骑士手中钞票的面值.注意：地精商店只有题中描述的三种道具. 【数据输出】对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费. 【样例输入】2900250 【样例输出】050覆盖的面积Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 170 Accepted Submission(s): 60【问题描述】给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.【要求】【数据输入】输入数据的第一行是一个正整数T(1=T=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1=N13，12-23，13-12，13-32，23-21， 23-31。注意：文件里只有一个整数N(2N1000)。 【数据输出】输出一个整数，为可能的过程的总数除以10007的余数。【样例输入】4【样例输出】96猴子的争斗Time limit: 1s Memory limit: 32768K Total Submit : 184 Accepted Submit : 75 【问题描述】从前在一个森林里，有N只好斗的猴子。一开始，他们互不认识。互不认识的猴子间是无法避免争斗的，而且争斗只会发生在两只互不认识的猴子间。决斗结束后，这两只猴子和他们各自的朋友们通过这场决斗相互间都认识了，争斗便不会再发生在这一大群猴子中的任两只。由于争斗是比较激烈的，所以同一时间内不会有两场决斗一起发生。经过N-1次决斗后，这N只猴子间相互都认识了，现在问有多少种可能的决斗过程。例如N=3，有6种不同的过程：12-13，12-23，13-12，13-32，23-21， 23-31。【要求】【数据输入】文件里只有一个整数N(2N1000)。 【数据输出】输出一个整数，为可能的过程的总数除以10007的余数。【样例输入】4【样例输出】96排序Time limit: 10s Memory limit: 32768K Total Submit : 70 Accepted Submit : 2 【问题描述】通常我们对一个长度为n(n24)的整数数列进行排序操作，其实就是讲他们按照从小到大的顺序重整。一般情况下我们可以比较任意两个数之间的大小并交换他们的位置，但这里我们限制只能数列的某一个前缀序列翻转，除此之外的任何操作都是不允许的。更精确地说，假设数列a1，a2，an，一个合法的操作是把数列变为ak，ak-1，a2, a1, ak+1, ak+2, an，其中1kn。例如：数列3 2 1 4，可能的操作有三种，分别是2 3 1 4、1 2 3 4、4 1 2 3。你任务是求出一个序列用上面的方法排序至少需要多少步。【要求】【数据输入】输入文件有两行：第一行是一个整数n，表示数列的长度。第二行有n个整数，表示待排序的数列，每个整数的绝对值不大于32767。【数据输出】输出文件有一行是一个整数s，表示完成排序所需的最少步数。【样例输入】43 2 1 4【样例输出】1提示：只需要一步就可以完成排序：3 2 1 4 1 2 3 4。选址Time limit: 10s Memory limit: 32768K Total Submit : 100 Accepted Submit : 13 【问题描述】很久以前，在世界的某处有一个形状为凸多边形的小岛，岛上的居民们决定建一个祭坛，居民们认为祭坛的位置离岛的顶点处越远越好。你的任务是求凸多边形内一点，使其与各顶点的距离中最短的距离最远，点在边上也可以。这样的点可能有多个，你只需输出这些点与各顶点的最短距离。【要求】【数据输入】第一行是一个整数N(3N100)。接下来N行按逆时针顺序给出每个顶点的坐标，每行包含2个实数，表示顶点的横坐标和纵坐标(坐标绝对值小于10000)。【数据输出】输出一个实数，表示凸多边形内一点与各顶点的距离中最短的距离的最大值。【样例输入】30 29 07 7【样例输出】4.893过河Time limit: 1s Memory limit: 32768K Total Submit : 518 Accepted Submit : 65 【问题描述】在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。【要求】【数据输入】输入的第一行有一个正整数L（1 = L = 109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 = S = T = 10，1 = M = 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 【数据输出】输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。【样例输入】102 3 52 3 5 6 7【样例输出】2数字游戏Time limit: 1s Memory limit: 32768K Total Submit : 323 Accepted Submit : 89 【问题描述】小W发明了一个游戏，他在黑板上写出了一行数字a1,a2,.an，然后给你m个回合的机会，每回合你可以从中选择一个数擦去它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合，所有你擦去的数字之和就是你所得到的分数。 小W和他的好朋友小Y玩了这个游戏，可是他发现，对于每个给出的an和bn序列，小Y的得分总是比他高，所以他就很不服气。于是他想让你帮他算算，对于每个an和bn序列，可以得到的最大得分是多少。这样他就知道有没有可能超过小Y的得分。 【要求】【数据输入】第一行，一个整数n（1=n=200），表示数字的个数。第二行，一个整数m（1=m=n），表示回合数。接下来一行有n个不超过10000的正整数，a1,a2an，表示原始数字，最后一行有n个不超过500的正整数，b1,b2.bn，表示每回合每个数字递减的值【数据输出】一个整数，表示最大可能的得分 【样例输入】3 310 20 304 5 6【样例输出】47速配游戏Time limit: 5s Memory limit: 32768K Total Submit : 295 Accepted Submit : 209 【问题描述】有这么一个速配电视节目。N位男士和N位女士要在摄像机前选出他们合适的伴侣。每位女士按照其对每位男士作为配偶的偏爱程度给每位男士排名次，每位男士也按照其对每位女士作为配偶的偏爱程度给每位女士排名次。这些名次不允许并列。然后每位男士将向心仪的对象求婚，经过残酷的竞争之后各自找到适合的伴侣。最开始的时候每位男士都还没有被任何一位女士拒绝。求婚环节会经过很多轮进行，每一轮：(1) 每位男士向还没有拒绝过自己的女士中选出自己认为最理想的一个，并向她求婚(2) 每位女士在所有这一轮中向她求婚的男士中选出自己认为最理想的一个，并不答应，也不拒绝。她把其余向她求婚的男士都婉言拒绝掉。经过了若干轮求婚之后，在某一轮，幸运的事情发生了：所有的女士都恰好有一个求婚者，所有的男士都找到一个心仪的对象。主持人将继续指出这个配对方式的神奇之处：没有任意的两个配对，比方说男士A和女士a配对,男士B和女士b配对，使得在A心目中b较a更理想，而且在b心目中A较B更理想（这样A和b就会私奔）。因此，主持人总结说，这个配对是非常合理的。（他知道，这种情况是一定会发生的。）主持人在节目之前已经知道男士和女士之间的偏爱情况，他想预先知道最后的匹配结果是怎么样的，你能帮帮他吗？【要求】【数据输入】第一行包括一个数字N（1=N=1000）以下N*2行，每行有N个数字。第i+1行（1=i=N）表示编号为i的男士对女士们的排序（从最喜欢的到最不喜欢的）。第N+j+1行（1=j=N）表示编号为j的女士对男士们的排序（同样从最喜欢的到最不喜欢的）。【数据输出】N行，每行包括一个数字。第i行的数字表示与编号为i的男士匹配的女士的编号。【样例输入】31 2 32 3 12 1 33 2 12 3 12 3 1【样例输出】321 3n+1数链问题Time limit: 1s Memory limit: 32768K Total Submit : 471 Accepted Submit : 325 【问题描述】在计算机科学上，有很多类问题是无法解决的，我们称之为不可解决问题。然而，在很多情况我们并不知道哪一类问题可以解决，那一类问题不可解决。现在我们就有这样一个问题，问题如下： 1. 输入一个正整数n；2. 把n显示出来；3. 如果n=1则结束；4. 如果n是奇数则n变为 ，否则n变为n/2；5. 转入第2步。例如对于输入的正整数22，应该有如下数列被显示出来：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 我们推测：对于任意一个正整数，经过以上算法最终会推到1。尽管这个算法很简单，但我们仍然无法确定我们的推断是否正确。不过好在我们有计算机，我们验证了对于小于1,000,000的正整数都满足以上推断。对于给定的正整数n，我们把显示出来的数的个数定义为n的链长，例如22的链长为16。 你的任务是编写一个程序，对于任意一对正整数i和j，给出i、j之间的最长链长，当然这个最长链长是由i、j之间的其中一个正整数产生的。我们这里的i、j之间即包括i也包括j。【要求】【数据输入】输入文件只有一行，即为正整数i和j，i和j之间以一个空格隔开。0 i j 10,000。 【数据输出】文件只能有一行，即为i、j之间的最长链长。【样例输入】1 10【样例输出】20数制转换Time limit: 1s Memory limit: 32768K Total Submit : 479 Accepted Submit : 190 【问题描述】有一种数制的基数是3，权值可以取-1,0,1，并分别用符号-,0,1表示，如这种数制的101表示十进制数的10，即1*(32)+0*(31)+1*(30)=10，又如这种数制的-0 表示十进制数的-3，即-1*(31)+0*(30)=-3。编程要求把给定的有符号整数转换为新数制的数，该数的前面不能有多余的0，如10的新数制表示是101，则不要输出成0101。【要求】【数据输入】文件有一行或多行，每行有一个整数N (-2,147,483,647N2,147,483,647)，整数内不会有其他分隔符。【数据输出】对输入文件的每一行输出一行，该行是输入行的整数的新数制表示，不能有多余空行，每行之前不能有前导空格。【样例输入】10-3【样例输出】101-0数列Time limit: 1s Memory limit: 32768K Total Submit : 415 Accepted Submit : 226 【问题描述】给定一个正整数k(3k15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是： 1，3，4，9，10，12，13， （该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，） 请你求出这个序列的第N项的值（用10进制数表示）。 例如，对于k=3，N=100，正确答案应该是981。【要求】【数据输入】输入包含多个测试数据。每个测试数据只有1行，为2个正整数，用一个空格隔开：k N（k、N的含义与上述的问题描述一致，且3k15，10N1000）【数据输出】对于每个测试数据输出一个正整数（在所有的测试数据中，结果均不超过2.1*109）。【样例输入】3 1003 100【样例输出】9819812k进制数Time limit: 1s Memory limit: 32768K Total Submit : 110 Accepted Submit : 28 【问题描述】设r是个2k 进制数，并满足以下条件： （1）r至少是个2位的2k 进制数。 （2）作为2k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。 （3）将r转换为2进制数q后，则q的总位数不超过w。 在这里，正整数k（1k9）和w（kw30000）是事先给定的。 问：满足上述条件的不同的r共有多少个？ 我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k 进制数r。 例：设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有： 2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，高位为6：1个（即67）。共6+5+1=21个。 3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，第2位为6：1个（即167）。共5+4+1=15个。 所以，满足要求的r共有36个。【要求】【数据输入】输入包含多个测试数据，每个测试数据只有1行，为两个正整数，用一个空格隔开：k W【数据输出】对于每个测试数据，输出一行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。（提示：作为结果的正整数可能很大，但不会超过200位）【样例输入】3 73 7【样例输出】3636奖学金Time limit: 1s Memory limit: 32768K Total Submit : 363 Accepted Submit : 218 【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 2795 279这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：5 2797 279则按输出错误处理，不能得分。【要求】【数据输入】输入包含多组测试数据，每个测试数据有n+1行。第1行为一个正整数n，表示该校参加评选的学生人数。第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1n（恰好是输入数据的行号减1）。所给的数据都是正确的，不必检验。 【数据输出】对于每个测试数据输出5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。两个相邻测试数据间用一个空行隔开。【样例输入】690 67 8087 66 9178 89 9188 99 7767 89 6478 89 98880 89 8988 98 7890 67 8087 66 9178 89 9188 99 7767 89 6478 89 98【样例输出】6 2654 2643 2582 2441 2378 2652 2646 2641 2585 258纪念品分组Time limit: 1s Memory limit: 32768K Total Submit : 92 Accepted Submit : 51 【问题描述】元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。【要求】【数据输入】 输入包含多组测试数据，每个测试数据包含n+2行：第1行包括一个整数w，为每组纪念品价格之和的上限。第2行为一个整数n，表示购来的纪念品的总件数。第3n+2行每行包含一个正整数pi (5 = pi = w)，表示所对应纪念品的价格。1 = n = 30000, 80 = w = 200 【数据输出】对每个测试数据，输出一行，包含一个整数，即最少的分组数目。相邻两个测试数据间用一个空行隔开。【样例输入】1009902020305060708090【样例输出】6统计数字Time limit: 1s Memory limit: 32768K Total Submit : 165 Accepted Submit : 58 【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【要求】【数据输入】包含多个测试数据，每个包含n+1行：第1行是整数n，表示自然数的个数。第2n+1行每行一个自然数。1=n=200000，每个数均不超过1 500 000 000（1.5*109） 【数据输出】对每个测试数据输出m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。相邻两个测试数据间用一个空行隔开。【样例输入】8242451002100【样例输出】2 34 25 1100 2矩阵取数游戏Time limit: 1s Memory limit: 32768K Total Submit : 150 Accepted Submit : 27 【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2. 每次取走的各个元素只能是该元素所在行的行首或行尾；3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4. 游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。【要求】【数据输入】输入有多个测试数据，每个包括n+1行：第1行为两个用空格隔开的整数n和m。第2n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。1=n, m=80, 0=aij=1000 【数据输出】对每个数据，输出一行，为一个整数，即输入矩阵取数后的最大得分。相邻两个输出间用一个空行隔开。【样例输入】1 44 5 0 52 1096 56 54 46 86 12 23 88 80 4316 95 18 29 30 53 88 83 64 67【样例输出】122316994四塔问题【问题描述】 “汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？ 为了编程方便，您只需要输出这个结果mod 10000的值。 【要求】【数据输入】该题含有多组测试数据，每组一个正整数n。(0n=50000) 【数据输出】一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。 【样例输入】15【数据输出】129平方数【问题描述】给出包含M个数字的列表，和列表中所有数字的所有质因数。求出最长的子列表，使得子列表中所有数字的乘积是一个完全平方数。 【要求】【数据输入】输入文件包含多组测试数据。第一行包含两个整数N , M ( 1 = N = 30 , 1 = M = 30000 ). N 是质因数的个数。接下来一行有N个整数，给出所有的质因数。然后一行包含M个整数，给出列表。 输入文件结束于N = M = 0. 【数据输出】对于每组数据，输出最长子列表的两个位置坐标l r。l是该子列表在列表中的起始位置，r是结束位置。如果多种情况都满足子列表长度最大，输出l最小的一个。如果不存在这样的子列表输出“None”。 【样例输入】3 42 3 54 9 25 63 42 3 56 6 3 30 0【样例输出】1 31 4【问题描述】给定平面上三个圆的位置，请你用钢笔在纸上画出它们，作图的起点自定。拿起钢笔的时候，你不能作图。在画完一个完整的圆后，才可以接着画另一个，决不可半途中止去画另一个圆.已知把钢笔移动一个单位距离需要一个单位时间，拿起它则不需时间。请计算画完这三个圆所需的最小时间。【要求】【数据输入】第一行为一个正整数T(T=100)，表示测试程序的次数。接下来的T行，每一行都有9个实数x1,y1,r1,x2,y2,r2,x3,y3,r3，分别指第i(i=1,2,3)个圆的圆心坐标和半径长。其中，-10000=xi,yi=10000, 0ri=10000.【数据输出】对于每一种测试情况，输出相应的最小作图时间。【样例输入】20 0 0.5 -2 0 0.5 2 0 0.50 0 1 -2 2 1 2 2 1【样例输出】12.42521.322埃及分数【问题描述】在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。 如： 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0ab1000),编程计算最好的表达方式。 【要求】【数据输入】第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0ab1000)。 【数据输出】每组测试数据若干个数，自小到大排列，依次是单位分数的分母。 【样例输入】119 45【样例输出】5 6 18植树活动Time