{"problem":{"name":"Topology","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc043_e"},"statements":[{"statement_type":"Markdown","content":"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.\n\n*   Let $x = \\sum_{i \\in S} 2^i$ and $B_S$ be the set of points ${ (i+0.5,0.5) | i \\in S }$.\n*   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$.\n*   If there is no such way, $A_x = 0$.\n\nFor instruction on printing a closed curve, see Output below.\n\n## Constraints\n\n*   $1 \\leq N \\leq 8$\n*   $A_i = 0,1 \\quad (0 \\leq i \\leq 2^N-1)$\n*   $A_0 = 1$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_0A_1 \\cdots A_{2^N-1}$\n\n[samples]\n\n## Notes\n\n$C$ is said to be a closed curve if and only if:\n\n*   $C$ is a continuous function from $[0,1]$ to $\\mathbb{R}^2$ such that $C(0) = C(1)$.\n\nWe 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:\n\n*   There exists a function $f : [0,1] \\times [0,1] \\rightarrow \\mathbb{R}^2$ that satisfies all of the following.\n    *   $f$ is continuous.\n    *   $f(0,t) = C(t)$.\n    *   $f(1,t) = D(t)$.\n    *   $f(x,t) \\notin X$.","is_translate":false,"language":"English"}],"meta":{"iden":"agc043_e","tags":[],"sample_group":[["1\n10","Possible\n4\n0 0\n0 1\n1 1\n1 0\n0 0\n\nWhen $S = \\emptyset$, we can move this curve so that every point on it has a negative $y$\\-coordinate.\n![image](https://img.atcoder.jp/agc043/d44ca639698b4c14bb84b90da5442ca6.png)\nWhen $S = {0}$, we cannot do so.\n![image](https://img.atcoder.jp/agc043/5a960a0c4167e8593b6c8f8af685253d.png)"],["2\n1000","Possible\n6\n1 0\n2 0\n2 1\n1 1\n0 1\n0 0\n1 0\n\nThe output represents the following curve:\n![image](https://img.atcoder.jp/agc043/283e490d520a451f1b15160900c9b545.png)"],["2\n1001","Impossible"],["1\n11","Possible\n0\n1 1"]],"created_at":"2026-03-03 11:01:13"}}