11359 - Guards, Imbecile Guards

All about problems in Volume 113. 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
baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

11359 - Guards, Imbecile Guards

Post by baodog »

"You are caught by a guard if both of you land on the same cell at the same time or if you bump into each other during a move. In the latter case, you are caught in between the cells."

What does it mean by "bump into each other"?
Caught in between what cells? What are "the cells" ?
An example is greatly appreciated.

Thanks in advance.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah »

An example is the following:

P - your position
X - enemy

.....
.PX..
.....

X's direction is to the left and you decide to go to the right:

.....
.XP..
.....

This is forbidden because you jump over X and he jumps over you.

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

Re: 11359

Post by sohel »

baodog wrote: What does it mean by "bump into each other"?
Caught in between what cells? What are "the cells" ?
Well, every point on the grid is considered as a cell. I didn't explicitly mention it since I thought it's obvious.
Sorry for the confusion caused.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

WR

Post by sapnil »

I am trying with BFS,But till WR.
Can any one tell me whats wrong here:

My code:

Code: Select all

//                        Removed
Thanks
Keep posting
Sapnil
Last edited by sapnil on Tue Nov 27, 2007 5:18 am, edited 1 time in total.
"Dream Is The Key To Success"

@@@ Jony @@@

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I don't see why your algorithm can actually return the correct answer.
The correct states for the BFS should be (x,y,t) where (x,y) are the current position, and t is the time since beginning mod L, where L is the lcm of the guard's cycle lengths.

Anders
New poster
Posts: 6
Joined: Mon Jan 12, 2004 8:09 am
Location: Russia
Contact:

Post by Anders »

jah wrote:An example is the following:

P - your position
X - enemy

.....
.PX..
.....

X's direction is to the left and you decide to go to the right:

.....
.XP..
.....

This is forbidden because you jump over X and he jumps over you.
That still does not answer whether this is possible:

PX
..

to

X.
P.

It all depends on the size of the persons. If they can be described by circles of a maximum radius of 1/sqrt(8) this move should be legal (as the distance of their centers is 1/sqrt(2) after t=0.5s), but if they are more similar to squares occupying most of the cells their corners would bump into each other.

So which is it?

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

Post by sohel »

Anders wrote: It all depends on the size of the persons. If they can be described by circles of a maximum radius of 1/sqrt( 8 ) this move should be legal (as the distance of their centers is 1/sqrt(2) after t=0.5s), but if they are more similar to squares occupying most of the cells their corners would bump into each other.

So which is it?
Hmm.. You have a point!

Your case is a valid one. It is possible.
The player is caught if he shares the same cell with a guard in a particular time or if they exchange places in an unit time interval.

And one gets the feeling that bump into each other means there is a head-on collision :) .

Post Reply

Return to “Volume 113 (11300-11399)”