AT_abc140_f [ABC140F] Many Slimes

题目描述

有 $1$ 只史莱姆。

你可以自由地将这只史莱姆的“体力”设置为任意整数值。

史莱姆每经过 $1$ 秒，会生成一只体力严格小于自己的史莱姆。每只史莱姆在每次生成时，其生成的史莱姆的体力可以自由指定。第一次生成将在 $1$ 秒后发生。

请判断是否可以通过适当地设定最初史莱姆以及每次生成的史莱姆的体力，使得 $N$ 秒后存在的 $2^N$ 只史莱姆的体力集合恰好等于集合 $S$。

这里，$S$ 是一个包含 $2^N$ 个元素的多重集合，其元素为 $S_1, S_2, \ldots, S_{2^N}$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $S_1$ $S_2$ $\ldots$ $S_{2^N}$

输出格式

如果可以通过适当设定最初史莱姆及生成的史莱姆的体力，使得 $N$ 秒后存在的 $2^N$ 只史莱姆的体力集合恰好等于 $S$，则输出 Yes；否则输出 No。

样例 1

输入

2
4 2 3 1

输出

Yes

样例 2

输入

2
1 2 3 1

输出

Yes

样例 3

输入

1
1 1

输出

No

样例 4

输入

5
4 3 5 3 1 2 7 8 7 4 6 3 7 2 3 6 2 7 3 2 6 7 3 4 6 7 3 4 2 5 2 3

输出

No

说明/提示

限制

• 所有输入均为整数。
• $1 \leq N \leq 18$
• $1 \leq S_i \leq 10^9$

样例解释 1

下面给出一个在 $2$ 秒后使史莱姆体力集合等于 $S$ 的例子。首先，将最初的史莱姆体力设为 $4$。让最初的史莱姆生成一只体力为 $3$ 的史莱姆，这样 $1$ 秒后存在的史莱姆体力为 $4, 3$。然后让最初的史莱姆生成体力为 $2$ 的史莱姆，让第二只史莱姆生成体力为 $1$ 的史莱姆，这样 $2$ 秒后存在的史莱姆体力为 $4, 3, 2, 1$，作为集合与 $S$ 一致。

样例解释 2

$S$ 也可以包含相同的整数。

由 ChatGPT 4.1 翻译