B.go

/*
*  Google Code Jam 2013 Round 1A
*  Problem B. Manage Your Energy
 */
package main

import (
	"bufio"
	"container/list"
	"flag"
	"fmt"
	"os"
	"reflect"
	"sort"
	"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 []int64
)

func flags() {
	inpath = flag.String("i", "B-large-practice.in", "Input filepath for the problem.")
	outpath = flag.String("o", "B-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([]int64, 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, " ")
		E, _ := strconv.Atoi(s0[0])
		R, _ := strconv.Atoi(s0[1])
		N, _ := strconv.Atoi(s0[2])
		v := make([]int, N)
		l1, p1, e1 := reader.ReadLine()
		if e1 != nil {
			fmt.Println(e1, p1)
		}
		row2 := string(l1)
		s1 := strings.Split(row2, " ")
		for i := 0; i < len(s1); i++ {
			v[i], _ = strconv.Atoi(s1[i])
		}
		wg.Add(1)
		go max(i, E, R, N, v)
	}
}

func max(i int, E int, R int, N int, v []int) {
	if R > E {
		R = E
	}
	gain := list.New()
	amount := list.New()
	result := int64(0)

	amount.PushBack(int64(E))
	gain.PushBack(int64(v[0]))

	for i := 1; i < N; i++ {
		take := int64(R)
		for take > int64(0) {
			if amount.Len() == 0 {
				break
			}
			if reflect.ValueOf(amount.Front().Value).Int() > take {
				result = result + reflect.ValueOf(gain.Front().Value).Int()*take
				front := reflect.ValueOf(amount.Remove(amount.Front())).Int()
				front = front - take
				amount.PushFront(front)
				take = int64(0)
			} else {
				result = result + reflect.ValueOf(gain.Front().Value).Int()*reflect.ValueOf(amount.Front().Value).Int()
				take = take - reflect.ValueOf(amount.Front().Value).Int()
				amount.Remove(amount.Front())
				gain.Remove(gain.Front())
			}
		}
		add := int64(R)
		for gain.Len() != 0 && reflect.ValueOf(gain.Back().Value).Int() <= int64(v[i]) {
			add = add + reflect.ValueOf(amount.Back().Value).Int()
			amount.Remove(amount.Back())
			gain.Remove(gain.Back())
		}
		amount.PushBack(add)
		gain.PushBack(int64(v[i]))
	}
	for gain.Len() != 0 {
		result = result + reflect.ValueOf(amount.Front().Value).Int()*reflect.ValueOf(gain.Front().Value).Int()
		amount.Remove(amount.Front())
		gain.Remove(gain.Front())
	}
	results[i] = result
	wg.Done()
}

func span(a []int) []int {
	b := make([]int, len(a))
OUTER:
	for i := 0; i < len(a)-1; i++ {
		for j := i + 1; j < len(a); j++ {
			if a[j] > a[i] {
				b[i] = j - i
				continue OUTER
			}
		}
	}

	return b
}

func sortDesc(a []int) []int {
	b := make([]int, len(a))
	copy(b, a)
	sort.Sort(Reverse{sort.IntSlice(b)})
	return b
}

type Reverse struct {
	sort.Interface
}

func (r Reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

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

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

// thanks misof for another fine sol'n
// fails on large, int64 not Big enough?