D. Create a Maze

[{"iden":"statement","content":"ZS the Coder 喜欢迷宫。你的任务是创建一个迷宫，让他可以玩。一个迷宫由 #cf_span[n × m] 个房间组成，这些房间排列成 #cf_span[n] 行（从上到下编号，从 #cf_span[1] 开始）和 #cf_span[m] 列（从左到右编号，从 #cf_span[1] 开始）。位于第 #cf_span[i] 行和第 #cf_span[j] 列的房间记为 #cf_span[(i, j)]。玩家从房间 #cf_span[(1, 1)] 出发，目标是到达房间 #cf_span[(n, m)]。\n\n每个房间有四个门（边界上的房间除外），分别位于四面墙上，相邻的两个房间共享同一个门。有些门是锁住的，意味着无法通过该门。例如，如果连接 #cf_span[(i, j)] 和 #cf_span[(i, j + 1)] 的门被锁住，则无法从 #cf_span[(i, j)] 移动到 #cf_span[(i, j + 1)]。此外，玩家只能向下（从房间 #cf_span[(i, j)] 到房间 #cf_span[(i + 1, j)]）或向右（从房间 #cf_span[(i, j)] 到房间 #cf_span[(i, j + 1)]）移动，前提是对应的门未被锁住。\n\nZS the Coder 认为一个迷宫的 _难度_ 为 #cf_span[x]，当且仅当从房间 #cf_span[(1, 1)] 到房间 #cf_span[(n, m)] 恰好有 #cf_span[x] 种不同的路径。两条路径被认为是不同的，当且仅当它们经过的房间序列不同。\n\n你的任务是创建一个难度恰好为 #cf_span[T] 的迷宫。此外，ZS the Coder 不喜欢太大的迷宫，因此迷宫的大小和锁住的门的数量是有限制的。听起来很简单，对吧？\n\n输入的第一行（也是唯一一行）包含一个整数 #cf_span[T]（#cf_span[1 ≤ T ≤ 1018]），表示所需迷宫的难度。\n\n第一行应包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 50]）— 分别表示迷宫的行数和列数。\n\n下一行应包含一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 300]）— 表示迷宫中锁住的门的数量。\n\n接下来的 #cf_span[k] 行描述锁住的门。每行包含四个整数 #cf_span[x1, y1, x2, y2]，表示连接房间 #cf_span[(x1, y1)] 和房间 #cf_span[(x2, y2)] 的门被锁住。注意，房间 #cf_span[(x2, y2)] 必须与 #cf_span[(x1, y1)] 相邻，且位于其右侧或下方，即 #cf_span[x2 + y2] 应等于 #cf_span[x1 + y1 + 1]。列表中不应出现重复的锁住门。\n\n保证至少存在一个解。如果有多个解，输出任意一个即可。\n\n以下是样例输入和输出的示意图。彩色箭头表示所有可能的路径，红色叉号表示锁住的门。\n\n在第一个样例中：\n\n在第二个样例中：\n\n"},{"iden":"input","content":"输入的第一行（也是唯一一行）包含一个整数 #cf_span[T]（#cf_span[1 ≤ T ≤ 1018]），表示所需迷宫的难度。"},{"iden":"output","content":"第一行应包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 50]）— 分别表示迷宫的行数和列数。下一行应包含一个整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 300]）— 表示迷宫中锁住的门的数量。接下来的 #cf_span[k] 行描述锁住的门。每行包含四个整数 #cf_span[x1, y1, x2, y2]，表示连接房间 #cf_span[(x1, y1)] 和房间 #cf_span[(x2, y2)] 的门被锁住。注意，房间 #cf_span[(x2, y2)] 必须与 #cf_span[(x1, y1)] 相邻，且位于其右侧或下方，即 #cf_span[x2 + y2] 应等于 #cf_span[x1 + y1 + 1]。列表中不应出现重复的锁住门。保证至少存在一个解。如果有多个解，输出任意一个即可。"},{"iden":"examples","content":"输入\n3\n输出\n3 2\n0\n\n输入\n4\n输出\n4 3\n3\n1 2 2 2\n3 2 3 3\n1 3 2 3"},{"iden":"note","content":"以下是样例输入和输出的示意图。彩色箭头表示所有可能的路径，红色叉号表示锁住的门。在第一个样例中： 在第二个样例中： "}]}

