Connection Status:
Competition Arena > AntsMeet

AntsMeet

SRM 541 · 2011-11-22 · by semiexp

SRM 541 · 2011-11-22 · by semiexp · Simulation
Class Name: AntsMeet
Return Type: int
Method Name: countAnts
Arg Types: (vector<int>, vector<int>, string)
Problem Statement

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.

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)
{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.

1)
{-10,0,0,10}
{0,-10,10,0}
"NEWS"
Returns: 0

More than two ants can meet at the same time.

2)
{0,9,0,0}
{0,0,4,5}
"EWSS"
Returns: 2
3)
{-1,1,0,-1,1,0,0,-1,1}
{0,0,0,-1,-1,1,-1,1,1}
"EENWWSWSE"
Returns: 5
4)
{-2,-3,-2,1,-3}
{-1,-1,-3,3,-2}
"SWNSE"
Returns: 2
5)
{-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.

Submissions are judged against all 119 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AntsMeet with a public method int countAnts(vector<int> x, vector<int> y, string direction) · 119 test cases · 2 s / 256 MB per case

Submitting as anonymous