116 - Unidirectional TSP

[CSGrandeur]

????????????10000????????????????……
Input

Code: Select all

1 1
1
2 1
1
1
1 2
1 1

Output

Code: Select all

1
1
1
1
1 1
2

[nest]

One day, one of my favorite teacher challeged me to solve this problem. i tried my best only one night to solve it.
at last i saw it gives the exact output for given sample input.
but this got wa.
i shocked very much.
after a long time, i want to show my code,why is wrong
#include<stdio.h>
#define min(x,y) (x<y?x:y)
int left(int i,int j);
int right(int i,int j);
int side(int i,int j);
int add(int i,int j);
int row(int b[20][120],int t, int y);
long long a[100][120];
int c,as,ar,al,m,n;
int main()
{
int i,j,small,b[20][120],x,y,p;

while(scanf("%d%d",&m,&n)==2){
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%lld",&a[j]);

int t=n;
for(i=1;i<=m;i++){
for(j=n-1;j>=1;j--){
if(j==n-1){
c=add(i,j);
a[j]=a[j]+c;
if(ar==al&&ar==as)
b[j]=i;
else if(c==ar) {

if(i==1)
b[j]=m;
else
b[j]=i-1;
}

else if(c==as)
b[j]=i;
else if(c==al){
if(i==m)
b[j]=1;
else
b[j]=i+1;
}

}
if(i==m){
n--;
i=0;
break;
}
}


}
small=a[1][1];
for(i=1;i<=m;i++){
j=1;
if(small>a[j])
small=a[i][j];
}
int sm=small;
for(x=1;x<=m;x++){

y=1;
if(sm==a[x][y]){
printf("%d ",x);
sm=-9999;
printf("%d ",b[x][y]);
int v=b[x][y];
int l=2;
while(l!=t){
if(l==2)
p=row(b,v,l);
else
p=row(b,p,l);
printf("%d ",p);
l++;

}
}



}
printf("\n%d\n",small);
}

return 0;
}
int add(int i,int j){
//int al,ar,as;
al=left(i,j);
ar=right(i,j);
as=side(i,j);
return min(al,min(as,ar));

}
int left(int i,int j){
if(i==m)
return a[1][j+1];
else
return a[i+1][j+1];

}
int right(int i,int j){
if(i==1)
return a[m][j+1];
else
return a[i-1][j+1];

}
int side(int i,int j){
return a[i][j+1];
}
int row(int b[20][120],int v,int l){

return b[v][l];

}
note: i never see this after that night

[brianfry713]

Don't print a space at the end of a line.

[@li_kuet]

Sample Input :

Code: Select all

6 6
1 2 2 1 1 1
1 1 2 2 1 1
1 1 1 2 2 1
1 1 1 2 2 1
1 1 1 2 1 1
1 1 1 1 2 1

Output :

Code: Select all

1 6 5 6 1 1
6

[karakuritempya]

hello, can someone help me to solve this?
I've tried many input but still WA
Here's my code

Code: Select all

#include <stdio.h>
#define FOR(ii,jj) for(ii=0;ii<jj;ii++)
#include <algorithm>
using namespace std;

int i,j,tb,r,c,posi;
long long memo[1000][1000],ar[1000][1000],maks;
bool check[1000][1000],mk;

void lk()
{
	if((memo[j][i]+ar[tb][i+1]<memo[tb][i+1])||(memo[tb][i+1]==-1))
		memo[tb][i+1]=memo[j][i]+ar[tb][i+1];
}

void bt(int posr,int posc)
{
	int ce[3],iii;
	if (check[posr][posc]!=1)
	{
		check[posr][posc]=1;
		if (posc!=0)
		{
			ce[0]=posr;
			if (posr-1<0)
				ce[1]=posr+r-1; else
			ce[1]=posr-1;
			if (posr+1>=r)
				ce[2]=posr-r+1; else
			ce[2]=posr+1;
			FOR(iii,3)
			{
				if (memo[ce[iii]][posc-1]+ar[posr][posc]==memo[posr][posc])
					bt(ce[iii],posc-1);
			}
		}
	}
}

