In
a country circulating coins exist in denominations of 1u (unit), 5u,
10u, 20u, 25u, 50u, and 100u. Your goal is to select X of these coins
to make exactly 100u. What is the smallest value of X that makes it
impossible to reach your goal?
Note: X > 0
不負責任解題:
第一時間我沒看懂這道題目,
心想不就任何數字都可以達成嗎??
1
coin x 100
2
coins x 50
3
coins (2 x 25, 1 x 50)
....
大概要到101
coins 爆表之後才會不能湊成吧....
但我們如果假設100
是最大可能的數字(
100 coins x 1)
就會發到99
是不可能的,
因為99
個1u
不到100,
但要是其中一枚變成5u,
就會破表100
可是老實說找可能比找不可能容易
因為找可能只要找到一種方法,
但找不可能要找全部的方法再說都達不到
所以我仍然選擇由1
coin 開始試
一開始很好找到組成100的方法
但是到了超過50以後,
會發現每次都會將大量的數字都用在1u,
而且必須是5的倍數(因為其他幣值及達成的目標都是5的倍數)
慢慢的會發現一個規律,
就是20u可以換成2個10u,
1個10u
又可以換成2個5u,
如此就可以快速累積可能的組合,
然後等到到了某個數字時,
你會發現,
那個數字如果全換成1u
不夠,
但是要是退到前一個5的倍數時,
剩下的硬幣即使全換成5u
這種次小的面額,
又會破100的表
然後你就知道那個讓你達不成100u
的最小的數量到底是多少了。
沒有留言:
張貼留言