Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2272. Три сына
Индукция и другие математические методыОлимпиадные задачи на русском языке
| 01/02/2016 | Региональный этап олимпиады школьников по информатике. II тур. (5) |
| 09/11/2022 | Тренировка (повторение) (проводит BOGAT) (F) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: division.in или стандартный ввод Вывод: division.out или стандартный вывод 
Послать решение 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/ 