A.go

/*
*  Google Code Jam 2013 Round 1A
*  Problem A. Bullseye
*/
package main

import (
    "bufio"
    "flag"
    "fmt"
    "math/big"
    "os"
    "strconv"
    "strings"
    "sync"
)

var (
    inpath *string
    outpath *string
    infile *os.File
    outfile *os.File
    reader *bufio.Reader
    writer *bufio.Writer
    tests int
    wg sync.WaitGroup
    results []*big.Int
)

func flags() {
    inpath = flag.String("i", "A-large-practice.in", "Input filepath for the problem.")
    outpath = flag.String("o", "A-large-practice.out", "Output filepath for the problem.")
}

func files() {
    var err error
    infile, err = os.Open(*inpath)
    if err != nil {
        fmt.Println(err)
    }
    outfile, err = os.Create(*outpath)
    if err != nil {
        fmt.Println(err)
    }
    reader = bufio.NewReader(infile)
    writer = bufio.NewWriter(outfile)
}

func cleanup() {
    var err error
    err = infile.Close()
    if err != nil {
        fmt.Println(err)
    }
    err = outfile.Close()
    if err != nil {
        fmt.Println(err)
    }
}

func parse() {
    l0, p0, e0 := reader.ReadLine()
    if e0 != nil {
        fmt.Println(e0, p0)
    }
    tests, _ = strconv.Atoi(string(l0))
    results = make([]*big.Int, tests)
    for i := 0; i < tests; i++ {
        l0, p0, e0 := reader.ReadLine()
        if e0 != nil {
            fmt.Println(e0, p0)
        }
        row := string(l0)
        s0 := strings.Split(row, " ")
        // r0, _ := strconv.Atoi(s0[0])
        // t0, _ := strconv.Atoi(s0[1])
        r1 := big.NewInt(0)
        t1 := big.NewInt(0)
        r1.SetString(s0[0], 10)
        t1.SetString(s0[1], 10)
        wg.Add(1)
        // go solve(i, r1, t1)
        go bins(i, r1, t1)
    }
}

func bins(i int, r0 *big.Int, t0 *big.Int) {
    // binary search
    // p(k) = (2r+2k-1)*k
    count := big.NewInt(0)
    zero := big.NewInt(0)
    one := big.NewInt(1)
    mone := big.NewInt(-1)
    two := big.NewInt(2)
    lo := big.NewInt(0)
    hi := big.NewInt(0)
    mid := big.NewInt(0)
    lo.Add(lo, one)
    hi.Add(hi, t0)
    for lo.Cmp(hi) <= 0 {
        mid.Add(lo, hi)
        mid.Div(mid, two)
        a := big.NewInt(0)
        a.Add(a, mid)
        a.Mul(a, two)
        a.Add(a, mone)
        b := big.NewInt(0)
        b.Add(b, r0)
        b.Mul(b, two)
        b.Add(b, a)
        b.Mul(b, mid)
        // fmt.Println(lo, mid, hi, a, b, r0, t0)
        if b.Cmp(t0) > 0 {
            hi.Add(mid, mone)
            continue
        }
        count.Add(zero, mid)
        lo.Add(mid, one)
    }
    results[i] = count
    wg.Done()
}

func paint(r *big.Int) *big.Int {
    a := big.NewInt(0)
    a.Mul(r, r)
    b := big.NewInt(-1)
    c := big.NewInt(0)
    c.Add(r, b)
    c.Mul(c, c)
    c.Mul(c, b)
    c.Add(a, c)
    // return (r * r) - ((r - 1) * (r - 1))
    return c
}

func solve(i int, r0 *big.Int, t0 *big.Int) {
    // infinite series
    count := big.NewInt(0)
    one := big.NewInt(1)
    two := big.NewInt(2)
    r1 := r0.Add(r0, one)
    t1 := paint(r1)
    for t1.Cmp(t0) <= 0 {
        count.Add(count, one)
        r1.Add(r1, two)
        t1.Add(t1, paint(r1))
    }
    results[i] = count
    if i % 100 == 0 {
        fmt.Println(i)
    }
    wg.Done()
}


func output() {
    for i := 0; i < len(results); i++ {
        s0 := fmt.Sprintf("Case #%d: %s\n", i+1, results[i].String())
        writer.WriteString(s0)
    }
    writer.Flush()
}

func main() {
    flags()
    files()
    defer cleanup()
    parse()
    wg.Wait()
    output()
}