AntsMeet | Topcoder Archive

Problem Statement

Magical Girl Lein is observing ants.
There are N ants. At first, they have integer coordinates in the Cartesian plane. More precisely, ant i starts at the point (x[i], y[i]). All ants move at the same speed. Each ant moves in one of the four basic directions. (I.e., either parallel to the x axis or parallel to the y axis.) When 2 or more ants meet at the same time, these ants disappear.

You are given two int[]s x and y, containing N elements each, and a String direction, containing N characters. Character i of direction encodes the direction in which ant i is going:

'N' means north (y coordinate increases),
'E' means east (x coordinate increases),
'S' means south (y coordinate decreases),
and 'W' means west (x coordinate decreases).

Return the number of ants that still exist after the last meeting occurs.

Definition

Class:: AntsMeet
Method:: countAnts
Parameters:: int[], int[], String
Returns:: int
Method signature:: int countAnts(int[] x, int[] y, String direction)
(be sure your method is public)

Constraints

x will contain between 1 and 50 elements, inclusive.
y will contain the same number of elements as x.
The number of characters in direction will be the same as the number of elements in x.
Each element of x and y will be between -1000 and 1000, inclusive.
No pair of points in the input will be equal.
Each character of direction will be one of 'N', 'E', 'W' and 'S'.

Examples

```
{0,10,20,30}
```
```
{0,10,20,30}
```
```
"NWNE"
```
```
Returns: 2
```
The ants that start at (0,0) and (10,10) will meet at (0, 10) at time 10. The remaining two ants will never meet.
```
{-10,0,0,10}
```
```
{0,-10,10,0}
```
```
"NEWS"
```
```
Returns: 0
```
More than two ants can meet at the same time.
```
{-1,-1,-1,0,0,0,1,1,1}
```
```
{-1,0,1,-1,0,1,-1,0,1}
```
```
"ESEWNNEWW"
```
```
Returns: 4
```
The ants that start at (-1,-1) and (0,-1) will meet at (-0.5,-1). The ants that start at (-1,1), (0,0) and (1,1) will meet at (0,1). Thus, 4 ants will remain after all meetings. Note that ants that start at (-1,0) and (0,-1) won't meet at (-1,1) because one of them will disappear before reaching the meeting point.

{4,7,6,2,6,5,7,7,8,4,7,8,8,8,5,4,8,9,1,5,9,3,4,0,0,1,0,7,2,6,9,6,3,0,5,5,1,2,0,4,9,7,7,1,8,1,9,2,7,3}

{2,3,0,6,8,4,9,0,5,0,2,4,3,8,1,5,0,7,3,7,0,9,8,1,9,4,7,8,1,1,6,6,6,2,8,5,1,9,0,1,1,1,7,0,2,5,4,7,5,3}

"SSNWSWSENSWSESWEWSWSENWNNNESWSWSWWSSWEEWWNWWWNWENN"

Returns: 25

{478,-664,759,434,-405,513,565,-396,311,-174,56,993,251,-341,993,-112,242,129,383,513,-78,-341,-148,129,423
,493,434,-405,478,-148,929,251,56,242,929,-78,423,-664,802,251,759,383,-112,-591,-591,-248,660,660,735,493}

{-186,98,948,795,289,-678,948,-170,-195,290,-354,-424,289,-157,-166,150,706,-678,684,-294,-234,36,36,-294,-216
,-234,427,945,265,-157,265,715,275,715,-186,337,798,-170,427,706,754,961,286,-216,798,286,961,684,-424,337}

"WNSNNSSWWWEENWESNSWSWSEWWEWEWWWNWESNSSNNSNNWWWNESE"

Returns: 44

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.