NEERC (29 იანვრის წერა)
ავტორი tsotne
III ამოცანის გარჩევა (fibseq)
წერილები: 83
tsotne says:
5 თებერვალი 2012, 4:11
ამოცანის პირობა
ტესტები

პირველ რიგში, შევნიშნოთ, რომ რიცხვი ფიბონაჩის სისტემაში არ შეიცავს ორ ერთმანეთის გვერდით მდგარ 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] საზღვრებს სცდება.
გთხოვთ გაიარეთ ავტორიზაცია კომენტარის გამოსაქვეყნებლად.
სიახლეები Facebook-ზე
მომავალი ღონისძიებები
მომავალი ღონისძიებების სია ცარიელია.
ღონისძიებების კალენდარი
მხარდამჭერები






ახალი კომენტარები
Dixtosa Episode II - Analysis...
Eშისაიდან მოვიდა 3**13?ისე 4 * 52 * 3**13 = 331M+ ...
Quick GeOlymp 2013 - ფინალური ეპიზოდი იწყება...
Upsolving ჩაირთო...
saba_tavdgiridze GeOlymp 2013 - ფინალური ეპიზოდი იწყება...
აღარ მინდა.:)...
saba_tavdgiridze GeOlymp 2013 - ფინალური ეპიზოდი იწყება...
B ამოცანის 17 ტესტს ვერ მიმანიშნებთ?...
tornike5 GeOlymp 2013 - ფინალის შესახებ...
ვაპირებდი იგივე მეკითხა მარა მეგონა უეჭველი იქნება...
giorgi123 GeOlymp 2013 - ფინალის შესახებ...
მადლობა.შარშან ფინალში ამოცანების ყურებით ვიფარგლე...
Elle GeOlymp 2013 - ფინალის შესახებ...
შარშან ფინალს codeblocks-ით წერდით?დავაყენეთ codeb...