int main()
{	
	int xxx;
	while (scanf("%d%d\n",&r,&c)!=EOF)
	{
		FOR(i,r)
		{
			FOR(j,c)
				scanf("%lld",&ar[i][j]);
			scanf("\n");
		}
		FOR(i,r)
			FOR(j,c)
			{
				if (j==0)
					memo[i][j]=ar[i][j]; else
				memo[i][j]=-1LL;
			}
		FOR(i,c-1)
		{
			FOR(j,r)
			{
				tb=j;
				lk();
				if(j-1<0)
					tb=j+r-1; else
					tb=j-1;
				lk();
				if(j+1>=r)
					tb=j-r+1; else
					tb=j+1;
				lk();
			}
		}
		FOR(i,r)
			FOR(j,c)
				check[i][j]=0;
		mk=0;
		FOR(j,r)
			if((memo[j][c-1]<maks)||(!mk))
			{
				maks=memo[j][c-1];
				mk=1;
			}
		FOR(j,r)
			if(memo[j][c-1]==maks)
			{
				bt(j,c-1);
			}
		FOR(j,r)
			if (check[j][0])
			{
				posi=j;
				break;
			}
		printf("%d",posi+1);
		for(i=1;i<c;i++)
		{	
			int ce[3];
				ce[0]=posi;
			if (posi-1<0)
				ce[1]=posi+r-1; else
			ce[1]=posi-1;
			if (posi+1>=r)
				ce[2]=posi-r+1; else
			ce[2]=posi+1;
			sort(ce,ce+3);
			FOR(j,3)
			{
				if ((memo[posi][i-1]+ar[ce[j]][i]==memo[ce[j]][i])&&(check[ce[j]][i]))
				{
					printf(" %d",ce[j]+1);
					posi=ce[j];
					break;
				}
			}
		}
		printf("\n");
		printf("%lld\n",maks);
	}	
	return 0;
}

[brianfry713]

Input:

Code: Select all

4 69
-287 257 229 -297 374 457 -31 -8 -477 -239 -374 -198 -197 346 -286 5 -332 351 -157 -164 228 437 -187 400 -217 270 -169 278 275 451 232 489 208 313 -308 435 270 161 -73 -355 -226 406 299 429 252 -487 -65 421 364 278 109 93 -433 422 345 203 -456 -324 -19 320 -21 -287 309 -313 -122 -147 -378 1 -134
402 146 140 308 -54 69 412 311 -496 -315 176 -365 294 121 -298 -432 -34 -243 -387 494 239 433 -27 -196 -406 160 183 -53 -365 36 313 -463 34 -47 -303 -168 -478 -391 -356 -121 -205 320 14 -411 -59 -432 10 -241 -174 123 -247 -83 408 226 221 -498 238 256 -51 373 -208 114 410 -321 -433 -393 11 -59 69
155 320 364 327 186 -195 -232 -393 315 379 -67 290 -368 350 198 -290 423 -448 449 -468 1 322 -176 -385 -415 355 34 44 -133 -172 -387 -478 0 -171 350 -313 135 -30 -206 302 -150 -421 445 334 -219 495 -455 56 -452 494 88 401 -332 -235 -131 105 -380 403 -350 -13 -269 -237 10 -416 93 212 -229 80 -318
417 234 384 -152 179 219 481 175 264 37 223 -390 -374 124 130 243 493 -264 363 -251 -114 -149 332 -499 -287 416 446 -223 39 26 -41 -44 113 196 -344 -208 -85 -363 -181 31 -473 -458 493 5 -481 123 -252 -136 359 -389 113 97 314 298 99 -121 214 45 156 -246 -76 -32 -438 -463 -336 71 181 431 -440

AC output:

Code: Select all

1 2 2 1 2 3 3 3 2 2 1 4 3 2 2 2 1 2 2 3 4 4 1 4 3 2 1 2 2 3 3 3 3 3 4 3 2 2 2 1 4 3 2 2 3 2 3 2 3 4 3 2 3 3 3 2 1 1 1 4 3 3 4 3 2 2 1 1 4
-19108

[brianfry713]

Input:

Code: Select all

