Bytelandian gold coins

                            Solution in C :

#include<stdio.h>
long long int dp[10000000];
void initialize()
{
    int i;
    for(i=1;i<=10000000;i++)
    dp[i]=0;
}
long long int coins(long long int n)
{
    long long int ans;
    if(n<12)
    return n;
    if(n<10000000 && dp[n]!=0)
    {
        return dp[n];
    }
    ans=coins(n/2)+coins(n/3)+coins(n/4);
    if(n<10000000)
    {
        ans=coins(n/2)+coins(n/3)+coins(n/4);
        dp[n]=ans;
    }
    return ans;
}
int main()
{
    long long int n,res;
    initialize();
    while(scanf("%lld",&n)!=EOF)
    {
        res=coins(n);
        printf("%lld\n",res);
    }
}
                        

                        Solution in C++ :

#include <bits/stdc++.h>
#define inf INT_MAX
#define mod 1e9+7
#define yes         cout<<"YES"<<endl
#define no          cout<<"NO"<<endl
typedef long long ll;
#define pb          push_back
#define lcm(a,b)    (a*b)/(__gcd(a,b))
#define fw(i,a,b)    for(int i=a;i<b;i++)
#define vl vector<ll>
#define vvl vector<vl>
using namespace std;
 
ll power(ll a , ll b,ll modi)
{
    a%=modi;
    ll res = 1 ;
    while(b)
    {
        if(b%2) {
            res = (res * a) % modi ;
        }
        b/=2 ;
        a = (a*a) % modi ;
    }
    return res ;
}
 

map<ll , ll > dp;

ll Dp(ll n)
{
    if(dp.find(n)==dp.end())dp[n] = max(Dp(n/2) + Dp(n/3) + Dp(n/4), n);
return dp[n];
}



ll fun(ll n)
{
    if(n<12)return dp[n]=n;
    
    if(dp[n]) return dp[n];
    
    return dp[n]=max(n,fun(n/2)+fun(n/3)+fun(n/4));
}

int main()
{
    ll n;
    while(cin>>n)
    {
        cout<<fun(n)<<endl;
    }
    return 0;
}
                    

                        Solution in Java :

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 
import java.lang.*; 


public class Main{

