結果

問題 No.3211 NAND Oracle
コンテスト
ユーザー ID 21712
提出日時 2025-07-31 02:38:31
言語 Go
(1.23.4)
結果
AC  
実行時間 377 ms / 2,000 ms
コード長 2,132 bytes
コンパイル時間 12,360 ms
コンパイル使用メモリ 253,128 KB
実行使用メモリ 10,020 KB
最終ジャッジ日時 2025-07-31 02:38:52
合計ジャッジ時間 19,888 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 {
		Println(`Yes
1 2
1 2
1 2
3 4
3 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 check() {
	orig := [][]int{
		append(make([]int, 0, 10), 0, 0)[:10],
		append(make([]int, 0, 10), 0, 1)[:10],
		append(make([]int, 0, 10), 1, 0)[:10],
		append(make([]int, 0, 10), 1, 1)[:10],
	}
	bestSum := make([]int, 10)
	for i := range bestSum {
		bestSum[i] = 9999
	}
	bestCmd := make([][]int, 10)
	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 > 8 {
			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