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 つの小課題があります.
- (30 点) T = 1.
- (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