naive solution to acm-icpc-2012-problems

fib.go

package main

//problem d

import (
	"fmt"
)

var lm []int64

func init() {
	lm = make([]int64, 100)
	lm[0] = 1
	lm[1] = 1
	for i := 2; i < 100; i++ {
		lm[i] = lm[i-1] + lm[i-2]
	}
}

func f(n int) string {
	switch n {
	case 0:
		return "0"
	case 1:
		return "1"
	}
	return f(n-1) + f(n-2)
}

func getfib(n int) int {
	m := 0
	for ; m < 100; m++ {
		if lm[m] >= int64(n) {
			break
		}
	}
	return m
}

func calcmid(pattern string) (int64, int64) {
	l0 := len(pattern)
	m := getfib(l0)
	b := []byte(f(m))
	b2 := []byte(f(m + 1))
	b = append(b[len(b)-l0+1:], b[:l0-1]...)
	b2 = append(b2[len(b2)-l0+1:], b2[:l0-1]...)
	l1 := len(b) - l0
	l2 := len(b2) - l0
	count, count2 := int64(0), int64(0)
	for i := 0; i <= l1; i++ {
		if string(b[i:i+l0]) == pattern {
			count++
			// fmt.Println("[1]: ", i, string(b[i:i+l0]))
		}
	}
	for i := 0; i <= l2; i++ {
		if string(b2[i:i+l0]) == pattern {
			count2++
			// fmt.Println("[2]: ", i, string(b2[i:i+l0]))
		}
	}
	// fmt.Println(string(b), string(b2))
	return count, count2
}

func calcend(pattern string) (int64, int64, int) {
	l0 := len(pattern)
	lim := getfib(l0)
	fib1 := f(lim)
	fib2 := f(lim + 1)
	b := []byte(fib1)
	b2 := []byte(fib2)
	l1 := len(b) - l0
	l2 := len(b2) - l0
	count, count2 := int64(0), int64(0)
	for i := 0; i <= l1; i++ {
		if string(b[i:i+l0]) == pattern {
			count++
		}
	}
	for i := 0; i <= l2; i++ {
		if string(b2[i:i+l0]) == pattern {
			count2++
		}
	}
	return count2, count, lim
}

func brute(num int, pattern string) int64 {
	if num > 20 { // suitable when n is small enough
		return -1
	}
	b := []byte(f(num))
	count := int64(0)
	l0 := len(pattern)
	l := len(b) - len(pattern)
	for i := 0; i <= l; i++ {
		if string(b[i:i+l0]) == pattern {
			count++
		}
	}
	return count
}

func Calc(num int, pattern string) int64 {
	if num > 100 || num < 0 {
		return -1
	}
	a1, a2, d := calcend(pattern)
	j := num - d
	switch {
	case j < 0:
		return 0
	case j == 0:
		return a2
	case j == 1:
		return a1
	}
	c1, c2 := calcmid(pattern)
	k1, k2 := int64(0), int64(0)
	for i := 1; i < j; i++ {
		if d%2 == i%2 {
			k1 += lm[i-1]
		} else {
			k2 += lm[i-1]
		}
	}
	return (lm[j-1]*a1 + lm[j-2]*a2 + k1*c1 + k2*c2)
}

func main() {
	for i := 10; i < 97; i++ {
		fmt.Printf("%d: %v\n", i, Calc(i, "10110101101101"))
	}
}

prism.go

package main

// problem b
// sample.txt
// 1
// 4.0 -0.25
// 0.0 12.0 25
// 1
// 4.0 -0.25
// 0.0 12.0 300
// 0
// 1.7841241161782
// 5.0 10.0 20
// 0
// 1.0
// 0.0 10.0 10

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

type Prism struct {
	vector    []float64
	low, high float64
}

func NewPrism(a []float64, x0, x1 float64) *Prism {
	p := new(Prism)
	p.vector = initVector(a)
	p.low = x0
	p.high = x1
	return p
}

func (id *Prism) Volume() float64 {
	return volume(id.vector, id.low, id.high)
}

func (id *Prism) Distances(v float64) ([]float64, error) {
	v0 := id.Volume()
	if v > v0 {
		return nil, fmt.Errorf("insufficient volume")
	}
	n := int(v0 / v)
	if n > 8 {
		n = 8
	}
	ds := make([]float64, n)
	low := id.low
	for i := 0; i < n; i++ {
		k := float64(0.0001)
		for volume(id.vector, low, low+k) < v {
			k += 0.0001
		}
		low += k
		ds[i] = low - id.low
	}
	return ds, nil
}

func initVector(a []float64) []float64 {
	m := len(a) // 0 ~ n
	matrix := make([][]float64, m)
	for i := 0; i < m; i++ {
		matrix[i] = make([]float64, m)
		for j := 0; j < m; j++ {
			matrix[i][j] = a[i] * a[j]
		}
	}
	vec := make([]float64, 2*m-1)
	for i := 0; i < 2*m-1; i++ {
		vec[i] = 0
		k := i - m + 1
		if k < 0 {
			k = 0
		}
		j := i - k
		h := j
		for k <= h {
			vec[i] += matrix[k][j]
			k++
			j--
		}
	}
	return vec
}

func volume(vec []float64, x0, x1 float64) float64 {
	m := len(vec) // 0 ~ 2n+1
	r := float64(0)
	var c float64
	for i := 0; i < m; i++ {
		c = float64(i + 1)
		r += vec[i] * (math.Pow(x1, c) - math.Pow(x0, c)) / c
	}
	return r * math.Pi
}

func main() {
	file, err := os.Open("sample.txt")
	if err != nil {
		fmt.Println(err)
		return
	}
	defer file.Close()
	reader := bufio.NewReader(file)
	var line string
	var p *Prism
	var a []float64
	var b []string
	var x0, x1, inc float64
	for {
		_, err = reader.ReadString('\n')
		if err != nil {
			break
		}
		line, _ = reader.ReadString('\n')
		b = strings.Fields(line)
		a = make([]float64, len(b))
		for i := 0; i < len(b); i++ {
			a[i], _ = strconv.ParseFloat(b[i], 64)
		}
		line, _ = reader.ReadString('\n')
		b = strings.Fields(line)
		x0, _ = strconv.ParseFloat(b[0], 64)
		x1, _ = strconv.ParseFloat(b[1], 64)
		inc, _ = strconv.ParseFloat(b[2], 64)
		p = NewPrism(a, x0, x1)
		fmt.Printf("%.2f\n", p.Volume())
		ds, err := p.Distances(inc)
		if err != nil {
			fmt.Println(err)
		} else {
			fmt.Printf("%.2f\n", ds)
		}
	}
	return
}