Thi thử Duyên hải 2021 - Lần 2 - Bài 4 - CPU

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

DMA mới phát minh ra một loại vi xử lí hai nhân kiểu mới có thể thực hiện ~26~ chỉ thị khác nhau, kí hiệu bằng ~26~ chữ cái in hoa trong bảng chữ cái tiếng Anh. Trong mỗi xung nhịp, một nhân của vi xử lí có thể xử lí đúng một chỉ thị. Một chương trình sau khi được biên dịch sẽ gồm một chuỗi các chỉ thị cần được thực thi tuần tự. Vì là vi xử lí hai nhân, nên người ta có thể chạy hai chương trình cùng một lúc. Tuy nhiên, loại vi xử lí này có một nhược điểm là không thể thực hiện hai chỉ thị khác nhau trên hai nhân trong cùng một xung nhịp. Dĩ nhiên, vi xử lí sẽ tìm cách tối ưu để thực thi được cả hai chương trình trong số lượng xung nhịp ít nhất.

Ví dụ với ~2~ chương trình ABB và ABC, vi xử lí sẽ thực hiện đồng thời hai chỉ thị ~A~ trong xung nhịp thứ nhất, hai chỉ thị ~B~ trong xung nhịp thứ hai, chỉ thị ~B~ của chương trình thứ nhất trong xung nhịp thứ ba và chỉ thị ~C~ của chương trình thứ hai trong xung nhịp thứ tư. Như vậy, vi xử lí cần ~4~ xung nhịp để thực thi xong cả hai chương trình. Và đây là phương án tối ưu nhất.

An đã mua về ~n~ vi xử lí loại vừa nêu và hiện có ~2n~ chương trình cần thực thi. Hãy giúp cậu ấy phân ~2n~ chương trình này cho ~n~ máy chạy song song, mỗi máy chạy hai chương trình sao cho thời gian thực thi là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 10)~ là số lượng vi xử lí.

~2n~ dòng sau, mỗi dòng chứa từ ~1~ đến ~100~ kí tự in hoa trong bảng chữ cái tiếng Anh mô tả chuỗi chỉ thị của một chương trình.

Output

Ghi ra thời gian thực thi tối thiểu trên một dòng duy nhất.

Sample Input

2
ABB
BAB
CAB
ABC

Sample Output

4

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • 4
    SPyofgame   commented on April 30, 2021, 11:17 a.m. edit 3

    Em xin đóng góp bài giải cho bài này như sau