Задача A. Варфоломей и вафли ≡

Условие

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

Какой максимальной высоты можно построить башню, если на каждом этаже нужно установить K вафель?

Формат входных данных

Входные данные содержат 3 числа: A — количество вафель первого вида, B — количество вафель второго вида, K — количество вафель на этаже.

Формат выходных данных

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

Ограничения

1 ≤ A, B, K ≤ 10⁴

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

4 8 2

5

5 7 3

3

Задача B. Рыбоводная ферма ≡

Условие

В агрокомплексе открывается новое направление деятельности – выращивание рыбы методом закрытого разведения в установках замкнутого водоснабжения (УЗВ). В рамках подготовительных работ была обустроена площадка прямоугольной формы размером a×b метров для размещения рыбоводной фермы УЗВ. По периметру данной площадки необходимо организовать ровный помост шириной h метров, покрытый нескользящим материалом для удобства обслуживания элементов рыбоводной фермы (см. рис.). Определите площадь помоста.

Напишите программу для решения этой задачи!

Формат входных данных

Единственная строка содержит три целых числа, каждое из которых отделено друг от другого одним пробелом, a, b, h, , где a – ширина площадки в метрах, b – длина площадки в метрах, h – ширина помоста в метрах.

Формат выходных данных

Выведите единственное целое число S – площадь помоста, измеряемое в квадратных метрах.

Ограничения

0 < a ≤ 10³

0 < b ≤ 10⁴

0 < h ≤ 10²

b > a > 2 * h

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

  20 30 10

  1400

  11 19 5
  

  400

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

Условие

Один из способов построения множества всех неотрицательных несократимых дробей вида 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

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

Условие

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

Задача E. Путешествие ≡

Условие

Утенок Даки только выпустился из университета и устроился на работу разработчиком игр. Ему поручили создание новой игры SpaceWar. Игра заключается в сражениях с космическим флотом противника путём отправки флотов кораблей между планетами.

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

В этой игре между двумя планетами иногда появляются "кротовые норы" (англ. wormholes), пройдя через которые, флот может переместиться вперед во времени и оказаться у следующей планеты. В то же время может также существовать "обычный" путь между планетами, который флот может преодолеть за некоторое время. Существование кротовых нор и обычного пути не связаны между собой. Кротовые норы появляются не сразу и, если флот окажется у планеты, нора около которой еще не образовалась, он не сможет ею воспользоваться. Воспользоваться норой в обратном направлении невозможно. Даки хочет определить, в какой самый ранний момент времени его флот, находящийся у планеты A, может оказаться у планеты B.

Формат входных данных

Первая строка содержит 3 целых числа: N, A, B – количество планет, планету с флотом и планету-цель, соответственно.

Далее следует строка с 2 целыми числами: M – количество кротовых нор и K – количество обычных путей.

Последующие M строк содержат 4 целых числа: A_i, B_i – две планеты, между которыми появляется нора, t_i – время её появления и dt_i – насколько изменится время при перемещении по ней из A_i в B_i.

Далее идут K строк в таком формате: A_j, B_j, t_j – две планеты и время пути между ними.

Считаем, что изначально время равно 0. Все планеты нумеруются от 1 до N включительно. Обычные пути существуют в любое время.

Формат выходных данных

Выведите единственное число – самое раннее время в которое флот сможет оказаться у планеты B.

Гарантируется, что путь существует.

Ограничения

1 ≤ A, B, A_i, B_i, A_j, B_j ≤ N ≤ 10⁴

N ≤ M + K ≤ 10⁵

0 ≤ t_i, dt_i, t_j ≤ 10⁹

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

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

3

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

4