Рус Uzb Eng

C40C. Sunnat va Alisherning ketma-ketligi
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

Sunnat va Alisher sonli ketma-ketliklarni yoqtirishadi. Bir kuni Alisher va Sunnat birgalikda quyidagicha ketma-ketlikni hosil qilishdi:
0112122012202001112…
Bu ketma-ketlikni hosil qilish qonuniyati quyidagicha edi: Avval 0 yoziladi. Keyin quyidagi amallar takrorlanadi: avval yozilgan ketma-ketlikning o’ng tomonga 0 ni 1 ga, 1 ni 2 ga, 2 ni 0 ga almashtirib yozib qo’yiladi, ya’ni: 0 -> 01 -> 0112 -> 01121220 -> …
Bu ketma-ketlikni ko’rib Sunnat bu ketma-ketlikning n-elementi qanday son bo’lishiga qiziqdi va Alisherdan buni so’radi. Alisher esa buni tezda javobini topdi. Siz ham n-o’rinda turgan elementni topa oladigan dastur tuza olasizmi?

Входные данные:
Bitta natural n(n ≤ 109) soni. Aniqlanishi kerak bo’lgan element nomeri.

Выходные данные:
Kerma-ketlikning n-o’rinda turganini aniqlang.

Пример ввода Пример вывода
1
17
0
1
Область:
Источник задачи: Abdukarimov Sirojiddin, Ismoilov Isfandiyor, Islomov Nodirbek

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.