Mật Khẩu (PASSW
Đề bài
PASSW – MẬT KHẨU – HSG 16.17 · Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Trong chiến dịch truy bắt nhóm tội phạm công nghệ cao, tổ công tác thu được Laptop của nhóm tội phạm, tuy nhiên laptop bị đặt mật khẩu. Nhóm trinh sát báo về mật khẩu nằm trong tin nhắn là một xâu kí tự gồm chữ cái thường, hoa, dấu cách và chữ số, trong đó có ít nhất $k$ kí tự là số.
Tổ trinh sát cho biết sau khi loại bỏ đi một số kí tự trong xâu $S$ sao cho còn lại đúng $k$ kí tự số theo đúng thứ tự của nó tạo thành số lớn nhất trong các kí tự số của xâu $S$ và số lớn nhất này có tính chất đối xứng thì đó là mật khẩu mở Laptop.
Yêu cầu: Em hãy lập trình giúp cho tổ công tác giải mã mật khẩu để mở laptop. Biết rằng một số được gọi là đối xứng nếu khi ta đảo ngược số đó thì bằng chính nó. Ví dụ 1221, 121 là đối xứng.
Dữ liệu nhập:
- Dòng thứ nhất chứa số nguyên $k$ $(1 \le k \le 255)$.
- Dòng thứ hai chứa xâu $s$ có độ dài không quá 255.
Kết quả:
- Dòng 1 in ra $k$ kí tự số được giữ lại tạo thành số lớn nhất.
- Dòng 2 ghi
YESnếu tìm được mật khẩu, còn không ghiNO.
Ràng buộc: Xâu kí tự có độ dài không quá 255.
5
abc abc 123abc2acb1da00 cc32100
NO5
0abc abc0 123abc2acb1da cc12321
YESLời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên VinhDinhCoderLộ trình lời giải, bấm vào từng phần để nhảy tới:
Phân tíchĐề bài thực chất hỏi gì?
Đọc đề ta thấy rằng cái sau cùng quan tâm chính là chuỗi kết quả sao cho chuỗi này chỉ chứa các ký tự số (không có chữ cái gì hết nhé) và có đủ $K$ ký tự theo đúng thứ tự xuất hiện của nó, tức là ký tự nào xuất hiện trước trong chuỗi input thì nó phải nằm trước, và hãy cố gắng để chuỗi số đó là số lớn nhất có thể, đó chính là mật khẩu. Rồi thì in mật khẩu đó ra và kiểm tra tính đối xứng của nó.
Việc kiểm tra tính đối xứng quá đơn giản, chỉ cần tạo ra chuỗi mới là chuỗi đảo ngược của chuỗi kết quả, sau đó so sánh 2 chuỗi với nhau: bằng nhau thì đối xứng, không bằng nhau thì không đối xứng. Cái khó là làm sao tạo ra được chuỗi kết quả có đúng $K$ chữ số theo đúng thứ tự sao cho nó là số lớn nhất trong tất cả các trường hợp hợp lệ.
Bước 1Tiền xử lý: chỉ giữ lại ký tự số – đừng xóa!
Chuỗi đầu vào đang lộn xộn cả chữ cái và chữ số, mà ta chỉ cần làm việc với những ký tự chữ số thôi. Một giải pháp là dựa trên chính chuỗi ban đầu, gặp ký tự nào không phải ký tự số thì ta xóa ký tự đó đi.
Nếu làm theo cách xóa như vậy thì độ phức tạp sẽ rất lớn. Vì bản chất khi xóa một phần tử trong mảng (chuỗi bản chất là mảng 1 chiều các ký tự) là các phần tử ở ngay sau vị trí xóa đồng loạt dời về phía trước 1 ô. Giả sử chuỗi có độ dài $N$ mà ta xóa ngay vị trí 0 thì $N - 1$ phần tử phía sau phải dời lên ⇒ thao tác xóa có độ phức tạp trường hợp xấu nhất là $O(N)$. Mà ta có thể phải xóa cả $N$ ký tự, như thế là $O(N^2)$.
Trong khi đó nếu muốn tối ưu hơn, ta chỉ cần tạo ra 1 chuỗi mới, duyệt từng ký tự trong chuỗi ban đầu, gặp ký tự số thì thêm nó vào chuỗi mới. Chỉ cần duyệt 1 lượt là ta có chuỗi chỉ chứa các ký tự số theo đúng thứ tự, độ phức tạp $O(N)$. Thậm chí việc xóa nếu không cẩn thận còn rất dễ bị sót: nếu xóa 2, 3 ký tự liên tiếp mà quên không giảm chỉ số sau mỗi lần xóa thì sẽ bị sót ký tự chưa xóa đấy nhé.
Cách 1Tham lam chọn từng chữ số trong cửa sổ [start, finish] – AC
Coi như giờ ta đã có chuỗi $s$ chỉ chứa các ký tự số. Như ví dụ đầu tiên thì $s$ = "1232100" với $L = 7$, $K = 5$: cần chọn ra 5 ký tự theo đúng thứ tự từ trái qua phải (giả sử đã chọn ký tự '3' thì tiếp theo chỉ còn được chọn trong '2', '1', '0', '0' chứ không được chọn các ký tự đứng trước '3' nữa), sao cho ghép lại thành số có 5 chữ số lớn nhất. Đáp án là "32100". Vậy các bạn hãy cố gắng nhìn ra xem tư tưởng chọn thế nào?
Tư tưởng tham lam
Ta sẽ dùng phương pháp tham lam (Greedy). Cho bạn nào không biết thì mình nói nhanh: tham lam nghĩa là ta cố gắng chọn ra cách tốt nhất trong tất cả các cách ở hiện tại rồi đi theo nó; nếu lại đứng trước nhiều lựa chọn nữa thì lại chọn cái tốt nhất trong số đó, tóm lại cứ tốt nhất mà triển nên gọi là tham lam. Nó chỉ là dạng tư tưởng thôi, không có công thức từng bước cụ thể như các thuật toán khác, còn để hiện thực được nó thì có thể cần đến những kỹ thuật bổ trợ khác. Tại sao bài này nhìn ra là tham lam? Đọc đề thấy rõ mùi rồi hehe: xử lý theo quy luật gì đó để sau cùng đáp án phải là lớn nhất/nhỏ nhất, đọc kiểu này phát thấy mùi tham lam ngay.
Phạm vi được chọn. Gọi res là chuỗi đáp án. Khi res chưa có gì và cần chọn ký tự đầu tiên với $K = 5$, thì tối đa chỉ được chọn từ vị trí 0 đến vị trí 2, tức là 3 ký tự đầu tiên. Vị trí cuối cùng có thể chọn là 2 để sau đó còn lại 4 ký tự (vị trí 3 đến 6) thì $K$ cũng còn lại 4 là vừa đủ. Chứ nếu chọn vị trí 3 thì chỉ còn 3 ký tự cho các lần sau trong khi $K$ còn 4, các bạn thấy nghịch lý chưa? Vậy lần chọn đầu tiên: start = 0 đến finish = L − K = 7 − 5 = 2.
Chọn ký tự nào? Để số có 5 chữ số lớn nhất thì từ trái qua từng ký tự phải càng lớn càng tốt, và mức độ ưu tiên quan trọng nhất là ký tự càng ở ngoài cùng bên trái. Ví dụ "20000" lớn hơn "19999": dù sau đó toàn chữ số 0 nhỏ nhất so với toàn chữ số 9 lớn nhất, nhưng ký tự đầu '2' > '1' nên vẫn lớn hơn.
[start, finish]; chọn ký tự số lớn nhất trong phạm vi đó. Nếu có nhiều hơn 1 ký tự lớn nhất thì ưu tiên chọn ký tự ở vị trí nhỏ nhất để dành các ký tự lớn còn lại cho các lần sau. Sau mỗi lần chọn: start = idxMax + 1, finish++, K--.Thử với các ví dụ
Ví dụ 1: $s$ = "1232100", $L = 7$, $K = 5$. Lần 1: phạm vi $[0, 2]$ gồm '1', '2', '3', chọn '3' tại vị trí 2 ⇒ res = "3". Lần 2: start = 3, finish = 3, start và finish trùng nhau nghĩa là chỉ có 1 ký tự được chọn, lấy luôn '2' ⇒ res = "32". Tiếp tục các lần 3, 4, 5 vẫn lấy đủ các ký tự tại vị trí 4, 5, 6 ⇒ res = "32100".
Trường hợp đặc biệt – kết thúc sớm. Nếu từ start đến cuối chuỗi còn đúng $K$ ký tự, tức là L − start == K, thì coi như phải chọn hết. Số ký tự từ start (tính luôn start) đến cuối chính là L − start: ví dụ $L = 10$, start = 0 thì còn 10 ký tự, start = 3 thì còn 7 ký tự (vị trí 3..9). Ở ví dụ 1, sau lần chọn đầu start = 3, $K = 4$, mà L − start = 7 − 3 = 4 bằng đúng $K$ ⇒ lấy hết "2100" luôn. Trường hợp này đúng với cả trường hợp đặc biệt nhất là $K = L$ ngay từ đầu: start = 0 thì L − start = K, chọn hết từ đầu, đâu cần mất công chọn gì đâu.
Ví dụ 2: sau tiền xử lý $s$ = "0012321", $L = 7$, $K = 5$. Lần 1: phạm vi $[0, 2]$ gồm '0', '0', '1', chọn '1' tại vị trí 2 ⇒ res = "1", $K = 4$. Lần 2: start = 3, L − start = 4 = K ⇒ trường hợp đặc biệt, lấy hết '2', '3', '2', '1' ⇒ res = "12321", đối xứng ⇒ YES.
Ví dụ có 2 chữ số lớn nhất bằng nhau: $s$ = "1882520", $L = 7$, $K = 5$:
| Lần | [start, finish] | str = 1882520 | Chọn |
|---|---|---|---|
| 1 | [0, 2] | 01182832455260 | 8 |
| 2 | [2, 3] | 01182832455260 | 8 |
| 3 | [3, 4] | 01182832455260 | 5 |
| 4 | [5, 6] | 01182832455260 | 20 – L − start = k → lấy hết |
⇒ res = "88520".
Hãy nhìn lại lần chọn đầu tiên: giữa 2 ký tự '8' tại vị trí 1 và 2, nếu các bạn chọn vị trí 2 thì sang lần tiếp theo trường hợp đặc biệt xảy ra, kết quả sẽ là "82520", rõ ràng nhỏ hơn "88520". Vậy nên phải lưu ý chọn ký tự lớn nhất ở vị trí nhỏ nhất nhé. Cứ thế số lần chọn tối đa sẽ là $K$.
Em nhập $k$ và xâu rồi bấm Tiếp để xem cửa sổ [start, finish] trượt dần và từng chữ số được chọn:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string s, int k){
string res = "";
int start = 0, finish = (int)s.length() - k;
while(k != 0){
if((int)s.length() - start == k){
res += s.substr(start);
break;
}
int idxMax = start;
for(int i = start + 1; i <= finish; ++i){
if(s[i] > s[idxMax]){
idxMax = i;
}
}
res.push_back(s[idxMax]);
start = idxMax + 1;
finish++;
k--;
}
return res;
}
int main() {
// freopen("passw.inp", "r", stdin);
// freopen("passw.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
string s, str;
getline(cin, s);
int k;
k = stoi(s);
getline(cin, s);
for(int i = 0; i < s.length(); ++i){
if(s[i] >= '0' && s[i] <= '9'){
str.push_back(s[i]);
}
}
string res = MaxNum(str, k);
cout << res << endl;
string rever_res = res;
reverse(rever_res.begin(), rever_res.end());
if(res == rever_res){
cout << "YES";
}
else{
cout << "NO";
}
return 0;
}import sys
def MaxNum(s: str, k: int) -> str:
res = ""
start = 0
finish = len(s) - k
while k != 0:
if len(s) - start == k:
res += s[start:]
break
idxMax = start
for i in range(start + 1, finish + 1):
if s[i] > s[idxMax]:
idxMax = i
res += s[idxMax]
start = idxMax + 1
finish += 1
k -= 1
return res
# Nếu đề yêu cầu file thì thay sys.stdin bằng open("passw.inp", "r")
lines = [line.rstrip("\r\n") for line in sys.stdin.readlines()]
k = int(lines[0])
s = lines[1]
digits = "".join(ch for ch in s if ch.isdigit())
res = MaxNum(digits, k)
print(res)
if res == res[::-1]:
print("YES")
else:
print("NO")freopen("passw.inp", ...) và freopen("passw.out", ...) theo đúng đề thi HSG. Khi nộp lên VinhDinhCoder (đọc từ bàn phím) mình để 2 dòng đó thành chú thích; nếu đề yêu cầu đọc/ghi file thì các bạn chỉ cần bỏ dấu // đi. Bản Python cũng vậy: thay sys.stdin bằng open("passw.inp") và ghi ra passw.out.Giải thích một số chỗ trong code ở trên:
- Thường thì mình rất ngán những bài cần đọc chuỗi mà trước đó có đọc số (số nguyên/số thực), vì rất dễ bị dư ký tự xuống dòng trong bộ nhớ đệm, ta phải xóa bộ nhớ đệm đi. Nên giải pháp an toàn mình hay làm là đọc hết dữ liệu dạng chuỗi (
getline), dữ liệu nào là số thì convert qua. Như bài này dòng đầu là $k$ thì mình đọc dạng chuỗi rồi dùng hàmstoi(có sẵn trong thư viện string của C++) đổi sang số. Tất nhiên cái này là mình cẩn thận thôi, các bạn cứ làm bình thường nếu chạy AC là được hihi. s.substr(a)là lấy chuỗi con của $s$ từ vị trí $a$ đến cuối. Ví dụ $s$ ="123456789"thìs.substr(4)="56789". Còns.substr(a, b)là lấy chuỗi con từ vị trí $a$ và lấy đủ $b$ ký tự, ví dụs.substr(3, 4)="4567"(các vị trí 3, 4, 5, 6). Hàm trả về chuỗi con mới, nênres += s.substr(start)là nối phần từstartđến cuối vào saures. Kiểustringcủa C++ hỗ trợ rất tiện, chứ chuỗi kiểu C thì để nối phải gọistrcat, cònsubstrthì phải tự cài đặt.reverse(rever_res.begin(), rever_res.end())nằm trong thư việnalgorithm(đã có trongbits/stdc++.h). Hàm nhận 2 iterator chỉ định đảo từ đâu đến đâu, và đảo trực tiếp trên biến chứ không trả về kết quả, nên ta phải tạo chuỗi mớirever_reschép từresrồi mới đảo, sau đó so sánh vớiresđể kết luận có đối xứng hay không.
Đánh giá độ phức tạp: không gian $O(N)$. Thời gian: $O(N)$ đọc và lọc chuỗi (giả sử chuỗi toàn ký tự số để $N$ thống nhất). Bước chọn lặp $K$ lần, phạm vi [start, finish] lớn nhất là ở lần đầu, khoảng $N - K$, nên tối đa $K \cdot (N - K)$ lần lặp. Đảo chuỗi $O(N)$. Với $K = N/2$ thì $N + N^2/4 + N$, theo quy tắc cộng và nhân Big-O kết luận trường hợp xấu nhất là $O(N^2)$.
Chuỗi tối đa 255 ký tự, $255^2 = 65.025$ lần lặp, ít hơn rất rất nhiều so với ngưỡng 1 giây $(3 \text{ đến } 5) \cdot 10^7$ hay cao lắm là $10^8$, nên chắc chắn không sợ TLE.
Thì mình cũng nói luôn là cách làm ở trên được xem là cách làm "tệ nhất" cho bài này nha các bạn hihi: chỉ cần gặp bài tương tự mà độ dài chuỗi từ $10^4$ trở lên thì $N^2$ đã chạm $10^8$, còn $10^5$ thành $10^{10}$, $10^6$ thành $10^{12}$ thì chắc chắn TLE. Nhưng nếu đang trong kỳ thi có tính thời gian thì mình cũng sẽ làm theo cách đơn giản nhất ở trên thôi để nhanh chóng giải quyết vấn đề, vì sau cùng vẫn chỉ cần AC thôi mà. Còn nào có thời gian thoải mái thì mới nghĩ đến cách tối ưu hơn.
Cách 2Ngăn xếp – O(N) (mình viết thêm)
Anh có thử thách các bạn bài Xóa chữ số trên LQDOJ (lqdoj.edu.vn/problem/delnum): cùng thể loại nhưng chuỗi dài tới $10^6$, nên cách trên chắc chắn bị TLE. Ở đây mình viết sẵn 1 cách $O(N)$ để các bạn tham khảo trước (bài giải chi tiết của bài đó anh sẽ đăng riêng): chọn $K$ chữ số ⇔ xóa del = L − K chữ số. Duyệt từng chữ số $c$: chừng nào còn lượt xóa và $c$ lớn hơn chữ số cuối cùng đang giữ thì bỏ chữ số cuối đó đi (đưa $c$ lên trước thì số lớn hơn), rồi giữ $c$ lại. Duyệt xong nếu còn dư lượt xóa thì cắt bớt phần đuôi cho đúng $K$ chữ số.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s, str, res;
int k;
getline(cin, s);
k = stoi(s);
getline(cin, s);
for(char c : s){
if(c >= '0' && c <= '9') str.push_back(c);
}
int del = (int)str.length() - k;
for(char c : str){
while(!res.empty() && del > 0 && c > res.back()){
res.pop_back();
del--;
}
res.push_back(c);
}
res.resize(k);
cout << res << endl;
string rev(res.rbegin(), res.rend());
cout << (res == rev ? "YES" : "NO");
return 0;
}import sys
lines = sys.stdin.read().split('\n')
k = int(lines[0])
s = lines[1] if len(lines) > 1 else ""
digits = [c for c in s if c.isdigit()]
dele = len(digits) - k
res = []
for c in digits:
while res and dele > 0 and c > res[-1]:
res.pop()
dele -= 1
res.append(c)
res = "".join(res[:k])
print(res)
print("YES" if res == res[::-1] else "NO")Mỗi chữ số được thêm vào res 1 lần và bị bỏ ra nhiều nhất 1 lần, nên tổng số bước của vòng while không quá $N$: cả thuật toán là $O(N)$.
Nhận xét
Đăng nhận xét