|
|
back to boardFilippov Nickolas SSAU#2's AC program is HERE! program kbasednumbers;
var i:integer;
a:array[0..16] of longint;
n,k:word;
begin
read(n);
read(k);
a[0]:=1;
a[1]:=k-1;
for i:=2 to n do
a[i]:=(k-1)*(a[i-1]+a[i-2]);
writeln(a[n]);
end. Mine is better? isnt it? var
n,k,i :byte;
p1,p2,p3 :longint;
begin
read(n,k);
p2:=1; p1:=k;
for i:=1 to n-2 do begin
p3:=p1;
p1:=(k-1)*(p1+p2);
p2:=p3;
end;
writeln((k-1)*p1);
end.
Aidin_n7@hotmail.com what does the problem mean? i really can't understand the meaning of the problem.
please help me Re: what does the problem mean? Posted by ntmquan 20 Dec 2005 17:38 Let's consider:
f(n, 0) - an amount of valid n digits , k-based number.
f(n, 0) - an amount of valid n digits, k-based number which ends with 0.
f(n, 1) - an amount of valid n digits, k- based number which ends with 1,2,..,k - 1.
We have:
f(n, 1) = (k - 1)f(n - 1)
f(n, 0) = f(n - 1, 1) = (k - 1)f(n -2)
So, f(n) = f(n, 1) + f(n, 0) = (k -1)( f(n - 1) + f(n - 2))
Edited by author 20.12.2005 17:39 Re: what does the problem mean? I get AC f(t)=f(t-1)*(k-1)+f(t-2)*(k-1); thanks Let's consider:
f(n, 0) - an amount of valid n digits , k-based number.
f(n, 0) - an amount of valid n digits, k-based number which ends with 0.
f(n, 1) - an amount of valid n digits, k- based number which ends with 1,2,..,k - 1.
We have:
f(n, 1) = (k - 1)f(n - 1)
f(n, 0) = f(n - 1, 1) = (k - 1)f(n -2)
So, f(n) = f(n, 1) + f(n, 0) = (k -1)( f(n - 1) + f(n - 2))
Edited by author 20.12.2005 17:39 Re: what does the problem mean? It's so simple! And I'm so stupid, that didn't guess it myself. :( |
|
|
