ამოცანის პირობა
ტესტები

პირველ რიგში, შევნიშნოთ, რომ რიცხვი ფიბონაჩის სისტემაში არ შეიცავს ორ ერთმანეთის გვერდით მდგარ 1-იანს (ეს დაამტკიცეთ). ანუ, თუ იმ მიმდევრობაში გვეხვდება "11", ე.ი. პირველი ერთიანი არის ერთი რიცხვის დასასრული, მეორე 1-იანი კი შემდეგი რიცხვის დასაწყისი. საბოლოო ჯამში, უნდა იპოვოთ პირველ N სიმბოლოში (სიმბოლოში და არა რიცხვში!) რამდენი რიცხვი შედის, რომელიც ბოლოვდება 1-იანით (მისი შემდეგი რიცხვი აუცილებლად 1-იანით დაიწყება)


დავითვალოთ ფიბონაჩის მიმდევრობა:

F[0] = 1
F[1] = 1
F[2] = 2
F[3] = 3
F[4] = 5
F[5] = 8
F[6] = 13
F[7] = 21
...

ჩვენ ვიცით, რომ "11" შეგვხვდება მხოლოდ ერთი რიცხვის დასასრულს და მეორე რიცხვის დაწყებისას. რადგან ყოველი რიცხვი 1-იანით იწყება, საჭიროა მხოლოდ გავიგოთ რომელი რიცხვები ბოლოვდება 1-იანით ფიბონაჩის სისტემაში. შემდეგ კი დავითვალოთ პირველ N სიმბოლოში რამდენი ასეთი რიცხვი შეგვხვდა.

პირველი და ყველაზე მარტივი ნაბიჯი არის იმის გარკვევა, თუ რამდენ რიცხვს მოიცავს პირველი N სიმბოლო სრულად. (შემდეგ, უნდა ვიპოვოთ პირველ n რიცხვში რამდენი ბოლოვდება 1იანით)

პირველი ნაბიჯის ამოსახსნელად საკმარისია შევნიშნოთ, რომ:
თავიდან 1 რიცხვია 1 ნიშნა.
შემდეგ, 1 რიცხვია 2 ნიშნა.
შემდეგ, 2 რიცხვია 3 ნიშნა.
შემდეგ, 3 რიცხვია 4 ნიშნა.
შემდეგ, 5 რიცხვია 5 ნიშნა.
შემდეგ, 8 რიცხვია 6 ნიშნა.
....
n ნიშნა არის F[n-1] რიცხვი.
ამიტომ, N-ს ვაკლებთ i*F[i-1] სადაც i იცვლება 1-დან ზევით მანამ, სანამ N>=i*F[i-1]. და ციკლის ყოველ იტერაციაზე პასუხს ვუმატებთ F[i-1]-ს, რადგან ვიცით, რომ მაგდენი რიცხვი მოთავსდება პირველ N სიმბოლოში. როდესაც აღმოჩნდება, რომ N<i*F[i-1], მივიღებთ რომ კიდევ N/i რაოდენობის რიცხვი მოთავსდება პირველ N სიმბოლოში. თუმცა, ბოლო რიცხვი, რომელიც ამ მიმდევრობაში შედის ვერ დაამყარებს "11" კავშირს შემდეგ რიცხვთან, თუ შემდეგი რიცხვი არ არის დაწყებული (მაგალითად: 1 10 101 - ბოლოს კი მთავრდება 1იანით, მაგრამ შემდეგი რიცხვი არაა დაწყებული). ამიტომ, უნდა განვიხილოთ პირველ N-1 სიმბოლოში რამდენი რიცხვი შედის სრულად.

N = n-1; // n სიმბოლოების რაოდენობა
m = 0; // m რამდენი რიცხვი ჩაეტევა
i = 0; // ციკლისათვის საჭირო ცვლადი
while(N/(i+1)>=a[i])
{
N-=a[i]*(i+1);
m+=a[i];
i++;
}
m+=N/(i+1);

შევნიშნოთ, რომ ფიბონაჩის სისტემაში:

