Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

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 tôi 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 tôi lại sử dụng khoảng cách này một cách ngẫu nhiên. Để giải mã tôi phải đoán khoảng cách này. Vì vậy, tôi 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

Các 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:

+ Tôi 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 tôi 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 tôi 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à tôi 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ì tôi sẽ bắt đầu giải mã.

Lời giải:

(Các 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 tôi 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 tôi 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 các 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;
}

Code by Phạm Văn Lâm.

98 views

1 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài GCPC11F – Diary trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

Để lại bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *