P12911 [POI 2020/2021 R2] 棋盘 / Projekt planszy

翻译来自于 [LibreOJ](https://loj.ac/p/4828)。

**题目译自 [XXVIII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi28-2/dashboard/) [Projekt planszy](https://szkopul.edu.pl/problemset/problem/tFYVKjavLmyczkxMH7WFewXe/statement/)** 棋盘由 $n \cdot n$ 个格子组成，分为 $n$ 行和 $n$ 列，格子编号从 $1$ 到 $n$。第 $i$ 行第 $j$ 列的格子坐标为 $(i, j)$。你需要从左上角的格子 $(1,1)$ 走到右下角的格子 $(n, n)$。棋盘上有些格子是被封锁的，你只能在未被封锁的格子上向右或向下移动，也就是说，从格子 $(i, j)$ 可以走到 $(i, j+1)$ 或 $(i+1, j)$，前提是目标格子没有被封锁。 有的棋盘只有一种走法，有的则有多种走法。给定一个数字 $K$，请你设计一个尺寸不超过 $100$ 的棋盘，使从起点到终点的不同走法数量恰好为 $K$。

输入的第一行包含一个整数 $K$ $(0 \leq K)$。

输出的第一行是一个整数 $n$ $(1 \leq n \leq 100)$，表示棋盘的大小。接下来 $n$ 行，每行输出一个长度为 $n$ 的字符串，由字符 `.`（表示未封锁的格子）和 `#`（表示被封锁的格子）组成。第 $i$ 行的第 $j$ 个字符描述了格子 $(i, j)$ 的状态。 在题目给定的限制条件下，答案总是存在的。如果有多种可能的答案，你的程序可以输出其中任意一种。

详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $K \leq 50$ | $15$ | | $2$ | $K \leq 2000$ | $15$ | | $3$ | $K \leq 10^{9}$ | $40$ | | $4$ | $K \leq 10^{18}$ | $30$ |