=begin
 
 
>293 デフォルトの名無しさん 2020/04/27(月) 09:21:19.63 ID:Vk+6u7Hb
>    次は全加算器をやってみよう。
>    ４入力セレクタ辺りで限界でしょう。
 
さすがに無理臭いので半加算器でお茶を濁す
 
半加算器は 5つのNANDゲートで構成できることが分かっている (またはXOR,ORを1各1個)
全加算器は 2つの半加算器と1つのORゲートで構成できる
※ 最低1つのNANDゲートの入力は A,Bであることは自明なので、1つ目のNANDゲートの入力はA,Bに固定
※ その場合の解は 96通り。固定しない場合の解は 768通り。
 
=end
 
	$ans = 0
	NandPiece = 5
	ab = [ 0,1, 0,0, 0,0, 0,0, 0,0 ]	# 1つ目のNANDゲートの入力を A,Bに固定
 
def print_map2( ab, c, s )
	tbl  = %w{ X Y c1 c2 c3 c4 c5 }
	ab.each_with_index{|n,i|
		m, a = i.divmod(2)
		print "#{tbl[n]} "
	}
	puts " c#{c+1} c#{s+1}"
	$ans += 1
end
 
def check( ab )
	return false	unless ab.index(0) && ab.index(1)	# X,Y 入力を使わない物は枝刈り
	cnum = [0] * NandPiece	# 出力ビットテーブル f(x,y) -> c_, s_
	2.times{|x|
		2.times{|y|
			lg = []
			c = []
			ab.each_with_index{|n,i|
				case n
				when 0;	lg[i] = x
				when 1;	lg[i] = y
				end
			}
			NandPiece.times{
				NandPiece.times{|cn|
					next	if c[cn]
					if lg[2*cn] && lg[2*cn+1]
						c[cn] = (lg[2*cn] & lg[2*cn+1]) ^ 1		# nand
						ab.each_with_index{|n,i|
							case n
							when 2;	lg[i] = c[0]
							when 3;	lg[i] = c[1]
							when 4;	lg[i] = c[2]
							when 5;	lg[i] = c[3]
							end
						}
					end
				}
			}
			NandPiece.times{|n|
				if c[n] && cnum[n]
					cnum[n] = (cnum[n] << 1) | c[n]
				else
					cnum[n] = nil
				end
			}
			return false	if cnum.index( nil )		# 枝刈り
		}
	}
	if cnum.index( 0b0001 ) && cnum.index( 0b0110 )	# パターン検索 Half adder C, S
		print_map2( ab, cnum.index( 0b0001 ), cnum.index( 0b0110 ) )
	end
end
 
def solve( ab, n = 0 )
	return	if n > 2 * NandPiece - 1
	solve( ab, n + 1 )
	check( ab )	if n == 2 * NandPiece - 1
	ab[n] += 1
	ab[n] += 1	if n >> 1 == ab[n] - 2		# 出力は入力につなげない (一段のループだけチェック)
	if ab[n] > NandPiece + 1
		ab[n] = 0
		return
	end
	solve( ab, n )
end
 
#####################################################################
 
	solve( ab, 2 )	# 最初の nand の a,b を X,Y に固定
 
 

