ps2b.py

#########################################
#WARNING! Exponential order of compexity#
#########################################

def isSolution(coefficients, number_of_nuggets):
    '''returns True if there is a solution to a*x + b*y + c*z = n and None if there is no solution'''
    for k in range(0,number_of_nuggets+1):
        for m in range(0,number_of_nuggets+1):
            for j in range(0,number_of_nuggets+1):
                current_number_of_nuggets = coefficients[0]*j+coefficients[1]*m+coefficients[2]*k
                if current_number_of_nuggets == number_of_nuggets:
                    isSolution = True
                    #print str(coefficients[0])+"*"+str(j)+"+"+str(coefficients[1])+"*"+str(m)+"+"+str(coefficients[2])+"*"+str(k)+"="+str(current_number_of_nuggets) # for debugging
                    return isSolution

while True:
    n = input ("Input integer number of McNuggets between 1 and 200:")
    if 0 < n < 201:
        break

a = input ("Input the first coefficient 'a':")
b = input ("Input the second coefficient 'b':")
c = input ("Input the third coefficient 'c':")
packages = (a,b,c)
packages = sorted(packages)

if a > n and b > n and c > n:
    print str(n)+" nuggets can't be bought with packages of "+str(a)+", "+str(b)+" "+"and "+str(c)+" nuggets."
else:

    the_largest_number = 0
    for j in range(1,n+1):
        if isSolution(packages,j) == None:
            the_largest_number = j
            # print  "isSolution == None "+str(j)+" nuggets cannot be bought in exact quantity" # for debugging
    print "Given package sizes of "+str(packages[0])+", "+str(packages[1])+", and "+str(packages[2])+", the largest number of McNuggets that\ncannot be bought in exact quantity is: "+str(the_largest_number)