ABC042_B - Iroha và chuỗi ký tự

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Iroha có một tập hợp ~N~ chuỗi ~S_1, S_2, ..., S_n~. Độ dài của mỗi chuỗi là ~L~.

Cô ấy sẽ nối các chuỗi này lại theo 1 thứ tự nào đó để được một chuỗi dài hơn. Trong tất cả các cách nối chuỗi mà Iroha có thể nối, hãy tìm cách nối mà chuỗi kết quả có thứ tự từ điển nhỏ nhất.

Cụ thể, chuỗi ~s = s_1s_2...s_n~ có thứ tự từ điển nhỏ hơn chuỗi ~t = t_1t_2...t_m~ nếu 1 trong các điều kiện sau được đáp ứng:

  • Tồn tại chỉ số ~i\ (1 \le i \le min(n, m))~, sao cho ~s_j = t_j\ \forall{j} (1 \le j \lt i)~ và ~s_i \lt t_i~.
  • ~s_i = t_i\ \forall{i}\ (1 \le i \le min(n, m))~ và ~n \lt m~

Input

  • Dòng đầu tiên gồm 2 số ~N~ và ~L~
  • ~N~ dòng tiếp theo, dòng thứ ~i~ là chuỗi ~S_i~

Output

  • Kết quả của bài toán.

Sample

Input #1
3 3
dxx
axx
cxx

Output #1
axxcxxdxx

Hint

Thứ tự nối sẽ là: axx, cxx, dxx

Problem source: AtCoder Beginner Contest 042


Comments

Please read the guidelines before commenting.


There are no comments at the moment.