10337 - Flight Planner

[seolv]

Is there anybody who know why the output of testcase2 is "354"?

plz answer me.

[Shih-Chia Cheng]

The airplane must land on arrival, the altitude of it thus must be zero at the destination.

[seolv]

thank you cheng.

I got Accepted

[henar2]

I know that the plane must have land.
My program which checks every way of flying gives me for the first case:

120

but for the second one:

370

any hint?

[UFP2161]

The plane must climb when it takes off and must land at the end. It cannot "skim" along the bottom in between.

My matrix for the second flight looks something like:

Code: Select all

   0   0   0   0   0   0   0   0   0 505
   0   0   0   0   0   0   0   0 454 475
   0   0   0   0   0   0   0 403 424 445
   0   0   0   0   0   0 352 373 394 415
   0   0   0   0   0 301 322 343 364 385
   0   0   0   0 250 271 292 313 334 355
   0   0   0 197 220 243 266 289 312 335
   0   0 132 167 202 233 256 279 302 325
   0  69 102 139 176 213 250 281 304 327
   0   0   0   0   0   0   0   0   0   0

327 + 20 (descend) - (-7) (the windspeed at row 2, column 10 [row 1 is bottom row, column 1 is leftmost column]) = 354

I had 370 for the longest time too.

[dll]

I got 6 WA , I can't find my mistake, anyone help me ?
thanks in advance

[cpp]
#include <stdio.h>
#include <string.h>

const int M = 1001;

int d[2][11], a[M][11];
int n;

int main() {
int T,i,j;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
n/=100;
for(i=9;i>=0;i--) {
for(j=0;j<n;j++) scanf("%d",&a[j]);
}
int MAX = 200000000;
int w, pre=0, c=1;

for(i=0;i<10;i++) d[0]=MAX;
d[0][0]=0;
for(i=0;i<n;i++) {
for(j=0;j<10;j++) d[c][j]=MAX;

for(j=0;j<10;j++) if(d[pre][j]<MAX) {

w = d[pre][j] + 30 - a[j];
d[c][j]=d[c][j]<w?d[c][j]:w;

if(j>0) {
w = d[pre][j] + 20 - a[j];
d[c][j-1]=d[c][j-1]<w?d[c][j-1]:w;
}
if(j<9) {
w = d[pre][j] + 60 - a[j];
d[c][j+1]=d[c][j+1]<w?d[c][j+1]:w;
}
}
pre=1-pre;
c=1-c;
}
printf("%d\n\n",d[pre][0]);
}
return 0;
}

[/cpp]

[Abednego]

Same for me. I think it's a straightforward DP problem, but I get WA.

[sohel]

You are right.. it is a straight forward DP.

Did you consider the case where you can reach the final altitude(ie 0) by climbing down from the previous column( ie previous hundred mile).

There are two ways to reach the destination;
1) from previous column and same row.
2) from previous column and a row above.

Hope it helps..

[Abednego]

I'm such an idiot!
t[1024][16] is very different from t[16][1024].

[sklitzz]

I'm having trouble with this problem. I written a simple dp.
But I can't get the right answears even for the example test cases. Have I understood something wrong?

This is my code:

Code: Select all

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <climits>
using namespace std;

#define INF INT_MAX / 2

int N, M;
int field[1000][10];
int best[1000][10];

int get_min( int a, int b ) {
	int ret = INF;
	if( b > 0 ) ret <?= best[a-1][b-1] + 20 - field[a][b];
 	if( b < 9 ) ret <?= best[a-1][b+1] + 60 - field[a][b];
	ret <?= best[a-1][b] + 30 - field[a][b];
	
	return ret;
}

int doit() {
	for( int i = 0; i < 10; ++i ) best[0][i] = INF;
	best[0][0] = 30 - field[0][0];
	
	for( int i = 1; i < M; ++i )
		for( int j = 0; j < 10; ++j )
			best[i][j] <?= get_min( i, j );
	
	return best[M-1][0];
}

int main() {
	scanf( "%d", &N );
	for( int i = 0; i < N; ++i ) {
		scanf( "%d", &M ); 
		M /= 100;
		
		for( int j = 9; j >= 0; --j )
			for( int k = 0; k < M; ++k ) {
				scanf( "%d", &field[k][j] );
				best[k][j] = INF;
			}
		
		printf( "%d\n", doit() );			
	}
	return 0;
}

[LucasSchm]

Code: Select all

That little '\n' at the end of every output... ACC now.

[chucky316]

i got LOTS OF WAs :S:S:S is there any test cases plz ?!!!

[LucasSchm]

i got LOTS OF WAs :S:S:S is there any test cases plz ?!!!

Here you go:

Code: Select all

16

400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 9 9 1
1 -9 -9 1

1000
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9
 9  9  9  9  9  9  9  9  9  9  
 7  7  7  7  7  7  7  7  7  7
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5
-7 -3 -7 -7 -7 -7 -7 -7 -7 -7
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9

300
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10

1000
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9  
7 7 7 7 7 7 7 7 7 7
5 5 5 5 5 5 5 5 5 5
7 3 7 7 7 7 7 7 7 7
9 9 9 9 9 9 9 9 9 9

400
1 1 1 -1
1 -1 1 1
1 1 1 1
1 1 -1 1
-1 1 1 1
1 5 6 -1
1 -1 1 4
-7 4 -3 1
2 9 -9 4
1 -9 -9 1

1000
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9 
-7 -7 -7 -7 -7 -7 -7 -7 -7 -7
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5
-7 -3 -7 -7 -7 -7 -7 -7 -7 -7
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9

