Skip to content

Instantly share code, notes, and snippets.

@gorlum0
Created August 12, 2011 23:38
Show Gist options
  • Save gorlum0/1143249 to your computer and use it in GitHub Desktop.
Save gorlum0/1143249 to your computer and use it in GitHub Desktop.
spoj - 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))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment