ICPC North America Championship 2021

Start

2021-08-14 07:00 AKDT

ICPC North America Championship 2021

End

2021-08-14 10:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -69 days 2:14:04

Time elapsed

3:30:00

Time remaining

0:00:00

Problem M
You be The Judge, Again

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:

$\blacksquare $

$\blacksquare $

 

$\blacksquare $

$\blacksquare $

 

$\blacksquare $

     

$\blacksquare $

$\blacksquare $

     

$\blacksquare $

 

$\blacksquare $

$\blacksquare $

 

$\blacksquare $

$\blacksquare $

Input

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

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$.

Sample Input 1 Sample Output 1
2
1 1 2 2
1 3 3 2
4 4 3 5
4 0 5 5
1
Sample Input 2 Sample Output 2
1
1 1
1 1
0