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

Common Board

Why the same algorithm works on C++ but not on Pascal???Are the Pascal test programs correct????Have a look at this...
Posted by Vladimir Milenov Vasilev 18 Jan 2002 21:25
Here are my two sources - Pascal and C++. The first got Wrong answer,
and the second - accepted... Why????

C++ program   ......

#include <stdio.h>
void main(){
const max=500;
long int a[100][max];
int ind[100][max],br,k,m,n,i,j,index,out[15000];
double min,sum,b[100][max];
scanf("%d %d",&m,&n);
for(i=0;i<m;i++)
 for(j=0;j<n;j++){
     scanf("%ld",&a[i][j]);
     b[i][j]=0;
    }
for(j=0;j<n;j++){
    b[0][j]=a[0][j];
    ind[0][j]=j;
   }
for(i=1;i<m;i++)
 for(j=0;j<n;j++){
     min=b[i-1][j]+a[i][j];
     index=j;
     sum=a[i][j];
     for(k=j-1;k>=0;k--){
    sum+=a[i][k];
    if (sum>1000000000) break;
    if (sum+b[i-1][k]<min){
       min=sum+b[i-1][k];
       index=k;
      }
    }
     sum=a[i][j];
     for(k=j+1;k<n;k++){
    sum+=a[i][k];
    if (sum>1000000000) break;
    if (sum+b[i-1][k]<min){
       min=sum+b[i-1][k];
       index=k;
      }
    }
     ind[i][j]=index;
     b[i][j]=min;
    }
index=0;
min=b[m-1][0];
for(i=1;i<n;i++)
 if (b[m-1][i]<min){
     index=i;
     min=b[m-1][i];
    }

br=-1;
for(i=m-1;i>=0;i--){
    if(index<ind[i][index])
    for(j=index;j<=ind[i][index];j++){br+=1; out[br]=j;}
    else for(j=index;j>=ind[i][index];j--){br++;out[br]=j;}
    index=ind[i][index];
   }
for(k=br;k>=0;k--)printf("%d\n",out[k]+1);
}

And my Pascal source...
program minist;
const max=500;
      pm=100;
      maxi=25000;
var br,k,m,n,i,j,index,pos : integer;
    sum,min : longint;
    c : array[1..maxi] of integer;
    ind : array[1..pm,1..max] of integer;
    b,a : array[1..pm,1..max] of longint;
Begin
readln(m,n);
for i:=1 to n do ind[1,i]:=i;
for i:=1 to m do
 for j:=1 to n do read(a[i,j]);
for i:=1 to n do b[1,i]:=a[1,i];
for br:=2 to m do
 for i:=1 to n do
  Begin
   index:=i;
   min:=a[br,i]+b[br-1,i];
   sum:=a[br,i];
   for k:=i-1 downto 1 do
    Begin
     inc(sum,a[br,k]);
     if sum>1000000000 then break;
     if sum+b[br-1,k]<min
     then
      Begin
       min:=sum+b[br-1,k];
       index:=k;
      End;
    End;
   sum:=a[br,i];
   for k:=i+1 to n do
    Begin
     inc(sum,a[br,k]);
     if sum>1000000000 then break;
     if sum+b[br-1,k]<min
     then
      Begin
       min:=sum+b[br-1,k];
       index:=k;
      End;
    End;
   ind[br,i]:=index;
   b[br,i]:=min;
  End;
min:=b[m,1];
index:=1;
for i:=2 to n do
if b[m,i]<min
then
 Begin
  index:=i;
  min:=b[m,i];
 End;
pos:=0;
for br:=m-1 downto 1 do
 Begin
  if ind[br+1,index]>index
  then for k:=index to ind[br+1,index] do
       Begin
        inc(pos);
        c[pos]:=k;
       End
  else for k:=index downto ind[br+1,index] do
       Begin
        inc(pos);
        c[pos]:=k;
       End;
  index:=ind[br+1,index];
 End;
inc(pos);
c[pos]:=index;
for i:=pos downto 1 do writeln(c[i]);
End.
You'll get AC for you Pascal program if you do this: (+)
Posted by Michael_Rybak 19 Jan 2002 01:12
Some strange problems occure if you use 3 cycles inside each other:
For i:=1 To 10 Do
 For j:=1 To 10 Do
  For k:=1 To 10 Do Begin
   {Here if you use k it will have wrong value}
  End;
You should do this instead:
For i:=1 To 10 Do
 For j:=1 To 10 Do
  For temp:=1 To 10 Do Begin
   k:=temp;
   {Here if you use k it will have correct value}
  End;
I did this with your pascal source code and it got AC.