Данил и Даниил гуляли по Нижне-Волжской набережной и подошли к катеру 'Герой'. Они оглянулись и увидели какой-то памятник наверху. Им стало интересно, что это за памятник, но подниматься по большой лестнице, чтобы узнать название памятника, им было лень. Однако, они смогли уговорить себя подняться, но только по наименьшему количеству ступенек. Помогите Данилу и Даниилу понять, сколько ступенек им придется пройти.

План лестницы представлен на картинке ниже. На каждой части лестницы находится соответствующее ей количество ступенек $$$(a, \ b, \ c, \ d, \ e)$$$.

Идет дождь.

Дождь состоит из $$$n$$$ капель, падающих вертикально вниз на прямую $$$y=0$$$. Для каждой капли известно положение, куда она упадет — $$$x_i$$$ и время, когда она упадет — $$$t_i$$$. После падения капля растекается так, что через $$$k$$$ секунд она полностью накроет отрезок $$$[x_i - k, x_i + k]$$$, включая его концы.

Вам нужно найти наименьшее целое число $$$T$$$, такое что через $$$T$$$ секунд капли полностью накроют отрезок $$$[0, r]$$$.

В Нижнем Новгороде идëт $$$2221$$$ год. Люди уже давно живут в гигантских небоскрëбах и передвигаются на летающих машинах. Под землëй был обнаружен старый город - отголосок далëкого прошлого. Туда стали водить экскурсии, а это место прозвали Нижний Нижний Новгород. И вот недавно там обнаружили старинное метро, некоторые станции которого нужно отреставрировать, чтобы проводить экскурсии и там. Рабочее название у древней подземки - Нижний Нижний Нижний Новгород. Старинное нижегородское метро представляет из себя $$$n$$$ станций. Некоторые пары станций соединены двунаправленными туннелями. Всего таких туннелей $$$m$$$. Рабочие пронумеровали станции числами от $$$1$$$ до $$$n$$$. Цена реставрации станции под номером $$$i$$$ равна $$$c_i$$$ рублей. Реставрация происходит так:

Сначала выбирается целое число $$$s\ (1 \leq s \leq n)$$$ - номер стартовой станции. Затем рабочие рассматривают все станции, до которых можно доехать от стартовой не более чем по $$$d$$$ туннелям, в том числе и сама станция под номером $$$s$$$. Несколько (больше нуля) станций из рассматриваемых будут реставрировать, однако, деньги на реставрацию выделяют суммами по $$$k$$$ рублей, поэтому требуется, чтобы суммарная стоимость реставрации выбранных станций делилась на $$$k$$$. Вам нужно для всех возможных стартовых станций $$$i$$$ от $$$1$$$ до $$$n$$$ сказать, какое должно быть минимальное $$$d$$$, чтобы среди всех рассмотренных станций можно было выбрать несколько таких, что суммарная стоимость их реставрации делилась на $$$k$$$. Заметьте, что стартовая станция не обязательно будет выбрана для реставрации.

Как известно, коренные москвичи любят покупать еду по скидкам, и Балбек не исключение. В таком прекрасном заведении, как «Тусно и вкочка», проходит очередная акция для жителей столицы. Всего в Москве $$$n$$$ таких заведений, и каждое располагается на плоскости в точке с координатами ($$$x_i, \ y_i$$$). В каждом заведении можно получить ровно 1 стикер.

Собрав $$$t$$$ стикеров, можно получить скидку в $$$\frac{100t}{n}\%$$$ на следующую покупку. К сожалению, москвичи ходят только по прямой, поэтому могут забрать стикеры только из заведений, находящихся на одной прямой. Балбек вышел на улицу и очень хочет получить скидку хотя бы $$$m\%$$$. Помогите определить, возможно ли это сделать при условии, что Балбек выйдет на улицу только один раз и, как коренной москвич, тоже будет идти только по единственной прямой, не сворачивая. Если это возможно, то скажите, какие номера заведений ему нужно посетить?

Дана строка $$$S$$$, состоящая из $$$k$$$ видов пар скобок. Каждая скобка имеет вид $$$t$$$ — целое число, такое что $$$1 \leq |t| \leq k$$$. Если скобка имеет вид $$$t$$$, то

• Если $$$t$$$ > 0, то это открывающая скобка типа $$$t$$$.
• Если $$$t$$$ < 0, то это закрывающая скобка типа $$$-t$$$.

