AndPicture
TCO 2014 Wildcard · 2014-03-26 · by rng_58
TCO 2014 Wildcard · 2014-03-26 · by rng_58 · Simple Search, Iteration
Problem Statement
Problem Statement
Cat Snuke likes drawing pictures.
He came up with a new way to draw interesting pictures. First, he chooses an integer n and two permutations of integers between 0 and 2^n-1, inclusive, p and q. Then, he prepares a board divided into 2^n x 2^n cells. The cell at the intersection of the i-th row and the j-th column (both 0-based) is called cell (i, j). He paints the cell (i, j) black if (p[i] AND q[j]) is nonzero. Otherwise he paints the cell white. (Here AND is the bitwise AND operator).
You are given anint n and a String[] picture.
The j-th character of the i-th element of picture represents the color of the cell (i, j): '1' represents black and '0' white.
Determine whether Snuke can draw this picture using the method described above. Return "Possible" if this is possible and "Impossible" otherwise.
He came up with a new way to draw interesting pictures. First, he chooses an integer n and two permutations of integers between 0 and 2^n-1, inclusive, p and q. Then, he prepares a board divided into 2^n x 2^n cells. The cell at the intersection of the i-th row and the j-th column (both 0-based) is called cell (i, j). He paints the cell (i, j) black if (p[i] AND q[j]) is nonzero. Otherwise he paints the cell white. (Here AND is the bitwise AND operator).
You are given an
Constraints
- n will be between 1 and 6, inclusive.
- picture will contain exactly 2^n elements.
- Each element of picture will contain exactly 2^n elements.
- Each character in each element of picture will be either '0' or '1'.
Examples
0)
2
{"0011",
"1010",
"0000",
"1011"}
Returns: "Possible"
For example, Snuke can draw this picture by choosing the two permutations p = {1, 2, 0, 3} and q = {2, 0, 3, 1}.
1)
2
{"0011",
"1000",
"0001",
"1011"}
Returns: "Impossible"
Snuke can't draw this picture.
2)
1
{"01",
"00"}
Returns: "Possible"
3)
1
{"00", "01"}
Returns: "Possible"
4)
1
{"01", "00"}
Returns: "Possible"
64)
4
{"0000000000000000",
"0000011111100000",
"0000000110000000",
"0000000110000000",
"0000000110000000",
"0000000000000000",
"0000011111000000",
"0000110000000000",
"0000110000000000",
"0000011111000000",
"0000000000000000",
"0000001111100000",
"0000011000110000",
"0000011000110000",
"0000001111100000",
"0000000000000000"}
Returns: "Impossible"
TCO.
Submissions are judged against all 65 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class AndPicture with a public method string isPossible(int n, vector<string> picture) · 65 test cases · 2 s / 256 MB per case