Задача A. Пицца ≡

Условие

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

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

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

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

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

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

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

Далее следует N различных целых чисел a_i — размеры кусочков пиццы, перечисленные в порядке обхода по кругу.

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁹

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

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

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

3
1 2 3

1

5
8 5 6 10 3

5

1
1000000000

1000000000

Задача B. Мы делили... ≡

Условие

На день рождения пришли N гостей. Праздничный торт разделили между всеми гостями поровну. После этого неожиданно явились ещё K гостей.

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

Ответ вывести в виде несократимой обыкновенной дроби A / B.

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

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

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

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

Ограничения

1 ≤ N, K ≤ 10⁴

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

1 3

3 4

3 9

1 4

Задача C. Минимальный лабиринт ≡

Условие

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

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

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

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

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

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

Далее идут N строк по M символов, описывающие лабиринт:

• # (ASCII 35) — обозначает блок
• . (ASCII 46) — обозначает пустое место

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

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

Ограничения

1 ≤ N, M ≤ 100

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

3 7
......#
.#..#.#
....#..

......#
.#..#.#
....#..

3 8
##.#..##
##.#.###
...#.##.

.#.#..#.
##.#.#.#
...#.##.

Задача D. Avengers and Shawarma ≡

Условие

Разобравшись с инопланетным вторжением, Мстители решили перекусить шаурмой.

Придя в шаурмечную, Халк заказал себе N штук шаурмы. M поваров немедленно приступили к выполнению заказа. Каждый повар может приготовить свою первую шаурму за T минут. Каждая последующая шаурма требует для приготовления на S минут больше, чем предыдущая.

Халк крушит!, пока ожидает приготовления заказанной шаурмы.

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

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

В первой строке записано два целых числа N и M — количество шаурмы, заказанные Халком, и количество поваров, взявшихся за заказ гиганта.

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

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

Выведите одной целое число — время приготовления всего заказа Халка.

Ограничения

1 ≤ N, M, T ≤ 100

0 ≤ S ≤ 100

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

5 2
10 5

45

13 4
4 1

22

10 1
5 0

50

Задача E. Bedtime thoughts ≡

Условие

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

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

Окна комнаты Анастасии находятся на высоте H метров. Можно считать, что автомобиль осветил комнату, если освещена любая часть окна.

Свет от фар автомобиля образует сектор окружности. Дальность свечения от фар составляет L метров. Максимальный угол распространения света равен A градусов.

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

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

В первой строке записано три целых числа H, L и A.

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

Выведите "Yes" или "No" (без кавычек) — может ли автомобиль Анастасии осветить её комнату.

Ограничения

1 ≤ L, H ≤ 100

0 < A < 90

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

25 50 30

Yes

25 45 30

No

9 10 89

Yes

Задача F. Casino ≡

Условие

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

Самому старшему из братьев родители дали больше всего денег. Второму по старшинству — на один меньше, чем первому. Третьему — на один меньше, чем второму и т.д. Анингак самый младший и ему досталось всего M долларов.

Братья собираются играть до тех пор, пока у каждого из них не останется денег. Причем, передавать деньги друг другу братья не собираются.

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

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

В первой строке записано два целых числа N и M — количество братьев и количество денег у Анингака.

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

Выведите одно целое число — минимальное количество раундов.

Ограничения

0 ≤ N ≤ 40

1 ≤ M ≤ 1000

Пояснение к примерам

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

Во втором примере у Анингака есть 1 доллар, а у его брата — 2 доллара. Братья могут выбрать ставку в один доллар. Тогда в первом раунде Анингак истратит все свои деньги, а у брата хватит денег сыграть еще в одном раунде.

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

0 2

1

1 1

2

Задача G. Edge of the knight ≡

Условие

Во время игры в шахматы существует выгодная ситуация, когда две фигуры коней прикрывают друг друга.

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

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

В первой строке записано расположение первого коня в формате HW, где H — обозначение колонки (вертикали), W — обозначение строки (горизонтали).

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

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

Ограничения

H ∈ (a, b, c, d, e, f, g, h)

1 ≤ W ≤ 8

Пояснение к примерам

Напомним, что фигура конь ходит буквой Г. То есть во время своего хода конь перемещается в одном из направлений (вертикальном или горизонтальном) на 1 одну клетку, а в другом направлении — на 2 клетки.

В первом примере второго коня можно поставить в клетки c 1, g 1, c 3, g 3, d 4 и f 4.

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

e2

6

f5

8

Задача H. Слишком вложенные скобки ≡

Условие

Дана правильная последовательность из круглых скобок. Требуется удалить из неё все скобки, находящиеся на глубине вложенности N и более. Например, в последовательности (()((()(())())))(((()))) выделены скобки, вложенные на 3 и более уровней.

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

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

Ограничения

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

2
()(())

()(())

3
(()((()(())())))(((())))

(()(()))((()))

Problem I. Altitude and visibility ≡

Statement

Consider a sequence of numbers a₁, …, a_N, representing heights. Let's say that element a_i has a visibility radius d if a_i ≥ a_j for all j such that 1 ≤ j ≤ N and |i − j| < d.

You task is to find maximum d_i for every a_i.

Input file format

Input file contains integer N followed by N integers a_i.

Output file format

Output file must contain N integers d_i — maximum visibility for every a_i. If maximum visibility radius for element a_i is unlimited, output d_i = 0.

Constraints

1 ≤ N ≤ 10⁶, 0 ≤ a_i ≤ 10⁹

Sample tests

1
10

0 

6
1 5 2 2 1 4

1 0 1 2 1 4 

Задача J. Ближайшее число ≡

Условие

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

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

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

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

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача K. Максимум в скользящем окне ≡

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2 n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Задача L. Очередь в поликлинике ≡

Условие

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

За отдельно взятые сутки была собрана статистика, состоящая из моментов времени t_i, указанных в талоне каждого i-го пациента, и времени m_i, которое было затрачено на его прием.
Требуется определить максимальную длину очереди, которая имела место за текущие сутки, а также время окончания приема последнего пациента.

При решении задачи следует полагать, что все t_i и m_i указывают время в минутах и могут принимать только целочисленные значения. Число минут в сутках полагается равным t_max.

Также известно, что пациентам, которые не успели пройти прием в течение суток, очередь автоматически продлевается на следующий день.
В качестве окончания приема для всех таких пациентов указывается максимально допустимое время t = t_max.

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

В начале входного файла "input.txt" содержится пара натуральных чисел t_max и n, за которыми следует ровно n записей, представленных в виде пар положительных целых чисел t_i и m_i. При этом полагается, что все они упорядочены по возрастанию t_i.

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

Выходной файл "output.txt" должен содержать два значения: максимальную длину очереди и время завершения последнего приема.

Ограничения

0 < t_max ≤ 10⁶, 0 < (t_i, m_i) ≤ t_max, t_i < t_i + 1

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

1440 10
1 1
2 1
3 2
54 2
349 1
720 2
1024 2
1175 2
1193 1
1205 3

0 1208

1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3

2 1210