問題一覧 > 通常問題

No.1589 Bit Vector

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 38
作問者 : e869120e869120 / テスター : 沙耶花沙耶花
9 ProblemId : 6694 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-09 00:15:14

問題文

長さ $N+1$ のビット列 $a[0], a[1], \cdots, a[N]$ があるとします($a[i] \in \{0, 1\}$)。先頭の $N$ 要素の初期値は $B[0], B[1], \cdots, B[N-1]$ であり(あなたには知らされません)、残りの要素の初期値は $0$ です。あなたの目的は、最終的に $a[N]$ を以下の値にすることです。

  • $B[0], B[1], \cdots, B[N-1]$ の中で $1$ が $K$ 個以上存在する場合、$a[N] = 1$
  • そうでない場合、$a[N] = 0$
あなたが行えるのは、以下の三種類の操作です(ここで $0 \leq i, j, k \leq N, x \in \{0, 1\}$ ですが、$i, j, k$ に重複があっても構いません):
  • UPD i x:$a[i] = x$ とする。
  • AND i j k:$a[i] = a[j] \ \rm{AND}$$\ a[k]$ とする。
  • XOR i j k:$a[i] = a[j] \ \rm{XOR}$$\ a[k]$ とする。
$B[0], B[1], \cdots, B[N-1]$ $(B[i] \in \{0, 1\})$ がどんな値でも正解を出せるような操作列を出力してください。ただし、操作列の長さは $10000$ (回) 以下でなければなりません。なお、実際の正誤判定機は、与えられる $T$ 個のテストケース全てについて操作列を実行し、全て期待通りの結果となれば正解とみなされます。

入力

$N$ $K$
$T$
$C_{1,0}$ $C_{1,1}$ $C_{1,2}$ $\cdots$ $C_{1,N-1}$
$C_{2,0}$ $C_{2,1}$ $C_{2,2}$ $\cdots$ $C_{2,N-1}$
$\vdots$
$C_{T,0}$ $C_{T,1}$ $C_{T,2}$ $\cdots$ $C_{T,N-1}$

$T$ はテストケースの数、$C_{i, j}$ は $i$ 個目のテストケースにおける $B[j]$ の値を意味します。

出力

$1$ 行目に、操作を行う回数を出力してください。続けて、行う操作を UPD i xAND i j kXOR i j k のいずれかの形式で出力してください。

制約

  • $2 \leq N \leq 50$
  • $1 \leq K \leq N$
  • $1 \leq T \leq 100$
  • $C_{i, j} \in \{0, 1\}$
  • 入力はすべて整数

サンプル

サンプル1
入力
2 1
3
0 0
0 1
1 1
出力
2
UPD 2 0
XOR 2 1 2

$1$ 個目のテストケースでは、配列 $A$ の値は $(a[0], a[1], a[2]) = (0, 0, 0) \to (0, 0, 0) \to (0, 0, 0)$ と変化します。(最終的に $a[2] = 0$ です)

$2$ 個目のテストケースでは、配列 $A$ の値は $(a[0], a[1], a[2]) = (0, 1, 0) \to (0, 1, 0) \to (0, 1, 1)$ と変化します。(最終的に $a[2] = 1$ です)

$3$ 個目のテストケースでは、配列 $A$ の値は $(a[0], a[1], a[2]) = (1, 1, 0) \to (1, 1, 0) \to (1, 1, 1)$ と変化します。(最終的に $a[2] = 1$ です)

いずれの場合も正しい答えであるため、このテストケースでは正解となります。

ただし、$(B[0], B[1]) = (1, 0)$ の場合、最終的に $a[2] = 0$ となり、正しい答えにならないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。