ABC042_B - Iroha và chuỗi ký tự
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
include<stdio.h>
include<string.h>
include<ctype.h>
include<stdlib.h>
int ss(const voida, const voidb) { charx= (char)a; chary=(char)b; char xy[10000], yx[10000]; strcpy(xy,x); strcat(xy,y); strcpy(yx,y); strcat(yx,x); return strcmp(xy,yx); } int main() { int n; scanf("%d",&n); int l; scanf("%d",&l); char a[n][10000]; for(int i=0;i<n;i++) { scanf("%s",a[i]); } qsort(a,n,sizeof(a[0]),ss); for(int i=0;i<n;i++) { printf("%s",a[i]); }
}