Tập xâu nhị phân
Đề bài
Mô tả
Cho là một tập các xâu. Ký hiệu là tập gồm xâu rỗng và mọi xâu thu được bằng cách ghép nối các xâu thuộc (mỗi xâu trong có thể được dùng nhiều lần).
Cho xâu . Với mỗi , hãy tìm số ký tự ít nhất cần xóa khỏi để xâu còn lại thuộc .
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên .
- dòng tiếp theo, mỗi dòng chứa một xâu gồm các ký tự '0' và '1'.
Dữ liệu ra
In ra dòng, dòng thứ chứa một số nguyên là số ký tự ít nhất cần xóa khỏi .
Ràng buộc
- .
- Tổng độ dài các xâu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 00110 110 |
0 1 |
00110 = 0 + 01 + 10 nên không cần xóa. Với 110, xóa một ký tự 1 được 10. |
| 3 1 0101 1100 |
1 0 1 |
Ví dụ bổ sung (không có trong đề gốc). 0101 = 01 + 01; với 1100, xóa ký tự 1 đầu tiên được 100 = 10 + 0. |
Bình luận