Problem:
 Score : 1400 points    Problem Statement Given are a positive integer N and a sequence of length 2^N consisting of 0 s and 1 s: 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

Solution (Python):
n = int(input())
a = [int(x) for x in input()]

holes = []

for i in range(2**n):
    if a[i] == 1:
        continue
    for j in range(i+1, 2**n):
        if (j | i) == j and a[j] == 1:
            print("Impossible")
            exit()
    if any((k | i) == i for k in holes):
        continue
    else:
        holes.append(i)

print("Possible")
if len(holes) == 0:
    print(0)
    print(1, 1)
    exit()

clockwise = []

for i in range(n):
    locus = []
    for j in range(i+1):
        locus.append((j, 0))
    locus += [(i, 1), (i+1, 1), (i+1, 0)]
    for j in range(i, -1, -1):
        locus.append((j, 0))
    clockwise.append(locus)

m = len(holes)
roops = []

for i in range(m):
    x = holes[i]
    curve = []
    is_first = True
    for j in range(n):
        if (x >> j) & 1 and is_first:
            curve += clockwise[j]
            is_first = False
        elif (x >> j) & 1:
            curve = curve + clockwise[j] + curve[::-1] + clockwise[j][::-1]
    roops.append(curve)

ans = []
for x in roops:
    ans += x

L = -1
for i, x in enumerate(ans):
    if i > 0 and ans[i] == ans[i-1]:
        continue
    else:
        L += 1

print(L)
for i, x in enumerate(ans):
    if i > 0 and ans[i] == ans[i-1]:
        continue
    else:
        print(*x)

Solution (Python):
res = []

n = int(input())
a = [int(c) for c in input()]

def solve():
    if a[0] == 0:
        return False
    for x in range(1, 2**n):
        s = list(filter(lambda i: (x >> i) & 1, range(n)))
        xl = [(x >> i) & 1 for i in range(n)]
        if a[x] == 0:
            for d in s:
                y = x ^ (1 << d)
                if a[y] == 1:
                    break
            else:
                continue
            def move_ceiling(r, dest):
                i, j = r[-1]
                if i < dest:
                    for i in range(i, dest):
                        if xl[i] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i + 1, j))
                else:
                    for i in range(i, dest, -1):
                        if xl[i - 1] == 0 and j == 1:
                            r.append((i, 0))
                            j = 0
                        elif xl[i - 1] == 1 and j == 0:
                            r.append((i, 1))
                            j = 1
                        r.append((i - 1, j))
                return r
            def move_floor(r, dest):
                i, j = r[-1]
                if j == 1:
                    r.append((i, 0))
                for i in range(i + 1, dest + 1) if i < dest else range(i - 1, dest - 1, -1):
                    r.append((i, 0))
                return r
            r = [(s[0] + 1, 1), (s[0], 1), (s[0], 0), (s[0] + 1, 0)]
            cur = s[0] + 1
            for d in s[1:]:
                r0 = [(d + 1, 1)] if cur == d else move_ceiling([(d + 1, 1)], cur)
                r1 = move_ceiling(r.copy(), d + 1)
                r1 = move_floor(r1, cur)
                r1.pop()
                r2 = list(reversed(r))
                r2 = move_floor(r2, d + 1)
                r = r0 + r1 + r2
                cur = d + 1
            r = move_floor(r, n)
            r.reverse()
            r = move_floor(r, n)
            r.pop()
            res.append(r)
        else:
            for d in s:
                y = x ^ (1 << d)
                if a[y] != 1:
                    return False
    return True

if __name__ == '__main__':
    if solve():
        print('Possible')
        r = [(i, j) for r in res for i, j in r]
        r.append((n, 0))
        print(len(r) - 1)
        for i, j in r:
            print(i, j)
    else:
        print('Impossible')

Solution (Python):
import sys
from heapq import *

def first_1(x):
  if x:
    i = 0
    while x & 1 == 0:
      x >>= 1
      i += 1
    return i

def sep_single(s):
  if s:
    r = 1 << (s.bit_length()-1)
    i = s.bit_length()-1
    while s:
      if r & s:
        yield -i, r
        s ^= r
      r >>= 1
      i -= 1

def prepare_to_right(g, x):
  x0, y0 = g[-1]
  if x0 < x and y0:
    y0 = 0
    g.append((x0, 0))
  while x0 < x:
    x0 += 1
    g.append((x0, 0))

def prepare_to_left(g, x):
  x0, y0 = g[-1]
  if x+1 < x0 and y0:
    y0 = 0
    g.append((x0, 0))
  while x+1 < x0:
    x0 -= 1
    g.append((x0, 0))

