I use Dynamic Programming..and i made several tests myself, my code could calculate the right answer = =...sorry for my poor English Simple tests: 1) 5 2 2 2 ????? ans:XX.XX 2) 4 2 2 2 ???? ans:Impossible 3) 15 3 2 1 2 ??X?.?.......X? ans:.?X?.X.......XX 4) 15 5 2 1 2 1 2 ??X?.?.X.?.?.X? ans:Impossible 5) 5 0 XXXXX ans:Impossible 6) 5 3 1 1 1 X.X.X ans:X.X.X 7) 5 2 1 1 .?.?. ans:.X.X. 8) 18 5 3 1 1 3 1 .???.X?.??..?XX?.? ans:.XXX.X..??..?XX?.X It's neccesary to use dances with diamonds to get AC in java without ML =)) Recoursive DP and DFS gets ML12, but iterative DP and BFS with queue based on arrays gets AC. I think that the same (Rec DP+DFS) solution in C++ can pass all tests without troubles.. Can you give me a hint about TEST#27?I have been checked my program for 2 days.And I can't find what's wrong with my program.I'm crazy! Here is my program: program puzzle; const maxn=410; var d,f:array [0..maxn,0..maxn] of longint; b,e,s,a:array [0..maxn] of longint; t,vis:array [0..maxn] of boolean; ch:array [0..maxn] of char; i,j,p,k,l,m,n:longint; procedure init; begin read(n,m); for i:=1 to m do read(a[i]);readln; for i:=1 to n do begin repeat read(ch[i]); until ch[i] in ['?','X','.']; end; readln; end; procedure solve; begin for i:=1 to n do begin s[i]:=s[i-1]; if ch[i]='X' then inc(s[i]); end; fillchar(d,sizeof(d),-$3f); d[n+1,m+1]:=0; k:=n; for i:=n downto 1 do begin for j:=m+1 downto 1 do begin d[i,j]:=d[i+1,j]; if (j=m+1) or (i+a[j]-1>n) or (ch[i]='.') then continue; if i+a[j]+1>n then l:=n+1 else l:=i+a[j]+1; if (i+a[j]-1<=k) and (d[l,j+1]>=0) and (d[l,j+1]+s[i+a[j]-1]-s[i-1]>d[i,j]) then d[i,j]:=d[l,j+1]+s[i+a[j]-1]-s[i-1]; end; if ch[i]='.' then k:=i-1; end; if d[1,1]<>s[n] then begin writeln('Impossible');exit; end; fillchar(f,sizeof(f),-$3f); f[0,0]:=0; k:=1; for i:=1 to n do begin for j:=0 to m do begin f[i,j]:=f[i-1,j]; if (j=0) or (i<a[j]) or (ch[i]='.') then continue; if i-a[j]-1<1 then l:=0 else l:=i-a[j]-1; if (i-a[j]+1>=k) and (f[l,j-1]>=0) and (f[l,j-1]+s[i]-s[i-a[j]]>f[i,j]) then f[i,j]:=f[l,j-1]+s[i]-s[i-a[j]]; end; if ch[i]='.' then k:=i+1; end; fillchar(vis,sizeof(vis),false); fillchar(t,sizeof(t),false); fillchar(b,sizeof(b),255); p:=0; for i:=1 to n do begin if ch[i]='.' then begin p:=i;continue; end; for j:=1 to m do begin if i-a[j]+1<=p then continue; if i+2<=n then k:=d[i+2,j+1] else begin if j<m then continue;k:=0; end; if i-a[j]-1>0 then inc(k,f[i-a[j]-1,j-1]) else begin if j>1 then continue; end; if s[i]-s[i-a[j]]+k=s[n] then begin for l:=i-a[j]+1 to i do t[l]:=true; if b[j]=-1 then begin b[j]:=i-a[j]+1;e[j]:=i; continue; end; if e[j]<i-a[j]+1 then begin b[j]:=i-a[j]+1;e[j]:=i; vis[j]:=true; end; if vis[j] then continue; b[j]:=i-a[j]+1; end; end; end; for i:=1 to n do if not t[i] and (ch[i]='?') then ch[i]:='.'; for i:=1 to m do begin if vis[i] then continue; for j:=b[i] to e[i] do ch[j]:='X'; end; for i:=1 to n do write(ch[i]);writeln; end; begin assign(input,'puzzle.in');reset(input); assign(output,'puzzle.out');rewrite(output); init; solve; close(input);close(output); end. At last.Sorry for my poor English. A test for you: 8 2 2 2 ??.X?.?? I got WA on it about 20 times.I'm crazy now! Please help me. Thank you! deffinitely -> definitely (used twice in statement) Also I suggest the following change: The first line contains the length of the row L and the number of groups of consecutive cells that must be painted (1 ≤ L ≤ 400). The second line contains K integers (0 ≤ K ≤ L), which are the lengths of these groups. -> The first line contains the length of the row L (1 ≤ L ≤ 400) and the number of groups of consecutive cells that must be painted K (0 ≤ K ≤ L). The second line contains K integers, which are the lengths of these groups. I can't imagine how its possible. Test 1 == Sample Test 1, I think. Here is my code (I delete it when I find the bug): [code deleted] Oh, I am too stupid... Don't read this!!!!!!!! Edited by author 17.08.2007 13:33 Does anybody know what test #27 is? I made two different programs and both were stoped here. Now I am really confused... Thanks in andvance. I got AC! Topic is closed. In the description of input, "The second line contains K integers". If K = 0, the second should be empty line. But in Sample input #2 9 0 ??????.X? There is not so-called second line. So I read data like following. and got WA at 3. ---------------- Readln(N, M); if M > 0 then begin for i := 1 to M do Read(L[i]); Readln; end; for i := 1 to N do Read(T[i]); ---------------- Then I suppose sample input #2 is wrong, there must be an empty line in second line when K = 0. I change code like following. and got WA at 20. ---------------- Readln(N, M); for i := 1 to M do Read(L[i]); Readln; for i := 1 to N do Read(T[i]); ---------------- It implys there is some invalid char in input file. So I change code like following. and got AC. Readln(N, M); for i := 1 to M do Read(L[i]); for i := 1 to N do repeat Read(T[i]); until T[i] in ['X', '.', '?']; So there must be something wrong in testcase. There was a bug in sample output #2. Tests are correct. |
|