700
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

1000
 9  9  9  9  9  9  9  9  9  9
 9  9  9  -9  -9  9  9  9  9  9
 9  9  9  -6  9  -8  -9  9  9  9
 9  9  6  9  10  10  10  10  9  9
 -10  -10  -10  6  7  5  9  9  9  9
 9  9  -4  9  6  9  9  -9  9  9  
 7  7  2  5  -4  -6  7  -7  7  7
-5 -3 -5 5 5 -5 -5 5 -5 -5
7 3 -8 7 -7 4 5 -7 7 -8
-5 -9 9 9 -9 -9 -9 6 6 -9

400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0

1000
 9  9  6  9  5  -4  -9  9  9  9
 -1  9  9  -9  -9  4  1  -3  -9  9
 9  -2  3  -6  9  -8  -9  9  4  9
 9  9  6  9  10  10  10  10  3  3
 -10  -10  -1  3  0  0  9  9  9  6
 9  5  -4  2  6  9  9  -9  9  9  
 7  8  3  5  -4  -6  0  -7  3  7
-5 -3 5 2 5 -1 -3 5 -5 -2
7 3 -8 1 -7 4 5 -7 4 1
-5 -9 2 1 -9 -9 -9 4 6 -9

400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

1200
 9  9  6  9  5  -4  -9  9  9  9 3 2
 -1  9  9  -9  -9  4  1  -3  -9  9 4 4
 9  -2  3  -6  9  -8  -9  9  4  9 7 8
 9  9  6  9  10  10  10  10  3  3 -9 -9
 -10  -10  -1  3  0  0  9  9  9  6 0 0
 9  5  -4  2  6  9  9  -9  9  9 2 3
 7  8  3  5  -4  -6  0  -7  -3  7 6 1
-5 -3 5 2 5 -1 -3 5 -5 -2 5 4
7 3 -8 1 -7 4 5 -7 4 1 -3 2
-5 -9 2 1 -9 -9 -9 4 6 -9 7 8

400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 6 2
1 -5 1 5
3 7 6 -2
1 3 10 8
-5 -9 10 1
1 9 -9 1

1500
 9  9  6  9  5  -4  -9  9  9  9 3 2 5 1 0
 -1  9  9  -9  -9  4  1  -3  -9  9 4 4 3 0 -9
 9  -2  3  -6  9  -8  -9  9  4  9 7 8 2 -7 6
 9  9  6  9  10  10  10  10  3  3 -9 -9 1 0 1
 -10  -10  -1  3  0  0  9  9  9  6 0 0 -9 9 -2
 9  5  -4  2  6  9  9  -9  9  9 2 3 3 3 1
 7  8  3  5  -4  -6  0  -7  -3  7 6 1 -8 7 6
-5 -3 5 2 5 -1 -3 5 -5 -2 5 4 3 4 5
7 3 -8 1 -7 4 5 -7 4 1 -3 2 10 -10 2
-5 -9 2 1 -9 -9 -9 4 6 -9 7 8 -6 4 5

700
1 1 9 1 -10 -10 -10
1 3 -7 4 7 10 10
1 3 -4 1 -4 1 5
1 10 2 3 0 1 -2
-10 2 6 2 7 3 -1
1 -5 1 3 2 -5 4
3 8 2 -2 -5 7 8
1 3 -9 8 -10 3 5
-5 -9 10 1 2 -8 1
1 9 -9 1 0 4 -5

1700
 9  9  6  9  5  -4  -9  9  9  9 3 2 5 1 0 3 4
 -1  9  9  -9  -9  -4  -1  -3  -9  9 4 4 3 0 -9 -2 1
 9  -2  3  -6  9  -8  -9  9  4  9 7 8 2 -7 6 7 8
 9  9  6  7  1  2  3  -10  3  3 -9 -9 1 0 1 0 0
 -10  10  -1  3  0  4  9  9  -9  6 3 0 -9 9 -2 -3 3
 9  5  -4  -9  6  9  9  -9  -9  9 2 3 3 3 1 5 -1
 7  1  3  5  -4  -6  2  -7  -3  -7 6 1 -8 7 6 8 -3
-5 -3 5 -10 5 -1 -2 -10 -5 -2 5 4 3 4 5 -4 3
7 2 -8 10 -7 4 5 -7 4 1 -3 2 1 -10 2 5 0
-5 -9 2 1 -9 -9 -9 4 6 -9 7 8 -6 4 5 2 3

My ACC output:

Code: Select all

120

354

100

252

135

388

223

329

140

323

140

384

137

468

232

525

[a13032002]

why the answer of the input
1

300
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10
10 -10 10


is


100???

Could someone explain to me?? thanks

[lucastan]

I would say this problem is confusing and ambiguous.

It is straightforward but not very well explained.

Say if the input is

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 9 9 1
1 -9 -9 1

Let row 0 be the bottommost (altitude 0) (1 -9 -9 1)
Let column 0 be the left most column

To get to column 1, row 1, you need to fly from column 0, row 0
This is a climb and you face a wind of 1. So fuel needed is 60-1 = 59
To get to column2, row 1, (stay on altitude) the fuel needed is 30-9 = 21
To get to column 3, row 1, (stay) the fuel needed is 30-9 = 21
To get to column 4, row 0, (landing), fuel needed is 20-1=19
Total = 59+21+21+19 = 120

Note column4 is non-existent

you are not allowed to go down to altitude 0, except at starting and landing.

Hope this helps!