QOJ.ac

QOJ

Límite de tiempo: 3 s Límite de memoria: 512 MB Puntuación total: 100 Dificultad: [mostrar] Interactivo

#194. Mật khẩu

Estadísticas

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".

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.