eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

АнтиГрей

АнтиГрей

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Як відомо, англійський математик Френк Грей (Franc Gray) запропонував цікаву формулу, яка дозволяє за порядковим номером визначити відповідний член послідовності, яка має ту властивість, що двійкове подання кожного наступного члена відрізняється рівно в одному від двійкового подання попереднього. Якщо позначити i-ий розряд двійкового подання порядкового номеру коду Грея через N_i, а через G_i - i-ий разряд двійкового подання відповідного коду Грея, то має місце формула:

G_i = N_i^N_{i+1}

Відмітимо, що розряди вважаються занумерованими зправа наліво (з нуля). Функція на мові C, яка реалізує отримання коду Грея для заданого цілого параметра, дорівнює номеру цього коду буде виглядати так:

unsigned long long G(long long N)

{ return V ^ V » 1;}

Послідовність (G_i) будемо називати послідовністю Грея. Наша задача, за заданим кодом Грея отримати число, якому цей код відповідає (тобто номер члена послідовності Грея, рівного цьому коду).

Вхідні дані

Файл складається з єдиного рядка - коду Грея, заданого у шістнадцятковому виді. Довжина заданого рядка не перевищує 200 000, у якості цифр, значення яких перевищують 9, взяті перші англійські літери верхнього регістру.

Вихідні дані

Вихідний файл складається з єдиного рядка - шістнадцяткового значення числа, код Грея якого було задано у вхідному файлі. У результата не повинно бути ведучих нулів, в якості цифр, значення яких перевищують 9, слід взяти перші англійські літери верхнього регістру.

Приклад

Вхідні дані #1
3F
Вихідні дані #1
2A
Автор Т.Заркуа
Джерело Зимові збори у Харкові 2010 День 7