Recent CP News

Bytelandian Gold Coins || Hard Problem

Let’s get some Bytelandian Gold Coins (;

In Byteland they have a very strange monetary system. Each Bytelandian Gold Coins have 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 test case is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your Byteland Gold 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
2

SAMPLE OUTPUT

13
2

Solution With Explanation

From the problem definition, say f (n) = ways to compute the change.

f (n) = max (n, f (n / 2) + f (n / 3) + f (n / 4))  (by definition).    
f (0) = 0   (Base case).

Problem 1: Writing a simple recursive solution will time out due to exponential complexity i.e. O (3 ).
Problem 2: Writing a linear dynamic programming solution using arrays will exceed memory limit since N can be 10 in the worst case.

To circumvent both of the aforementioned problems, we can use maps and memorization.

Note: This is one of those problems where state space is extra large and memoization only explores space what is needed unlike bottom-up dynamic programming which needs one to visit all the state space, memoization is the preferred solution in this case.

Time Complexity: O (N)
Space Complexity: O (log N)

Code in C++

// {{{ Headers
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <cassert>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#include <fstream>
#include <iostream>
#include <sstream>

#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;
// }}}

typedef long long int64;
const int INF = 0x3f3f3f3f;
template <class T> inline int len (const T &a) { return a.size (); }

#define MAXN 50
char line [MAXN];
map <int, int64> memo;

int64
solve (int n) {
    if (n == 0 || n == 1) return n;
    if (memo.count (n)) return memo [n];
    int64 ret = n;
    ret = max (ret, solve (n / 2) + solve (n / 3) + solve (n / 4));
    return memo [n] = ret;
}

int
main () {
#ifdef LOCALHOST
    freopen ("test.in", "r", stdin);
    // freopen ("test.out", "w", stdout);
#endif

    int N;
    while (fgets (line, MAXN, stdin)) {
        sscanf (line, "%d", &N);
        int64 ret = solve (N);
        printf ("%lld\n", ret);
    }

    return 0;
}

{Code with Code@ter}

Give Your Reviews




Leave a Reply