SPOJ.COM - Thuật toán bài GCPC11F - Diary

Đề bài:

Ngày nay, con người muốn kết nối với nhau theo một cách an toàn hơn nhờ việc sử dụng thuật toán mã hóa không đối xứng, ví dụ RSA. Tuy nhiên, anh trai mình lại sử dụng một cái khác, một phương pháp mã hóa đơn giản hơn, để viết nội dung nhật kí của anh ấy. Khoảng cách giữa kí tự gốc và kí tự được mã hóa là cố định. Nếu chúng ta định nghĩa khoảng cách này là d = 5, thì khi đó A sẽ được thay bởi F; B được thay bởi G; C được thay bởi H;... và Z được thay bởi E.

Với việc biết trước khoảng cách d này, việc giải mã sẽ trở nên vô cùng đơn giản. Tuy nhiên anh trai mình lại sử dụng khoảng cách này một cách ngẫu nhiên. Để giải mã mình phải đoán khoảng cách này. Vì vậy, mình sử dụng một dấu hiệu đó là kí tự E xuất hiện nhiều hơn các kí tự khác. Bạn có thể viết một chương trình để tính khoảng cách d dựa vào vấn đề đó là kí tự được sử dụng nhiều nhất trong chuỗi kí tự đã được mã hóa sẽ được thay thế cho kí tự E. Và dĩ nhiên là giải mã chuỗi kí tự đó.

Đầu vào

Bao gồm nhiều test case, số test case c thỏa mãn 1 ≤ c ≤ 100. Mỗi test case được cho trên 1 dòng. Nội dung chỉ bao gồm các kí tự viết hoa từ A-Z, và có tối đa 1000 kí tự, bao gồm cả dấu cách.

Đầu ra

In ra một dòng chứa khoảng cách d nhỏ nhất có thể (0 ≤ d ≤ 25) và chuỗi kí tự được giải mã. Nếu không thể giải mã được do có nhiều khoảng cách thỏa mãn luật trên thì in ra "NOT POSSIBLE". Chú ý rằng kí tự cách sẽ không được mã hóa.

Ví dụ

Đầu vào:

4
RD TQIJW GWTYMJWX INFWD JSYWNJX ZXJ F XNRUQJ JSHWDUYNTS YJHMSNVZJ
THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK UVTIPGKZFE
XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK

Đầu ra:

5 MY OLDER BROTHERS DIARY ENTRIES USE A SIMPLE ENCRYPTION TECHNIQUE
10 JXU GKYSA RHEMD VEN ZKCFI ELUH JXU BQPO TEW
17 GERMAN COLLEGIATE PROGRAMMING CONTEST DECRYPTION
NOT POSSIBLE

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

Phân tích

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

• Để giải bài toán này, trước tiên mình phải tìm ra kí tự nào được sử dụng nhiều nhất để tính ra khoảng cách d theo như luật trên. Có nhiều cách để tính, còn ở đây mình sử dụng cách đơn giản nhất đó là sử dụng mảng đếm tần suất.

• Việc tiếp theo là mình sẽ đếm xem có bao nhiêu trường hợp có cùng khoảng cách d như vậy. Nếu như có hơn một trường hợp thì không thể giải mã được. + Nếu có thể giải mã được thì mình sẽ bắt đầu giải mã.

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 = 1005;
int cnt[300];

int main()
{
	//freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);

	int Testcase = 0;
	cin >> Testcase;

	cin.get();
	for(int tc = 0; tc < Testcase; tc++)
	{
		for(int i = 0; i < 300; i++)
			cnt[i] = 0;

		char text[MAX];
		cin.getline(text,MAX);

		int leng = 0;
		while(text[leng] != '\0')
		{
			cnt[text[leng]]++;
			leng++;
		}

		int max_frequent = 0;	// tần suất nhiều nhất
		int character = 0;		// kí tự với tần suất lớn nhất
		for(int i = 'A'; i <= 'Z'; i++)
			if(cnt[i] > max_frequent)
			{
				max_frequent = cnt[i];
				character = i;
			}

		// Đếm số kí tự có tần suât lớn nhất
		int num_max = 0;
		for(int i = 'A'; i <= 'Z'; i++)
			if(cnt[i] == max_frequent)
				num_max++;

		// Nếu có nhiều hơn một trường hợp thì không thể giải mã
		if(num_max > 1)
			cout << "NOT POSSIBLE" << endl;
		else	// giải mã
		{
			int d;
			if(character >= 'E')
			{
				d = character - 'E';
				cout << d << " ";

				for(int i = 0; i < leng; i++)
				{
					if(text[i] == ' ') cout << ' ';
					else
					{
						int temp = text[i] - d;
						if(temp >= 'A') cout << (char)temp;
						else
						{
							int delta = 'A' - temp;
							cout << (char)('Z' - delta + 1);
						}
					}
				}
			}
			else
			{
				d = ('Z' - 'E') + character - 'A' + 1;
				cout << d << " ";

				int back = 'E' - character;
				for(int i = 0; i < leng; i++)
				{
					if(text[i] == ' ') cout << ' ';
					else
					{
						int temp = text[i] + back;
						if(temp <= 'Z') cout << (char) temp;
						else
						{
							int del = temp - 'Z';
							cout << (char)('A' + del - 1);
						}
					}
				}
			}
			cout << endl;
		}
	}

	return 0;
}