PWJlZ2luCgoKPjI5MyDjg4fjg5Xjgqnjg6vjg4jjga7lkI3nhKHjgZfjgZXjgpMgMjAyMC8wNC8yNyjmnIgpIDA5OjIxOjE5LjYzIElEOlZrKzZ1N0hiCj4gICAg5qyh44Gv5YWo5Yqg566X5Zmo44KS44KE44Gj44Gm44G/44KI44GG44CCCj4gICAg77yU5YWl5Yqb44K744Os44Kv44K/6L6644KK44Gn6ZmQ55WM44Gn44GX44KH44GG44CCCgrjgZXjgZnjgYzjgavnhKHnkIboh63jgYTjga7jgafljYrliqDnrpflmajjgafjgYrojLbjgpLmv4HjgZkKCuWNiuWKoOeul+WZqOOBryA144Gk44GuTkFOROOCsuODvOODiOOBp+ani+aIkOOBp+OBjeOCi+OBk+OBqOOBjOWIhuOBi+OBo+OBpuOBhOOCiyAo44G+44Gf44GvWE9SLE9S44KSMeWQhDHlgIspCuWFqOWKoOeul+WZqOOBryAy44Gk44Gu5Y2K5Yqg566X5Zmo44GoMeOBpOOBrk9S44Ky44O844OI44Gn5qeL5oiQ44Gn44GN44KLCuKAuyDmnIDkvY4x44Gk44GuTkFOROOCsuODvOODiOOBruWFpeWKm+OBryBBLELjgafjgYLjgovjgZPjgajjga/oh6rmmI7jgarjga7jgafjgIEx44Gk55uu44GuTkFOROOCsuODvOODiOOBruWFpeWKm+OBr0EsQuOBq+WbuuWumgrigLsg44Gd44Gu5aC05ZCI44Gu6Kej44GvIDk26YCa44KK44CC5Zu65a6a44GX44Gq44GE5aC05ZCI44Gu6Kej44GvIDc2OOmAmuOCiuOAggoKPWVuZAoKCSRhbnMgPSAwCglOYW5kUGllY2UgPSA1CglhYiA9IFsgMCwxLCAwLDAsIDAsMCwgMCwwLCAwLDAgXQkjIDHjgaTnm67jga5OQU5E44Ky44O844OI44Gu5YWl5Yqb44KSIEEsQuOBq+WbuuWumgoKZGVmIHByaW50X21hcDIoIGFiLCBjLCBzICkKCXRibCAgPSAld3sgWCBZIGMxIGMyIGMzIGM0IGM1IH0KCWFiLmVhY2hfd2l0aF9pbmRleHt8bixpfAoJCW0sIGEgPSBpLmRpdm1vZCgyKQoJCXByaW50ICIje3RibFtuXX0gIgoJfQoJcHV0cyAiIGMje2MrMX0gYyN7cysxfSIKCSRhbnMgKz0gMQplbmQKCmRlZiBjaGVjayggYWIgKQoJcmV0dXJuIGZhbHNlCXVubGVzcyBhYi5pbmRleCgwKSAmJiBhYi5pbmRleCgxKQkjIFgsWSDlhaXlipvjgpLkvb/jgo/jgarjgYTnianjga/mnp3liIjjgooKCWNudW0gPSBbMF0gKiBOYW5kUGllY2UJIyDlh7rlipvjg5Pjg4Pjg4jjg4bjg7zjg5bjg6sgZih4LHkpIC0+IGNfLCBzXwoJMi50aW1lc3t8eHwKCQkyLnRpbWVze3x5fAoJCQlsZyA9IFtdCgkJCWMgPSBbXQoJCQlhYi5lYWNoX3dpdGhfaW5kZXh7fG4saXwKCQkJCWNhc2UgbgoJCQkJd2hlbiAwOwlsZ1tpXSA9IHgKCQkJCXdoZW4gMTsJbGdbaV0gPSB5CgkJCQllbmQKCQkJfQoJCQlOYW5kUGllY2UudGltZXN7CgkJCQlOYW5kUGllY2UudGltZXN7fGNufAoJCQkJCW5leHQJaWYgY1tjbl0KCQkJCQlpZiBsZ1syKmNuXSAmJiBsZ1syKmNuKzFdCgkJCQkJCWNbY25dID0gKGxnWzIqY25dICYgbGdbMipjbisxXSkgXiAxCQkjIG5hbmQKCQkJCQkJYWIuZWFjaF93aXRoX2luZGV4e3xuLGl8CgkJCQkJCQljYXNlIG4KCQkJCQkJCXdoZW4gMjsJbGdbaV0gPSBjWzBdCgkJCQkJCQl3aGVuIDM7CWxnW2ldID0gY1sxXQoJCQkJCQkJd2hlbiA0OwlsZ1tpXSA9IGNbMl0KCQkJCQkJCXdoZW4gNTsJbGdbaV0gPSBjWzNdCgkJCQkJCQllbmQKCQkJCQkJfQoJCQkJCWVuZAoJCQkJfQoJCQl9CgkJCU5hbmRQaWVjZS50aW1lc3t8bnwKCQkJCWlmIGNbbl0gJiYgY251bVtuXQoJCQkJCWNudW1bbl0gPSAoY251bVtuXSA8PCAxKSB8IGNbbl0KCQkJCWVsc2UKCQkJCQljbnVtW25dID0gbmlsCgkJCQllbmQKCQkJfQoJCQlyZXR1cm4gZmFsc2UJaWYgY251bS5pbmRleCggbmlsICkJCSMg5p6d5YiI44KKCgkJfQoJfQoJaWYgY251bS5pbmRleCggMGIwMDAxICkgJiYgY251bS5pbmRleCggMGIwMTEwICkJIyDjg5Hjgr/jg7zjg7PmpJzntKIgSGFsZiBhZGRlciBDLCBTCgkJcHJpbnRfbWFwMiggYWIsIGNudW0uaW5kZXgoIDBiMDAwMSApLCBjbnVtLmluZGV4KCAwYjAxMTAgKSApCgllbmQKZW5kCgpkZWYgc29sdmUoIGFiLCBuID0gMCApCglyZXR1cm4JaWYgbiA+IDIgKiBOYW5kUGllY2UgLSAxCglzb2x2ZSggYWIsIG4gKyAxICkKCWNoZWNrKCBhYiApCWlmIG4gPT0gMiAqIE5hbmRQaWVjZSAtIDEKCWFiW25dICs9IDEKCWFiW25dICs9IDEJaWYgbiA+PiAxID09IGFiW25dIC0gMgkJIyDlh7rlipvjga/lhaXlipvjgavjgaTjgarjgZLjgarjgYQgKOS4gOauteOBruODq+ODvOODl+OBoOOBkeODgeOCp+ODg+OCrykKCWlmIGFiW25dID4gTmFuZFBpZWNlICsgMQoJCWFiW25dID0gMAoJCXJldHVybgoJZW5kCglzb2x2ZSggYWIsIG4gKQplbmQKCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwoKCXNvbHZlKCBhYiwgMiApCSMg5pyA5Yid44GuIG5hbmQg44GuIGEsYiDjgpIgWCxZIOOBq+WbuuWumgoK