Google Code Jam 2015 * Qualification Round * Problem B. Infinite House of Pancakes

B.go

/*
 *   Google Code Jam
 *   2015 Qualification Round
 *   Problem B. Infinite House of Pancakes
 *   AQ <[email protected]>
 */
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
	"sync"
	"time"
)

const (
	IN  = "B-large-practice.in"
	OUT = "B-large-practice.out"
)

var (
	I   *os.File
	O   *os.File
	S   *bufio.Scanner
	W   *bufio.Writer
	T   int
	Pan []*Pancake
	WG  sync.WaitGroup
)

type Pancake struct {
	D int
	P []int
	M int
}

func NewPancake() *Pancake {
	return &Pancake{}
}

func (p *Pancake) Solve() {
	p.M = 1010
	max := p.Max()
	p.M = max
	for i := 1; i < max; i++ {
		tm := 0
		for j := 0; j < len(p.P); j++ {
			tm += (p.P[j] - 1) / i
		}
		if (tm + i) < p.M {
			p.M = tm + i
		}
	}
	WG.Done()
}

func (p *Pancake) Max() int {
	r := p.P[0]
	l := len(p.P)
	if l > 1 {
		for i := 1; i < l; i++ {
			if p.P[i] > r {
				r = p.P[i]
			}
		}
	}
	return r
}

func Load() {
	var err error
	I, err = os.Open(IN)
	if err != nil {
		fmt.Println(err)
	}
	S = bufio.NewScanner(I)
	O, err = os.Create(OUT)
	if err != nil {
		fmt.Println(err)
	}
	W = bufio.NewWriter(O)
}

func Cases() {
	var err error
	S.Scan()
	T, err = strconv.Atoi(S.Text())
	if err != nil {
		fmt.Println(err)
	}
	fmt.Printf("%d test cases.\n", T)
}

func Split() {
	var err error
	Pan = make([]*Pancake, T)
	for i := 0; i < T; i++ {
		p := NewPancake()
		S.Scan()
		p.D, err = strconv.Atoi(S.Text())
		if err != nil {
			fmt.Println(err)
		}
		S.Scan()
		a := strings.Split(S.Text(), " ")
		p.P = make([]int, len(a))
		for j := 0; j < len(a); j++ {
			p.P[j], err = strconv.Atoi(a[j])
			if err != nil {
				fmt.Println(err)
			}
		}
		Pan[i] = p
		WG.Add(1)
		go Pan[i].Solve()
	}
}

func Finish() {
	defer I.Close()
	defer O.Close()
	for i := 0; i < T; i++ {
		s0 := fmt.Sprintf("Case #%d: %d\n", i+1, Pan[i].M)
		W.WriteString(s0)
	}
	W.Flush()
}

func main() {
	// at every minute, decide if a special is optimal
	// splits must be binary
	begin := time.Now()
	Load()
	Cases()
	Split()
	WG.Wait()
	Finish()
	end := time.Now()
	fmt.Printf("total running time: %v.\n", end.Sub(begin))
}
// ingenious bottom up simulation from analysis
// total run time for large data set: 160ms