Таким образом, всего существует $$$k$$$ типов пар скобок.

Напомним определение правильной скобочной последовательности:

• Пустая последовательность является правильной.
• Если $$$A$$$ и $$$B$$$ - две правильные скобочные последовательности, то их конкатенация $$$« AB»$$$ тоже является правильной скобочной последовательностью.
• Если $$$A$$$ - правильная скобочная последовательность, $$$c \ (1\leq c \leq k)$$$ — некоторый тип скобок, то последовательность $$$«c\ \ A\ \ {-c}»$$$ тоже является правильной.

Циклический сдвиг скобочной последовательности вправо на $$$m$$$ > 1 эквивалентен $$$m$$$ циклическим сдвигам на 1.

Найдите все такие $$$m \ (0 \leq m \leq |S| - 1) $$$, что при циклическом сдвиге на $$$m$$$ элементов получившаяся скобочная последовательность будет правильной.

Два друга — Данил и Даниил — шли домой дорогой ночной, вдруг они придумали игру. Эта игра проходит следующим образом: На доске изначально написано число $$$n$$$. У Данила есть число $$$d_1$$$, а у Даниила — число $$$d_2$$$. Игра состоит из нескольких ходов. Данил и Даниил ходят по очереди. Первым ходит игрок с меньшим количеством букв «и» в своём имени (Данил). На каждом ходу игрок, которому принадлежит ход, пытается разделить число, написанное на доске (обозначим его $$$x$$$), на своё число. Если $$$x$$$ делится на число игрока нацело, то число на доске заменяется на результат деления, иначе вместо $$$x$$$ записывается $$$x - 1$$$. Затем ход завершается, а очередь ходить переходит к другому игроку. Как только $$$x$$$ становится равным нулю, игра завершается. Данилу и Даниилу интересно, сколько ходов произойдёт в такой игре в зависимости от значений $$$n$$$, $$$d_1$$$ и $$$d_2$$$.

На доске находится одна белая пешка и несколько чёрных фигур. Белая пешка изначально расположена в самой левой нижней клетке $$$(1, 1)$$$ и может ходить по правилам шахмат, при этом чёрные фигуры ходить не могут. Более формально:

• Из клетки $$$(1, R)$$$, пешка может попасть в $$$(1, R + 1)$$$, только если в клетке $$$(1, R + 1)$$$ нет чёрной фигуры.
• Из клетки $$$(1, R)$$$, пешка может попасть в $$$(2, R + 1)$$$, только если в клетке $$$(2, R + 1)$$$ есть чёрная фигура (после такого хода чёрная фигура исчезает и на её место становится белая пешка).
• Из клетки $$$(2, R)$$$, пешка может попасть в $$$(2, R + 1)$$$, только если в клетке $$$(2, R + 1)$$$ нет чёрной фигуры.
• Из клетки $$$(2, R)$$$, пешка может попасть в $$$(1, R + 1)$$$, только если в клетке $$$(1, R + 1)$$$ есть чёрная фигура (после такого хода чёрная фигура исчезает и на её место становится белая пешка).

Если пешка не способна сделать ход, по правилам, описанным выше, то она останавливается.

Вам известны позиции чёрных фигур. Необходимо проверить, сможет ли пешка достичь своей цели, то есть дойти до одной из клеток: $$$(1, 10^{18})$$$ или $$$(2, 10^{18})$$$.

Сколько же задач будет на очередной Нижегородской олимпиаде по информатике? Понятно, что ответ зависит от некоторого числа $$$n$$$, но чтобы вычислить количество задач точно (а это крайне необходимо, ведь решительно не ясно, до какой буквы надо учить английский алфавит на этот раз), нужно строго следовать инструкциям.

Пару натуральных чисел $$$a$$$ и $$$b$$$ назовем дружной, если каждое из них содержит хотя бы две цифры (то есть они не меньше $$$10$$$), не содержит ведущих нулей и последняя цифра числа $$$a$$$ совпадает с первой цифрой числа $$$b$$$.

Количество различных дружных пар (a, b), таких, что $$$a + b = n$$$, и будет ответом на поставленный выше извечный вопрос.

Если число $$$a$$$ не равно числу $$$b$$$, то пары $$$(a, b)$$$ и $$$(b, a)$$$ считаются различными (см. пример 1).