Цифры Фибоначчи

по мотивам задачи №2 районного тура IX городской олимпиады школьников Санкт-Петербурга по информатике, 1994 г.
Время на тест — 10 секунд.

Все числа Фибоначчи выписали подряд:

1 1 2 3 5 8 13 21 34 55 ...

По данному числу N найдите в этом ряду N-ю цифру.

Входные данные
Единственное натуральное число N<106.

Выходные данные
Цифра с номером N в этом ряду.

Пример входных данных
10

Пример выходных данных
1

Добавлено: 04 Апреля 2018 11:37:58 Добавил: Андрей Ковальчук

Попытка к бегству

Время на тест - 3 секунды.

Идентификатор для autotest: ol001

Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.

Формат входных данных
Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).

Формат выходных данных
Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.

Пример
Входные данные

3 5
11111
10101
11111
Выходные данные

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

3 5
11101
10101
10111
Выходные данные

impossible

Добавлено: 04 Апреля 2018 11:36:23 Добавил: Андрей Ковальчук

Вводная задача: a+b

Даны два целых числа. Вычислите их сумму.

Входные данные
Программа получает на вход два целых числа, не превышающих по модулю 30000.

Выходные данные
Программа должна вывести сумму исходных чисел.

Пример входных данных
2 2
Пример выходных данных

Добавлено: 04 Апреля 2018 11:35:10 Добавил: Андрей Ковальчук