Connection Status:
Competition Arena > PointLifeGame

PointLifeGame

SRM 221 · 2004-12-01 · by AdminBrett

SRM 221 · 2004-12-01 · by AdminBrett · Simulation, Sorting
Class Name: PointLifeGame
Return Type: String
Method Name: simulate
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Given a set S of points in the plane we can generate a new set T in the following fashion:
  • 1) For all distinct points p and q in S, the midpoint of the line segment from p to q should be added to T.
  • 2) Remove all duplicate points in T so that there is only one copy of each point in T.
The process used to convert S into T is called a round.

You will be given int[]s xs and ys denoting the points contained in S. Point i will have x-coordinate xs[i] and y-coordinate ys[i]. After applying rnds rounds to S, you will return the best point. One point is better than another if it has a larger y-coordinate. In case of a tie, the point with the larger x-coordinate is then better. The returned point should have the form (quotes for clarity) "x y" where x and y denote the x and y coordinates respectively. Each coordinate has the format (quotes for clarity) "####.####". In other words, there should be exactly 4 digits before the decimal place and 4 digits afterward. When necessary, round down to the nearest ten-thousandth.

Constraints

  • xs must contain between 3 and 50 elements inclusive.
  • ys must contain the same number of elements as xs.
  • Each element of xs will be between 0 and 5000 inclusive.
  • Each element of ys will be between 0 and 5000 inclusive.
  • rnds must be between 1 and 10 inclusive.
  • Each given point will be distinct.
Examples
0)
{0,0,10,10}
{0,10,0,10}
1
Returns: "0005.0000 0010.0000"

The given points are arranged in a 10 by 10 square. After 1 round the best point lies on the middle of the top edge of the original square.

1)
{0,0,10,10}
{0,10,0,10}
10
Returns: "0005.0097 0007.5000"

Same as before, but now there are 10 rounds.

2)
{0,10,20}
{0,10,0}
1
Returns: "0015.0000 0005.0000"

Here we have a triangular arrangement. After 1 round the best point lies on the upper right edge of the original triangle.

3)
{0,10,20}
{0,10,0}
1
Returns: "0015.0000 0005.0000"
4)
{1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10}
{1,1,1,1,1,1,1,1,1,1, 
 2,2,2,2,2,2,2,2,2,2,
 3,3,3,3,3,3,3,3,3,3,
 4,4,4,4,4,4,4,4,4,4,
 5,5,5,5,5,5,5,5,5,5}
10
Returns: "0009.0009 0005.0000"
17)
{5,0,1,1}
{8,0,9,7}
10
Returns: "0002.3310 0008.0019"

{8,0,9,7} 10

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

Coding Area

Language: C++17 · define a public class PointLifeGame with a public method string simulate(vector<int> xs, vector<int> ys, int rnds) · 80 test cases · 2 s / 256 MB per case

Submitting as anonymous