Đề bài

Cho một bảng số hình vuông kích thước \( N \times N \), ban đầu được điền các giá trị từ 1 đến \( N^2 \) lần lượt theo hàng: ô đầu tiên là 1, tiếp theo là 2 ở cột kế bên, và cứ như vậy cho đến khi dòng đầy thì xuống dòng mới. Ví dụ với \( N = 4 \), bảng sẽ có dạng:

1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16

Có hai thao tác được phép thực hiện trên bảng:

• Dịch chuyển hàng: Dịch tất cả các phần tử trong một hàng sang phải một vị trí, phần tử cuối cùng quay về đầu hàng.
• Dịch chuyển cột: Dịch tất cả các phần tử trong một cột xuống dưới một vị trí, phần tử cuối cùng quay về đầu cột.

Nhiệm vụ là di chuyển một số \( X \) đến vị trí đích \( (R, C) \) (hàng R, cột C) bằng cách lặp lại các bước sau:

1. Nếu \( X \) chưa nằm ở cột \( C \), dịch chuyển hàng chứa \( X \) sang phải cho đến khi \( X \) vào đúng cột.
2. Nếu \( X \) chưa nằm ở hàng \( R \), dịch chuyển cột chứa \( X \) xuống dưới cho đến khi \( X \) vào đúng hàng.

Yêu cầu: Với \( K \) truy vấn độc lập, mỗi truy vấn gồm ba số \( X, R, C \), hãy tính số thao tác tối thiểu cần thực hiện để đưa \( X \) đến vị trí \( (R, C) \). Các truy vấn được xử lý tuần tự, và bảng thay đổi sau mỗi truy vấn.

Phân tích

Trước tiên, ta xác định tọa độ ban đầu của số \( X \):

• Hàng: \( \left\lceil \frac{X}{N} \right\rceil \), hay \( (X - 1) / N + 1 \)
• Cột: \( ((X - 1) \% N) + 1 \)

Khi thực hiện dịch chuyển hàng hoặc cột, toàn bộ dữ liệu trong hàng hoặc cột đó bị dịch vòng. Do đó, thay vì mô phỏng toàn bộ bảng (tốn thời gian), ta chỉ cần theo dõi vị trí hiện tại của từng số.

Với mỗi truy vấn:

1. Tính số lần dịch hàng cần thiết để đưa \( X \) vào cột \( C \).
2. Sau khi dịch hàng, cập nhật lại cột của tất cả các số đang cùng hàng với \( X \) (do ảnh hưởng lan truyền).
3. Tính số lần dịch cột cần thiết để đưa \( X \) vào hàng \( R \).
4. Cập nhật lại hàng của các số đang cùng cột với \( X \) sau khi dịch cột.

Tổng số thao tác là tổng số lần dịch hàng và dịch cột.

Triển khai bằng C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    // Lưu tọa độ hiện tại của từng số X
    vector<pair<int, int>> pos(k + 1);

    // Đọc các truy vấn và tính tọa độ ban đầu
    for (int i = 1; i <= k; ++i) {
        int x, r_target, c_target;
        cin >> x >> r_target >> c_target;

        // Tính tọa độ khởi tạo của x
        int row = (x - 1) / n + 1;
        int col = (x - 1) % n + 1;
        pos[i] = {row, col};

        // Số bước dịch chuyển cột cần thiết
        int move_col = 0;
        if (col != c_target) {
            if (col < c_target) {
                move_col = c_target - col;
            } else {
                move_col = n - col + c_target;
            }
        }

        // Cập nhật các số khác cùng hàng do dịch cột
        for (int j = i + 1; j <= k; ++j) {
            if (pos[j].first == row) {
                pos[j].second += move_col;
                if (pos[j].second > n) {
                    pos[j].second -= n;
                }
            }
        }

        // Số bước dịch chuyển hàng cần thiết
        int move_row = 0;
        if (pos[i].first != r_target) {
            if (pos[i].first < r_target) {
                move_row = r_target - pos[i].first;
            } else {
                move_row = n - pos[i].first + r_target;
            }
        }

        // Cập nhật các số khác cùng cột do dịch hàng
        for (int j = i + 1; j <= k; ++j) {
            if (pos[j].second == c_target) {
                pos[j].first += move_row;
                if (pos[j].first > n) {
                    pos[j].first -= n;
                }
            }
        }

        cout << move_col + move_row << '\n';
    }

    return 0;
}

Chương trình sử dụng mảng cặp tọa độ để theo dõi vị trí hiện tại của từng số cần xử lý. Mỗi truy vấn được xử lý tuần tự, đồng thời cập nhật ảnh hưởng của thao tác lên các truy vấn còn lại.