bytelandian-gold-coins

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.

Explanation
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.

SAMPLE INPUT
12
2SAMPLE OUTPUT
13
2

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

Starter code:

Solutions:
import sys
hashmap = {}
def count(n):
	if n <= 5:
		return n
	elif n in list(hashmap.keys()):
		return hashmap[n]
	else:
		k = count(n / 2) + count(n / 3) + count(n / 4)
		if k > n:
			hashmap[n]=k
			return k
		else:
			hashmap[n]=n
			return n
for line in sys.stdin:
		result = count(int(line))
		print(result)


n=10
a=dict()
def fct(t):
	if t in a:
		return a[t]

	if t<12:
		return t
	
	s=fct(t/2)+fct(t/3)+fct(t/4)
	a[t]=s
	return a[t]


for i in range(n):
	try:
		t=eval(input())
		
	except:
		break
	else:
		print(fct(t))


from collections import defaultdict
map = defaultdict(int)
def func(n):
	if n == 0:
		return 0
	elif map[n] == 0:
		map[n] = max(n,func(n/2) + func(n/3) +func(n/4))
	return map[n]

while True:
	try:
		n = eval(input())
		print(func(n))
	except:
		break
	


def result(n):
	return int(n/2)+int(n/3)+int(n/4)
list1=[]
def sum_coins(n):
	if n<len(list1) and list1[n]!=-1:
		return list1[n]
	else:
		if (n!=0 and result(n)>=n):
			s=sum_coins(int(n/2))+sum_coins(int(n/3))+sum_coins(int(n/4))
		else:
			s=n
		if n<len(list1):
			list1[n]=s
		return s
while 1:
	try:
		n=int(eval(input()))
		if n==-1:
			break
	except EOFError:
		break
	list1=[-1 for i in range(1000000)]
	for i in range(10000):
		list1[i]=sum_coins(i)
	print((sum_coins(n)))


store={0:0}
import math
def coins(n):
	if n in store:
		a=store[n]
	else:
		if n > 0:
			a = max(n, coins(n/2)+coins(n/3)+coins(n/4))
			store[n]=a
		else:
			a=n
 
	return int(a)
    	
	    
while True:
	try:
		print(coins(int(input())))
	except:
	    break        


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
store={0:0}
import math
def coins(n):
	if n in store:
		a=store[n]
	else:
		if n > 0:
			a = max(n, coins(n/2)+coins(n/3)+coins(n/4))
			store[n]=a
		else:
			a=n

	return int(a)
    	
	    
while True:
	try:
		print(coins(int(input())))
	except:
	    break        


    



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


dict = {0:0}

def bytelandian(n):
	if n in dict: return dict[n]
	dict[n] = max(n,bytelandian(n/2)+bytelandian(n/3)+bytelandian(n/4))
	return dict[n]
	
for i in range(10):
	try: print((bytelandian(eval(input()))))
	except:	break


#Bytelandian Gold Coins

sols = {0:0}
 
def solve(x):
	if x in sols:
		return sols[x]
	else:
		sols[x] = max(x , solve(x/2) + solve(x/3) + solve(x/4))
		return sols[x]

while True:
	try:
		n=eval(input())
		print((solve(n)))
	except:
		break


exchange = {0:0}

def convert(x) :
	if x in exchange:
		return exchange[x]
	else:
		exchange[x] = max(x, convert(x/4)+convert(x/3)+convert(x/2))
		return exchange[x]

while True:
	try:
		num = eval(input())
		print(convert(num))	
	except:
		break


coin={0:0,}
def change(n) :
	try :
		ans=coin[n]
	except :
		
		ans=0
		
	if ans :
		
		return int(ans)
	
	
	
	sums=int(n/2 )+ int(n/3) +int(n/4)
	if sums>n :
		ans= change(n/2) + change(n/3) + change(n/4)
		coin[n]=ans
		return int(ans)
	ans=n
	coin[n]=ans
	
	return int(ans)
t=10
while t :
	try :
		n=int(input())
		
	except :
		break
	p=change(n)
	#print(len(coin))
	print(p)
	t=t-1



import sys

cache = list(range(12))
for i in range(12, 1000001):
	cache.append(cache[i/2] + cache[i/3] + cache[i/4])

def solve(n):
	if n <= 1000000:
		return cache[n]
	r1 = n/2
	r2 = n/3
	r3 = n/4
	if r1+r2+r3 <= n:
		return n
	else:
		return solve(r1) + solve(r2) + solve(r3)

ll = list(map(int, sys.stdin.readlines()))
for n in ll:
	print(solve(n))


Mem={}
def Find(N):
	if N<=1:
		return 0
	if N in Mem:
		return Mem[N]
	a1,a2,a3=N//2,N//3,N//4
	max1=Find(a1)
	max2=Find(a2)
	max3=Find(a3)
	if N<=max1+max2+max3:
		Mem.update({N:max1+max2+max3})
		return Mem[N]
	else:
		Mem.update({N:N})
		return N

def solve():
	try:
		while True:
			N=int(input())
			ans=Find(N)
			print(ans)
	except:
		return
solve()