    public static PrintWriter out;
    public static FastReader in;
    public static int mod = 1000003;
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while(st==null || !st.hasMoreTokens()){
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        String nextLine(){
            String str="";
            try {
                str=br.readLine().trim();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) {
        try {
            in = new FastReader();
            out = new PrintWriter(new BufferedOutputStream(System.out));
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                long n = sc.nextLong();
                long ans = solve(n);


                out.println(ans);
            }

            out.flush();
            out.close();
        } catch (Exception e) {
            System.out.println("Exception");
            return;
        }
    }

    public static long solve(long n ){
        long res = n/2+n/3+n/4;
        if(n<res){
            return solve(n/2)+solve(n/3)+solve(n/4);
        }else{
            return n;
        }
    }



/*
// Points to rememeber:
    - if a question is asked where you are given two condition one where you have to include
      and one in which you have to exclude them use dp memoization (maximum in non-adjecent array)
    - In a problem which has distance given by two point use graph and if we need to find the 
      element in between sort in the pair array for values instead of keys
    - Use pascal's triangle to solve nCr problem.
    - b^-1%m = b^m-2 (Fermat's little theorem). (nCr problem)
    - if you have a^10 (use fast exponenetiation or fast factorial computation)
    - xor adds if one of the two number are power of 2 and the other is less than it and 
      it subtracts if it is more. (8^7 == 15 but 8^9 == 1).
    - even number with xor 1 adds and odd subtracts.
//String:
    - total possible substring -> n * (n+1)/2, total permutations -> n!
    - You can use Manacher’s algorithm to find and longest palindromic substirng
      and also modify it to find count pallindromic substrings.
    - you can also use dp (diagonal  method tabulation) to count pallindromic substrings. 
*/



    static int highestPowerOf2(int x)
    {
       
        // check for the set bits
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
         
        // Then we remove all but the top bit by xor'ing the
        // string of 1's with that string of 1's shifted one to
        // the left, and we end up with just the one top bit
        // followed by 0's.
        return x ^ (x >> 1); 
     
    }

    static boolean isPrime(int a){
        if (a == 1) return false;
        if (a == 2 || a == 3) return true;
        if (a%2==0 || a%3==0) return false;
        for (int i=5;i*i<=a;i+=6){
            if (a%i==0 || a%(i+2)==0) return false;
        }
        return true;
    }

    static void printAllPrime(int n){

        // Sieve of Eratosthenes algorithm
        if(n <= 1)  return;

        boolean[] arr = new boolean[n+1];
        Arrays.fill(arr,true);
        for (int i=2;i*i<=n;i++){
            if (arr[i]){
                for (int j=i*i;j<=n;j+=i){
                    arr[j] = false;
                }
            }
        }
        for (int i=2;i<=n;i++){
            if (arr[i]){
                System.out.printf(i+" ");
            }
        }
    }

    static long pow(long a,long b){
        long ans = b;
        long res =1;
        if(b<0){
            ans = -1*b;
        }
        while(ans>0){
            if((ans&1)==1){
                res = (res*a)%mod;
            }
            a = (a*a)%mod;
            ans = ans>>1;
        }
        if(b<0){
            res = 1/res;
        }
        return res;
    }
    static double pow(double a,long b){
        long ans = b;
        double res =1;
        if(b<0){
            ans = -1*b;
        }
        while(ans>0){
            if((ans&1)==1){
                res = (res*a)%mod;
            }
            a = (a*a)%mod;
            ans = ans>>1;
        }
        if(b<0){
            res = 1/res;
        }
        return res;
    }

    static void sort(int[] arr)
    {
        ArrayList<Integer> ls = new ArrayList<Integer>();
        for(int x: arr)
            ls.add(x);
        Collections.sort(ls);
        for(int i=0; i < arr.length; i++)
            arr[i] = ls.get(i);
    }

    static void sort(long[] arr)
    {
        ArrayList<Long> ls = new ArrayList<Long>();
        for(long x: arr)
            ls.add(x);
        Collections.sort(ls);
        for(int i=0; i < arr.length; i++)
            arr[i] = ls.get(i);
    }

    static HashMap<Integer, Integer>  sortValue(HashMap<Integer,Integer> h){
        List<Map.Entry<Integer, Integer> > list = new ArrayList<>(h.entrySet());
 
        // Sort the list
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer> >() {
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
                int fp = o2.getValue().compareTo(o1.getValue());
                int sp = o2.getKey().compareTo(o1.getKey());
                return fp==0 ? sp : fp;
            }
        });
        //clear the hashmap
        // h.clear();
        HashMap<Integer, Integer> hm = new LinkedHashMap<>();
        for(Map.Entry<Integer, Integer> mp : list){
            hm.put(mp.getKey(),mp.getValue());
        }
        return hm;
    }
    static HashMap<Integer, Integer>  sortKey(HashMap<Integer,Integer> h){
        List<Map.Entry<Integer, Integer> > list = new ArrayList<>(h.entrySet());
 
        // Sort the list
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer> >() {
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
                int fp = o2.getValue().compareTo(o1.getValue());
                int sp = o2.getKey().compareTo(o1.getKey());
                return fp==0 ? fp : sp;
            }
        });
        //clear the hashmap
        // h.clear();
        HashMap<Integer, Integer> hm = new LinkedHashMap<>();
        for(Map.Entry<Integer, Integer> mp : list){
            hm.put(mp.getKey(),mp.getValue());
        }
        return hm;
    }

    static long totient(long n)
    {
        long result = n;
        for (int p = 2; p*p <= n; ++p)
            if (n % p == 0)
            {
                while(n%p == 0)
                    n /= p;
                result -= result/p;
            }
        if (n > 1)
            result -= result/n;
        return result;
    }

    static int pow(int x,int y){
        return (int)Math.pow(x,y);
    }

    static void allDivisor(int a){
        int i=0;
        for (i=1;i*i<=a;i++){
            if (a%i==0){
                System.out.printf(i+" ");
            }
        }
        for (;i>=1;i--){
            if (a%i==0){
                System.out.printf(a/i+" ");
            }
        }
    }

    static int binaryToInt(String s){
        return Integer.parseInt(s,2);
    }
    static String toBinaryString(int s){
        return Integer.toBinaryString(s);
    }


    static void primeFactors(int a){
        if (a<=1) return;
        while (a%2==0) {System.out.printf(2+" "); a=a/2;}
        while (a%3==0) {System.out.printf(3+" "); a=a/3;}
        for (int i=5;i*i<=a;i+=6){
            while (a%i==0){
                System.out.printf(i+" ");
                a = a/i;
            }
            while (a%(i+2)==0){
                System.out.printf((i+2)+" ");
                a = a / (i+2);
            }
        }
        if (a>3){
            System.out.printf(a+" ");
        }
        System.out.println();
    }

    static int lcm(int a,int b){
        return a*b/gcd(a,b);
    }

    static int gcd(int a, int b){
        if (a==0) return b;
        return gcd(b%a,a);
    }

    static int countZeros(int f){
        int x = 0;
        for (int i=5;i<=f;i=i*5){
            x += f/i;
        }
        return x;
    }

    static int ExtendedGcd(int a, int b,int x,int y){
       if(b == 0){
           x = 1;
           y = 0;
           return a;
       }
        int x1=1,y1=1;
       int ans = ExtendedGcd(b, a%b,x1,y1);
       x = y1;
       y = x1 - (a/b)*y1;
       System.out.println(x+" "+y);
       return ans;
    }





