SPOJ.COM - Thuật toán bài HANGOVER - Hangover

Posted on December 5th, 2016

Đề bài:

Bạn có thể tạo ra độ dài bao xa khi xếp những quân bài bên trên một cái bàn. Nếu bạn có một quân bài bạn có thể tạo ra độ dài tối đa là 1/2 quân bài. Giả sử rằng những quân bài vuông góc với bàn. Với 2 quân bài bạn có thể làm cho quân bài trên nhô ra so với quân bài ở dưới độ dài là 1/2 quân bài. Và quân bài dưới cùng nhô ra so với bàn 1/3 độ dài quân bài. Như vậy, tổng độ dài là 1/2 + 1/3 = 5/6 độ dài quân bài. Như vậy, bạn có thể xếp được n quân bài với độ dài nhô ra là: 1/2 + 1/3 + 1/4 + ... + 1/(n+1)) độ dài quân bài.

Đầu vào

Bao gồm một hay nhiều test case, mỗi test case chỉ bao gồm 1 dòng, chứa 1 số thực dương c, có giá trị từ 0.01 đến 5.20. c có chính xác 3 chữ số.

Đầu ra

Mỗi test case in ra trên một dòng số lượng quân bài tối thiểu để đạt được c độ dài quân bài. Đầu ra theo dạng ví dụ dưới đây.

Ví dụ

Đầu vào:

1.00
3.71
0.04
5.19
0.00

Đầu ra:

3 card(s)
61 card(s)
1 card(s)
273 card(s)

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

Phân tích

Với bài toán này, cách xếp con bài là không thay đổi. Do đó, mình sẽ sử dụng một mảng để lưu lại độ dài khi xếp n con bài. Thuật toán ở đây sẽ là thuật toán vét cạn Brute Force.

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++

#include <iostream>
using namespace std;

const int MAX = 1000000;
float a[MAX];	// Độ dài khi xếp n quân bài

float F(int n)
{
	float f = 0.0f;
	for(int i = 2; i <= n+1; i++)
		f += 1.0f/i;
	return f;
}

int main()
{
	//freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	for(int i = 0; i < MAX; i++)
		a[i] = -1;

	float c = 0.0f;
	while(true)
	{
		cin >> c;
		if(c == 0.00) break;
		for(int i = 0; i < MAX; i++)
		{
			float f = 0.0f;
			if(a[i] < 0)
			{
				f = F(i);
				a[i] = f;
			}
			else f = a[i];

			if(f > c) 
			{ 
				cout << i << " card(s)" << endl;
				break;
			}
		}
	}
	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é:

Xin chào và hẹn gặp lại, thân ái!