11301 - Great Wall of China

[Rocky]

Sorry for post here..there is no thread for vol-113.....so i post here.
can anybody give me some hints for this problem...??

Thank's in advance
Rocky

[baodog]

Three Solutions work here !!! Take your pick or try all 3 .

1) Network flow .. create 2 nodes for each grid... enter and exit...
connect... run your flow code.

2) Dynamic Programming.

3) Simplex Method. write contraints. solve.

[sclo]

The dp is somewhat tricky.
both flow and simplex needs to be implemented carefully to avoid tle.

[mccarre]

sorry I'm tired. Ignore this post.

[shakil]

Why WA.Please, give some sample input and output.
Thanks advance.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
long a,b,c,t,sa[1009][33],x[100],i,n,j,max,sum,I;
char temp[7][1009];


void make(long h1,long h2,long h3,long h4)
{
long t1;
if(h1+1<b&&h1+1<h2)
{
t1=pow(2,h1+1)+pow(2,h2)+pow(2,h3);
if(x[t1]>h4+(temp[h1+1][i]-48))
{
x[t1]=h4+(temp[h1+1][i]-48);
make(h1+1,h2,h3,h4+(temp[h1+1][i]-48));
}
}
if(h2+1<c&&h2+1<h3)
{
t1=pow(2,h1)+pow(2,h2+1)+pow(2,h3);
if(x[t1]>h4+(temp[h2+1][i]-48))
{
x[t1]=h4+(temp[h2+1][i]-48);
make(h1,h2+1,h3,h4+(temp[h2+1][i]-48));
}
}
if(h3+1<=4)
{
t1=pow(2,h1)+pow(2,h2)+pow(2,h3+1);
if(x[t1]>h4+(temp[h3+1][i]-48))
{
x[t1]=h4+(temp[h3+1][i]-48);
make(h1,h2,h3+1,h4+(temp[h3+1][i]-48));
}
}
if(h1-1>=0)
{
t1=pow(2,h1-1)+pow(2,h2)+pow(2,h3);
if(x[t1]>h4+(temp[h1-1][i]-48))
{
x[t1]=h4+(temp[h1-1][i]-48);
make(h1-1,h2,h3,h4+(temp[h1-1][i]-48));
}
}
if(h2-1>a&&h2-1>h1)
{
t1=pow(2,h1)+pow(2,h2-1)+pow(2,h3);
if(x[t1]>h4+(temp[h2-1][i]-48))
{
x[t1]=h4+(temp[h2-1][i]-48);
make(h1,h2-1,h3,h4+(temp[h2-1][i]-48));
}
}
if(h3-1>b&&h3-1>h2)
{
t1=pow(2,h1)+pow(2,h2)+pow(2,h3-1);
if(x[t1]>h4+(temp[h3-1][i]-48))
{
x[t1]=h4+(temp[h3-1][i]-48);
make(h1,h2,h3-1,h4+(temp[h3-1][i]-48));
}
}
}

int main()
{

for(i=0;i<=1000;i++)
for(j=0;j<=32;j++)
sa[i][j]=2000000;

while(1)
{
scanf("%ld",&n);

if(n==0)
break;

for(i=0;i<5;i++)
scanf("%s",temp[i]);



t=0;
for(i=0;i<5;i++)
if(temp[i][0]=='@')
{
x[t]=i;
t++;
}



i=pow(2,x[0])+pow(2,x[1])+pow(2,x[2]);


sa[0][i]=0;

for(i=0;i<n;i++)
{

for(j=0;j<=32;j++)
{x[j]=sa[i][j];
if(i!=0)
sa[i-1][j]=2000000;
}
for(a=0;a<=2;a++)
for(b=a+1;b<=3;b++)
for(c=b+1;c<=4;c++)
{
t=pow(2,a)+pow(2,b)+pow(2,c);
if(sa[i][t]!=2000000)
{

make(a,b,c,sa[i][t]);

}
}



for(a=0;a<=2;a++)
for(b=a+1;b<=3;b++)
for(c=b+1;c<=4;c++)
{
t=pow(2,a)+pow(2,b)+pow(2,c);
if(x[t]<sa[i][t])
sa[i][t]=x[t];
if(i!=n-1&&sa[i+1][t]>(sa[i][t]+(temp[a][i+1]-48)+(temp[b][i+1]-48)+(temp[c][i+1]-48)))
sa[i+1][t] = sa[i][t]+(temp[a][i+1]-48)+(temp[b][i+1]-48)+(temp[c][i+1]-48);

}

sum=0;

for(I=i+1;I<n;I++)
{
	sum=sum+temp[0][I]-48+temp[1][I]-48+temp[2][I]-48+temp[3][I]-48+temp[4][I]-48;
     if(sa[I][28]>sa[i][25]+sum)
     sa[I][28]=sa[i][25]+sum;
	 if(sa[I][25]>sa[i][28]+sum)
		 sa[I][25]=sa[i][28]+sum;
	 if(sa[I][25]>sa[i][19]+sum)
		 sa[I][25]=sa[i][19]+sum;
     if(sa[I][19]>sa[i][25]+sum)
		 sa[I][19]=sa[i][25]+sum;
	 if(sa[I][19]>sa[i][7]+sum)
		 sa[I][19]=sa[i][7]+sum;
	 if(sa[I][7]>sa[i][19]+sum)
		 sa[I][7]=sa[i][19]+sum;

}

}


max=2000000;
for(a=0;a<=2;a++)
for(b=a+1;b<=3;b++)
for(c=b+1;c<=4;c++)
{

t=pow(2,a)+pow(2,b)+pow(2,c);
if(sa[n-1][t]<max)
max=sa[n-1][t];

}

for(i=0;i<=32;i++)
sa[n-1][i]=2000000;
printf("%ld\n",max);

}
return 0;
}

[Angeh]

Solved it By Dijkstra ...

[metaphysis]

Test data generator.

Code: Select all

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

string c[10] = {
    "@@@00", "@@0@0", "@0@@0", "0@@@0", "@@00@",
    "@00@@", "00@@@", "@0@0@", "0@0@@", "0@@0@"
};

int main(int argc, char *argv[])
{
    srand(time(NULL));
    
    for (int i = 1; i <= 20; i++)
    {
        int t = rand() % 998 + 3;

        cout << t << '\n';
        
        int m = rand() % 10;
        for (int n = 0; n < 5; n++)
        {
            cout << c[m][n];
            for (int j = 2; j <= t; j++)
            {
                int k = rand() % 100;
                if (k < 30)
                    k = rand() % 9 + 1;
                else
                    k = 0;
                
                cout << k;
            }
            cout << '\n';
        }
    }

    cout << 0 << '\n';
    
    return 0;
}