Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход |
Артём и Женя играют в следующую игру: они по очереди называют натуральные числа в порядке возрастания, которые в своей двоичной записи не имеют двух единиц подряд. Такими числами, например, будут 1,2,4,5,8 и так далее. А вот числа 3=112, 6=1102 или 7=1112 игроки пропускают.
Артём только что назвал число n. Какое число следует назвать Жене, чтобы продолжить игру?
Единственная строка входных данных содержит натуральное число n. Гарантируется, что в его двоичном представлении нет двух единиц подряд.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long
long
в C++, int64
в Free Pascal, long
в Java.
Выведите одно натуральное число — ответ на вопрос задачи.
1≤n≤1017
В примере дано n=9=10012. Следующее число n+1=10=10102 тоже не имеет двух единиц подряд в своей двоичной записи.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|