=begin 286 デフォルトの名無しさん 2020/04/24(金) 20:56:21.49 ID:pA5GOauV お題 XORゲートは4つのNANDゲートで構成できることが知られている この構成方法をプログラムで探索せよ i番目のNANDゲートの入力を(ai,bi)、出力をciとする XORゲートの入力を(X,Y)、出力をZとする 出力例 X->a1 Y->b1 X->a2 c1->b2 Y->a3 c1->b3 c2->a4 c3->b4 c4->Z =end # 自由度は入力の接続先。出力のどれかと必ず接続する。 # 入力同士は接続できる (同じ出力に接続できる) # 出力同士は接続できない # どこにもつながらない出力は無いはず # 出力 X,Y, c1,c2,c3,c4 0..5 # 入力 a1,b1, a2,b2, a3,b3, a4,b4 ab[0..7] # c1..4 いずれか -> Z NandPiece = 4 OutputMax = 2 + NandPiece InputMax = 2 * NandPiece Ntbl = %w{ X Y c1 c2 c3 c4 } $ans = 0 def print_map2( ab, z ) puts [ ab.map{|n| Ntbl[n]}, Ntbl[z] ].join(' ') end # お題の出力フォーマット def print_map( ab, z ) ab.each_with_index{|n,i| m, a = i.divmod(2) puts " %3s -> %s%d" % [ Ntbl[n], (97+a).chr, m+1 ] } puts " #{Ntbl[z]} -> Z\n\n" end def check( ab ) fc = [ true, true ] # 出力確定フラグ x,y,c1..c4 nn = NandPiece # 未確定 個数 oc = [ 0b1010, 0b1100 ] # 出力値(x,y)(00, 10, 01, 11) c1..c4 NandPiece.times{ nf = false NandPiece.times{|cn| next if fc[ cn+2 ] a, b = ab[2*cn], ab[2*cn+1] next unless fc[a] && fc[b] oc[ cn+2 ] = oc[a] & oc[b] ^ 0b1111 # nand fc[ cn+2 ] = true nn -= 1 nf = true } break if nn == 0 return false unless nf } cn = oc.rindex( 0b0110 ) # xor パターン検索 return false unless cn $ans += 1 print_map2( ab, cn ) end def solve( ab, n = 0 ) begin solve( ab, n + 1 ) if n < InputMax-1 check( ab ) if n == InputMax-1 && ab.uniq.size == 5 # Nand出力を3つ使わない物は排除、X,Y はどちらも必須 ab[n] += 1 ab[n] += 1 if n >> 1 == ab[n] - 2 # 出力は入力につなげない (一段のループだけチェック) end while ab[n] <= OutputMax-1 ab[n] = 0 end ##################################################################### ab = [ 0 ] * InputMax solve( ab ) puts "Done. #{$ans}"
Standard input is empty
X Y X c1 Y c1 c2 c3 c4 X Y X c1 Y c1 c3 c2 c4 X Y X c1 c1 Y c2 c3 c4 X Y X c1 c1 Y c3 c2 c4 X Y X c1 c2 c4 Y c1 c3 X Y X c1 c2 c4 c1 Y c3 X Y X c1 c4 c2 Y c1 c3 X Y X c1 c4 c2 c1 Y c3 X Y Y c1 X c1 c2 c3 c4 X Y Y c1 X c1 c3 c2 c4 X Y Y c1 c1 X c2 c3 c4 X Y Y c1 c1 X c3 c2 c4 X Y Y c1 c2 c4 X c1 c3 X Y Y c1 c2 c4 c1 X c3 X Y Y c1 c4 c2 X c1 c3 X Y Y c1 c4 c2 c1 X c3 X Y c1 X Y c1 c2 c3 c4 X Y c1 X Y c1 c3 c2 c4 X Y c1 X c1 Y c2 c3 c4 X Y c1 X c1 Y c3 c2 c4 X Y c1 X c2 c4 Y c1 c3 X Y c1 X c2 c4 c1 Y c3 X Y c1 X c4 c2 Y c1 c3 X Y c1 X c4 c2 c1 Y c3 X Y c1 Y X c1 c2 c3 c4 X Y c1 Y X c1 c3 c2 c4 X Y c1 Y c1 X c2 c3 c4 X Y c1 Y c1 X c3 c2 c4 X Y c1 Y c2 c4 X c1 c3 X Y c1 Y c2 c4 c1 X c3 X Y c1 Y c4 c2 X c1 c3 X Y c1 Y c4 c2 c1 X c3 X Y c3 c4 X c1 Y c1 c2 X Y c3 c4 X c1 c1 Y c2 X Y c3 c4 Y c1 X c1 c2 X Y c3 c4 Y c1 c1 X c2 X Y c3 c4 c1 X Y c1 c2 X Y c3 c4 c1 X c1 Y c2 X Y c3 c4 c1 Y X c1 c2 X Y c3 c4 c1 Y c1 X c2 X Y c4 c3 X c1 Y c1 c2 X Y c4 c3 X c1 c1 Y c2 X Y c4 c3 Y c1 X c1 c2 X Y c4 c3 Y c1 c1 X c2 X Y c4 c3 c1 X Y c1 c2 X Y c4 c3 c1 X c1 Y c2 X Y c4 c3 c1 Y X c1 c2 X Y c4 c3 c1 Y c1 X c2 X c2 X Y Y c2 c1 c3 c4 X c2 X Y Y c2 c3 c1 c4 X c2 X Y c1 c4 Y c2 c3 X c2 X Y c1 c4 c2 Y c3 X c2 X Y c2 Y c1 c3 c4 X c2 X Y c2 Y c3 c1 c4 X c2 X Y c4 c1 Y c2 c3 X c2 X Y c4 c1 c2 Y c3 X c2 Y X Y c2 c1 c3 c4 X c2 Y X Y c2 c3 c1 c4 X c2 Y X c1 c4 Y c2 c3 X c2 Y X c1 c4 c2 Y c3 X c2 Y X c2 Y c1 c3 c4 X c2 Y X c2 Y c3 c1 c4 X c2 Y X c4 c1 Y c2 c3 X c2 Y X c4 c1 c2 Y c3 X c3 Y c3 X Y c1 c2 c4 X c3 Y c3 X Y c2 c1 c4 X c3 Y c3 Y X c1 c2 c4 X c3 Y c3 Y X c2 c1 c4 X c3 c1 c4 X Y Y c3 c2 X c3 c1 c4 X Y c3 Y c2 X c3 c1 c4 Y X Y c3 c2 X c3 c1 c4 Y X c3 Y c2 X c3 c3 Y X Y c1 c2 c4 X c3 c3 Y X Y c2 c1 c4 X c3 c3 Y Y X c1 c2 c4 X c3 c3 Y Y X c2 c1 c4 X c3 c4 c1 X Y Y c3 c2 X c3 c4 c1 X Y c3 Y c2 X c3 c4 c1 Y X Y c3 c2 X c3 c4 c1 Y X c3 Y c2 X c4 Y c4 c1 c2 X Y c3 X c4 Y c4 c1 c2 Y X c3 X c4 Y c4 c2 c1 X Y c3 X c4 Y c4 c2 c1 Y X c3 X c4 c1 c3 Y c4 X Y c2 X c4 c1 c3 Y c4 Y X c2 X c4 c1 c3 c4 Y X Y c2 X c4 c1 c3 c4 Y Y X c2 X c4 c3 c1 Y c4 X Y c2 X c4 c3 c1 Y c4 Y X c2 X c4 c3 c1 c4 Y X Y c2 X c4 c3 c1 c4 Y Y X c2 X c4 c4 Y c1 c2 X Y c3 X c4 c4 Y c1 c2 Y X c3 X c4 c4 Y c2 c1 X Y c3 X c4 c4 Y c2 c1 Y X c3 Y X X c1 Y c1 c2 c3 c4 Y X X c1 Y c1 c3 c2 c4 Y X X c1 c1 Y c2 c3 c4 Y X X c1 c1 Y c3 c2 c4 Y X X c1 c2 c4 Y c1 c3 Y X X c1 c2 c4 c1 Y c3 Y X X c1 c4 c2 Y c1 c3 Y X X c1 c4 c2 c1 Y c3 Y X Y c1 X c1 c2 c3 c4 Y X Y c1 X c1 c3 c2 c4 Y X Y c1 c1 X c2 c3 c4 Y X Y c1 c1 X c3 c2 c4 Y X Y c1 c2 c4 X c1 c3 Y X Y c1 c2 c4 c1 X c3 Y X Y c1 c4 c2 X c1 c3 Y X Y c1 c4 c2 c1 X c3 Y X c1 X Y c1 c2 c3 c4 Y X c1 X Y c1 c3 c2 c4 Y X c1 X c1 Y c2 c3 c4 Y X c1 X c1 Y c3 c2 c4 Y X c1 X c2 c4 Y c1 c3 Y X c1 X c2 c4 c1 Y c3 Y X c1 X c4 c2 Y c1 c3 Y X c1 X c4 c2 c1 Y c3 Y X c1 Y X c1 c2 c3 c4 Y X c1 Y X c1 c3 c2 c4 Y X c1 Y c1 X c2 c3 c4 Y X c1 Y c1 X c3 c2 c4 Y X c1 Y c2 c4 X c1 c3 Y X c1 Y c2 c4 c1 X c3 Y X c1 Y c4 c2 X c1 c3 Y X c1 Y c4 c2 c1 X c3 Y X c3 c4 X c1 Y c1 c2 Y X c3 c4 X c1 c1 Y c2 Y X c3 c4 Y c1 X c1 c2 Y X c3 c4 Y c1 c1 X c2 Y X c3 c4 c1 X Y c1 c2 Y X c3 c4 c1 X c1 Y c2 Y X c3 c4 c1 Y X c1 c2 Y X c3 c4 c1 Y c1 X c2 Y X c4 c3 X c1 Y c1 c2 Y X c4 c3 X c1 c1 Y c2 Y X c4 c3 Y c1 X c1 c2 Y X c4 c3 Y c1 c1 X c2 Y X c4 c3 c1 X Y c1 c2 Y X c4 c3 c1 X c1 Y c2 Y X c4 c3 c1 Y X c1 c2 Y X c4 c3 c1 Y c1 X c2 Y c2 X Y X c2 c1 c3 c4 Y c2 X Y X c2 c3 c1 c4 Y c2 X Y c1 c4 X c2 c3 Y c2 X Y c1 c4 c2 X c3 Y c2 X Y c2 X c1 c3 c4 Y c2 X Y c2 X c3 c1 c4 Y c2 X Y c4 c1 X c2 c3 Y c2 X Y c4 c1 c2 X c3 Y c2 Y X X c2 c1 c3 c4 Y c2 Y X X c2 c3 c1 c4 Y c2 Y X c1 c4 X c2 c3 Y c2 Y X c1 c4 c2 X c3 Y c2 Y X c2 X c1 c3 c4 Y c2 Y X c2 X c3 c1 c4 Y c2 Y X c4 c1 X c2 c3 Y c2 Y X c4 c1 c2 X c3 Y c3 X c3 X Y c1 c2 c4 Y c3 X c3 X Y c2 c1 c4 Y c3 X c3 Y X c1 c2 c4 Y c3 X c3 Y X c2 c1 c4 Y c3 c1 c4 X Y X c3 c2 Y c3 c1 c4 X Y c3 X c2 Y c3 c1 c4 Y X X c3 c2 Y c3 c1 c4 Y X c3 X c2 Y c3 c3 X X Y c1 c2 c4 Y c3 c3 X X Y c2 c1 c4 Y c3 c3 X Y X c1 c2 c4 Y c3 c3 X Y X c2 c1 c4 Y c3 c4 c1 X Y X c3 c2 Y c3 c4 c1 X Y c3 X c2 Y c3 c4 c1 Y X X c3 c2 Y c3 c4 c1 Y X c3 X c2 Y c4 X c4 c1 c2 X Y c3 Y c4 X c4 c1 c2 Y X c3 Y c4 X c4 c2 c1 X Y c3 Y c4 X c4 c2 c1 Y X c3 Y c4 c1 c3 X c4 X Y c2 Y c4 c1 c3 X c4 Y X c2 Y c4 c1 c3 c4 X X Y c2 Y c4 c1 c3 c4 X Y X c2 Y c4 c3 c1 X c4 X Y c2 Y c4 c3 c1 X c4 Y X c2 Y c4 c3 c1 c4 X X Y c2 Y c4 c3 c1 c4 X Y X c2 Y c4 c4 X c1 c2 X Y c3 Y c4 c4 X c1 c2 Y X c3 Y c4 c4 X c2 c1 X Y c3 Y c4 c4 X c2 c1 Y X c3 c2 X X Y Y c2 c1 c3 c4 c2 X X Y Y c2 c3 c1 c4 c2 X X Y c1 c4 Y c2 c3 c2 X X Y c1 c4 c2 Y c3 c2 X X Y c2 Y c1 c3 c4 c2 X X Y c2 Y c3 c1 c4 c2 X X Y c4 c1 Y c2 c3 c2 X X Y c4 c1 c2 Y c3 c2 X Y X Y c2 c1 c3 c4 c2 X Y X Y c2 c3 c1 c4 c2 X Y X c1 c4 Y c2 c3 c2 X Y X c1 c4 c2 Y c3 c2 X Y X c2 Y c1 c3 c4 c2 X Y X c2 Y c3 c1 c4 c2 X Y X c4 c1 Y c2 c3 c2 X Y X c4 c1 c2 Y c3 c2 Y X Y X c2 c1 c3 c4 c2 Y X Y X c2 c3 c1 c4 c2 Y X Y c1 c4 X c2 c3 c2 Y X Y c1 c4 c2 X c3 c2 Y X Y c2 X c1 c3 c4 c2 Y X Y c2 X c3 c1 c4 c2 Y X Y c4 c1 X c2 c3 c2 Y X Y c4 c1 c2 X c3 c2 Y Y X X c2 c1 c3 c4 c2 Y Y X X c2 c3 c1 c4 c2 Y Y X c1 c4 X c2 c3 c2 Y Y X c1 c4 c2 X c3 c2 Y Y X c2 X c1 c3 c4 c2 Y Y X c2 X c3 c1 c4 c2 Y Y X c4 c1 X c2 c3 c2 Y Y X c4 c1 c2 X c3 c2 c3 X c4 Y c4 X Y c1 c2 c3 X c4 Y c4 Y X c1 c2 c3 X c4 c4 Y X Y c1 c2 c3 X c4 c4 Y Y X c1 c2 c3 Y c4 X c4 X Y c1 c2 c3 Y c4 X c4 Y X c1 c2 c3 Y c4 c4 X X Y c1 c2 c3 Y c4 c4 X Y X c1 c2 c3 c4 X Y c4 X Y c1 c2 c3 c4 X Y c4 Y X c1 c2 c3 c4 X c4 Y X Y c1 c2 c3 c4 X c4 Y Y X c1 c2 c3 c4 Y X c4 X Y c1 c2 c3 c4 Y X c4 Y X c1 c2 c3 c4 Y c4 X X Y c1 c2 c3 c4 Y c4 X Y X c1 c2 c4 X c3 X Y Y c3 c1 c2 c4 X c3 X Y c3 Y c1 c2 c4 X c3 Y X Y c3 c1 c2 c4 X c3 Y X c3 Y c1 c2 c4 Y c3 X Y X c3 c1 c2 c4 Y c3 X Y c3 X c1 c2 c4 Y c3 Y X X c3 c1 c2 c4 Y c3 Y X c3 X c1 c2 c4 c3 X X Y Y c3 c1 c2 c4 c3 X X Y c3 Y c1 c2 c4 c3 X Y X Y c3 c1 c2 c4 c3 X Y X c3 Y c1 c2 c4 c3 Y X Y X c3 c1 c2 c4 c3 Y X Y c3 X c1 c2 c4 c3 Y Y X X c3 c1 c2 c4 c3 Y Y X c3 X c1 c3 X Y c3 X Y c1 c2 c4 c3 X Y c3 X Y c2 c1 c4 c3 X Y c3 Y X c1 c2 c4 c3 X Y c3 Y X c2 c1 c4 c3 X c1 c4 X Y Y c3 c2 c3 X c1 c4 X Y c3 Y c2 c3 X c1 c4 Y X Y c3 c2 c3 X c1 c4 Y X c3 Y c2 c3 X c3 Y X Y c1 c2 c4 c3 X c3 Y X Y c2 c1 c4 c3 X c3 Y Y X c1 c2 c4 c3 X c3 Y Y X c2 c1 c4 c3 X c4 c1 X Y Y c3 c2 c3 X c4 c1 X Y c3 Y c2 c3 X c4 c1 Y X Y c3 c2 c3 X c4 c1 Y X c3 Y c2 c3 Y X c3 X Y c1 c2 c4 c3 Y X c3 X Y c2 c1 c4 c3 Y X c3 Y X c1 c2 c4 c3 Y X c3 Y X c2 c1 c4 c3 Y c1 c4 X Y X c3 c2 c3 Y c1 c4 X Y c3 X c2 c3 Y c1 c4 Y X X c3 c2 c3 Y c1 c4 Y X c3 X c2 c3 Y c3 X X Y c1 c2 c4 c3 Y c3 X X Y c2 c1 c4 c3 Y c3 X Y X c1 c2 c4 c3 Y c3 X Y X c2 c1 c4 c3 Y c4 c1 X Y X c3 c2 c3 Y c4 c1 X Y c3 X c2 c3 Y c4 c1 Y X X c3 c2 c3 Y c4 c1 Y X c3 X c2 c3 c2 X c4 Y c4 X Y c1 c3 c2 X c4 Y c4 Y X c1 c3 c2 X c4 c4 Y X Y c1 c3 c2 X c4 c4 Y Y X c1 c3 c2 Y c4 X c4 X Y c1 c3 c2 Y c4 X c4 Y X c1 c3 c2 Y c4 c4 X X Y c1 c3 c2 Y c4 c4 X Y X c1 c3 c2 c4 X Y c4 X Y c1 c3 c2 c4 X Y c4 Y X c1 c3 c2 c4 X c4 Y X Y c1 c3 c2 c4 X c4 Y Y X c1 c3 c2 c4 Y X c4 X Y c1 c3 c2 c4 Y X c4 Y X c1 c3 c2 c4 Y c4 X X Y c1 c3 c2 c4 Y c4 X Y X c1 c3 c4 X Y X c2 Y c2 c1 c3 c4 X Y X c2 c2 Y c1 c3 c4 X Y Y c2 X c2 c1 c3 c4 X Y Y c2 c2 X c1 c3 c4 X Y c2 X Y c2 c1 c3 c4 X Y c2 X c2 Y c1 c3 c4 X Y c2 Y X c2 c1 c3 c4 X Y c2 Y c2 X c1 c3 c4 Y X X c2 Y c2 c1 c3 c4 Y X X c2 c2 Y c1 c3 c4 Y X Y c2 X c2 c1 c3 c4 Y X Y c2 c2 X c1 c3 c4 Y X c2 X Y c2 c1 c3 c4 Y X c2 X c2 Y c1 c3 c4 Y X c2 Y X c2 c1 c3 c4 Y X c2 Y c2 X c1 c4 X Y c4 c1 c2 X Y c3 c4 X Y c4 c1 c2 Y X c3 c4 X Y c4 c2 c1 X Y c3 c4 X Y c4 c2 c1 Y X c3 c4 X c1 c3 Y c4 X Y c2 c4 X c1 c3 Y c4 Y X c2 c4 X c1 c3 c4 Y X Y c2 c4 X c1 c3 c4 Y Y X c2 c4 X c3 c1 Y c4 X Y c2 c4 X c3 c1 Y c4 Y X c2 c4 X c3 c1 c4 Y X Y c2 c4 X c3 c1 c4 Y Y X c2 c4 X c4 Y c1 c2 X Y c3 c4 X c4 Y c1 c2 Y X c3 c4 X c4 Y c2 c1 X Y c3 c4 X c4 Y c2 c1 Y X c3 c4 Y X c4 c1 c2 X Y c3 c4 Y X c4 c1 c2 Y X c3 c4 Y X c4 c2 c1 X Y c3 c4 Y X c4 c2 c1 Y X c3 c4 Y c1 c3 X c4 X Y c2 c4 Y c1 c3 X c4 Y X c2 c4 Y c1 c3 c4 X X Y c2 c4 Y c1 c3 c4 X Y X c2 c4 Y c3 c1 X c4 X Y c2 c4 Y c3 c1 X c4 Y X c2 c4 Y c3 c1 c4 X X Y c2 c4 Y c3 c1 c4 X Y X c2 c4 Y c4 X c1 c2 X Y c3 c4 Y c4 X c1 c2 Y X c3 c4 Y c4 X c2 c1 X Y c3 c4 Y c4 X c2 c1 Y X c3 c4 c2 X c3 X Y Y c3 c1 c4 c2 X c3 X Y c3 Y c1 c4 c2 X c3 Y X Y c3 c1 c4 c2 X c3 Y X c3 Y c1 c4 c2 Y c3 X Y X c3 c1 c4 c2 Y c3 X Y c3 X c1 c4 c2 Y c3 Y X X c3 c1 c4 c2 Y c3 Y X c3 X c1 c4 c2 c3 X X Y Y c3 c1 c4 c2 c3 X X Y c3 Y c1 c4 c2 c3 X Y X Y c3 c1 c4 c2 c3 X Y X c3 Y c1 c4 c2 c3 Y X Y X c3 c1 c4 c2 c3 Y X Y c3 X c1 c4 c2 c3 Y Y X X c3 c1 c4 c2 c3 Y Y X c3 X c1 c4 c3 X Y X c2 Y c2 c1 c4 c3 X Y X c2 c2 Y c1 c4 c3 X Y Y c2 X c2 c1 c4 c3 X Y Y c2 c2 X c1 c4 c3 X Y c2 X Y c2 c1 c4 c3 X Y c2 X c2 Y c1 c4 c3 X Y c2 Y X c2 c1 c4 c3 X Y c2 Y c2 X c1 c4 c3 Y X X c2 Y c2 c1 c4 c3 Y X X c2 c2 Y c1 c4 c3 Y X Y c2 X c2 c1 c4 c3 Y X Y c2 c2 X c1 c4 c3 Y X c2 X Y c2 c1 c4 c3 Y X c2 X c2 Y c1 c4 c3 Y X c2 Y X c2 c1 c4 c3 Y X c2 Y c2 X c1 Done. 384