Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача А. Выбор оружия (зачеркнуто) дистрибутива

Задачу добавил: alef

Успешно сдано решений: 3

Директор фирмы поручил N сотрудникам одного отдела изучить M дистрибутивов Linux, а после этого устроить конференцию и, обсудив дистрибутивы, выбрать тот самый, единственный, который и будет установлен на всех компьютерах.
Конференция состоялась, но к общему мнению на ней прийти не удалось. Все отстаивали те дистрибутивы, которые изучали, и не соглашались поддержать никакой другой дистрибутив. И тогда директор принял следующее решение.
Он поручил одному из своих заместителей составить график попарных встреч сотрудников этого отдела. Сотрудник может участвовать только в одной встрече в течение дня. Повторных встреч (между уже встречавшимися) быть не должно.
После такой встречи пара должна выбрать один дистрибутив, и на встречах, которые состоятся позже, каждый человек из этой пары считается поддерживающим этот дистрибутив. Конечно, на следующей встрече сотрудника могут вновь переубедить...
Чтобы процесс согласований не стал бесконечным, директор объявил, что на принятие решения он готов отвести не более X дней. Если к концу какого-то дня до дня X включительно окажется, что не менее D (D <= N) сотрудников поддерживают некоторый дистрибутив, то он и будет выбран. Если же окажется, что одновременно не менее D сотрудников поддерживают еще и какой-то другой дистрибутив, выбран будет тот, который поддержит его заместитель. Заместитель директора поддержит при возможности симпатичный ему дистрибутив, но если придется выбирать из других дистрибутивов, поддержит тот дистрибутив, у которого меньше порядковый номер.
Надо сказать, что у заместителя есть собственные предпочтения. И он бы хотел, чтобы был выбран симпатичный ему дистрибутив. Поскольку он давно и хорошо знает сотрудников отдела, ему известно, кто кого переубедит при встрече в паре. Он составил график встреч и хотел бы проверить, получится ли согласно этому графику остановить выбор на симпатичном ему дистрибутиве. Ваша задача — по заданному графику определить, какой дистрибутив будет выбран до истечения X дней.

Формат входного файла input.txt
Первая строка — целые числа X (1 <= X <= 100, количество дней, отведенных директором на принятие решения), N (2 <= N <= 100, количество сотрудников), M (1 <= M <= N, количество дистрибутивов), D (1 <= D <= N) – минимальное количество сотрудников, которые должны поддержать дистрибутив, Z (1 <= Z <= M) – номер дистрибутива, симпатичного заместителю директора.
Каждая из следующих N строк содержит целое число L (1 <= L <= M) – номер дистрибутива, который изучал сотрудник #J, и через пробел — строку из N символов «+», «-» и 0. Ноль (0) в строке только один, он стоит на позиции #J (сотрудник не может переубедить сам себя). Плюс на месте I означает, что сотрудник #J переубедит сотрудника #I, минус — что сотрудник #J будет переубежден сотрудником #I.
Следующие N строк содержат график встреч сотрудников. На пересечении строки #J и столбца #I стоит номер дня, в который состоится встреча между ними, или ноль, если встреча в графике не запланирована. На главной диагонали находятся нули.
Гарантируется, что входные данные корректны.

Формат выходного файла output.txt
Первая строка — целое число K — количество дней, спустя которые согласно графику будет принято решение и через пробел — номер выбранного дистрибутива. Если решение достигнуто быть не может, выведите в первой строке No solution

Пример входного файла
5 3 3 3 1
1 0++
2 -0+
3 --0
0 2 3
2 0 4
3 4 0


Пример выходного файла
3 1

Сдать задачу

Задать вопрос жюри по этой задаче