images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
16/02/2025 17:30:43

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2272. Три сына

Ограничения: время – 1s/2s, память – 256MiB Ввод: division.in или стандартный ввод Вывод: division.out или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Во владениях короля Флатландии находится прямая дорога длиной `n` километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.
У короля три сына: младший, средний и старший. Король решил, что в заповедник не войдут участки лесного массива, которые он оставит сыновьям в наследство. При составлении завещания король хочет, чтобы для участков выполнялись следующие условия:
  • каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры `a times a`, `b times b` и `c times c`;
  • стороны квадратов должны полностью покрывать дорогу: величина `a + b + c` должна быть равна `n`;
  • участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство `a < b < c`;
  • суммарная площадь участков `a^2 + b^2 + c^2` должна быть минимальна.
Требуется написать программу, которая по заданной длине дороги определяет размеры участков, которые следует выделить сыновьям короля.
Формат входного файла
Входной файл содержит одно целое число `n` (`6 ≤ n ≤ 10^9`).
Формат выходного файла
Выходной файл должен содержать три целых положительных числа, разделенных пробелами: `a`, `b` и `c` – длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

Пример ввода

6

Пример вывода

1 2 3
Описание подзадач и системы оценивания
В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.
Подзадача 1 (25 баллов)
`n ≤ 50`.
Подзадача 2 (25 баллов)
`n ≤ 2000`.
Подзадача 3 (25 баллов)
`n ≤ 40 000`.
Подзадача 4 (25 баллов)
`n ≤ 10^9`.
По запросу сообщается результат окончательной проверки на каждом тесте.
Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/
loading