Неприводимые диаграммы Юнга
(Время: 2 сек. Память: 16 Мб Сложность: 52%)
Диаграммы Юнга используются для того, чтобы изобразить разбиение числа на слагаемые. Разбиение числа n на слагаемые представляет собой сумму вида n = m1+ m2+ . . . + mk, где m1≥ m2≥ . . . ≥ mk.
Диаграмма состоит из n квадратиков, организованных в виде k рядов, где k –количество слагаемых в разбиении. Ряд, соответствующий числу mi, содержит mi квадратиков. Все ряды выровнены по левому краю и упорядочены от более длинного к более короткому.
Например, диаграмма Юнга, приведенная на рисунке, соответствует разбиению 9 = 5 + 2 + 2.
Рассмотрим один метод преобразования диаграмм Юнга. Разрешается выбрать любые два соседних квадратика и удалить их. При этом накладывается следующее ограничение: после преобразования оставшийся набор квадратиков должен быть корректной диаграммой Юнга, верхний левый квадратик которой расположен в том же месте, что и у исходной диаграммы (либо должна остаться пустая диаграмма).
Например, удалив последние квадратики второго и третьего ряда из приведенной выше диаграммы, мы получаем диаграмму для разбиения 7 = 5 + 1 + 1.
Удаляя два последних квадратика первого ряда из этой исходной диаграммы, мы получаем диаграмму для разбиения 7 = 3 + 2 + 2.
И еще один способ преобразовать эту диаграмму – удалить последний ряд целиком. Диаграмма, которую нельзя преобразовать указанным способом, называется неприводимой. В частности, пустая диаграмма Юнга является неприводимой.
Каждую диаграмму можно преобразовывать до тех пор, пока она не станет неприводимой. Вообще говоря, может быть несколько способов преобразовать диаграмму к неприводимой. По заданной диаграмме Юнга найдите все неприводимые диаграммы, в которые ее можно преобразовать.
Входные данные
Первая строка входного файла INPUT.TXT содержит число k – количество рядов в диаграмме (1 ≤ k ≤ 105). Вторая строка содержит k целых чисел: m1, m2, ..., mk. Сумма n = m1+ m2+ . . . + mk не превышает 108.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите число p – количество неприводимых диаграмм Юнга, к которым можно преобразовать заданную. Следующие p строк должны описывать эти диаграммы. Каждая строка должна начинаться с числа t – количества рядов в соответствующей диаграмме.
Далее должно следовать t чисел – количество квадратиков в соответствующих рядах.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
5 2 2 | 1
1 1 |
| 2 | 1
2 | 1
0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
