/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
整数 N,\ A,\ B が与えられます。 (0,\ 1,\ ...\ 2^N-1) の順列 (P_0,\ P_1,\ ...\ P_{2^N-1}) であって、 次の条件をすべて満たすものが存在するかどうか判定してください。 また、存在するなら 1 つ構成してください。
- P_0=A
- P_{2^N-1}=B
- すべての 0 \leq i < 2^N-1 について、P_i と P_{i+1} は 2 進数表記でちょうど 1 桁だけ異なる。
制約
- 1 \leq N \leq 17
- 0 \leq A \leq 2^N-1
- 0 \leq B \leq 2^N-1
- A \neq B
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
条件を満たす順列が存在しないならば NO と出力せよ。
存在するならば、まず 1 行目に YES と出力せよ。
そして 2 行目に (P_0,\ P_1,\ ...\ P_{2^N-1}) を空白区切りで出力せよ。
なお、解が複数個存在する場合はどれを出力してもよい。
入力例 1
2 1 3
出力例 1
YES 1 0 2 3
P=(1,0,2,3) を 2 進数表記すると (01,00,10,11) となり、どの隣り合う 2 要素もちょうど 1 桁だけ異なります。
入力例 2
3 2 1
出力例 2
NO
Score : 800 points
Problem Statement
You are given integers N,\ A and B. Determine if there exists a permutation (P_0,\ P_1,\ ...\ P_{2^N-1}) of (0,\ 1,\ ...\ 2^N-1) that satisfies all of the following conditions, and create one such permutation if it exists.
- P_0=A
- P_{2^N-1}=B
- For all 0 \leq i < 2^N-1, the binary representations of P_i and P_{i+1} differ by exactly one bit.
Constraints
- 1 \leq N \leq 17
- 0 \leq A \leq 2^N-1
- 0 \leq B \leq 2^N-1
- A \neq B
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
If there is no permutation that satisfies the conditions, print NO.
If there is such a permutation, print YES in the first line.
Then, print (P_0,\ P_1,\ ...\ P_{2^N-1}) in the second line, with spaces in between.
If there are multiple solutions, any of them is accepted.
Sample Input 1
2 1 3
Sample Output 1
YES 1 0 2 3
The binary representation of P=(1,0,2,3) is (01,00,10,11), where any two adjacent elements differ by exactly one bit.
Sample Input 2
3 2 1
Sample Output 2
NO