ACM编程竞赛入门：最少钱币数与Feli的生日礼物问题

"这个资源是面向ACM编程比赛初学者的题目集，包含了两道典型问题，旨在帮助新手熟悉竞赛环境和编程技巧。" 第一题是"最少钱币数"问题，这是一道经典的动态规划题目。问题背景是给定一些不同面值的钱币，要求找出凑成特定金额时最少需要使用多少个钱币。题目规定每种钱币的数量是无限的，且给定的钱币面值互不相同。考生需要编写程序，输入包括待凑的钱数M（1 <= M <= 2000）和钱币种类数K（1 <= K <= 10），接着是K个钱币的面值（1 <= Ki <= 1000）。当M=0时，输入结束。程序输出应该是凑成M所需的最少钱币数，若无法凑成则输出"Impossible"。 解决这类问题的关键在于设计合适的动态规划状态转移方程。通常可以定义一个数组dp[i]表示凑成i元最少需要的钱币数，然后按照钱币面值从小到大的顺序进行填充。在填充过程中，对于每个面值Ki，更新dp数组的值，使得dp[j]尽可能小，其中j >= i。最后，dp[M]即为所求的答案。 第二题是"Feli的生日礼物"，这是一道关于阶乘尾部非零数字的计算问题。题目要求计算n!（n的阶乘），但只需要最后一位非零数字。由于n!可能非常大，超出常规整型变量的范围，因此不能直接计算整个阶乘。为了解决这个问题，可以采用模运算，计算n!对某个较大的质数p取模后的结果，这样可以避免数值溢出。同时，注意到题目要求找到最后一位非零数字，这可以通过观察n!对10取模的结果变化来实现。每次乘以n后，如果结果对10取模不等于0，那么当前的n就是导致最后一位非零数字变化的那个数。通过这种方法，可以有效地计算出n!的最后一位非零数字，而不需要计算完整的阶乘。 这两道题目分别考察了动态规划和数论在算法竞赛中的应用，对于ACM编程比赛的新手来说，是很好的实践和学习素材。通过解决这些问题，参赛者可以提升自己的编程思维和问题解决能力。