#85086 (Go) No.355 数当てゲーム(2)

提出ソース

結果

問題	No.355 数当てゲーム(2)
ユーザー	yukirin
提出日時	2016-04-02 15:37:38
言語	Go (1.22.1)
結果	AC
実行時間	27 ms / 2,000 ms
コード長	2,295 bytes
コンパイル時間	10,895 ms
コンパイル使用メモリ	211,852 KB
実行使用メモリ	24,468 KB
平均クエリ数	41.62
最終ジャッジ日時	2023-09-23 23:36:34
合計ジャッジ時間	14,553 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	27 ms 23,436 KB
testcase_01	AC	22 ms 24,324 KB
testcase_02	AC	22 ms 24,024 KB
testcase_03	AC	22 ms 23,448 KB
testcase_04	AC	22 ms 24,036 KB
testcase_05	AC	23 ms 23,556 KB
testcase_06	AC	22 ms 23,412 KB
testcase_07	AC	22 ms 23,568 KB
testcase_08	AC	21 ms 24,228 KB
testcase_09	AC	21 ms 23,652 KB
testcase_10	AC	21 ms 23,976 KB
testcase_11	AC	22 ms 23,556 KB
testcase_12	AC	22 ms 23,988 KB
testcase_13	AC	21 ms 23,412 KB
testcase_14	AC	22 ms 24,060 KB
testcase_15	AC	22 ms 23,652 KB
testcase_16	AC	21 ms 23,664 KB
testcase_17	AC	21 ms 23,388 KB
testcase_18	AC	21 ms 23,388 KB
testcase_19	AC	21 ms 24,204 KB
testcase_20	AC	21 ms 24,036 KB
testcase_21	AC	20 ms 23,640 KB
testcase_22	AC	20 ms 24,288 KB
testcase_23	AC	22 ms 23,544 KB
testcase_24	AC	21 ms 24,024 KB
testcase_25	AC	22 ms 23,436 KB
testcase_26	AC	21 ms 24,456 KB
testcase_27	AC	21 ms 23,568 KB
testcase_28	AC	27 ms 23,400 KB
testcase_29	AC	22 ms 24,060 KB
testcase_30	AC	21 ms 23,436 KB
testcase_31	AC	23 ms 23,688 KB
testcase_32	AC	21 ms 23,676 KB
testcase_33	AC	22 ms 23,364 KB
testcase_34	AC	22 ms 23,388 KB
testcase_35	AC	19 ms 23,412 KB
testcase_36	AC	22 ms 23,976 KB
testcase_37	AC	21 ms 23,424 KB
testcase_38	AC	21 ms 23,388 KB
testcase_39	AC	21 ms 23,400 KB
testcase_40	AC	26 ms 23,664 KB
testcase_41	AC	22 ms 23,976 KB
testcase_42	AC	21 ms 23,388 KB
testcase_43	AC	21 ms 23,376 KB
testcase_44	AC	22 ms 23,376 KB
testcase_45	AC	22 ms 23,544 KB
testcase_46	AC	21 ms 24,408 KB
testcase_47	AC	21 ms 24,468 KB
testcase_48	AC	22 ms 23,568 KB
testcase_49	AC	22 ms 23,424 KB
testcase_50	AC	22 ms 23,676 KB
testcase_51	AC	19 ms 23,652 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)
}

yukicoder

結果

テストケース

ソースコード