2019-1C Problem B

Final solution

// package, import, etc...

func start() {
	var t, F int
	mustReadLineOfInts(&t, &F)
	for i := 0; i < t; i++ {
		test(F)
	}
}

const A = byte('A')

type Pib struct {
	id  int
	arr []byte
}

var fact [6]int = [6]int{1, 1, 2, 6, 24, 120}

func test(F int) {
	query := func(pos int) byte {
		fmt.Fprintf(stdout, "%d\n", pos+1)
		stdout.Flush()
		ret := mustReadLine()[0]
		if ret == 'N' {
			os.Exit(0)
		}
		return ret - A
	}
	leftToQuery := make([]Pib, 119)
	for i := 0; i < len(leftToQuery); i++ {
		leftToQuery[i].id = i
		leftToQuery[i].arr = make([]byte, 5)
	}
	for prefixKnown := 0; prefixKnown < 3; prefixKnown++ {
		// debug(fmt.Sprintf("%v %v", prefixKnown, leftToQuery))
		counts := make([]int, 5)
		for i := 0; i < len(leftToQuery); i++ {
			lt := &leftToQuery[i]
			res := query(lt.id*5 + prefixKnown)
			counts[res]++
			lt.arr[prefixKnown] = res
		}
		letterIs := byte(0)
		expectedCount := 120
		for i := 0; i <= prefixKnown; i++ {
			expectedCount /= (5 - i)
		}
		for i, cnt := range counts {
			if cnt == expectedCount-1 {
				letterIs = byte(i)
				break
			} else if cnt != expectedCount {
				assert(cnt == 0)
			}
		}
		newLeftToQuery := make([]Pib, 0, len(leftToQuery))
		for _, lt := range leftToQuery {
			if lt.arr[prefixKnown] == letterIs {
				newLeftToQuery = append(newLeftToQuery, lt)
			}
		}
		assert(len(newLeftToQuery) == expectedCount-1)
		leftToQuery = newLeftToQuery
	}
	assert(len(leftToQuery) == 1)
	// find out last 2 letter with 1 query
	rsp := query(leftToQuery[0].id*5 + 3)
	leftToQuery[0].arr[4] = rsp // arr[3] is not rsp
	missing := leftToQuery[0].arr
	// last 1 letter
	letterMissing := make(map[byte]bool)
	for b := byte(0); b < 5; b++ {
		letterMissing[b] = true
	}
	for _, l := range missing[0:3] {
		delete(letterMissing, l)
	}
	delete(letterMissing, missing[4])
	var msLetter byte
	for l, _ := range letterMissing {
		msLetter = l
		break
	}
	missing[3] = msLetter
	for _, b := range missing {
		stdout.WriteByte(b + A)
	}
	stdout.WriteByte('\n')
	stdout.Flush()
	if mustReadLine() != "Y" {
		os.Exit(0)
	}
}

// boilerplate omitted...