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

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ ai ≤ 109

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
n
1211 ≤ n ≤ 3
2311 ≤ n ≤ 1031
3481 ≤ n ≤ 1051, 2

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2 3
1
2
5
8 5 6 10 3
5
3
1
1000000000
1000000000

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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N, K ≤ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 3
3 4
2
3 9
1 4

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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 7
......#
.#..#.#
....#..
......#
.#..#.#
....#..
2
3 8
##.#..##
##.#.###
...#.##.
.#.#..#.
##.#.#.#
...#.##.

Задача D. Avengers and Shawarma

Автор:A. Usmanov. Translation: V. Toropov.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M, T ≤ 100

0 ≤ S ≤ 100

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

Стандартный вход Стандартный выход
1
5 2
10 5
45
2
13 4
4 1
22
3
10 1
5 0
50

Задача E. Bedtime thoughts

Автор:A. Usmanov. Translation and Illustrations: A. Logutova.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ L, H ≤ 100

0 < A < 90

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

Стандартный вход Стандартный выход
1
25 50 30
Yes
2
25 45 30
No
3
9 10 89
Yes

Задача F. Casino

Автор:佳木斯大学, A. Usmanov. Translation: V. Toropov.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

Ограничения

0 ≤ N ≤ 40

1 ≤ M ≤ 1000

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

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

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

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

Стандартный вход Стандартный выход
1
0 2
1
2
1 1
2

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

Автор:A. Usmanov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

В первой строке записано расположение первого коня в формате 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.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
e2
6
2
f5
8

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

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Первая строка входного файла содержит число N. Вторая строка содержит правильную скобочную последовательность длиной от 2 до 10000 символов.

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

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

Ограничения

1 ≤ N ≤ 5000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
()(())
()(())
2
3
(()((()(())())))(((())))
(()(()))((()))

Problem I. Altitude and visibility

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

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

You task is to find maximum di for every ai.

Input file format

Input file contains integer N followed by N integers ai.

Output file format

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

Constraints

1 ≤ N ≤ 106, 0 ≤ ai ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
10
0 
2
6
1 5 2 2 1 4
1 0 1 2 1 4 

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

Автор:Известная   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106

|ai| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
2 3 4 4
2
1
1
1

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

Автор:Известная   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

|ai| ≤ 109

0 ≤ m ≤ 2 n − 2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
-3 -2 -1 0
6
RRRLLL
-2 -1 0 0 0 0
2
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. Очередь в поликлинике

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

0 < tmax ≤ 106, 0 < (ti, mi) ≤ tmax, ti < ti + 1

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

Входной файл (input.txt) Выходной файл (output.txt)
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
2
1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3
2 1210

0.812s 0.018s 37