結果

問題 No.3211 NAND Oracle
コンテスト
ユーザー Yakumo221
提出日時 2025-07-26 15:03:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 911 ms / 2,000 ms
コード長 1,256 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 90,332 KB
最終ジャッジ日時 2025-07-26 15:03:16
合計ジャッジ時間 6,591 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

def nand(a, b):
    """Return the NAND of two boolean values."""
    return not (a and b)


q, k = map(int, input().split())

if q <= 9:
    # naive solution
    ans = []

    vallist = [[] for i in range(4)]

    vallist[0] = [0,0]
    vallist[1] = [0,1]
    vallist[2] = [1,0]
    vallist[3] = [1,1]

    def solve(cnt):
        if cnt == q:
            maxval = 0
            for i in range(4):
                maxval = max(maxval, sum(vallist[i]))
            if maxval <= k:
                print("Yes")
                for x,y in ans:
                    print(x,y)
                exit()
            return

        for x in range(cnt+2):
            for y in range(x+1, cnt+2):
                for i in range(4):
                    vallist[i].append(nand(vallist[i][x], vallist[i][y]))
                ans.append((x+1, y+1))
                solve(cnt + 1)
                for i in range(4):
                    vallist[i].pop()
                ans.pop()
    
    solve(0)
    print("No")
else:
    # x = 0/0
    if k >= 5:
        print("Yes")
        ans = [(1,2), (1,2), (3,4), (4,5), (4,5)]
        for i in range(6, q + 1):
            ans.append((6, 7))
        
        for x, y in ans:
            print(x, y)

    else:
        print("No")
0