Khởi tạo mật khẩu
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Steve xây dựng một diễn đàn cho Câu lạc bộ Tin học. Khi đăng ký, hệ thống sẽ tạo một mật khẩu dễ nhớ nhưng không quá đơn giản.
Hệ thống đưa ra bốn số nguyên ~n, a, b, c~. Người dùng cần nhập một xâu mật khẩu độ dài đúng ~n~ chỉ gồm các ký tự sau:
- chữ cái hoa: ~'A'..'Z'~
- chữ cái thường: ~'a'..'z'~
- chữ số: ~'0'..'9'~
Xâu mật khẩu phải thỏa mãn các điều kiện:
- Có ít nhất ~a~ ký tự chữ cái hoa,
- Có ít nhất ~b~ ký tự chữ cái thường,
- Có ít nhất ~c~ ký tự chữ số,
- Không có hai ký tự liên tiếp giống nhau.
Yêu cầu
Với ~n, a, b, c~ cho trước, hãy tìm:
- Mật khẩu hợp lệ có thứ tự từ điển nhỏ nhất,
- Mật khẩu hợp lệ có thứ tự từ điển lớn nhất.
So sánh từ điển theo thứ tự ký tự ASCII chuẩn: ~'0' < '1' < \dots < '9' < 'A' < \dots < 'Z' < 'a' < \dots < 'z'~.
Dữ liệu
Một dòng chứa bốn số nguyên ~n, a, b, c~ với:
- ~a + b + c \le n~
- ~1 \le n \le 100~
Kết quả
In ra 2 dòng:
- Dòng 1: mật khẩu hợp lệ có thứ tự từ điển nhỏ nhất.
- Dòng 2: mật khẩu hợp lệ có thứ tự từ điển lớn nhất.
Ví dụ
Ví dụ 1
Input
8 2 5 1
Output
0ABababa
zyzyzZY9
Giải thích
Ví dụ 1
- Xâu ~0ABababa~ có độ dài ~8~, gồm ~1~ chữ số (~0~), ~2~ chữ hoa (~A~, ~B~), ~6~ chữ thường (đủ ít nhất ~5~) và không có hai ký tự kề nhau giống nhau, đồng thời là xâu hợp lệ nhỏ nhất theo từ điển.
- Xâu ~zyzyzZY9~ cũng hợp lệ và là xâu lớn nhất theo từ điển.
Ràng buộc và chấm điểm
Ràng buộc
~1 \le n \le 100~, ~a+b+c \le n~.
Bình luận
Solution bài này: https://ideone.com/oae7gX
Với xâu có thứ tự từ điển nhỏ nhất, ta chỉ cần sử dụng nhiều số nhất có thể, sau đó là giữ nguyên số lượng chữ in hoa và chữ in thường. Vì mật khẩu có đúng n kí tự, vậy nên khi a + b + c < n, ta hãy thêm n - a - b - c kí tự vào c, để số lượng chữ số là nhiều nhất. Mấu chốt của bài toán là không có 2 kí tự kề nhau giống nhau, vì vậy ta chỉ cần đặt số và chữ xen kẽ (là "0101..." và "ABAB...") là có thể tạo ra xâu theo yêu cầu đề bài. Tương tự với xâu có thứ tự từ điển lớn nhất, ta chỉ cần làm ngược lại với xâu nhỏ nhất.
Bài này ta có thể sử dụng một mảng lưu trữ 2 số 0 và 1 dưới dạng char. Thay vì if(i % 2 == 0) str += '0', ta có thể cộng một phát ngon luôn như sau: str += numberarray[i%2]; Tức là mảng numberarray chứa {'0', '1'} nên chỉ cần lấy i%2 và chạy i từ 0, ta đã có được một xâu như mong muốn thay vì kiểm tra i % 2 == 0. Sau đó là tương tự với capsarray = {'A', 'B'} và chararray = {'a', 'b'}, cũng như xâu có thứ tự từ điển lớn nhất.