116 - Unidirectional TSP

Moderator: Board moderators

CSGrandeur
New poster
Posts: 5
Joined: Tue Aug 16, 2011 11:15 am

Re: 116 Help me

????????????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
New poster
Posts: 6
Joined: Sun May 20, 2012 10:18 am

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 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){
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 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 116 Help me

Don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!
@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

Re: 116 Help me

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
New poster
Posts: 3
Joined: Sun Oct 21, 2012 10:34 am

Re: 116 Help me

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 116 Help me

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
``````
Check input and AC output for thousands of problems on uDebug!
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 116 Help me

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
``````
Check input and AC output for thousands of problems on uDebug!
gkevinyen5418
New poster
Posts: 3
Joined: Wed Jul 03, 2013 2:35 pm

116 [WA] Unidirectional TSP (C++)

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 116 [WA] Unidirectional TSP (C++)

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
``````
Check input and AC output for thousands of problems on uDebug!
gkevinyen5418
New poster
Posts: 3
Joined: Wed Jul 03, 2013 2:35 pm

Re: 116 [WA] Unidirectional TSP (C++)

wow~ i dint notice that
and thank u <(_ _)>
moody
New poster
Posts: 9
Joined: Tue Sep 24, 2013 2:19 am

116 - Unidirectional TSP WA-even so it passed all test cases

Accepted
Last edited by moody on Sat Oct 19, 2013 9:56 pm, edited 1 time in total.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 116 - Unidirectional TSP WA-even so it passed all test c

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
``````
Check input and AC output for thousands of problems on uDebug!
moody
New poster
Posts: 9
Joined: Tue Sep 24, 2013 2:19 am

Re: 116 - Unidirectional TSP WA-even so it passed all test c

brianfry713 wrote: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
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 116 - Unidirectional TSP WA-even so it passed all test c

``````Accepted