Thay thế
Đề bài
Mô tả
Alice vừa phát triển một ngôn ngữ hoạt động trên các ký tự là các số tự nhiên nhỏ hơn . Cô có một tập gồm luật biến đổi, mỗi luật có dạng (với ; ): thay một ký tự trong dãy bằng dãy . Mỗi luật có thể được áp dụng nhiều lần, và quá trình chỉ dừng khi thu được một dãy nhị phân (chỉ gồm các số và ). Ví dụ, với các luật:
cô có thể biến đổi dãy như sau: .
Bob có một tập gồm dãy nhị phân. Hãy giúp Alice: xuất phát từ một số duy nhất, tìm dãy nhị phân ngắn nhất có thể tạo ra mà không có đoạn con liên tiếp nào trùng với một dãy trong tập của Bob.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên (; ).
- Mỗi dòng trong dòng tiếp theo mô tả một luật dạng (, , ). Tổng các của mọi luật không vượt quá . Có thể có số không có luật nào; khi đó từ không tạo được dãy nhị phân nào.
- Mỗi dòng trong dòng tiếp theo mô tả một dãy nhị phân của Bob dạng (, ). Tổng các của mọi dãy không vượt quá .
Dữ liệu ra
In ra dòng, dòng thứ chứa độ dài của dãy nhị phân ngắn nhất mà Alice có thể tạo ra khi xuất phát từ số , sao cho không có đoạn con liên tiếp nào của nó trùng với một dãy của Bob. Nếu không có dãy hữu hạn nào thỏa mãn, in ra . Dữ liệu đảm bảo nếu tồn tại dãy hữu hạn thỏa mãn thì tồn tại một dãy như vậy có độ dài không vượt quá .
Ràng buộc
- ,
- , , , tổng của các luật
- , tổng độ dài các dãy của Bob
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 5 3 3 2 2 3 3 3 2 4 6 2 3 0 0 1 4 1 1 6 3 4 0 4 3 0 0 0 3 1 1 1 4 0 1 0 1 |
3 0 1 0 3 |
Ví dụ của đề gốc, dãy của Bob là 000, 111, 0101. Từ được ; từ được ; từ được . Mọi dãy hữu hạn tạo từ đều chứa một dãy của Bob (ví dụ cho 0011101, chứa 111); số không có luật nào. |
| 4 4 2 2 1 0 2 2 3 3 3 2 1 1 3 2 2 1 1 0 2 1 1 |
0 0 |
Ví dụ bổ sung, tính bằng lời giải mẫu. Mọi dãy tạo từ hoặc đều chứa ký tự hoặc hai ký tự liền nhau. |
Bình luận