Задача A. Длинный отрезок

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

Условие

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

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

В первой строке входного файла содержится число вершин N . В следующих N строках расположены целочисленные координаты вершин xi, yi, перечисленные в порядке обхода. (При этом у каждой пары соседних вершин либо координаты x, либо координаты y совпадают).

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

Выходной файл должен содержать единственное целое число — длину самого длинного отрезка.

Ограничения

4 ≤ N ≤ 50 0 ≤ 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)

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

Условие

Имеется текст и N слов. Длина текста составляет L символов, длина каждого слова — от 1 до 1000 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из маленьких латинских букв.

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

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

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

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

Ограничения

1 ≤ L ≤ 250000, 1 ≤ N ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
longlongstring
2
short
string
0 1

Задача C. Максимальный перепад

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

Условие

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

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

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

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

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

Выходной файл должен содержать единственное целое число — максимальный перепад высот в этом регионе.

Ограничения

1 ≤ N ≤ 100. Все высоты — целые числа от 0 до 231−1

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

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

Задача D. Линейный чёрный ящик

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

Условие

Имеется линейная функция от двух аргументов 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 — целые

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 -1 -2
2 2 4  3 5 8  7 10 17
-3
  
2
1 3 4
3 4 5
5
3
2 50 60
1 -1 0  2 2 0
0 0

Задача E. Монстры

Автор:?   Ограничение времени:2 сек
Входной файл:monsters.in   Ограничение памяти:200 Мб
Выходной файл:monsters.out  

Условие

В одной секретной лаборатории вывели новый вид маленьких монстров, размером чуть больше суслика. В ходе исследований ученые решили поставить следующий эксперимент. В центре комнаты устанавливается прямоугольный стол, поверхность которого разбита на N x M клеток размера 1x1. В начальный момент времени на некоторых его клетках располагаются монстры, смотрящие параллельно сторонам стола. По команде экспериментатора монстры начинают двигаться по прямой в ту сторону, в которую они смотрят, доходят до края стола и спрыгивают на пол. Там их собирает лаборант Петя и относит в клетку.

Рисунок 1. Монстры на столе для экспериментов

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

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

Первая строка входного файла содержит числа M и N - размеры лабораторного стола. Следующая строка содержит число K - количество монстров. Следующие K строк содержат описания монстров - два целых числа и один символ из множества {N, E, S, W} - начальные координаты и направление соответствующего монстра (соответствие направлений и координат приведено на рисунке 1). Символ отделен от чисел ровно одним пробелом.

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

В выходной файл выведите единственное число - количество клеток стола, на которых побывают монстры.

Ограничения

1 ≤ N, M ≤ 106, 1 ≤ K ≤ 103,

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

Входной файл (monsters.in) Выходной файл (monsters.out)
1
8 5
4
4 4 S
6 2 W
6 3 N
6 4 S
13

Задача F. Муравей и дерево

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

Условие

Муравей находится в лесу с плоской поверхностью почвы в точке с координатами (x1, y1), и направляется в точку (x2, y2). В лесу растёт дерево, основание ствола которого имеет форму круга с центром в точке (xT, yT) и радиусом RT. Дерево, возможно, помешает муравью дойти до цели по прямой. В таком случае ему придётся обойти дерево вокруг ствола.

Требуется определить длину кратчайшего пути для муравья.

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

Входной файл содержит вещественные числа x1 y1 x2 y2 xT yT RT.

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

Выходной файл должен содержать единственное вещественное число — длину кратчайшего пути. Абсолютная ошибка результата не должна превосходить 0.01 (т.е. следует выводить число с точностью не менее 3 знаков после запятой).

Ограничения

Все числа во входном файле находятся в диапазоне от 0 до 1000.
(x1 − xT)2 + (y1 − yT)2 ≥ RT2, (x2 − xT)2 + (y2 − yT)2 ≥ RT2

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

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

Задача G. OLE

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

Условие

Текстовый редактор OLE (One-Line Editor) работает с текстом, состоящим ровно из одной строки строчных латинских букв. Редактор поддерживает следующие команды, длиной в один символ каждая:

Команды, пытающиеся переместить курсор за пределы строки или удалить символ справа от последнего символа строки, игнорируются редактором.

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

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

Входной файл состоит из 3 строк. В первой строке содержится позиция курсора p, (0 — курсор перед первым символом, 1 — после первого перед вторым, и т.д.) во второй строке — начальное состояние строки редактора, в третьей — последовательность команд.

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

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

Ограничения

Длина исходной строки находится в диапазоне от 1 до 1000000 символов. Длина строки команд находится в диапазоне от 1 до 100000 символов.
0 ≤ p ≤ длина исходной строки.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
abc
deLXX
adc
2
0
aa
bbLLx
xbbaa

Задача H. Single-Color Lines

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

Условие

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

По данной позиции сразу после хода игрока определить число удаляемых с поля шариков.

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

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

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

Выходной файл должен содержать единственное целое число — количество удаляемых шариков.

Ограничения

N = 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
..........
....O.....
....OOOOO.
....O.....
..OOOOOO..
.....O....
......O...
.......O..
........O.
..........
15

Задача I. Максимальная тройка

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

Условие

В данном двумерном целочисленном массиве a размером N × N требуется найти три элемента, сумма которых максимальна. При этом первый элемент должен быть соседним по горизонтали или вертикали со вторым, а второй — с третьим.

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

Входной файл содержит число N, за которым следует N2 чисел
a1,1 a1,2a1,N
a2,1 a2,2a2,N
  
aN,1 aN,2aN,N
 — элементы массива.

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

Выходной файл должен содержать единственное число — максимальную сумму. При N = 1 следует вывести единственный элемент матрицы.

Ограничения

1 ≤ N ≤ 2000, 0 ≤ ai,j ≤ 109,

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

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

Задача J. Океанариум

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

Условие

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

Всего у Пети скопилось N таких листков. Требуется написать программу, которая по Петиным записям определит минимально возможное количество рыбок в аквариуме.

Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста, а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.

Рекомендуется рассмотреть частичные решения

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

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

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

Выходной файл должен содержать единственное число — минимальное количество рыбок.

Ограничения

1 ≤ N, Ki ≤ 50, длина названий не превосходит 255 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
2
Carassius auratus
Poecilia reticulata
2
2
3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead
8

Задача K. Числообменник

Автор:IX Всероссийская олимпиада школьников   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Числа от 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 баллов. Естественно, в тестирующей системе частичные решения оцениваться не будут.

Ограничения

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

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

Задача L. Путешествие из Петербурга в Москву

Автор:Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Профессор едет по шоссе из Петербурга в Москву, имея при себе карту с указанием всех N стоящих на шоссе бензоколонок и расстояний Di до них от Петербурга. Известно расстояние S, которое может проехать машина с полностью заправленным баком.
Требуется выяснить, на каких бензоколонках нужно заправляться, чтобы количество заправок было минимально. В начале пути бак полон.
Расстояние от Петербурга до Москвы равно L.

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

Во входном файле сначала указаны числа L, S, N, после чего перечислено N чисел Di.

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

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

Ограничения

0 <= L <= 10^9

0 <= S <= 10^9

0 <= N <= 500000

0 <= Di <= L

Все числа целые.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 60 2
50 30
1
2
100 30 3
60 20 50 
-1

0.471s 0.008s 41