SPOJ.COM - Thuật toán bài NSTEPS - Number Steps

Đề bài:

Bắt đầu từ điểm có tọa độ (0,0) trên mặt phẳng. Chúng mình đã viết sẵn những số nguyên không âm 0, 1, 2,.. như hình dưới. Ví dụ: 1, 2, 3 lần lượt được viết ở các điểm (1, 1), (2,0) và (3,1), và cách viết này sẽ được tiếp tục.

Bạn hãy viết một chương trình đọc vào tọa độ (x, y) và viết ra số tương ứng với tọa độ đó (nếu có). Biết giá trị của tọa độ x, y đều thuộc từ 0 đến 10000.

Đầu vào

Dòng đầu tiên của đầu vào là số N - số lượng test case. N dòng tiếp theo, mỗi dòng sẽ gồm 2 số tương ứng là tọa độ x, y của một điểm.

Đầu ra

Với mỗi test case, in ra trên một dòng một số là số tương ứng với tọa độ đó nếu có. Ngược lại thì in ra No Number.

Ví dụ

Đầu vào:

3
4 2
6 6
3 4

Đầu ra:

6
12
No Number

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

Phân tích

• Bài này sử dụng thuật toán tham lam Greedy để giải quyết.

• Trước tiên, bạn có thể thấy rằng các số sẽ nằm trên 2 đường thẳng có phương trình là y = x và y = x - 2. Do đó, khi đọc vào một điểm (x, y), nếu như điểm đó không thuộc một trong hai đường trên thì có nghĩa là sẽ không có số. Ngược lại, chắc chắn sẽ có số.

• Tiếp theo, vì các điểm thuộc 2 phương trình y = x và y = x - 2 nên tọa độ của chúng sẽ cùng chẵn hoặc cùng lẻ. Hơn nữa, mình phát hiện ra một quy luật đó là:

  • Nếu x, y chẵn thì giá trị số = x + y.
  • Nếu x, y lẻ thì giá trị số = x + y - 1.

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;

int CheckValid(int x, int y)
{
	if (x >= y && x - y <= 2)
	{
		if (x%2 == 0 && y%2 == 0) return x + y;
		if (x%2 == 1 && y%2 == 1) return x + y -1;
	}
	return -1;
}

int main()
{
	//freopen("input.txt","r", stdin);
	int N, x, y;
	cin >> N;
	for(int tc = 0; tc < N; tc++)
	{
		cin >> x >> y;
		int ch = CheckValid(x,y);

		if ( ch == -1) cout << "No Number" << endl;
		else cout << ch << endl;
	}
	return 0;
}