ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1009. K-based Numbers

Posted by Jordan 18 Feb 2002 08:33
Sos!I really don't know why i always get this reply!Could anybody
point out my fault or give me some testdata?Thanks
Re: Wrong Answer Again and Again
Posted by Anton Lokhov 19 Feb 2002 02:46
> Sos!I really don't know why i always get this reply!Could anybody
> point out my fault or give me some testdata?Thanks
Use DP:
M = K;
M = (K-1) * K;

M[K] = (K-1) * ( Mas[K-2] + Mas[K-1] ); k<N;

I didn't understand that formula, but here is my program. It uses a different one.
Posted by Costel::icerapper@k.ro 21 Feb 2002 01:23
so, A(i)=is the number of valid numbers where the I-th digit is 0
and,B(i)=is the number of valid numbers where the
I-th digit is IN [1..9]

program timus1009;
const
maxn=20;
type
ta=array[0..maxn]of integer;
var
n,k:integer;
A,B:ta;
i:integer;

begin
while not seekeof do begin
A:=0;
B:=k-1;
for i:=2 to n do
begin
A[i]:=B[i-1];
B[i]:=(k-1)*(A[i-1]+B[i-1]);
end;
writeln(A[n]+B[n]);
end;
end.
Re: I didn't understand that formula, but here is my program. It uses a different one.
Posted by Dr Zhihua Lai 29 Aug 2011 01:25
:)
this is the same thing :)
if you replace A[i-1] = B[i-2] you will get
B[i] = (k - 1) * (B[i - 2] + B[i - 1])