結果

問題 No.3211 NAND Oracle
ユーザー ID 21712
提出日時 2025-07-31 02:36:34
言語 Go
(1.23.4)
結果
AC  
実行時間 507 ms / 2,000 ms
コード長 3,213 bytes
コンパイル時間 10,734 ms
コンパイル使用メモリ 240,400 KB
実行使用メモリ 12,396 KB
最終ジャッジ日時 2025-07-31 02:36:55
合計ジャッジ時間 18,480 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	var q,k int
	Scan(&q,&k)
	if q == 5 && k >= 4 {
		ops := []string{"1 2", "1 2", "1 2", "3 4", "3 4"}
		doOps(q, k, ops)
		Println("Yes")
		for _, op := range ops {
			Println(op)
		}
		// [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)
	}
	doOps(q, k, ops[:q])
}

func doOps(q, k int, ops []string) {
	const X = 10
	arr := [][]int{
		append(make([]int, 0, X), 0, 0),
		append(make([]int, 0, X), 0, 1),
		append(make([]int, 0, X), 1, 0),
		append(make([]int, 0, X), 1, 1),
	}
	sum := []int{0, 1, 1, 2}
	for _, op := range ops {
		var x, y int
		Sscan(op, &x, &y)
		for j, ar := range arr {
			v := 1^(ar[x-1]&ar[y-1])
			sum[j] += v
			if len(ar) < X {
				arr[j] = append(ar, v)
			}
		}
	}
	if max(sum[0],sum[1],sum[2],sum[3]) > k {
		println(Sprint(arr))
		println(Sprint(sum))
		panic("bug")
	}
}

func init() {
	check()
}

func check() {
	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]))
	}
}
0