ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1508. Японский кроссворд

Показать все сообщения Спрятать все сообщения

To admin yuyan 31 мар 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 asia 2 апр 2009 02:04
A test for you:
8 2
2 2
??.X?.??