Задача A. Принтер ≡

Условие

Принтер печатает 2 страницы на листе. Сколько нужно листов, чтобы напечатать N страниц?

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

Входной файл содержит целое число N — количество страниц.

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

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

Ограничения

1 ≤ N ≤ 1000

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

1

1

2

1

4

2

9

5

Задача B. Дерево Штерна-Броко ≡

Условие

Один из способов построения множества всех неотрицательных несократимых дробей вида m/n называется деревом Штерна-Броко.

Начнем с дробей 0/1 и 1/0, а затем будем повторять следующую операцию: вставить дробь (m + m')/(n + n') между двумя соседними дробями m/n и m'/n'.

Например первый шаг дает одну новую дробь между 0/1 и 1/0: 0/1, 1/1, 1/0. Следующий шаг добавляет две дроби, получая 0/1, 1/2, 1/1, 2/1, 1/0. Весь процесс можно представить в виде бесконечного бинарного дерева (см. рисунок).

Воспользуемся символами L и R для обозначения левой и правой ветвей при продвижении от корня вниз к определенной дроби. Тогда строка символов L и R однозначно определяет местоположения дроби в дереве. Например, строка LRRL соответствует дроби 5/7.

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

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

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

Выходной файл должен содержать строку, являющаяся представлением дроби в дереве Штерна-Броко.

Ограничения

1 ≤ N, M ≤ 10⁵; N ≠ M

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

5 7

LRRL

Задача C. БуКвест ≡

Условие

Юный любитель RPG Вася начал играть в новую компьютерную игру БуКвест. Игровой мир представляет собой прямоугольное поле размером W клеток в ширину и H в высоту. Каждая клетка либо пуста, либо занята стенкой, либо содержит главное сокровище, либо содержит монстра уровня k.

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

Попав в клетку с монстром, Вася вступает с ним в бой. Вася — довольно опытный игрок, и поэтому в конце концов побеждает любого монстра. Однако, на бой с монстром k-го уровня Васе требуется k минут. С другой стороны, в качестве трофея за победу над монстром k-го уровня Вася получает мощное оружие, которое позволяет мгновенно убивать любого монстра уровнем k или ниже, хотя и не помогает сократить время боя против более высокоуровневых монстров.

В первом примере Васе необходимо победить монстра A за одну минуту, затем монстра B за 2 минуты. Во втором примере Вася мог бы победить сначала A, потом B, потом C, затратив 1 + 2 + 3 = 6 минут, но быстрее победить монстра D за 4 минуты, и с полученным за него оружием без дополнительных затрат времени пройти монстров A, B и C.

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

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Решение будет полностью проверяться сразу после отправки, и участникам будут видны набранные за данную задачу баллы.

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

Первая строка входного файла содержит целое число N — количество тестов в данном файле

Далее N идёт блоков с описанием тестов:

• Первая строка теста содержит два целых числа W H.
• Следующие H строк по W символов содержат описание лабиринта. Пустая клетка обозначаются символом '.' (ASCII 46). Клетка со стенкой — символом '#' (ASCII 44). Клетка с сокровищем — символом '*' (ASCII 42). Клетка с монстром — символом от 'A' (для монстра первого уровня) до 'Z' (для монстра 26-го уровня).
• Каждый тест заканчивается пустой строкой

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

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

Ограничения

1 ≤ W, H ≤ 50

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

2
6 5
.####.
...AB.
..###.
...D#*
..###.

6 5
.####.
..ABC.
..###.
...D#*
..###.

3
4

Задача D. Восстановление сетки ≡

Условие

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

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

Назовём упорядоченной такую первоначальную последовательность участников, что в каждом матче сетки победителем оказывается первый участник. Например, первоначальная последовательность в приведённой справа сетке не соответствует этому условию — чтобы это исправить, нужно расположить участников в порядке: Life, MarineKing, TaeJa, Leenock, Mvp, Symbol, Rain, Hero.

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

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

N ≤ 10;

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

Входной файла содержит целое число N, за которым следуют 2^N − 1 пар чисел W_i L_i, означающих, что участник с номером W_i победил участника с номером L_i. Участники пронумерованы от 1 до 2^N.

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

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

Ограничения

1 ≤ N ≤ 20

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

3
1 2  3 1  7 3
7 6  6 5  7 8  3 4

7 8 6 5 3 4 1 2 

Задача E. Эффективное чтение ≡

Условие

С тех пор как Петя поступил на филфак, его жизнь круто изменилась. Оказалось, что нужно много читать для того, чтобы успевать по всем предметам. Петя читает книги только из университетской библиотеки. Поскольку Петя — не единственный студент в университете, он не может взять все нужные ему книги в начале семестра и сдать в конце. Для каждой книги определена дата, в которую Петя должен её взять и дата, в которую Петя должен её вернуть.

Более формально, занумеруем дни учебного семестра начиная с 1. Пете для учебы необходимо N книг. Занумеруем их числами от 1 до N. Для книги с номером i известны три числа:

• L_i — номер дня, в который книгу следует взять в библиотеке;
• R_i — номер дня, в который книгу следует отдать;
• p_i — количество страниц в книге.

Будем считать, что Петя приходит в библиотеку утром, забирая и отдавая необходимые книги. Таким образом, взяв книгу в день с номером L_i, он может в тот же день начать её читать. Вместе с этим, если книгу необходимо отдать в день с номером R_i, то Петя должен успеть дочитать её в день с номером R_i−1.

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

В приведённом примере имеется 2 книги и 3 дня для чтения (в день номер 4 Петя приходит в библиотеку утром). В первый день Петя берёт в библиотеке книгу с номером 1 и прочитывает, например, 30 страниц из неё. Во второй день Петя берёт книгу с номером 2. Поскольку эту книгу необходимо отдать в следующий день, все её 50 страниц следует прочесть в день с номером 2. На третий день Петя относит книгу 2 в библиотеку и дочитывает оставшиеся 30 страниц первой книги. Таким образом, Петя может прочесть обе книги, читая не более 50 страниц в день. С другой стороны, ответ не может быть меньше 50, поскольку вторую книгу нужно прочесть за один день.

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

N = 1;

N ≤ 10³;

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

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

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

Выходной файл должен содержать единственное целое число P.

Ограничения

1 ≤ N ≤ 10⁵;

1 ≤ L_i < R_i ≤ 10⁵;

1 ≤ p_i ≤ 10⁵;

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

2
1 4 60
2 3 50

50