結果

問題 No.355 数当てゲーム(2)
コンテスト
ユーザー yukirin
提出日時 2016-04-02 15:37:38
言語 Go
(1.23.4)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 2,295 bytes
コンパイル時間 13,769 ms
コンパイル使用メモリ 240,196 KB
実行使用メモリ 25,496 KB
平均クエリ数 41.62
最終ジャッジ日時 2024-07-16 23:27:12
合計ジャッジ時間 17,929 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	ns, c1, c2 := first()
	if c1 == 4 {
		return
	}

	ans, count, all, found := make([]int, 4), 0, false, false
	for j := 0; count < 2 && j < 5; j++ {
		for i := 0; i < 10; i++ {
			if check(ns, i) {
				continue
			}
			tmp := ns[j]
			ns[j] = i
			x, y := inOut(ns)
			ns[j] = tmp
			if x == 4 {
				return
			}

			if c1+c2 > x+y {
				ans[count] = tmp
				count++
				break
			}
		}
	}

	candi := make([]int, 0, 8)
	for i := 0; i < 10; i++ {
		if ans[0] == i || ans[1] == i {
			continue
		}
		candi = append(candi, i)
	}

	comb(candi, 2, func(nums []int) {
		if all || found {
			return
		}
		copy(ans[2:4], nums)
		x, y := inOut(ans)
		if x == 4 {
			found = true
		}

		if x+y == 4 {
			all = true
		}
	})

	perm(ans, 4, func(nums []int) {
		if found {
			return
		}
		x, _ := inOut(nums)
		if x == 4 {
			found = true
		}
	})
}

func check(ns []int, n int) bool {
	for _, v := range ns {
		if n == v {
			return true
		}
	}
	return false
}

func first() ([]int, int, int) {
	nss := [][]int{
		{0, 1, 2, 3}, {4, 5, 6, 7}, {6, 7, 8, 9},
	}

	for _, v := range nss {
		x, y := inOut(v)
		if x+y >= 2 {
			return v, x, y
		}
	}
	return nil, 0, 0
}

func inOut(ns []int) (int, int) {
	fmt.Println(ns[0], ns[1], ns[2], ns[3])
	os.Stdout.Sync()
	return nextInt(), nextInt()
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextLine())
	return i
}

func comb(a []int, r int, fn func([]int)) {
	if r > len(a) || r < 1 {
		return
	}

	var f func([]int, int, int)
	f = func(ret []int, last, c int) {
		if c == 0 {
			fn(ret)
			return
		}

		c--
		for i, v := range a[last : len(a)-c] {
			ret[r-c-1] = v
			f(ret, i+last+1, c)
		}
	}

	ret := make([]int, r)
	f(ret, 0, r)
}

func perm(a []int, r int, fn func([]int)) {
	permL := make([]int, r)
	f := func(s []int) {
		copy(permL, s)

		k := 1
		c := make([]int, r+1)
		for i := 1; i < len(c); i++ {
			c[i] = i
		}

		for k < r {
			i := 0
			if k&1 == 1 {
				i = c[k]
			}

			permL[k], permL[i] = permL[i], permL[k]

			fn(permL)
			for k = 1; c[k] == 0; k++ {
				c[k] = k
			}
			c[k]--
		}
	}

	if r < 2 {
		comb(a, r, fn)
		return
	}
	comb(a, r, f)
}
0