PlaneFractal
TCO09 Round 2 · 2009-02-24 · by Nickolas
TCO09 Round 2 · 2009-02-24 · by Nickolas · Brute Force, Simple Math
Problem Statement
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 aString[] 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'.
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
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" }
4)
0
8
2
0
0
0
0
Returns: {"0" }
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PlaneFractal with a public method vector<string> getPattern(int s, int N, int K, int r1, int r2, int c1, int c2) · 78 test cases · 2 s / 256 MB per case