Вася хочет представить число 2018 в виде суммы кубов натуральных чисел, содержащих наименьшее количество слагаемых. Помогите ему это сделать.

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

Идея решения: если можно использовать только 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])