Задача A. Крот и лопата ≡

Условие

Прямоугольный участок земли протяжённостью S_x с запада на восток и S_y с севера на юг покрыт слоем почвы глубиной S_z. Внутри почвы, в точке с координатами (x, y, z) находится крот. (Ось x направлена c запада на восток, ось y — с юга на север, ось z — сверху вниз, точка (0, 0, 0) находится на поверхности в юго-западном углу участка).

Крот ползёт под землёй, оставляя за собой проход. Будем считать, что проход состоит из N отдельных ячеек размером 1x1x1. За единицу времени крот смещается на одну ячейку в одном из шести направлений: север, юг, запад, восток, вверх или вниз, не выходя за пределы участка. Направления обозначены буквами N, S, W, E, U, D соотвественно. Таким образом, весь путь крота можно задать строкой из N символов. На участке было выкопано T очень узких траншей глубиной S_z. Каждая траншея пересекает весь участок в направлении строго с запада на восток, от ячейки (0, y_i, 0) до (S_x − 1, y_i, S_z − 1).

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

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

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

Ограничения

1 ≤ S_y ≤ 10⁴

1 ≤ S_x, S_z ≤ 100

0 ≤ x ≤ S_x − 1

0 ≤ y ≤ S_y − 1

0 ≤ z ≤ S_z − 1

0 ≤ N ≤ 10⁶

1 ≤ T ≤ 100

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

4 3 5  2 1 3  3 1
2
NDE

....
....
....
..0.
..00

Задача B. Рыбы и сеть ≡

Условие

Косяк из F рыб разной толщины желает проплыть сквозь сеть таким образом, чтобы ни одна рыба не попалась. Предположим, что i-ая рыба имеет в наибольшем поперечном сечении форму круга диаметра d_i. Рыба может проскочить через определённую ячейку сети в том случае, если окружность диаметром d_i целиком помещается в соотвествующем треугольнике. Касания сторон треугольника разрешены. В единицу времени через данную ячейку может проплыть не более одной рыбы.

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

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

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

Ограничения

1 ≤ N, F ≤ 1000

0 ≤ x_i, y_i, u_i, v_i, p_i, q_i ≤ 1000

0 ≤ d_i ≤ 1000

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

1
0 0 10 10 0 10
2
1 1

2

Задача C. Ежеминутные автобусы ≡

Условие

На автобусную остановку каждую минуту подходит автобус одного из маршрутов. Диспетчерская служба собрала данные за N минут — номера маршрутов каждого автобуса.

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

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

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

Все числа целые. Каждый номер маршрута встречается не менее двух раз.

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

Ограничения

2 ≤ i ≤ 10⁶

1 ≤ a_i ≤ 100

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

8
2 11 2 2 25 11 25 11

4

4
23 23 41 41

1

Задача D. Подстроки из одинаковых букв ≡

Условие

В данной строке, состоящей из малых латинских букв, найти пару самых длинных подстрок, состоящиx из одних и тех же букв (возможно, в разном порядке).

Например, в строке twotwow это будут подстроки wotwo и otwow.

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

Входной файл содержит исходную строку.

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

Ограничения

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

abcde

0

abcdea

5