M - Huge A + B
問題文
$1$ 以上 $16$ 以下の整数 $N$ が与えられます。 $4$ つの変数 $A,B,C,D$ があり、
初期値はそれぞれ$A=a, B=b, C=0, D=0$ ( $a + b< 2^{2^N}$ , $a,b$ は非負整数) です。
あなたはこれらの変数に対して、以下の操作を一つ選んで実行することを $8(N+1)$ 回まで行うことができます。
AND X Y Z- $X,Y,Z \in \left\lbrace A,B,C,D\right\rbrace$ に対し、変数 $X$ を $Y \ \textrm{AND} \ Z$ で置き換える。
OR X Y Z- $X,Y,Z\in \left\lbrace A,B,C,D\right\rbrace$ に対し、変数 $X$ を $Y \ \textrm{OR} \ Z$ で置き換える。
NOT X Y- $X,Y\in \left\lbrace A,B,C,D\right\rbrace$ に対し、変数 $X$ を $\textrm{NOT} \ Y$ で置き換える。
SHL X Y k- $X,Y\in \left\lbrace A,B,C,D\right\rbrace, 0\le k\le 2^N$ を満たす整数 $k$ に対し、変数 $X$ を $(Y \times 2^k) \ \textrm{mod} \ 2^{2^N}$ で置き換える。
$x,y$ を $2^N$ ビット整数としたとき、 $x \ \textrm{AND} \ y$ は $x$ と $y$ のビットごとの論理積、 $x \ \textrm{OR} \ y$ は $x$ と $y$ のビットごとの論理和、 $\textrm{NOT}\ x$ は $x$ の全ビットを反転した $2^N$ ビット整数とします。
なお、各操作後の各変数の値は常に $2^{2^N}$ 未満の非負整数、すなわち $2^N$ ビットで表現できる整数となることが証明できます。
最終的に $C=a+b$ を満たすような操作列を構成してください。
$a, b$ は入力で与えられないことに注意してください。
制約
- $N$ は $1$ 以上 $16$ 以下の整数
- $a,b$ は非負整数
- $a+b<2^{2^N}$
入力
入力は以下の形式で標準入力から与えられる。
$N$
出力
実行する操作の回数を $M(\le 8(N + 1))$ として、以下の形式で出力せよ。
$\textrm{operation}_1$
$\textrm{operation}_2$
$\vdots$
$\textrm{operation}_M$
$\textrm{operation}_i$ は $i$ 回目に実行する操作を表す。 各操作は、 $X,Y,Z$ を A, B, C, Dのうちいずれかの文字、 $k$ を $0$ 以上 $2^N$ 以下の整数として、以下に示す形式のいずれかに従って出力せよ。
AND $X$ $Y$ $Z$
OR $X$ $Y$ $Z$
NOT $X$ $Y$
SHL $X$ $Y$ $k$
ジャッジについて
各テストケースには複数の非負整数の組 $(a,b) \ (a+b < 2^{2^N})$ が設定されている。この値は事前に用意されたものであり、テストケースごとに固定である。ジャッジプログラムは、各 $(a,b)$ に対して独立に、操作列に含まれる操作を順に実行する。全ての $(a,b)$ に対して、実行終了時に変数 $C$ に $a+b$ が代入されているとき、ジャッジ結果は AC となり、そうでない場合はジャッジ結果は WA となる。
1
OR C A B
AND D A C
SHL A A 1
NOT B A
これは、正しい形式に従った出力の例であって、問題文の条件を満たす出力であるとは限りません。
例として、 $a=1,b=2$ の場合を考えます。
変数の初期状態は $(A,B,C,D)=(1,2,0,0)$ です。各操作によって各変数の状態は以下のように変化します。
OR C A Bにより $C$ を $A\ \textrm{OR}\ B = 1\ \textrm{OR}\ 2 = 3$ に置き換える。操作後の各変数の状態は $(A,B,C,D)=(1,2,3,0)$ となる。AND D A Cにより $D$ を $A\ \textrm{AND}\ C = 1\ \textrm{AND}\ 3 = 1$ に置き換える。操作後の各変数の状態は $(A,B,C,D)=(1,2,3,1)$ となる。SHL A A 1により $A$ を $(A\times 2^1)\ \textrm{mod} \ 2^{2^1} = (1\times 2)\ \textrm{mod}\ 4 = 2$ に置き換える。操作後の各変数の状態は $(A,B,C,D)=(2,2,3,1)$ となる。NOT B Aにより $B$ を $\textrm{NOT}\ A = \textrm{NOT}\ 2 = 1$ に置き換える。 $2^N$ ビット整数として計算するため、 $\textrm{NOT}$ は下位 $2$ ビットのみを反転することに注意すること。操作後の各変数の状態は $(A,B,C,D)=(2,1,3,1)$ となる。
最終的な各変数の状態は $(A,B,C,D)=(2,1,3,1)$ となり、$C=a+b$ を満たすため、このケースについては正解と判定されます。