実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1400 点
問題文
正整数 N と、長さ 2^N の 0 か 1 からなる数列 A_0,A_1,\ldots,A_{2^N-1} が与えられます。 2^N 個すべての S \subseteq \{0,1,\ldots,N-1 \} について、以下の条件を満たす閉曲線 C が存在するか判定し、存在する場合はひとつ構成してください。
- x = \sum_{i \in S} 2^i とする。また、点集合 B_S を \{ (i+0.5,0.5) | i \in S \} と定義する。
- 閉曲線 C を B_S を通らずに連続的に動かして、閉曲線上のすべての点の y 座標を負にするような方法が存在するならば、A_x = 1 である。
- 閉曲線 C を B_S を通らずに連続的に動かして、閉曲線上のすべての点の y 座標を負にするような方法が存在しないならば、A_x = 0 である。
出力方法に関しては、"出力" のチャプターを読んでください。
補足
C が閉曲線であるとは、次のように定義される。
- C は [0,1] から \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
と出力せよ。
存在するならば、まず 1 行目に 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 は整数 \quad (0 \leq i \leq L)
- |x_i-x_{i+1}| + |y_i-y_{i+1}| = 1 \quad (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\} のときはどのようにしても閉曲線上のすべての点の y 座標を負にすることはできません。
入力例 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
Score : 1400 points
Problem Statement
Given are a positive integer N and a sequence of length 2^N consisting of 0s and 1s: A_0,A_1,\ldots,A_{2^N-1}. Determine whether there exists a closed curve C that satisfies the condition below for all 2^N sets S \subseteq \{0,1,\ldots,N-1 \}. If the answer is yes, construct one such closed curve.
- Let x = \sum_{i \in S} 2^i and B_S be the set of points \{ (i+0.5,0.5) | i \in S \}.
- If there is a way to continuously move the closed curve C without touching B_S so that every point on the closed curve has a negative y-coordinate, A_x = 1.
- If there is no such way, A_x = 0.
For instruction on printing a closed curve, see Output below.
Notes
C is said to be a closed curve if and only if:
- C is a continuous function from [0,1] to \mathbb{R}^2 such that C(0) = C(1).
We say that a closed curve C can be continuously moved without touching a set of points X so that it becomes a closed curve D if and only if:
- There exists a function f : [0,1] \times [0,1] \rightarrow \mathbb{R}^2 that satisfies all of the following.
- f is continuous.
- f(0,t) = C(t).
- f(1,t) = D(t).
- f(x,t) \notin X.
Constraints
- 1 \leq N \leq 8
- A_i = 0,1 \quad (0 \leq i \leq 2^N-1)
- A_0 = 1
Input
Input is given from Standard Input in the following format:
N A_0A_1 \cdots A_{2^N-1}
Output
If there is no closed curve that satisfies the condition, print Impossible
.
If such a closed curve exists, print Possible
in the first line.
Then, print one such curve in the following format:
L x_0 y_0 x_1 y_1 : x_L y_L
This represents the closed polyline that passes (x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L) in this order.
Here, all of the following must be satisfied:
- 0 \leq x_i \leq N, 0 \leq y_i \leq 1, and x_i, y_i are integers. (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).
Additionally, the length of the closed curve L must satisfy 0 \leq L \leq 250000.
It can be proved that, if there is a closed curve that satisfies the condition in Problem Statement, there is also a closed curve that can be expressed in this format.
Sample Input 1
1 10
Sample Output 1
Possible 4 0 0 0 1 1 1 1 0 0 0
When S = \emptyset, we can move this curve so that every point on it has a negative y-coordinate.
When S = \{0\}, we cannot do so.
Sample Input 2
2 1000
Sample Output 2
Possible 6 1 0 2 0 2 1 1 1 0 1 0 0 1 0
The output represents the following curve:
Sample Input 3
2 1001
Sample Output 3
Impossible
Sample Input 4
1 11
Sample Output 4
Possible 0 1 1