分数: 1400 点
问题陈述
给定一个正整数 N 和长度序列 2^N 组成 0和 1s: A_0,A_1,\ldots,A_{2^N-1}。 判断是否存在闭合曲线 C 满足以下所有条件 2^N 套 S \subseteq \{0,1,\ldots,N-1 \}。如果答案是肯定的,则构建一条这样的闭合曲线。
- 让 x = \sum_{i \in S} 2^i 和 B_S 是点的集合 \{ (i+0.5,0.5) | i \in S \}.
- 如果有办法让闭合曲线连续移动 C 无需触摸 B_S 使得闭合曲线上的每个点都有负值 y- 坐标, A_x = 1.
- 如果没有这样的办法, A_x = 0.
有关打印闭合曲线的说明,请参阅下面的输出。
注释
C 被称为闭合曲线当且仅当:
- C 是一个连续函数 [0,1] to \mathbb{R}^2 这样 C(0) = C(1).
我们说一条闭合曲线 C 可以连续移动而不接触一组点 X 使其成为闭合曲线 D 当且仅当:
- 存在一个函数 f : [0,1] \times [0,1] \rightarrow \mathbb{R}^2 满足以下所有条件。
- f 是连续的。
- f(0,t) = C(t).
- f(1,t) = D(t).
- f(x,t) \notin X.
约束
- 1 \leq N \leq 8
- A_i = 0,1 \quad (0 \leq i \leq 2^N-1)
- A_0 = 1
输入
输入由标准输入按以下格式给出:
N
A_0A_1 \cdots A_{2^N-1}
输出
如果没有满足条件的闭合曲线,则打印 Impossible.
如果存在这样的闭合曲线,则打印 Possible 在第一行。
然后,按以下格式打印一条这样的曲线:
L x_0 y_0 x_1 y_1 : x_L y_L
这表示通过的闭合折线 (x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L) 按此顺序。
此处,必须满足以下所有条件:
- 0 \leq x_i \leq N, 0 \leq y_i \leq 1,和 x_i, y_i 是整数。 (0 \leq i \leq L)
- |x_i-x_{i+1}| + |y_i-y_{i+1}| = 1. (0 \leq i \leq L-1)
- (x_0,y_0) = (x_L,y_L).
另外,闭合曲线的长度 L 必须满足 0 \leq L \leq 250000.
可以证明,如果存在满足问题陈述中条件的闭合曲线,则也存在可以用这种格式表示的闭合曲线。
示例输入 1
1 10
示例输出 1
Possible 4 0 0 0 1 1 1 1 0 0 0
当 S = \emptyset,我们可以移动这条曲线,使其上的每个点都有负数 y- 坐标。

当 S = \{0\},我们不能这样做。

示例输入 2
2 1000
示例输出 2
Possible 6 1 0 2 0 2 1 1 1 0 1 0 0 1 0
输出代表以下曲线:

示例输入 3
2 1001
示例输出 3
Impossible
示例输入 4
1 11
示例输出 4
Possible 0 1 1