Задача A. Автостоянка на улице Кантора ≡

Условие

Автостоянка, находящаяся поблизости от улицы имени Г. Кантора, ограничена с севера и запада домами, а с востока и юга открыта в большое поле.

Чтобы упорядочить размещение автомобилей, владелец стоянки решил пронумеровать места на ней и выделить каждому клиенту номер и соответствующее место. Нумерацию решено производить так: месту в углу стоянки присвоен номер ноль, далее нумерация идёт по диагоналям в направлении с северо-востока на юго-запад.

Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).

Требуется написать программу, которая для каждого из N данных номеров мест определит их координаты.

Рекомендуется рассмотреть частичные решения

N = 1

C ≤ 10⁶

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ C_i ≤ 10⁹

Примеры тестов

1
1

1 0

2
20101204
226

6106 234
4 16

Задача B. Тонкий и толстый ≡

Условие

На финал чемпионата мира по программированию отправилось так много болельщиков (P человек), что для них пришлось организовать чартерные рейсы. Авиакомпания, доставляющая болельщиков, имеет в своем распоряжении N самолетов. По политическим соображениям, авиакомпания должна использовать для доставки пассажиров все имеющиеся самолёты.

Каждый самолет имеет две модификации. В модификации "Тонкий" самолет может поднять любое количество пассажиров в отрезке [a₁, b₁]. Перевозить меньше a₁ пассажиров экономически невыгодно, а больше b₁ пассажиров самолет просто не сможет поднять. В модификации "Толстый" самолет может поднять любое количество пассажиров в отрезке [a₂, b₂].

Требуется определить, можно ли распределить P болельщиков по N самолетам так, что все самолеты взлетят и их использование будет экономически выгодным. Каждый самолет может быть использован только в одном рейсе и в одной из модификаций.

Рекомендуется рассмотреть частичные решения

N ≤ 1000

Формат входного файла

Во входном файле находятся целые числа N P a₁ b₁ a₂ b₂.

Формат выходного файла

Если требуемая рассадка пассажиров существует, выведите два целых неотрицательных числа, дающие в сумме N: необходимое количество самолетов "тонкой" и "толстой" модификаций. Если существует несколько решений, выведите то, в котором количество самолетов "тонкой" модификации максимально. Если решения не существует, выведите два нуля через пробел.

Ограничения

1 ≤ N, P ≤ 10⁹

1 ≤ a₁ ≤ b₁ < a₂ ≤ b₂ ≤ 10⁹

Примеры тестов

10 50 2 4 7 10

8 2

10 200 2 4 7 10

0 0

Задача C. Современная библиотека ≡

Условие

Группа, состоящая P из юных программистов, поступила на первый курс университета. Занятия на первом курсе будут продолжаться в течение D дней. Помочь студентам в приобретении знаний может новая библиотека университета, в которой имеется B различных книг, посвящённых программированию. Из-за проблем с финансированием каждая книга имеется в единственном экземпляре.

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

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

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

Если несколько студентов приходят в библиотеку в один день, они обслуживаются в порядке списка, составленного при поступлении в университет.

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

По представленным планам самообучения требуется для каждого студента определить, сколько книг он прочтёт и будет ли отчислен.

Рекомендуется рассмотреть частичные решения

P = 2

Формат входного файла

Входной файл содержит два целых числа — P D, за которыми следуют P описаний планов самообучения.

Каждое описание содержит D пар целых чисел R_i, T_i, которые означают что в i-ый день студент хочет сдать книгу с номером R_i и получить книгу с номером T_i. Если студент не собирается брать или сдавать книгу в этот день, соответствующее число равно нулю.

Планы перечислены в порядке, соответствующем порядку обслуживания студентов.

Формат выходного файла

Выходной файл должен содержать P пар целых чисел Q_i M_i, где Q_i — количество книг, которые прочитает i-й студент, M_i равно единице, если i-ый студент будет отчислен, и нулю в противном случае.

Ограничения

1 ≤ P, D ≤ 200

1 ≤ B ≤ 10⁵

0 ≤ R_i, T_i ≤ B

Примеры тестов

2 4
0 1  0 2  1 0  2 0
0 2  0 1  1 0  2 0

1 1
1 1

3 4
0 1  0 3  1 0  3 0
0 2  2 3  3 5  5 0
0 3  0 0  3 4  4 0

2 0
3 0
2 0

Задача D. Камень, ножницы, бумага и другие ≡

Условие

Глеб и Вася, студенты Института математики и компьютерных наук ДВФУ, часто играют в игру "камень, ножницы, бумага", чтобы определить, кто пойдёт мыть тряпку для стирания с доски.

Правила этой игры таковы: участники произносят фразу "камень, ножницы, бумага раз, два, три", после чего каждый участник показывает рукой один из трёх предметов: камень, ножницы или бумагу. В игре считается, что камень ломает ножницы, ножницы режут бумагу, бумага накрывает камень. Если, например, Глеб выбрал бумагу, а Вася выбрал ножницы, то Вася побеждает, а если оба игрока выбрали камень, то объявляется ничья.

Однажды Глеб и Вася захотели обобщить игру "камень, ножницы, бумага". Теперь в игре задействовано N предметов. Задаётся список пар предметов. Считается, что если один игрок выбрал первый предмет из некоторой пары, а другой игрок — второй предмет из этой пары, то тот, кто выбрал первый предмет из пары, побеждает. Если игроки выбрали пару предметов, которая не встречается в списке пар, то объявляется ничья.

Напишите программу, принимающую на вход список предметов, список пар предметов и список игр и выводящую результаты игр.

Рекомендуется рассмотреть частичные решения

1 ≤ M, K ≤ 200

Формат входного файла

Первая строка входного файла содержит целое число N — количество предметов. Далее следуют N строк — названия предметов. Длина названия составляет от 1 до 20 символов. Названия состоят из маленьких латинских букв. Все названия различны.

Следующая строка содержит целое число M — длину списка пар предметов. Далее следуют 2 × M строк — пары предметов. В каждой из этих строк может содержаться только название предмета из списка предметов. Никакие два предмета не могут содержаться одновременно в двух парах.

Следующая строка содержит целое число K — количество игр. Далее следуют 2 × K строк. В каждой из этих строк может содержаться только название предмета из списка предметов.

Формат выходного файла

Выходной файл должен содержать K чисел. Для каждой игры должно быть выведено число 1, если выиграл первый игрок, число 2, если выиграл второй игрок, и число 0, если игроки сыграли вничью.

Ограничения

2 ≤ N ≤ 1000

1 ≤ M, K ≤ 20000

Примеры тестов

3
kamen
nozhnitsy
bumaga
3
kamen
nozhnitsy
nozhnitsy
bumaga
bumaga
kamen
2
bumaga
nozhnitsy
kamen
kamen

2 0