e-olymp
Yarışlar

KBTU OPEN 2014 Spring

Бинарный пароль

Жомарт использует двоичную строку в качестве пароля для своего компьютера. Теперь он забыл свой старый пароль и хочет получить новый, который является бинарной строкой длины n. Он считает, что пароль достаточно надежный, если он не содержит двух последовательных нулей. Чтобы получить новый пароль, он генерирует случайную двоичную строку длины n. Если он не надежный, то генерирует случайную строку снова и так до тех пор, пока не найдет надежный пароль. Найти ожидаемое число случайных паролей, которое Жомарт должен сгенерировать прежде, чем он найдет надежный.

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

Одно целое число n (1n60).

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

Вывести ожидаемое значение в виде p / q, где p и q взаимно простые натуральные числа.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
1
Çıxış verilənləri #1
1/1
Giriş verilənləri #2
4
Çıxış verilənləri #2
2/1
Mənbə 2014 KBTU Open, Весна Казахстан, Алма-Ата, 20 Апреля, Задача A