Функция F(n) для целых неотрицательных n определена так:
F(0)=0, F(1)=1, F(2n)=F(n), F(2n+1)=F(n)+F(n+1).

Для данного N найти и напечатать F(n). Обязательное условие: N столь велико, что недопустимо заводить массив из N чисел.

 

Задача ТРУБОПРОВОД

 

Пусть имеется трубопровод, заданный прямой линией на плоскости Ax+By+C=0 и два города с координатами ( X1, y1 ),(x2,y2). Необходимо соединить эти два города с трубопроводом, истратив при этом наименьшее число труб; указать суммарную длину использованных труб и две точки где происходит соединение трубопровод.
Входные данные:
Целые числа -100000<=A,B,C<=100000 – параметры трубопровода
- 100000<=X1,Y1<=100000 – координаты первого города
-100000<=X2,Y2<=100000 - координаты второго города
Выходные данные:
В первой строке суммарная длина использованных труб

Во второй и третьей соответственно координаты точек соединение трубопроводов

 

Задача ЛАБИРИНТ

В результате рейда налоговой полиции города Обломова в фирму Real в одном из небоскребов был обнаружен секретный уровень, на который вела только одна лестница, а в некоторых местах были аварийные выходы (в виде люков в полу). Согласно агентурным данным, уровень представляет собой прямоугольник из N*M комнат одинакового размера (M комнат вдоль западной стены, N – вдоль северной), причем между некоторыми парами соседних комнат есть двери. Положение осложняется тем, что точные координаты как входа, так и выходов неизвестны.
На разведку были отправлены обезьянки из местного зоопарка. Каждая из них поднималась по лестнице и ходила по уровню, пока не натыкалась на какой-нибудь выход. После этого она спускалась по нему и сообщала свой маршрут начальству. При этом первая обезьянка в начальной точке смотрела на север, а остальные – неизвестно куда. Маршрут каждой обезьянки представлен в виде последовательности символов, представляющих движения и повороты:
F шаг вперед
R поворот направо
L поворот налево
B разворот
W впереди стена, движения не было
E выход, конец маршрута (может идти только непосредственно после F)
Задача состоит в том, чтобы построить план обследованной части уровня, содержащий всю собранную информацию: стенки, проходы, выходы.
Входной файл: Input.txt
Выходной файл: Output.txt

 

Задача МОНЕТЫ

В сундуке у мистера Z имеется N монет. На следующий год мистер Z взял из сундука М монет. В каждый следующий год мистер Z добавлял в сундук столько монет, сколько у него было два года назад. Известно, что на Х-й год в сундуке мистера Z было Y монет. Требуется определить, сколько монет было в сундуке изначально, и сколько монет мистер Z взял на второй год.

Файл Input.txt содержит числа X и Y.

Файл Output.txt содержит числа N и M.