Bất an ở Praha
Đề bài
Mô tả
Praha là một thành phố nguy hiểm đối với những người thiết kế các lược đồ mật mã. Năm 2001, hai nhà nghiên cứu ở Praha công bố một lỗ hổng bảo mật trong giao thức mã hoá PGP nổi tiếng. Năm 2003, cũng tại Praha, người ta phát hiện một lỗ hổng trong các giao thức SSL/TLS (Secure Sockets Layer và Transport Layer Security). Tuy vậy, tiếng tăm "khó nhằn" của Praha với các giao thức mật mã không ngăn được nhà mật mã nghiệp dư bán thời gian kiêm người lập dị toàn thời gian Immanuel Kant-DeWitt (bạn bè gọi là "I. Kant-DeWitt") mang lược đồ mã hoá mới nhất của mình tới Praha. Lược đồ hoạt động như sau.
Cần truyền một thông điệp gốc có độ dài . Người gửi chọn một số nguyên và các số nguyên với và . Khi đó là độ dài của xâu mã được truyền đi. Ban đầu gồm ô trống, đánh số từ đến . Chữ cái đầu tiên của được đặt vào ô của . Chữ cái thứ () được đặt bằng cách bỏ qua ô trống của nằm sau chữ cái thứ , quay vòng về đầu khi cần (có thể quay vòng nhiều lần), rồi đặt vào ô trống tiếp theo. Các ô đã chứa chữ cái không được tính là ô trống. Ví dụ, với thông điệp PRAGUE, , và , các chữ cái được đặt vào như sau (dấu _ là ô trống):
array base=0 A P _ U _ _ _ _ R G _ _ E _ _
Bắt đầu từ ô trống đầu tiên tính từ ô trở đi (kể cả ô , quay vòng về đầu nếu cần), thông điệp gốc được ghi thêm một lần nữa, nhưng lần này bỏ qua ô trống giữa hai chữ cái liên tiếp. Ví dụ, với và , bản sao thứ hai của được ghi như sau (bắt đầu ở ô , ô trống đầu tiên tính từ ):
array base=0 A P P U R _ A U R G E G E _ _
Cuối cùng, mọi ô còn trống của được điền bằng các chữ cái chọn ngẫu nhiên:
array base=0 A P P U R A A U R G E G E W E
Kant-DeWitt tin rằng việc nhân đôi thông điệp, kết hợp với các chữ cái ngẫu nhiên, sẽ làm rối các phương pháp giải mã dựa trên tần suất chữ cái, và nếu không biết và thì không ai tìm ra được thông điệp gốc. Nhiệm vụ của bạn là chứng minh ông ta sai. Cho một số xâu mã (và không có thông tin nào khác), hãy xác định thông điệp dài nhất có thể đã được mã hoá thành mỗi xâu mã bằng phương pháp Kant-DeWitt.
Dữ liệu vào
Gồm nhiều xâu mã, mỗi xâu trên một dòng. Mỗi xâu chỉ gồm các chữ cái in hoa tiếng Anh, không có dấu cách ở đầu hay cuối dòng.
Sau xâu mã cuối cùng là một dòng chỉ chứa chữ cái X.
Dữ liệu ra
Với mỗi xâu mã, in ra xâu dài nhất có thể đã được mã hoá thành xâu mã đó. Nếu có nhiều hơn một xâu (khác nhau) cùng đạt độ dài lớn nhất, in ra "Codeword not unique". In theo đúng định dạng trong ví dụ: dòng thứ có dạng "Code : " rồi đến kết quả.
Ràng buộc
- Mỗi xâu mã có độ dài từ đến .
- Trong mỗi xâu mã có ít nhất một chữ cái xuất hiện ít nhất hai lần (luôn tồn tại thông điệp có độ dài ít nhất ).
- Mỗi file có không quá xâu mã.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| APPURAAURGEGEWE ABABABAB THEACMPROGRAMMINGCONTEST X |
Code 1: PRAGUE Code 2: Codeword not unique Code 3: Codeword not unique |
Xâu thứ nhất là ví dụ trong đề. |
| AA CBBDAEAAC AABB ABCA X |
Code 1: A Code 2: ABC Code 3: Codeword not unique Code 4: A |
Ví dụ tự thêm. Xâu AABB: cả AB và BA đều mã hoá được (ví dụ , , , cho AB, chữ B của bản sao thứ hai bỏ qua ô trống duy nhất hai lần rồi đặt vào chính ô ; , , , cho BA). Xâu ABCA: chỉ chữ A xuất hiện hai lần nên thông điệp dài nhất là A. |
https://oj.chuyentin.pro/problem/icpcwf04_d
Bình luận