АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1436. Детские сады

Ограничение времени: 2 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

В городе имеется N детских садов. Для каждого сада известно количество свободных мест для набора новых детей в младшие группы.

Для приёма заявок от родителей была создана комиссия. Всего в комиссию поступило M заявок. В каждой заявке родители указали список детских садов, которые для них по какой-то причине предпочтительны (например, расположены рядом с домом либо местом работы родителей).

Обработка заявок проводится в порядке, в котором они поступили. Первая заявка гарантированно выполняется. Вторая заявка выполняется в том случае, если при этом возможно также выполнить и первую (возможно, выбрав для неё другой садик). Каждая следующая заявка обрабатывается аналогично то есть i-я заявка выполняется в том случае, если при этом по-прежнему можно выполнить все заявки, признанные выполнимыми на предыдущих шагах.

Определите, какие заявки получится выполнить, и укажите подходящий вариант распределения заявок по детским садам.

Примечание. Вероятно, невыполненные заявки комиссия потом всё же распределит по оставшимся местам, но уже без учёта предпочтений. Впрочем, к решению данной задачи это совершенно не относится.

 

Входные данные. Первая строка входных данных содержит два разделенных пробелом целых числа N и M, где N — количество детских садов в городе, M — количество поданных заявок (1 ≤ N ≤ 100; 1 ≤ M ≤ 1000).

Вторая строка содержит N разделённых пробелом целых чисел — количество мест в каждом садике.

Каждая из следующих M строк содержит описание очередной заявки. Описание заявки представляет собой несколько разделенных пробелом целых чисел — вначале идёт количество садиков Qi, а затем Qi чисел — номера садиков (в диапазоне от 1 до N).

 

Выходные данные. В первую строку выходных данных выведите целое число K —количество заявок, которые получилось удовлетворить. В каждой из следующих K строк выведите два разделенных пробелом целых числа номер очередной заявки  и номер назначенного ей детского сада.

Номера заявок в выводе должны идти по возрастанию. Если возможны несколько вариантов назначения найденных заявок по детским садам, то выведите любой.

 

Примеры

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

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

2 5

2 1

1 2

2 1 2

1 2

1 1

1 2

3

1 2

2 1

4 1

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XVIII межвузовская олимпиада 2015 /
1435. I - Анализ ДНК 1436. 1437. Y - Число e
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Дополнительные задачи /
1435. 09 - Анализ ДНК 1436. 1437. 11 - Число e 1633. 12 - Пишите письма 1634. 13 - Паскаль 2.0
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.