TopCoder problem "PlaneFractal" used in TCO09 Round 2 (Division I Level One)



Problem Statement

    A plane fractal grows in the following way. At time 0, the fractal is a single white square. During each unit of time, each square in the fractal is divided into an NxN grid of equal subsquares. If the square was white, then the center KxK subsquares will become black (N and K will have the same parity).



For example, if N = 3 and K = 1, then at time 1, there are 3x3 squares, the middle square is black and the rest are white. At time 2, there are 9x9 squares, 17 are black and the rest are white.







Return a String[] representing the content of the fractal at time s between rows r1 and r2, inclusive, and columns c1 and c2, inclusive (all indices are 0-based). White squares should be represented by '0' (zero) and black squares should be represented by '1'.
 

Definition

    
Class:PlaneFractal
Method:getPattern
Parameters:int, int, int, int, int, int, int
Returns:String[]
Method signature:String[] getPattern(int s, int N, int K, int r1, int r2, int c1, int c2)
(be sure your method is public)
    
 

Constraints

-s will be between 0 and 10, inclusive.
-N will be between 3 and 8, inclusive.
-K will be between 1 and N-2, inclusive.
-N and K will have the same parity, i.e., N-K will be divisible by 2.
-r1, r2, c1 and c2 will each be between 0 and N^s-1, inclusive.
-r2 will be between r1 and r1+49, inclusive.
-c2 will be between c1 and c1+49, inclusive.
 

Examples

0)
    
1
5
3
0
4
0
4
Returns: {"00000", "01110", "01110", "01110", "00000" }
At time 1, there are 5x5 squares, the middle 3x3 of them are black.
1)
    
2
3
1
0
8
0
8
Returns: 
{"000000000",
"010010010",
"000000000",
"000111000",
"010111010",
"000111000",
"000000000",
"010010010",
"000000000" }
The example from the problem statement.
2)
    
3
3
1
4
11
5
10
Returns: 
{"101001",
"100000",
"000000",
"001001",
"000000",
"000011",
"001011",
"000011" }
At time 3, the fractal looks like this (the area that needs to be returned is shown in red):



3)
    
2
8
4
56
61
33
56
Returns: 
{"000000000000000000000000",
"000000000000000000000000",
"011110000111100001111000",
"011110000111100001111000",
"011110000111100001111000",
"011110000111100001111000" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10333

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13760&pm=10333

Writer:

Nickolas

Testers:

PabloGilberto , marian , ivan_metelsky

Problem categories:

Brute Force, Simple Math