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

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

Условие

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

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

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

Во входном файле находятся числа N и K, за которыми идут N строк по K вещественных чисел ai, j в каждой — ограничение скорости на j-м участке i-й полосы (в км/час).

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

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

Ограничения

1 ≤ N ≤ 10, 1 ≤ K ≤ 1000, 1 ≤ ai, j ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 3
70 60 40
0.559
2
3 2
1 10000
1 1
100 1
10.001

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

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

Условие

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

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

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

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

В первой строке входного файла содержатся числа N M. Далее следует M пар чисел в диапазаоне от 1 до N. Пара a b означает, что школьник с номером b может списать у школьника с номером a.

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

Выходной файл должен содержать единственное целое число — количество способов. Ответ должен быть выведен без лидирующих нулей. В приведенном примере возможны три способа выбора школьников, удовлетворяющих условию: {1,5},{2,5},{3,5}. Школьник 4 списывает в любой ситуации.

Ограничения

1 ≤ N ≤ 104, 0 ≤ M ≤ 105

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

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

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

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

Условие

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

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

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

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

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

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

Выходной файл должен содержать строку из букв, соответствующих цветам полос, в алфавитном порядке. Если не образуется ни одной полосы, слеудет вывести строку NO

Ограничения

1 ≤ N ≤ 300

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
owww
owow
wwow
oowo
w
2
3
ibi
ibi
ibi
bi
3
2
ab
cd
NO
4
5
aaxaa
axxaa
xxaxx
aaxxa
aaxaa
x

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

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

Условие

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

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

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

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

В первой строке входного файла находится чило N. Затем следуют N строк с описанем пирамиды. В i-ой строке находится i чисел 1 или 0, разделенных произвольным количеством пробелов. Они обозначают вид шара в i-м ряду (1 - одноцветный, 0 - полосатый).

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

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

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

Ограничения

1 ≤ N ≤ 50

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

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

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

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100, 0 ≤ k, ai ≤ 10000

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

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

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

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

Условие

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

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

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

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

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

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

Выведите три числа — номера компонент описывающих день, месяц и год. Если существует несколько решений, выведите любое из них. Если решения не существует, выведите -1. В первом примере даты расшифровываются как: 5 ноября 2005 и 4 октября 2006.

Ограничения

Все числа натуральные и не превосходят 3000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 2005 11
4 2006 10
1 3 2
2
7 8 9 9 8 7
3 2 1
3
1000 1000 1000 1 1 1
-1

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

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

Условие

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

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

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

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

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

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

Выходной файл должен содержать строку из букв, соответствующих цветам полос, в алфавитном порядке. Если не образуется ни одной полосы, слеудет вывести строку NO

Ограничения

1 ≤ N ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
owww
owow
wwow
oowo
NO
2
3
ibi
ibi
ibi
bi

0.092s 0.006s 19