Задача A. Марфа Геннадьевна в кустах ≡

Условие

Марфа Геннадьевна считает, что её соседка по даче, Элеонора Агафьевна, слишком любопытна и постоянно подглядывает за Марфой Геннадьевной из окна. Граница участков Марфы Геннадьевны и Элеоноры Агафьевны представляет собой отрезок длиной L см.

Марфа Геннадьевна решила загородить соседке обзор, засадив границу кустами. У Марфы Геннадьевны имеются семена N видов кустов. Известно, что кусты i-го вида вырастают до ширины в a_i см. При этом для нормального развития кустам i-го вида необходимо, чтобы расстояние между краями соседних кустов, а также от края куста до края границы участков было не менее b_i см.

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

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

• N = 1;
• N = 2;

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

Входной файл содержит целые числа N L, за которыми следует N пар целых чисел a_i b_i — ширина куста и минимальное расстояние для i-го вида.

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

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

Ограничения

1 ≤ N ≤ 10³

2 ≤ L ≤ 10⁴

1 ≤ a_i, b_i ≤ 10⁴.

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

2 5
3 1
2 1

2

2 7
3 2
2 3

4

1 10
5 3

10

Задача B. Открытый подсчёт ≡

Условие

Юный робототехник Вася построил робота, который способен перемещаться по неограниченному клетчатому полю согласно заложенной в него программе. Робот занимает ровно одну клетку поля. Программа для робота состоит из последовательности команд, разделённых запятой. Каждая команда состоит из латинской буквы и натурального числа. Буква задаёт направление движения (U — на север, D — на юг, L — на запад, R — на восток), а число — количество клеток, на которое робот должен сдвинуться.

Требуется по данной программе определить количество различных клеток (считая начальную), которые посетит робот во время её выполнения. Например, при выполнении программы D3,U4 робот сдвинется на юг на 3 клетки, затем на север на 4. В сумме робот посетит 5 различных клеток (3 из них — по два раза каждую).

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

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

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

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

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

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

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

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

2
D100,L10
R1,L1,R1,L2

111
3

Задача C. Посекундная тарификация ≡

Условие

Телефонная компания ввела новый тарифный план "Посекундный". Согласно этому плану, каждый месяц абоненту предоставляется F бесплатных минут. При этом длительности звонков, использующих только бесплатные минуты, округляются вверх до целой минуты. Например, звонок продолжительностью 3 минуты 15 секунд использует 4 бесплатных минуты.

Когда бесплатные минуты исчерпаны (даже если это произошло в середине звонка), включается посекундная тарификация — 1 рубль в секунду.

История звонков абонента представляет собой список из N пар чисел m s, где m — число минут, s — число секунд. Напишите программу, которая по истории звонков абонента за месяц определяет, сколько рублей ему придётся заплатить.

В первом примере первый и второй звонок тратят по 1 бесплатной минуте, третий звонок тратит 4 бесплатных минуты. На последний звонок остаётся 4 бесплатных минуты. После их исчерпания абонент оплачивает 12 секунд.

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

1. F = 0;
2. N ≤ 1.

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

Входного файла содержит целые числа N F, за которыми следует N пар целых чисел m_i s_i.

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

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

Ограничения

0 ≤ N, F ≤ 1000, 0 ≤ s_i ≤ 59, 0 ≤ m_i ≤ 1000.

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

4 10
1 0
0 5
3 40
4 12

12

2 5
6 40
70 11

4311

Задача D. Топография ≡

Условие

Юный топограф Вася тренируется в рисовании карт местности. Вася отметил на карте вокруг своей школы четыре точки A, B, C, D, образующие выпуклый четырёхугольник, и тщательно измерил расстояния AC, AD, BC и BD. Измерить расстояние CD ему помешало здание школы.

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

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

Входной файл содержит целые числа AC AD BC BD.

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

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

Ограничения

1 ≤ AC, AD, BC, BD ≤ 10⁹

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

3 5 6 3

4 7

3 2 50 60

-1

Задача E. Гаджет в кредит ≡

Условие

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

В магазине Васе объяснили правила предоставления кредита.

• Первоначально сумма долга равна стоимости гаджета C.
• По истечении максимум N лет вся сумма долга должна быть выплачена
• Вася должен определить ежемесячный платеж M — целое число рублей, которое он будет выплачивать каждый месяц. Исключение может составлять последний платёж — оставшаяся на последний месяц сумма долга может оказаться меньше M.
• Каждый месяц после Васиного платежа оставшаяся сумма долга увеличивается на P процентов и округляется вверх до целого числа.

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

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

1. P = 0
2. C, P ≤ 10³

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

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

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

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

Ограничения

1 ≤ C ≤ 10⁹; 0 ≤ P ≤ 10⁹; 1 ≤ N ≤ 10⁴

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

1 0 1

1

1 124 12

8

1 1 12

2

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

Условие

Юный любитель 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

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

Условие

Турнир по олимпийской системе, состоящий из 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 

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

Условие

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

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

Координаты каждого места на стоянке определяются числами (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

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

Условие

Группа, состоящая 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