Calculate a tip using the smallest number of coins Most tip calculator apps simply take a flat percentage of the meal price.  So, for example, if your meal is $23.45, you can leave a 15% tip = $3.52, or a more generous 20% tip = $4.69.

Convenient enough for credit card users.  But not so if you prefer to leave cash tips, in which case these oddball cent amounts get in the way.  So let's modify the idea to be more convenient for cash users.

Your assignment

Write, in as few bytes as possible, a program or function that takes as input:


Price of the meal
Minimum tip percentage
Maximum tip percentage


And output any tip amount within the range [price * min_percentage / 100, price * max_percentage / 100] that minimizes the number of bills/banknotes and coins required.

Assume the US monetary denominations of 1¢, 5¢, 10¢, 25¢, $1, $5, $10, $20, $50, and $100.

Example

Here is a non-golfed example program in Python:

import math
import sys

# Do the math in cents so we can use integer arithmetic
DENOMINATIONS = [10000, 5000, 2000, 1000, 500, 100, 25, 10, 5, 1]

def count_bills_and_coins(amount_cents):
    # Use the Greedy method, which works on this set of denominations.
    result = 0
    for denomination in DENOMINATIONS:
        num_coins, amount_cents = divmod(amount_cents, denomination)
        result += num_coins
    return result

def optimize_tip(meal_price, min_tip_percent, max_tip_percent):
    min_tip_cents = int(math.ceil(meal_price * min_tip_percent))
    max_tip_cents = int(math.floor(meal_price * max_tip_percent))
    best_tip_cents = None
    best_coins = float('inf')
    for tip_cents in range(min_tip_cents, max_tip_cents + 1):
        num_coins = count_bills_and_coins(tip_cents)
        if num_coins &lt; best_coins:
            best_tip_cents = tip_cents
            best_coins = num_coins
    return best_tip_cents / 100.0

# Get inputs from command-line
meal_price = float(sys.argv[1])
min_tip_percent = float(sys.argv[2])
max_tip_percent = float(sys.argv[3])
print('{:.2f}'.format(optimize_tip(meal_price, min_tip_percent, max_tip_percent)))


Some sample input and output:

~$ python tipcalc.py 23.45 15 20
4.00
~$ python tipcalc.py 23.45 15 17
3.55
~$ python tipcalc.py 59.99 15 25
10.00
~$ python tipcalc.py 8.00 13 20
1.05
JavaScript (ES6), 93 bytes

(x,m,M)=&gt;(g=(t,c=1e4)=&gt;t&gt;x*M?0:t&lt;x*m?[...'1343397439'].some(d=&gt;g(t+(c/=-~d/2)))*r:r=t)(0)/100


Try it online!

How?

We recursively compute a sum of bill/coin values until it falls within the acceptable range, always trying the highest value first.

This is guaranteed to use the minimum amount of bills and coins because for any solution \$\{b_0,\dots,b_n\}\$ returned by this algorithm:


all terms \$b_0\$ to \$b_n\$ are required, otherwise the algorithm would have selected \$\{b_0,\dots,b_{k-1},x\}\$ with \$x \ge b_k\$ for some \$0 \le k &lt; n\$
for any \$0 \le k &lt; n\$ and any \$x \le b_n\$, \$\{b_0,\dots,b_{k-1},b_k-x,b_{k+1},\dots,b_n\}\$ cannot be a solution, otherwise \$\{b_0,\dots,b_{n-1}\}\$ would have been selected
there may exist some \$0 &lt; x &lt; b_n\$ such that \$\{b_0,\dots,b_{n-1},x\}\$ is also valid, but that would not use less bills/coins than the selected solution


The bill/coin values \$c_n\$ expressed in cents are computed with:

$$\begin{cases}c_0=10000\\c_{n+1}=\dfrac{c_n}{(d_n+1)/2}\end{cases}$$

where \$(d_0,\dots,d_9) = (1,3,4,3,3,9,7,4,3,9)\$.

 n | c(n)  | d(n) | k = (d(n)+1)/2 | c(n+1) = c(n)/k
---+-------+------+----------------+-----------------
 0 | 10000 |   1  | (1+1)/2 = 1    |      10000
 1 | 10000 |   3  | (3+1)/2 = 2    |       5000
 2 |  5000 |   4  | (4+1)/2 = 2.5  |       2000
 3 |  2000 |   3  | (3+1)/2 = 2    |       1000
 4 |  1000 |   3  | (3+1)/2 = 2    |        500
 5 |   500 |   9  | (9+1)/2 = 5    |        100
 6 |   100 |   7  | (7+1)/2 = 4    |         25
 7 |    25 |   4  | (4+1)/2 = 2.5  |         10
 8 |    10 |   3  | (3+1)/2 = 2    |          5
 9 |     5 |   9  | (9+1)/2 = 5    |          1