eolymp
bolt
Try our new interface for solving problems
Məsələlər

И снова 3x+1

И снова 3x+1

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Проблема 3x+1 хорошо известна в математических кругах и понятна даже школьнику начальных классов. Возьмем любое натуральное число. Если оно четное, то разделим его на 2, а если нечетное, то умножим на 3 и прибавим 1. С вновь полученным числом поступим аналогично. И так далее...

Например, взяв число 5 получим цепочку:

5 (*3+1) 16 (/2) 8 (/2) 4 (/2) 2 (/2) 1 (*3+1) 4... цикл замкнулся (1-4-2).

И какое бы натуральное число мы не взяли - в конечном итоге преобразования всегда сведутся к 1. Строго говоря, данное утверждение доказано только для чисел не превосходящих 19-ти разрядные числа, однако в рамках данной задачи нет необходимости производить его строгое математическое доказательство.

Все, что от Вас требуется в этот раз - это рассчитать сколько существует натуральных чисел, начиная с которых при преобразованиях до 1 будут получаться цепочки длиной N. При этом цикл 1-4-2 в цепочки входить не должен, то есть цепочка 1-4-2-1 не является корректной цепочкой длиной 4.

Указанная выше цепочка 5-16-8-4-2-1 имеет длину 5.

Giriş verilənləri

Единственная строка входных данных содержит одно натуральное число N (1N62).

Çıxış verilənləri

Единственная строка выходных данных должна содержать одно натуральное число - количество чисел, дающих цепочки длиной N.

Nümunə

Giriş verilənləri #1
1
Çıxış verilənləri #1
1
Müəllif Второв Алексей
Mənbə Osipovsky Cup - 2013