acm入门题集.docx

1、acm入门题集程序设计比赛试题主办方：迅翔计算机协会最少钱币数：【问题描述】这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，可以用 5 个 2 元、1 个 5 元，或者 3 个 5 元，或者 1 个 5 元、1 个 10 元，等等。显然，最少需要 2 个钱币才能凑成 15 元。你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。【要求】【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值 M（1 = M = 2000，整

2、数），接着的一行中，第一个整数 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 带来了最新款

3、的“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 想

4、了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC 的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC 的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商 1101，附带写情书功能）。【要求】【数据输入】每行一个 n，直到输入数据结束【数据输出】对应输入的 n，每行输出一个答案【样例输入】1101【样例输出】8蛇行矩阵【问题描述】蛇形矩阵是由 1 开始的自然数依次排列成的一个矩阵上三角形。【要求】【数据输入】本题有多组数据，每组数据由一个正整数 N 组成。（N 不大于 100）【数据输出】对

5、于每一组数据，输出一个 N 行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。【样例输入】5【样例输出】1 3 6 10 152 5 9 144 8 137 1211青蛙的约会【问题描述】两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不

6、可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 0 度处为原点，由东往西为正方向，单位长度 1 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x，青蛙 B 的出发点坐标是 y。青蛙 A 一次能跳 m 米，青蛙 B 一次能跳 n 米，两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。【要求】【数据输入】输入只包括一行 5 个整数 x，y，m，n，L，其中 xy 2000000000，0 m、 n 20000000

7、00，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 的值，给出

8、邮票面值的最佳设计，使得可在 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 猫的基因编码【问题描

9、述】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【样例输出】CC

10、CABACCBAB取石子游戏【问题描述】有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。【要求】【数据输入】输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数 a 和 b，表示两堆石子的数目，a 和 b 都不大于 1,000,000,000。【数据输出】输出对应也有若干行，每行包含一个数字 1 或 0，如果最后你是胜者，则为 1，反

11、之，则为 0。【样例输入】2 18 44 7【样例输出】010勇气的挑战【问题描述】给定 n 个点的坐标(x,y,z),且 n=50,从点 1 出发,怎么样才能走一条路径,访问每个点一次且仅一次,使走过的距离和最小?【要求】【数据输入】多组数据. 第 1 行 n,然后 n 行 3 个整数坐标【数据输出】每组一行,代表最小权和【样例输入】31 0 02 1 01 -1 0【样例输出】3.4统计同成绩学生人数Total Submission(s): 1608 Accepted Submission(s): 877【问题描述】读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。【要求】【数据输

12、入】测试输入包含若干测试用例，每个测试用例的格式为第 1 行：N 第 2 行：N 名学生的成绩，相邻两数字用一个空格间隔。第 3 行：给定分数当读到 N=0 时输入结束。其中 N 不超过 1000，成绩分数为（包含）0 到 100 之间的一个整数。【数据输出】对每个测试用例，将获得给定分数的学生人数输出。【样例输出】380 60 9060285 660560 75 90 55 75750【样例输出】102钱币兑换问题Total Submission(s): 494 Accepted Submission(s): 247【问题描述】在一个国家仅有 1 分，2 分，3 分硬币，将钱 N 兑换成硬币

13、有很多种兑法。请你编程序计算出共有多少种兑法。【要求】【数据输入】每行只有一个正整数 N，N 小于 32768。【数据输出】对应每个输入，输出兑换方法数。【样例输入】293412553【样例输出】71883113137761字串数Total Submission(s): 405 Accepted Submission(s): 90【问题描述】一个 A 和两个 B 一共可以组成三种字符串:ABB,BAB,BBA.给定若赶字母和它们相应的个数,计算一共可以组成多少个不同的字符串.【要求】【数据输入】每组测试数据分两行,第一行为 n(1=n=26),表示不同字母的个数,第二行为 n 个数 A1,A2

14、,.,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)个正整数组成的数表两两

15、相加得到 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

16、8 9 100【样例输出】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【问题描述】某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。，以后从头开

17、始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。【要求】【数据输入】本题有多个测试数据组，第一行为组数 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)

18、: 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 中的

