def countCoinSlow(c):
    """
    THIS FUNCTION IS VERY SLOW AND INEFFICIENT, IT ONLY EXISTS TO SHOW THE IMPORTANCE OF EFFICIENT ALGORITHMS.
    Given a value in cents as a parameter, this function recursively calculates the number of combinations of
    pennies (1 cent), nickels (5 cents), dimes (10 cents),
    quarters (25 cents), and half dollar coins (50 cents)
    that add up to the given value.
    """
    combinations = []
    if c >= 1:  # creates a branch where a penny is added to every combination
        subCombinations = countCoinSlow(c - 1)
        if len(subCombinations) != 0:
            for i in subCombinations:
                i.append(1)
                i.sort()
        else:
            subCombinations.append([1])
        adding = [x for x in subCombinations if x not in combinations]  # removes combinations already in the list
        combinations.extend(adding)
    if c >= 5: # creates a branch where a nickel is added to every combination
        subCombinations = countCoinSlow(c - 5)
        if len(subCombinations) != 0:
            for i in subCombinations:
                i.append(5)
                i.sort()
        else:
            subCombinations.append([5])
        adding = [x for x in subCombinations if x not in combinations] # removes combinations already in the list
        combinations.extend(adding)
    if c >= 10: # creates a branch where a dime is added to every combination
        subCombinations = countCoinSlow(c - 10)
        if len(subCombinations) != 0:
            for i in subCombinations:
                i.append(10)
                i.sort()
        else:
            subCombinations.append([10])
        adding = [x for x in subCombinations if x not in combinations] # removes combinations already in the list
        combinations.extend(adding)
    if c >= 25: # creates a branch where a quarter is added to every combination
        subCombinations = countCoinSlow(c - 25)
        if len(subCombinations) != 0:
            for i in subCombinations:
                i.append(25)
                i.sort()
        else:
            subCombinations.append([25])
        adding = [x for x in subCombinations if x not in combinations] # removes combinations already in the list
        combinations.extend(adding)
    if c >= 50: # creates a branch where a half-dollar is added to every combination
        subCombinations = countCoinSlow(c - 50)
        if len(subCombinations) != 0:
            for i in subCombinations:
                i.append(50)
                i.sort()
        else:
            subCombinations.append([50])
        adding = [x for x in subCombinations if x not in combinations] # removes combinations already in the list
        combinations.extend(adding)
    return combinations


def countCoinFast(c):
    """
        Given a value in cents as a parameter,
        this function uses dynamic programing to calculate the number of combinations of
        pennies (1 cent), nickels (5 cents), dimes (10 cents),
        quarters (25 cents), and half dollar coins (50 cents)
        that add up to the given value.
    """
    combinations = []
    amounts = [1, 5, 10, 25, 50]
    for i in range(0, c + 1):
        # This loop serves to initialize the 2-dimensional list
        combinations.append([])
        for amount in amounts:
            combinations[i].append(0)
    for amount in range(len(amounts)):
        for i in range(0, c + 1):
            if amount == 0: # Fill the penny row with 1's since any number can be represented only 1 way with pennies
                combinations[i][amount] = 1
            else:
                remains = i
                combinations[i][amount] = 0
                while remains >= 0:
                    # Increment the currently calculated value by the number of combinations for the remaining cents
                    # that was calculated using the previous type of coin
                    combinations[i][amount] += combinations[remains][amount - 1]
                    remains -= amounts[amount]
    return combinations[c][4] # The absolute last cell is the total number of unique coin combinations


if __name__ == "__main__":
    cents = 0
    while cents != -1:
        try:
            cents = int(input("Please insert a cent amount: "))
        except ValueError:
            print("Not an Integer Value")
            continue
        method = input("Fast(f) or Slow(s)? ")
        if method == 'f':
            combinations = countCoinFast(cents)
        elif method == 's':
            combinations = len(countCoinSlow(cents))
        else:
            print("Invalid Method Type")
            continue
        print("Number of possible combinations = " + str(combinations))