163 - City Directions

[wyvmak]

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]

I don't no the answer
I just want to tell that I've got the same problem: maybe someone knows for sure that test in this problem wrong?

[FlyDeath]

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]

My answer is:
[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]

Yes.. this question is very ambiguous.. I would also like to know the answer to the data provided by FlyDeath...

[junbin]

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

My output (along with comments)

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]

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]

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]

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]

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]

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]

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.

[shanto86]

Code: Select all

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

string direction[10]={"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[100];
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[100],msg2[100],msg3[100];
	int d,turn,type;

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

	if(strcmp(msg1,"GO")==0)
	{
		sscanf(order,"%s%s",msg1,msg2);
		if(msg2[0]>='0' && msg2[0]<='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[100],order2[100];
	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?

[shanto86]

some one please give me some test case!

[ar2rd]

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

[yiuyuho]

4 years late reply, but I think it should be "A2W S0N N " noit "A2W S0 N"