P40_COINS.py

# In Byteland they have a very strange monetary system.
#
# Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into
# three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).
#
# You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy
# Bytelandian coins.
#
# You have one gold coin. What is the maximum amount of American dollars you can get for it?
#
# Input
# The input will contain several test cases (not more than 10). Each testcase is a single line with a number
# n, 0 <= n <= 1 000 000 000. It is the number written on your coin.
#
# Output
# For each test case output a single line, containing the maximum amount of American dollars you can make.
#
# Example
# Input:
# 12
# 2
#
# Output:
# 13
# 2
# You can change 12 into 6, 4 and 3, and then change these into $6+$4+$3 = $13. If you try changing the
# coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than $1 out of them.
# It is better just to change the 2 coin directly into $2.

import sys

list={}
def chk(n):
    if n in list.keys():
        return list[n]
    if n<=2:
        ans = n
    else:
        ans = chk(n//2) + chk(n//3) + chk(n//4)
    if ans<n : ans = n
    list[n] = ans
    return ans

for case in sys.stdin:
    n = int(case)
    print(chk(n))