SPOJ.COM - Thuật toán bài ACODE - Alphacode

Đề bài:

Alice và Bob cần gửi những tin nhắn bí mật cho nhau. Và họ đã thảo luận ra cách để mã hoá chúng:

Alice: "Chúng ta hãy sử dụng một cách đơn giản. Chúng ta sẽ cho 'A' ứng với 1, 'B' ứng với 2,..., cứ như vậy thì 'Z' sẽ ứng với 26"

Bob: "Đó là một cách mã hoá ngớ ngẩn, Alice. Giả sử tớ muốn gửi cho cậu từ 'BEAN' thì mã sẽ là 25114. Cậu có thể giải mã nó với nhiều cách khác nhau."

Alice: "Dĩ nhiên là cậu có thể. Tuy nhiên, cậu sẽ chọn từ nào? Ngoài 'BEAN' ra thì còn có 'BEAAD', 'YAAD', 'YAN', 'YKD' và 'BEKD'. Tớ nghĩ cậu sẽ tìm ra cách giải mã đúng nhất. Và tại sao cậu lại gửi cho tớ từ 'BEAN'"

Bob: "OK, có lẽ đây là một ví dụ không tốt. Nhưng tớ cá là nếu như độ dài xâu là 5000 thì sẽ có hàng tấn cách giải mã khác nhau. Và với rất nhiều những cách đó, chắc hẳn cậu sẽ tìm ra ít nhất 2 cái có nghĩa"

Alice: "Có bao nhiêu cách giải mã?"

Bob: "Hàng tỉ tỉ cách" Vì một số lí do, Alice vẫn không bị thuyết phục bởi Bob. Vì vậy, cô ấy yêu cầu Bob viết một chương trình để xác định xem có bao nhiêu cách giải mã đối với một xâu cho trước.

Đầu vào

Bao gồm nhiều test case, mỗi cái sẽ bao gồm 1 dòng chứa một xâu có tối đa 5000 chữ số, biểu diễn một cách mã hoá hợp lệ. Ví dụ: không có dòng nào bắt đầu bởi '0'. Và không có khoảng cách giữa các kí tự. Đầu vào kết thúc bởi '0'.

Đầu ra

In đáp án. tất cả đáp án sẽ trong phạm vi giới hạn của số nguyên có dấu 64 bit.

Ví dụ

Đầu vào:

25114
1111111111
3333333333
0

Đầu ra:

6
89
1

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

Phân tích

Ở đây mình sử dụng thuật toán quy hoạch động Dynamic programming và triển khai theo kiểu top - down. Nghĩa là mình sẽ viết hàm đệ quy để giải quyết bài toán này.

Mình sẽ dùng một mảng một chiều là Memo[MAX]. Trong đó, Memo[i] là số cách giải mã được khi tính từ kí tự i đến cuối (i được tính từ 0). Và hàm đệ quy tương ứng là Solve(i)

Ở đây, vì các chữ cái từ 'A' đến 'Z' tương ứng với các số từ 1 đến 26. Do đó, khi duyệt mình cần chú ý đến hai trường hợp là chọn 1 chữ số hay 2 chữ số để giải mã.

Có một chú ý ở đây là chữ số '0' không thể đứng một mình và không thể đứng trước một chữ số khác. Tức là nếu mình có đầu vào là: 1026 thì ở đây, chữ cái đầu tiên chắc chắn là K, tương ứng với số 10. Do đó, kết quả có thể là KBF hoặc KZ. Không thể lấy số 1 ra để giải mã. Vì khi đó ta có A026. Mà số 0 hay 02 thì không hợp lệ.

Công thức đệ quy mình sẽ viết rõ ở trong code. Bạn có thể tham khảo ở dưới.

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 = 5005;

char Str[MAX];
int Leng;
long long Memo[MAX];// Memo[i] là số cách tính từ kí tự i đến cuối.

int GetLeng(char *s)
{
	int leng = 0;
	while(s[leng] != '\0') leng++;
	return leng;
}

/*
* Lấy 2 kí tự tiếp theo trong xâu s, bắt đầu từ vị trí i
* RETURN: giá trị số nguyên của 2 chữ số đó.
*/
int Get2Next(char *s, int i)
{
	return (s[i] - '0') * 10 + s[i + 1] - '0';
}

long long Solve(int i)
{
	if(Str[i] == '0') return -1;
	if(Memo[i] != -1) return Memo[i];

	int t = Get2Next(Str, i);

	if(t == 10 || t == 20)
		return Memo[i] = Solve(i + 2);

	if(t <= 26)
	{
		long long t1 = Solve(i + 1);
		long long t2 = Solve(i + 2);

		// Kiểm tra xem t1, t2 cái nào hợp lệ.
		if(t1 == -1 && t2 != -1) return Memo[i] = Solve(i + 2);
		if(t1 != -1 && t2 == -1) return Memo[i] = Solve(i + 1);
		if(t1 == -1 && t2 == -1) return -1;
		return Memo[i] = Solve(i + 1) + Solve(i + 2);
	}
	return Memo[i] = Solve(i + 1);
}

int main(int argc, char** argv)
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	while(true)
	{
		cin >> Str;
		if(Str[0] == '0') break;
		Leng = GetLeng(Str);

		for(int i = 0; i < Leng; i++)
			Memo[i] = -1;

		if(Str[Leng-1] != '0') Memo[Leng-1] = 1;

		// Nếu 2 chữ cái đầu tiên có giá trị <= 26 thì tính đến 2 kí tự
		// Ta có hai cách: ví dụ: 25
		// Có 2 cách giải mã là: BE hoặc Y
		int t = Get2Next(Str, Leng-2);

		if(t > 26 || t == 10 || t == 20) Memo[Leng-2] = 1;
		else Memo[Leng-2] = 2;

		// Print the answer to standard output(screen).
		cout << Solve(0) << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}