Connection Status:
Competition Arena > ThreeNeighbors

ThreeNeighbors

TCO20 Round 1A · 2020-04-13 · by misof

TCO20 Round 1A · 2020-04-13 · by misof · Greedy, Simple Math, Simulation
Class Name: ThreeNeighbors
Return Type: String[]
Method Name: construct
Arg Types: (int)
Problem Statement

Problem Statement

Game of Life is a cellular automaton invented by the recently deceased mathematician John H. Conway. We included this problem into today's set to honor his memory.

In our version of the Game of Life the world is a rectangular array of cells. Each cell is either alive ('X') or dead ('.'). Each cell has up to eight neighbors: horizontal, vertical, and diagonal. Cells at the boundary have fewer than eight neighbors.

The world evolves in steps. In each step some living cells may die and some dead cells may become alive. In particular, a cell that is currently dead will become a living cell in the next step if and only if it currently has exactly three neighbors that are alive.

You are given the int N. Find any rectangular configuration of cells with dimensions at most 50x50 and with the following property: in the next step, exactly N of the dead cells will become living cells. Return your configuration as a String[].

Notes

  • For the given constraints a solution always exists, and any valid solution will be accepted.
  • We only care about the number of cells that change from dead to living. All other parameters of your world (dimensions, the number of cells that die, the total number of cells, etc.) may be arbitrary.

Constraints

  • N will be between 1 and 500, inclusive.
Examples
0)
2
Returns: {".....", ".XX..", ".X.X.", ".X...", "....." }

The return value corresponds to a configuration of cells known as a "glider": ..... .XX.. .X.X. .X... ..... Below, the two cells that will become alive in the next step are marked with asterisks. Each of these dead cells has exactly three neighbors that are alive. ..... .XX.. *X.X. .X*.. .....

1)
6
Returns: {"........", ".XXX..X.", "..X..X..", "..X..X..", "..X...X.", "........" }

..*..... .XXX..X. ..X.*X*. .*X*.X*. ..X...X. ........

2)
1
Returns: {"XXXX", "XXXX", ".XXX" }

XXXX XXXX *XXX

3)
3
Returns: {"..................................................", "XXX...............................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "................................................XX", "................................................X." }
4)
4
Returns: {"..................................................", "XXXX..............................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".................................................." }

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

Coding Area

Language: C++17 · define a public class ThreeNeighbors with a public method vector<string> construct(int N) · 69 test cases · 2 s / 256 MB per case

Submitting as anonymous