Последовательность Кеане
(Время: 1 сек. Память: 16 Мб Сложность: 57%)
Бесконечная последовательность битов, предложенная Кеане, равна 001001110001001110110110001… и формируется следующим алгоритмом: вначале записывается 0, потом 001, далее 001001110, то есть, для получения следующего члена, предыдущий записывается дважды, а справа приписывается его отрицание. Элементы этого ряда являются начальными подпоследовательностями Кеане.
Требуется написать программу, которая по заданному n определит N-й бит этой последовательности.
Входные данные
Входной файл INPUT.TXT содержит число N (N ≤ 10200).
Выходные данные
В выходной файл OUTPUT.TXT должен содержать найденный бит.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 | 1 |
| 2 | 18 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
