SXTRON - Sắp xếp trộn
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

       Để sắp xếp tăng dần một mảng A gồm n phần tử a1, a2,..., an, thuật toán sắp xếp trộn (MergeSort) áp dụng chia đôi mảng A thành hai mảng B và C, sắp xếp B, C và sau đó trộn B và C cho ra mảng A tăng dần. Ví dụ minh họa phương pháp trộn:

          - Mảng B gồm 4 phần tử b1, b2, b3, b4 đã sắp tăng dần:  1 2 4 6

          - Mảng C gồm 4 phần tử c1, c2, c3, c4 đã sắp tăng dần:  3 5 8 9

      Nếu trộn hai mảng trên theo dãy thứ tự trộn b1, b2, c1, b3, c2, b4, c3, cthì có được mảng sắp là 1 2 3 4 5 6 8 9.

      Cho một mảng B gồm n phần tử và mảng C gồm m phần tử. Hãy in ra dãy thứ tự trộn sao cho nếu áp dụng dãy thứ tự trộn trên thì mảng kết quả được sắp xếp tăng dần.

Dữ liệu nhập:

- Dòng đầu tiên là hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 20) là số phần tử của mảng B và mảng C.

- Dòng thứ 2 gồm n số nguyên b1, b2,..., bn (1 ≤ bi ≤ 100), mỗi số cách nhau một khoảng trắng.

- Dòng thứ 3 gồm m số nguyên c1, c2,..., cam (1 ≤ ci ≤ 100), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất:

- Là dãy thứ tự trộn, mỗi phần tử cách nhau một khoảng trắng (xem thêm ví dụ để hiểu cách xuất). Nếu có nhiều dãy thứ tự trộn, chỉ cần in ra một dãy bất kỳ.

Ví dụ

  • input
    4 4
    1 2 4 6
    3 5 8 9
    output
    b1 b2 c1 b3 c2 b4 c3 c4
Back to Top