LightsCube

SRM 328 · 2006-11-29 · by _efer_

SRM 328 · 2006-11-29 · by _efer_ · Brute Force, Simple Math, Simple Search, Iteration, Simulation

Show categories

Class Name: LightsCube

Return Type: int[]

Method Name: count

Arg Types: (int, vector<string>)

Problem Statement

You have received a nice gift from a friend. It consists of some colored lights arranged in a N x N x N cube, with a light at every slot inside the cube. The position of each light is described by three coordinates (x, y, z) where x, y and z are non-negative integers less than N. The light in position (x, y, z) is adjacent to the lights at positions (x-1, y, z), (x+1, y, z), (x, y-1, z), (x, y+1, z), (x, y, z-1) and (x, y, z+1) (when these lights exist). Initially some lights (at least one) are turned on. During each second, all turned off lights adjacent to a turned on light are switched on and take its color. If a light is adjacent to more than one turned on light, it takes the lower number color. This process continues until all the lights are on.

You are given an int N and a String[] lights. The i-th element of lights is formatted as "x y z" (quotes for clarity only) and describes the position of the light of color i. Return a int[] with the same number of elements as lights, the i-th element of which represents the number of lights of color i after the process described above ends.

Constraints

N will be between 1 and 40, inclusive.
lights will contain between 1 and 50 elements, inclusive.
Each element of lights will be in the form "x y z" (quotes for clarity) where x, y and z are integers between 0 and N-1, inclusive, with no leading zeroes.
The positions in lights will be distinct.

Examples

2
{"0 0 0", "0 0 1", "0 1 0", "0 1 1", "1 0 0", "1 0 1", "1 1 0", "1 1 1"}
Returns: {1, 1, 1, 1, 1, 1, 1, 1 }

Initially all lights are on. Therefore, we end with one light of each color.

3
{"1 1 1"}
Returns: {27 }

There is only 1 light turned on, so all other 26 lights will take its color. Six lights are turned on during the first second, twelve during the second one and the last eight are turned on during the third second.

4
{"0 0 0", "3 3 3"}
Returns: {32, 32 }

The lights turned on are at opposite corners. There will never be a turned off light adjacent to lights of different colors, so we end up with an equal number of lights of each color.

5
{"0 2 4", "2 0 0", "3 4 4", "4 1 2"}
Returns: {38, 28, 32, 27 }

A turned off light might be adjacent to lights of different colors. For example, just before it turns on, the light at position (4, 3, 3) will be adjacent to lights of the last two colors. It will take the third color.

3
{"1 1 1","0 1 1","2 1 1","1 0 1","1 2 1","1 1 0","1 1 2"}
Returns: {1, 9, 9, 3, 3, 1, 1 }

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

Coding Area

Language: C++17 · define a public class LightsCube with a public method vector<int> count(int N, vector<string> lights) · 70 test cases · 2 s / 256 MB per case