SPOJ: COINS – Bytelandian gold coins

Problem Link

http://www.spoj.com/problems/COINS/

Problem Description

In this problem, We can exchange each coin of value n with three coins of value (n/2),(n/3),(n/4).
So, we need to find maximum value we can obtain from a coin of n value.

Concepts Used

This is a straightforward DP problem.

Code

#include<bits/stdc++.h>
using namespace std;

// long long int as resultant value can be greater than 10^9.
long long int dp[10000005];

long long int coins(long long int n)
{
    //Base case
    if(n==0)
        return 0;

    // can't store value greater than 10^7 in an array so use recursion
    if(n>=10000000)
        return max(n,coins(n/2)+coins(n/3)+coins(n/4));

    // if dp[n] has already been calculated, then return that value.
    if(dp[n]!=0)
        return dp[n];

        // calculate the value
    dp[n]=max(n,coins(n/2)+coins(n/3)+coins(n/4));

        return dp[n];
}

long long int n;
int main()
{
        /*function to assign 0 to every location in dp array equivalent to

    for(i=0;i<sizeof(dp);i++)
        dp[i]=0;

        but it always intialise the whole array i.e. whole size of dp.
        */
            memset(dp,0,sizeof(dp));

    // to read untill end of file
    while(scanf("%lld",&n)!=EOF)
        printf("%lld\n",coins(n));

return 0;
}

Explanation

  1. Input the values of n till end of file.
  2. Call the function coins(n) for each value of n.
  3. An array long long int dp[10000005] is declared and the values set to 0. Here the limit of n is 10^9 but we can store only upto 10^7 in an array so we create a dp of 10^7 and for bigger values, we just apply recursive method.
  4. dp[i] represents the maximum amount we can obtain from coin value i.
  5. So, we memoize the coin values in dp and if(dp[i]!=0) means it has already been evaluated, then return dp[i] else evaluate it by considering it as
dp[i]= max(i,coins(i/2)+coins(i/3)+coins(i/4));

if(n==0)
    return 0; // This is base case

This content has been helpful to you?

Thanks for contributing!

Yes No