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 vector 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
vector 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.
DEFINITION
Class:LightsCube
Method:count
Parameters:int, vector
Returns:vector
Method signature:vector count(int N, vector lights)
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
0)
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.
1)
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.
2)
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.
3)
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.
4)
12
{"4 7 6", "8 0 0", "3 2 3", "7 7 2", "7 5 1",
"10 11 5", "4 9 7", "6 1 0", "10 1 1", "9 7 11",
"11 3 11", "9 0 3", "10 2 0"}
Returns: {264, 18, 303, 236, 105, 124, 216, 44, 53, 146, 126, 80, 13 }
5)
40
{"29 13 9", "4 10 34", "11 26 16", "2 33 22", "27 31 14", "36 20 8"}
Returns: {14657, 12834, 12364, 5902, 12678, 5565 }
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)2010, TopCoder, Inc. All rights reserved.