{"problem":{"name":"[POI 2021/2022 R1] Domino","description":{"content":"> 有一个 $2$ 行 $n$ 列的矩形，上面有若干个格子被占用了。你要用 $1\\times 2$ 或 $2\\times 1$ 的牌，覆盖所有未被占用的格子，一个格子不可被占用两次。记方案数为 $m$。 给你 $m$，求出最小的 $n$，使得存在一种方案设置占用格，使得覆盖的方案数恰好为 $m$。无解输出 `NIE`。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9416"},"statements":[{"statement_type":"Markdown","content":"> 有一个 $2$ 行 $n$ 列的矩形，上面有若干个格子被占用了。你要用 $1\\times 2$ 或 $2\\times 1$ 的牌，覆盖所有未被占用的格子，一个格子不可被占用两次。记方案数为 $m$。\n\n给你 $m$，求出最小的 $n$，使得存在一种方案设置占用格，使得覆盖的方案数恰好为 $m$。无解输出 `NIE`。\n\n## Input\n\n一行一个正整数 $m$。\n\n## Output\n\n如果有解，输出你的答案 $n$。\n\n如果无解，输出 `NIE`。\n\n[samples]\n\n## Background\n\n译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Domino](https://sio2.mimuw.edu.pl/c/oi29-1/p/dom/)。\n\n## Note\n\n对于所有数据，$1\\leq m\\leq 10^{18}$。\n\n| 子任务编号 | 附加限制 | 分数 |\n| :----------: | :----------: | :----------: |\n| 1 | 答案 $\\leq 12$ | 20 |\n| 2 | $m\\leq 2000000$ | 30 |\n| 3 |  | 50 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9416","tags":["动态规划 DP","搜索","POI（波兰）","2021"],"sample_group":[["4\n","5\n"],["101\n","NIE\n"],["9\n","7\n"],["11\n","NIE\n"],["500\n","20\n"],["112233445566778899\n","NIE\n"]],"created_at":"2026-03-03 11:09:25"}}