Trò chơi ô số

Tý đang tham gia một trò chơi ô số, trò chơi như sau: Cho dãy số A gồm M x N số nguyên a₁, a₂,.., a_M.N. Người chơi lần lượt lấy các phần tử của dãy A rồi đặt vào các ô của hình chữ nhật kích thước M x N, sao cho giá trị các ô của hình chữ nhật không giảm theo hình zigzac:

 Yêu cầu: Các bạn hãy giúp Tý xác định hình chữ nhật sau khi đã đặt được hết các ô trong dãy.
Dữ liệu vào từ tệp văn bản TROCHOI.INP gồm:

• Dòng thứ nhất ghi số hai số nguyên dương M và N.
• Dòng tiếp theo gồm M x N số nguyên là các phần tử của dãy A.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.
Kết quả ghi ra tệp văn bản TROCHOI.OUT gồm M dòng, mỗi dòng gồm N số là giá trị của các ô trong hình chữ nhật sau khi thực hiện theo yêu cầu.
Ví dụ:

Giới hạn:

• Có 50% số test ứng với 50% số điểm thỏa mãn M = 1; N <= 1000
• Có 25% số test ứng với 25% số điểm thỏa mãn MxN <= 10³
• Có 25% số test ứng với 25% số điểm thỏa mãn MxN <= 10⁵.

Ý tưởng - Phân tích:
Chuyển các chỉ số bắt đầu từ 0.
Nếu không viết zigzac thì ô (x, y) trong bảng sẽ chứa giá trị A[x*n+y] (sau khi đã sắp xếp).
Hàng x = 0, 2, 4,…các số viết từ trái sang phải tăng dần.
Hàng x = 1, 3, 5,…các số viết từ trái sang phải giảm dần.

Thuật toán:

• Nhập m, n;
• Nhập dãy A[0..m.n-l];
• Sắp xếp dãy A tăng dần;
• Với mỗi x chạy từ 0 đến m-1:

* Nếu x chẵn thì
+ Với mỗi y chạy từ 0 đến n-1:
+ Viết A[x*n+y];
* Ngược lại (x lẻ):
+ Với mỗi y chạy lùi từ n-1 về 0:
+ Viết A[x*n+y];

Code C++

 

#include <bits/stdc++.h>
using namespace std;
const int x = 1E5 + 15 ;
int m, n, a[x];
int main ()
{
    freopen("TROCHOI.INP", "r", stdin);
    freopen("TROCHOI.OUT", "w", stdout);
    cin.tie(NULL) -> sync_with_stdio(false);
    int i, j ;
    cin>>m>>n;
        for(i = 0 ; i < m*n; i++)
             cin>>a[i];
    sort(a, a + m * n);
    for (i = 0; i < m; i++)
{
    if (i % 2 ==0)
       for (j = 0; j < n; j++)
           cout<<a[i * n + j ]<<" ";
else
       for (j = n-1 ; j >=0 ; j--)
           cout<<a[i * n + j ] <<" ";
}
return 0;
}