acm编程比赛入门题目.pdfVIP

acm编程比赛入门题目 acm编程比赛入门题目集 最少钱币数： 【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一 6 2 5 10 20 般而言有多种方式。例如：给定了 种钱币面值为 、 、 、 、 50 100 15 5 2 1 5 3 、 ，用来凑 元，可以用 个 元、 个 元，或者 个 5 1 5 1 10 2 元，或者 个 元、 个 元，等等。显然，最少需要 个钱币 15 才能凑成 元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需 要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待 M 1lt; Mlt; 2000 凑的钱数值 （ ，整数），接着的一行中，第 K 1lt; Klt; 10 K 一个整数 （ ）表示币种个数，随后是 个互不 相同的钱币面值Ki(1lt; Kilt; 1000)。输入M 0 时结束。 M 【数据输出】每个测试用例输出一行，即凑成钱数值 最少需要的 钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种 待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 12 0 【样例输出】 2 Impossible Feli 的生日礼物 【问题描述】 Felicia 11 1 Kitty Feli 的生日是 月 日 （和 是同一天生的哦）。于是 请来Kitty 一起过生日。Kitty 带来了必威体育精装版款的 “Kitty 猫”玩具准备 Feli Feli 送给 ，不过她说，这份礼物可不是白送的。 要帮她一个忙， 才能够得到心仪已久的玩具。 Kitty 说，“Kitty 猫”玩具已经卖出了 n! nlt; 10^100*_* Kitty 个， ， 想知道确切的数字，而不是无聊的 Feli n! “一个数加个感叹号”。 听了大吃一惊。要知道，算出 是一个 Feli Kitty Feli n! Kitty 无比艰巨的任务。 告诉 ，就算 算出 ， 也看不 n 20 Kitty 下去，因为当 时，计算机的长整型已经存不下了 （ 只能 1-9 Kitty n! 接受 之间的数字）。于是 说，你只要告诉我 最后一位非 0 Feli 的数就可以了。 想了想，立刻动手