CareerCup

precompute till 10^6 using D.P.
Then use recursion that stops if n<=1000000

This combination of precomputation + recursion should get it done within the time limit

I think a recursive with memoization solution would do. To save space, memoization can be implemented with hash table.

Pseudo-code may look like:

long long valueOf(long n){

    if (hash[n] != 0) return hash[n];

    if (n<4) return n;

    long long tmp = max(n, valueOf(n/2) + valueOf(n/3) + valueOf(n/4) );
    hash[n] = tmp;	// memoizing the tmp result into the hash.

    return tmp;
};

The hash table once memoized can be used for different function calls, thus it works efficiently for multiple test cases.

Note that, in this case memoization (top-down) may have better space complexity than using DP table (bottom-up).

//HIOS 


#include<iostream>

using namespace std;

int maxcoin(long int c)
{

    if((c/2+c/3+c/4)<c) return c;

    else return (maxcoin(c/2)+maxcoin(c/3)+maxcoin(c/4));

}

int main()

{
long int c;
cin>>c;

long int d=maxcoin(c);


cout<<d<<"$";


}

I think the key is that this process of trading for smaller coins can bring you more money or less money in an iterative fashion. For example, take a coin of value 24:
24 can be broken into 12, 8, 6.
12 in turn can be broken into 6, 4, 3.
Coins of 8 or 6 or 4 or 3 do not increase in value when breaking them, but by breaking a 24 and then breaking the resulting 12, you get 8 + 6 + 6 + 4 + 3 = 27.

So at each opportunity to either split a coin or trade it for dollars, you have to find the maximum. There are more efficient ways of doing this iteratively or with memo-ization but a simple recursive method only takes a few seconds for n=1,000,000,000. Java:

public static long maxCoinValue(long n) {
    if (n < 1)
      return 0;
    
    return Math.max(n,
        maxCoinValue(n / 2) +
        maxCoinValue(n / 3) +
        maxCoinValue(n / 4));
  }

private static int find(int n, String path) {
int a = n / 2;
int b = n / 3;
int c = n / 4;

int _n = a + b + c;

if (_n <= n) {
System.out.println(path);
return n;
}

int a1 = find(a, path + "/2 - > " + a);
int b1 = find(b, path + "/3 - > " + b);
int c1 = find(c, path + "/4 - > " + c);

return a1 + b1 + c1;
}

#include<cstdio>
#include<map>
using namespace std ;

map< long long int , long long int > h ;

inline long long int rec( long long int f )
{
if( f == 0 )
return 0 ;

long long int a = h[f] ;
if( a == 0 )
{
a= max(f,rec(f/2)+rec(f/3)+rec(f/4));
h[f]=a;
}
return a ;
}

int main( )
{
long long int n ;

while( ~scanf("%lld",&n) )
printf("%lld\n",rec(n)) ;

return 0 ;
}