H - 論理回路の構成 Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

N 個のスイッチがあり，それぞれスイッチ 1, 2, 3, ..., N と番号付けられています．各スイッチは，0 か 1 のいずれか二通りの状態を持ちます．

さて，あなたは番号 N+1, N+2, ..., N+M がついた M 個のメモリを使って，回路を作ることができます．（M の値は自由に決められます．）


メモリには，以下の 4 種類があります．以下の説明では，該当するメモリの番号を x としています．

① AND メモリ
2 つのスイッチ/メモリから繋がっており，これらを番号 u, v (u < x, v < x) とします．番号 x のメモリの値は，番号 u がついたスイッチ/メモリの値・番号 v がついたスイッチ/メモリの値が両方 1 であれば 1 となり，そうでなければ 0 となります．

② OR メモリ
2 つのスイッチ/メモリから繋がっており，これらを番号 u, v (u < x, v < x) とします．番号 x のメモリの値は，番号 u がついたスイッチ/メモリの値・番号 v がついたスイッチ/メモリの値のうち片方でも 1 であれば 1 となり，そうでなければ 0 となります．

③ XOR メモリ
2 つのスイッチ/メモリから繋がっており，これらを番号 u, v (u < x, v < x) とします．番号 x のメモリの値は，番号 u がついたスイッチ/メモリの値・番号 v がついたスイッチ/メモリの値のうち一つだけが 1 であれば 1 となり，そうでなければ 0 となります．

④ NOT メモリ
1 つのスイッチ/メモリから繋がっており，これを番号 u (u < x) とします．番号 x のメモリの値は，番号 u がついたスイッチ/メモリの値が 0 であれば 1 となり，そうでなければ 0 となります．


例えば，以下の図のような回路を考えます．

この回路の場合，それぞれのスイッチの状態について各メモリの状態は，以下の表のようになります．

スイッチ1 スイッチ2 スイッチ3 メモリ4 メモリ5 メモリ6
0 0 0 0 1 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 1 0 0
1 0 0 1 1 1
1 0 1 1 0 0
1 1 0 0 1 0
1 1 1 0 0 0

そのため，{スイッチ1, スイッチ2, スイッチ3} の状態が {0, 1, 0}, {1, 0, 0} の 2 通りに限り，メモリ6 の値が 1 となります．


それについて，以下の 2 つの問題を解いてください．

T=1 のとき
スイッチの状態は 2^N 通りありますが，そのうちちょうど K 通りについて，番号 N+M のメモリ（M=0 の場合はスイッチ）の値が 1 となるような回路を一つ構成してください．

ただし，2^{N}×4N 個を超えるメモリを使ってはいけません．

T = 2 のとき
スイッチの状態が S_1, S_2, S_3, ..., S_K であるときに限り，番号 N+M のメモリ（M=0 の場合はスイッチ）の値が 1 となるような回路を一つ構成してください．

ただし，50 \ 000 個を超えるメモリを使ってはいけません．

制約

  • 1 \leq T \leq 2
  • 2 \leq N \leq 10
  • 1 \leq K \leq 2^{N}-1
  • T, N, K は整数

小課題・得点

この問題には，2 つの小課題があります．

  1. (30 点) T = 1．
  2. (70 点) T = 2．

小課題 1 において，各テストケースに対して以下のように得点が定められます．この小課題の全部のテストケースに対する最低得点がこの小課題の得点となります．

  • 2^{N}×4N < M のとき，0 点．
  • 2^{N}×2 < M \leq 2^{N}×4N のとき，10 点．
  • N^2 < M \leq 2^{N}×2 のとき，16 点．
  • N-1 < M \leq N^2 のとき，23 点．
  • M \leq N-1 のとき，30 点満点．

次に，小課題 2 において，すべてのテストケースにおける M の最大値を L_2 としたとき，この小課題の得点は以下のようになります．

  • 50 \ 001 \leq L_2 のとき，0 点．
  • 4 \ 201 \leq L_2 \leq 50 \ 000 のとき，15 点．
  • 3 \ 101 \leq L_2 \leq 4 \ 200 のとき，18 点．
  • 2 \ 101 \leq L_2 \leq 3 \ 100 のとき，21 点．
  • 1 \ 601 \leq L_2 \leq 2 \ 100 のとき，25 点．
  • 1 \ 201 \leq L_2 \leq 1 \ 600 のとき，29 点．
  • 751 \leq L_2 \leq 1 \ 200 のとき，35 点．
  • 501 \leq L_2 \leq 750 のとき，floor(70 - \frac{L_2 - 500}{8}) 点．
  • L_2 \leq 500 のとき，70 点満点．

入力

入力は以下の形式で標準入力から与えられます．

(☆) T = 1 のとき 

1
N K

ただし，N はスイッチの個数，K は番号 N+M のスイッチ（M=0 の場合メモリ）の値が 1 であるべき状態の通り数を意味します．

(★) T = 2 のとき 

2
N K
S_1
S_2
S_3
 :
S_K

ここでは，S_i は番号 N+M のスイッチ (M=0 の場合メモリ) の値が 1 であるべき状態のうち，i 番目のものです．
S_i は N 文字の文字列で表され，i 文字目が 0 である場合は i 番目のスイッチの状態が 0 である，i 文字目が 1 である場合は i 番目のスイッチの状態が 1 であることを意味します．
例えば，N = 4 で S_i = 0101 の場合，スイッチ 2, 4 が 1 であり，スイッチ 1, 3 が 0 であるような状態のことを表します．

出力

以下のように，論理回路の構成方法を出力してください． 

M
(番号 N+1 のメモリの情報)
(番号 N+2 のメモリの情報)
(番号 N+3 のメモリの情報)
 :
(番号 N+M のメモリの情報)

番号 x のメモリの情報は，以下のように出力してください．

AND メモリの場合

AND u v

これは，番号 u と v のスイッチ/メモリから，番号 x のメモリに繋がっていることを表します．u < x, v < x を満たさなければなりません．（ただし u = v でも構わない）

OR メモリの場合

OR u v

これは，番号 u と v のスイッチ/メモリから，番号 x のメモリに繋がっていることを表します．u < x, v < x を満たさなければなりません．（ただし u = v でも構わない）

XOR メモリの場合

XOR u v

これは，番号 u と v のスイッチ/メモリから，番号 x のメモリに繋がっていることを表します．u < x, v < x を満たさなければなりません．（ただし u = v でも構わない）

NOT メモリの場合

NOT u

これは，番号 u のスイッチ/メモリから，番号 x のメモリに繋がっていることを表します．u < x を満たさなければなりません．

入力例 1

1
3 2

出力例 1

3
XOR 1 2
NOT 3
AND 4 5

この出力の場合，N = 2 に対して M = 3 であり，N 以上 N^2 以下なので 23 点となります．

入力例 2

2
3 2
010
100

出力例 2

3
XOR 1 2
NOT 3
AND 4 5

入力例 3

1
5 24

出力例 3

1
OR 1 2

入力例 4

2
3 4
001
101
011
111

出力例 4

0