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 an int 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 int 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.
Definition
- Class:
- AndPicture
- Method:
- isPossible
- Parameters:
- int, String[]
- Returns:
- String
- Method signature:
- String isPossible(int n, String[] picture)
- (be sure your method is public)
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
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}.2
{"0011", "1000", "0001", "1011"}Returns: "Impossible"
Snuke can't draw this picture.1
{"01", "00"}Returns: "Possible"
3
{"01010011", "11110111", "11110011", "00000000", "11110101", "11010111", "11110000", "11000101"}Returns: "Possible"
4
{"0000000000000000", "0000011111100000", "0000000110000000", "0000000110000000", "0000000110000000", "0000000000000000", "0000011111000000", "0000110000000000", "0000110000000000", "0000011111000000", "0000000000000000", "0000001111100000", "0000011000110000", "0000011000110000", "0000001111100000", "0000000000000000"}Returns: "Impossible"
TCO.
Back to all problems