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

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

HotLog


 

Разбиения множества

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

Рассмотрим множество, состоящее из первых n натуральных чисел: Nn = {1, 2, …, n}. Разбиение - это представление этого множества в виде объединения одного или нескольких непустых попарно непересекающихся множеств. Примерами разбиений для n = 5 являются:

{1, 2, 3, 4, 5} = {1, 2, 3} U {4, 5}
{1, 2, 3, 4, 5} = {1, 3, 5} U {2, 4}
{1, 2, 3, 4, 5} = {1, 2, 3, 4, 5}
{1, 2, 3, 4, 5} = {1} U {2} U {3} U {4} U {5}

Всего существует 52 разбиения множества N5. Заметим, что разбиения, отличающиеся только порядком объединяемых множеств, не различаются.

Разбиения множества Nn можно упорядочить лексикографически. Для того, чтобы определить этот порядок, вначале определим лексикографический порядок на подмножествах Nn. Будем говорить, что подмножество A={a1, a2, ..., ak} (a1 < a2 < ... < ak) множества Nn лексикографически меньше подмножества B={b1, b2, ..., bm} (b1 < b2 < ... < bm) множества Nn и писать A < B, если верно одно из следующих утверждений:

  • найдётся i, такое что a1 = b1, a2 = b2, ..., ai - 1 = bi - 1 и ai < bi;
  • k < m и при этом a1 = b1, a2 = b2, ..., ak = bk.

Таким образом, для любых двух подмножеств A и B верно ровно одно из трёх утверждений: или A < B, или A совпадает с B, или B < A, а также есть транзитивность: если A < B и B < C, то A < C. Теперь определим каноническое представление разбиения как представление, в котором объединяемые множества упорядочены лексикографически.

Разбиения упорядочиваются лексикографически следующим образом. Разбиение Nn = A1 U A2 U … U Ak лексикографически меньше разбиения Nn = B1 U B2 U … U Bm, если существует такое i, что A1 = B1, A2 = B2, . . . , Ai-1 = Bi-1 и Ai < Bi.

По разбиению множества Nn найдите следующее в лексикографическом порядке разбиение.

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

Входной файл INPUT.TXT содержит несколько описаний тестов. Каждое описание является каноническим представлением разбиения. Первая строка описания содержит n и k - количество элементов в разбиваемом множестве и количество частей в разбиении (1 ≤ n ≤ 200). Последующие k строк содержат элементы разбиения. Элементы каждого множества упорядочены по возрастанию. Описания тестов отделены друг от друга пустыми строками. Последняя строка входного файла содержит два нуля. Этот тест не должен обрабатываться. Сумма n по всем описаниям не превосходит 2000.

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

В выходной файл OUTPUT.TXT для каждого теста выведите следующее в лексикографическом порядке разбиение. Если разбиение во входном файле является последним в лексикографическом порядке, выведите первое в лексикографическом порядке. Используйте тот же формат, что и во входном файле. Отделяйте разбиения друг от друга пустыми строками. Элементы каждого множества следует выводить в порядке возрастания.

Пример

INPUT.TXTOUTPUT.TXT
15 2
1 2 3
4 5

5 2
1 3 5
2 4

5 1
1 2 3 4 5

5 5
1
2
3
4
5

0 0
5 2
1 2 3 4
5

5 4
1 4
2
3
5

5 2
1 2 3 5
4

5 4
1
2
3
4 5

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

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

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