Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 22.07.2008, 04:25
Новичок

Отправить личное сообщение для ZakharovRoman Посмотреть профиль Найти все сообщения от ZakharovRoman
 
Регистрация: 19.01.2007
Сообщений: 10

Трипростые числа
помогите разобраться в задаче вот ссылка
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, но если двигаться таким образом то задача становится не на ДП а комбинаторной число размещений трипростых чисел, хотя решается ДП подскажите плиз. что не так
  #2  
Старый 28.07.2008, 19:31
гость

 
Сообщений: n/a

состояние динамики должно быть 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 - простое трехциферное число
  #3  
Старый 10.08.2008, 23:13
гость1

 
Сообщений: n/a

я реализовал так как вы сказали, но почему то получаю вр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.
  #4  
Старый 11.08.2008, 00:22
cmd cmd вне форума
Пользователь

Отправить личное сообщение для cmd Посмотреть профиль Найти все сообщения от cmd
 
Регистрация: 10.12.2006
Адрес: VSTU[Volgograd]
Сообщений: 53

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

Я думаю из-за того, что ты не учел условия задачи, что ответ нужно вывести(считать) по модулю 10^9+9
  #5  
Старый 11.08.2008, 00:53
гость1

 
Сообщений: n/a

я изменил сторочку вывода
writeln(ans mod (1000000009));
да я это не заметил совсем, но к сожалению не из-за этого всё равно вр5(((
  #6  
Старый 11.08.2008, 14:29
cmd cmd вне форума
Пользователь

Отправить личное сообщение для cmd Посмотреть профиль Найти все сообщения от cmd
 
Регистрация: 10.12.2006
Адрес: VSTU[Volgograd]
Сообщений: 53

А ты учитываешь, что "подряд идущие 3 цифры образуют трехзначное простое число. " -- именно трехзначное, т.е. например 031 -- это не трехзначное ?
  #7  
Старый 11.08.2008, 15:06
гость

 
Сообщений: n/a

конечно вот в этой процедурке
Код:
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;
  #8  
Старый 11.08.2008, 17:32
cmd cmd вне форума
Пользователь

Отправить личное сообщение для cmd Посмотреть профиль Найти все сообщения от cmd
 
Регистрация: 10.12.2006
Адрес: VSTU[Volgograd]
Сообщений: 53

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

writeln(ans mod 1000000009) не достаточно. Ибо у тебя может быть переполнение где-нибудь (за int64 выйти за границы), поэтому желательно после каждого действий брать по модулю 1000000009
  #9  
Старый 11.08.2008, 17:34
cmd cmd вне форума
Пользователь

Отправить личное сообщение для cmd Посмотреть профиль Найти все сообщения от cmd
 
Регистрация: 10.12.2006
Адрес: VSTU[Volgograd]
Сообщений: 53

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

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра