## 163 - City Directions

Moderator: Board moderators

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
i wonder in the sample input:

A2W S1N E
TURN SHARP LEFT

if according to the graph in the question, at (2,1). it cannot turn 135 to any direction. can someone clarify the workings for me?

MegaS
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am
I just want to tell that I've got the same problem: maybe someone knows for sure that test in this problem wrong?

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

### 163 - City Directions

I've worked hours on this problem but I still got WA.Is there any trick in this problem?Are there empty lines in the input?
By the way,I've got several test cases:
[c]
A2W S1N W
GO STRAIGHT 2
TURN LEFT
TURN LEFT
GO 2
TURN LEFT
STOP
A2W S1N W
GO STRAIGHT 2
TURN LEFT
TURN LEFT
GO 1
TURN LEFT
STOP
A2W S1N W
GO STRAIGHT 2
TURN LEFT
TURN LEFT
GO 2
STOP
A2W S1N W
GO ??????
STOP
A2W S1N W
GO 1 ?????
STOP
A2W S1N W
GO ?
STOP
A2W S1N S
TURN LEFT
GO 1
????????
STOP
END
[/c]

[c]
A2W S0 N
A3W S0 N
Illegal stopping place
A2W S1N W
A2W S1N W
A2W S1N W
Illegal stopping place
[/c]

Is this correct?
I'd be very appreciate if someone can give me more test data junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Yes.. this question is very ambiguous.. I would also like to know the answer to the data provided by FlyDeath...

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### 163 - City Directions

I seem to have some trouble understanding the question for question 163 (City Directions).. if anyone has AC for this question, can you please post your results (and any tips/hints on tricky inputs) for the following test cases?

Test data:

Code: Select all

``````A50W S49N N
TURN SHARP RIGHT
TURN SHARP LEFT
STOP

A50W S49N N
TURN RIGHT
GO 49
TURN SHARP RIGHT
TURN RIGHT
GO 2
TURN LEFT
STOP

A1W S0N E
TURN HALF LEFT
TURN SHARP LEFT
STOP

A1W S0N E
TURN RIGHT
TURN LEFT
STOP

A1W S0N E
TURN SHARP RIGHT
TURN SHARP RIGHT
TURN SHARP LEFT
STOP

A26W S24N NE
TURN LEFT
STOP

A26W S24N NE
TURN RIGHT
STOP

A26W S24N NE
TURN SHARP LEFT
STOP

A26W S24N NE
TURN SHARP RIGHT
STOP

A26W S24N NE
TURN HALF RIGHT
STOP

A26W S24N NE
TURN HALF LEFT
STOP

END
``````

Code: Select all

``````A50W S49N N: Position set: A50W S49N N
TURN SHARP RIGHT: New position: A50W S50N SE
TURN SHARP LEFT: New position: A49W S49N N
STOP: Instruction block end.
Result:  A49W S49N N

A50W S49N N: Position set: A50W S49N N
TURN RIGHT: New position: A50W S50N E
GO 49: New position: A1W S50N E
TURN SHARP RIGHT: Ignored.
TURN RIGHT: New position: A0E S50N S
GO 2: New position: A0E S48N S
TURN LEFT: New position: A0E S47N E
STOP: Instruction block end.
Result:  A0E S47N E

A1W S0N E: Position set: A1W S0N E
TURN HALF LEFT: New position: A0E S0N NE
TURN SHARP LEFT: New position: A1E S1N W
STOP: Instruction block end.
Result:  A1E S1N W

A1W S0N E: Position set: A1W S0N E
TURN RIGHT: New position: A0E S0N S
TURN LEFT: New position: A0E S1S E
STOP: Instruction block end.
Result:  A0E S1S E

A1W S0N E: Position set: A1W S0N E
TURN SHARP RIGHT: New position: A0E S0N SW
TURN SHARP RIGHT: Ignored.
TURN SHARP LEFT: New position: A1W S1S E
STOP: Instruction block end.
Result:  A1W S1S E

A26W S24N NE: Position set: A26W S24N NE
TURN LEFT: Ignored.
STOP: Instruction block end.
Result:  A26W S24N NE

A26W S24N NE: Position set: A26W S24N NE
TURN RIGHT: Ignored.
STOP: Instruction block end.
Result:  A26W S24N NE

A26W S24N NE: Position set: A26W S24N NE
TURN SHARP LEFT: New position: A25W S25N W
STOP: Instruction block end.
Result:  A25W S25N W

A26W S24N NE: Position set: A26W S24N NE
TURN SHARP RIGHT: New position: A25W S25N S
STOP: Instruction block end.
Result:  A25W S25N S

A26W S24N NE: Position set: A26W S24N NE
TURN HALF RIGHT: New position: A25W S25N E
STOP: Instruction block end.
Result:  A25W S25N E

A26W S24N NE: Position set: A26W S24N NE
TURN HALF LEFT: New position: A25W S25N N
STOP: Instruction block end.
Result:  A25W S25N N

END: End of file.
``````

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Only one test case is wrong. For the second one, my AC program outputs A2W S48N SW. The sharp right should not be ignored.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
2nd case:
A50W S49N N: Position set: A50W S49N N
TURN RIGHT: New position: A50W S50N E
GO 49: New position: A1W S50N E
TURN SHARP RIGHT: Ignored.
TURN RIGHT: New position: A0E S50N S
GO 2: New position: A0E S48N S
TURN LEFT: New position: A0E S47N E
STOP: Instruction block end.
Result: A0E S47N E

Why should the sharp right be taken? According to the question statement, "You may only enter or leave them by turning left (sharp left in the case of boulevards).".. since we are leaving a throughway into a non-throughway boulevard, shouldn't we be turning sharp left?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
For this question, my understanding of turns is this:

If you are entering a throughway from a non-throughway, the turn is only valid if and only if:

1) You are turning either left or sharp left
2) The final position after the turn is a valid position

Otherwise, as long as the final position is valid, the turn is valid.

If my understanding is wrong, please feel free to post the correct version :p

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Yes, now I remember. There is a very important thing which is not at all obvious from the problem statement: at the nine boulevard intersections, you may turn any direction you like.

I think the phrase "...which is shared by all other roads that meet at that intersection" is supposed to say this, but I don't think it succeeds very well.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Thank you very much Per! I've finally got it correct..

I agree with you.. the problem statement is completely ambiguous about how turns should be allowed and disallowed.. and the fact that you are supposed to make a turn at the NEXT intersection is completely not-mentioned...

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
Ok, I just got AC and I spent so much time on this problem that I would like to make clear what the rules are:

First check if the turn makes sense at all (i.e. there is a road in the direction you want to turn). If not then obviously the turn is NOT valid.

Next check if you are entering or exiting a throughway (remember the throughways are the dark grey streets). If you are not entering or exiting a throughway, then the turn IS valid. Entering is defined as starting the turn on a non-throughway and ending it on a throughway. Exiting is just the opposite, starting on the throughway and ending on a non-throughway.

The remaining case is that of entering or exiting. If you are at one of the nine special circle intersections, then the turn IS valid (Thanks Per).

Finally if entering or exiting the turn is valid only in the following cases:
a) The turn is SHARP LEFT and the throughway involved is a boulevard
b) The turn is (normal) LEFT and the throughway involved is NOT a boulevard

I hope this helps. If you have any other questions about it you can ask me.
I'm always willing to help, if you do the same.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<string>
using namespace std;

string direction={"N","NE","E","SE","S","SW","W","NW"};
int dir_x[]={0,1,1,1,0,-1,-1,-1};
int dir_y[]={1,1,0,-1,-1,-1,0,1};
int cx,cy,cdir;
char order;
int state1,state2;

void GO(int k)
{
cx+=k*dir_x[cdir];
cy+=k*dir_y[cdir];
}

bool LEAVE_VALIDITY(int x,int y,int turn)
{
if(state1==-1)
return (turn==6);
else
return (turn==5);
}

bool ARRIVE_VALIDITY(int x,int y,int turn)
{
if(state2==-1)
return (turn==6);
else
return (turn==5);
}

bool DIR_VALIDITY(int x,int y,int dir)
{
if(x==0 && y==0)
return true;
if(x==50 && y==50)
return (dir==5 || dir==6 || dir==4);
if(x==50 && y==0)
return (dir==7 || dir==5 || dir==0 || dir==4 || dir==6);
if(x==50 && y==-50)
return (dir==7 || dir==0 || dir==6);
if(x==0 && y==50)
return (dir==3 || dir==5 || dir==2 || dir==4 || dir==6);
if(x==0 && y==-50)
return (dir==1 || dir==7 || dir==2 || dir==0 || dir==6);
if(x==-50 && y==50)
return (dir==3 || dir==2 || dir==4);
if(x==-50 && y==0)
return (dir==1 && dir==3 || dir==0 || dir==2 || dir==4);
if(x==-50 && y==-50)
return (dir==1 || dir==0 || dir==2);

if((x-y==0 || x-y==-50 || x-y==50) && (dir==1 || dir==5))
return true;
if((x+y==0 || x+y==50 || x+y==-50) && (dir==7 || dir==3))
return true;

if(dir==0 || dir==2 || dir==4 || dir==6)
return true;

return false;
}

//return negetive if gray. -1 if ||x or y else -2. and other case 1.

int BOULVARD(int x,int y,int dir)
{
if( (y==50 || y==0 || y==-50) && (dir==2 || dir==6))
return -1;
if( (x==50 || x==0 || x==-50) && (dir==0 || dir==4))
return -1;
if(x+y==0 && (dir==7 || dir==3))
return -2;
if(x-y==0 && (dir==1 || dir==5))
return -2;
return 1;
}

bool CIRCLE(int x,int y)
{
if((x==-50 || x==0 || x==50) && (y==-50 || y==0 || y==50))
return true;
return false;
}

void  TURN(int k)
{
bool xx;

if(!DIR_VALIDITY(cx+dir_x[cdir],cy+dir_y[cdir],(cdir+k)%8))
return;

state1=BOULVARD(cx+dir_x[cdir],cy+dir_y[cdir],cdir);//
state2=BOULVARD(cx+dir_x[cdir],cy+dir_y[cdir],(cdir+k)%8);

if(state1<0 && state2>0)
xx= LEAVE_VALIDITY(cx+dir_x[cdir],cy+dir_y[cdir],k);
else if(state1>0 && state2<0)
xx=ARRIVE_VALIDITY(cx+dir_x[cdir],cy+dir_y[cdir],k);
else
xx=true;

if(xx || CIRCLE(cx+dir_x[cdir],cy+dir_y[cdir]))
{
cx+=dir_x[cdir];
cy+=dir_y[cdir];
cdir=(cdir+k)%8;
}
}

void DECODE()
{
char msg1,msg2,msg3;
int d,turn,type;

sscanf(order,"%s",msg1);

if(strcmp(msg1,"GO")==0)
{
sscanf(order,"%s%s",msg1,msg2);
if(msg2>='0' && msg2<='9')
sscanf(order,"%s%d",msg1,&d);
else
{
sscanf(order,"%s%s%d",msg1,msg2,&d);
if(strcmp(msg2,"STARIGHT")!=0)
return;
}
GO(d);
}
else if(strcmp(msg1,"TURN")==0)
{
sscanf(order,"%s%s",msg1,msg2);

if(strcmp(msg2,"LEFT")==0 || strcmp(msg2,"RIGHT")==0)
type=2;
else
{
sscanf(order,"%s%s%s",msg1,msg2,msg3);
type=3;
}

if(type==2 && strcmp(msg2,"LEFT")==0)
turn=6;
else if(type==2 && strcmp(msg2,"RIGHT")==0)
turn=2;
else if(type==3 && strcmp(msg2,"SHARP")==0 && strcmp(msg3,"LEFT")==0)
turn=5;
else if(type==3 && strcmp(msg2,"SHARP")==0 && strcmp(msg3,"RIGHT")==0)
turn=3;
else if(type==3 && strcmp(msg2,"HALF")==0 && strcmp(msg3,"LEFT")==0)
turn=7;
else if(type==3 && strcmp(msg2,"HALF")==0 && strcmp(msg3,"RIGHT")==0)
turn=1;
else
return;
TURN(turn);
}
}
void PRINT()
{
printf("A%d%c",cx*(cx<0 ? -1:1),(cx<0 ? 'W' : 'E'));
printf(" S%d%c",cy*(cy<0 ? -1:1),(cy<0 ? 'S' : 'N'));
printf(" %s\n",direction[cdir].c_str());
}

void RESULT()
{
int OK=1;
OK=BOULVARD(cx,cy,cdir);
//printf(">>>>>>>>>>>>>");
if(OK>0)
PRINT();
else
printf("Illegal stopping place\n");
}

int main()
{
char order1,order2;
char AOS,dir;
int d,i;

while(scanf("%s",order)!=EOF)
{
if(strcmp(order,"END")==0)
break;

scanf("%s%s%c",order1,order2,&AOS);

sscanf(order,"%c%d%c",&AOS,&d,&dir);
if(AOS=='A')
cx=d*(dir=='W' ? -1:1);
else
cy=d*(dir=='S' ? -1:1);

sscanf(order1,"%c%d%c",&AOS,&d,&dir);
if(AOS=='A')
cx=d*(dir=='W' ? -1:1);
else
cy=d*(dir=='S' ? -1:1);

for(i=0;i<8;i++)
if(order2==direction[i])
cdir=i;
while(gets(order))
{
if(strcmp(order,"STOP")==0)
break;
DECODE();
//			printf(">>%d %d %d\n",cx,cy,cdir);
}

RESULT();
}

return 0;
}

``````
Getting Wa. can any one help?
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
some one please give me some test case!
Self judging is the best judging!

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am
Is this case allowed? What's the AC program output?
Thanks for replies.

Code: Select all

``````A4W S1N SW
TURN RIGHT
TURN   HALF RIGHT
TURN SHARP RIGHT
GO   STRAIGHT    41
GO -32
PW
TURN   RIGHT
TURN   RIGHT
GO STRAIGHT 21
TURN HALF LEFT
TURN SHARP LEFT
GO          ON 47
TURN HALF LEFT
OPPEKEOBWFGFXRYISILEIMFGUFRZZZDWVO
TURN SHARP LEFT
TURN SHARP RIGHT
GO ON 28
GO STRAIGHT -16
TURN SHARP       RIGHT
TURN   RIGHT
TURN RIGHT
TURN HALF    LEFT
TURN       LEFT
TURN       LEFT
GO   9
GO STRAIGHT -27
TURN       LEFT
TURN   HALF RIGHT
TURN   RIGHT
TURN SHARP RIGHT
TURN HALF LEFT
TURN LEFT
TURN       LEFT
TURN LEFT
TURN HALF    LEFT
TURN       LEFT
TURN SHARP RIGHT
TURN HALF    LEFT
GARL   NYU  QK      FZ
TURN   HALF RIGHT
GO STRAIGHT 25
TURN HALF RIGHT
GO          ON 29
XTQXBWEPTNUAPCDSHYOOUOLSBXGWZSBCEM
TURN SHARP       RIGHT
TURN         SHARP           LEFT
TURN   HALF RIGHT
TURN LEFT
GO   STRAIGHT    -33
GO   STRAIGHT    25
GO ON 78
TURN   HALF RIGHT
TURN SHARP LEFT
GO   9
TURN SHARP LEFT
GO   2
TURN SHARP RIGHT
GO   STRAIGHT    -38
TURN HALF    LEFT
GO 23
GO   STRAIGHT    -14
GO ON 51
AZ  L      RR FT
TURN HALF RIGHT
QKJNBYYJUHWBLICQMTJRF
TURN SHARP       RIGHT
TURN HALF RIGHT
TURN HALF RIGHT
TURN SHARP RIGHT
GO STRAIGHT 11
TURN       LEFT
TURN HALF LEFT
TURN LEFT
GO 2
GO   STRAIGHT    -8
TURN HALF RIGHT
GO ON 27
GO ON 22
TURN HALF    LEFT
TURN SHARP       RIGHT
TURN HALF LEFT
GO 22
TURN LEFT
GLDMAMTHAESFZQAS
TURN   RIGHT
STOP
END
``````
You're never too old to become younger...

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
4 years late reply, but I think it should be "A2W S0N N " noit "A2W S0 N"