## 10337 - Flight Planner

Moderator: Board moderators

seolv
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 am

### 10337 - Flight Planner

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

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
The airplane must land on arrival, the altitude of it thus must be zero at the destination.

seolv
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 am
thank you cheng.

I got Accepted

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am

### 10337 Flight Planner

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

[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]
Nothing is impossible

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Same for me. I think it's a straightforward DP problem, but I get WA.
If only I had as much free time as I did in college...

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### ....

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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
I'm such an idiot!
t[1024][16] is very different from t[16][1024].
If only I had as much free time as I did in college...

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

### 10337 Flight Planner

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
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 10337 - Flight Planner

Code: Select all

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

chucky316
New poster
Posts: 5
Joined: Mon Apr 12, 2010 11:18 am

### Re: 10337 - Flight Planner

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

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 10337 - Flight Planner

chucky316 wrote: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
New poster
Posts: 5
Joined: Wed Aug 27, 2008 7:05 pm

### Re: 10337 - Flight Planner

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
New poster
Posts: 10
Joined: Sat Jul 02, 2011 6:46 am

### Re: 10337 - Flight Planner

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!