Hướng dẫn giải của Mật khẩu an toàn


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, thattinh777, thanhdoan, nquang2909

Editorial for passw: Mật khẩu an toàn

Hiểu bài toán

Bài toán yêu cầu tính 'độ an toàn' của từng mật khẩu trong danh sách. Độ an toàn được tính dựa trên hai tiêu chí:

  1. Độ dài: Nếu độ dài m của mật khẩu:
    • m <= 5: điểm = 0.
    • m > 5: điểm = min(5, m - 5) (tức là m - 5, nhưng tối đa là 5).
  2. Loại ký tự: Mật khẩu có thể chứa các ký tự in hoa (A-Z), in thường (a-z), và số (0-9).
    • 1 loại: điểm = 1.
    • 2 loại: điểm = 2.
    • 3 loại: điểm = 5. Độ an toàn tổng là tổng của hai điểm trên. Input gồm số lượng mật khẩu nn chuỗi mật khẩu. Output là các độ an toàn tương ứng, cách nhau bởi dấu cách. Giới hạn: n <= 100, độ dài mật khẩu <= 15.

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

Cách Duyệt chuỗi và kiểm tra từng ký tự (Cơ bản)
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char pass[101];
        scanf("%s", pass);

        int len = strlen(pass);
        int has_upper = 0, has_lower = 0, has_digit = 0;

        // Kiểm tra từng ký tự để xác định loại
        for (int i = 0; i < len; i++) {
            if (isupper(pass[i])) has_upper = 1;
            else if (islower(pass[i])) has_lower = 1;
            else if (isdigit(pass[i])) has_digit = 1;
        }

        // Tính điểm độ dài: min(5, max(len - 5, 0))
        int length_score = (len - 5 > 0) ? (len - 5) : 0;
        if (length_score > 5) length_score = 5;

        // Tính điểm loại ký tự
        int type_count = has_upper + has_lower + has_digit;
        int type_score;
        if (type_count == 1) type_score = 1;
        else if (type_count == 2) type_score = 2;
        else type_score = 5;

        printf("%d ", length_score + type_score);
    }
    return 0;
}
  • Time Complexity: O(T * L) (T là số lượng pass, L là độ dài tối đa 15)
  • Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Với mỗi mật khẩu, ta chỉ cần duyệt qua từng ký tự một lần. Trong quá trình duyệt, ta sử dụng các biến cờ (flag) để đánh dấu sự xuất hiện của các loại ký tự (in hoa, in thường, số).

  • Tính điểm loại ký tự: Sau khi duyệt xong, đếm số lượng cờ đang bật (1, 2, hoặc 3) và gán điểm tương ứng.
  • Tính điểm độ dài: Áp dụng công thức min(5, max(len - 5, 0)) trực tiếp vào độ dài của chuỗi. Cách này rất dễ hiểu và dễ cài đặt.
Cách Sử dụng hàm tiện ích
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<math.h>

int max(int a, int b){
    return a > b ? a : b;
}

int min(int a, int b){
    return a < b ? a : b;
}

// Hàm đếm số lượng loại ký tự
int count_types(char *s){
    int dem = 0;
    int len = strlen(s);
    int has_digit = 0, has_lower = 0, has_upper = 0;

    for(int i = 0; i < len; i++){
        if(s[i] >= '0' && s[i] <= '9') has_digit = 1;
        else if(s[i] >= 'a' && s[i] <= 'z') has_lower = 1;
        else if(s[i] >= 'A' && s[i] <= 'Z') has_upper = 1;
    }

    return has_digit + has_lower + has_upper;
}

int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        char s[16];
        scanf("%s", s);

        // Tính điểm độ dài
        int score_len = min(5, max(strlen(s) - 5, 0));

        // Tính điểm loại
        int types = count_types(s);
        int score_type = 0;

        if(types == 3) score_type = 5;
        else if(types == 2) score_type = 2;
        else if(types == 1) score_type = 1;

        printf("%d ", score_len + score_type);
    }
    return 0;
}
  • Time Complexity: O(T * L)
  • Space Complexity: O(1)

