## 11301 - Great Wall of China

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

### 11301 - Great Wall of China

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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 3 Solutions possible.

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
The dp is somewhat tricky.
both flow and simplex needs to be implemented carefully to avoid tle.

mccarre
New poster
Posts: 5
Joined: Mon Oct 01, 2007 7:46 pm
sorry I'm tired. Ignore this post.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:
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;
}``````
SHAKIL

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11301 - Great wall

Solved it By Dijkstra ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 11301 - Great Wall of China

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;
}
``````