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 Format ------ 

The input will contain several test cases (not more than 10). \
Each testcase is a single line with a number n, it is the number written on your coin.

------ Output Format ------ 

For each test case output a single line, containing the maximum amount of American dollars you can make.

------ Constraints ------ 

$0 ≤ n ≤ 10^{9}$

----- Sample Input 1 ------ 
12
2

----- Sample Output 1 ------ 
13
2

----- explanation 1 ------ 
Test case 1: You can change 12 into 6, 4 and 3, and then change these into $6+4+3 = 13$. \
Test case 2: 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$.

Difficulty: EASY
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
found = {}

def byteLander(n):
	if n < 12:
		return n
	elif n in found:
		return found[n]
	else:
		sum = byteLander(n // 2) + byteLander(n // 3) + byteLander(n // 4)
		found[n] = sum
		return sum
while True:
	try:
		n = int(input())
		print(byteLander(n))
	except:
		break
found = {}

def byteLander(n):
	if n < 12:
		return n
	elif n in found:
		return found[n]
	else:
		sum = byteLander(n // 2) + byteLander(n // 3) + byteLander(n // 4)
		found[n] = sum
		return sum
while True:
	try:
		n = int(input())
		print(byteLander(n))
	except:
		break


found = {}

def byteLander(m):
	if m < 12:
		return m
	elif m in found:
		return found[m]
	else:
		s = byteLander(m // 2) + byteLander(m // 3) + byteLander(m // 4)
		found[m] = s
		return s
while True:
	try:
		m = int(input())
		print(byteLander(m))
	except:
		break


fp = {}

def blp(np):
	if np < 12:
		return np
	elif np in fp:
		return fp[np]
	else:
		sp = blp(np // 2) + blp(np // 3) + blp(np // 4)
		fp[np] = sp
		return sp
while True:
	try:
		np = int(input())
		print(blp(np))
	except:
		break


dp = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
while True:
	try:
		n = int(input())

		def solve(n, dp):
			if n in dp:
				return dp[n]
			else:
				out = max(n, solve(n // 2, dp) + solve(n // 3, dp) + solve(n // 4, dp))
				dp[n] = out
				return out
		solve(n, dp)
		print(dp[n])
	except:
		break


def ans(x):
	if x < 10:
		return x
	if x in a:
		return a[x]
	a[x] = max(x, ans(x // 2) + ans(x // 3) + ans(x // 4))
	return a[x]
a = {}
while True:
	try:
		x = int(input())
		print(ans(x))
	except:
		break


dict = {}

def find_max(n):
	if n in dict.keys():
		max_val = dict[n]
		return max_val
	if n >= 0 and n < 12:
		max_val = n
		dict[n] = n
		return max_val
	elif n >= 12:
		val = 0
		val += find_max(n // 2)
		val += find_max(n // 3)
		val += find_max(n // 4)
		if val > n:
			max_val = val
			dict[n] = val
		elif val <= n:
			max_val = n
			dict[n] = n
		return max_val
while True:
	try:
		n = int(input())
		max_val = find_max(n)
		print(max_val)
	except:
		break


found = {}

def byteLander(nkk):
	if nkk < 12:
		return nkk
	elif nkk in found:
		return found[nkk]
	else:
		smm = byteLander(nkk // 2) + byteLander(nkk // 3) + byteLander(nkk // 4)
		found[nkk] = smm
		return smm
while True:
	try:
		nkk = int(input())
		print(byteLander(nkk))
	except:
		break


cache = {}

def max_dollars(n):
	if n in cache:
		return cache[n]
	if n == 0:
		return 0
	dollars = max(max_dollars(n // 2) + max_dollars(n // 3) + max_dollars(n // 4), n)
	cache[n] = dollars
	return dollars
while True:
	try:
		n = int(input())
		print(max_dollars(n))
	except:
		break


memo = {0: 0}
while True:
	try:
		n = int(input())

		def recursion(n):
			if n in memo:
				return memo[n]
			else:
				ans = max(n, recursion(n // 2) + recursion(n // 3) + recursion(n // 4))
				memo[n] = ans
				return ans
		result = recursion(n)
		print(result)
	except:
		break


def Res(N):
	if N < 10:
		return N
	if N in a:
		return a[N]
	a[N] = max(N, Res(N // 2) + Res(N // 3) + Res(N // 4))
	return a[N]
a = {}
while True:
	try:
		print(Res(int(input())))
	except:
		break


def fun(n):
	if n < 10:
		return n
	if n in a:
		return a[n]
	else:
		a[n] = max(n, fun(n // 2) + fun(n // 3) + fun(n // 4))
		return a[n]
a = {}
while True:
	try:
		n = int(input())
		print(fun(n))
	except:
		break


fdp = {}

def byteLander(n):
	if n < 12:
		return n
	elif n in fdp:
		return fdp[n]
	else:
		smp = byteLander(n // 2) + byteLander(n // 3) + byteLander(n // 4)
		fdp[n] = smp
		return smp
while True:
	try:
		n = int(input())
		print(byteLander(n))
	except:
		break


import math

def coins(coin, memo={}):
	if coin == 0:
		return 0
	if coin in memo.keys():
		return memo[coin]
	val = math.floor(coin / 4) + math.floor(coin / 3) + math.floor(coin / 2)
	if coin > val:
		memo[coin] = coin
		return coin
	else:
		c4 = coins(math.floor(coin / 4))
		c3 = coins(math.floor(coin / 3))
		c2 = coins(math.floor(coin / 2))
		memo[coin] = c4 + c3 + c2
		return c4 + c3 + c2
while True:
	try:
		x = int(input())
		print(coins(x))
	except:
		break


def best_exchange(n, memo=None):
	if memo is None:
		memo = {}
	if n in memo:
		return memo[n]
	if n == 0:
		memo[n] = 0
		return memo[n]
	memo[n] = max(n, best_exchange(n // 2, memo) + best_exchange(n // 3, memo) + best_exchange(n // 4, memo))
	return memo[n]
while True:
	try:
		n = int(input())
		print(best_exchange(n))
	except EOFError:
		break


f = {}

def ByteLander(n):
	if n < 12:
		return n
	elif n in f:
		return f[n]
	else:
		sum1 = ByteLander(n // 2) + ByteLander(n // 3) + ByteLander(n // 4)
		f[n] = sum1
		return sum1
while True:
	try:
		n = int(input())
		print(ByteLander(n))
	except:
		break


def max_dollars(coin, memo):
	if coin in memo:
		return memo[coin]
	part1 = memo.get(coin // 2, max_dollars(coin // 2, memo))
	part2 = memo.get(coin // 3, max_dollars(coin // 3, memo))
	part3 = memo.get(coin // 4, max_dollars(coin // 4, memo))
	max_d = max(coin, part1 + part2 + part3)
	memo[coin] = max_d
	return max_d
while True:
	try:
		n = int(input())
	except:
		break
	memo = {0: 0, 1: 1}
	max_d = max_dollars(n, memo)
	print(max_d)


dp = {}

def f(n):
	if n < 12:
		return n
	if n in dp:
		return dp[n]
	sum = f(n // 2) + f(n // 3) + f(n // 4)
	dp[n] = sum
	return sum
while True:
	try:
		num = int(input())
		print(f(num))
	except:
		break