ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1002. Phone Numbers

pz, help. I used DP
Posted by NoName 30 Apr 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
Posted by wsoangel 2 May 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
Posted by NoName 2 May 2008 20:22
Thnx I got AC. It is the stupid mistake!