trang chủ / đề bài / icpcwf17_i

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 m (1≤m≤500) và n (1≤n≤50), trong đó m là số phép dịch chữ cái và n là số cặp từ.

Mỗi dòng trong m dòng tiếp theo chứa hai chữ cái khác nhau a và b cách nhau bởi dấu cách, cho biết chữ cái a có thể được dịch thành chữ cái b. Mỗi cặp có thứ tự (a,b) xuất hiện nhiều nhất một lần.

Tiếp theo là n 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 1 và nhiều nhất 50 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

  • 1≤m≤500, 1≤n≤50.
  • 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ừ 1 đến 50 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 0 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

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