Tôi lại quên mật khẩu của mình nữa rồi! Tôi đang ngồi trước máy tính và gõ vào những mật khẩu sai. Tất cả những gì tôi nhớ là mật khẩu của mình chỉ gồm các chữ cái thường. May mắn thay, hệ thống đăng nhập phản hồi nhiều hơn là chỉ “sai mật khẩu”. Nó còn cho tôi biết độ dài tiền tố dài nhất của xâu tôi nhập vào xuất hiện như một dãy con (không nhất thiết liên tiếp) trong mật khẩu. Một cách hình thức, với mật khẩu $P = p_1 p_2 \dots p_N$ và xâu nhập vào $Q = q_1 q_2 \dots q_N$, câu trả lời của hệ thống đăng nhập là số $L$ lớn nhất sao cho tồn tại các chỉ số $1 \le k_1 < k_2 < \dots < k_L \le N$ thỏa mãn $q_i = p_{k_i}$ với mọi $1 \le i \le L$. Hệ thống cũng cho tôi biết $N$, độ dài mật khẩu của tôi, và $S$, nghĩa là mật khẩu của tôi chỉ sử dụng $S$ chữ cái đầu tiên trong bảng chữ cái. Ví dụ, $S = 4$ có nghĩa là mật khẩu của tôi chỉ chứa $\text{a}$, $\text{b}$, $\text{c}$ và $\text{d}$ (nhưng không nhất thiết chứa tất cả chúng).
Xin hãy giúp tôi khôi phục mật khẩu của mình!
Chi tiết cài đặt
Đây là bài toán tương tác. Bạn cần cài đặt hàm
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- Tham số: $N$ và $S$ như đã mô tả ở trên.
- Giá trị trả về: mật khẩu đúng.
Chương trình của bạn có thể gọi hàm
C: int query(char* str);
C++: int query(string str);
- Tham số: một xâu gồm từ $1$ đến $N$ chữ cái được chọn từ $S$ chữ cái đầu tiên trong bảng chữ cái.
- Giá trị trả về: một số nguyên nằm trong đoạn từ $0$ đến độ dài của
str, biểu thị câu trả lời của hệ thống đăng nhập cho truy vấn của bạn. - Để tránh lỗi biên dịch, bạn cần khai báo hàm này bằng đúng nguyên văn đoạn mã ở trên, ở bất kỳ đâu trong phạm vi toàn cục trước khi gọi nó.
- Bạn được gọi hàm này tối đa $50\,000$ lần cho mỗi test.
Chương trình của bạn có thể định nghĩa thêm các hàm phụ khác.
Trình chấm mẫu
Một trình chấm mẫu grader.{c,cpp} được cung cấp để bạn kiểm thử mã nguồn trên máy cá nhân. Trình chấm mẫu đọc dữ liệu vào từ tệp password.in theo định dạng:
- dòng $1$: $N$ $S$
- dòng $2$: mật khẩu
Bạn có thể biên dịch trình chấm cùng với lời giải của mình. Sau đó, bạn có thể chạy tệp thực thi thu được để kiểm thử chiến lược đoán mật khẩu với dữ liệu vào đã cho.
Nhiệm vụ con
Các test có thể được chấm theo nhóm. Theo thứ tự, các nhiệm vụ con như sau:
| Nhiệm vụ con | Tỷ lệ điểm | Ràng buộc dữ liệu vào |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; tất cả các chữ cái trong mật khẩu đều phân biệt |
| 2 | 20% | $2 \le N \le 100$ và $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ và $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
Ví dụ
Giả sử mật khẩu là $\text{aab}$. Trình chấm gọi guess(3, 2). Nhật ký lời gọi có thể như sau:
| Lời gọi | Giá trị trả về |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
Tại thời điểm này, guess(3, 2) cần trả về "aab".