19、数据相减，结果放到寄存器 R3 中。你的任务是：设计一个程序模拟 PpMm 的运行。【要求】【数据输入】有若干组，每组有 2 行，第一行是 2 个整数，分别表示 M1 和 M2 中的初始内容；第二行是一串长度不超过 200 的由大写字母 A 到 F 组成的命令串，命令串的含义如上所述。【数据输出】对应每一组的输入，输出只有一行，二个整数，分别表示 M1，M2 的内容；其中 M1 和 M2 之间用逗号隔开。其他说明：R1，R2，R3 的初始值为 0，所有中间结果都在-231 和 231 之间。【样例输入】100 288ABECED876356 321456ABECAEDBECAF【数据输出】38

20、8,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

21、 想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。【要求】【数据输入】本题目包含多组测试，请处理到文件结束。每组测试包含一个长度不大于 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

22、 Submission(s): 29【问题描述】Gardon 和小希玩了一个游戏，Gardon 随便想了一个数 A（首位不能为 0），把它去掉一个数字以后得到另外一个数 B，他把 A 和 B 的和 N 告诉了小希，让小希猜想他原来想的数字。不过为了公平起见，如果小希回答的数虽然不是 A，但同样能达到那个条件（去掉其中的一个数字得到 B，A 和 B 之和是 N），一样算小希胜利。而且小希如果能答出多个符合条件的数字，就可以得到额外的糖果。所以现在小希希望你编写一个程序，来帮助她找到尽可能多的解。例如，Gardon 想的是 A=31,B=3 告诉小希 N=34，小希除了回答 31 以外还可以回答

23、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):

24、 875 Accepted Submission(s): 358【问题描述】不死族的巫妖王发工资拉,死亡骑士拿到一张 N 元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉，他决定给自己买一些道具，于是他来到了地精商店前.死亡骑士：“我要买道具！”地精商人：“我们这里有三种道具，血瓶 150 块一个，魔法药 200 块一个，无敌药水 350 块一个。”死亡骑士：“好的,给我一个血瓶。”说完他掏出那张 N 元的大钞递给地精商人.地精商人：“我忘了提醒你了，我们这里没有找客人钱的习惯的，多的钱我们都当小费收了的，嘿嘿。”死亡骑士：“”死亡骑士想，与其把钱当小费送个他还不如自己多买一点道

25、具，反正以后都要买的，早点买了放在家里也好，但是要尽量少让他赚小费。现在死亡骑士希望你能帮他计算一下，最少他要给地精商人多少小费。【要求】【数据输入】输入数据的第一行是一个整数 T(1=T=100),代表测试数据的数量.然后是 T 行测试数据,每个测试数据只包含一个正整数 N(1=N=10000),N 代表死亡骑士手中钞票的面值.注意：地精商店只有题中描述的三种道具.【数据输出】对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.【样例输入】2900250【样例输出】050覆盖的面积Time Limit: 10000/5000 MS (Java/Others) Memory

26、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猴子的

27、争斗Time limit: 1s Memory limit: 32768KTotal Submit : 184 Accepted Submit : 75【问题描述】从前在一个森林里，有 N 只好斗的猴子。一开始，他们互不认识。互不认识的猴子间是无法避免争斗的，而且争斗只会发生在两只互不认识的猴子间。决斗结束后，这两只猴子和他们各自的朋友们通过这场决斗相互间都认识了，争斗便不会再发生在这一大群猴子中的任两只。由于争斗是比较激烈的，所以同一时间内不会有两场决斗一起发生。经过 N-1 次决斗后，这 N 只猴子间相互都认识了，现在问有多少种可能的决斗过程。例如 N=3，有 6 种不同的过程：12-13

28、，12-23，13-12，13-32，23-21， 23-31。【要求】【数据输入】文件里只有一个整数 N(2N1000)。【数据输出】输出一个整数，为可能的过程的总数除以 10007 的余数。【样例输入】4【样例输出】96排序Time limit: 10s Memory limit: 32768KTotal Submit : 70 Accepted Submit : 2【问题描述】通常我们对一个长度为 n(n24)的整数数列进行排序操作，其实就是讲他们按照从小到大的顺序重整。一般情况下我们可以比较任意两个数之间的大小并交换他们的位置，但这里我们限制只能数列的某一个前缀序列翻转，除此之外的任何操作都是不允许的。更精确地说，假设数列 a1，a2，an，一个合法的操作是把数列变为 ak，ak-1，a2, a1, ak+1, ak+2,