Google Code Jam 2015 * Round 1A * Problem B. Haircut

B.go

/*
 * Google Code Jam
 * 2015 Round 1A
 * Problem B. Haircut
 * 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
	B  []*Barber
	WG sync.WaitGroup
)

type Barber struct {
	Id int   // case number
	B  int   // number of barbers
	N  int   // initial place in line
	M  []int // cutting rate array
	S  int   // solution
}

func NewBarber() *Barber {
	return &Barber{}
}

func (b *Barber) Solve() {
	// b.S = b.Clock()
	b.S = b.Binary()
	// fmt.Printf("Case #%d solved: %d\n", b.Id, b.S)
	WG.Done()
}

func (b *Barber) Served(t int64) int {
	if t < 0 {
		return 0
	}
	sc := 0
	for i := 0; i < b.B; i++ {
		sc += int(t/int64(b.M[i])) + 1
	}
	return sc
}

func (b *Barber) Binary() int {
	low := int64(-1)
	high := int64(10000 * b.N)
	for (low + 1) < high {
		mid := int64((low + high) / 2)
		if b.Served(mid) < b.N {
			low = mid
		} else {
			high = mid
		}
	}
	t := high
	before := b.Served(t - 1)
	be := b.N - before
	for i := 0; i < b.B; i++ {
		if t%int64(b.M[i]) == 0 {
			be = be - 1
			if be == 0 {
				return i
			}
		}
	}
	return b.B
}

/* direct simulation - slow for large N
func (b *Barber) Clock() int {
    c := 1
    for t := 0; ; t++ {
        for a := 0; a < b.B; a++ {
            if t % b.M[a] == 0 {
                if c == b.N {
                    return a
                }
                c = c + 1
            }
        }
    }
}
*/

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
	B = make([]*Barber, T)
	for i := 0; i < T; i++ {
		b := NewBarber()
		S.Scan()
		a := strings.Split(S.Text(), " ")
		b.B, err = strconv.Atoi(a[0])
		b.N, err = strconv.Atoi(a[1])
		S.Scan()
		a = strings.Split(S.Text(), " ")
		b.M = make([]int, b.B)
		for j := 0; j < b.B; j++ {
			b.M[j], err = strconv.Atoi(a[j])
		}
		if err != nil {
			fmt.Println(err)
		}
		b.Id = i + 1
		B[i] = b
		// fmt.Println(b)
		WG.Add(1)
		go B[i].Solve()
	}
}

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

func main() {
	begin := time.Now()
	fmt.Println("ok haircut!")
	Load()
	Cases()
	Split()
	WG.Wait()
	Finish()
	end := time.Now()
	fmt.Printf("total run time: %v.\n", end.Sub(begin))
}

// interesting binary search sol'n
// total run time: 60ms large input