10337 - Flight Planner
Moderator: Board moderators
10337 - Flight Planner
Is there anybody who know why the output of testcase2 is "354"?
plz answer me.
plz answer me.
-
- New poster
- Posts: 17
- Joined: Fri May 24, 2002 4:24 am
- Location: Taiwan
- 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:
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.
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
I had 370 for the longest time too.
10337 Flight Planner
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]
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
....
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..
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..
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:
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
Code: Select all
That little '\n' at the end of every output... ACC now.
Re: 10337 - Flight Planner
i got LOTS OF WAs :S:S:S is there any test cases plz ?!!!
Re: 10337 - Flight Planner
Here you go:chucky316 wrote:i got LOTS OF WAs :S:S:S is there any test cases plz ?!!!
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
Code: Select all
120
354
100
252
135
388
223
329
140
323
140
384
137
468
232
525
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
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
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!
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!