OJ Board

The Online Judge board
https://onlinejudge.org/board/

10337 - Flight Planner

https://onlinejudge.org/board/viewtopic.php?t=12082

Page 1 of 2

10337 - Flight Planner

Posted: Tue Aug 06, 2002 11:35 am
by seolv
Is there anybody who know why the output of testcase2 is "354"?

plz answer me.

Posted: Tue Aug 06, 2002 11:52 am
by Shih-Chia Cheng
The airplane must land on arrival, the altitude of it thus must be zero at the destination.

Posted: Tue Aug 06, 2002 12:38 pm
by seolv
thank you cheng.

I got Accepted :D

Posted: Thu Oct 03, 2002 1:28 am
by 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?

Posted: Thu Aug 28, 2003 7:30 pm
by 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.

10337 Flight Planner

Posted: Sat Jun 19, 2004 1:28 pm
by 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]

Posted: Sun Apr 24, 2005 7:04 am
by Abednego
Same for me. I think it's a straightforward DP problem, but I get WA.

....

Posted: Sun Apr 24, 2005 12:33 pm
by 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..

Posted: Mon Apr 25, 2005 1:35 am
by Abednego
I'm such an idiot!
t[1024][16] is very different from t[16][1024].

10337 Flight Planner

Posted: Thu Sep 21, 2006 10:41 pm
by 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;
}

Re: 10337 - Flight Planner

Posted: Sat May 01, 2010 9:20 pm
by LucasSchm

Code: Select all

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

Re: 10337 - Flight Planner

Posted: Fri Aug 13, 2010 12:56 am
by chucky316
i got LOTS OF WAs :S:S:S is there any test cases plz ?!!!

Re: 10337 - Flight Planner

Posted: Fri Aug 13, 2010 12:59 am
by LucasSchm
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

Re: 10337 - Flight Planner

Posted: Wed May 25, 2011 8:50 am
by 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

Re: 10337 - Flight Planner

Posted: Fri Aug 12, 2011 5:31 pm
by 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!
All times are UTC+02:00
Page 1 of 2

Powered by phpBB® Forum Software © phpBB Limited