spoj - Coins.go

Coins.go

/*(c) gorlum0 [at] gmail.com*/
package main

import (
    "fmt"
)

func max(x, y int64) int64 {
    if x > y {
        return x
    }
    return y
}

var _cache = map[int64] int64 {}
func exchange(n int64) int64 {
	if _, present := _cache[n]; !present {
		v := exchange(n/2) + exchange(n/3) + exchange(n/4)
		_cache[n] = max(n, v)
	}
	return _cache[n]
}

func main() {
	_cache[0] = 0

	for ;; {
		n := int64(-1)
		fmt.Scanf("%d", &n)
		if n == -1 { break }

		fmt.Println(exchange(n))
	}
}