← 返回题目列表

AtCoder · agc043_e

E. 拓扑

中文机器翻译题面 查看原题

分数: 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