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

i really can't understand the meaning of the problem.
please help me

I write it for 1013, so I use the Big Integers class.
but actually they are the same problem except for the Scale.

#include <iostream>
#include <cstring>

using namespace std;
////////////////////////////////////////////////////////////////
// this class is not efficient enough, but it's useful!
// BigNum
class BigNum {
    friend ostream& operator<<(ostream &out, const BigNum &rhs);
    friend const BigNum operator+(const BigNum &lhs, const BigNum
&rhs);
    friend const BigNum operator*(const BigNum &lhs, int digit);
public:
    BigNum();
    BigNum(int digit);
    BigNum& operator=(int digit);
    BigNum& operator+=(const BigNum &rhs);
    BigNum& operator*=(int digit);

private:
    static const int MAX_D = 500;
    int numbers[MAX_D];
};
const int BigNum::MAX_D;

BigNum::BigNum()
{
    memset(numbers, 0, sizeof(numbers));
}

BigNum::BigNum(int digit)
{
    memset(numbers, 0, sizeof(numbers));
    int carry = digit;
    for (int i = 0; i < MAX_D && carry != 0; ++i) {
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
}

BigNum& BigNum::operator=(int digit)
{
    int carry = digit;
    for (int i = 0; i < MAX_D && carry != 0; ++i) {
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
    return (*this);
}


BigNum& BigNum::operator+=(const BigNum &rhs)
{
    int carry = 0;
    for (int i = 0; i < MAX_D; ++i) {
        carry += (numbers[i] + rhs.numbers[i]);
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
    return (*this);
}

BigNum& BigNum::operator*=(int digit)
{
    int carry = 0;
    for (int i = 0; i < MAX_D; ++i) {
        carry += (numbers[i] * digit);
        numbers[i] = carry % 10000;
        carry /= 10000;
    }
    return (*this);
}

ostream& operator<<(ostream &out, const BigNum &rhs)
{
    int idx = BigNum::MAX_D - 1;
    for ( ; (idx >= 0) && (rhs.numbers[idx] == 0); --idx) ;
    if (idx < 0) {
        return (out << 0);
    }

    cout << rhs.numbers[idx--];
    for ( ; idx >= 0; --idx) {
        if (rhs.numbers[idx] / 10 == 0)
            cout << "000";
        else if (rhs.numbers[idx] / 100 == 0)
            cout << "00";
        else if (rhs.numbers[idx] / 1000 == 0)
            cout << "0";
        out << rhs.numbers[idx];
    }
    return out;
}

const BigNum operator+(const BigNum &lhs, const BigNum &rhs)
{
    return BigNum(lhs) += rhs;
}

const BigNum operator*(const BigNum &lhs, int digit)
{
    return BigNum(lhs) *= digit;
}

const BigNum operator*(int digit, const BigNum &rhs)
{
    return BigNum(rhs) *= digit;
}

//////////////////////////////////////////////////////////////////////
////

const int MAX_N = 1800;
const int MAX_K = 10;

int N, K;

int main()
{
    cin >> N >> K;
    BigNum Fn1 = 1, Fn2 = K-1, Fn;

    BigNum *pfn1 = &Fn1, *pfn2 = &Fn2, *pfn = &Fn;
    for (int i = 2; i <= N; ++i) {
        *pfn = (K-1) * (*pfn1 + *pfn2);
        pfn1 = pfn2;
        pfn2 = pfn;
        pfn = pfn1;
    }
    cout << (*pfn2) << endl;
    //
    return 0;
}

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.
~~~~~~~~~~~~~
wish it help you
Yours Aidin_n7
(happybird is nice name!)

> I think it's 85096170

     headache

The correct dp fomula should be:

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

so for your case,m[1]=9;m[2]=90;m[3]=9*(9+90)=891.

> var ric,min,max,i,j,k,l,m,n: longint;
>     a:array [1..1000] of longint;
> begin
>   readln (n,k);
>   min:=1;
>   i:=1;
>   while i=n-1 do
>     begin
>       min:=min*10;
>       inc (i);
>     end;
>   max:=k-1;
>   j:=1;
>   while j=n-1 do
>     begin
>       max:=max*10+(k-1);
>       inc (j);
>     end;
>   for i:=min to max do
>     begin
>       ric:=i;
>       l:=0;
>       while ric<>0 do
>         begin
>           inc (l);
>           a[l]:=(ric mod 10);
>           ric:=(ric div 10);
>         end;
>       for j:=1 to l do
>         if a[j]>k-1 then
>           begin
>             a[j]:=0;
>             inc (a[j+1]);
>           end;

>       i:=0;
  {HAve a look at my comment - here is your wrong!!!}
>       for j:=l downto 1 do
>         i:=i*10+a[j];
>       if (i mod 100)<>0 then
>         inc(m);
>     end;
>   writeln (m);
> end.
> Hei, the compiler in timus is Delphi - you can not change the value
of a variable, that controls the cicle, but in PAscal that i spossible
Where you have written "i=0", use another variable..I think, you will
get accepted.
Bye!
from Vlado

> 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[1] = K;
 M[2] = (K-1) * K;

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

 Answer is M[N] = (K-1)*Mas[N-1]

> In this program n is k , k is n
> var
>   l : array [1..1000] of byte;
>   n , k , ss : integer;
>   tot : longint;
> function cf(aa,bb:integer) : longint;
> var
>   temp , ii : longint;
> begin
>   temp := 1;
>   for ii := 1 to bb do
>     temp := temp * aa;
>   cf := temp;
> end;
> procedure try(now,left,source : integer);
> var
>   jj : byte;
> begin
>   if left = 0 then begin
>     tot := tot + cf(n-1,k-source);
>     exit;
>   end;
>   if now > k then exit;
>   if left > k - now+1 then exit;
>   for jj := 0 to 1 do
>     if (jj = 0) or ((jj=1) and (l[now-1]<>1)) then begin
>       l[now] := jj;
>       try(now+1 , left-jj , source);
>     end;
> end;
>
> begin
>   readln(k);
>   readln(n);
>   tot := cf(n-1,k);
>   for ss := 1 to k-1 do
>    try(2,ss,ss);
>   writeln(tot);
> end.
>
1. warning: missing program header;
With header my GPC compiled your program? but ...
2. While trying to solve this problem and checking my e-mail i find
one error: function or procedure can't use name 'try'. When i change
'try' in your program to 'trye', your program solve the problem. Thank
you for your code :-)

> >Why my program get Compilation error?
> >var ric,min,max,i,j,k,l,m,n: longint;
> >    a:array [1..1000] of longint;
> >begin
> >  read (n,k);
> >  min:=1;
> >  for i:=1 to n-1 do
> >    min:=min*10;
> >  max:=k-1;
> >  for i:=1 to n-1 do
> >    max:=max*10+(k-1);
> >  for i:=min to max do
> >    begin
> >      ric:=i;
> >      l:=0;
> >      while ric<>0 do
> >        begin
> >          inc (l);
> >          a[l]:=(ric mod 10);
> >          ric:=(ric div 10);
> >        end;
> >      for j:=1 to l do
> >        if a[j]>k-1 then
> >          begin
> >            a[j]:=0;
> >            inc (a[j+1]);
> >          end;
> >      i:=0;
> >      for j:=l downto 1 do
> >        i:=i*10+a[j];
> >    if (i mod 100)<>0 then
> >      inc(m);
> >    end;
> >  writeln (m);
> >end.
>
1. warning: missing program header; (program my1009)
 GPC have not find anu other errors ...
2. You change i into for.
That's all. By ... Time Limit Exesteeded.

K-based. A number in Base k, a number is in Base K if all his digits
are from 0 to K-1 (10-Based numbers are numbers used by people). The
value is obtained as this:
an*k**n + ... a0*k**0, where an through a0 are the digits from left
to right order and k** is the power operation.
Though is basic for you to know this concepts :)

Yes, may email: raynaldo_adp@yahoo.com

yaeh...
100 - is valid in 10-digit system
55400342 - is valid in 5-digit system...

> So, two successful zeros is zero, and after it another
one zero, example: 1001123.
  There can't be leader zeros, such as 0123; 0123 - is 3-
digits number.

in my oppinion the author mistakook successful with successive

Edited by author 27.02.2009 02:14

Edited by author 27.02.2009 02:14

> I wanna know why i've got wrong answer, anybody help me
> please.
> Try this test