Bytelandian gold coins


Problem Statement :


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.



Solution :



title-img


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


View More Similar Problems

No Prefix Set

There is a given list of strings where each string contains only lowercase letters from a - j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked. Note If two strings are identical, they are prefixes of each other. Function Descriptio

View Solution →

Cube Summation

You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor

View Solution →

Direct Connections

Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do

View Solution →

Subsequence Weighting

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =

View Solution →

Kindergarten Adventures

Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti

View Solution →

Mr. X and His Shots

A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M

View Solution →