import sys
arrmax=[0]*1000000
def getmax(coin):
	coin=int(coin)
	if coin < 1000000 and arrmax[coin]!=0:
		return arrmax[coin]
	if coin >= 1000000000 or coin < 10:
		return coin
	else:
		maximum=max(coin,(getmax(coin//2)+getmax(coin//3)+getmax(coin//4)))
		if coin < 1000000:
			arrmax[coin]=maximum
		return maximum
	
for inpt in sys.stdin:
	coin=int(inpt)
	print((getmax(coin)))


from sys import stdin as cin

dic = {0:0,1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9}

def preprocess(n):
	if(n in dic):
		return dic[n]    
	return max(n, preprocess(n/2)+ preprocess(n/3) + preprocess(n/4) )

for x in range(10,100000):
	dic[x] = preprocess(x)
while(1):
	line = cin.readline()
	if not line or line == "\n":
		break
	n = int(line.strip())       
	print((preprocess(n)))
	


import sys

d = dict()

def solve(n):
	if(n <= 1):
		return n
	if n in d:
		return d[n]
	
	d[n] = max(solve(n // 2) + solve(n // 3) + solve(n // 4),n)
	return d[n]

for line in sys.stdin:
	print(solve(int(line)))



import sys

d = dict()

def solve(n):
	if(n <= 1):
		return n
	if n in d:
		return d[n]
	d[n] = max(solve(n // 2) + solve(n // 3) + solve(n // 4),n)
	return d[n]

for line in sys.stdin:
	print((solve(int(line))))


import sys

d = dict()

def solve(n):
	if(n <= 1):
		return n
	if n in d:
		return d[n]
	d[n] = max(solve(n // 2) + solve(n // 3) + solve(n // 4),n)
	return d[n]

for line in sys.stdin:
	print((solve(int(line))))


z=[0,1,2,3,4,5,6,7,8,9,10,11,13]
for x in range(13,1000000):
	z.append(z[x/2]+z[x/3]+z[x/4])
def f( x):
	x=int(x)
	if x<1000000:
		return z[x]
	else :
		return f(x/2)+f(x/3)+f(x/4)
import sys
for n in sys.stdin:
	
	print(f(n))
		
		
	


import sys

vals = {}
vals[0]=0
vals[1] = 1


def dist(n):
	global vals
	
	f = int(n/2)
	s = int(n/3)
	t = int(n/4)
	
	if f not in list(vals.keys()):
		vals[f] = max(f,dist(f))
	
	if s not in list(vals.keys()):
		vals[s] = max(s,dist(s))
		
	if t not in list(vals.keys()):
		vals[t] = max(f,dist(t))
	
	return vals[f] + vals[s] + vals[t]


def solve(n):
	global vals
	if n not in list(vals.keys()):
		vals[n] = max(n,dist(n))
	return vals[n]

for line in sys.stdin:
	print(solve(int(line)))


f = dict()
f[0] = 0
def val(N):
	if N in f:
		return f[N]
	else:
		f[N] = max(N, val(N/2) + val(N/3) + val(N/4))
		return f[N]
while True:
	try:
		N = int(input())
		print(val(N))
	except(EOFError):
		break


conv = {0:0}
 
def exch(num):
	if num in conv:
		return conv[num]
	else:
		conv[num] = max(num, exch(num/4)+exch(num/3)+exch(num/2))
		return conv[num]
while True:
	try:
		print(exch(int(input())))
	except:
		break


import sys

coin_val_map = {}
def recurse(inp):
	if inp in coin_val_map:
		 return coin_val_map[inp]
	
	if (inp/2 + inp/3 + inp/4 ) < inp:
		 return inp
		 
	coin_val = recurse(inp/2) + recurse(inp/3) + recurse(inp/4)
	coin_val_map[inp] = coin_val
	return coin_val


if __name__ =='__main__':
	 data= ( sys.stdin.readlines() )
	 for inp in data:
	 	max_coin_val = recurse(int(inp))
	 	print(max_coin_val)




def max(n):
	global ref
	if( n==0 ):
		return 0
	
	try:
	        p=ref[n]
	
	except KeyError:

	        if( n > ( max(n/2) + max(n/3) + max(n/4) ) ):
		         ref[n]= n;
	
                else:
		         ref[n]= ( max(n/2) + max(n/3) + max(n/4) );
	
	
	return ref[n];



ref=dict()
while 1:
	try:
		  n=eval(input())
	          print(max(n))
        except:
		  break 
	


from functools import wraps
for _ in range(10):
	try:
		n=int(input())
	except Exception:
		break
	def memo(f):
		cache={}
		@wraps(f)
		def wrap(*args):
			if args not in cache:
				cache[args]=f(*args)
			return cache[args]
		return wrap
	@memo
	def sol(n):
		if n<2:
			return n
		else:
			return max(n,sol(n//2)+sol(n//3)+sol(n//4))
	print(sol(n))



import sys

d = dict()

def solve(n):
	if(n <= 1):
		return n
	if n in d:
		return d[n]
	
	d[n] = max(solve(n // 2) + solve(n // 3) + solve(n // 4),n)
	return d[n]

for line in sys.stdin:
	print(solve(int(line)))



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def result(n):
	return int(n/2)+int(n/3)+int(n/4)
def summ(n):
	global A
	if n<len(A) and A[n]!=-1:
		return A[n]
	else:
		if n!=0 and result(n)>=n:
			s=summ(int(n/2))+summ(int(n/3))+summ(int(n/4))
		else:
			s=n
		if n<len(A):
			A[n]=s
		return s
while 1:
	try:
		n=int(input())
		if n==-1:
			break
	except EOFError:
		break
	A=[-1 for i in range(1000000)]
	for i in range(10000):
		A[i]=summ(i)
	print(summ(n))



dict = {0:0,1:1,2:2}

def bytelandian(n):
	if n in dict: return dict[n]
	dict[n] = max(n,bytelandian(n/2)+bytelandian(n/3)+bytelandian(n/4))
	return dict[n]
	
for i in range(10):
	try: print((bytelandian(eval(input()))))
	except:	break