trang chủ / bài tập / hidemsg

Thông điệp

Đề bài

Mô tả

Trong hội trại năm nay, trường của Alice tổ chức một trò chơi đi tìm thông điệp. Theo bản đồ hướng dẫn của Ban tổ chức, các bạn học sinh sẽ tìm đến 3 địa điểm. Tại mỗi địa điểm, các bạn nhận được một phong bì chứa một tấm thiệp. Trên thiệp ghi một xâu ký tự gồm các chữ cái in thường, và cả 3 xâu đều có cùng độ dài n.

Gọi xâu trong phong bì thứ nhất là X, xâu trong phong bì thứ hai là Y và xâu trong phong bì thứ ba là Z. Thông điệp mà các bạn học sinh cần tìm là 3 xâu A,B và C được giấu trong 3 xâu X,Y,Z theo quy tắc sau:

  • Xâu X có dạng *A*B*;
  • Xâu Y có dạng *C*A*;
  • Xâu Z có dạng *B*C*.

Trong đó, dấu * đại diện cho một xâu bất kỳ, có thể là xâu rỗng. Các xâu A,B và C hoàn toàn có thể là xâu rỗng.

Ví dụ: Nếu có thông điệp A= ab, B= cd, C= ef thì:

  • X có thể là oabgcdpo (chứa ab là A, rồi đến cd là B);
  • Y có thể là hefhabro (chứa ef là C, rồi đến ab là A);
  • Z có thể là kcdjefgh (chứa cd là B, rồi đến ef là C).

Yêu cầu: Cho trước ba xâu X,Y và Z. Hãy tìm 3 xâu A,B và C thỏa mãn điều kiện giấu thông điệp sao cho tổng độ dài của cả 3 xâu (|A|+|B|+|C|) là lớn nhất có thể.

Dữ liệu vào

  • Dòng đầu tiên ghi số nguyên n (n≥2);
  • Dòng thứ hai chứa xâu X;
  • Dòng thứ ba chứa xâu Y;
  • Dòng thứ tư chứa xâu Z.

(Dữ liệu đảm bảo tất cả các xâu đều có độ dài đúng bằng n và chỉ gồm các chữ cái latin in thường).

Dữ liệu ra

  • Ghi ra một số nguyên duy nhất là tổng độ dài lớn nhất của 3 xâu A,B và C tìm được.

Ràng buộc

  • Có 20% số test tương ứng với 20% số điểm của bài thỏa mãn: n≤200.
  • 80% số test còn lại tương ứng với 80% số điểm của bài thỏa mãn: n≤2000.

Ví dụ

Input Output Giải thích
3
abc
cde
dea		 2 Phương án tối ưu là chọn A= "" , B="" và C= "de". Tổng độ dài là 0+0+2=2.
Kiểm tra tính hợp lệ:
X= "abc" chứa A rồi tới B (hai xâu rỗng được coi là xuất hiện ở mọi vị trí);
Y= "cde" chứa C= "de" rồi tới A= "";
Z= "dea" chứa B= "" rồi tới C= "de".
4
agtb
icea
tbhc		 4 Phương án tối ưu là chọn A= "a", B= "tb" và C= "c". Tổng độ dài là 1+2+1=4.
Kiểm tra tính hợp lệ:
X= "agtb" chứa "a" là A rồi tới "tb" là B;
Y= "icea" chứa "c" là C rồi tới "a" là A;
Z= "tbhc" chứa "tb" là B rồi tới "c" là C.

Bình luận

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0