Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
264. Сумма кубов
Рекурсивный переборСокращение перебора с помощью идеи
Олимпиадные задачи на русском языке
| 02/07/2007 | Лето 2007 дорешивание (10C) |
| 23/07/2007 | Лето 2007 - 10 (C) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Известно, что любое натуральное число можно представить в виде суммы
не более чем четырёх
квадратов каких-то натуральных чисел. Вася решил придумать
аналогичное утверждение для кубов — он
хочет узнать, сколько же кубов достаточно для представления любого
числа. Первая рабочая гипотеза — восемь.
Выяснилось, что почти все чиcла, которые Вася смог придумать,
представляются в виде суммы не более чем восьми кубов.
Однако число 239, например, не допускает такого
представления. Вася заинтересовался этим вопросом, и
теперь он хочет найти какие-либо
другие такие числа, а также, возможно, какую-либо закономерность в
представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно
вида всех чисел, которые не представляются в виде суммы восьми кубов.
Помогите Васе написать программу, которая проверяла бы, возможно ли представить
данное натуральное число в виде суммы не более чем восьми кубов натуральных
чисел, и если это возможно, то находила бы какое-либо такое представление.
Ввод
Натуральное число `N\ ≤\ 2\ 000\ 000\ 000`.
Вывод
Не более восьми натуральных чисел, кубы которых в сумме дают `N`.
Если искомого представления
не существует, то в выходной файл необходимо вывести слово
"IMPOSSIBLE".
Пример ввода 1
17
Пример вывода 1
2 2 1
Пример ввода 2
239
Пример вывода 2
IMPOSSIBLE
