To admin
Posted by
yuyan 31 Mar 2009 20:25
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.