411 - Centipede Collisions

[afonsocsc]

Everything looks ok, but it gives wa, don't know what's wrong...
[c]
...
[/c]

[afonsocsc]

solved!

[Jan]

Can you please answer the following questions...

1. Suppose we have two centipedes,

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 1 1 1 2 2 2 2 2 . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
***
Here 1 is moving towards right and 2 is moving left.

Now what should be the answer?

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . X . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Or

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . X X . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Again if we have..

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 1 1 1 . . X . . . . . . . . . . . . . 2 2 2 . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
***
Here 1 is moving towards right and 2 is moving left.

What will be the answer?

3. And if we have...

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 1 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . 2 . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . 2 . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
***
Here 1 is moving towards right and 2 & 3 both are moving up.

Now what will be the answer?

4. And if we have...

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 1 1 1 1 . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . 2 . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . 2 . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
***
Here 1 is moving towards right and 2 & 3 both are moving up.

Now what will be the answer?

Thanks in advance...

[afonsocsc]

Hi

1.
The collision occurs when 1, that moves first, hits 2, and since when a centipede segment collides with a collision site it becomes part of the collision, the answer will be:

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . X . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.
Both collide with the collision site:

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . X . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
***

3.
1 moves left, then 2 hits 1, and 3 goes up till it falls:

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . X . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
***

4.
Since 1 is the first to move, 2 will collide with 1's second segment:

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 1 1 X 1 . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . 2 . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
***

and the first segment of 1 goes right and collides with the second segment of 3:

Code: Select all

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . X . . X . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
***

Hope it helps!

[Jan]

Thanks afonso for answering so quickly....

You wrote...

3.
1 moves left, then 2 hits 1, and 3 goes up till it falls:

Here shouldn't it be...

3.
1 moves right, then 2 hits 1, and 3 goes up till it falls:

I think it is a silly mistake..nothing more...

You have made it so clear that I donot have to read the description again....

Thank you again.

[Jan]

I got Accepted...

Thank you again.

[afonsocsc]

Great!
Glad that I could help

[Wei-Ming Chen]

The input of ACM 411 is

Code: Select all

10
R 9 11 23   ->0
U 8 11 17   ->1
U 5 15 15   ->2
U 5 15 8    ->3
D 9 23 13   ->4
U 6 23 6    ->5
R 9 8 9     ->6
L 13 17 0   ->7
U 12 13 11  ->8
L 5 20 9    ->9

First, it was like that

Code: Select all

   0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
29 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23 . . . 0 0 0 0 0 0 0 0 0 . . . . . . . . . . . . . . . . . .
22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21 . . . . . . . . . . . . . . . . . . . . . . . 4 . . . . . .
20 . . . . . . . . . . . . . . . . . . . . . . . 4 . . . . . .
19 . . . . . . . . . . . . . . . . . . . . . . . 4 . . . . . .
18 . . . . . . . . . . . . . . . . . . . . . . . 4 . . . . . .
17 . . . . . . . . . . . 1 . . . . . . . . . . . 4 . . . . . .
16 . . . . . . . . . . . 1 . . . . . . . . . . . 4 . . . . . .
15 . . . . . . . . . . . 1 . . . 2 . . . . . . . 4 . . . . . .
14 . . . . . . . . . . . 1 . . . 2 . . . . . . . 4 . . . . . .
13 . . . . . . . . . . . 1 . . . 2 . . . . . . . 4 . . . . . .
12 . . . . . . . . . . . 1 . . . 2 . . . . . . . . . . . . . .
11 . . . . . . . . . . . 1 . 8 . 2 . . . . . . . . . . . . . .
10 . . . . . . . . . . . 1 . 8 . . . . . . . . . . . . . . . .
09 6 6 6 6 6 6 6 6 6.  . . . 8 . . . . . . 9 9 9 9 9 . . . . .
08 . . . . . . . . . . . . . 8 . 3 . . . . . . . . . . . . . .
07 . . . . . . . . . . . . . 8 . 3 . . . . . . . . . . . . . .
06 . . . . . . . . . . . . . 8 . 3 . . . . . . . 5 . . . . . .
05 . . . . . . . . . . . . . 8 . 3 . . . . . . . 5 . . . . . .
04 . . . . . . . . . . . . . 8 . 3 . . . . . . . 5 . . . . . .
03 . . . . . . . . . . . . . 8 . . . . . . . . . 5 . . . . . .
02 . . . . . . . . . . . . . 8 . . . . . . . . . 5 . . . . . .
01 . . . . . . . . . . . . . 8 . . . . . . . . . 5 . . . . . .
00 . . . . . . . . . . . . . 8 . . . 7 7 7 7 7 7 7 7 7 7 7 7 7

And 0 and 1 will meet at (23,11)
0 and 2 will meet at (23,15)
But 2 and 3 ? I thought they will meet.
The sample output tells "No"
Can someone tell me why 2 and 3 didn't meet? Thanks

[Jan]

2 and 3 both are facing upwards. Imagine that all are moving at the same time. So, they cant meet.