Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Cho hai từ x, y và một dãy hữu hạn các từ (w1, w2, ..., wk).

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ừ w1, w2, ..., wk. 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ừ w1, w2, ..., wk, 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

Được gửi lên bởi:Duc
Ngày:2008-03-20
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Polish OI 3

hide comments
2015-04-18 02:28:25 Phạm Huỳnh Nhật


Last edit: 2015-04-18 02:28:42
2014-11-12 03:18:36 The Mastermind


Last edit: 2014-11-12 03:20:18
2014-06-25 06:07:04 Anh Duc Le
BFS :))
2012-07-17 05:04:09 1212
Cho em hỏi là liệu với test
1
1 a
4 aaa
1 a
thì kết quả là Nie hay là 2 ạ? (tức là từ a có thể sử dụng dc nhiều lần hay ko? )
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.