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

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

HotLog


 

Олимпиада для роботов

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

Жюри чемпионата по скоростному вычислению булевых функций среди роботов готовит задания для участников.

Задание для роботов представляет собой таблицу из m строк и n столбцов, каждая ячейка которой содержит целое число. Обозначим число в i-й строке, j-м столбце таблицы как xi,j . В каждом столбце значения в ячейках таблицы образую перестановку чисел от 0 до m − 1. Иначе говоря, числа в каждом столбце различны: если i ≠ k, то xi,j ≠ xk,j для всех j, и выполнено условие 0 ≤ xi,j < m.

Для каждого столбца таблицы задаётся значение порога — целое неотрицательное число zj от 0 до m. В качестве аргументов булевых функций, которые будут вычислять участники олимпиады, используются значения логических выражений xi,j < zj . Значение такого логического выражения равно 1, если неравенство выполнено, иначе оно равно 0.

В процессе соревнования участники вычисляют значения m булевых функций — по одному для каждой строки. Каждая булева функция задаётся в виде бесповторной монотонной линейной программы (БМЛП).

Рассмотрим БМЛП для i-й строки таблицы. Она представляет собой последовательность из n − 1 инструкции, пронумерованных от 1 до n − 1, p-я инструкция задаётся тремя числами: ap, bp и opp. Число opp принимает два возможных значения: 1 для операции and — логическое «и», 2 для операции or — логическое «или». Числа ap и bp являются номерами аргументов p-й инструкции, выполнены неравенства 1 ≤ ap, bp < n + p.

Рассмотрим массив val[1..2n − 1], каждое из значений которого равно 0 или 1. Проинициализируем значения val[1]..val[n] с использованием порогов, val[j] = 1, если xi,j < zj , иначе val[j] = 0. Значение val[n + p] вычисляется с использованием p-й инструкции.

  • Если opp = 1, то val[n + p] = (val[ap] and val[bp]), то есть значение val[n + p] равно 1 если и только если каждое из значений val[ap] и val[bp] равно 1.
  • Если opp = 2, то val[n + p] = (val[ap] or val[bpp]), то есть значение val[n + p] равно 1 если и только если хотя бы одно из значений val[ap] и val[bp] равно 1.

При этом программа является бесповторной, а именно все 2n − 2 значений ap и bp для p от 1 до n − 1 различны. Иначе говоря, ap ≠ bp, а если p ≠ q, то ap ≠ aq, ap ≠ bq, bp ≠ aq и bp ≠ bq. Результатом исполнения программы является значение val[2n − 1]. Жюри олимпиады подготовило таблицу xi,j , выбрало булевы функции для каждой строки и записало их в виде БМЛП. Теперь осталось выбрать значение порога для каждого столбца, чтобы получить задание для олимпиады. Жюри считает задание сбалансированным, если ровно s из m программ для строк таблицы возвращают единицу, а остальные m − s возвращают ноль. Ваша задача — помочь жюри найти подходящие значения порогов.

Требуется написать программу, которая по заданным значениям в ячейках таблицы и БМЛП для строк таблицы определяет такие значения порогов zj, чтобы значение ровно s из m заданных функций было равно 1. Можно доказать, что при описанных в условии задачи ограничениях требуемые значения порогов всегда можно подобрать.

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

В первой строке входного файла INPUT.TXT заданы целые числа n, m и s (1 ≤ n ≤ 3×105, 1 ≤ m ≤ 3×105, n×m ≤ 3×105, 0 ≤ s ≤ m).

Далее следует m блоков по n−1 строке в каждом, каждый блок задает бесповторную монотонную линейную программу для одной строки таблицы. В каждом блоке p-я строка содержит 3 целых числа: ap, bp и opp (1 ≤ ap < n + p, 1 ≤ bp < n + p, гарантируется, что в одном блоке все значения ap и bp попарно различны, opp = 1 или opp = 2).

Последние m строк задают таблицу, i-я строка содержит n целых чисел, j-е из которых равно xi,j (0 ≤ xi,j ≤ m−1, в каждом столбце все числа различны, то есть если i ≠ k, то xi,j ≠ xk,j для всех j).

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

В выходной файл OUTPUT.TXT выведите n целых чисел — искомые значения порогов z1, z2, ... , zn (0 ≤ zj ≤ m). Если подходящих вариантов несколько, выведите любой из них.

Пример

INPUT.TXTOUTPUT.TXT
14 3 2
1 2 1
3 4 1
5 6 2
1 2 2
3 5 1
4 6 2
1 4 1
2 3 1
5 6 2
0 1 2 2
2 2 1 0
1 0 0 1
0 1 2 3

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Разность квадратов
 B. Превышение скорости
 C. Борьба с рутиной
 D. Олимпиада для роботов
 E. Максимальное произведение
 F. Планировка участка
 G. Банкомат
 H. Плакаты

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru



казино пин ап играть за деньги