Cách này tương tự cách 1 nhưng được tổ chức code tốt hơn bằng cách tách logic đếm loại ký tự ra thành một hàm riêng (count_types) và sử dụng các hàm min, max để tính điểm độ dài một cách ngắn gọn. Cấu trúc code rõ ràng hơn, dễ bảo trì hơn. Logic tính toán vẫn giữ nguyên: duyệt qua chuỗi để cập nhật trạng thái các loại ký tự, sau đó tính điểm.

Cách Tối ưu hóa kiểm tra loại ký tự (Loop Fusion)
#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        char s[20];
        scanf("%s", s);
        int len = strlen(s);

        // Tính điểm độ dài
        int len_score = len - 5;
        if (len_score < 0) len_score = 0;
        if (len_score > 5) len_score = 5;

        // Kiểm tra loại ký tự trong 1 vòng lặp duy nhất
        int has_upper = 0, has_lower = 0, has_digit = 0;
        for (int i = 0; i < len; i++) {
            char c = s[i];
            if (c >= 'A' && c <= 'Z') has_upper = 1;
            else if (c >= 'a' && c <= 'z') has_lower = 1;
            else if (c >= '0' && c <= '9') has_digit = 1;

            // Tối ưu: thoát sớm nếu đã đủ 3 loại (thoát vòng lặp)
            if (has_upper && has_lower && has_digit) break;
        }

        int type_count = has_upper + has_lower + has_digit;
        int type_score;
        if (type_count == 3) type_score = 5;
        else if (type_count == 2) type_score = 2;
        else type_score = 1;

        printf("%d ", len_score + type_score);
    }
    return 0;
}
  • Time Complexity: O(T * L)
  • Space Complexity: O(1)

Đây là phiên bản tối ưu nhất về mặt kỹ thuật.

  1. Kiểm tra điều kiện thoát sớm: Trong vòng lặp duyệt ký tự, nếu ta đã tìm thấy cả 3 loại ký tự (has_upper, has_lower, has_digit đều bằng 1), ta có thể break ngay lập tức. Vì độ dài chuỗi rất ngắn (<=15), việc này không tạo ra sự khác biệt lớn về tốc độ nhưng là một kỹ thuật lập trình tốt.
  2. Tránh gọi hàm library: Sử dụng so sánh ký tự trực tiếp (c >= 'A' && c <= 'Z') thay vì isupper có thể nhanh hơn một chút và không phụ thuộc vào thư viện ctype.h.
  3. Tính toán trực tiếp: Việc tính điểm độ dài và loại được thực hiện ngay khi có thông tin cần thiết.

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

Cách tiếp cận Time Space Tên
1 O(T * L) (T là số lượng pass, L là độ dài tối đa 15) O(1) Duyệt chuỗi và kiểm tra từng ký tự (Cơ bản)
2 O(T * L) O(1) Sử dụng hàm tiện ích
3 O(T * L) O(1) Tối ưu hóa kiểm tra loại ký tự (Loop Fusion)

Bài học kinh nghiệm

  • Bài toán là bài toán simulation/khảo sát đơn giản, không cần thuật toán phức tạp. Chỉ cần duyệt qua dữ liệu đầu vào và áp dụng công thức định sẵn.
  • Có thể tối ưu hóa việc kiểm tra loại ký tự bằng cách kết hợp các điều kiện trong một vòng lặp duy nhất và thoát sớm nếu đã đủ 3 loại.
  • Nên sử dụng các biến cờ (boolean/integer 0-1) để theo dõi sự tồn tại của các loại ký tự thay vì đếm số lượng ký tự cụ thể.

Lỗi thường gặp

  • Sai công thức tính điểm độ dài: Cần chú ý min(5, max(m - 5, 0)). Nếu m <= 5, kết quả phải là 0, không phải âm.
  • Quên xử lý trường hợp m > 10: Khi m = 11, m - 5 = 6, nhưng điểm tối đa là 5, cần dùng hàm min.
  • Trộn lẫn các loại ký tự: Đảm bảo phân biệt rõ ràng giữa a-z, A-Z, và 0-9 khi kiểm tra.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.