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 1508. Japanese Puzzle

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.
Re: To admin
Posted by asia 2 Apr 2009 02:04
A test for you:
8 2
2 2
??.X?.??