시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 2048 MB (추가 메모리 없음) | 87 | 55 | 33 | 54.098% |
You are a judge, again! The contest you're judging includes the following problem:
You have one L-shaped triomino of each of $\frac{4^n-1}{3}$ different colors. Tile a $2^n$ by $2^n$ grid using each of these triominos such that there is exactly one blank square and all other squares are covered by exactly one square of such a triomino. All triominos must be used."
Your team is to write a checker for this problem. Validation of the input values and format has already taken place. You will be given a purported tiling of a $2^n$ by $2^n$ grid, where each square in the grid is either 0 or a positive integer from $1$ to $\frac{4^n-1}{3}$ representing one of the colors. Determine if it is, indeed, a covering of the grid with $\frac{4^n-1}{3}$ unique triominos and a single empty space.
L-shaped triominos look like this:
The first line of input contains a single integer $n$ ($1 \le n \le 10$), which is the $n$ of the description.
Each of the next $2^n$ lines contains $2^n$ integers $x$ ($0 \le x \le \frac{4^n-1}{3}$), where 0 represents an empty space, and any positive number is a unique identifier of a triomino.
Output a single integer, which is $1$ if the given grid is covered with $\frac{4^n-1}{3}$ unique triominos and a single empty space. Otherwise, output $0$.
2 1 1 2 2 1 3 3 2 4 4 3 5 4 0 5 5
1
1 1 1 1 1
0
ICPC > Regionals > North America > North America Championship > North America Championship 2021 M번
Camp > Petrozavodsk Programming Camp > Summer 2021 > Day 2: The American Contest M번