#1679

Министры его величества

Темы: [Простые задачи на перебор] [Разные комбинаторные структуры]

Его Величество Король Бубей Второй пожелал назначить новый кабинет министров (информация о том, что случилось со старым – строго засекречена). К составу кабинета министров есть следующие пожелания:

1) министров должно быть как можно меньше (так ими легче управлять, да и на зарплате можно сэкономить);

2) для каждой области (строительство, финансы и т.д.) должен быть хотя бы один министр, который в ней разбирается.

На рассмотрение Его Величества поступило \(N\) кандидатур. Определите, сколько и каких людей должны получить министерские посты, с учетом пожеланий.

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

сначала вводится число \(N\) (натуральное, не превышает 10) – количество кандидатов в списке, затем вводится число \(K\) (натуральное, не превышает 20 – общее количество областей, в которых министры должны разбираться). Затем идет \(N\) строк следующего формата: в начале строки вводится число \(P_i\) (натуральное, не превышает \(K\)) – количество областей, в которых разбирается \(i\)-й кандидат, потом вводятся номера этих областей (натуральные числа, не превышают \(K\)).

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

сначала выведите количество министров, которое планируется назначить, исходя из требований задачи, затем перечислите номера подходящих кандидатов, в порядке возрастания. Если решений несколько, то выберите из них то, в котором участвуют кандидаты, идущие раньше по списку. Гарантируется, что решение существует (то есть можно получить такой набор кандидатов, что в каждой области будет разбираться хотя бы один из них)

Примеры

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

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

1
1

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

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

2
3 4

#1680

Королевское путешествие

Темы: [Гамильтонов цикл] [Простые задачи на перебор]

Его Величество Король Бубей Второй пожелал объехать свои владения. При этом к маршруту есть следующие пожелания:

1) маршрут должен занимать наименьшее возможное время (королевское время – вещь очень ценная и его надо беречь);

2) маршрут должен включать все населенные пункты ровно по одному разу (если король пропустит какой-то населенный пункт, то его жители будут возмущены королевским невниманием и перестанут платить налоги; если король посетит какой-то населенный пункт больше одного раза, то жители остальных населенных пунктов также возмутятся)

3) маршрут должен начинаться и заканчиваться в столице государства (объехав свои владения, король должен сразу приступить к делам). Столица входит в маршрут ровно 2 раза: как пункт отбытия и как пункт назначения, она не может являться промежуточным населенным пунктом маршрута.

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

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

сначала вводится число \(N\) (натуральное, не превышает 10) – количество населенных пунктов королевства. Затем следует \(N\) строк по \(N\) чисел в каждой – время пути между населенными пунктами (время – целое неотрицательное число, не превышает 500; если время = 0, то это означает, что пути между какими-то населенными пунктами нет). Населенный пункт №1 является столицей государства.

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

выведите наименьшее суммарное время, которое Его Величество потратит на объезд своих владений, или число -1, если построить маршрут с заданными свойствами невозможно.

Примеры

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

1
0

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

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

2
0 1
1 0

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

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

2
0 85 
85 0

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

#1681

Статуи на мосту

Темы: [Простые задачи на перебор]

В столице королевства Бубея Второго построен новый мост, который решено украсить статуями работы лучших мастеров. Для украшения моста были выбраны N мастеров, каждый из которых создал по одной статуе. К сожалению, мастера сделали статуи разного веса, поэтому если эти произведения искусства распределить между левой и правой сторонами моста произвольным образом, то возникает риск, что одна из сторон «перетянет» и мост опрокинется. С другой стороны, проект уже утвержден Его Величеством и необходимо обязательно использовать все статуи. Определите оптимальное распределение статуй между левой и правой сторонами моста.

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

сначала вводится число \(N\) (натуральное, не превышает 12), затем вводятся \(N\) чисел (натуральные, не превышают 1000) – веса статуй.

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

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

Примеры

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

3
1 2 3

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

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

5
1 2 3 3 10

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

#1682

Во дворце заговор

Темы: [Перебор]

Секретная Служба Его Величества Бубея Второго разоблачила заговор среди придворных. Теперь необходимо уволить всех явных заговорщиков и подозрительных придворных. Придворный считается «явным заговорщиком» - если существуют явные доказательства его причастности к заговору. Придворный считается «подозрительным», если он был назначен на свою должность кем-то из «явных заговорщиков» или других «подозрительных» придворных. Определите, сколько людей сохранит свои должности при дворе Его Величества.

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

сначала вводится число \(N\) (натуральное, не превышает 1000) – общее количество придворных. Затем вводится \(N\) чисел \(a_i\) (целые, неотрицательное, не превышают \(N\)) – номер придворного, благодаря которому придворный \(i\) получил свою должность. Если \(a_i\)=0, то это означает, что этот придворный назначен на свою должность самим Королем. Затем вводится число \(K\) (натуральное, не превышает \(N\)) – общее количество явных заговорщиков. Затем вводится \(K\) чисел (натуральные, не превышают \(N\)) – номера заговорщиков. Гарантируется, что данные корректны (например, что придворный не мог назначить на должность сам себя, или, что двое придворных не могли назначить друг друга одновременно).

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

выведите единственное число – количество придворных, которые сохранят свои должности после окончания расследования.

Примеры

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

3 0 0 1
1 3

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

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

5 0 0 1 1 2
1 1

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

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

4 0 1 2 3
1 2

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

#1683

Распределение заказов

Темы: [Паросочетания] [Потоки]

В компанию по обслуживанию компьютеров поступило \(N\) заявок от клиентов. В компании есть \(S\) сотрудников разной квалификации. Руководитель компании знает, какие из заявок каждый сотрудник способен выполнить (возможно, каждый сотрудник может выполнить несколько заявок, также верно, что одну и ту же заявку способны выполнить несколько сотрудников). Каждый сотрудник в какой-то момент времени может выполнять не более одной заявки. Для выполнения каждой заявки достаточно ровно одного сотрудника.

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

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

Cначала вводятся числа \(N\) и \(S\) (натуральные, не превышают 100), затем вводится \(S\) строк по \(N\) чисел в каждой – сведения о квалификации сотрудников. Если в \(j\)-й позиции \(i\)-й строки находится 0, то \(i\)-й сотрудник не способен выполнить данную заявку, если 1 – то способен.

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

Выведите единственное число – максимальное количество заявок, которое можно начать выполнять.

Примеры

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

2 2
1 1 
1 1

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

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

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