Формат входных данных.

Детский сад

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

У Деда Мороза есть мешок, в котором находится N карточек. На каждой из них написано некоторое целое число A_i. В игру играют двое детей. В начале игры оба играющих ребенка наугад вытягивают по одной карточке из мешка Деда Мороза. Затем ребенок, который вытащил карточку с бо′льшим числом, получает от Деда Мороза конфеты, причем количество полученных конфет равно разности чисел, написанных на карточках, которые вытянули дети.

Например, Петя и Вася играют в эту игру. Петя вытащил карточку с числом 4, а Вася с числом 2. После этого Петя берет себе 2 (4 – 2 = 2) конфеты.

У Деда мороза появилась проблема – он не знает, сколько конфет необходимо купить на праздник. И он решил обратиться к вам за помощью. Его интересует максимальное количество конфет, которое может получить ребенок в результате игры. Помогите ему решить эту проблему!

Входные данные

Первая строка входного файла содержит одно целое число N (2 ≤ N ≤ 100), которое представляет собой число карточек.

Вторая строка входного файла содержит ровно N целых чисел A_i (1 ≤ A_i ≤ 32767). Числа в строке разделяются одиночными пробелами. A_i – число, написанное на i -й карточке.

Выходные данные

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

Входной файл input.txt

Выходной файл output.txt

Время на тест 1 сек

Ограничение памяти 64 MB

Анализ изображения

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

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

Дополнительные расчеты заключаются в нахождении коэффициента связности исходного изображения. Коэффициент связности – это число различных пар соседних пикселей.

Изображение представляет собой прямоугольную таблицу пикселей размера N x M. Каждый пиксель имеет либо белый цвет, либо черный. Два различных пикселя называются соседними, если выполняются следующие условия:

1. Оба пикселя имеют белый цвет.

2. Оба пикселя находятся или в одном и том же столбце или в одной и той же строке.

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

Рисунок №1: N = 5 и M = 6, пример соседних символов для пикселя (2, 4).

Для приведенного выше примера все закрашенные пиксели являются соседними для пикселя, обозначенного звездочкой. Две пары соседних пикселей, которые могут быть получены одна из другой при помощи перестановки элементов, не считаются различными. То есть пара соседних пикселей {(2; 4), (2; 6)} и пара {(2; 6), (2; 4)} не считаются различными.

Вам как младшему научному сотруднику НИИ было поручено написать программу, которая по заданному описанию изображения рассчитывает коэффициент связности данного изображения.

Входные данные

Первая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 200).

Далее следуют N строк по M символов в каждой, описывающих исходное монохромное изображение. Символ ‘.’(ASCII 46) – обозначает белый символ, а ‘#’(ASCII 35) – черный.

Выходные данные

Одно целое число – коэффициент связности исходного монохромного изображения.

Имя входного файла: lantern.in

Имя выходного файла: lantern.out

Ограничения по времени: 1 секунда

Ограничения по памяти: 256 Мбайт

Фонари у дороги

Прямой отрезок дороги из Нью-Васюков в Старую Москву длины M снискал дурную славу из-за большого количества аварий на нём, особенно в ночное время. Дорожный департамент в конце концов решил установить фонари и осветить весь этот отрезок. И тут чиновники обратили внимание, что отдельные участки дороги уже освещаются N фонарями, стоящими у заправочных станций, придорожных кафе и т.д., так что выделенные деньги можно сэкономить… В частности, фонарь с номером i (1 ≤ i ≤ N) освещает участок дороги [ ai, bi ], где 0 ≤ ai < bi ≤ M.

Участок дороги считается безопасным, если он освещен хотя бы одним фонарём.

По информации о расположении освещённых участков дороги определите суммарную длину безопасных участков дороги и количество неосвещённых участков.

Формат входных данных.

Первая строка содержит два целых числа: M – длину дороги, и N – количество фонарей (1 ≤ M ≤ 10⁶, 1 ≤ N ≤ 10⁵). Каждая из последующих N строк задаёт информацию об одном фонаре и содержит два целых числа ai и bi.

Не нашли, что искали? Воспользуйтесь поиском: