/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 匹のスライムがいます。
あなたはこのスライムの「体力」を自由な整数の値に設定できます。
スライムは 1 秒ごとに、自分より真に小さい整数の体力をもつスライムを 1 匹生成することで増殖していきます。生成されるスライムの体力は、スライムごとに毎回自由に決めることができます。最初の増殖はこれから 1 秒後に起こります。
最初のスライム、および生成されるスライムの体力を適切に定めることで、これから N 秒後に存在する 2^N 匹のスライムの体力の集合を集合 S に一致させることができるか判定してください。
ここで S は 2^N 要素からなる重複を認める整数の集合で、その要素は S_1,~S_2,~...,~S_{2^N} です。
制約
- 入力は全て整数である。
- 1 \leq N \leq 18
- 1 \leq S_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
S_1 S_2 ... S_{2^N}
出力
最初のスライム、および生成されるスライムの体力を適切に定めることで、N 秒後に存在する 2^N 匹のスライムの体力の集合を集合 S に一致させることができるなら Yes を、できないなら No を出力せよ。
入力例 1
2 4 2 3 1
出力例 1
Yes
2 秒後に存在するスライムの体力の集合を S に一致させる一例を示します。
まず最初のスライムの体力を 4 に設定します。
最初のスライムに体力が 3 のスライムを生成させることで、1 秒後に存在するスライムの体力を 4,~3 とできます。
そして最初のスライムに体力が 2 の、2 匹目のスライムに体力が 1 のスライムを生成させることで、2 秒後に存在するスライムの体力を 4,~3,~2,~1 とできます。これは集合として S に一致しています。
入力例 2
2 1 2 3 1
出力例 2
Yes
S は同じ整数を複数含むこともあります。
入力例 3
1 1 1
出力例 3
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
出力例 4
No
Score : 600 points
Problem Statement
We have one slime.
You can set the health of this slime to any integer value of your choice.
A slime reproduces every second by spawning another slime that has strictly less health. You can freely choose the health of each new slime. The first reproduction of our slime will happen in one second.
Determine if it is possible to set the healths of our first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals a multiset S.
Here S is a multiset containing 2^N (possibly duplicated) integers: S_1,~S_2,~...,~S_{2^N}.
Constraints
- All values in input are integers.
- 1 \leq N \leq 18
- 1 \leq S_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
S_1 S_2 ... S_{2^N}
Output
If it is possible to set the healths of the first slime and the subsequent slimes spawn so that the multiset of the healths of the 2^N slimes that will exist in N seconds equals S, print Yes; otherwise, print No.
Sample Input 1
2 4 2 3 1
Sample Output 1
Yes
We will show one way to make the multiset of the healths of the slimes that will exist in 2 seconds equal to S.
First, set the health of the first slime to 4.
By letting the first slime spawn a slime whose health is 3, the healths of the slimes that exist in 1 second can be 4,~3.
Then, by letting the first slime spawn a slime whose health is 2, and letting the second slime spawn a slime whose health is 1, the healths of the slimes that exist in 2 seconds can be 4,~3,~2,~1, which is equal to S as multisets.
Sample Input 2
2 1 2 3 1
Sample Output 2
Yes
S may contain multiple instances of the same integer.
Sample Input 3
1 1 1
Sample Output 3
No
Sample Input 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
Sample Output 4
No