|
|
back to boardpz, 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 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! |
|
|