Hướng dẫn giải của Mật khẩu an toàn
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ậpTác giả: , , ,
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í:
- Độ dài: Nếu độ dài
mcủ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).
- 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
nvànchuỗ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.
- 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ểbreakngay 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. - 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ìisuppercó thể nhanh hơn một chút và không phụ thuộc vào thư việnctype.h. - 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ếum <= 5, kết quả phải là 0, không phải âm. - Quên xử lý trường hợp
m > 10: Khim = 11,m - 5 = 6, nhưng điểm tối đa là 5, cần dùng hàmmin. - 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-9khi kiểm tra.
Bình luận