筑波大学プログラミングコンテスト2025
コンテスト日時
2025/11/16 (Su) 13:15 - 16:45

M - Huge A + B

Flavor
2
s
1024
MB
800

問題文

$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
1
出力例 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$ を満たすため、このケースについては正解と判定されます。

提出
C++23 (g++ 12.2.0)