Gameshow "Ai là triệu phú"
Đề bài
Taii tham gia một trò chơi hách não. Để bắt đầu anh ta phải chọn được chính xác ô cửa bắt đầu của mình.
Để chọn chính xác ô cửa bắt đầu, trọng tài phát cho mỗi người một mảnh giấy trong đó có ghi mật mã chính là số của ô cửa mà anh ta phải bắt đầu. Tuy nhiên, có vẻ ngay câu hỏi đầu của trò chơi khá khó với Taii do anh ta rất lú lẫn. Taii đã chọn quyền trợ giúp của người thân.
Bạn hãy giúp Taii vượt qua câu hỏi đầu tiên này để tiến tới các câu hỏi khác nhé <3. Nếu bạn giải ra được, mật mã của mảnh giấy chính là điểm xuất phát của bạn.
Luật lệ như sau: Bạn chỉ có thể chọn ra một số chữ cái của mật mã ghi trong mảnh giấy và ghép chúng lại, đó chính là số của ô cửa mà anh ta bắt đầu (Tuyệt đối không được đảo vị trí các chữ). Mật mã là một trong các dãy: ZERO, ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE.
Tuy nhiên, trong số các tờ giấy mà Taii nhận được có 1 tờ giấy mà bạn không thể tìm ra mật mã được. Và đó cũng chính là kết thúc của bạn, tức là ô cửa ra về!
Dữ liệu vào: Một dòng duy nhất: Mật mã trong mảnh giấy là một xâu kí tự $S$, $|S| \le 10^6$.
Dữ liệu ra: Nếu không tìm ra mật mã thì in ra "CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!"
NOTE: Nếu có nhiều hơn một mật mã thì in ô cửa có số nhỏ nhất.
Subtask:
- 60% số test đầu tiên có $|S| \le 10^4$.
- 40% số test còn lại không có giới hạn gì thêm.
KJNKJDHSHDSDTSNJSDWJOKJSHKDSKPWTWOFSDFCHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!Lờ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 chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạ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 CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngXét lần lượt từ ZERO đến NINE
Như trường hợp bài này, đề bài định nghĩa ta sẽ chọn ra một số chữ cái trong xâu ban đầu và không được đảo vị trí các chữ cái, nghĩa là thằng nào được chọn trước thì trong xâu ban đầu nó cũng sẽ đứng trước thằng được chọn sau, hay nói rõ hơn là ta chỉ đi từ đầu đến cuối và chọn ra chứ không được đi lùi lại, cứ đi tới thôi. Và cần kiểm tra xem có thể chọn ra được các chữ cái tiếng Anh của các số từ 0 đến 9 hay không? Nếu không thể thì sẽ kết luận chia buồn hẹn năm sau gì gì đó 🤪 còn nếu chọn được thì ta sẽ ưu tiên chọn sao cho các chữ cái được chọn là số nhỏ nhất (trong các số từ 0 đến 9) và in ra từ tiếng Anh của số đó ra.
Đọc đến đây là ta hiểu rằng ta sẽ đi xét lần lượt từ tiếng Anh của các số từ bé nhất trở lên, tức là từ 0 trở lên, để nếu tìm thấy trường hợp thoả mãn thì ta ngay lập tức dừng lại và in ra kết quả luôn, không cần phải xét tiếp từ tiếng Anh của các số tiếp theo. Vì ta đang đi xét từ số nhỏ đến số lớn, ngay lúc nào thoả thì đó đảm bảo là số nhỏ nhất đúng như yêu cầu của đề bài rồi. Còn trường hợp xấu nhất là khi xét đủ 10 số từ 0 đến 9 mà vẫn không tìm thấy thì lúc này ta kết luận chia buồn.
Đơn giản là vậy thôi, nhưng cách cài đặt nếu không biết sẽ code dài dòng phức tạp lắm. Dưới đây mình sẽ hướng dẫn cho các bạn cách code cho đơn giản.
Ví dụ 1: chọn được T (vị trí 12), rồi W (vị trí 18), rồi O (vị trí 20) → ghép thành TWO. Trong xâu không hề có chữ Z (nên không có ZERO), có O, N nhưng không có E (nên không có ONE), vì vậy số nhỏ nhất ghép được là TWO.
Tìm 1 mật mãKiểm tra "ZERO" có nằm trong xâu không?
Giờ nói chi tiết cách thức xử lý khi tìm 1 chuỗi con cụ thể nào đó, ví dụ chuỗi con cần tìm là "ZERO" và tìm xem có nằm trong chuỗi gốc ban đầu không? Chuỗi con ZERO này trong chuỗi gốc không nhất thiết các ký tự nằm liên tiếp nhau mà nó có thể rời rạc cách xa nhau, miễn là đúng theo nguyên tắc vị trí của nó: đầu tiên sẽ có ký tự 'Z', sau đó đến ký tự 'E', rồi ký tự 'R' và sau cùng là ký tự 'O'. Nếu gặp đủ 4 ký tự theo đúng thứ tự như vậy trong chuỗi gốc ban đầu thì ngay lập tức kết luận tìm thấy và in nó ra; nếu đến cuối cùng mà không tìm thấy thì ta sẽ xét tìm sang chuỗi con tiếp theo là "ONE", không thấy lại xét tiếp sang "TWO" và cứ thế quy trình lặp lại đến "NINE" rồi mà vẫn không thấy thì kết luận chia buồn 🤪.
Để tìm "ZERO" thì rất đơn giản, chỉ cần duyệt chuỗi đầu vào:
- Tìm thấy ký tự 'Z' đầu tiên thì tăng biến đếm lên 1;
- tiếp tục duyệt, thấy ký tự 'E' thì tăng biến đếm lên 1;
- tiếp tục duyệt, thấy ký tự 'R' thì tăng biến đếm lên 1;
- tiếp tục duyệt, thấy ký tự 'O' thì tăng biến đếm lên 1 nữa.
Cứ mỗi lần biến đếm được tăng lên 1 thì ta kiểm tra: nếu biến đếm là 4 (tức là bằng độ dài chuỗi "ZERO") thì nghĩa là chuỗi "ZERO" đã xuất hiện đủ trong chuỗi ban đầu theo thứ tự, lúc này ta có thể dừng việc tìm kiếm và kết luận. Còn nếu xét hết chuỗi ban đầu rồi mà biến đếm vẫn chưa bằng độ dài chuỗi con đang tìm thì nghĩa là chuỗi con đó không tồn tại, ta xét qua chuỗi con tiếp theo ("ONE") và lặp lại quy trình như trên.
a có 10 phần tử: a[0] = "ZERO", a[1] = "ONE", … , a[9] = "NINE". Với $i$ lần lượt từ 0 đến 9: khởi tạo idx = 0 là vị trí ký tự đang cần tìm của a[i]. Duyệt từng ký tự s[j], nếu s[j] == a[i][idx] thì idx++ để lần sau tìm ký tự kế tiếp của a[i]. Mỗi lần khớp thì kiểm tra idx đã bằng độ dài a[i] chưa, bằng rồi nghĩa là a[i] đã được tìm thấy.Em nhập xâu $S$ (chữ in hoa) rồi bấm Tiếp để xem từng bước dò tìm 10 mật mã:
Cách 1Dùng biến cờ res và mẹo gán i = 10
Ta lưu index $i$ của chuỗi con tìm thấy đầu tiên vào biến res rồi kết thúc cả 2 vòng lặp, sau cùng in ra a[res]. Ban đầu ta nên khởi tạo res = -1 để sau cùng kiểm tra nếu res vẫn là $-1$ thì in ra câu chia buồn. Biến res đóng vai trò như cờ hiệu, bởi làm gì có index nào là $-1$ đúng không? Còn nếu khác $-1$ nghĩa là ta đã tìm ra được chuỗi con.
Source code các bạn tham khảo để nhìn thấy rõ với tất cả những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
string a[] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
string s;
getline(cin, s);
int res = -1;
for(int i = 0; i < 10; ++i){
int idx = 0;
for(int j = 0; j < (int)s.length(); ++j){
if(s[j] == a[i][idx]){
idx++;
if(idx == (int)a[i].length()){
res = i;
i = 10;
break;
}
}
}
}
if(res == -1){
cout << "CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!";
}
else{
cout << a[res];
}
return 0;
}a = ["ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"]
s = input().strip()
res = -1
for i in range(10):
idx = 0
for ch in s:
if ch == a[i][idx]:
idx += 1
if idx == len(a[i]):
res = i
break
if res != -1:
break
if res == -1:
print("CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!")
else:
print(a[res])if(idx == (int)a[i].length()): mình lưu res = i, sau đó cập nhật i = 10 rồi mới break. Nếu ta chỉ lưu res = i xong rồi break thì câu lệnh break chỉ giúp ta thoát ra khỏi vòng lặp gần nhất đang chứa nó là vòng for j thôi, còn vòng for i thì vẫn chạy tiếp. Mẹo ở đây: gán i = 10 thì khi thoát khỏi vòng for j, vòng for i làm bước ++i (lúc này $i$ đang là 10 thì tăng lên thành 11) rồi kiểm tra điều kiện i < 10, không thoả nên tự kết thúc vòng lặp for i luôn. Sau cùng ra bên ngoài ta kiểm tra biến res và kết luận.Bản Python không gán lại được biến của vòng for như vậy, nên sau vòng lặp trong mình kiểm tra if res != -1: break để thoát luôn vòng ngoài.
Cách 2In ngay và return 0
Thì thực ra là do mình quen code kiểu sau cùng mới đi kiểm tra kết luận, chứ ta có thể ngay lập tức in ra kết luận luôn và return 0; kết thúc chương trình tại đó. Cuối hàm main ta để dòng in câu chia buồn: nếu chương trình vẫn còn chạy được xuống dưới cùng đó, tức là nó không bị kết thúc sớm, tức là không tìm thấy bất kỳ chuỗi con nào trong 10 chuỗi con, thì lúc này ta in ra câu chia buồn.
Cách 2 – in ngay và return 0
#include <bits/stdc++.h>
using namespace std;
int main(){
string a[] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
string s;
getline(cin, s);
for(int i = 0; i < 10; ++i){
int idx = 0;
for(int j = 0; j < (int)s.length(); ++j){
if(s[j] == a[i][idx]){
idx++;
if(idx == (int)a[i].length()){
cout << a[i];
return 0;
}
}
}
}
cout << "CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!";
return 0;
}import sys
a = ["ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"]
s = input().strip()
for word in a:
idx = 0
for ch in s:
if ch == word[idx]:
idx += 1
if idx == len(word):
print(word)
sys.exit()
print("CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!")Đánh giá độ phức tạp
- Không gian: $O(1)$ vì mảng chuỗi 10 phần tử thì cũng chỉ là số nhỏ cố định không đáng kể (không tính xâu đầu vào).
- Thời gian: trường hợp xấu nhất là khi không tìm thấy bất kỳ chuỗi con nào, lúc này là $O(10 \cdot N)$ với $N$ là độ dài chuỗi đầu vào.
Độ dài chuỗi tối đa $10^6$ nên trường hợp xấu nhất số lần lặp cũng chỉ là $10 \cdot 10^6 = 10^7$, thoả nhỏ hơn ngưỡng giới hạn 1 giây là $(3 \text{ đến } 5) \cdot 10^7$ hay cao lắm là $10^8$, nên yên tâm sẽ không sợ bị TLE nhé.
Cách 3Tối ưu thêm bằng mảng đếm 26 chữ cái
Thực ra nếu muốn tối ưu hơn về thời gian thì vẫn có cách để trong trường hợp xấu nhất sẽ không phải lặp đủ $10 \cdot N$. Tuy nhiên nó phải code dài thêm một chút, vì thế với bài này khi độ dài chuỗi tối đa cũng chỉ $10^6$ thì là mình, mình sẽ chọn cách ngắn gọn đơn giản như ở trên thôi. Nhưng nếu giả sử độ dài chuỗi đầu vào tối đa có thể lên đến $10^7$ hay cao hơn nữa như cỡ $5 \cdot 10^7$ thì cách ở trên có thể bị TLE. Lúc này ta phải tìm giải pháp tốt hơn để trường hợp xấu nhất (không tồn tại chuỗi con nào) vẫn nhanh chóng kết luận được.
Bước 1: lọc nhanh bằng số lần xuất hiện
Ý tưởng là ta sử dụng 2 mảng đánh dấu cntS, cntA, mỗi mảng có 26 phần tử để thống kê số lần xuất hiện của 26 chữ cái từ A đến Z trong chuỗi đầu vào $s$ và trong chuỗi con a[i]. Mảng đếm của chuỗi đầu vào thì ta chỉ thống kê 1 lần, còn mảng cntA của chuỗi con thì mỗi lần xét chuỗi con mới phải thống kê lại.
Khi duyệt từng ký tự a[i][k] của chuỗi con, ta tăng cntA của ký tự đó và đối chiếu với cntS: nếu số lần xuất hiện bên cntS bé hơn bên cntA thì có thể ngay lập tức kết luận không thể tìm thấy chuỗi con a[i] trong $s$, xét tiếp qua chuỗi con tiếp theo mà khỏi cần phải duyệt qua toàn bộ chuỗi $s$ như cách làm trước rồi mới biết là không tồn tại.
| a[i] | Số lần cần / số lần có trong s | Kết luận |
|---|---|---|
| ZERO | Z: cần 1, có 0, E: cần 1, có 0, R: cần 1, có 0, O: cần 1, có 1 | Thiếu Z, E, R → bỏ qua ngay |
| ONE | O: cần 1, có 1, N: cần 1, có 2, E: cần 1, có 0 | Thiếu E → bỏ qua ngay |
| TWO | T: cần 1, có 1, W: cần 1, có 2, O: cần 1, có 1 | Đủ → duyệt s |
| THREE | T: cần 1, có 1, H: cần 1, có 3, R: cần 1, có 0, E: cần 2, có 0 | Thiếu R, E → bỏ qua ngay |
| FOUR | F: cần 1, có 0, O: cần 1, có 1, U: cần 1, có 0, R: cần 1, có 0 | Thiếu F, U, R → bỏ qua ngay |
| FIVE | F: cần 1, có 0, I: cần 1, có 0, V: cần 1, có 0, E: cần 1, có 0 | Thiếu F, I, V, E → bỏ qua ngay |
| SIX | S: cần 1, có 6, I: cần 1, có 0, X: cần 1, có 0 | Thiếu I, X → bỏ qua ngay |
| SEVEN | S: cần 1, có 6, E: cần 2, có 0, V: cần 1, có 0, N: cần 1, có 2 | Thiếu E, V → bỏ qua ngay |
| EIGHT | E: cần 1, có 0, I: cần 1, có 0, G: cần 1, có 0, H: cần 1, có 3, T: cần 1, có 1 | Thiếu E, I, G → bỏ qua ngay |
| NINE | N: cần 2, có 2, I: cần 1, có 0, E: cần 1, có 0 | Thiếu I, E → bỏ qua ngay |
Với ví dụ 1, chỉ cần đếm 1 lần là loại ngay ZERO và ONE mà không phải duyệt xâu $s$; tới TWO thì đủ chữ nên mới đi duyệt $s$ và tìm thấy.
Bước 2: duyệt s nhưng dừng sớm khi chắc chắn thua
Còn nếu mọi ký tự của a[i] đều thoả cntS >= cntA thì lúc này ta duyệt vào chuỗi $s$ và đi tìm như cách trước. Nhưng ta có thể tiếp tục tận dụng mảng đánh dấu để phát hiện ra khi nào nó thực sự không thể tồn tại mà không cần xét đến tận cùng chuỗi $s$:
- Mỗi lần xét ký tự
s[j], nếu trùng vớia[i][idx]thì ngoài việc tăngidx, ta giảm 1 ở cả 2 mảngcntS,cntAtại ký tự đó (chữ này đã dùng xong, không còn cần nữa). - Nếu
s[j]kháca[i][idx]thì chỉ giảmcntScủa ký tựs[j]đi 1 (không giảm bêncntA). - Rồi kiểm tra: nếu
cntScủa ký tựs[j]giờ nhỏ hơncntAcủa nó, nghĩa là phần còn lại của $s$ không còn đủ chữ đó để ghép, chắc chắna[i]không tồn tại trong $s$ → dừng, xét qua chuỗi con mới, hoặc nếu đang là chuỗi con cuối cùng thì kết luận chia buồn.
Source code các bạn tham khảo để nhìn thấy rõ với tất cả những gì mình đã phân tích ở trên:
Cách 3 – lọc bằng mảng đếm, dừng sớm
#include <bits/stdc++.h>
using namespace std;
int main(){
string a[] = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
string s;
getline(cin, s);
int cntS[26];
int temp_cntS[26] = {0};
int index;
for(int i = 0; i < (int)s.length(); ++i){
index = s[i] - 'A';
temp_cntS[index]++;
}
for(int i = 0; i < 10; ++i){
for(int k = 0; k < 26; ++k){
cntS[k] = temp_cntS[k];
}
int cntA[26] = {0};
bool check = true;
for(int k = 0; k < (int)a[i].length(); ++k){
index = a[i][k] - 'A';
cntA[index]++;
if(cntS[index] < cntA[index]){
check = false;
break;
}
}
if(check == true){
int idx = 0;
for(int j = 0; j < (int)s.length(); ++j){
index = s[j] - 'A';
if(s[j] == a[i][idx]){
idx++;
if(idx == (int)a[i].length()){
cout << a[i];
return 0;
}
cntA[index]--;
}
cntS[index]--;
if(cntS[index] < cntA[index]){
break;
}
}
}
}
cout << "CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!";
return 0;
}a = ["ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"]
s = input().strip()
cntS = [0] * 26
temp_cntS = [0] * 26
for ch in s:
index = ord(ch) - ord('A')
temp_cntS[index] += 1
found = False
for i in range(10):
cntS = temp_cntS.copy()
cntA = [0] * 26
check = True
for ch in a[i]:
index = ord(ch) - ord('A')
cntA[index] += 1
if cntS[index] < cntA[index]:
check = False
break
if check:
idx = 0
for ch in s:
index = ord(ch) - ord('A')
if ch == a[i][idx]:
idx += 1
if idx == len(a[i]):
print(a[i])
found = True
break
cntA[index] -= 1
cntS[index] -= 1
if cntS[index] < cntA[index]:
break
if found:
break
if not found:
print("CHIA BUON, PHAI VE ROI, HEN NAM SAU NHE!!")cntS[index]-- để so sánh với cntA[index] (ở khúc cuối cùng trong code ở trên) nên mảng cntS đã bị thay đổi khi xét từng chuỗi con a[i]; nếu phải tiếp tục xét qua chuỗi con tiếp theo thì cntS không còn chính xác nữa. Vì thế ban đầu ta tạo mảng temp_cntS để thống kê số lần xuất hiện các ký tự trong chuỗi $s$, rồi mỗi lần xét chuỗi con a[i] thì gán dữ liệu mảng temp_cntS sang mảng cntS để như reset lại mảng cntS về giá trị ban đầu.Với cách làm trước, trường hợp xấu nhất phải 10 lần duyệt đi duyệt lại chuỗi $s$ (mấy chuỗi con thì độ dài chẳng bao nhiêu nên không đáng kể). Còn với cách làm này ta luôn chỉ mất 1 lần duyệt qua toàn bộ chuỗi $s$ để tạo mảng đánh dấu; các chuỗi con hay các mảng đánh dấu thì độ dài cũng không đáng kể. Thực ra cũng có thể phải duyệt thêm $s$ đấy, nhưng không cần phải luôn duyệt đến tận cùng mà có thể dừng sớm. Đây là điểm để ghi nhận nó tốt hơn cách làm trước, nhưng đánh đổi lại là phải code dài và phức tạp thêm. Nên như mình đã nói: nếu độ dài chuỗi đầu vào $< 10^7$ thì cứ dùng cách đầu tiên cho đơn giản, chừng nào $\ge 10^7$ lúc đó mình mới phải nặn óc suy nghĩ ra những hướng làm tốt hơn như kiểu thế này 🤪
getline và giả sử xâu chỉ gồm chữ in hoa như đề.
Nhận xét
Đăng nhận xét