SPOJ.COM - Thuật toán bài CANTON - Count on Cantor

Đề bài:

Một trong những phép chứng minh nổi tiếng trong toán học hiện đại là phép chứng minh của Georg Cantor về dãy những số hữu tỷ đếm được. Cái này thực hiện bằng cách sử dụng phép đếm những số hữu tỷ được trình bày như hình sau:

1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1

Trên hình trên, số hạng đầu tiên là 1/1, thứ hai là 1/2, thứ 3 là 2/1, thứ tư là 3/1 và thứ 5 là 2/2, vân vân.

Đầu vào

Bắt đầu bằng số t, t <= 20, là số lượng test case. Sau đó là t test case. Mỗi test case chứa một số trên 1 dòng.

Đầu ra

Bạn hãy viết một chương trình để đọc danh sách các số, trong khoảng từ 1 đến 10^7 và in ra số hạng tương ứng theo cách đếm trên.

Ví dụ

Đầu vào:

3
3
14
7

Đầu ra:

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4

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

Phân tích

Mình sẽ sử dụng thuật toán tham lam Greedy để giải bài toán.

Nếu đánh số thứ tự cho các số từ 1, và coi mỗi đường chéo là một hàng thì mình sẽ có quy luật như sau:

1 
2 3 
4 5 6 
7 8 9 10 
...

Ta chỉ xét tới số nhỏ nhất của mỗi hàng là: 1, 2, 4, 7, ... sẽ có công thức như sau: x1 = 1 và x_n = 1 + (n*(n-1)) / 2 với n sẽ là chỉ số hàng.

Bạn có thể thay thử n vào sẽ thấy công thức trên đúng. Lúc này nếu như mình cần tìm số hạng thứ a. Mình có thể tìm được chỉ số của hàng chứa a bằng cách cho 1 + (n*(n-1)) / 2 = a. Suy ra: n = (1 + sqrt(8a-7))/2. Thực tế sẽ không đúng, tuy nhiên vì phép chia này là phép chia nguyên do đó kết quả cho ra là hoàn toàn đúng.

Bây giờ mình đã có được chỉ số hàng của hàng chứa a rồi là n. Suy ra số nhỏ nhất của hàng đó là: 1 + (n*(n-1)) / 2

Quy luật tiếp theo có thể thấy được là trên cùng một hàng thì tổng của tử số và mẫu số là như nhau với mọi số hạng và nó chính bằng chỉ số hàng + 1.

Cụ thể tiếp theo như nào xin mời bạn xem code của mình phía dưới nhé.

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>
#include <math.h>
using namespace std;

#define ull unsigned long long

/*	sum	 	term		id	x
*	 2		1			1	1
*	 3		2	3		2	2
*	 4		4	5	6	3	4
*	 5		7	8	9	4	7
*
*	1,2,4,7,...=> x1 = 1, x_n = 1 + n(n-1)/2;
*	we have term = a => 1 + n(n-1)/2 = a => n = (1 + sqrt(8a-7))/2
*/

int main()
{
	//freopen("input.txt","r",stdin);
	ull t = 0;
	cin >> t;
	for(int tc = 0; tc < t; tc++)
	{
		ull a = 0;
		cin >> a;

		ull id  = (1 + (ull) sqrt(8*a-7))/2;
		ull sum = id + 1;
		ull start = 1 + (id * (id-1))/ 2;
		ull delta = (a - start);

		ull y = 1;
		ull x = sum - y;

		x -= delta;
		y += delta;

		if(sum%2 == 0)
		{
			// form: x/y
			cout << "TERM " << a << " IS " << x << "/" << y << endl;
		}
		else
		{
			// form: y/x
			cout << "TERM " << a << " IS " << y << "/" << x << endl;
		}
	}
	return 0;
}