ac-m编程比赛学习入门题目集.doc

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，整数） ，接着的一行中，第一个整数 K（1 = K

2、 = 10）表示币种个数，随后是K 个互不相同的钱币面值 Ki(1 = Ki = 1000)。输入 M=0 时结束。【数据输出】每个测试用例输出一行，即凑成钱数值 M 最少需要的钱币个数。如果凑钱失败，输出“Impossible” 。你可以假设，每种待凑钱币的数量是无限多的。【样例输入】156 2 5 10 20 50 10011 20【样例输出】2Impossible#*Feli 的生日礼物【问题描述】Felicia 的生日是 11 月 1 日（和 Kitty 是同一天生的哦） 。于是 Feli 请来 Kitty 一起过生日。Kitty 带来了最新款的“Kitty 猫”玩具准备送给 Feli

3、，不过她说，这份礼物可不是白送的。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）【数据输出】对于每一组数据，输出一个 N 行的蛇

5、形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。【样例输入】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 2000000000 ，0 L 2100

7、000000。【数据输出】输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行“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【样例输出】16#*kitty 猫的基因编码【问题

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【样例输出

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

11、为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