Slime Season 3 (Programming) – 60

Description

I only pay in coins because I’m hipster, but I forgot to bring my nickels today! But I really want to buy this elite gaming computer. What’s the smallest amount of coins you need to make $1,827.43 using quarters, dimes, and pennies.

Solution

Immediately, this rings dynamic programming bells on making change that I learnt in my algorithms class, however as this is american currency, we can simply use greedy instead. 

For the so-called canonical coin systems, like the one used in US and many other countries, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will produce the optimal result.[2] This is not the case for arbitrary coin systems, though: if the coin denominations were 1, 3 and 4, then to make 6, the greedy algorithm would choose three coins (4,1,1) whereas the optimal solution is two coins (3,3).

Therefore, we don’t need to use programming for this, we can simply just do the calculations by hand. 

7309 quarters + 1 dime + 7 pennies

ABCTF{7315}

 

Comments are closed.

WordPress.com.

Up ↑