ACM编程竞赛入门：凑钱问题与阶乘挑战

"acm编程比赛入门题目集" 本资源是一个针对初学者的ACM编程比赛入门题目集，旨在帮助新手熟悉编程竞赛的题型和解决策略。其中包含两道示例题目，分别是“最少钱币数”和“Feli的生日礼物”。 首先，我们来看第一道题目——“最少钱币数”。这是一道典型的组合优化问题，要求根据给定的钱币面值，找出凑成特定金额所需的最少钱币数量。给定的输入包括待凑的钱数值M（1 <= M <= 2000，整数）和不同面值的钱币种类K（1 <= K <= 10），随后是K个互不相同的钱币面值Ki（1 <= Ki <= 1000）。题目假设每种钱币的数量无限。解决这个问题通常采用动态规划的方法，从最小的钱数开始，逐步增加，每次尝试用当前面值的钱币去替换已有组合中的钱币，以减少总数量，直到达到目标金额或无法继续减少。若无法凑出目标金额，则输出"Impossible"。 第二题是“Feli的生日礼物”，它涉及计算阶乘的问题。题目中提到，Kitty想要知道n!（n的阶乘）最后一位非零数字。由于n!的数值可能会非常大，超过常规整型变量的存储范围，因此我们需要找到一种方法仅计算阶乘尾部的非零数字。解决这个问题可以利用模运算，对一个足够大的质数（大于10^9）取模，这样可以避免计算整个阶乘，只关注结果的模值。此外，对于寻找最后一位非零数字，我们可以从大到小逐个去除2和5的影响，因为它们会导致0出现在阶乘的末尾，直到找到第一个不会使末尾为0的因子。 这两道题目涵盖了基本的算法思想，如动态规划和模运算，以及对数据类型的理解和边界条件处理，适合ACM编程比赛初学者进行练习和提升。通过解决这些问题，参赛者可以提高自己的编程技巧，增强问题分析和算法设计能力。