← Home
For problem statement at 0-999/300-399/330-339/331/problemC3.txt this is a correct solution, but verifier at 0-999/300-399/330-339/331/verifierC3.go ends with All 200 tests passed. can you fix the verifier? ```go
package main

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

const (
	D     = 10
	MASKS = 1 << 9
	MAXK  = 17
	INF   = int64(4000000000000000000)
)

type Matrix [D * D]int64

var id Matrix
var B [MASKS]Matrix
var full [MAXK + 1][MASKS]Matrix
var digitMask [10]int

func mul(a, b *Matrix) Matrix {
	var c Matrix
	for i := 0; i < D*D; i++ {
		c[i] = INF
	}
	for i := 0; i < D; i++ {
		ii := i * D
		for j := 0; j < D; j++ {
			av := a[ii+j]
			if av == INF {
				continue
			}
			jj := j * D
			for k := 0; k < D; k++ {
				bv := b[jj+k]
				if bv == INF {
					continue
				}
				v := av + bv
				idx := ii + k
				if v < c[idx] {
					c[idx] = v
				}
			}
		}
	}
	return c
}

func build() {
	for i := 0; i < D*D; i++ {
		id[i] = INF
	}
	for i := 0; i < D; i++ {
		id[i*D+i] = 0
	}
	B[0] = id
	for d := 1; d <= 9; d++ {
		digitMask[d] = 1 << (d - 1)
	}
	for mask := 1; mask < MASKS; mask++ {
		var mat Matrix
		for i := 0; i < D*D; i++ {
			mat[i] = INF
		}
		for start := 0; start < 10; start++ {
			var dist [10]int64
			for i := 0; i < 10; i++ {
				dist[i] = INF
			}
			dist[start] = 0
			row := start * D
			for x := start; x >= 0; x-- {
				cur := dist[x]
				if cur == INF {
					continue
				}
				nxt := cur + 1
				if x > 0 && nxt < dist[0] {
					dist[0] = nxt
				}
				for d := 1; d <= 9; d++ {
					if mask&(1<<(d-1)) == 0 {
						continue
					}
					if d <= x {
						y := x - d
						if nxt < dist[y] {
							dist[y] = nxt
						}
					} else {
						v := x + 10 - d
						if nxt < mat[row+v] {
							mat[row+v] = nxt
						}
					}
				}
			}
		}
		B[mask] = mat
	}
	full[0][0] = id
	for mask := 1; mask < MASKS; mask++ {
		full[0][mask] = B[mask]
	}
	for k := 1; k <= MAXK; k++ {
		for mask := 0; mask < MASKS; mask++ {
			res := id
			for d := 0; d <= 9; d++ {
				m2 := mask | digitMask[d]
				res = mul(&full[k-1][m2], &res)
			}
			full[k][mask] = res
		}
	}
}

func prefixTransform(n uint64) Matrix {
	s := strconv.FormatUint(n, 10)
	res := id
	mask := 0
	for pos := 0; pos < len(s); pos++ {
		d := int(s[pos] - '0')
		rem := len(s) - pos - 1
		for a := 0; a < d; a++ {
			m2 := mask | digitMask[a]
			res = mul(&full[rem][m2], &res)
		}
		mask |= digitMask[d]
	}
	if mask != 0 {
		res = mul(&B[mask], &res)
	}
	return res
}

func main() {
	build()
	in := bufio.NewReader(os.Stdin)
	var n uint64
	fmt.Fscan(in, &n)
	q := n / 10
	r := int(n % 10)
	p := prefixTransform(q)
	row := r * D
	ans := INF
	if p[row] < ans {
		ans = p[row]
	}
	for j := 1; j < 10; j++ {
		v := p[row+j]
		if v != INF && v+1 < ans {
			ans = v + 1
		}
	}
	out := bufio.NewWriter(os.Stdout)
	fmt.Fprintln(out, ans)
	out.Flush()
}
```