← Home
For problem statement at 0-999/0-99/10-19/10/problemE.txt this is a correct solution, but verifier at 0-999/0-99/10-19/10/verifierE.go ends with All tests passed can you fix the verifier? package main

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

func greedyRep(x int64, a []int64) ([]int64, int64) {
	n := len(a)
	g := make([]int64, n)
	var cnt int64
	rem := x
	for i := 0; i < n; i++ {
		if rem >= a[i] {
			q := rem / a[i]
			g[i] = q
			cnt += q
			rem -= q * a[i]
		}
	}
	return g, cnt
}

func greedyCount(x int64, a []int64) int64 {
	var cnt int64
	rem := x
	for i := 0; i < len(a); i++ {
		if rem >= a[i] {
			q := rem / a[i]
			cnt += q
			rem -= q * a[i]
			if rem == 0 {
				break
			}
		}
	}
	return cnt
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)
	a := make([]int64, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &a[i])
	}

	var ans int64 = -1

	for i := 1; i < n; i++ {
		s := a[i-1] - 1
		g, totalCnt := greedyRep(s, a)

		suffixVal := make([]int64, n+1)
		suffixCnt := make([]int64, n+1)
		for k := n - 1; k >= 0; k-- {
			suffixVal[k] = suffixVal[k+1] + g[k]*a[k]
			suffixCnt[k] = suffixCnt[k+1] + g[k]
		}

		for j := i; j < n; j++ {
			w := s - suffixVal[j+1] + a[j]
			cnt := totalCnt - suffixCnt[j+1] + 1
			if cnt < greedyCount(w, a) {
				if ans == -1 || w < ans {
					ans = w
				}
			}
		}
	}

	fmt.Fprintln(out, ans)
}