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

SP

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

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

M гостей города S планируют совершить теперь поездку в город P. Они хотят распределить между собой обязанности
 - кто-то занимается приобретением билетов на поезд, кто-то - планированием экскурсионной программы...
Однако по поводу выбора гостиницы у них случились бурные обсуждения. Оказалось, что для кого-то принципиально
наличие в номере кондиционера, другой хотел бы, чтобы в номере непременно был интернет, третий настаивает,
что все это неважно, главное, чтобы гостиница располагалась в центре города. В результате каждый составил список, в котором указал важные (с его точки зрения) характеристики гостиницы. Также им удалось получить полный список гостиниц города P, в котором указано наличие / отсутствие данной
услуги / характеристики. Гарантируется, что все характеристики, указанные гостями города, присутствуют
в полном списке. Назовем гостиницу подходящей для данного гостя города, если все пункты из его списка являются характеристиками
гостиницы. Ваша задача - определить, найдется ли подходящая для всех гостей города гостиница. Если таковой не обнаружится,
то найдите гостиницу, которая удовлетворяет максимальному количеству требований. Формат входного файла input.txt Первая строка - целые числа M, N, U, где 1 <= M <= 100 - количество гостей города S, 1 <= N <= 200000 - количество гостиниц в списке 1 <= U <= 20 - количество характеристик гостиницы Каждая из следующих M строк содержит не более U чисел из диапазона 1..U через пробел - номера характеристик,
существенные для очередного гостя, за которыми следует 0. Каждая из следующих N строк содержит строку из U знаков + и - (без пробелов), показывающих наличие или
отсутствие той или иной характеристики у гостиницы. Знак + на позиции #j показывает наличие характеристики,
знак - (минус) - отсутствие. Гарантируется, что входной файл не превосходит 4Мб. Формат выходного файла output.txt Если удается найти гостиницу, которая подходит для всех гостей города, то в первой строке выходного файла
должно быть слово YES, а во второй - номер гостиницы, подходящей для всех гостей города (если таких несколько,
выведите любую). Если же такой гостиницы нет, то в первой строке выходного файла должно быть слово NO, а во второй - номер
гостиницы, в которой наличествует максимально возможное количество характеристик, которые были указаны
гостями города (если таких несколько, выведите любую). Пример входного файла - 1 3 6 5 5 2 1 0 2 3 0 3 5 1 0 ---++ +-+-+ +++-- +-++- +++-+ +++-+ Пример выходного файла - 1 YES 6 Пример входного файла - 2 3 6 5 5 2 1 0 2 3 0 3 5 1 0 ---++ +-+-+ +++-- +-++- ++--+ +++-- Пример выходного файла - 2 NO 5

Сдать задачу

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