//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////Lazy work/////////////////////////////////////////////////////////////


    
    static void input(int[] a){
        for (int i=0;i<a.length;i++){
            a[i] = in.nextInt();
        }
    }
    static void input(long[] a){
        for (int i=0;i<a.length;i++){
            a[i] = in.nextLong();
        }
    }
    static void input(String[] a){
        for (int i=0;i<a.length;i++){
            a[i] = in.next();
        }
    }

    static void swap(char[] c,int i,int j){
        char t = c[i];
        c[i] = c[j];
        c[j] = t;
    }
    static void swap(int[] c,int i,int j){
        int t = c[i];
        c[i] = c[j];
        c[j] = t;
    }
    static void swap(long[] c,int i,int j){
        long t = c[i];
        c[i] = c[j];
        c[j] = t;
    }

    static void print(int[] a){
        for (int i=0;i<a.length;i++){
            out.printf(a[i]+" ");
        }
        out.println();
    }

    static void print(int[][] a){
        for (int i=0;i<a.length;i++){
            for(int j=0;j<a[i].length;j++){
                out.printf(a[i][j]+" ");
            }
            out.println();
        }
    }

    static void print(long[] a){
        for (int i=0;i<a.length;i++){
            out.printf(a[i]+" ");
        }
        out.println();
    }

    static void print(char[] a){
        for (int i=0;i<a.length;i++){
            out.printf(a[i]+" ");
        }
        out.println();
    }

    static void print(String s){
        for (int i=0;i<s.length();i++){
            out.printf(s.charAt(i)+" ");
        }
        out.println();
    }

    static void print(ArrayList<Integer> a){
        a.forEach(e -> out.printf(e+" "));
        out.println();
    }

    static void print(LinkedList<Integer> a){
        a.forEach(e -> out.printf(e+" "));
        out.println();
    }
    
    static void print(HashSet<Integer> a){
        a.forEach(e -> out.printf(e+" "));
        out.println();
    }

    static void print(HashMap<Integer,Integer> a){

        for(Map.Entry<Integer, Integer> mp : a.entrySet()){
           out.println(mp.getKey() + " "+ mp.getValue());
        } 
    }

    static void reverse(int[] a){
        int i=0,j=a.length-1;
        while(i<j){
            int t = a[i];
            a[i] = a[j];
            a[j]= t;
            i++;
            j--;
        }
    }
    static String reverse(String s){
        char[] a = s.toCharArray();
        int i=0,j=a.length-1;
        while(i<j){
            char t = a[i];
            a[i] = a[j];
            a[j]= t;
            i++;
            j--;
        }
        return String.valueOf(a);
    }
}
class CompareP implements Comparator<Pair> {
    public int compare(Pair a, Pair b){
        long dif = a.v - b.v;
        if (dif > 0) return 1;
        if (dif < 0) return -1;
        return 0; 
    }
}
class CompareT implements Comparator<Triplet> {
    public int compare(Triplet a, Triplet b){
        long dif = a.z - b.z;
        if (dif > 0) return 1;
        if (dif < 0) return -1;
        return 0; 
    }
}

class Triplet{
    long x;
    long y;
    long z;
    public Triplet(long x,long y,long z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
}


class Pair {
    int k;
    int v;

