Why the same algorithm works on C++ but not on Pascal???Are the Pascal test programs correct????Have a look at this...
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.