Диаграммы Юнга
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 10 | 41
4 2 2 1 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
