Задача A. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход текущее время (часы и минуты) и вычисляющую, сколько времени осталось до Нового года.

Число секунд в текущем времени принять равным 0.

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

Входной файл содержит текущее время — часы и минуты.

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

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

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

12 0

12 0

23 59

0 1

22 25

1 35

Задача B. Во саду ли, в огороде ≡

Условие

Во саду ли, в огороде бегала собачка.

Огород, по которому бегает собачка, представляет собой квадрат размером N × N метров.

Разумеется, это не первая среди собак, бегавших по этому огороду, и каждая из них хотя бы раз закапывала в нем косточки. Поэтому в разных местах огорода присутствует вкусный запах разной интенсивности. Огород разделён на N² квадратиков, в квадратике с координатами (i, j) интенсивность запаха равняется a_i,j.

Квадратик с координатами (1, 1) расположен в левом верхнем углу огорода. Первая координата откладывается по горизонтали, вторая — по вертикали.

Вначале собака находится в квадратике с координатами (i₀, j₀). На каждом шаге собака перемещается в соседний (слева, сверху, справа или снизу) квадратик, в котором запах самый сильный и сильнее, чем в квадратике, в котором находится собака. Если такого квадратика не оказалось, то собака останавливается.

Напишите программу, позволяющую найти траекторию собаки.

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

Входной файл содержит целые числа N i₀ j₀.

Далее следуют N² целых чисел a_i,j.

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

Выходной файл должен содержать пары целых чисел — траекторию собаки.

Входные данные таковы, что траектория собаки определена однозначно.

Ограничения

2 ≤ N ≤ 100

0 ≤ a_i,j ≤ 100

1 ≤ i₀, j₀ ≤ N

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

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

2 2
2 3
3 3

Задача C. Барабанная почта ≡

Условие

Когда-то давно члены одного африканского племени, жившие в разных деревнях, использовали для передачи информации звуковую почту. Чтобы передать сообщение, отправитель бил в барабан в промежутки времени a_i ≤ t ≤ b_i, а получатель слушал и рассказывал жителям своей деревни. Сила звука зависит от погоды — например, во время дождя и грозы звук барабана практически не слышен.

Однажды у племени поменялся вождь, и необходимо было оповестить об этом всех жителей племени. Но, как назло, погода в этот день была очень неустойчивая — то дождь, то туман, то ветер, то солнце. Поэтому звуки барабана можно было слышать только в промежутки времени c_i ≤ t ≤ d_i.

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

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

Входной файл содержит целое число N — количество промежутков [a_i, b_i]. Далее следуют N пар целых чисел a_i b_i. Далее во входном файле содержится целое число M — количество промежутков [c_i, d_i], — за которым следуют M пар целых чисел c_i d_i.

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

Выходной файл должен содержать целое число K — количество промежутков [e_i, f_i] — и K пар целых чисел e_i f_i.

Должны выполняться неравенства: f_i < e_i+1, i = 1, …, K−1.

Промежутки нулевой длины выводить не нужно.

Ограничения

1 ≤ N, M ≤ 1000, 0 ≤ a_i < b_i ≤ 10000, 0 ≤ c_i < d_i ≤ 10000

b_i < a_i+1, i = 1, …, N−1

d_i < c_i+1, i = 1, …, M−1

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

3
0 3
5 9
12 14
3
1 4
5 11
13 15

3
1 3
5 9
13 14

2
0 4
7 10
2
5 7
10 13

0

Задача D. Прямоугольный осадкомерный стакан ≡

Условие

Сотрудники Научно-исследовательского института алгебры, геометрии и анализа (НИИ АГА) по заказу метеорологов разработали новый вид осадкомерных стаканов с основанием в виде прямого угла.

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

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

Сотрудникам НИИ АГА нужна программа, принимающая на вход угол наклона стакана α и уровень воды в стакане h и вычисляющая площадь части прямого угла, занятой водой.

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

Входной файл содержит вещественные числа α h.

Угол задан в градусах. Уровень воды задан в миллиметрах.

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

Требуется вывести вещественное число — площадь части прямого угла, занятой водой, в мм².

Ответ вывести с точностью не менее 5-ти знаков после запятой.

Ограничения

1 ≤ α ≤ 89

1 ≤ h ≤ 1000

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

45.0 1.0

1.0

Задача E. Шушанчики и музыкальное просвещение ≡

Условие

Однажды шушанчики решили заняться изучением музыки. Для начала они познакомились с понятием длительности ноты — условной продолжительности звука, выраженной в относительных единицах.

Длительность ноты записывается как дробь, числитель которой — число в диапазоне от 1 до 128, а знаменатель — одно из чисел 1, 2, 4, 8, 16, 32.

Также используется модификатор длительности — символ "точка". Добавление первой точки увеличивает длительность ноты на 1/2 её исходной длительности, добавление второй точки — ещё на 1/4 её исходной длительности, и так далее. Например, длительность ноты с тремя точками равна 15/8 = 1 + 1/2 + 1/4 + 1/8 длительности основной ноты.

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

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

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

В первой строке входного файла содержится число N — количество нот в такте. В следующих N строках содержится описание нот — сначала дробь, означающая длительность ноты, затем — ноль или более точек. Числитель и знаменатель дроби разделяются символом "/" (ASCII 47). Строки с описанием нот не содержат пробелов.

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

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

Ограничения

1 ≤ N ≤ 1000

Количество точек после каждой ноты не превосходит 5.

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

1
2/4

1 2

2
1/8
1/4

3 8

1
2/4.

3 4

