On Aug 12, 2010, at 11:33 AM, Paul Rubin wrote:
Baba <raoul...@gmail.com> writes:
exercise: given that packs of McNuggets can only be bought in 6, 9 or
20 packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.
Is that a homework problem? Hint: first convince yourself that a
largest number actually exists.
Good point. There is actually an upper bound. Let's take 6 packs of
20, that's 120 nuggets.
Now 121 nuggets can be reached by substituting 1 pack of 20 with 2
packs of 6 and 1 pack of 9.
122 = 4*20 + 2*(2*6+9)
123 = 3*20 + 3*(2*6+9)
...
126 = 6*20 + 6
127 = 121 + 6 = 5*20 + (2*6 + 9) + 6
... etcetera.
Now you have to find the largest number below 120, which you can
easily do with brute force (untested):
can_be_bought = [False for i in range(120)]
for twenties in range(6):
for nines in range(14):
for sixes in range(20):
can_be_bought[twenties*20+nines*9+sixes*6] = True
for i in reverse(range(120)):
if not can_be_bought[i]: return i
Cheers, Roald
--
http://mail.python.org/mailman/listinfo/python-list