6 8 
9 1 9 9 1 1 1 1 
1 9 9 1 9 9 9 9 
9 9 1 9 9 1 1 1 
1 1 9 9 1 9 9 9 
9 9 9 1 9 9 9 9 
9 9 1 9 9 9 9 9 
6 7
1 9 9 1 9 9 9
9 1 1 9 9 9 9
9 9 9 9 1 1 1
9 9 9 1 9 9 9
9 9 1 9 9 9 9
9 1 9 9 1 1 1
5 4
9 1 9 9
1 9 9 9
9 9 9 9
1 1 1 1
9 9 1 9
5 6
-3 -4 -1 -2 -8 -6
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4
10 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

AC output:

Code: Select all

2 1 6 5 4 3 3 3
8
1 2 2 1 6 6 6
7
2 1 5 4
4
4 3 2 3 3 4
-49
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100

[gkevinyen5418]

Code: Select all

// i dont know why i get WA 
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int m, n; 
    while( scanf("%d %d", &m, &n)!=EOF )
    {
        int SJ[15][105]={0};int dp[15][105]={0};int sp[15][105]={0};
                   
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            scanf("%d", &SJ[i][j]);
    
    for(int i = 0; i < m; i++)
        dp[i][n-1] = SJ[i][n-1];
    
    for(int j = n-2; j >= 0; j--)
        for(int i = 0; i < m; i++)
        {
           
            if( i == 0 )
            {
                dp[i][j] = dp[i][j+1];
                sp[i][j] = i;
                if( dp[i][j] > dp[i+1][j+1] )
                { 
                    dp[i][j] = dp[i+1][j+1];
                    sp[i][j] = i+1; 
                }
                if( dp[i][j] > dp[m-1][j+1] )
                { 
                    dp[i][j] = dp[m-1][j+1];
                    sp[i][j] = m-1; 
                }
                
            }
            else if( i == m-1 )
            {
                dp[i][j] = dp[0][j+1];
                sp[i][j] = 0;
                if( dp[i][j] > dp[i-1][j+1] )
                { 
                    dp[i][j] = dp[i-1][j+1];
                    sp[i][j] = i-1; 
                }
                if( dp[i][j] > dp[i][j+1] )
                { 
                    dp[i][j] = dp[i][j+1];
                    sp[i][j] = i; 
                }    
            }
            else
            {
                
                
                dp[i][j] = dp[i-1][j+1];
                sp[i][j] = i-1;
                if( dp[i][j] > dp[i][j+1] )
                { 
                    dp[i][j] = dp[i][j+1];
                    sp[i][j] = i; 
                }
                if( dp[i][j] > dp[i+1][j+1] )
                { 
                    dp[i][j] = dp[i+1][j+1];
                    sp[i][j] = i+1; 
                }   
              
            }
            dp[i][j]+=SJ[i][j];
        }
    int mn = 0;
    for(int i = 1; i < m; i++)
        if( dp[mn][0] > dp[i][0] ){ mn = i; }
    
    printf("%d", mn+1);
    int r = mn;
    for(int j = 0; j < n-1; j++)
    {
         r = sp[r][j]; 
        printf(" %d", r+1);
          
    }
    printf("\n%d\n", dp[mn][0]);
    }    
}

[brianfry713]

Try input:

Code: Select all

1 36
258 375 -345 -263 -12 79 292 292 43 347 -23 227 -68 -98 74 386 -188 194 -172 413 -263 -469 375 -102 444 -77 -130 170 306 -95 452 64 132 -40 -347 -380

[gkevinyen5418]

wow~ i dint notice that
and thank u <(_ _)>

[moody]

Accepted

[brianfry713]

Input:

Code: Select all

6 2
-447 -242
-23 -409
60 -169
362 -136
413 -443
-165 20
8 1
40
-357
-459
-71
-43
48
-18
-104

AC output:

Code: Select all

1 2
-856
3
-459

[moody]

Input:

Code: Select all

6 2
-447 -242
-23 -409
60 -169
362 -136
413 -443
-165 20
8 1
40
-357
-459
-71
-43
48
-18
-104

AC output:

Code: Select all

1 2
-856
3
-459

first i really appreciate ur concern
there was an error in the case that was there only one col,i fixed it and the cases u sent below works fine for me but on the judge still WA
any help , please?

[brianfry713]

Post your updated code.

[moody]

Code: Select all

Accepted