def append_to_right(g, x, y):
  prepare_to_right(g, x)
  x0, y0 = g[-1]
  if y != y0:
    g.append((x, y))
  g.append((x+1, y))

def subloop_tp_group(g):
  x = 0
  while g&1 == 0:
    g >>= 1
    x += 1
  loop = [(x+1, 0)]
  tail = [(x, 0), (x, 1), (x+1, 1)]
  g >>= 1
  x += 1
  while g:
    while g&1==0:
      g >>= 1
      x += 1
    prepare_to_right(loop, x)
    prepare_to_right(tail, x)
    rev = reversed(loop)
    append_to_right(loop, x, 1)
    loop.append((x+1, 0))
    loop.extend(rev)
    loop.extend(tail)
    append_to_right(loop, x, 0)
    append_to_right(tail, x, 1)
    g >>= 1
    x += 1
  loop.extend(reversed(tail))
  return loop

N = int(input())

single = 0
tpg = []
for i in range(1<<N):
  a = int(sys.stdin.read(1))
  if bin(i).count("1") == 1:
    if a == 0:
      single |= i
  else:
    b = i & single
    if i and b | a == 0 and all(p & i != p for n, p in tpg):
      heappush(tpg, (-first_1(i), i))
    elif i | a == 0 or a and (b or any(p & i == p for n, p in tpg)):
      print("Impossible")
      break
else:
  print("Possible")
  loop = []
  for n, g in merge(sep_single(single), nsmallest(len(tpg),tpg)):
    subloop = subloop_tp_group(g)
    if loop:
      prepare_to_left(loop, subloop[0][0])
      if loop[-1] == subloop[0]:
        loop.pop()
    loop.extend(subloop)
  
  if not loop:
    loop.append((0, 0))
  prepare_to_right(loop, loop[0][0])
  
  print(len(loop)-1)
  for p in loop:
    print(*p)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(map(int,readline().rstrip().decode()))

minimal_sets = []
for n in range(1<<N):
    s = n
    is_min = (A[n] == 0)
    while s:
        s = (s - 1) & n
        if A[n] == 1 and A[s] == 0:
            print('Impossible')
            exit()
        if A[s] == 0:
            is_min = False
    if is_min:
        minimal_sets.append(n)

def make(nums, x):
    if not nums:
        return [(x,0)]
    path = []
    if len(nums) == 1:
        n = nums[0]
        for i in range(x, n+1):
            path.append((i,0))
        path += [(n+1,0),(n+1,1),(n,1),(n,0)]
        for i in range(n-1,x-1,-1):
            path.append((i,0))
        return path
    n = nums[0]
    for i in range(x, n+1):
        path.append((i,0))
    P = make(nums[1:], n+1)
    path += P
    path += [(n,0), (n,1), (n+1,1), (n+1, 0)]
    path += P[::-1][1:]
    path += [(n+1,1), (n,1), (n,0)]
    for i in range(n-1,x-1,-1):
        path += [(i,0)]
    return path

path = [(0,0)]
for n in minimal_sets:
    path += make([i for i in range(N) if n & (1<<i)], 0)[1:]

print('Possible')
print(len(path) - 1)
print('\n'.join('{} {}'.format(x,y) for x,y in path))

Solution (Python):
def rev(a):
    return [-v for v in a[::-1]]

def make(s):
    assert len(s)>0
    pre_s = s[:-1]
    v = s[-1]
    if len(pre_s)==0:
        return [v]
    return make(pre_s) + [v] + rev(make(pre_s)) + [-v]

def make_pre_path(v):
    if v>0:
        return [(i,0) for i in range(1,v+1)] + [(v,1), (v-1,1)] + [(i,0) for i in range(v-1,0,-1)]
    elif v<0:
        return make_pre_path(-v)[::-1]
    assert False

def make_path(v):
    return make_pre_path(v)+[(0,0)]

def test():
    
    main("3","11111110")
    

def main(s1,s2):
    ok = True
    n = int(s1)
    ret_gp = []
    for i in range(2**n-1,-1,-1):
        s = [v+1 for v in range(n) if (i>>v)%2==1 ]
        if s2[i]=="0":
            for ind in range(n):
                if (i>>ind)%2==0 and s2[(i+2**ind)]=="1":
                    ok = False
            if len(s)>0:
                ret_gp += make(s)
    ret_path = [(0,0)] + [p for v in ret_gp for p in make_path(v)]
    if 0:
        print(ret_gp)
    if ok:
        print("Possible")
        print(len(ret_path) - 1)
        for x,y in ret_path:
            print(str(x)+" "+str(y))
    else:
        print("Impossible")


        
s1 = raw_input()
s2 = raw_input()
main(s1,s2)