10337 - Flight Planner

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10337 - Flight Planner

Post by seolv » Tue Aug 06, 2002 11:35 am

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

plz answer me.

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:

Post by Shih-Chia Cheng » Tue Aug 06, 2002 11:52 am

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

Post by seolv » Tue Aug 06, 2002 12:38 pm

thank you cheng.

I got Accepted :D

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Thu Oct 03, 2002 1:28 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?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 28, 2003 7:30 pm

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

Post by dll » Sat Jun 19, 2004 1:28 pm

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Apr 24, 2005 7:04 am

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...

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

....

Post by sohel » Sun Apr 24, 2005 12:33 pm

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..

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Apr 25, 2005 1:35 am

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

Post by sklitzz » Thu Sep 21, 2006 10:41 pm

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

Post by LucasSchm » Sat May 01, 2010 9:20 pm

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

Post by chucky316 » Fri Aug 13, 2010 12:56 am

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

Post by LucasSchm » Fri Aug 13, 2010 12:59 am

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

Post by a13032002 » Wed May 25, 2011 8:50 am

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

Post by lucastan » Fri Aug 12, 2011 5:31 pm

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!

Post Reply

Return to “Volume 103 (10300-10399)”