#3203

Вася и его друзья

Темы: [Динамическое программирование по профилю]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заочный этап, Задача I ]

В новой игре "Closed Loops 7" игрокам предлагается клетчатая таблица \(N\) на \(M\) клеток. Ход состоит в том, что очередной игрок рисует цикл - замкнутую линию без самопересечений, идущую только по сторонам клеток. Каждый цикл можно нарисовать только один раз за всю игру (при этом, конечно, не запрещается рисовать циклы, пересекающиеся с уже нарисованными). Игроки ходят по очереди. Выигрывает тот, кто рисует последний возможный цикл. К примеру, если \(N=2\), \(M=1\), то циклов всего три и игрок, делающий третий ход, выигрывает.

Вася позвал \(K-1\) друзей поиграть с ним. Чтобы произвести впечатление, он непременно хочет выиграть. Для этого ему нужно узнать, каким по счету игроком он должен быть, чтобы гарантированно одержать победу. Вася наслышан о ваших успехах в программировании, и за помощью он обратился именно к вам.

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

Даны три целых числа: \(N, M\) - размеры таблицы (\(1 \le N \le 100, 1 \le M \le 8\)) и \(K\) - количество игроков (\(1 < K \le 10^9\)).

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

Выведите одно число от 1 до \(K\) - каким по счету игроком должен быть Вася, чтобы выиграть.

Примечания

Тесты состоят из трёх групп. В этой задаче нет off-line групп.

Тесты 1 и 2, из условия, оцениваются в 0 баллов.
Тесты 3--15. \(N \cdot M \le 24\). Эта группа оценивается в 40 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 16--42. Полные ограничения, группа оценивается в 60 баллов. Баллы начисляются только при прохождении всех тестов группы.

Примеры

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

2 1 2

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

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

1 8 8064

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

#3204

Отрезки на прямой возвращаются

Темы: [Сканирующая прямая] [Список]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заочный этап, Задача J ]

На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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

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

Сначала вводится целое число \(N\) (\(1 \le N \le 100\,000\)). Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(-10^9 \le a_i < b_i \le 10^9\)).

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

Выведите \(N\) чисел. Число номер \(i\) должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \(i\), либо 0 - если такого не существует.

Если существует несколько решений, выведите любое.

Примечания

Тесты состоят из четырёх групп.

Тест 1, из условия, оценивается в 0 баллов.
Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.

Примеры

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

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

3 4 0 0

#3205

Отрезки на прямой возвращаются--2

Темы: [Сортировка событий] [Сканирующая прямая] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2010-2011, Заочный этап, Задача K ]

При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.

Проверяющей программе доступно три блока информации:

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

Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.

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

Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.

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

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

Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.

Примечания

Тесты состоят из четырёх групп.

Тест 1, из условия, оценивается в 0 баллов.
Тесты 2--11. В них \(N \le 100\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 12--27. В них \(N \le 10\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
Тесты 28--35. Полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.

Примеры

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

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

OK
WA
WA
OK