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 1167. Bicolored Horses

Why WA?
Posted by sillyboy 20 Dec 2001 17:08
I always get wrong answer.
Could anybody help me?
Here is my programme:

var n,k,c,d,f,g,h:word; t:text;
    a,b:array[0..500] of word; e:array[1..500,1..500] of word;
begin
  assign(t,''); reset(t);
  readln(t,n,k);
  a[0]:=0; b[0]:=0;
  for c:=1 to n do begin
    readln(t,d);
    if d=0 then begin
      a[c]:=a[c-1]+1; b[c]:=b[c-1];
    end else begin
      a[c]:=a[c-1]; b[c]:=b[c-1]+1;
    end;
  end;
  close(t);
  for c:=1 to n do for d:=1 to k do e[c,d]:=65535;
  for c:=1 to n do begin
    e[c,1]:=a[c]*b[c];
    for d:=1 to c-1 do begin
      h:=(a[c]-a[d])*(b[c]-b[d]);
      if d<k-1 then f:=d else f:=k-1;
      for g:=1 to f do
        if e[c,g+1]>e[d,g]+h then e[c,g+1]:=e[d,g]+h;
    end;
  end;
  writeln(e[n,k]);
end.
WA because...
Posted by shitty.Mishka 20 Dec 2001 18:38
This is really very strange, but if you do the following, you'll get
AC. In part Var make a new variable i, and change cycle
      for g:=1 to f do
        if e[c,g+1]>e[d,g]+h then e[c,g+1]:=e[d,g]+h;
to this:
      for i:=1 to f do begin
        g:=i;
        if e[c,g+1]>e[d,g]+h then e[c,g+1]:=e[d,g]+h;
      end;
This should be the same, of course, but this way you'll get AC.
Actually, I don't know why:)
I think it's a bug of the pascal compiler. It happens inside three for-loops, look at the following program:(+)
Posted by abc 20 Dec 2001 18:52
{Submit this program, you'll get Time Limit Exceeded!}

var
  i,j,k:integer;
  p:array [1..2,1..1] of integer;
begin
  p[1,1]:=1; p[2,1]:=0;
  for i:=1 to 1 do begin
    j:=1;
    while p[i,j]=0 do inc(j);
    for j:=2 to 2 do begin
      for k:=1 to 1 do p[j,k]:=p[i,k];
      if p[2,1]=0 then repeat until false;
    end;
  end;
end.
Re: WA because...
Posted by sillyboy 21 Dec 2001 13:07
I've got AC. :)
Thank you very much indeed.