Страница: 1 Отображать по:
#860
Путь через горы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x1, y1), (x2, y2),…,(xN, yN), при этом xi<xi+1.

Обычный горный маг находится в точке (x1, y1) и хочет попасть в точку (xN, yN). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в том числе не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов.

Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (xN, yN).

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

Вводится сначала натуральное число N (2≤N≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (x1, y1), (x2, y2),…,(xN, yN). Все координаты – целые числа, не превышающие по модулю 10000, для всех i от 1 до N–1: xi<xi+1.

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

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

Примеры

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

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

5 2 5

0 0

2 2

3 -1

4 1

5 0

6.47871

9 2 3

1 2

2 1

3 3

5 -1

6 2

7 0

8 1

9 0

10 1

14.93498
#862
Перекраска N-угольника
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Разрешается выбрать четырехугольник, в котором ровно одна диагональ, и при этом эта диагональ черного цвета (сам четырехугольник не обязан быть полностью черным) и проделать с ним следующее: заменить диагональ на противоположную (т.е. если сам четырехугольник был ABCD и в нем была диагональ AC, то она меняется на диагональ BD), после чего перекрасить стороны этого четырехугольника и новую диагональ в красный цвет.

Требуется определить, можно ли с помощью таких операций сделать так, чтобы все отрезки (т.е. стороны N-­угольника и изображенные диагонали) стали красными, и не осталось бы ни одного черного отрезка. А если это возможно, то какое минимальное количество операций для этого требуется.

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

Вводится сначала число N (3≤N≤30000). Далее идет описание N–3 проведенных диагоналей. Каждая диагональ описывается двумя натуральными числами — номерами вершин, которые она соединяет. Гарантируется, что проведенные диагонали внутри N-угольника не пересекаются.

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

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

Примеры

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

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

3

–1

4

1 3

1
#863
Заполните массив
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

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

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

Вводится одно натуральное число N (1≤N≤60000).

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

Выведите одно число — искомое количество способов заполнения массива.

Пример

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

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

Комментарии

2

1

Массив можно заполнить единственным способом:

3 2
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест