GCJ/2017/Qualification/B/main.go

package main

import (
	"fmt"
)

func main() {
	// The least tidy number starts with n is nnnn..., array of ones is a faster way to work it out.
	ones := make([]int, 20)
	ones[1] = 1
	for i := 2; i < 20; i++ {
		ones[i] = ones[i-1]*10 + 1
	}
	// 1, 10, 100, 1000, ...
	base := make([]int, 20)
	base[1] = 1
	for i := 2; i < 20; i++ {
		base[i] = base[i-1] * 10
	}
	var T, N int
	fmt.Scan(&T)
	for cid := 1; cid <= T; cid++ {
		fmt.Scan(&N)
		cnt := 0
		for n := N; n != 0; n /= 10 {
			cnt++ // Count the digits of N
		}
		fmt.Printf("Case #%d: %d\n", cid, tidy(ones, base, N, cnt))
	}
}

func tidy(ones, base []int, num, cnt int) int {
	if cnt == 1 { // Has only one digit, returns itself.
		return num
	}
	highest := num / base[cnt]
	least := highest * ones[cnt]
	if num == least { // Is valid.
		return num
	} else if num < least { // Smaller than the least num starts with n, returns (n-1)9999...
		return (highest-1)*base[cnt] + 9*ones[cnt-1]
	} else { // Keep the highest digit, tidy up the remaining part.
		return highest*base[cnt] + tidy(ones, base, num-highest*base[cnt], cnt-1)
	}
}