3 ნიშნა რიცხვები სულ F[2]-ია და მათგან F[1] ბოლოვდება 0-ით, ხოლო F[0] 1-ით.
4 ნიშნა რიცხვები სულ F[3]-ია და მათგან F[2] ბოლოვდება 0-ით, ხოლო F[1] 1-ით.
5 ნიშნა რიცხვები სულ F[4]-ია და მათგან F[3] ბოლოვდება 0-ით, ხოლო F[2] 1-ით.
...
n ნიშნა რიცხვები სულ F[n-1]-ია და მათგან F[n-2] ბოლოვდება 0-ით, ხოლო F[n-3] 1-ით. (როცა n>=3)
გამონაკლისია 2 ნიშნა და 1 ნიშნა რიცხვების შემთხვევა: 2 ნიშნებში 1 რიცხვია და ისიც 0-ით ბოლოვდება, ხოლო 1 ნიშნებში 1 რიცხვია და 1ით ბოლოვდება.

შემოვიღოთ ფუნქცია, რომელიც გვიბრუნებს t ნიშნა რიცხვებში რამდენი ბოლოვდება 1-ით.

long long f(int t)
{
if(t< 1) return 0;
if(t==1) return 1;
if(t==2) return 0;
return F[t-3];
}

შემოვიღოთ g ფუნქცია, რომელიც დაგვიბრუნებს რამდენი რიცხვი ბოლოვდება 1-ით პირველ n რიცხვში დაწყებული პირველი t ნიშნა რიცხვიდან რიცხვის ფიბონაჩის ჩაწერის სისტემაში: long long g(int t,long long n)
მაშინ, პასუხს დაგვიბრუნებს g(1,m). (სადაც m არის პასუხი მიღებული წინა კოდში).

g(t,n) ფუნქციის იმპლემენტაცია შემდეგნაირია:

long long g(int t,long long n)
{
if(n<=0) return 0;
if(F[t-1] <= n)
return f(t) + g(t+1,n-F[t-1]);

long long x;
if(t>1)
x = F[t-2]; else
x = 1;
return g(1,min(n,x)-1) + g(t-2,max(n-x,0LL));
}

ჯერჯერობით x-ს არ მიაქციოთ ყურადღება და ბოლო ხუთი ხაზის მაგივრად განიხილეთ: return g(1,min(n,F[t-2])-1) g(t-2,max(n-F[t-2],0LL));

პირველ სამ ხაზში განხილულია ვარიანტი, როცა n>=F[t-1], მაშინ ეს ფუნქცია ყველა t ნიშნა რიცხვს მოიცავს. მაშინ, პასუხია f(t) g(t 1,n-F[t-1]).

თუ n100000
100001
100010
100100
100101

101000
101001
101010

პირველი F[t-2] რიცხვი დავაჯგუფოთ ერთად და ბოლო F[t-3] რიცხვი ერთად, როგორც სურათზეა ნაჩვენები. შევნიშნოთ, რომ მეორე ჯგუფის პირველი რიცხვი პირველია, რომელშიც მარცხნიდან მესამე ციფრი 1 ხდება. დავყოთ ამოცანა 2 ვარიანტად: როცა n<=F[t-2] და როცა n>F[t-2]. მე მეორე, უფრო რთულ ვარიანტს განვიხილავ და მარტივს თქვენ თვითონაც მიხვდებით.
თუ n>F[t-2], მაშინ პირველი ჯგუფის ყველა რიცხვს შეიცავს. მაშინ ყველა რიცხვს ჩამოვაშოროთ ყველაზე მარცხენა 1-იანი (ეს არ შეცვლის 1იანებით დაბოლოებულ რიცხვთა რაოდენობას). მივიღებთ 0, 1, 10, 100, 101 ამ მაგალითში. ისე კი, 0, 1, 10, ... F[t-2]-1. ანუ პასუხს ემატება g(1,F[t-2]-1). მეორე ჯგუფში, სულ n-F[t-2] ელემენს ვიღებთ. მათაც, ჩამოვაშოროთ ყველაზე მარცხენა 1იანი და ისე დავითვალოთ რამდენი ბოლოვდება 1ით. მაგალითში მივიღებთ 1000, 1001, 1010. ზოგადად კი პირველი t-2 ნიშნა რიცხვიდა დაწყებული n-F[t-2] რიცხვი. ანუ პასუხს ემატება g(t-2,n-F[t-2]).
თუ n<=F[t-2] პასუხია g(1,n-1).

return g(1,min(n,F[t-2])-1) g(t-2,max(n-F[t-2],0LL));
ეს ფორმულა ორივე ვარიანტს აერთიანებს.
x კი იმ ერთადერთი მიზნითაა შემოღებული, რომ თუ t = 1, F[t-2] საზღვრებს სცდება.