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

Автор:В. Степанец, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

013610
24711
5812
913
14

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

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

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

N = 1

C ≤ 106

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

Входной файла содержит число N, за которым следуют N целых чисел Ci — номера мест.

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

Выходной файл должен содержать N пар чисел xi yi — координаты мест, соответствующие номерам во входном файле.

Ограничения

1 ≤ N ≤ 105

0 ≤ Ci ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
1 0
2
2
20101204
226
6106 234
4 16

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

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

N ≤ 1000

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

Во входном файле находятся целые числа N P a1 b1 a2 b2.

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

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

Ограничения

1 ≤ N, P ≤ 109

1 ≤ a1 ≤ b1 < a2 ≤ b2 ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 50 2 4 7 10
8 2
2
10 200 2 4 7 10
0 0

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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

P = 2

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

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

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

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

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

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

Ограничения

1 ≤ P, D ≤ 200

1 ≤ B ≤ 105

0 ≤ Ri, Ti ≤ B

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 4
0 1  0 2  1 0  2 0
0 2  0 1  1 0  2 0
1 1
1 1
2
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. Камень, ножницы, бумага и другие

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Однажды Глеб и Вася захотели обобщить игру "камень, ножницы, бумага". Теперь в игре задействовано 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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
kamen
nozhnitsy
bumaga
3
kamen
nozhnitsy
nozhnitsy
bumaga
bumaga
kamen
2
bumaga
nozhnitsy
kamen
kamen
2 0

0.058s 0.005s 13