結果

問題 No.3211 NAND Oracle
コンテスト
ユーザー ID 21712
提出日時 2025-07-31 02:37:39
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 3,002 bytes
コンパイル時間 12,715 ms
コンパイル使用メモリ 256,444 KB
実行使用メモリ 7,764 KB
最終ジャッジ日時 2025-07-31 02:38:00
合計ジャッジ時間 18,617 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 20 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func Xmain() {
	var q,k int
	Scan(&q,&k)
	if q == 5 && k >= 4 {
		Println(`Yes
1 2
1 2
1 2
3 4
3 4`)
		// [0,0] [0,1] [1,0] [1,1]  sum<=2
		// Q=1 -> 1,2
		// [0,0,1] [0,1,1] [1,0,1] [1,1,0] sum<=2
		// Q=2 -> 1,2
		// [0,0,1,1] [0,1,1,1] [1,0,1,1] [1,1,0,0] sum<=3
		// Q=3 -> 1,2
		// [0,0,1,1,1] [0,1,1,1,1] [1,0,1,1,1] [1,1,0,0,0] sum<=4
		// Q=4 -> 3,4
		// [0,0,1,1,1,0] [0,1,1,1,1,0] [1,0,1,1,1,0] [1,1,0,0,0,1] sum<=4
		// Q=5 -> 3,4
		// [0,0,1,1,1,0,0] [0,1,1,1,1,0,0] [1,0,1,1,1,0,0] [1,1,0,0,0,1,1] sum<=4
		return
	}
	// [0,0] [0,1] [1,0] [1,1]  sum<=2
	// Q=1 -> 1,2
	// [0,0,1] [0,1,1] [1,0,1] [1,1,0] sum<=2
	// Q=2 -> 1,2
	// [0,0,1,1] [0,1,1,1] [1,0,1,1] [1,1,0,0] sum<=3
	// Q=3 -> 3,4
	// [0,0,1,1,0] [0,1,1,1,0] [1,0,1,1,0] [1,1,0,0,1] sum<=3
	// Q=4 -> 4,5
	// [0,0,1,1,0,1] [0,1,1,1,0,1] [1,0,1,1,0,1] [1,1,0,0,1,1] sum<=4
	// Q=5 -> 4,5
	// [0,0,1,1,0,1,1] [0,1,1,1,0,1,1] [1,0,1,1,0,1,1] [1,1,0,0,1,1,1] sum<=5
	// Q>=6 -> 6,7
	// [0,0,1,1,0,1,1,0] [0,1,1,1,0,1,1,0] [1,0,1,1,0,1,1,0] [1,1,0,0,1,1,1,0] sum<=5
	var ans bool
	switch q {
		case 1:
			ans = k >= 2
		case 2,3:
			ans = k >= 3
		case 4:
			ans = k >= 4
		default:
			ans = k >= 5
	}
	if ans {
		Println("Yes")
	} else {
		Println("No")
		return
	}
	ops := make([]string, 0, q)
	ops = append(ops, "1 2", "1 2", "3 4", "4 5", "4 5")
	for len(ops) < q {
		ops = append(ops, "6 7")
	}
	for _, op := range ops[:q] {
		Println(op)
	}
}

func init() {
	// check()
}

func main() {
	const X = 10
	orig := [][]int{
		append(make([]int, 0, X), 0, 0)[:X],
		append(make([]int, 0, X), 0, 1)[:X],
		append(make([]int, 0, X), 1, 0)[:X],
		append(make([]int, 0, X), 1, 1)[:X],
	}
	bestSum := make([]int, X)
	for i := range bestSum {
		bestSum[i] = 9999
	}
	bestCmd := make([][]int, X)
	var dfs func(sz int, arr [][]int, ops, sum []int)
	dfs = func(sz int, arr [][]int, ops, sum []int) {
		if s := max(sum[0],sum[1],sum[2],sum[3]); s < bestSum[sz] {
			bestSum[sz] = s
			tmp := make([]int, len(ops))
			copy(tmp, ops)
			bestCmd[sz] = tmp
		}
		if sz+1 >= X {
			return
		}
		for i := 0; i < sz; i++ {
			for j := i+1; j < sz; j++ {
				for _, ar := range arr {
					ar[sz] = 1^(ar[i] & ar[j])
				}
				ops = append(ops, i+1, j+1)
				for i, ar := range arr {
					sum[i] += ar[sz]
				}
				dfs(sz+1, arr, ops, sum)
				ops = ops[:len(ops)-2]
				for i, ar := range arr {
					sum[i] -= ar[sz]
				}
			}
		}
	}
	dfs(2, orig, make([]int, 0, 100), []int{0,1,1,2})
	for i, s := range bestSum {
		println(Sprintf("q=%d, k=%d, %#v", i-2, s, bestCmd[i]))
	}
	{
		var q, k int
		Scan(&q,&k)
		ops := []int{}
		if q+2 < len(bestSum) {
			if k < bestSum[q+2] {
				Println("No")
				return
			}
			ops = bestCmd[q+2]
		} else {
			if k < bestSum[X-1] {
				Println("No")
				return
			}
			ops = make([]int, len(bestCmd[X-1]), q*2)
			copy(ops, bestCmd[X-1])
			for len(ops) < q*2 {
				ops = append(ops, 3, 4)
			}
		}
		Println("Yes")
		for i := 0; i < q; i++ {
			Println(ops[i*2], ops[i*2+1])
		}
	}
}
0