Editorial for encrypt: Mã hóa mật khẩu

Hiểu bài toán

Bài toán yêu cầu giải mã một mật khẩu đã bị mã hóa. Mật khẩu gốc bao gồm một chuỗi các ký tự chữ cái (tiền tố) và một số nguyên dương ở cuối. Quá trình mã hóa thực hiện bằng cách chèn các chữ số (từ 0 đến 9) vào bất kỳ vị trí nào trong phần chuỗi chữ cái (kể cả đầu và cuối) sao cho tổng của tất cả các chữ số được chèn bằng với số ở cuối mật khẩu gốc.

Ví dụ: Mật khẩu gốc 'Abcd12' được mã hóa thành 'A1b23c4d2'.

• Phần chữ cái gốc: 'Abcd'.
• Số cuối gốc: 12.
• Các chữ số chèn: 1, 2, 3, 4, 2. Tổng = 12.

Đầu vào là một xâu đã mã hóa, chỉ chứa chữ cái Latinh và chữ số. Đầu ra cần khôi phục lại mật khẩu gốc (chuỗi chữ cái + số cuối).

Các cách tiếp cận

Cách Trích xuất và Tách từ (String Extraction & Tokenization)

#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main(){
    char a[100005];
    scanf(" %s",a);
    char b[] = "0123456789";
    char c[100005] = {'\0'};
    char d[100005] = "";
    strcpy(c,a);
    char *token = strtok(c,b);
    while(token != NULL){
        strcat(d,token);
        token = strtok(NULL,b);
    }
    int p = strlen(a);
    long long sum = 0;
    for (int i = 0;i < p; i++){
        if (isdigit(a[i])) sum += (a[i] - '0');
    }
    printf("%s%lld",d,sum);
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Phương pháp này sử dụng hàm strtok để tách chuỗi.

1. Chuỗi b chứa tất cả các ký tự phân tách (các chữ số từ 0 đến 9).
2. strtok được gọi trên bản sao của chuỗi đầu vào để tìm các token là các chuỗi con chỉ chứa chữ cái, ngăn cách bởi các chữ số.
3. Các token này được nối lại vào chuỗi d.
4. Vòng lặp riêng tính tổng các chữ số trong chuỗi gốc.
5. Kết quả là chuỗi d nối với tổng các chữ số. Cách này tận dụng thư viện sẵn có nhưng strtok có thể chậm và tiêu tốn bộ nhớ cho việc tạo bản sao và thao tác chuỗi.

Cách Duyệt đơn giản (Single Pass Iteration)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int main() {
    char str[100005];
    char cpy[100005];
    scanf("%s",str);
    int m = strlen(str);
    int k = 0,cnt = 0;
    for (int i = 0;i < m;i++){
        if ((str[i] >= 'A' && str[i] <= 'Z') || (str[i] >= 'a' && str[i] <= 'z')){
            cpy[k++] = str[i];
        }
        else if (str[i] >= '0' && str[i] <= '9'){
            cnt += str[i] - '0';
        }
    }
    printf("%s%d",cpy,cnt);
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là phương pháp trực quan và hiệu quả nhất.

1. Khởi tạo một mảng ký tự cpy để lưu phần chữ cái và một biến số nguyên cnt để lưu tổng các chữ số.
2. Duyệt qua từng ký tự của chuỗi đầu vào.
3. Nếu ký tự là chữ cái, thêm vào mảng cpy.
4. Nếu ký tự là chữ số, cộng giá trị số đó vào cnt.
5. Sau vòng lặp, in ra chuỗi cpy và giá trị cnt. Phương pháp này chỉ cần duyệt qua chuỗi một lần duy nhất, tối ưu cả về thời gian và bộ nhớ so với cách dùng strtok.

Cách Trích xuất thủ công (Manual Extraction)

#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main() {
    char s[100005];
    scanf("%s", s);
    int len = strlen(s);
    char letters[100005];
    int letter_idx = 0;
    int digit_sum = 0;

    for(int i = 0; i < len; i++) {
        if(isalpha(s[i])) {
            letters[letter_idx++] = s[i];
        } else {
            digit_sum += s[i] - '0';
        }
    }
    letters[letter_idx] = '\0';
    printf("%s%d", letters, digit_sum);
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là biến thể của phương pháp duyệt đơn giản, sử dụng hàm isalpha và isdigit để kiểm tra kiểu ký tự thay vì so sánh trực tiếp mã ASCII. Logic hoạt động giống hệt phương pháp thứ 2: tách riêng các chữ cái và tính tổng các chữ số, sau đó ghép lại.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Thứ tự các chữ cái trong phần mã hóa không thay đổi so với mật khẩu gốc, chỉ có các chữ số được chèn vào.
• Tổng các chữ số chèn vào bằng chính giá trị của số cuối trong mật khẩu gốc.
• Việc giải mã không cần quan tâm đến vị trí chèn các chữ số, chỉ cần tách hết các chữ số ra và tính tổng.

Lỗi thường gặp

• Sử dụng hàm gets có thể gây tràn bộ nhớ đệm nếu không kiểm soát độ dài, nên dùng scanf hoặc fgets.
• Quên khai báo mảng đủ lớn để chứa chuỗi đầu vào (cần lên tới 10^5 ký tự).
• Lỗi kiểu dữ liệu khi in tổng số nếu số đó quá lớn, nhưng theo đề bài số cuối tối đa 6 chữ số và tổng các chữ số chèn tối đa 9*10^5 nên int là đủ, nhưng long long là an toàn hơn.