Описание
Шахматная ассоциация решила предоставить своим сотрудникам телефонные номера, которые бы набирались на кнопочном телефоне ходом коня (шахматный конь перемещается по схеме начертания русской буквы "Г". Так с номера 4 (рис.1) можно за один ход попасть на номер 0, 3 или 9


     Рис.1

Например, ходом коня набирается телефон 340-49-27 (рис.1). При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8

Задача
Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня


Входные данные
Во входном файле записано целое число N (1N100)

Выходные данные
Выведите в выходной файл искомое количество телефонных номеров


Нап
ример:

KNIGHT.IN
2

KNIGHT.OUT
16




Идеи
Динамическое программирование, длинная арифметика

Комментарии
Пусть F(k,d) означает количество набираемых ходом коня последовательностей цифр длины k, первая из которых равна d. Выпишите рекуррентные соотношения для чисел F(k,d). Например F(k+1,6)=F(k,0)+F(k,1)+F(k,7). Ответом на задачу будет являться сумма чисел F(N,d), взятая по всем цифрам d, отличным от 0 и 8




Решение

{$A+,B-,D+,E+,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X+,Y+} 
{$M 65520,0,655360} 
 
program knight; 
type long=array [0..30] of integer; 
     fig=array [0..9] of long; 
var a,b:fig; 
    i,n:integer; 
 
function max (a,b:integer):integer; 
begin 
if a>b then max:=a else max:=b; 
end
 
procedure addlong (var a,b:long); 
var i,z,cy:integer; 
begin 
z:=max (a[0],b[0]); 
cy:=0; 
for i:=1 to z+1 do 
  begin 
    inc (cy,a[i]+b[i]); 
    if cy>9999 then begin a[i]:=cy-10000;cy:=1;end 
    else begin a[i]:=cy;cy:=0;end
  end
if a[z+1]>0 then a[0]:=z+1 else a[0]:=z; 
end
 
procedure xwrite (a:integer); 
var s:string [4]; 
begin 
str (a,s); 
while length (s)<4 do s:='0'+s; 
write (s); 
end
 
procedure writelong (var a:long); 
var i:integer; 
begin 
write (a[a[0]]); 
for i:=a[0]-1 downto 1 do 
  xwrite (a[i]); 
end
 
begin 
assign (input,'knight.in'); 
reset (input); 
readln (n); 
for i:=0 to 9 do 
  begin 
    a[i][0]:=1; 
    a[i][1]:=1; 
  end
a[0][1]:=0; 
a[8][1]:=0; 
for i:=2 to n do                   (* [7] [8] [9] *) 
  begin                            (* [4] [5] [6] *) 
    b[0]:=a[4];         {4+6}      (* [1] [2] [3] *) 
    addlong (b[0],a[6]);           (*     [0]     *) 
    b[1]:=a[6];         {6+8} 
    addlong (b[1],a[8]); 
    b[2]:=a[7];         {7+9} 
    addlong (b[2],a[9]); 
    b[3]:=a[4];         {4+8} 
    addlong (b[3],a[8]); 
    b[4]:=a[0];         {0+3+9} 
    addlong (b[4],a[3]); 
    addlong (b[4],a[9]); 
    b[5][0]:=1;         {-} 
    b[5][1]:=0; 
    b[6]:=a[0];         {0+1+7} 
    addlong (b[6],a[1]); 
    addlong (b[6],a[7]); 
    b[7]:=a[2];         {2+6} 
    addlong (b[7],a[6]); 
    b[8]:=a[1];         {1+3} 
    addlong (b[8],a[3]); 
    b[9]:=a[2];         {2+4} 
    addlong (b[9],a[4]); 
    a:=b; 
  end
for i:=1 to 9 do 
  addlong (a[0],a[i]); 
assign (output,'knight.out'); 
rewrite (output); 
writelong (a[0]); 
close (output); 
end.


© Особенности национальных задач по информатике