trang chủ / đề bài / icpcwf09_k

Văn phạm thay thế hậu tố

Đề bài

Mô tả

Là lập trình viên, hẳn bạn đã nghe về biểu thức chính quy và văn phạm phi ngữ cảnh. Đó là những cách phong phú để sinh ra các tập xâu trên một bảng chữ cái nhỏ (còn gọi là một ngôn ngữ hình thức). Còn có những cách khác, ít phổ biến hơn, để sinh ra ngôn ngữ, chẳng hạn văn phạm kề cây, văn phạm cảm ngữ cảnh và văn phạm không hạn chế. Bài toán này dùng một cách mới để sinh ra ngôn ngữ: văn phạm thay thế hậu tố.

Một văn phạm thay thế hậu tố gồm một xâu bắt đầu S và một tập các luật thay thế hậu tố. Mỗi luật có dạng X⇒Y, trong đó X và Y là hai xâu có cùng độ dài, gồm các ký tự chữ cái và chữ số. Luật này có nghĩa là nếu hậu tố (tức là các ký tự ở cuối bên phải) của xâu hiện tại là X thì bạn có thể thay hậu tố đó bằng Y. Các luật có thể được áp dụng bao nhiêu lần tùy ý.

Ví dụ, giả sử có 4 luật A ⇒ B, AB ⇒ BA, AA ⇒ CC và CC ⇒ BB. Khi đó bạn có thể biến xâu AA thành BB bằng ba lần áp dụng luật: AA ⇒ AB (dùng luật A ⇒ B), rồi AB ⇒ BA (dùng luật AB ⇒ BA), và cuối cùng BA ⇒ BB (lại dùng luật A ⇒ B). Nhưng bạn cũng có thể biến đổi nhanh hơn, chỉ với 2 lần áp dụng luật: AA ⇒ CC rồi CC ⇒ BB.

Hãy viết chương trình nhận một văn phạm thay thế hậu tố và một xâu T, xác định xem xâu bắt đầu S của văn phạm có thể biến đổi thành xâu T hay không. Nếu có thể, chương trình còn phải tìm số lần áp dụng luật ít nhất để thực hiện việc biến đổi đó.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai xâu S và T có cùng độ dài, gồm các ký tự chữ cái và chữ số (mỗi xâu dài từ 1 đến 20 ký tự, cách nhau bởi khoảng trắng), và một số nguyên NR là số luật. Mỗi dòng trong NR dòng tiếp theo chứa hai xâu X và Y có cùng độ dài, gồm các ký tự chữ cái và chữ số (mỗi xâu dài từ 1 đến 20 ký tự, cách nhau bởi khoảng trắng), cho biết X⇒Y là một luật của văn phạm. Mọi xâu đều phân biệt chữ hoa và chữ thường.

Sau bộ test cuối cùng là một dòng chứa một dấu chấm (.).

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ 1) và số lần áp dụng luật ít nhất cần để biến S thành T. Nếu không thể biến đổi được, in No solution. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 1≤|S|=|T|≤20, 0≤NR≤100.
  • 1≤|X|=|Y|≤20 với mọi luật (luật có thể dài hơn S).
  • Các xâu chỉ gồm chữ cái A-Z, a-z và chữ số 0-9.
  • Mỗi file có không quá 200 bộ test và tổng các giá trị NR trong một file không quá 1000.

Ví dụ

Input Output Giải thích
AA BB 4
A B
AB BA
AA CC
CC BB
A B 3
A C
B C
c B
.
Case 1: 2
Case 2: No solution
Bộ test 1 là ví dụ trong đề: AA ⇒ CC ⇒ BB. Bộ test 2: từ A chỉ đi được tới C, còn luật c ⇒ B dùng chữ c thường, không áp dụng được cho C.
000 111 3
0 1
01 10
011 100
ab ab 0
xY xy 2
y Y
xxY xxy
.
Case 1: 7
Case 2: 0
Case 3: No solution
Bộ test 1: các luật đếm nhị phân, 000 ⇒ 001 ⇒ 010 ⇒ 011 ⇒ 100 ⇒ 101 ⇒ 110 ⇒ 111. Bộ test 2: S=T, không cần áp dụng luật nào. Bộ test 3: luật y ⇒ Y không áp dụng được cho xY, còn luật xxY ⇒ xxy dài hơn xâu.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0