AdditionalFile4100.zip

P9416 [POI 2021/2022 R1] Domino

题目背景

译自 XXIX Olimpiada Informatyczna – I etap Domino。

题目描述

有一个 $2$ 行 $n$ 列的矩形，上面有若干个格子被占用了。你要用 $1\times 2$ 或 $2\times 1$ 的牌，覆盖所有未被占用的格子，一个格子不可被占用两次。记方案数为 $m$。

给你 $m$，求出最小的 $n$，使得存在一种方案设置占用格，使得覆盖的方案数恰好为 $m$。无解输出 NIE。

输入格式

一行一个正整数 $m$。

输出格式

如果有解，输出你的答案 $n$。

如果无解，输出 NIE。

输入输出样例 #1

输入 #1

4

输出 #1

5

输入输出样例 #2

输入 #2

101

输出 #2

NIE

输入输出样例 #3

输入 #3

9

输出 #3

7

输入输出样例 #4

输入 #4

11

输出 #4

NIE

输入输出样例 #5

输入 #5

500

输出 #5

20

输入输出样例 #6

输入 #6

112233445566778899

输出 #6

NIE

说明/提示

对于所有数据，$1\leq m\leq 10^{18}$。

子任务编号	附加限制	分数
1	答案 $\leq 12$	20
2	$m\leq 2000000$	30
3		50

#4100. 「POI 2021/2022 R1」Domino

标签: 传统 | 时间限制: 7000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap Domino

Bajtek 喜欢用尺寸为 $2 \times 1$ 的多米诺骨牌覆盖尺寸为 $2 \times n$ 的长方形。这个宽度为 $n$ 的长方形由 $2n$ 个尺寸为 $1 \times 1$ 的小方格组成，Bajtek 可以选择涂黑其中的一些小方格。他希望能够用多米诺骨牌覆盖所有未涂黑的小方格，而且骨牌之间不能重叠（骨牌可以旋转）。更进一步，Bajtek 想要确保恰好有 $m$ 种不同的覆盖方式。最后，他想找到能够达成这一目的的最小长方形。

下图展示了一个宽度为 $n=6$ 的长方形，其中两个小方格被涂黑了。有四种不同的方式用多米诺骨牌恰好覆盖剩下的 $10$ 个小方格 。图中展示了两种覆盖方式：

然而，对于 $m=4$ 来说，这并不是最优解，因为存在一个 $n=5$ 的方案。

编写一个程序，对于给定的 $m$，找出能够达到上述条件的最小长方形宽度 $n$。

输入格式

输入一行一个整数 $m\ (1 \leq m \leq 10^{18})$。

输出格式

输出一行一个整数 $n$，表示所求长方形的最小可能宽度。如果不存在这样的长方形，输出 NIE。

样例 1

输入

4

输出

5

样例 2

输入

101

输出

NIE

样例 3

见附加文件下 [dom1.in](file:dom1.in) 和 [dom1.out](file:dom1.out)。

该样例满足 $m=9$，答案是 $n=7$。

样例 4

见附加文件下 [dom2.in](file:dom2.in) 和 [dom2.out](file:dom2.out)。

该样例满足 $m=11$，答案是 NIE。

样例 5

见附加文件下 [dom3.in](file:dom3.in) 和 [dom3.out](file:dom3.out)。

该样例满足 $m=500$，答案是 $n=20$。

样例 6

见附加文件下 [dom4.in](file:dom4.in) 和 [dom4.out](file:dom4.out)。

该样例满足 $m=112233445566778899$，答案是 NIE。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	答案不超过 $12$	$20$
$2$	$m \leq 2\cdot 10^6$	$30$
$3$	无附加限制	$50$