Hướng dẫn giải của [VTT Q4 Contest 11] Bài 2: Khởi tạo mật khẩu [PWGEN]
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.
Hướng dẫn giải
Cần dựng xâu độ dài ~n~ có ít nhất ~a~ chữ hoa, ~b~ chữ thường, ~c~ chữ số, không có hai ký tự liền nhau giống nhau, nhỏ nhất và lớn nhất theo thứ tự từ điển (thứ tự ASCII: chữ số < chữ hoa < chữ thường).
Sub 1: ~a = n~
Xâu chỉ gồm chữ hoa. Xâu nhỏ nhất là ~ABAB\dots~, xâu lớn nhất là ~ZYZY\dots~ (xen kẽ hai ký tự để không trùng nhau). Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: ~b = n~
Tương tự với chữ thường: ~abab\dots~ và ~zyzy\dots~. Sub này cũng xử lý luôn trường hợp ~a = n~. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 3: ~c = n~
Xâu chỉ gồm chữ số: ~0101\dots~ và ~9898\dots~. Sub này cũng xử lý hai trường hợp trước. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 4: Tham lam từng vị trí — ~O(62 \cdot n)~
Dựng xâu từ trái sang phải. Ở mỗi vị trí, thử các ký tự theo thứ tự tăng dần (với xâu nhỏ nhất) hoặc giảm dần (với xâu lớn nhất), chọn ký tự đầu tiên thỏa hai điều kiện: khác ký tự đứng trước, và sau khi chọn thì số vị trí còn lại vẫn đủ cho tổng số ký tự còn thiếu (~\max(0, a') + \max(0, b') + \max(0, c')~). Điều kiện "đủ chỗ" cũng là điều kiện đủ để hoàn thành, vì mỗi loại ký tự có ít nhất 10 ký tự khác nhau nên luôn chọn được một ký tự khác ký tự đứng trước; các vị trí thừa thì điền tự do. Đáp án đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc ~n, a, b, c~; nếu ~a = n~ gọi sub1, ~b = n~ gọi sub2, ~c = n~ gọi sub3, còn lại gọi sub4. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, a, b, c;
// Sinh xâu xen kẽ hai ký tự p, q (dùng cho các subtask một loại ký tự)
string alt(char p, char q) {
string s;
for (int i = 0; i < n; i++) s += (i % 2 == 0 ? p : q);
return s;
}
// Sub 1: a = n — toàn chữ in hoa
void sub1() { cout << alt('A', 'B') << "\n" << alt('Z', 'Y') << "\n"; }
// Sub 2: b = n (hoặc a = n) — toàn chữ thường / in hoa
void sub2() {
if (a == n) { sub1(); return; }
cout << alt('a', 'b') << "\n" << alt('z', 'y') << "\n";
}
// Sub 3: c = n (hoặc a = n, b = n) — xâu chỉ gồm một loại ký tự
void sub3() {
if (a == n || b == n) { sub2(); return; }
cout << alt('0', '1') << "\n" << alt('9', '8') << "\n";
}
int cls(char ch) { return isupper(ch) ? 0 : islower(ch) ? 1 : 2; }
// Sub 4: tham lam từng vị trí. Thứ tự ký tự: chữ số < in hoa < thường.
// Chọn ký tự tốt nhất sao cho phần còn lại vẫn đủ chỗ cho số ký tự còn thiếu.
string build(bool smallest) {
string chars;
for (char ch = '0'; ch <= '9'; ch++) chars += ch;
for (char ch = 'A'; ch <= 'Z'; ch++) chars += ch;
for (char ch = 'a'; ch <= 'z'; ch++) chars += ch;
if (!smallest) reverse(chars.begin(), chars.end());
int need[3] = {a, b, c};
string s;
for (int i = 0; i < n; i++) {
for (char ch : chars) {
if (i > 0 && s[i - 1] == ch) continue;
int k = cls(ch);
int nd[3] = {need[0], need[1], need[2]};
if (nd[k] > 0) nd[k]--;
// còn n-i-1 vị trí; lớp nào còn thiếu thì luôn chọn được ký tự khác ký tự trước
if (nd[0] + nd[1] + nd[2] <= n - i - 1) {
s += ch;
need[0] = nd[0]; need[1] = nd[1]; need[2] = nd[2];
break;
}
}
}
return s;
}
void sub4() { cout << build(true) << "\n" << build(false) << "\n"; }
int main() {
freopen("PWGEN.INP", "r", stdin);
freopen("PWGEN.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> a >> b >> c;
if (a == n) sub1();
else if (b == n) sub2();
else if (c == n) sub3();
else sub4();
}
Bình luận