In author's solution the fractal is built by a recursive function. Let ''a'' be a square nk × nk result matrix. Write the recursive function fractal(x, y, k) filling a square part of the matrix with an upper left corner in (x, y) and a length of the side nk, drawing the fractal of depth k. In case k = 0 put ''.'' at the current position. Otherwise you have to divide the part of the matrix into n2 square parts with size nk - 1 × nk - 1, and fill them according to the model. If the corresponding symbol in the model is ''*'', fill the square with symbols ''*'', otherwise execute fractal(x1, y1, k-1) for (x1, y1) being the coordinates of the upper left corner of the new square.
kdalex offers a solution (http://codeforces.net/blog/entry/764), which is easier in implementation. Consider all positions (x, y). If for some c = nd, 0 ≤ d < k the square ((x/c)%n, (y/c)%n) of the model is black then (x, y) must be black, otherwise it is white. It is easy to check that if the square ((x/c)%n, (y/c)%n) is black for d = k - 1 , then we have that the current position (x, y) is in the black square after the first step of the algorithm. If ((x/c)%n, (y/c)%n) is black for d = k - 2, it happens after the second step, etc.
Comments (0)
