COINS_2.cpp

#include <iostream>
using namespace std;

const int MAX = 10000000; 
unsigned long int store[MAX];

unsigned long int coins(unsigned long int n)
{
    unsigned long int a=n/2, b=n/3, c=n/4;	
    
	 // Nếu đổi thành 3 đồng xu nhỏ hơn
	 // mà giá trị thu được lớn hơn thì đổi
    if (a + b + c > n)
	{
		unsigned long int x,y,z;

		// Nếu giá trị đổi ra mà >= MAX hoặc < MAX 
		// mà nó chưa được tính thì ta phải tính.
		// Ngược lại thì ta lấy luôn giá trị lưu trong mảng.
		if(a >= MAX || store[a] == 0)
		{
			x = coins(a);
			if(a < MAX) store[a] = x;
		}
		else x = store[a];

		if(b >= MAX || store[b] == 0)
		{
			y = coins(b);
			if(b < MAX) store[b] = y;
		}
		else y = store[b];

		if(c >= MAX || store[c] == 0)
		{
			z = coins(c);
			if(c < MAX) store[c] = z;
		}
		else z = store[c];

		return x + y + z;
	}
	
	// Nếu không thì đổi luôn thành đồng xu.
	return n;	
}

int main() 
{
	 //freopen("input.txt","r",stdin);
     unsigned long int n;

	 for(int i = 0; i < MAX; i++)
		 store[i] = 0;

     while(cin >> n)
     {
          cout << coins(n) << endl;
     }

     return 0;
}