Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Диаграммы Юнга

(Время: 1 сек. Память: 16 Мб Сложность: 74%)

Диаграммы Юнга используются для того, чтобы изобразить разбиение числа на слагаемые. Разбиение числа n на слагаемые представляет собой сумму вида n = m1 + m2 + … + mk, где m1 ≥ m2 ≥ … ≥ mk.

Диаграмма состоит из n квадратиков, организованных в виде k рядов, где k количество слагаемых в разбиении. Ряд, соответствующий числу mi, содержит mi квадратиков. Все ряды выровнены по левому краю и упорядочены от более длинного к более короткому.

Например, диаграмма Юнга, приведенная на рисунке, соответствует разбиению 10 = 5 + 3 + 2.

Иногда можно вписать одну диаграмму Юнга в другую. Диаграмму X можно вписать в диаграмму Y , если можно удалить некоторые квадратики из диаграммы Y так, чтобы получилась диаграмма X. Отметим, что разрешается только удалять некоторые квадратики, вращать или отражать диаграмму не разрешается. Например, диаграмма для разбиения 5 = 3 + 2 может быть вписана в диаграмму для разбиения 10 = 5 + 3 + 2, как показано на рисунке.

С другой стороны, диаграмму для разбиения 8 = 4+4 нельзя вписать в диаграмму для разбиения 10 = 5 + 3 + 2. Для заданного n найдите такое разбиение n на слагаемые, что в соответствующую ему диаграмму Юнга можно вписать максимальное количество различных диаграмм. Например, в диаграмму для разбиения 10 = 5 + 3 + 2 можно вписать 36 различных диаграмм. Однако это не максимальное значение. В диаграмму для разбиения 10 = 4 + 2 + 2 + 1 + 1 можно вписать 41 диаграмму Юнга.

Входные данные

Входной файл INPUT.TXT содержит целое число n (1 ≤ n ≤ 100).

Выходные данные

На первой строке выходного файла OUTPUT.TXT выведите максимальное число диаграмм Юнга, которые можно вписать в некоторую диаграмму, соответствующую разбиению на слагаемые числа n. На второй строке выведите одно или более целых чисел - количество квадратиков в каждом из рядов оптимальной диаграммы.

Пример

INPUT.TXTOUTPUT.TXT
11041
4 2 2 1 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483