На плоскости задан многоугольник с целочисленными координатами вершин и сторонами,
параллельными осям координат.
Требуется найти самый длинный горизонтальный или вертикальный отрезок,
лежащий внутри многоугольника.
(Многоугольник включает свою границу).
Формат входного файла
В первой строке входного файла содержится число вершин N .
В следующих N строках расположены целочисленные координаты вершин xi, yi,
перечисленные в порядке обхода.
(При этом у каждой пары соседних вершин либо координаты x, либо координаты y совпадают).
Формат выходного файла
Выходной файл должен содержать единственное целое число — длину самого длинного отрезка.
Ограничения
4 ≤ N ≤ 500 ≤ xi, yi ≤ 1000
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
8
15 10
20 10
20 20
40 20
40 5
60 5
60 50
15 50
45
2
8
10 50
20 50
20 0
30 0
30 60
20 60
20 80
10 80
80
Задача B. Длинный текст и много слов (revisited)
≡
Имеется текст и N слов. Длина текста составляет L символов,
длина каждого слова — от 1 до 1000 символов.
Требуется для каждого слова определить, входит ли оно в текст.
Все слова и текст состоят из маленьких латинских букв.
Формат входного файла
В первой строке входного файла содержится текст,
во второй — число N, в следующих N строках — слова.
Формат выходного файла
В выходном файле должны содержаться N чисел 1 или 0,
обозначающих, что соответствующее слово входит или не входит в текст.
Недавно в главном офисе картографической службы Ландшафтии случился пожар.
Сгорел архив, хранящий таблицы с перепадами высот в различных регионах страны.
Для восстановления этой информации требуется заново
посчитать перепады высот по сохранившимся картам.
Карта региона представляет собой матрицу размером N x N клеток,
в каждой клетке которой содержится
средняя высота определённого района над уровнем моря.
Максимальным перепадом высот называется
максимальная величина, на которую отличаются средние высоты двух районов,
соседних на карте по горизонтали или по вертикали.
Требуется по карте региона определить максимальный перепад высот в нем.
Формат входного файла
Входной файл содержит число N,
за которым следуют N2 целых чисел — описание карты региона.
Формат выходного файла
Выходной файл должен содержать единственное целое число —
максимальный перепад высот в этом регионе.
Ограничения
1 ≤ N ≤ 100.
Все высоты — целые числа от 0 до 231−1
Имеется линейная функция от двух аргументов
f(x, y) = ax + by + c, причём коэффициенты
a, b, c неизвестны.
По данным N значениям
f(x1, y1) = d1, ...,
f(xN, yN) = dN
требуется однозначно определить значение функции
f(u, v) или указать, что это невозможно.
Обратите внимание, что однозначно восстанавливать саму функцию не требуется.
Гарантируется, что функция f существует.
Формат входного файла
Входной файл содержит целые числа N u v,
за которыми следует N троек целых чисел xi yi di.
Формат выходного файла
Выходной файл должен содержать единственное целое число f(u, v)
либо два числа 0 (ноль), если однозначное определение невозможно.
Ограничения
1 ≤ N ≤ 100,
−106 ≤ xi, yi, di ≤ 106,
коэффициенты a, b, c — целые
В одной секретной лаборатории вывели новый вид маленьких монстров, размером чуть больше суслика.
В ходе исследований ученые решили поставить следующий эксперимент.
В центре комнаты устанавливается прямоугольный стол, поверхность которого разбита на
N x M клеток размера 1x1.
В начальный момент времени на некоторых его клетках располагаются монстры,
смотрящие параллельно сторонам стола. По команде экспериментатора монстры начинают
двигаться по прямой в ту сторону, в которую они смотрят, доходят до края стола и
спрыгивают на пол. Там их собирает лаборант Петя и относит в клетку.
Рисунок 1. Монстры на столе для экспериментов
Поскольку у монстров очень грязные лапки, они оставляют следы на тех клетках, на которых они побывали.
Так как отмывать стол придется лаборанту Пете, его заинтересовал вопрос -
в каком количестве клеток побывают монстры. Помогите ему решить эту сложную задачу.
Формат входного файла
Первая строка входного файла содержит числа M и N - размеры лабораторного стола.
Следующая строка содержит число K - количество монстров.
Следующие K строк содержат описания монстров - два целых числа и один символ из множества
{N, E, S, W} - начальные координаты и направление соответствующего монстра
(соответствие направлений и координат приведено на рисунке 1).
Символ отделен от чисел ровно одним пробелом.
Формат выходного файла
В выходной файл выведите единственное число - количество клеток стола, на которых побывают монстры.
Муравей находится в лесу с плоской поверхностью почвы в точке с координатами
(x1, y1), и направляется в точку
(x2, y2).
В лесу растёт дерево, основание ствола которого имеет форму круга с центром в точке
(xT, yT) и радиусом RT.
Дерево, возможно, помешает муравью дойти до цели по прямой. В таком случае
ему придётся обойти дерево вокруг ствола.
Требуется определить длину кратчайшего пути для муравья.
Формат входного файла
Входной файл содержит вещественные числа x1y1x2y2xTyTRT.
Формат выходного файла
Выходной файл должен содержать единственное вещественное число — длину кратчайшего пути.
Абсолютная ошибка результата не должна превосходить 0.01
(т.е. следует выводить число с точностью не менее 3 знаков после запятой).
Ограничения
Все числа во входном файле находятся в диапазоне от 0 до 1000.
(x1 − xT)2 +
(y1 − yT)2 ≥
RT2,
(x2 − xT)2 +
(y2 − yT)2 ≥
RT2
Текстовый редактор OLE (One-Line Editor) работает с текстом,
состоящим ровно из одной строки строчных латинских букв.
Редактор поддерживает следующие команды, длиной в один символ каждая:
a … z — вставить справа от текущей позиции курсора
указанный символ, переместить курсор на один символ вправо
L — переместить курсор на 1 символ влево
R — переместить курсор на 1 символ вправо
X — удалить символ справа от позиции курсора
Команды, пытающиеся переместить курсор за пределы строки или удалить
символ справа от последнего символа строки, игнорируются редактором.
Требуется по данному начальному состоянию строки, начальной позиции курсора и
последовательности команд определить результат работы редактора.
Формат входного файла
Входной файл состоит из 3 строк. В первой строке содержится позиция курсора p,
(0 — курсор перед первым символом, 1 — после первого перед вторым, и т.д.)
во второй строке — начальное состояние строки редактора, в третьей — последовательность
команд.
Формат выходного файла
Выходной файл должен содержать строку, полученную в результате выполнения команд.
Ограничения
Длина исходной строки находится в диапазоне от 1 до 1000000 символов.
Длина строки команд находится в диапазоне от 1 до 100000 символов. 0 ≤ p ≤ длина исходной строки.
Поле для игры в Lines представляет собой квадрат размером N x N клеток,
в каждой клетке которого может находиться шарик.
После хода игрока (состоящего в перемещении одного из шариков) все шарики,
входящие в горизонтальные, вертикальные либо диагональные ряды длиной 5 и более,
удаляются с поля.
По данной позиции сразу после хода игрока определить число удаляемых с поля шариков.
Формат входного файла
Входной файл состоит из N строк по N символов в каждой. Символ "." обозначает
пустую клетку, а символ "O" (латинская заглавная O) — шарик.
Формат выходного файла
Выходной файл должен содержать единственное целое число — количество удаляемых шариков.
В данном двумерном целочисленном массиве a размером N × N
требуется найти три элемента, сумма которых максимальна.
При этом первый элемент должен быть соседним по горизонтали или вертикали со вторым, а второй — с третьим.
Формат входного файла
Входной файл содержит число N, за которым следует N2 чисел
a1,1a1,2
…
a1,N
a2,1a2,2
…
a2,N
…
aN,1aN,2
…
aN,N
— элементы массива.
Формат выходного файла
Выходной файл должен содержать единственное число — максимальную сумму.
При N = 1 следует вывести единственный элемент матрицы.
Петя часто ходит в Океанариум — особенно ему там нравится один большой аквариум,
в котором плавают разнообразные маленькие рыбки.
Пете очень интересно, сколько всего рыбок в аквариуме, но часть из них всё время скрывается
за камнями и водорослями.
Поэтому каждый раз, когда Петя подходил к аквариуму, он выписывал на листок названия
всех рыбок, которые были ему видны.
Всего у Пети скопилось N таких листков. Требуется написать программу,
которая по Петиным записям определит минимально возможное количество
рыбок в аквариуме.
Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста,
а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.
Рекомендуется рассмотреть частичные решения
N = 1,
каждый листок содержит ровно одно название рыбки.
Формат входного файла
Первая строка входного файла содержит число N.
Далее следует последовательность из N описаний листков.
В первой строке каждого описания содержится число рыбок Ki, в последующих
Ki строках — названия рыбок.
Формат выходного файла
Выходной файл должен содержать единственное число — минимальное количество рыбок.
Ограничения
1 ≤ N, Ki ≤ 50, длина названий не превосходит 255 символов.
Числа от 1 до N выписаны подряд в строку. Разрешается менять местами любые два числа,
между которыми в строке стоят ровно P1, P2, ... или PM, чисел (числа P1, P2, ..., PM заданы).
Например, пусть N = 5, M = 2, P1 = 3, P2 = 2.
Тогда после перестановки чисел в позициях 1 и 4 (между ними стоят 2 числа) и
чисел в позициях 1 и 5 (между ними стоят 3 числа) получится по-следовательность 5, 2, 3, 1, 4.
Напишите программу, вычисляющую количество расположений чисел в строке, которые можно
получить из начальной строки какой либо последовательностью перестановок.
Формат входного файла
Файл исходных данных INPUT.TXT содержит (в указанном порядке): N, M, P1, P2, ..., PM.
Все числа в файле разделяются пробелами и (или) символами перевода строки. Входные данные корректны.
Формат выходного файла
В выходном файле OUTPUT.TXT должно находиться искомое число.
Частичные решения задачи (количество перестановок < 2 147 483 648) будут оцениваться исходя из 15 баллов.
Естественно, в тестирующей системе частичные решения оцениваться не будут.
Ограничения
2 ≤ N ≤ 3000
1 ≤ M ≤ 500
Для всех i (1 ≤ i ≤ M) выполняется 0 ≤ Pi ≤ N - 2
Профессор едет по шоссе из Петербурга в Москву, имея при себе карту с
указанием всех N стоящих на шоссе бензоколонок и расстояний
Di до них от Петербурга. Известно расстояние S,
которое может проехать машина с полностью заправленным
баком.
Требуется выяснить, на каких бензоколонках нужно заправляться, чтобы
количество заправок было минимально. В начале пути бак полон.
Расстояние от Петербурга до Москвы равно L.
Формат входного файла
Во входном файле сначала указаны числа L, S, N,
после чего перечислено N чисел Di.
Формат выходного файла
Выходной файл должен содержать единственное число - минимальное количество
заправок. Если добраться из Петербурга в Москву невозможно, следует вывести
число -1.
