Căn phòng bí mật ở núi Rushmore
Đề bài
Mô tả
Có lẽ bạn đã nghe nói về tác phẩm điêu khắc đá ngoạn mục khắc chân dung bốn tổng thống nổi tiếng của Hoa Kỳ ở núi Rushmore. Tuy nhiên, rất ít người biết rằng công trình này chứa một căn phòng bí mật. Nghe như tình tiết trong một bộ phim Hollywood, nhưng căn phòng đó có thật. Nó nằm phía sau đầu của Abraham Lincoln và được thiết kế làm Phòng Lưu trữ (Hall of Records) để cất giữ các tài liệu và hiện vật lịch sử quan trọng của Hoa Kỳ. Các nhà sử học khẳng định việc xây dựng căn phòng bị dừng lại năm 1939 và căn phòng dang dở được để nguyên cho tới cuối thập niên 1990, nhưng đó không phải là toàn bộ sự thật.
Năm 1982, nhà khảo cổ học nổi tiếng S. Dakota Jones đã bí mật đến thăm công trình và phát hiện ra rằng căn phòng thực ra đã được hoàn thành, nhưng điều này được giữ kín. Thấy đáng ngờ, sau một hồi tìm tòi, bà phát hiện một hầm cất giấu bên trong có vài tài liệu. Đáng tiếc là các tài liệu này không có nghĩa gì cả, toàn là những chữ vô nghĩa. Bà nghi ngờ chúng được viết bằng mật mã nhưng dù cố gắng thế nào cũng không giải mã được.
Đầu tuần này, khi đến vùng này để theo dõi kỳ thi ACM-ICPC World Finals, tiến sĩ Jones cuối cùng đã tìm ra chìa khóa để giải mã các tài liệu, tại Connolly Hall của SDSM&T. Bà tìm thấy một tài liệu chứa danh sách các phép dịch chữ cái. Có chữ cái có nhiều hơn một phép dịch, có chữ cái không có phép dịch nào. Bằng cách áp dụng lặp lại một số phép dịch này lên từng chữ cái riêng lẻ trong các tài liệu vô nghĩa, bà có thể giải mã chúng thành các văn kiện lịch sử của Hoa Kỳ như Tuyên ngôn Độc lập hay Hiến pháp. Bà cần bạn giúp.
Cho các phép dịch chữ cái có thể dùng và một danh sách các cặp gồm từ gốc và từ đã giải mã. Nhiệm vụ của bạn là kiểm tra xem hai từ trong mỗi cặp có khớp nhau hay không. Hai từ khớp nhau nếu chúng có cùng độ dài và mỗi chữ cái của từ thứ nhất có thể biến thành chữ cái ở vị trí tương ứng của từ thứ hai bằng cách dùng các phép dịch có sẵn không hoặc nhiều lần.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên () và (), trong đó là số phép dịch chữ cái và là số cặp từ.
Mỗi dòng trong dòng tiếp theo chứa hai chữ cái khác nhau và cách nhau bởi dấu cách, cho biết chữ cái có thể được dịch thành chữ cái . Mỗi cặp có thứ tự xuất hiện nhiều nhất một lần.
Tiếp theo là dòng, mỗi dòng chứa một cặp từ cần kiểm tra, cách nhau bởi dấu cách.
Các phép dịch và các từ chỉ dùng chữ cái thường từ a đến z, và mỗi từ có ít nhất và nhiều nhất chữ cái.
Dữ liệu ra
Với mỗi cặp từ, in ra yes nếu hai từ khớp nhau, ngược lại in ra no, mỗi kết quả trên một dòng.
Ràng buộc
- , .
- Mỗi phép dịch gồm hai chữ cái thường khác nhau; mỗi cặp có thứ tự xuất hiện nhiều nhất một lần.
- Mỗi từ gồm từ đến chữ cái thường; hai từ trong một cặp có thể có độ dài khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 9 5 c t i r k p o c r o t e t f u h w p we we can the work people it of out the |
yes no no yes yes |
we khớp chính nó (dùng phép dịch). can/the: chữ a không có phép dịch nào nên không thành h được. work/people: khác độ dài. it/of: i r o và t f. out/the: o c t, u h, t e. |
| 3 3 a c b a a b aaa abc abc aaa acm bcm |
yes no yes |
aaa/abc: a giữ nguyên, a b, a c. abc/aaa: chữ c không dịch được thành a. acm/bcm: a b, hai chữ còn lại giữ nguyên. |
Bình luận