Chiến Lược Đoán Mã Tối Ưu

Buổi 63 — Interactive & Constructive Dynamic Programming
Points
90
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho danh sách gồm $N$ mật mã đôi một khác nhau, mỗi mật mã là một chuỗi độ dài $L$ gồm các chữ cái in hoa. Máy chấm chọn bí mật một mật mã $S$ trong danh sách $N$ mật mã đó.

Ở mỗi lượt đoán, bạn được chọn một mật mã $G$ bất kỳ trong danh sách $N$ mật mã đã cho. Máy chấm sẽ trả về cặp số $(B, C)$ theo luật Mastermind:

  • $B$ (Bulls): số vị trí $i$ mà $G[i] = S[i]$.
  • $C$ (Cows): số ký tự khớp ở vị trí khác nhau (trên phần ký tự còn lại sau khi đã bỏ qua các vị trí Bulls).

Nếu $B = L$, bạn đoán đúng $S$ và trò chơi kết thúc. Hãy tìm số lượt đoán ít nhất trong trường hợp xấu nhất để chắc chắn tìm ra $S$ với chiến lược thích nghi tối ưu.

Dữ liệu vào
  • Dòng đầu ghi hai số nguyên $N, L$ ($1 \le N \le 14$, $1 \le L \le 6$).
  • $N$ dòng tiếp theo, mỗi dòng là một chuỗi độ dài $L$ gồm các chữ cái in hoa A-Z.
Dữ liệu ra
  • Một số nguyên duy nhất là số lượt đoán tối thiểu trong trường hợp xấu nhất.
Ví dụ
Input Output
4 2
AA
AB
BA
BB
3
Giới hạn
  • $1 \le N \le 14$
  • $1 \le L \le 6$
Draft saved