硬币组合不可唯一确定的最小硬币数
Coin Identifier
题目详情
Brian 口袋里有 0.60 美元,只由 5 分、10 分、25 分硬币组成。若他共有 枚硬币,求最小的 使得这些硬币的具体张数(各面额多少枚)无法被唯一确定。
Brian walks to the convenience store with NN$ such that the quantities of each type of coin in Brian's pocket can't be uniquely identified.
解析
最小为 。
例如 0.40 可用 4 枚硬币表示为:1 枚 25 分 + 3 枚 5 分,或 4 枚 10 分。把两种方案都再加 2 枚 10 分即可得到 0.60 且硬币数同为 6。
Original Explanation
Clearly, and don't work, as you can't obtain N = 321$ dime work. There are no other ways to obtain the sum besides this.
Now, note that is the smallest denomination that can be written in two different ways using the same amount of coins. Namely, we can use coins to write as quarter and nickels OR dimes. Therefore, we can just append dimes to each of these combinations, and we get that is the smallest value for which this is true.
To verify is the smallest value, we know that the number is at least , as otherwise we can't utilize quarters, so test and and see that they don't work.