Good day to all!

There is the following task:

McDonalds sells roast chicken in 6, 9, and 20 chunks in portions. It is possible to buy exactly 15 pieces (if you buy a portion of 6 and 9 pieces). But exactly 16 cannot be bought, because no combination of the sums of positive values ​​of 6, 9, and 20 will result in 16.

The task is to write a function that counts for any number n, whether it is possible or not to buy exactly n pieces of chicken: 6a + 9b + 20c = n ////
a, b, c can be natural numbers or 0.

There are no problems with programming, but from a mathematical point of view, I have no idea how to approach this. For any idea how to count it, I will be very grateful !!!!!

Closed due to the fact that off-topic participants Kromster , Peter Olson , torokhkun , null , LEQADA Oct 28 '15 at 8:47 .

  • Most likely, this question does not correspond to the subject of Stack Overflow in Russian, according to the rules described in the certificate .
If the question can be reformulated according to the rules set out in the certificate , edit it .

  • You are not to us. and on the matcode . And google "linear Diophantine equations." - VladD
  • Thank you all so much for your help! Decided in 2 ways: N1: brute-force by def McNuggets (n): "If" integer combination of 6, 9 and 20 equals n Otherwise returns False. "" "# 10): for b in range (10): for a in range (10): if n == 6 * a + 9 * b + 20 * c: return True return False - Konstantin Rybakov
  • n2: recursion def McNuggets (n): if (n == 0): return True else: if (n <0): return False else: if (McNuggets (n-6) or McNuggets (n-9) or McNuggets ( n-20)) == True: return True else: return False - Konstantin Rybakov
  • 3
    I vote for closing this question as not relevant, because it is a mathematical problem, not a programming question. - Peter Olson

2 answers 2

The easiest way to solve the blunt bust. Obviously, the maximum possible value of a is N / 6. The maximum possible value is b = N / 9. And so on. So we do three nested loops.

This, of course, the most naive way. The most elegant, perhaps through recursion. We ask ourselves a certain a (from an acceptable range), the task is reduced to a simpler one — the total of Na portions, which must be divided into two groups, in b and c portions. Feel where I'm going? Python, though not Lisp, is quite capable of this, I think.

    Ultimately, the task is reduced to solving an equation with three unknowns. Here is what we have:

    6a + 9b + 20c = N

    If to simplify, then:

     3(2a + 3b) + 20c = N 3(2a + 3b) = N - 20c 2a + 3b = (N-20c) / 3;

    Next, we look for such an integer value "c" so that (N - 20c) is a multiple of a triple. Suppose found (or 0).
    Found “with” and now the resulting value (N-20c) / 3 is replaced, say, by “K”:

     2a + 3b = K 2a = K - 3b a = (K-3b)/2

    Now we are looking for such an integer value of the variable "b" so that (K-3b) is an even number (a multiple of two). We get the value "b" and "a".

    I hope the general idea is clear, because personally I am not sure that the algorithm described in this form will work. We can, for example, find such a "c" that the number seems to be a multiple of three, but not such that further both "a" and "b" dock with it.