Трипростые числа

[ZakharovRoman]

помогите разобраться в задаче вот ссылка
http://acm.dvpion.ru/index.asp?main=task&id_task=335
вот условие:
Трипростые числа
(Время: 1 сек. Память: 16 Мб Сложность: 40%)

Будем называть натуральное число трипростым, если в нем любые подряд идущие 3 цифры образуют трехзначное простое число.

Требуется найти количество N-значных трипростых чисел.
Входные данные

Входной файл INPUT.TXT содержит натуральное число N (3 ≤ N ≤ 10000).
Выходные данные

Выходной файл OUTPUT.TXT должен содержать количество N-значных трипростых чисел, которое следует вывести по модулю 10^9+9.
INPUT.TXT
4
OUTPUT.TXT
204

ну как то ДП не очень чувствуется понятно что надо завести отдельный массив под все 3-х значные простые числа и ответ при 3-и будет как раз равен количеству элементов в нём, но как дальше..
пусть у нас N=4 тогда имеем abcd- это 4-х значное число и я думаю вот как надо пробежаться по всем 3-кам ну abc простым числам в том числе и тогда последняя чифра будет любая от 0 до 9, но если двигаться таким образом то задача становится не на ДП а комбинаторной число размещений трипростых чисел, хотя решается ДП подскажите плиз. что не так

состояние динамики должно быть dp[n][d1][d2] - кол-во трипростых чисел длиною n таких что последняя цифра равна d2 а предпоследняя d1.

dp[1][i][j] = 0
dp[2][i][i] = 0

dp[n][i][j] = sum(k=1..9) dp[n-1][k][i], если kij - простое трехциферное число

я реализовал так как вы сказали, но почему то получаю вр5 на 5-ом тесте..
даже и не знаю где может быть ошибка решение вроде бы правильное..
подскажите пожалуйста что не так сделал..
вот код ну как я реализовал

Const Maxn=10010;

var a:array[0..maxn,0..9,0..9]of integer;
    i,j,k,t,temp,n:integer;
    ans:Int64;

function eq(t1,t2,t3:integer):boolean;
var i,v:integer;
begin
  result:=false;
  if t1=0 then exit;
  v:=100*t1+10*t2+t3;
  for i:=2 to Floor(0.5+Sqrt(v*1.0)) do
    if v mod i=0 then exit;
  result:=true;
end;

begin
  Assign(Input,'INPUT.TXT');reset(Input);
  Assign(Output,'OUTPUT.TXT');rewrite(Output);
  readln(n);
  fillchar(a,sizeof(a),0);
  ans:=0;
    for i:=0 to 9 do
      for j:=0 to 9 do begin
        temp:=0;
        for k:=0 to 9 do begin
          if eq(k,i,j) then temp:=temp+1;
        end;
        a[3,i,j]:=a[3,i,j]+temp;
      end;


  for t:=4 to n do begin
    for i:=0 to 9 do
      for j:=0 to 9 do begin
        temp:=0;
        for k:=0 to 9 do begin
          if eq(k,i,j) then temp:=temp+a[t-1,k,i]
        end;
        a[t,i,j]:=temp;
      end;
  end;

  for i:=0 to 9 do
    for j:=0 to 9 do
      ans:=ans+a[n,i,j];
  writeln(ans);
  close(Input);
  close(Output);
  { TODO -oUser -cConsole Main : Insert code here }
end.

[cmd]

"Выходной файл OUTPUT.TXT должен содержать количество N-значных трипростых чисел, которое следует вывести по модулю 10^9+9. "

Я думаю из-за того, что ты не учел условия задачи, что ответ нужно вывести(считать) по модулю 10^9+9

я изменил сторочку вывода
writeln(ans mod (1000000009));
да я это не заметил совсем, но к сожалению не из-за этого всё равно вр5(((

[cmd]

А ты учитываешь, что "подряд идущие 3 цифры образуют трехзначное простое число. " -- именно трехзначное, т.е. например 031 -- это не трехзначное ?

конечно вот в этой процедурке

function eq(t1,t2,t3:integer):boolean;
var i,v:integer;
begin
  result:=false;
  if t1=0 then exit;
  v:=100*t1+10*t2+t3;
  for i:=2 to Floor(0.5+Sqrt(v*1.0)) do
    if v mod i=0 then exit;
  result:=true;
end;

[cmd]

Все косяк у тебя с тем что ответ тебе нужно выдать по модулю 10^9 + 9.
добавил в твое решение mod 1000000009 и получил TLE 8

writeln(ans mod 1000000009) не достаточно. Ибо у тебя может быть переполнение где-нибудь (за int64 выйти за границы), поэтому желательно после каждого действий брать по модулю 1000000009

[cmd]

А что бы TLE избежать -- вычисли все простые трехзначные числа и в булевском массиве prime[i] := true сделай для каждого i - простого трехзначного числа.

большое спасибо разобрался в задаче сдал))