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

Обсуждение задачи 1856. Война и мир

TO ADMINS: wtf???
Послано Evgeny 30 июл 2012 06:39
Извините за то, что пишу не на английском. Это лучше, чем использование электронного переводчика, да и администрация, по всей видимости, состоит только из русскоговорящих :)

Пишу решение к зачаче 1856. Прилагаю две программы, первая - исходная, вторая - незначительно изменённая (добавлен новый формальный параметр к функции, который никак не используется и на ход программы не влияет). Первая прошла 2 теста, вторая - только 1 с вердиктом Wrong Answer на втором.


КОД 1
вердикт: Time Limit Exceeded #3
_____________________________________
type
  situation = array [1..1000] of boolean;
  memory = array of situation;



var
  a: array [1..1000] of record
       a, b: integer;
     end;
  mem: memory;
  n, i: integer;



Function Process (ml: integer; mem: memory): boolean;

var
  z1, z2: boolean;
  s: situation;

function Sravn (a, b: situation): boolean;
var i: integer;
begin
  for i := 1 to n do
    if a[i] <> b[i] then
    begin
      sravn := false;
      exit;
    end;
  sravn := true;
end;

function War: boolean;
var
  i: integer;
  z: boolean;
begin
  z := false;
  for i := 1 to n do
    if mem[ml][i] then
      if z
        then begin
          war := false;
          exit;
        end
        else z := true;
  war := true;
end;

function Peace: boolean;
var i: integer;
begin
  for i := 0 to ml-1 do
    if sravn(mem[ml], mem[i]) then
    begin
      peace := true;
      exit;
    end;
  peace := false;
end;

function zA: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].a = i) then
      begin
        s[i] := true;
        break;
      end;
  zA := s;
end;

function zB: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].b = i) then
      begin
        s[i] := true;
        break;
      end;
  zB := s;
end;

begin
  inc(ml);
  if ml = length(mem) then setlength(mem, length(mem)+50);
  s := za;
  mem[ml] := s;
  if war
    then if ml mod 2 = 1
      then process := true
      else begin
        mem[ml] := zb;
        if war
          then process := true
          else if peace
            then process := false
            else process := process(ml, mem);
      end
    else if peace
      then if ml mod 2 = 0
        then process := false
        else begin
          mem[ml] := zb;
          if war
            then process := true
            else if peace
              then process := false
              else process := process(ml, mem);
        end
      else begin
        mem[ml] := zb;
        if war
          then if ml mod 2 = 1
            then process := true
            else begin
              mem[ml] := s;
              process := process(ml, mem);
            end
          else if peace
            then if ml mod 2 = 0
              then process := false
              else begin
                mem[ml] := s;
                process := process(ml, mem);
              end
            else begin
              z2 := process(ml, mem);
              mem[ml] := s;
              z1 := process(ml, mem);
              if ml mod 2 = 1
                then process := z1 or z2
                else process := not(z1) or not(z2);
            end;
      end;
end;



BEGIN
  {$IFNDEF ONLINE_JUDGE}
   assign(input, 'input.txt');
   reset(input);
   assign(output, 'output.txt');
   rewrite(output);
  {$ENDIF}
  {$M 67108864}

  readln(n);
  setlength(mem, 50);
  for i := 1 to n do
  begin
    readln(a[i].a, a[i].b);
    mem[0][i] := true;
  end;
  if process(0, mem)
    then write('War')
    else write('Peace');

  {$IFNDEF ONLINE_JUDGE}
   close(input);
   close(output);
  {$ENDIF}
END.
_____________________________________



КОД 2, звёздочками выделены изменения
вердикт: Wrong Answer #2
_____________________________________
type
  situation = array [1..1000] of boolean;
  memory = array of situation;



var
  a: array [1..1000] of record
       a, b: integer;
     end;
  mem: memory;
  n, i: integer;



Function Process (ml: integer; mem: memory; v: boolean): boolean;  //***************

var
  z1, z2: boolean;
  s: situation;

function Sravn (a, b: situation): boolean;
var i: integer;
begin
  for i := 1 to n do
    if a[i] <> b[i] then
    begin
      sravn := false;
      exit;
    end;
  sravn := true;
end;

function War: boolean;
var
  i: integer;
  z: boolean;
begin
  z := false;
  for i := 1 to n do
    if mem[ml][i] then
      if z
        then begin
          war := false;
          exit;
        end
        else z := true;
  war := true;
end;

function Peace: boolean;
var i: integer;
begin
  for i := 0 to ml-1 do
    if sravn(mem[ml], mem[i]) then
    begin
      peace := true;
      exit;
    end;
  peace := false;
end;

function zA: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].a = i) then
      begin
        s[i] := true;
        break;
      end;
  zA := s;
end;

function zB: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].b = i) then
      begin
        s[i] := true;
        break;
      end;
  zB := s;
end;

begin
  inc(ml);
  if ml = length(mem) then setlength(mem, length(mem)+50);
  s := za;
  mem[ml] := s;
  if war
    then if ml mod 2 = 1
      then process := true
      else begin
        mem[ml] := zb;
        if war
          then process := true
          else if peace
            then process := false
            else process := process(ml, mem, false);  //***************
      end
    else if peace
      then if ml mod 2 = 0
        then process := false
        else begin
          mem[ml] := zb;
          if war
            then process := true
            else if peace
              then process := false
              else process := process(ml, mem, false);  //***************
        end
      else begin
        mem[ml] := zb;
        if war
          then if ml mod 2 = 1
            then process := true
            else begin
              mem[ml] := s;
              process := process(ml, mem, false);  //***************
            end
          else if peace
            then if ml mod 2 = 0
              then process := false
              else begin
                mem[ml] := s;
                process := process(ml, mem, false);  //***************
              end
            else begin
              z2 := process(ml, mem, false);  //***************
              mem[ml] := s;
              z1 := process(ml, mem, false);  //***************
              if ml mod 2 = 1
                then process := z1 or z2
                else process := not(z1) or not(z2);
            end;
      end;
end;



BEGIN
  {$IFNDEF ONLINE_JUDGE}
   assign(input, 'input.txt');
   reset(input);
   assign(output, 'output.txt');
   rewrite(output);
  {$ENDIF}
  {$M 67108864}

  readln(n);
  setlength(mem, 50);
  for i := 1 to n do
  begin
    readln(a[i].a, a[i].b);
    mem[0][i] := true;
  end;
  if process(0, mem, false)  //***************
    then write('War')
    else write('Peace');

  {$IFNDEF ONLINE_JUDGE}
   close(input);
   close(output);
  {$ENDIF}
END.
_____________________________________


Код 1 второй тест проходил, код 2 по неведомым мне причинам выдал неверный ответ.
Как это изменение могло повлиять на результат?

Заранее благодарю за помощь.
Re: TO ADMINS: wtf???
Послано Vladimir Yakovlev (USU) 31 июл 2012 06:05
Скорее всего программа портит свою память и в случае разного скомпилированного кода это приводит в разному непредсказуемому поведению.