Question

Вася хочет представить число 2018 в виде суммы кубов натуральных чисел, содержащих наименьшее количество слагаемых. Помогите ему это сделать.
В качестве ответа выведите слагаемые суммы в порядке возрастания, разделяя их одинарными пробелами. Например, для числа 10 представление с наименьшим количеством слагаемых есть 8+1+1 (8 – это 2 в кубе, 1 – это 1 в кубе), поэтому в качестве ответа нужно было бы вывести такой набор чисел: 1 1 8. Если возможных ответов с представлением числа в виде наименьшего возможного количества слагаемых несколько, выведите любой.

Answer 1

Идея решения: если можно использовать только 1^3, то ответ очевиден, дальше пытаемся узнать, не станет ли лучше, если разрешить использовать 2^3, 3^3 и т.д.

Программа на python 3, решающая эту задачу для произвольного n (в условии n = 2018):
n = int(input())
 
lens = list(range(n + 1))
max_terms = [1] * (n + 1)
 
t = 2
while t**3 <= n:
  max_term = t**3
  for k in range(max_term, n + 1):
    if lens[k] > 1 + lens[k - max_term]:
      lens[k] = 1 + lens[k - max_term]
      max_terms[k] = max_term
  t += 1
 
for_print = []
for _ in range(lens[n]):
  for_print.append(max_terms[n])
  n -= max_terms[n]
 
print(*for_print[::-1])