VWORDS - Tương đương hóa hai từ

Giới hạn
  • Thời gian: 0.4s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho hai từ x, y và một dãy hữu hạn các từ (w 1 , w 2 , ..., w k ).

Phép toán p * q mang ý nghĩa là phép nối từ p với từ q, hay nói cách khác p * q là một từ mới tạo thành bằng cách viết từ q phía sau từ p. Ta cần kiểm tra xem hai từ x, y có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước không.

Ví dụ: Từ abba và ab có thể tương đương hóa bằng cách sử dụng các từ trong dãy: baaabad aa badccaa cc. Ta cần nối vào từ abba các từ: aa và badccaa, và nối vào từ ab các từ baaabad, cc và aa theo thứ tự. Trong cả hai trường hợp, ta sẽ thu được cùng một từ: abbaaabadccaa.

Yêu cầu

Cho biết từ x, từ y và dãy từ w 1 , w 2 , ..., w k . Cho biết từ x và y có thể tương đương hóa bằng cách sử dụng các từ trong dãy cho trước được hay không? Nếu có thể, hãy tìm số lượng nhỏ nhất phép toán * cần sử dụng.

Dữ liệu

  • Dòng đầu tiên chứa một số nguyên dương k ≤ 40.
  • Dòng thứ hai và dòng thứ ba mô tả từ x và y.
  • K dòng tiếp theo mô tả dãy từ w 1 , w 2 , ..., w k , mỗi từ trên một dòng.
  • Mô tả của mỗi từ chứa một số nguyên cho biết độ dài của từ, theo sau bởi khoảng trắng và một chuỗi thể hiện từ đó.
  • Mỗi từ chỉ bao gồm các chữ cái Latin in thường và có độ dài không vượt quá 2000.
  • Tổng độ dài các từ không vượt quá 5000.

Kết quả

  • Nếu không tồn tại lời giải, in ra 'NIE'.
  • Nếu tồn tại lời giải, in ra một số nguyên dương, là số lượng nhỏ nhất các phép toán * cần để tương đương hóa hai từ x và y.

Ví dụ 

Dữ liệu
4
4 abba
2 ab
7 baaabad
2 aa
7 badccaa
2 cc

Kết quả
5

Dữ liệu
4
1 a
2 ab
2 bb
2 ab
2 ba
2 aa

Kết quả
NIE

  • Người up: paulmcvn
  • Nguồn bài: Polish OI 3