Задача A. Дорога в аэропорт ≡

Условие

Город соединяется с аэропортом автодорогой, имеющей N полос движения. Дорога состоит из K участков длиной 10 километров каждый. На каждом участке полосы разделены сплошной линией разметки (т.е. сворачивать с одной полосы на другую запрещено). На стыке участков разрешено перемещение на любую из соседних полос. В начале каждого участка на каждой полосе дороги поставлен знак ограничения скорости, при этом на разных полосах ограничения могут различаться.

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

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

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

Ограничения

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

1 3
70 60 40

0.559

3 2
1 10000
1 1
100 1

10.001

Задача B. Честное списывание ≡

Условие

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

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

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

Ограничения

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

5 4
1 2 
2 3
3 1
3 4

3

Задача C. Полосатый кафель ≡

Условие

Плитка кафеля представляет собой квадрат размером N × N клеток. Каждая клетка окрашена в один из цветов, заданный буквой от "a" до "z".

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

По описанию плитки следует определить, какого цвета полосы образуются.

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

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

Ограничения

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

4
owww
owow
wwow
oowo

w

3
ibi
ibi
ibi

bi

2
ab
cd

NO

5
aaxaa
axxaa
xxaxx
aaxxa
aaxaa

x

Задача D. Биллиардная пирамида ≡

Условие

Биллиардные шары сложены на столе в форме пирамиды. В первом ряду пирамиды находится один шар. В каждом последующем — на один больше, чем в предыдущем. В последнем ряду находится N шаров.

Назовем 1-внешними шары на последнем ряду пирамиды, а также самый левый и самый правый шары в каждом ряду. При удалении 1-внешних шаров размер пирамиды уменьшается. 1-внешние шары новой пирамиды мы будем называть 2-внешними. Продолжая процесс до тех пор, пока пирамида не исчезнет, можно определить k-внешние шары. Шары бывают двух видов: одноцветные и полосатые. Будем называть пирамиду хорошей, если при обходе 1-внешних шаров по периметру встретится не более одной пары соседних шаров одного вида. Будем называть пирамиду замечательной, если это свойство выполняется для t-внешних шаров для любого t.

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

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

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

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

В приведенном примере средний шар меняется местами с нижним правым (1 действие).

Ограничения

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

4
   1
  0 0 
 1 0 1  
1 0 1 1

1

Задача E. Уровень столбов ≡

Условие

Строительная компания построила кирпичный забор, имеющий N столбов. Из-за недосмотра оказалось, что столбы имеют разную высоту — i-й столб состоит из a_i кирпичей, лежащих вертикально один на другом. До приезда проверяющей комиссии осталось совсем немного времени, и за это время строители успеют положить либо убрать не более k кирпичей.

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

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

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

В выходной файл следует вывести числа s e m, где s, e — начало и конец максимального участка (1 ≤ s ≤ e ≤ N), m — количество потребовавшихся действий (0 ≤ m ≤ k). Затем вывести m чисел, d_i, которые обозначают, что на столб a_|di| следует положить кирпич, если d_i > 0, либо снять кирпич, если d_i < 0.

Если существует несколько решений, дающих участки одинаковой длины, вывести любое из них.

Ограничения

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

3 2
1 2 3

1 3 2
1 -3

4 10
1 5 1 100

1 3 4
-2 -2 -2 -2

Задача F. Календарная перестановка ≡

Условие

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

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

1. Даты соответствуют правилам календаря: в году 12 месяцев, количество дней в месяцах равно 31,28,31,30,31,30,31,31,30,31,30,31. Годы, номера которых делятся на 4, но не делятся на 100, являются високосными. Годы с номерами, делящимися на 400, также високосные. В високосный год в феврале 29 дней.
2. Дата начала события должна предшествовать дате окончания. Даты НЕ должны совпадать.

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

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

Ограничения

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

5 2005 11
4 2006 10

1 3 2

7 8 9 9 8 7

3 2 1

1000 1000 1000 1 1 1

-1

Задача G. Сплошной кафель ≡

Условие

Плитка кафеля имеет форму квадрата размером 1 × 1, раскрашенного в один из цветов, заданных буквами от "a" до "z".

Если замостить квадратную область размером N × N разноцветными плитками, то могут образоваться горизонтальные или вертикальные одноцветные полосы длиной N плиток.

По описанию области следует определить цвета горизонтальных и вертикальных полос.

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

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

Ограничения

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

4
owww
owow
wwow
oowo

NO

3
ibi
ibi
ibi

bi