Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Сумма кубов
Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов каких-то натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько же кубов достаточно для представления любого числа. Первая рабочая гипотеза - восемь. 

Выяснилось, что почти все чиcла, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Вася заинтересовался этим вопросом, и теперь он хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов. 

Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.
Входные данные:
Натуральное число N <= 2*109.
Выходные данные:
Не более восьми натуральных чисел, кубы которых в сумме дают N. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.

Примеры:
input.txt output.txt
1 17 2 2 1
2 239 IMPOSSIBLE

Сложность задачи: 35%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи
Обозначим задачу нахождения разложения числа N в сумму K кубов натуральных чисел (N,K).Тогда для того, чтобы решить исходную задачу, нужно найти такое число X, что (N-X3,K-1) имеет решение. Задача свелась к аналогичной меньшей размерности, значит, возможно ее решение рекурсивным методом.
Показать обсуждение


На сайте гостей 18, зарегистрированных 1:
Shizao,
[Данные за последние 5 минут]