ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1002. Телефонные номера

pz, help. I used DP
Послано NoName 30 апр 2008 17:52
Hi. I used dp but Im getting WA #2 and I cant find my bug

Here is my code in Pascal.

Program timus1002;

{$APPTYPE CONSOLE}

Uses
  SysUtils,math;
Var
  code:array['a'..'z'] of string[1];
  word,digit:array[0..50001] of string[50];
  bool:boolean;
  nword,iword:array[0..101] of longint;
  i,leng,num:longint;
  number:string[100];
  cur,min:longint;
  ans:array[0..101] of string[50];
Procedure Init;
begin
  code['a']:='2'; code['b']:='2'; code['c']:='2';
  code['d']:='3'; code['e']:='3'; code['f']:='3';
  code['g']:='4'; code['h']:='4'; code['i']:='1';
  code['j']:='1'; code['k']:='5'; code['l']:='5';
  code['m']:='6'; code['n']:='6'; code['o']:='0';
  code['p']:='7'; code['q']:='0'; code['r']:='7';
  code['s']:='7'; code['t']:='8'; code['u']:='8';
  code['v']:='8'; code['w']:='9'; code['x']:='9';
  code['y']:='9'; code['z']:='0';
end;

Function toDigit(wo:string):string;
var len,i:integer; s1:string[50];
begin
  len:=length(wo);
  s1:='';
  for i:=1 to len do
    s1:=s1+code[wo[i]];
  toDigit:=s1;
end;

Procedure Solve;
var
  boo:array[0..101] of boolean;
  i,l,ll:integer;j:longint;
begin
  for i:=0 to 101 do
  begin
    nWord[i]:=101;
    boo[i]:=false;
  end;
  boo[1]:=true;
  nWord[0]:=0;
  for i:=1 to leng do
    if boo[i] then
    begin
      l:=leng-i+1;
      for j:=1 to num do
      begin
        ll:=length(digit[j]);
        if l>=ll then
          if copy(number,i,ll)=digit[j] then
          begin
            boo[i+ll]:=true;
            if nWord[i-1]+1<nWord[i+ll-1] then
            begin
              nWord[i+ll-1]:=nWord[i-1]+1;
              iWord[i+ll-1]:=j;
            end;
          end;
      end;
    end;
end;

Begin
  assign(input,'');
  assign(output,'');
  reset(input);
  rewrite(output);
  Init;
  bool:=true;
  while bool do
  begin
    readln(number);
    if number='-1' then break;
    leng:=length(number);
    readln(num);
    for i:=1 to num do
    begin
      readln(word[i]);
      digit[i]:=toDigit(word[i]);
    end;
    Solve;
     min:=nWord[leng];
     if min>=101 then
     begin
        Writeln('No soltion.');
     end
     else
     begin
       cur:=leng;
       for i:=min downto 1 do
       begin
        ans[i]:=word[iword[cur]];
        cur:=cur-length(ans[i]);
       end;
       for i:=1 to min-1 do write(ans[i],' ');
       writeln(ans[min]);
     end;
  end;
  close(input);
  close(output);
  readln;readln;
End.

Here
number -- given phone number
word[i] -- i-word.
digit[i] -- digits available to word[i]
nWord[i] -- find out "the number of words" used for first i numbers of the given phone number.
iWord[i] -- the index of the word ends at point i of the given phone number.
boo[i] -- finds out if we can put the word at the i-point of the given phone number.

In my prog. begin from first letter of the number till the last one. At each point I find out if I can put a word from this point. If yes-- boo[i]==true-- then I check all the dictionary for this point. If I find the word that matches this point I arrange the j-point-- the next point of the ending point of this word and change the boo[j] to "true". ...
If U dont understand my prog, tell me I gonna explain it much more better.

Plz  help me and tell me where my bug is.

Thnx
Re: pz, help. I used DP
Послано wsoangel 2 май 2008 12:47
hi, may be you out put statement is wrong.
when no solution ,you should output "No solution" ,not "No soltion."
the first test group all have the answer,but the second is not:)
Re: pz, help. I used DP
Послано NoName 2 май 2008 20:22
Thnx I got AC. It is the stupid mistake!