Kiçik Con say sistemlərini öyrənir. Sabit əsaslı say sistemlərini öyrəndikdən sonra Conu daha qeyri-adilərini maraqlandırırdı. Onlar arasında o Fibonaççi sisteminə rast gəldi, ki bu sistemdə də hər bir natural ədəd birmənalı şəkildə iki rəqəmlə: sıfır və birlərlə ifadə olunur. Lakin adi ikilik say sistemindən fərqli olaraq Fibonaççi sistemində iki biri qonşu mövqedə yerləşdirmək olmaz.
İsbat etmək olar ki, əgər Fibonaççi sistemində ədədi varsa, onda onun qiyməti növbəti şəkildədir:
N = a_n·F_n + a_{n-1}·F_{n-1} + ... + a_1·F_1,
burada F_k – F_0 = F_1 = 1, F_i = F_{i-1} + F_{i-2} şəklində verilmiş Fibonaççi ardıcıllığıdır.
Məsələn, ilk natural ədədlər Fibonaççi sistemində növbəti şəkildə ifadə olunurlar:
1 = 1_F
2 = 10_F
3=100_F
4=101_F
5=1000_F
6=1001_F
7=1010_F
Con Fibonaççi sistemində ardıcıl natural ədədləri ehtiva edən (sonsuz uzunluqda hesab olunan) çox böyük sətir yazdı, Məsələn, belə bir sətrin ilk rəqəmləri 110100101100010011010... şəklindədir.
Conu 1 rəqəminin N-ci prefiksdə neçə dəfə rast gəlindiyi maraqlandırır. Xatırladırıq ki, sətrin N-ci prefiksi onun ilk N simvolunu ehtiva edən sətir adlanır.
Conun sətrində N-ci prefiksdə rast gəlinən 1-lərin sayını hesablayan proqramı tərtib edin.
Geriş verilənləri
Yeganə N (0 ≤ N ≤ 10^15) tam ədədi.
Con sətrində N-ci prefiksdəki birlərin sayını verməli.