ACM '99, Southeastern regionals

Problem B

Fibonacci Strings

Input File: B.DAT

Program Source File: B.PAS or B.C or B.CPP

A Fibonacci string F(n) for a natural number n is defined as:

F(1) = 'A'

F(2) = 'B'

F(n) = F(n-1) + F(n-2), n>2

where + denotes string concatenation.

Write a program that counts occurrences of a given string S consisting of characters 'A' and 'B' only, in the given Fibonacci string F(n). The maximum length of S is 25, the maximum value of the given n is 35, and the result has up to 8 digits.

The input file contains a sequence of input data sets. Each data set is given in one line, consisting of an integer n and a string S. The input should be read from the file. The input is guaranteed to be correct.

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the number of occurrences of S in F(n)).

Example:

Input Output

1 A 1

2 ABA 0

6 AB 3

8 BBABAB 3

35 BBABAB 1346268

 

 

Reshenie na zadachata:

Nai napred vijdame che zadachata niama da varvi s brute force (toest ne bi triabvalo makar che vse pak dokolkoto razbrah e tragnala I s brute) I zapochvame da tarsim rekurenciite. Parvata rekurencia e ochevidna I sledva ot samata definicia na zadachata I Fibonachi I tia e:

G(S,n) = G(S,n-1) + G(S,n-2) , kadeto G(S,n) e funkciata vrashtashta broia na povtoreniata na stringa S vav redicata generirana sas F(n). Kam tazi rekurencia obache sledva da pribavim broia na povtoreniata, koito se poluchavat pri concatenaciata na stringovete generirani s F(n-1) I F(n-2). Kak da gi namerim ?

Ami zabeliazva se che v konkretnia primer ima edin vid "rekurencia v rekurenciata" – toest tozi broi povtorenia pri concatenaciata ot svoia strana se povtariat prez edno. Kazano po nauchno – podstringa koito sadarja tezi povtorenia pri concatenaciata e obrazuvam ot nai desnite (k-1) elementa na F(n-1) I nai levite (k-1) elementa na F(n-2), kadeto k e daljinata na stringa koito tarsim. Tezi 2*(k-1) elementa obrazuvat string koito rekurentno se povtaria prez edna stapka, ili da obobshtim:

Ako iskame da nemerim broia na dopalnitelnite povtorenia pri koncatenaciata na F(34) = F(33) + F(32), nie mojem da sme sigurne che te shte sa ravni na tezi dopalnitelni simvoli pri F(32), pri F(30) I t.n. dokato stignem do niakakvo razumno nivo na koeto mojem da gi smetnem, v sluchaia sas tazi zadacha F(10). Sashtoto vaji I za nechetnite chisla, samo che togava shte stignem do F(9) (F(11) sashto e dostatachno razumno, nego sam izpolzval v programata).

Konkretno za tazi zadacha nai dobre e da si generirame parvite 13 fibonachite (zashtoto F(13) < 255) I se sabira vav tipa string I ako srtinga kogoto matchvame e po malak ot 13 napravo bruteforcevame. Ako ne, generirame chislata delta_odd I delta_even , koito sa imenno tezi dopalnitelni povtorenie pri konkatenaciata, za nizovete F(9) I F(10) I si gi polzvame po natatyka v edno prosto cikalche da generirame ostanalite.

Slojnosta na algoritama si e mai savsem lineina. Abe vsichko ok, samo deto ne uspiahme da ia reshim tam na miasto, to I ne samo neia mai. Opitahme se da prepishem ot vas ma I tova ne stana. Abe ujas, to nie ako ne prepishem nishto ne moim napraim.

Eto go I koda (raboti pone na testovete na jurito hehe ).

var

F : text;

Fib : array[1..13] of string;

FibGen : array[10..35] of longint;

function Brute(size : integer; S : string) : longint;

var i : integer;

counter : longint;

begin

counter := 0;

for i := 1 to length(Fib[size]) do

if S = copy(Fib[size],i,length(S)) then inc(counter);

Brute := counter;

end;

var

delta_even, delta_odd,a,b,c,d : longint;

i,size : integer;

S : string;

begin

Fib[1] := 'A'; Fib[2] := 'B';

for i := 3 to 13 do

Fib[i] := Fib[i-1] + Fib[i-2];

assign(F,'B.DAT'); reset(F);

while not EOF(F) do

begin

read(F,size);

readln(F,S); while ((S[1] <> 'A') and (S[1] <> 'B')) do delete(S,1,1);

if (size <= 13) then

begin

writeln(Brute(size,S));

end

else

begin

a := Brute(10,S); b := Brute(11,S);

c := Brute(12,S); d := Brute(13,S);

FibGen[10] := a; FibGen[11] := b;

FibGen[12] := c; FibGen[13] := d;

delta_even := c - (a + b);

delta_odd := d - (b + c);

for i := 14 to size do

begin

FibGen[i] := FibGen[i-1] + FibGen[i-2];

if odd(i) then Inc(FibGen[i],delta_odd)

else Inc(FibGen[i],delta_even);

end;

writeln(FibGen[size]);

end;

end;

close(F);

end.