Let $ T \in \mathbb{N} $, $ 1 \leq T \leq 10^{18} $. We seek integers $ n, m \in [1, 50] $, a set $ L \subseteq E $ of locked doors with $ |L| \leq 300 $, where $ E $ is the set of possible rightward and downward edges in an $ n \times m $ grid graph, such that the number of paths from $ (1,1) $ to $ (n,m) $ using only unblocked rightward and downward moves is exactly $ T $. Define the grid graph $ G = (V, E) $, where: - $ V = \{ (i,j) \mid 1 \leq i \leq n,\ 1 \leq j \leq m \} $, - $ E = \{ ((i,j), (i,j+1)) \mid 1 \leq i \leq n,\ 1 \leq j < m \} \cup \{ ((i,j), (i+1,j)) \mid 1 \leq i < n,\ 1 \leq j \leq m \} $. Let $ E_{\text{unblocked}} = E \setminus L $. Define $ P $ as the number of paths from $ (1,1) $ to $ (n,m) $ in $ (V, E_{\text{unblocked}}) $, moving only right or down. **Objective:** Find $ n, m, L $ such that $ P = T $. We construct the maze as follows: Let $ n = 2 $, $ m = \lceil \log_2(T) \rceil + 1 $ if $ T > 1 $, else $ m = 1 $. We use a binary representation of $ T $ to encode the number of paths via selectively blocking downward edges in the second row. Specifically, place $ m-1 $ rightward edges in row 1: $ ((1,j), (1,j+1)) $ for $ j = 1 $ to $ m-1 $, all unblocked. Place $ m-1 $ rightward edges in row 2: $ ((2,j), (2,j+1)) $ for $ j = 1 $ to $ m-1 $, all unblocked. Place $ m-1 $ downward edges: $ ((1,j), (2,j)) $ for $ j = 1 $ to $ m-1 $. Each path from $ (1,1) $ to $ (2,m) $ consists of: - Some number $ k \in [0, m-1] $ of right moves in row 1, - Then one downward move from $ (1, k+1) $ to $ (2, k+1) $, - Then $ m-1-k $ right moves in row 2. Thus, the number of paths equals the number of positions $ j \in \{1, \dots, m-1\} $ where the downward edge $ ((1,j), (2,j)) $ is **not locked**. Let $ b_0, b_1, \dots, b_{\ell-1} $ be the binary digits of $ T $, i.e., $ T = \sum_{i=0}^{\ell-1} b_i \cdot 2^i $, where $ \ell = \lfloor \log_2 T \rfloor + 1 $ if $ T > 1 $, else $ \ell = 1 $. Set $ m = \ell + 1 $, $ n = 2 $. For each $ j = 1 $ to $ \ell $, set the downward edge $ ((1,j), (2,j)) $ to be **locked** if and only if the $ (j-1) $-th bit of $ T $ is 0. (That is, if bit $ j-1 $ is 1, leave the door open; if 0, lock it.) Then the number of paths is exactly $ T $, since each open downward edge at column $ j $ contributes $ 2^{m-1-j} $ paths (due to freedom in the rightward moves after the downward move), and the sum over open doors equals $ T $ when bits are placed in powers of two. Alternatively, simpler construction: Use $ n = 2 $, $ m = \lfloor \log_2 T \rfloor + 2 $, and lock downward edges so that the number of open downward edges between columns 1 to $ m-1 $ corresponds to the binary representation of $ T $, with each open edge at position $ j $ contributing $ 2^{m-1-j} $ paths. But a cleaner, standard construction: **Final Construction:** Set $ n = 2 $, $ m = \lfloor \log_2 T \rfloor + 2 $ if $ T > 1 $, else $ m = 1 $. - For each $ j \in \{1, 2, \dots, m-1\} $: - Keep the downward edge $ ((1,j), (2,j)) $ **unlocked** if the $ (j-1) $-th bit in the binary representation of $ T $ is 1. - Otherwise, **lock** it. Then the total number of paths from $ (1,1) $ to $ (2,m) $ is: $$ \sum_{j=1}^{m-1} \left( \text{if } ((1,j),(2,j)) \text{ unlocked} \right) \cdot 2^{m-1-j} $$ This equals $ T $, because the weights $ 2^{m-1-j} $ for $ j = 1 $ to $ m-1 $ are exactly $ 2^{m-2}, 2^{m-3}, \dots, 2^0 $, and we are summing the bits of $ T $ multiplied by their respective powers of two. Thus, the number of locked doors is the number of 0-bits in the binary representation of $ T $, which is at most $ \lfloor \log_2 T \rfloor + 1 \leq 60 $, well below 300. **Formal Output:** Let $ T \in \mathbb{N} $, $ 1 \leq T \leq 10^{18} $. Define: - $ n = 2 $ - $ m = \lfloor \log_2 T \rfloor + 2 $ if $ T > 1 $, else $ m = 1 $ - Let $ \ell = m - 1 $ - For $ j = 1 $ to $ \ell $: - Let $ b_{j-1} $ be the $ (j-1) $-th bit of $ T $ (least significant bit is bit 0) - If $ b_{j-1} = 0 $, then lock the edge $ ((1,j), (2,j)) $ Then the number of paths from $ (1,1) $ to $ (n,m) $ is exactly $ T $. Locked doors: all $ ((1,j), (2,j)) $ such that the $ (j-1) $-th bit of $ T $ is 0. Number of locked doors: $ \ell - \text{popcount}(T) \leq \lfloor \log_2 T \rfloor + 1 \leq 60 \leq 300 $. **Final Answer (Formal):** $$ \boxed{ \begin{aligned} &n = 2 \\ &m = \begin{cases} 1 & \text{if } T = 1 \\ \lfloor \log_2 T \rfloor + 2 & \text{if } T > 1 \end{cases} \\ &k = \text{number of } j \in \{1, 2, \dots, m-1\} \text{ such that the } (j-1)\text{-th bit of } T \text{ is } 0 \\ &L = \left\{ \big( (1,j), (2,j) \big) \ \middle|\ j \in \{1, \dots, m-1\},\ \text{bit}_{j-1}(T) = 0 \right\} \end{aligned} } $$