824 - Coast Tracker

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

Moderator: Board moderators

Post Reply
zzzzzddddd
New poster
Posts: 6
Joined: Tue Sep 21, 2004 5:53 pm

824 - Coast Tracker

Post by zzzzzddddd »

An easy problem, but what's wrong with my program?
can anyone tell me? thanks a lot.
[cpp]#include <stdio.h>

int dire[8][2]={{1,0},{1,-1},{-1,0},{-1,-1},{0,-1},{-1,1},{0,1},{1,1}};
int start[8]={6,7,0,1,2,3,4,5};

struct Tdata{
int x,y,type;
}data[8];
int x,y,dir;

bool island(int x,int y)
{
int i;
for (i=0;i<8;i++)
if (data.x==x&&data.y==y)
if (data.type==1) return true;
else return false;
return false;
}

int main()
{
int i,nx,ny,ndir;
while (1){
scanf("%d",&y);
if (y==-1) break;
scanf("%d%d",&x,&dir);
for (i=0;i<8;i++) scanf("%d%d%d",&data.y,&data.x,&data.type);
for (i=0;i<8;i++){
ndir=(i+start[dir])%8;
nx=x+dire[ndir][0],ny=y+dire[ndir][1];
if (island(nx,ny)){
printf("%d\n",ndir);
break;
}
}
}
return 0;
}
[/cpp]

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Did u consider this:-
the robot will always start its job in a square of the coast, with the sea at its right; therefore, the coast will be tracked in a counter clockwise direction
I think u should test these inputs
  • Input:
    21 27 4
    21 28 1
    20 28 1
    20 27 0
    20 26 1
    21 26 1
    22 26 0
    22 27 1
    22 28 0
    21 27 4
    21 28 0
    20 28 1
    20 27 1
    20 26 1
    21 26 0
    22 26 1
    22 27 1
    22 28 1
    21 27 3
    21 28 1
    20 28 1
    20 27 1
    20 26 0
    21 26 1
    22 26 0
    22 27 1
    22 28 1
    -1
And the output will be
  • Output:
    3
    5
    4
I hope this works.... :D
Ami ekhono shopno dekhi...
HomePage

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Try this set of input.

INPUT

Code: Select all


22 25 6
22 26 1
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 0
21 24 1
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 1
21 24 1
22 24 0
23 24 0
23 25 0
23 26 0

22 25 0
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 1
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 1
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 1
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 1
21 24 1
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 0
21 26 1
21 25 0
21 24 1
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 0
21 24 1
22 24 0
23 24 0
23 25 0
23 26 0

22 25 0
22 26 0
21 26 0
21 25 1
21 24 0
22 24 1
23 24 0
23 25 0
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 0
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 0
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 0

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 2
22 26 0
21 26 1
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 1
22 26 1
21 26 1
21 25 1
21 24 0
22 24 1
23 24 1
23 25 0
23 26 0

22 25 0
22 26 0
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 1
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 0
23 26 0

22 25 2
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 1
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 1
22 26 0
21 26 1
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 0

22 25 1
22 26 0
21 26 0
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 0

22 25 5
22 26 0
21 26 1
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 0

22 25 5
22 26 0
21 26 1
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 2
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 1
23 25 1
23 26 1

22 25 5
22 26 1
21 26 1
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 0
23 24 0
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 0
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 0
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 0
22 24 1
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 1

22 25 7
22 26 0
21 26 1
21 25 1
21 24 1
22 24 0
23 24 1
23 25 1
23 26 0

22 25 5
22 26 1
21 26 1
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 1
23 24 0
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 1

22 25 5
22 26 0
21 26 1
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

-1

OUTPUT

Code: Select all


6
6
6
6
6
7
7
0
2
2
2
1
0
7
6
7
7
0
2
2
2
2
4
4
3
2
1
0
1
2
3
3
3
1
1
5
5
3
3
2
2
6
6
6
6
5
3
3
3
6
6
6
6
0
0
0
0
7
5
4
4
5
4
6


drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

Post by drewsome »

Jan,

I don't think your sample input makes sense. For instance, your first test case looks like this:

110
011
110


with direction = 4. However, this is impossible - the direction must be 5 (giving a previous square of [0,2]). If the direction were indeed 4 then we would have a non-optimal previous square of [1, 2].

Of course this is assuming our robot always moves perfectly, but for this problem I think that is a safe assumption :)

-Andrew

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

The problem states that..
Given the current position and direction of the robot, and a percept of the surrounding world, decide the direction of the next move. Note that you are not being asked to program the whole coasttracking software; you are just programming a part of it. The direction must be computed in such a way that an iterative call of the program, with percepts from an environment as the one described, would allow the robot to track the coast.
I think I just made a part of the whole system... :wink:
Ami ekhono shopno dekhi...
HomePage

kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm

reply to daveon

Post by kwedeer »

daveon on post gave the test cases with the answers that are assumed to be right - actually - they are wrong (at least from the point of Online Judge) - because my program was accepted although it on approx 10% cases gave the different answers.

My strategy was to consider the nearest direction on the clockwise (and if for the current number of steps it doesn't exist - so seek in the counterclockwise direction from the initial position/direction) with the follwing condition: the land should be in the direction under considertion and the water should be in the immediate neigbourgh. Note - thet if this is tru for the intial direction then - one should reject it and seek new one...

Well - it worked for me - at least...

Daveon - pleas - be kind and review your data...

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

My test data corresponds to Figure 1 in the problem.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Re: reply to daveon

Post by daveon »

kwedeer wrote:daveon on post gave the test cases with the answers that are assumed to be right - actually - they are wrong (at least from the point of Online Judge) - because my program was accepted although it on approx 10% cases gave the different answers.
And you think you know the IO of the judge? Geese, I'm just trying to help.

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo »

for the following configuration:

Code: Select all

1   1   0
0  [4]  1      (4 is the current direction)
1   1   0
why the next move is 3 not 6? similarly,

Code: Select all

1   1   1
1  [3]  1
0   1   0
why the next move is 6 not 4?
please help me to understand! :(

(these examples are taken from Jan's sample input 1 and 3, respectively.)
Image

Post Reply

Return to “Volume 8 (800-899)”