acm编程比赛入门题目集
发布时间：2014-10-25 13:42:36
最少钱币数：
【问题描述】
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了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”。你可以假设，每种待凑钱币的数量是无限多的。
【样例输入】
15
6 2 5 10 20 50 100
1
1 2
0
【样例输出】
2
Impossible
Feli 的生日礼物
【问题描述】
Felicia 的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给 Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。 Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，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 15
2 5 9 14
4 8 13
7 12
11
青蛙的约会
【问题描述】
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
【要求】
【数据输入】输入只包括一行5个整数x，y，m，n，L，其中x≠y < 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
【样例输出】
7
14
17
连续邮资问题
【问题描述】
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家至少养猪的数目。
【样例输入】
3
3 1
5 1
7 2
【样例输出】
16
kitty猫的基因编码
【问题描述】
kitty 的基因编码如下定义： kitty的基因由一串长度2^k（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'
【要求】
【数据输入】一行，长度为2^k，为kitty猫的01基因编码，有多个数据
【数据输出】一行，由ABC构成的ABC编码
【样例输出】
01001011
【样例输出】
CCCABACCBAB
取石子游戏
【问题描述】
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
【要求】
【数据输入】输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
【数据输出】输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
【样例输入】
2 1
8 4
4 7
【样例输出】
0
1
0
勇气的挑战
【问题描述】
给定n个点的坐标(x,y,z),且n<=50,从点1出发,怎么样才能走一条路径,访问每个点一次且仅一次,使走过的距离和最小?
【要求】
【数据输入】多组数据. 第1行n,然后n行3个整数坐标
【数据输出】每组一行,代表最小权和
【样例输入】
3
0 0 0
1 1 0
1 -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之间的一个整数。
【数据输出】对每个测试用例，将获得给定分数的学生人数输出。
【样例输出】
3
80 60 90
60
2
85 66
0
5
60 75 90 55 75
75
0
【样例输出】
1
0
2
钱币兑换问题
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。
【数据输出】对应每个输入，输出兑换方法数。
【样例输入】
2934
12553
【样例输出】
718831
13137761
字串数
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,表示一共有多少种字符串.
【样例输入】
2
1 2
3
2 2 2
0
【样例输出】
3
90
小希的数表
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结束。
假设输入保证解的存在性和唯一性。
【数据输出】对于每组数据，输出原来的数表。它们也应当是按照顺序排列的。
【样例输入】
4
4 5 7 10 12 13
4
5 6 7 8 9 10
0
【样例输出】
1 3 4 9
2 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行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。
【样例输入】
2
20
40
【样例输出】
1 7 19
1 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，所有中间结果都在-2^31和2^31之间。
【样例输入】
100 288
ABECED
876356 321456
ABECAEDBECAF
【数据输出】
388,388
2717080,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)
【样例输出】
4
1
整数对
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<=10^9)，文件以0结尾。
【数据输出】对于每个输入的N，输出所有符合要求的解（按照大小顺序排列）如果没有这样的解，输出"No solution."
【样例输入】
34
152
21
0
【样例输出】
27 31 32
126 136 139 141
No 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代表死亡骑士手中钞票的面值.
注意：地精商店只有题中描述的三种道具.
【数据输出】对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.
【样例输入】
2
900
250
【样例输出】
0
50
覆盖的面积
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<=N<= 1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和 Y轴平行.坐标的范围从0到100000.注意:本题的输入数据较多,推荐使用scanf读入数据.
【数据输出】对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
【样例输入】
2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1
【样例输出】
7.63
0.00
积木分发
Time limit: 10s Memory limit: 32768K
Total Submit : 1125 Accepted Submit : 365
【问题描述】
歌手The Pancakes到幼儿园跟小朋友玩耍，她到达的时候小朋友们已经争着积木玩了。小朋友都想要更多的积木砌一个自己喜欢的图形，砌完就可以和The Pancakes合照。同时，The Pancakes手上还有一些积木，她可以把手上的这些积木全部给一个小朋友，然后等该小朋友砌完后就可以收回所发的积木和该小朋友原先手上的积木。但她不知道能否让所有的小朋友都和她合照，聪明的你可以帮助她吗？
【要求】
【数据输入】输入包含多个数据。每个数据的第一行是两个正整数n和s，1≤n≤10000，1≤s≤1000000，表示一共有n位小朋友，The Pancakes手上有s块积木。以下有n行，每行有两个正整数，a和b，1≤a，b≤10^9，表示第i个小朋友手上有a块积木，还需要b块积木才能够砌完。有多少种可能的决斗过程。
例如N=3，有6种不同的过程：12->13，12->23，13->12，13->32，23->21， 23->31。
注意：文件里只有一个整数N(2≤N≤1000)。
【数据输出】输出一个整数，为可能的过程的总数除以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(2≤N≤1000)。
【数据输出】输出一个整数，为可能的过程的总数除以10007的余数。
【样例输入】
4
【样例输出】
96
排序
Time limit: 10s Memory limit: 32768K
Total Submit : 70 Accepted Submit : 2
【问题描述】
通常我们对一个长度为n(n≤24)的整数数列进行排序操作，其实就是讲他们按照从小到大的顺序重整。一般情况下我们可以比较任意两个数之间的大小并交换他们的位置，但这里我们限制只能数列的某一个前缀序列翻转，除此之外的任何操作都是不允许的。更精确地说，假设数列a1，a2，……，an，一个合法的操作是把数列变为ak，ak-1，……，a2, a1, ak+1, ak+2,……, an，其中1
你任务是求出一个序列用上面的方法排序至少需要多少步。
【要求】
【数据输入】输入文件有两行：第一行是一个整数n，表示数列的长度。第二行有n个整数，表示待排序的数列，每个整数的绝对值不大于32767。
【数据输出】输出文件有一行是一个整数s，表示完成排序所需的最少步数。
【样例输入】
4
3 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(3≤N≤100)。
接下来N行按逆时针顺序给出每个顶点的坐标，每行包含2个实数，表示顶点的横坐标和纵坐标(坐标绝对值小于10000)。
【数据输出】输出一个实数，表示凸多边形内一点与各顶点的距离中最短的距离的最大值。
【样例输入】
3
0 2
9 0
7 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个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
【数据输出】输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。
【样例输入】
10
2 3 5
2 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,a2…an，表示原始数字，最后一行有n个不超过500的正整数，b1,b2….bn，表示每回合每个数字递减的值
【数据输出】一个整数，表示最大可能的得分
【样例输入】
3
3
10 20 30
4 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的男士匹配的女士的编号。
【样例输入】
3
1 2 3
2 3 1
2 1 3
3 2 1
2 3 1
2 3 1
【样例输出】
3
2
1
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*(3^2)+0*(3^1)+1*(3^0)=10，又如这种数制的-0 表示十进制数的-3，即-1*(3^1)+0*(3^0)=-3。编程要求把给定的有符号整数转换为新数制的数，该数的前面不能有多余的0，如10的新数制表示是101，则不要输出成0101。
【要求】
【数据输入】文件有一行或多行，每行有一个整数N (-2,147,483,647≤N≤2,147,483,647)，整数内不会有其他分隔符。
【数据输出】对输入文件的每一行输出一行，该行是输入行的整数的新数制表示，不能有多余空行，每行之前不能有前导空格。
【样例输入】
10
-3
【样例输出】
101
-0
数列
Time limit: 1s Memory limit: 32768K
Total Submit : 415 Accepted Submit : 226
【问题描述】
给定一个正整数k(3≤k≤15),把所有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的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）
【数据输出】对于每个测试数据输出一个正整数（在所有的测试数据中，结果均不超过2.1*109）。
【样例输入】
3 100
3 100
【样例输出】
981
981
2^k进制数
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（1≤k≤9）和w（k
问：满足上述条件的不同的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 7
3 7
【样例输出】
36
36
奖学金
Time limit: 1s Memory limit: 32768K
Total Submit : 363 Accepted Submit : 218
【问题描述】
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。
例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：
7 279
5 279
这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：
5 279
7 279
则按输出错误处理，不能得分。
【要求】
【数据输入】输入包含多组测试数据，每个测试数据有n+1行。
第1行为一个正整数n，表示该校参加评选的学生人数。
第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。
所给的数据都是正确的，不必检验。
【数据输出】对于每个测试数据输出5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。两个相邻测试数据间用一个空行隔开。
【样例输入】
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
【样例输出】
6 265
4 264
3 258
2 244
1 237
8 265
2 264
6 264
1 258
5 258
纪念品分组
Time limit: 1s Memory limit: 32768K
Total Submit : 92 Accepted Submit : 51
【问题描述】
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
【要求】
【数据输入】 输入包含多组测试数据，每个测试数据包含n+2行：
第1行包括一个整数w，为每组纪念品价格之和的上限。
第2行为一个整数n，表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。
1 <= n <= 30000, 80 <= w <= 200
【数据输出】对每个测试数据，输出一行，包含一个整数，即最少的分组数目。
相邻两个测试数据间用一个空行隔开。
【样例输入】
100
9
90
20
20
30
50
60
70
80
90
【样例输出】
6
统计数字
Time limit: 1s Memory limit: 32768K
Total Submit : 165 Accepted Submit : 58
【问题描述】
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
【要求】
【数据输入】包含多个测试数据，每个包含n+1行：
第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。
1<=n<=200000，每个数均不超过1 500 000 000（1.5*109）
【数据输出】对每个测试数据输出m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
相邻两个测试数据间用一个空行隔开。
【样例输入】
8
2
4
2
4
5
100
2
100
【样例输出】
2 3
4 2
5 1
100 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。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
1<=n, m<=80, 0<=aij<=1000
【数据输出】对每个数据，输出一行，为一个整数，即输入矩阵取数后的最大得分。相邻两个输出间用一个空行隔开。
【样例输入】
1 4
4 5 0 5
2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67
【样例输出】
122
316994
四塔问题
【问题描述】
“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？ 为了编程方便，您只需要输出这个结果mod 10000的值。
【要求】
【数据输入】该题含有多组测试数据，每组一个正整数n。(0
【数据输出】一个正整数，表示把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 4
2 3 5
4 9 25 6
3 4
2 3 5
6 6 3 3
0 0
【样例输出】
1 3
1 4
【问题描述】
给定平面上三个圆的位置，请你用钢笔在纸上画出它们，作图的起点自定。拿起钢笔的时候，你不能作图。在画完一个完整的圆后，才可以接着画另一个，决不可半途中止去画另一个圆.已知把钢笔移动一个单位距离需要一个单位时间，拿起它则不需时间。请计算画完这三个圆所需的最小时间。
【要求】
【数据输入】第一行为一个正整数T(T<=100)，表示测试程序的次数。
接下来的T行，每一行都有9个实数x1,y1,r1,x2,y2,r2,x3,y3,r3，分别指第i(i=1,2,3)个圆的圆心坐标和半径长。其中，-10000<=xi,yi<=10000, 0
【数据输出】对于每一种测试情况，输出相应的最小作图时间。
【样例输入】
2
0 0 0.5 -2 0 0.5 2 0 0.5
0 0 1 -2 2 1 2 2 1
【样例输出】
12.425
21.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(0〈a〈b〈1000),编程计算最好的表达方式。
【要求】
【数据输入】第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0〈a〈b〈1000)。
【数据输出】每组测试数据若干个数，自小到大排列，依次是单位分数的分母。
【样例输入】
1
19 45
【样例输出】
5 6 18
植树活动
Time Limit:1000MS Memory Limit:65536K
Total Submit:589 Accepted:342
【问题描述】春暖花开，万物复苏，这正是植物生长的好季节。珠海校区举行了一次题为“迎百年校庆，添三分绿色”的植树活动。这次植树活动的目的除了美化我们的校园，进一步增强同学们的环保意识以外，还在于迎接即将到来的百年校庆，张江河副院长认为这次活动意义重大，并不亚于其他大型的植树活动。他希望同学们要坚持照顾好自己所种的树，为它们浇水捉虫，让它们茁壮成长。 师生共同植树，打成一片。在这里我们看到的是热情，是团队合作精神，还有同学们为庆祝百年校庆的真诚的心！经过将近一个小时的努力，各单位基本上都把树种好。看到自己亲手种的树，同学们都非常兴奋，纷纷拍照留念，记下这个难忘的时刻！同学们感叹说：“这次活动很有意义啊！”，有的同学则希望能留下一个见证，让他们以后回来母校，可以看到自己的班集体种的树，会觉得很有意义。
这次植树活动有n个部门参加，树种有米兰、玉兰，有桂花、榕树，还有大皇椰等。每个部门分别种了m个树种，每个树种分别种了k1,k2,k3,…,km-1,km棵，现在有一个简单的任务，就请你帮忙计算一下每个部门分别种了多少棵树，全院一共种了多少棵树。
【要求】
【数据输入】所有的数据都是从键盘输入，其数据格式是：第一行是参与植树的部门数n，后面跟着的每二行是一个部门的数据，在每一个部门的数据中，第一行是该部门植树的树种数m，第二行是m个树种所种的棵数k1,k2,k3,…,km-1,km。
【数据输出】输出结果为按顺序输出每个部门所种的树棵数，及全院共种树的棵数。
【样例输入】
2
3
4 5 2
4
6 7 3 1
【样例输出】
11
17
28
有趣的排列
Time Limit:1000MS Memory Limit:65536K
Total Submit:27 Accepted:19
【问题描述】
大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。
任务描述： 给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。
比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。
【要求】
【数据输入】第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64)，第二行有n个正整数，是1，2 … n的一个排列。
【数据输出】对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。
【样例输入】
3
3 1
2 3 1
3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
【样例输出】
3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10
三角形面积
Time Limit:1000MS Memory Limit:65536K
Total Submit:1195 Accepted:350
【问题描述】
给出三角形的三个边长为a，b，c，根据海伦公式来计算三角形的面积：
s = (a+b+c)/2；
area = sqrt(s*(s-a)*(s-b)*(s-c));
【要求】
【数据输入】测试的数据有任意多组，每一组为一行。
每一行为三角形的三个边长为a，b，c；
【数据输出】输出每一个三角形的面积，两位小数。如果不是一个三角形，则输出错误提示信息：“Input error!”
【样例输入】
3 4 5
6 8 10
1 2 3
【样例输出】
6．00
24．00
Input error!
吃豆豆
timelimit:5 seconds
memlimit:32768 K
Prev |Next
【问题描述】
两个PACMAN 吃豆豆。一开始的时候，PACMAN 都在坐标原点的左下方，豆豆都在右上方。PACMAN 走到豆豆处就会吃掉它。PACMAN 行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。请你帮这两个PACMAN 计算一下，他们俩加起来最多能吃掉多少豆豆。
【要求】
【数据输入】输入包括多组数据每组输入数据第一行为N（1≤ N ≤2000），表示豆豆的数目。接下来N行，每行一对正整数Xi、Yi（不超过10^8），表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。
【数据输入】两个PACMAN 加起啻最多能吃掉的豆豆数量。
每组输出后跟一个空行
【样例输入】
8
8 1
1 5
5 7
2 2
7 8
4 6
3 3
6 4
【样例输出】
7
序列
timelimit:30 seconds
memlimit:32768 K
Prev |Next
【问题描述】
一个序列{Ai, i=0,1,2,…,3N}由3N+1 项组成，每一项要么为1，要么为-2。
定义部分和SK=A0+A1+…+AK，求所有满足性质P的序列的数目。性质P为：S3N=1 且对于所有的K=0,1,2,…,3N-1,3N，有SK>0（即所有项的和为１，且所有部分和为正）。
例如N=2 的时候，共有3 组这样的序列：
1, 1, 1, -2, 1, 1, -2
1, 1, 1, 1, -2, 1, -2
1, 1, 1, 1, 1, -2, -2
【要求】
【数据输入】第一行输入N(N≤1000)。
【数据输出】满足P 性质的序列数目
【样例输入】
2
【样例输出】
3
宠物
timelimit:1 seconds
memlimit:32768 K
Prev |Next
【问题描述】fzk非常喜欢养宠物，比如他现在就养了2头奶牛，3只小熊，4个猩猩，5头大象，还有一个daizi。fzk 把他的宠物关在一些笼子里，例如，fzk当前的分配是： 笼子1： 奶牛，daizi ；笼子2： 奶牛；笼子3： 猩猩，大象；笼子4： 小熊，猩猩这样总共需要4个笼子。为了节省资金，fzk想用尽可能少的笼子来装下所有宠物。他的办法是在当前的分配下，合并一些笼子。假设每个笼子都足够大，可以装下任意多的宠物，而两个笼子如果装有相同的一种或多种宠物，就可以合并。现在给出fzk当前的分配，你能否帮助fzk算出按照他的方法合并后，总共只需要几个笼子? 比如对于上面的分配，可以合并为： 笼子1：奶牛，daizi ；笼子2：猩猩，小熊，大象总共需要2个笼子。
【要求】
【数据输入】首先一个整数t表示测试数据组数（1=
【数据输出】对每组测试数据，输出一个整数，表示笼子合并之后fzk可以使用的最少的笼子数。
【样例输入】
1
4
2 nainiu daizi
1 nainiu
2 xingxing daxiang
2 xiaoxiong xingxing
【样例输出】
2
多边形
timelimit:1 seconds
memlimit:32768 K
Prev |Next
【问题描述】
在一个坐标平面上，给一个n个点的集合，能不能画出一个简单多边形（除相邻边外其他任意两条边没有公共点）。要求这个多边形的顶点集合就是给定的点集，而且多边形的边必须与x轴或y轴平行.更进一步,要求多边形相邻的边不平行,也就是说,多边形的边是一条横线段,接着一条竖线段,再接着一条横线段....
【要求】
【数据输入】输入包括多组数据.
输入数据的第一行包括一个整数t,表示有t组输入数据，t<10.
每组输入数据的第一行为一个整数n,(4 ≤ n ≤ 100000)
接下来的n行每行描述一个点的坐标,包括两个整数x y,( |x|,|y| ≤ 1000 )
【数据输出】
每个输入数据输出一行
如果可以画出要求的多边形,输出多边形的周长.如果存在多个这样的多边形，输出周长最小的。
如果不存在这样的多边形,输出-1
【样例输入】
1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2
【样例输出】
12
H数
timelimit:1 seconds
memlimit:32768 K
Prev |Next
【问题描述】
让我们来做做David Hilbert的一个练习题.
定义H数为4的正整数倍加1,比如: 1, 5, 9, 13, 17, 21, 25... 都是H数.可以证明两个H数相乘结果还是H数.类似于整数,我们也可以把H数分为1, H素数和H合数.一个H数为H素数,当且仅当,它除了1和自己之外,没有其他的H数整除它.除了1和H素数外,其他的H数都是H合数.比如9是H素数,因为除了1和9之外没有其他的H数整除9; 17和21也是H素数; 45是H合数，45=5×9，25也是H合数,因为 25=5×5.
你的任务是计算H半素数的个数. 一个H数是H半素数,当且仅当,它能分解成两个H素数的乘积.
这两个H素数可以是同一个数.比如25是H半素数,25=5×5。45也是H半素数, 45 = 5×9,而125不是H半
素数,125 = 5 × 5 × 5,它可以分解成3个H素数的乘积.
给你一个H数n,要求你输出有多少个不大于n的H半素数.
【要求】
【数据输入】输入包括多组数据,每组数据输出一行,包括一个整数n,(n ≤ 1,000,001 )
最后一行为一个0,表示输入结束.
【数据输出】每个输入数据输出一行,先输出n,然后输出小于等于n的H数中有几个是H半素数,这两个数用一个空格隔开
【样例输入】
21
85
789
0
【样例输出】
21 0
85 5
789 62
数列找数
Time Limit:1000MS Memory Limit:65536K
Total Submit:635 Accepted:263
【问题描述】
在一个数组A(N)各下标变量中存储N个互不相等的数，键盘输入正整数M(M≤N)，要求打印出数组中第M大的下标变量的值。
例如：数组A（10）的数据为：
A(1), A(2), A(3), A(4), A(5), A(6), A(7), A(8), A(9), A(10)
16, 57, 20, 19, 38, 41, 6, 13, 25, 32
M=3时的运行结果为： A(5)=38 （即第3大的数是A(5)=38）
【要求】
【数据输入】第一行为测试的数据的组数k，说明共有K组数据，每一组有两行。每组中第一行为N，M,第二行为N个下标变量的值。
【数据输出】输出每一组数据中符合要求的下标值和下标变量值。
【样例输入】
2
5 1
6 8 3 4 5
3 2
1 2 3
【样例输出】
A(2)=8
A(2)=2
放苹果
Time Limit:1000MS Memory Limit:65536K
Total Submit:136 Accepted:94
【问题描述】
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
【要求】
【数据输入】第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
【数据输出】对输入的每组数据M和N，用一行输出相应的K。
【样例输入】
1
7 3
【样例输出】
8
密码
Time Limit:1000MS Memory Limit:65536K
Total Submit:126 Accepted:65
【问题描述】网上流传一句话:"常在网上飘啊，哪能不挨刀啊～"。其实要想能安安心心地上网其实也不难，学点安全知识就可以。 首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件：
(1).密码长度大于等于8，且不要超过16。
(2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。
这四个字符类别分别为：
1.大写字母：A,B,C...Z;
2.小写字母：a,b,c...z;
3.数字：0,1,2...9;
4.特殊符号：~,!,@,#,$,%,^;
给你一个密码，你的任务就是判断它是不是一个安全的密码。
【要求】
【数据输入】输入数据有多组，对于每一组输入第一行包含一个数M，接下有M行，每行一个密码（长度最大可能为50），密码仅包括上面的四类字符输入0退出。
【数据输出】对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。
【样例输入】
3
a1b2c3d4
Linle@ACM
^~^@^@!%
0
【数据输出】
NO
YES
NO
绝对值排序
Time Limit:1000MS Memory Limit:65536K
Total Submit:79 Accepted:50
【问题描述】
输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。
【要求】
【数据输入】输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。
【数据输出】对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。
【样例输入】
3 3 -4 2
4 0 1 2 -3
0
【样例输出】
-4 3 2
-3 2 1 0
求逆序对个数
Time Limit:1000MS Memory Limit:65536K
Total Submit:64 Accepted:28
【问题描述】
有一实数或者字母序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n]，若i＜j，并且A[i]＞A[j]，则称A[i]与A[j]构成了一个逆序对，求字符串A中逆序对的个数。
【要求】
【数据输入】输入包括多个测试数据，每一行为一个，每个测试数据长度不超过50000。
【数据输出】输出每个数据的逆序对。
【样例输入】
52462326
AEDCB
kfeFES54saW
【样例输出】
12
6
35
阶乘的和
Time Limit:1000MS Memory Limit:65536K
Total Submit:10 Accepted:4
【问题描述】
给一个非负整数，判断这个数是不是相互不同的非负整数的阶乘的和。
如6=3！；7=3！+ 1！；但5不是相互不同的非负整数的阶乘的和。
【要求】
【数据输入】有多组测试数据，输入为负数时结束。
【数据输出】如n是相互不同的非负整数的阶乘的和，输出YES，否则输出NO，每个一行。
【样例输入】
5
6
【样例输出】
NO
YES
换零钱
Time Limit:1000MS Memory Limit:65536K
Total Submit:17 Accepted:15
【问题描述】
为了解决珠海学院学生坐公交车没零钱的情况，神通广大的Cl同学决定帮大家无偿换钱，假设他有1到n元的各种币值的钱无限张，如果你有一张n元的钱，与Cl换能有多少种换法。
【要求】
【数据输入】多组测试数据，每组一个整数n（1＝＜n＜＝70）,表示要换的钱的值。
【数据输出】每组一行，输出有多少种方法。
【样例输入】
1
2
【样例输出】
1
2
旅游路线
Time Limit:1000MS Memory Limit:65536K
Total Submit:10 Accepted:7
【问题描述】
假如长江沿岸有n个城市，每个城市依次标号（上游到下游次序编）为1，2，3…, n-3, n-2, n-1, n。alg想从长江上游出发，游玩这些城市。其中alg的旅游路线选取原则为：
1.至少要游玩一个城市。
2.不会游玩相邻的两个城市。即相邻的两个城市不会出现在algoo的旅游路线中。例如：当游玩过城市n-k后，就不会考虑在城市n-k+1停下。
现在你的任务是：如果有n个城市，帮助algoo计算有多少种路线可以选择。
【要求】
【数据输入】多组测试数据。每组测试数据一行，为一个数n（1<=n<=100），表示城市的个数。
【数据输出】对每组测试数据，输出algoo总共有多少种路线选择。
【样例输入】
3
4
5
【样例输出】
4
7
12
Hint
数据会好大^_^
当n=4时，有如下几种路线。
1
2
3
4
1--> 3
1--> 4
2--> 4 （1，3城市都不玩，游玩过城市2后再到城市4）
共7种路线。
割钢管
Time Limit:1000MS Memory Limit:65536K
Total Submit:7 Accepted:6
【问题描述】
A公司有一台钢管切割机提供钢管加工业务。钢管切割机每次可以将一根钢管按照要求在指定位置切割为2段。每次切割的费用为钢管的长度。
给定一根长度为L的钢管，要求将其在位置l1
【要求】
【数据输入】多组测试数据。
每组数据第1行有2个正整数L和n，L表示钢管的长度，n表示切割次数。第2行有n个正整数，表示切割位置l1
【数据输出】最小切割总费用并换行.
【样例输入】
15 4
3 9 12 14
【样例输出】
33
亲和数
Time Limit:1000MS Memory Limit:65536K
Total Submit:35 Accepted:26
【问题描述】
古希腊数学家毕达哥拉斯在自然数研究中发现，220的所有真约数(即不是自身的约数)之和为： 1+2+4+5+10+11+20+22+44+55+110＝284。
而284的所有真约数为1、2、4、71、 142，加起来恰好为220。人们对这样的数感到很惊奇，并称之为亲和数。一般地讲，如果两个数中任何一个数都是另一个数的真约数之和，则这两个数就是亲和数。
你的任务就编写一个程序，判断给定的两个数是否是亲和数
【要求】
【数据输入】输入数据第一行包含一个数M，接下有M行，每行一个实例,包含两个整数A,B； 其中 0 <= A,B <= 600000 ;
【数据输出】对于每个测试实例，如果A和B是亲和数的话输出YES，否则输出NO。
【样例输入】
2
220 284
100 200
【样例输出】
YES
NO
分解素因子
Time Limit:1000MS Memory Limit:65536K
Total Submit:14 Accepted:11
【问题描述】
假设x是一个正整数，它的值不超过65535(即1
【要求】
【数据输入】输入的第一行含一个正整数k (1<=k<=10)，表示测试例的个数，后面紧接着k行，每行对应一个测试例，包含一个正整数x。
【数据输出】每个测试例对应一行输出，输出x的素数乘积表示式，式中的素数从小到大排列，两个素数之间用“*”表示乘法。
【样例输入】
2
11
9828
【样例输出】
11
2*2*3*3*3*7*13
有趣的数列
Time Limit:1000MS Memory Limit:65536K
Total Submit:2 Accepted:1
【问题描述】
数列F(n)和G(n)是由下列三个条件所确定的两个自然数列：
(1) F(1) = 1；
(2) G(n) = n*a - 1 - F(n)，a是一个大于4的整数；
(3) F(n+1)是与2n个数:F(1),F(2),...,F(n);G(1),G(2),...,G(n)不同的最小自然数。
给定a和n,你能求出满足以上条件的数列F(n)和G(n)吗？
【要求】
【数据输入】测试数据有多行，每行包含两个数a和n，其中：4 < a <= 1000, 1 <= n <= 1000000;
当a = n = 0时，输入结束，此行无须处理。
【数据输出】为简便起见，只须输出数列F(n)和G(n)的第n项f(n), g(n)；
输出数据有一行，分别包含两个数f(n)和g(n)。
【样例输入】
5 1
5 3
0 0
【样例输出】
1 3
4 10
洗牌问题
Time Limit:1s Memory limit:32M
Accepted Submit:301 Total Submit:644
【问题描述】
设2n张牌分别标记为1, 2, ..., n, n+1, ..., 2n，初始时这2n张牌按其标号从小到大排列。经一次洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ..., 2n, n。即前n张牌被放到偶数位置2, 4, ..., 2n，而后n张牌被放到奇数位置1, 3, ..., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的n的值(n≤10^5)，最少需要经过多少次洗牌可恢复到初始状态。
【数据输入】输入数据由多组数据组成。每组数据仅有一个整数，表示n的值。
【数据输出】对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。
【样例输入】
10
【样例输出】
6
DNA序列密码问题
Time Limit:6s Memory limit:32M
Accepted Submit:7 Total Submit:22
【问题描述】
一些生物的复杂结构可以用其DNA序列来表示。而DNA序列又可以表示为带有标记的核苷酸字符串。最近，福州大学信息学院生物信息学研究小组的一项工作表明，大多数蛋白质序列可以从核苷酸数据库记录中推导出来。研究小组的科学家们用密码学方法将DNA序列变换为2维Cray码后发现，任一DNA的Cray码序列S具有如下性质：
序列S:(x1,y1),(x2,y2),...,(xn,yn)是一个有限序列；
序列S中各项(xi,yi)均落在一个网格边长为1的300*3000平面网格N的网格点上；
序列S中各项最多分布在网格N的3行中。
科学家们发现，若将序列S的每一项都看作平面上一个点，从序列的任意一点出发，连接序列中每个点恰好一次，又回到出发点的最短平面回路T的长度与该序列表示的DNA密码密切相关。为了有效地破译DNA密码，科学家们希望设计出一个高效的计算程序，能对给定DNA的Cray码序列S，快速计算出其最短回路T的长度。
编程任务
对于给定的DNA的Cray码序列S，计算出其最短回路T的长度。
数据输入本题只有一组数据。 Cray码序列S依其在网格N中的位置分为3行：
(a1,ya),(a2,ya),...,(a_na,ya);
(b1,yb),(b2,yb),...,(b_nb,yb);
(c1,yc),(c2,yc),...,(c_nc,yc);
其中，0<=ya
【要求】
【数据输入】
输入数据第1行中的3个整数为na，nb和nc；
第2行中的3个整数为ya，yb和yc；
接下来的na行中每行1个整数，依次为a1,a2,…,a_na；
再接下来的nb行中每行1个整数，依次为b1,b2,…,b_nb；
最后的nc行中每行1个整数，依次为c1,c2,…,c_nc。
【数据输出】程序运行结束时，输出所找到的序列S的最短回路T的长度值，精确到小数点后2位。
【样例输入】
2 1 2
1 2 3
5
7
6
5
7
【样例输出】
8.83
DNA序列密码问题
Time Limit:6s Memory limit:32M
Accepted Submit:7 Total Submit:22
【问题描述】
一些生物的复杂结构可以用其DNA序列来表示。而DNA序列又可以表示为带有标记的核苷酸字符串。最近，福州大学信息学院生物信息学研究小组的一项工作表明，大多数蛋白质序列可以从核苷酸数据库记录中推导出来。研究小组的科学家们用密码学方法将DNA序列变换为2维Cray码后发现，任一DNA的Cray码序列S具有如下性质：
序列S:(x1,y1),(x2,y2),...,(xn,yn)是一个有限序列；
序列S中各项(xi,yi)均落在一个网格边长为1的300*3000平面网格N的网格点上；
序列S中各项最多分布在网格N的3行中。
科学家们发现，若将序列S的每一项都看作平面上一个点，从序列的任意一点出发，连接序列中每个点恰好一次，又回到出发点的最短平面回路T的长度与该序列表示的DNA密码密切相关。为了有效地破译DNA密码，科学家们希望设计出一个高效的计算程序，能对给定DNA的Cray码序列S，快速计算出其最短回路T的长度。
编程任务
对于给定的DNA的Cray码序列S，计算出其最短回路T的长度。
【要求】
【数据输入】本题只有一组数据。 Cray码序列S依其在网格N中的位置分为3行：
(a1,ya),(a2,ya),...,(a_na,ya);
(b1,yb),(b2,yb),...,(b_nb,yb);
(c1,yc),(c2,yc),...,(c_nc,yc);
其中，0<=ya
输入数据第1行中的3个整数为na，nb和nc；
第2行中的3个整数为ya，yb和yc；
接下来的na行中每行1个整数，依次为a1,a2,…,a_na；
再接下来的nb行中每行1个整数，依次为b1,b2,…,b_nb；
最后的nc行中每行1个整数，依次为c1,c2,…,c_nc。
【数据输出】程序运行结束时，输出所找到的序列S的最短回路T的长度值，精确到小数点后2位。
【样例输入】
2 1 2
1 2 3
5
7
6
5
7
【样例输出】
8.83
麦森数
Time Limit:5s Memory limit:32M
Accepted Submit:114 Total Submit:585
【问题描述】
麦森数在数论中有着非常重要的地位，应用极广。形如2 ^ p – 1并且为质数的数字即为麦森数。可以证明当2^p-1 为一质数的时候，p为质数。
你的任务是对于给出的整数，判断他能不能表示成2^p-1的形式，且p为质数。
【要求】
【数据输入】输入包含多组测试数据。每行一组数据，包含一个不超过10^10000的整数。
【数据输出】
对于每组数据，如果该数字可以表示成2^p-1的形式，且p为质数，输出 “It may be a Mason number.” 否则，输出“It must not be a Mason number.”
【样例输入】
3
4
15
【样例输出】
It may be a Mason number.
It must not be a Mason number.
It must not be a Mason number.
飞机加油问题
Time Limit:2s Memory limit:32M
Accepted Submit:136 Total Submit:934
【问题描述】
F国际航空公司在世界范围有n个国际机场。第i 个国际机场到中心机场的距离为di, i=1，…，n。从国际机场j 到国际机场i 的飞行费用为c(i,j) = s + (dj - di)2 ，s 为地面加油费用。从任何国际机场飞往中心机场的飞机可以在任一国际机场加油后继续飞行。飞机加油问题要求确定从距中心机场最远的国际机场飞到中心机场的最少费用。
【编程任务】
对于给定的n个国际机场到中心机场的距离d1,d2,...,dn ,以及地面加油费用s，编程计算从距中心机场最远的国际机场飞到中心机场的最少费用。
【要求】
【数据输入】第一行有2 个整数n (n<=400,000)和s，表示有n个国际机场（不包括中心机场），地面加油费用s。接下来的1行中每行有n个整数d1,d2,...,dn，表示给定的 n个国际机场到中心机场的距离。
【数据输出】将编程计算出的最小费用输出。
【样例输入】
5 10
1 3 6 7 10
【样例输出】
64
ElGamal数字签名
Time Limit:5s Memory limit:32M
Accepted Submit:6 Total Submit:77
【问题描述】
在实际生活和工作中，许多事物的处理需要当事人的签名。尤其在现代通信中，签名更是起到了认证、核准、有效和负责等功效。数字签名是现代密码学的一个重要组成部分，自从Diffie和Hellman于1976年首次提出数字签名以来，数字签名就在学术界和计算机网络界得到了迅猛的发展。著名的公钥算法，椭圆曲线体制，在数字签名中都有一定的应用。ElGamal就是一种原理简单，应用广泛的数字签名方法，它的成功很大程度上取决于求解离散对数问题的困难。ElGamal的密钥和参数的产生过程如下： 它先选定一个足够大的素数P， 然后在比P小的正数中选取一个随机数g和随机数x， 并且计算出y=gx(mod P) 。然后，{y,g,P}作为公钥，而x则作为保密认证的私钥。如果你想获取他人的私人信息，那么，你就必须在已知 {y,g,P} 的情况下计算出x(当然，如果要获得明文，还必须攻破或获取签名时使用的Hash函数)。本题的任务并不复杂，它只需要你对于已知的三元组{y,g,P}，设法计算出签名验证的时候用户使用的私钥。
【要求】
【数据输入】本题有多组输入数据，你必须处理到EOF为止
输入数据有三个整数: P, g, y (2 <= P < 231)
【数据输出】输出仅仅一个数字x ,使得0
【样例输入】
7 5 3
5 1 4
【样例输出】
5
ERROR
缺失的数据
Time Limit:1s Memory limit:32M
Accepted Submit:196 Total Submit:512
【问题描述】
网络传输中由于受到链路层的最大传输单元(Maximum Transmission Unit，MTU)的限制，在很多情况下需要对原始的数据报进行分片，使得每一分片可以顺利的传输。F公司的网络设备根据MTU的限制将每个原始的数据划分成n片，用1~n这n个数字对每个分片进行编号，在目的主机上将这些分片重新组合成原始的数据。可是在测试中发现一个问题：经常出现缺失一个数据分片的情况。公司希望在将分片重新组合前就能知道缺失的数据分片编号。
【要求】
【数据输入】有多组输入数据，你必须处理到EOF为止。
每组输入数据第一行就一个整数n(2<=n<=105), 表示数据分成了n片。
第二行有n-1个以空格隔开的整数，表示目的主机收到的数据分片的编号，由于网络传输的一些因素，数据分片到达的顺序是随机的。
【数据输出】输出缺失的数据片编号。
【样例输入】
5
5 3 2 1
【样例输出】
4
相关推荐
快乐的一天作文400字 - 4（优品作文）
车的标志代表什么意思
国庆诗歌朗诵比赛主持词
线形规划在线作业
Jxl设置列的格式为文本
幼儿园自查自纠报告三篇
[最新]2019-2020精选人美小学美术四上《第2课：生活中的暖色》word教案(9)
小学三年级阅读及答案之三十三
小数除法单元检测
08春季学期 - 电子商务 - URT - BIPT教学机器人有限公司创业计划书
