Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Жюри чемпионата по скоростному вычислению булевых функций среди роботов готовит задания для участников.
Задание для роботов представляет собой таблицу из 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-й инструкции.
При этом программа является бесповторной, а именно все 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. Можно доказать, что при описанных в условии задачи ограничениях требуемые значения порогов всегда можно подобрать.
В первой строке входных данных заданы целые числа 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).
Выведите n целых чисел — искомые значения порогов z1,z2,…,zn (0≤zj≤m). Если подходящих вариантов несколько, выведите любой из них.
1≤n≤3⋅105, 1≤m≤3⋅105, n⋅m≤3⋅105, 0≤s≤m
1≤ap<n+p, 1≤bp<n+p, гарантируется, что в одном блоке все значения ap и bp попарно различны, opp=1 или opp=2
1≤ti≤109, 1≤ki≤1018
0≤xi,j≤m−1, в каждом столбце все числа различны, то есть если i≠k, то xi,j≠xk,j для всех j
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 10 | n≤2, m≤103 | первая ошибка | |
2 | 10 | n≤2, m≤105 | 1 | первая ошибка |
3 | 10 | n≤10, m≤2 | первая ошибка | |
4 | 5 | xi,j=i−1 | первая ошибка | |
5 | 5 | opp=1, только операции "и" | первая ошибка | |
6 | 20 | n≤100 | 1, 2, 3 | первая ошибка |
7 | 10 | БМЛП для всех строк одинаковые | первая ошибка | |
8 | 30 | нет | 1 — 7 | первая ошибка |
В примере в таблице три строки, каждой соответствует формула. Необходимо найти четыре порога так, чтобы ровно две формулы возвращали 1, а оставшаяся — 0.
Рассмотрим, как будет вычисляться массив val для первой строки.
Первые четыре значения вычисляются на основе чисел в этой строке и порогов:
Далее выполняем линейную программу для первой строки:
Таким образом значение булевой функции для первой строки равно 0. Кстати, если эту функцию записать формулой, то получится:
(((x1,1<z1) and (x1,2<z2)) or ((x1,3<z3) and (x1,4<z4))).
Аналогично, булева функция для второй строки равна:
((((x2,1<z1) or (x2,2<z2)) and (x2,3<z3)) or (x2,4<z4)),
а для третьей строки:
(((x3,1<z1) and (x3,4<z4)) or ((x3,2<z2) and (x3,3<z3))).
При подстановке порогов z1=0, z2=1, z3=2, z4=3 получим следующие выражения.
Вторая строка:
((((2<0) or (2<1)) and (1<2)) or (0<3))=(((0 or 1) and 1) or 1)=(0 or 1)=1,
Третья строка:
(((1<0) and (1<3)) or ((0<1) and (0<2)))=((0 and 0) or (1 and 1))=(0 or 1)=1.
Заметим, что это не единственный подходящий набор порогов, также подойдут, например, значения z1=0, z2=0, z3=3, z4=3.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|