    public Pair(int k, int v) {
        this.k = k;
        this.v = v;
    }
}
class ncr
{
    public int mod = 1000003;
    public long[] fact = new long[mod+1];
    public long[] ifact = new long[mod+1];
    public int nCr(long n, long r)
    {
        preFactFermat();
        long ans = 1;
        // while(n>0 && r>0){
        //     int a=(int) (n%mod),b= (int)(r%mod);
        //     n = n/mod;r=r/mod;
        //     if(a<b){
        //         return 0;
        //     }else{
        //         ans = (ans* (fact[a]*((ifact[b]*ifact[a-b])%mod)%mod))%mod;
        //     }
        // }
        ans = lucas(n,r,ans);
        
        return (int)ans;
    }
    public long lucas(long n,long r,long ans){
        if(r==0)return 1;
        long ni=n%mod,ri=r%mod;
        return (lucas(n/mod,r/mod,ans)*(fermat(ni,ri,ans)%mod))%mod;
    }
    
    public long fermat(long n,long r,long ans){
        if(n<r){
            return 0;
        }
        ans = (ans* (fact[(int)n]*((ifact[(int)r]*ifact[(int)(n-r)])%mod)%mod))%mod;
        return ans;
    }
    
    public void preFactFermat(){
        fact[1] = 1;
        fact[0] = 1;
        ifact[0] = expo(1,mod-2);
        ifact[1] = expo(1,mod-2);
        for(int i=2;i<=mod;i++){
            fact[i] = (i*(fact[i-1]%mod))%mod;
            ifact[i] = expo(fact[i],mod-2);
        }
    }
    
    public long expo(long a,long b){
        long ans = b;
        long res =1;
        if(b<0){
            ans = -1*b;
        }
        while(ans>0){
            if((ans&1)==1){
                res = (res*a)%mod;
            }
            a = (a*a)%mod;
            ans = ans>>1;
        }
        if(b<0){
            res = 1/res;
        }
        return res;
    }
}
class FenwickTree{

    int[] ft;

    public void print(){
        for (int i=0;i<ft.length;i++){
            System.out.printf(ft[i]+" ");
        }
    }

    public FenwickTree(int[] a){
        ft = new int[a.length+1];
        for (int i=0;i<a.length;i++){
            this.update(i,a[i]);
        }
    }

    public int getSum(int i){
        int sum = 0;

        while(i>0){
            sum += ft[i];
            i = i - (i & (-i));
        }
        return sum;
    }

    public void update(int i,int d){
        i = i +1;
        while(i<ft.length){
            ft[i] += d;
            i = i + (i &(-i));
        }
    }
}

class SegmentTree{
    
    int[] st;

    
    public SegmentTree(int[] a){
        st = new int[a.length*4];
        construct(a,0,a.length-1,0);
    }

    void print(){
        for(int i=0;i<st.length;i++){
            System.out.printf(st[i]+" ");
        }
        System.out.println();
    }

    int construct(int[] a,int ss,int se,int si){
        if(ss==se){
            st[si] = a[ss];
            return a[ss];
        }
        int mid = (ss+se)/2;

        st[si] = construct(a,ss,mid,2*si+1) + construct(a,mid+1,se,2*si+2);
        return st[si];
    }
    
    int getSum(int qs,int qe,int ss,int se,int si){
        if(qe<ss || qs>se){
            return 0;
        }
        if(ss>=qs && se <= qe){
            return st[si];
        }
        int mid = (ss+se)/2;

        return getSum(qs,qe,ss,mid,2*si+1) + getSum(qs,qe,mid+1,se,2*si+2);
    }
    
    void update(int ss,int se,int si,int i,int diff){
        if(ss > i || i> se){
            return;
        }
        this.st[si] += diff;
        if(ss< se){
            int mid = (ss+se)/2;
            update(ss,mid,2*si+1,i,diff);
            update(mid+1,se,2*si+2,i,diff);
        }
    }
}
                    

                        Solution in Python : 
                            
cache={i:i for i in range(12)}
def solve(i):
    global cache
    if i not in cache:
        cache[i] = max(solve(i//2)+solve(i//3)+solve(i//4), i)
    return cache[i]
while True:
    try:
        n=int(input())
    except:break
    print(solve(n))