Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1128. Экскурсия
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 06/11/2008 | Муниципальный этап олимпиады по информатике (4) |
| 09/07/2013 | Лето 2013-6 (I) |
| 20/07/2016 | Лето 2016 - 12 (C) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Экскурсии под руководством Ивана Петровича проходят всегда очень организованно.
Ивану Петровичу особенно нравятся построения в форме квадрата, так как если какой-то школьник отстанет от группы,
его отсутствие в квадрате является более заметным, чем при использовании построения в форме шеренги и колонны по одному.
Поэтому школьники разбиваются на несколько групп, для которых возможно построение в форме квадрата. Чтобы разные группы
были хорошо различимы визуально, требуется, чтобы в разных группах было разное число школьников.
Из 100 школьников можно сделать одну группу `10\ times\ 10`, или две группы `6\ times\ 6` и `8\ times\ 8`, но лучше
с точки зрения Ивана Петровича сделать 5 групп `1\ times\ 1`, `3\ times\ 3`, `4\ times\ 4`, `5\ times\ 5` и
`7\ times\ 7`.
Напишите программу, которая находит разбиение `N` школьников на группы в форме квадратов, среди которых нет двух одинаковых
по количеству. Количество групп в разбиении должно быть как можно больше.
В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 10^5`) – число школьников, отправляющихся на экскурсию.
Если разбиение найдено, то вывести в первой строке количество групп в разбиении, а во второй строке – в
порядке возрастания размеры стороны квадратных групп.
Если существует несколько разбиений с максимальным количеством групп, то можно вывести одно из них (любое).
Если разбиения не существует, в первой строке вывести 0.
Пример ввода
100
Пример вывода
5 1 3 4 5 7
