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
11301 - Great Wall of China
Moderator: Board moderators
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.
![:-)](./images/smilies/icon_smile.gif)
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.
-
- 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.
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
Re: 11301 - Great wall
Solved it By Dijkstra ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
-
- 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;
}
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.