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

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

Условие

Город соединяется с аэропортом автодорогой, имеющей 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. Честное списывание

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

Условие

В группе школьников, состоящей из 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. Уровень столбов

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

Условие

Строительная компания построила кирпичный забор, имеющий 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

Задача D. Нормальное честное списывание

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

Условие

В группе школьников, состоящей из 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

0.239s 0.017s 19