SPOJ.COM - Thuật toán bài COINS - Bytelandian gold coins

Posted on October 16th, 2016

Đề bài:

Ở Byteland, họ có một hệ thống tiền tệ rất kì lạ.

Mỗi đồng tiền vàng của họ có một số nguyên viết trên đó. Một đồng xu n có thể được trao đổi tại ngân hàng thành 3 đồng xu n/2, n/3 và n/4. Nhưng những số này luôn được làm tròn xuống (vì ngân hàng cần phải có lãi).

Bạn có thể bán những đồng xu này thành tiền đô la Mỹ. Tỉ lệ trao đổi là 1:1. Tuy nhiên, bạn không thể mua những đồng xu này.

Bạn có một đồng vàng. Hỏi số tiền tối đa bạn có thể có được là bao nhiêu.

Đầu vào

Đầu vào sẽ bao gồm một vài test case (số test case <= 10). Mỗi testcase sẽ chỉ bao gồm 1 dòng là số n, 0 <= n <= 1000000000. Đó là số được ghi trên đồng xu.

Đầu ra

Với mỗi test case, in ra một dòng giá trị số tiền tối đa bạn có thể có được.

Ví dụ

Đầu vào:

12 
2 

Đầu ra:

13 
2

Giải thích:

  • Test case 1: Bạn có thể đổi 12 thành 6, 4 và 3, rồi đổi chúng thành tiền tương ứng $6 + $4 + $3 = $13.

  • Test case 2: Nếu bạn thử đổi đồng xu 2 thành 3 đồng xu nhỏ hơn thì bạn sẽ nhận được 1, 0 và 0. Cuối cùng bạn chỉ nhận được $1. Do đó, trong trường hợp này, tốt nhất là bạn đổi đồng xu 2 thành $2.

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/COINS/

Phân tích

Bài toán này mình sẽ sử dụng đệ quy để quét hết tất cả các trường hợp có thể xảy ra. Với giới hạn thời gian là 9 giây thì cách này hoàn toàn có thể thực hiện được.

Nếu giới hạn thời gian nhỏ hơn thì với giá trị n tối đa là 1000000000, bắt buộc mình phải sử dụng thuật toán quy hoạch động - Dynamic programming để lưu lại trạng thái số tiền lớn nhất thu được sau khi trao đổi ứng với mỗi số n.

Ngoài ra, với giá trị n = 1000000000, thực tế là không thể khai báo mảng có độ dài như vậy. Do đó, mình sẽ chỉ lưu lại trạng thái tới giá trị n = 10000000.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

Cách 1:

Thời gian: 5.17s - Bộ nhớ 2.7M

#include <iostream>
using namespace std;

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)
		 return coins(a)+coins(b)+coins(c);

	 // 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;

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

	 return 0;
}

Cách 2:

Thời gian: 0.01s - bộ nhớ: 41M

#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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé: