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 1856. War and Peace

TO ADMINS: wtf???
Posted by Evgeny 30 Jul 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???
Posted by Vladimir Yakovlev (USU) 31 Jul 2012 06:05
Скорее всего программа портит свою память и в случае разного скомпилированного кода это приводит в разному непредсказуемому поведению.