Задача A. Столкновение шариков ≡

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

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса R метров каждый. В начальный момент времени шарики имеют координаты центров (x1, y1) и (x2, y2) метров, а также проекции скоростей на координатные оси (dx1, dy1) и (dx2, dy2) метров в секунду соответственно.

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

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

Входной файл содержит вещественные числа R x1 y1 dx1 dy1 x2 y2 dx2 dy2.

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

Выходной файл должен содержать вещественное число — время до столкновения, с точностью не менее 3 значащих цифр, либо −1, если столкновения не произойдёт.

Ограничения

1 ≤ R ≤ 1000, −1000 ≤ x1, y1, dx1, dy1, x2, y2, dx2, dy2 ≤ 1000,

(x1 − x2)2 + (y1 − y2)2 > 4 R2

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
0 0 10 0
50 0 -10 0
 
2.4

Задача B. Ближайшая стенка ≡

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

Условие

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

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

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

Входной файл содержит число N за которым идут N троек чисел xi yi di  — координаты i-й точки и расстояние до ближайшей стороны. Все числа целые.

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

Если решения не существует, то в выходной файл должно быть выведено число −1.

Если решение единственное, то в выходной файл должно быть выведено число 1, за которым следуют четыре целых числа x1 y1 x2 y2  — координаты двух противоположных вершин прямоугольника.

Если решений больше одного, то в выходной файл должно быть выведено число 0, за которым следуют четыре целых числа x1 y1 x2 y2  — координаты двух противоположных вершин любого прямоугольника, являющегося решением.

Ограничения

1 ≤ N ≤ 100, 0 ≤ xi, yi, di ≤ 10000

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
50 50 1
 
0 49 49 51 51
2 
2
100 100 3 101 101 90
 
-1

Задача C. Длинный спуск (45 баллов) ≡

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

Условие

Рельеф горного массива представлен матрицей размером NxN, с элементами, задающими высоту участков местности. Лыжник желает найти самый длинный спуск, т.е. такую строго убывающую последовательность соседних по вертикали или горизонтали элементов ai1,j1 > ai1,j1 > … > aiL,jL, что значение L (длина последовательности)  — максимально возможное.

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

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

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

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

Ограничения

1 ≤ N ≤ 1000, 0 ≤ ai,j ≤ 106.

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

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

8 7 3 1

Задача D. Гистограмма ≡

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

Условие

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

По данным целым числам a1, a2, …, aN требуется построить гистограмму. Гистограмма должна состоять из N столбцов, i-й столбец должен изображаться прямоугольником высотой ai и шириной в 3 символа. Столбцы должны быть:

Промежуток между столбцами, а также поля слева, справа и сверху гистограммы должны составлять один символ. В основании (нижней строке) гистограммы промежутки и поля должны изображаться символом '-' (ASCII 45), все остальные промежутки и поля — символом '.' (ASCII 46).

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

Входной файл содержит число N, за которым следуют числа a1, a2, …, aN.

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

Выходной файл должен содержать max(ai) + 3 строк длиной 6 N + 1 символов каждая — изображение гистограммы.

Ограничения

1 ≤ N ≤ 100, 1 ≤ ai ≤ 100

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2
1 6
 
.............
.......+---+.
.......|###|.
.......|###|.
.......|###|.
.......|###|.
.+---+.|###|.
.|###|.|###|.
-+---+-+---+-

Задача E. Разбиение абзаца на строки ≡

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

Условие

Абзац текста состоит из n слов длиной l1, l2, ..., ln (длина слова - число символов в нем). Требуется оптимальным образом разбить его на строки длиной не более M символов. Оптимальность при этом определяется так: посчитаем число "лишних" пробелов в каждой строке и сложим кубы этих чисел для всех строк, кроме последней. Чем больше эта сумма (назовем ее оценочной суммой), тем хуже абзац.

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

В первой строке находятся числа n и M. Далее следует n чисел li.

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

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

Ограничения

1 <= n <= 10000, 1 <= M <= 100000, 1 <= li <= M

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 6 
2 1 2 5
 
72
0.050s 0.007s 15