acm编程比赛入门题目集

《acm编程比赛入门题目集》由会员分享，可在线阅读，更多相关《acm编程比赛入门题目集（52页珍藏版）》请在金锄头文库上搜索。

1、程序设计比赛试题主办方:迅翔计算机协会最少钱币数：【问题描述】这是一个古老而又经典的问题。 用给定的几种钱币凑成某个钱数， 一般而言有多种方式。 例 如：给定了 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【样例输出 】2Impossible8Feli 的生日礼物【问题描述】Felicia 的生日是 11月 1 日（和 Kitty 是同一天生的哦） 。于是 Feli 请来 Kitty 一起过生日。 Kitty

3、带来了最新款的“ Kitty 猫”玩具准备送给 Feli ，不过她说，这份礼物可不是白送的。Feli 要帮她一个忙，才能够得到心仪已久的玩具。 Kitty 说，“ Kitty 猫”玩具已经卖出了 n!个，*=10X00 *_* , 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【样例输出 】蛇行矩阵【问题描述】蛇形矩阵是由 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,其中x丰y 200000

7、0000 , 0 m、 n 2000000000， 0 L 2100000000。【数据输出 】输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行 Impossible【样例输入 】1 2 3 4 5【样例输出 】敲七【问题描述】输出 7 和 7 的倍数，还有包含 7的数字例如（ 17，27，37.70，71，72，73.） 【要求 】【数据输入】一个整数N。 （N不大于30000）【数据输出 】从小到大排列的不大于 N 的与 7 有关的数字，每行一个。【样例输入 】20【样例输出 】71417连续邮资问题【问题描述】G 国发行了 n 种不同面值的邮票，并且规定每张信封上最多只允许贴 m

8、张邮票。连续邮资 问题要求对于给定的 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

9、 15 17 2【样例输出 】16kitty 猫的基因编码【问题描述】kitty的基因编码如下定义：kitty的基因由一串长度 2Ak (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【要求 】【数据输入】一行，长度为2Ak，为kitty猫的01基因编码，有多个数据【数据输出 】一行，由 ABC 构成的

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

11、对应也有若干行，每行包含一个数字 1 或 0，如果最后你是胜者，则为1，反之,则为 0。【样例输入 】2 18 44 7【样例输出 】010勇气的挑战【问题描述】,访问每个点一次且仅给定n个点的坐标（x,y,z）,且*=50,从点1出发,怎么样才能走一条路径 一次 ,使走过的距离和最小 ?【要求 】【数据输入】多组数据第1行n,然后n行3个整数坐标【数据输出 】每组一行 ,代表最小权和 【样例输入 】30 0 01 1 01 -1 0【样例输出 】3.4Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java

12、/Others)Total Submission(s): 1608Accepted Submission(s): 877统计同成绩学生人数【问题描述】读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。【要求 】【数据输入 】测试输入包含若干测试用例，每个测试用例的格式为第 1 行： N第 2 行： N 名学生的成绩，相邻两数字用一个空格间隔。第 3 行：给定分数当读到 N=0 时输入结束。其中 N 不超过 1000，成绩分数为(包含) 0 到 100 之间的一个整 数。【数据输出 】对每个测试用例，将获得给定分数的学生人数输出。【样例输出 】380 60 9060285 660560

13、75 90 55 75750【样例输出 】102钱币兑换问题【问题描述】在一个国家仅有 1分， 2分， 3分硬币，将钱 N 兑换成硬币有很多种兑法。请你编程序计算 出共有多少种兑法。【要求 】【数据输入 】每行只有一个正整数 N ，N 小于 32768。【数据输出 】对应每个输入，输出兑换方法数。【样例输入 】293412553【样例输出 】71883113137761字串数【问题描述】一个 A 和两个 B 一共可以组成三种字符串 :ABB,BAB,BBA. 给定若赶字母和它们相应的个数 ,计算一共可以组成多少个不同的字符串.【要求 】【数据输入 】每组测试数据分两行 ,第一行为 n(1=n=

14、26), 表示不同字母的个数 ,第二行为 n 个数 A1,A2,.,An(1=Ai=12), 表示每种字母的个数 .测试数据以 n=0 为结束 .【数据输出】对于每一组测试数据，输出一个m,表示一共有多少种字符串.【样例输入 】21 232 2 20【样例输出 】390小希的数表【问题描述】Gardon 昨天给小希布置了一道作业，即根据一张由不超过 5000 的 N(3=N=100) 个正整数 组成的数表两两相加得到 N*(N-1)/2 个和，然后再将它们排序。例如，如果数表里含有四个 数 1， 3，4，9，那么正确答案是 4，5，7， 10，12，13。小希做完作业以后出去玩了一阵， 可是下

15、午回家时发现原来的那张数表不见了， 好在她做出的答案还在， 你能帮助她根据她的 答案计算出原来的数表么？【要求 】【数据输入 】包含多组数据，每组数据以一个 N 开头，接下来的一行有按照大小顺序排列 的 N*(N-1)/2 个数，是小希完成的答案。文件最后以一个 0 结束。假设输入保证解的存在性和唯一性。【数据输出 】对于每组数据，输出原来的数表。它们也应当是按照顺序排列的。【样例输入 】44 5 7 10 12 1345 6 7 8 9 100【样例输出 】1 3 4 92 3 4 6士兵队列训练问题【问题描述】 某部队进行新兵队列训练， 将新兵从一开始按顺序依次编号， 并排成一行横队， 训练的规则 如下： 从头开始一至二报数