1009 Timus answer/Решение задачи 1009


№1009
http://acm.timus.ru/problem.aspx?space=1&num=1009
ЖМИ ДАЛЕЕ>>>


РЕШЕНИЕ:

PASCAL


var
   A: array [0..18] of LongInt;
   N, K, I: LongInt;
begin
     readLn (N);
     readLn (K);
     A[1] := K - 1;
     A[0] := 0;
     for I := 2 to N do
         begin
              A[I] := A[I-2] * (K - 1) + A[I-1] * (K - 1);
         end;
     writeLn (A[N] + A[N-1]);
end.


или


Var
N,K: LongInt;

Function RecZero(J:LongInt): LongInt; forward;
Function RecDigit(J:LongInt): LongInt; forward;

Function RecZero(J:LongInt): LongInt;
Begin
If J=1 then begin
RecZero:=K-1;
Exit;
End;
RecZero:=(K-1)*RecDigit(J-1);
End;
Function RecDigit(J:LongInt): LongInt;
Begin
If j=1 then begin
RecDigit:=K;
Exit;
End;
RecDigit:=(K-1)*RecDigit(J-1)+RecZero(J-1);
End;
Begin
Readln(N,K);
Writeln(RecZero(N));
End.

1009. K-ичные числа

Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
Рассмотрим N-значные числа в системе счисления с основанием K. Будем считать число правильным, если его K-ичная запись не содержит двух подряд идущих нулей. Например:
  • 1010230 — правильное 7-значное число;
  • 1000198 не является правильным числом;
  • 0001235 — не 7-значное, а 4-значное число.
Даны числа N и K, вычислите количество правильных K-ичных чисел, состоящих из N цифр.
Ограничения: 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.

Исходные данные

Числа N и K в десятичной записи, разделенные переводом строки.

Результат

Искомое количество в десятичной записи.

Пример

исходные данныерезультат
2
10

90
Источник задачи: Чемпионат УрГУ 1997
Ярлыки: