Nghi phạm mật khẩu
Đề bài
Mô tả
Bạn là thiên tài máy tính của tổ chức bí mật mang tên Sneaky Underground Smug Perpetrators of Evil Crimes and Thefts (SUSPECT). Mục tiêu của phi vụ tội ác mới nhất của SUSPECT là kẻ thù lớn nhất của họ, Câu lạc bộ Cảnh sát Thông minh Khó tả (ICPC), và mọi thứ đã sẵn sàng. Mọi thứ, trừ một điều nhỏ: mật khẩu bí mật của hệ thống máy tính chính của ICPC.
Mật khẩu chỉ gồm các chữ cái thường từ a đến z. Hơn nữa, qua nhiều lần quan sát lén lút, bạn đã xác định được độ dài của mật khẩu, cùng với một vài xâu con (có thể chồng lên nhau) của mật khẩu, nhưng bạn không biết chính xác chúng xuất hiện ở đâu trong mật khẩu.
Ví dụ, giả sử bạn biết mật khẩu dài ký tự và đã quan sát được các xâu con hello và world. Khi đó mật khẩu phải là helloworld hoặc worldhello.
Câu hỏi là những thông tin này có đủ để thu hẹp số mật khẩu có thể xuống một con số hợp lý hay không. Để trả lời, hãy viết chương trình xác định số mật khẩu có thể (tức là số xâu độ dài gồm các chữ cái thường chứa mọi xâu con đã biết) và, nếu có không quá mật khẩu, in ra tất cả chúng.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên và lần lượt là độ dài mật khẩu và số xâu con đã biết. Tiếp theo là dòng, mỗi dòng chứa một xâu con đã biết, gồm từ đến chữ cái thường a-z.
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ ) và Y suspects, trong đó là số mật khẩu có thể của bộ test đó (luôn viết suspects, kể cả khi ). Nếu số mật khẩu không quá , in tiếp tất cả các mật khẩu có thể theo thứ tự từ điển, mỗi mật khẩu trên một dòng. Làm theo đúng định dạng trong ví dụ.
Ràng buộc
- , .
- Mỗi xâu con đã biết gồm từ đến chữ cái thường; các xâu con có thể trùng nhau, có thể dài hơn .
- Dữ liệu đảm bảo số mật khẩu có thể của mỗi bộ test không vượt quá .
- Mỗi file có không quá bộ test và tổng các giá trị của các bộ test trong một file không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 2 hello world 10 0 4 1 icpc 0 0 |
Case 1: 2 suspects helloworld worldhello Case 2: 141167095653376 suspects Case 3: 1 suspects icpc |
Bộ test 1 là ví dụ trong đề. Bộ test 2: không có ràng buộc nào, có mật khẩu, nhiều hơn nên không in danh sách. Bộ test 3: chỉ có icpc. |
| 3 2 ab ba 3 3 ab ab b 2 1 abc 7 0 1 0 0 0 |
Case 1: 2 suspects aba bab Case 2: 52 suspects Case 3: 0 suspects Case 4: 8031810176 suspects Case 5: 26 suspects a b c d e f g h i j k l m n o p q r s t u v w x y z |
Bộ test 1: hai xâu con chồng lên nhau. Bộ test 2: xâu con ab xuất hiện hai lần trong danh sách, còn b nằm trong ab; mật khẩu có dạng ab? hoặc ?ab, tổng cộng . Bộ test 3: xâu con dài hơn mật khẩu nên không có mật khẩu nào. Bộ test 4: mật khẩu, vượt kiểu số nguyên bit. Bộ test 5: mật khẩu, không quá nên in hết. |
Bình luận