Задача F. Честная очередь ≡

Условие

В одном из травмпунктов города Владивостока прием пациентов осуществляется по следующим правилам:

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

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

Если к моменту, когда пациент, занявший обе очереди, выходит из рентгеновского кабинета, его очередь на вторичный осмотр уже прошла, то он становится в конец этой очереди. Если пациент выходит из рентгеновского кабинета в ту же минуту, что начинается его очередь на вторичный осмотр, то считается, что он её пропустил (см. пример 2).

По заданной последовательности появления пациентов выясните время, которое понадобится каждому из пациентов, чтобы посетить все назначенные ему кабинеты. При этом следует считать, что для любого пациента длительность приема в кабинете рентгенографии равна P минут, длительность приема в кабинете второго осмотра равна Q минут, а время первичного приёма равно нулю.

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

Входной файл содержит числа N P Q, за которыми следуют N наборов чисел.

В каждом наборе первое число означает время прихода пациента t_i, измеренное в минутах с начала приема. Далее идет число, обозначающее, в какие кабинеты требуется попасть i-му пациенту — 1, если сперва в кабинет рентгенографии и 2, если сразу в кабинет вторичного приема.

Для пациентов, которым требуется сделать снимок, далее идет число 1 или 2, обозначающее, займет ли пациент он место в одной очереди или в двух.

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ P, Q ≤ 15, 0 ≤ t_i ≤ 1000, t_i < t_i+1

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

2 5 10
0 1 1
5 1 1

15 20

2 5 5
0 1 1
5 2  

15 5

3 5 10 0 1 2 2 2 3 2

32 10 19

Задача G. Волшебные горшочки Бабы Яги ≡

Условие

В некотором царстве, некотором государстве жила-была Баба Яга. Однажды исполнилось Бабе Яге 500 лет, и она решила отпраздновать свой юбилей и позвала гостей: Кощея Бессмертного, Кота Баюна, Лешего, Водяного, Кикимору и других.

Было у Бабы Яги N волшебных горшочков. Все горшочки абсолютно одинаковы. Каждый горшочек готовит одно из M блюд, причём каждое из M блюд может быть приготовлено с одинаковой вероятностью (все блюда равновероятны).

Баба Яга любит разнообразие блюд на праздничном столе, поэтому она хочет, чтобы во всех горшочках блюда были разные. С какой вероятностью это случится?

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

Входной файл содержит целые числа N M.

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

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

Ответ необходимо вывести с точностью не менее семи знаков после запятой.

Ограничения

1 ≤ N ≤ 9

1 ≤ M ≤ 9

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

2 2

0.5

2 3

0.6666666667

1 4

1

Задача H. Упрощение плана ≡

Условие

Стройка, приуроченная к саммиту АТЭС — очень большая задача. Как и все большие задачи, её разбили на подзадачи. Между подзадачами есть зависимости: есть такие пары подзадач (u, v), что к подзадаче v нельзя приступать, не завершив предварительно подзадачу u.

При этом некоторые зависимости могут присутствовать и неявно. Например, если имеются зависимости (u, v) и (v, w), то подзадачу w нельзя выполнять, пока не будет выполнена подзадача u.

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

Множество зависимостей можно удалить, если после его удаления все неявные зависимости сохранятся.

Так, в примере 1 могут быть удалены зависимости (1, 3) и (2, 4). В том же примере зависимость (2, 3) удалена быть не может, поскольку остальные четыре не создают её неявно.

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

Во первой строке входного файла находятся числа N M — количество подзадач и количество зависимостей. Далее следует M пар чисел, обозначающих зависимости. Пара u v означает, что подзадача v не может быть выполнена, пока не будет выполнена u.

Подзадачи пронумерованы первыми N натуральными числами.

Гарантируется, что ни одна зависимость не упомянута дважды.

Гарантируется, что никакая задача не зависит от самой себя и зависимости не образуют циклов.

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

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

Ограничения

1 ≤ N ≤ 50

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

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

2
2 3

Задача I. Благотворительность Марфы Геннадьевны ≡

Условие

Однажды Марфа Геннадьевна выиграла в лотерею большую сумму денег и решила потратить часть выигрыша на благотворительность.

Чтобы определить, сколько денег отдать на благотворительность, Марфа Геннадьевна придумала игру. Она записала N чисел a₁, a₂, ..., a_N по кругу (по часовой стрелке).

Начинает Марфа Геннадьевна с числа a₁. Начальная сумма денег равняется a₁. Затем Марфа Геннадьевна кидает игральный кубик (на разных гранях кубика нарисовано 1, 2, 3, 4, 5 и 6 точек). Если на кубике выпало число x, то Марфа Геннадьевна отсчитывает x чисел по часовой стрелке. Например, если выпало число 3, то Марфа Геннадьевна перейдёт от числа a₁ к числу a₄. Число, к которому перешла Марфа Геннадьевна, прибавляется к сумме. Марфа Геннадьевна бросает кубик M раз и каждый раз прибавляет очередное число к сумме.

Марфе Геннадьевне интересно, какая наибольшая сумма денег может получиться при такой игре, поэтому ей нужна программа, вычисляющая наибольшую сумму.

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

Входной файл содержит целые числа N M, за которыми следуют N целых чисел a₁ a₂... a_N.

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

Требуется вывести в выходной файл целое число — максимальную сумму.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ 5000

0 ≤ a_i ≤ 1000

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

7 1
1 2 3 4 5 6 7

8

7 2
1 2 3 4 5 6 7

14

5 2
5 0 10 1 6

25