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

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

HotLog


 

Неприводимые диаграммы Юнга

(Время: 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 выведите число l – количество неприводимых диаграмм Юнга, к которым можно преобразовать заданную. Следующие l строк должны описывать эти диаграммы. Каждая строка должна начинаться с числа t – количества рядов в соответствующей диаграмме.

Далее должно следовать t чисел – количество квадратиков в соответствующих рядах.

Примеры

INPUT.TXTOUTPUT.TXT
13
5 2 2
1
1 1
21
2
1
0

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru