Страница: << 12 13 14 15 16 17 18 >> Отображать по:
#842
Последняя цифра числа Фибоначчи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Последовательность чисел Фибоначчи определяется следующим образом: F0 = F1 = 1,

Fn+1 = Fn+F n-1. Напишите программу для вычисления последней цифры n-го члена последовательности.

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

В единственной строке входных данных записано натуральное число n (1≤n≤1000).

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

Вывести последнюю цифру числа Fn.

Примеры
Входные данные
4
Выходные данные
5
#843
Простая последовательность
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вычислите n-й член последовательности, заданной формулами:

a2n = an ­+ an-1,
a2n+1 = an – an-1,
a0 = a1 = 1.

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

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

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

Вывести одно число an.

Примеры
Входные данные
4
Выходные данные
3
#844
Хитрая последовательность
  
Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача H ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вычислите n-й член последовательности, заданной формулами:

a2n = an ­+ 1 (n>0),
a2n+2 = a2n+1 - an (n>0),
a0=1, a1=1.

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

Вводится натуральное число n, не превосходящее 1000.

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

Выведите ответ к задаче.

Примеры
Входные данные
4
Выходные данные
3
#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
Страница: << 12 13 14 15 16 17 18 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест