trang chủ / đề bài / icpcwf04_d

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 p có độ dài n. Người gửi chọn một số nguyên m≥2n và các số nguyên s,t,i,j với 0≤s,t,i,j<m và i<j. Khi đó m là độ dài của xâu mã c được truyền đi. Ban đầu c gồm m ô trống, đánh số từ 0 đến m−1. Chữ cái đầu tiên của p được đặt vào ô s của c. Chữ cái thứ k (k≥2) được đặt bằng cách bỏ qua i ô trống của c nằm sau chữ cái thứ k−1, quay vòng về đầu c 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, s=1, i=6 và m=15, các chữ cái được đặt vào c 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ừ ô t trở đi (kể cả ô t, quay vòng về đầu c 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 j ô trống giữa hai chữ cái liên tiếp. Ví dụ, với t=0 và j=8, bản sao thứ hai của p được ghi như sau (bắt đầu ở ô 2, ô trống đầu tiên tính từ t=0):

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 đượ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 s và i 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ứ k có dạng "Code k: " rồi đến kết quả.

Ràng buộc

  • Mỗi xâu mã có độ dài từ 2 đến 40.
  • 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 1).
  • Mỗi file có không quá 50 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ụ s=0, i=1, t=1, j=2 cho AB, chữ B của bản sao thứ hai bỏ qua ô trống duy nhất 3 hai lần rồi đặt vào chính ô 3; s=2, i=1, t=3, j=2 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.

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