Skip to content

Instantly share code, notes, and snippets.

@gorlum0
Created August 12, 2011 23:27
Show Gist options
  • Save gorlum0/1143218 to your computer and use it in GitHub Desktop.
Save gorlum0/1143218 to your computer and use it in GitHub Desktop.
spoj - Coins.py
#!/usr/bin/env python
"""(c) gorlum0 [at] gmail.com"""
from sys import stdin
def exchange(n, _cache = {0: 0}):
if not _cache.has_key(n):
v = exchange(n//2) + exchange(n//3) + exchange(n//4)
_cache[n] = max(n, v)
return _cache[n]
def main():
for n in map(int, stdin):
print exchange(n)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment