AT_abc288_g [ABC288G] 3^N Minesweeper

题目描述

在位置 $0,\ 1,\ 2,\ \ldots,\ 3^N-1$ 上，每个位置上有 $0$ 个或 $1$ 个炸弹。
另外，当且仅当对于 $i=0,1,\ldots,N-1$，下述条件都成立时，位置 $x$ 和位置 $y$ 被认为是相近的位置。

• 将 $x,\ y$ 用 $3$ 进制表示后，$3^i$ 位上的数字分别为 $x',\ y'$，若 $|x'-y'|\leq 1$，则条件成立。

已知每个位置 $i$ 及其所有相近位置上的炸弹总数为 $A_i$。请输出一种可能的炸弹分布方案。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_0$ $A_1$ $\ldots$ $A_{3^N-1}$

输出格式

请输出 $B_0,\ B_1,\ldots,B_{3^N-1}$，其中 $B_i=0$ 表示位置 $i$ 没有炸弹，$B_i=1$ 表示位置 $i$ 有炸弹。各数值用空格分隔。

输入输出样例 #1

输入 #1

1
0 1 1

输出 #1

0 0 1

输入输出样例 #2

输入 #2

2
2 3 2 4 5 3 3 4 2

输出 #2

0 1 0 1 0 1 1 1 0

输入输出样例 #3

输入 #3

2
0 0 0 0 0 0 0 0 0

输出 #3

0 0 0 0 0 0 0 0 0

说明/提示

限制条件

• $1\leq N\leq 12$
• 存在满足 $A_0,A_1,\ldots,A_{3^N-1}$ 的炸弹分布方案
• 输入均为整数

样例解释 1

$0$ 的相近位置为 $0$ 和 $1$，这两个位置上的炸弹总数为 $0$。$1$ 的相近位置为 $0,1,2$，这三个位置上的炸弹总数为 $1$。$2$ 的相近位置为 $1$ 和 $2$，这两个位置上的炸弹总数为 $1$。只有 $2$ 处有炸弹的分布方案满足上述所有条件，因此这是一个正确答案。

由 ChatGPT 4.1 翻译