J - Tấn Công Nitro Toluen

Mô tả bài toán: Cho một mảng số nguyên `a`. Đếm số cặp chỉ số `(i, j)` sao cho `a[i] XOR a[j] = GCD(a[i], a[j])`.

Ý tưởng giải pháp:

Đặt `X = a[i]` và `Y = a[j]`. Điều kiện là `X XOR Y = GCD(X, Y)`. Gọi `P = GCD(X, Y)`.

Ta biết rằng `P` phải là một ước của `X`. Từ đẳng thức `X XOR Y = P`, ta có thể suy ra `Y = X XOR P` (vì `A XOR B = C` kéo theo `A XOR C = B` và `B XOR C = A`).

Do đó, bài toán trở thành tìm cặp `(X, Y)` trong mảng sao cho `Y = X XOR P` và `P = GCD(X, Y)`. Thay `Y` vào điều kiện `P = GCD(X, Y)`, ta được `P = GCD(X, X XOR P)`.

Điều này có nghĩa là, với mỗi số `X` trong mảng, ta cần kiểm tra các ước `P` của `X`. Nếu `P` thỏa mãn `P = GCD(X, X XOR P)` và số `Y = X XOR P` tồn tại trong mảng, thì cặp `(X, Y)` là một cặp hợp lệ.

Để tối ưu, ta có thể duyệt qua tất cả các số `X` duy nhất trong mảng. Với mỗi `X`, ta tìm tất cả các ước `P` của nó. Sau đó, tính `Y = X XOR P`. Nếu `Y > X` (để tránh đếm trùng cặp và không đếm cặp `(X, X)` nếu không cần), và `P == GCD(X, Y)`, thì ta cộng `số lượng X * số lượng Y` vào tổng kết quả.

Độ phức tạp thời gian là `O(N * sqrt(max_val))` vì với mỗi số, ta tìm ước mất `sqrt(số đó)`. Sử dụng `std::map` để lưu tần suất xuất hiện của các số giúp xử lý các số trùng lặp hiệu quả.

#include <iostream>
#include <vector>
#include <numeric> // For std::gcd in C++17, otherwise implement gcd
#include <map>
#include <cmath> // For sqrt

// Hàm GCD (Ước chung lớn nhất)
long long calculate_gcd(long long num1, long long num2) {
    while (num2) {
        num1 %= num2;
        std::swap(num1, num2);
    }
    return num1;
}

void process_case() {
    int array_size;
    std::cin >> array_size;
    std::map<long long, int> frequency_map;
    for (int i = 0; i < array_size; ++i) {
        long long val;
        std::cin >> val;
        frequency_map[val]++;
    }

    long long total_pairs = 0;
    // Duyệt qua từng số duy nhất trong map
    for (auto const& entry : frequency_map) {
        long long current_num = entry.first;
        int current_num_count = entry.second;

        // Tìm các ước của current_num
        for (long long divisor = 1; divisor * divisor <= current_num; ++divisor) {
            if (current_num % divisor == 0) {
                // Ước thứ nhất: divisor
                long long xor_target1 = current_num ^ divisor;
                // Chỉ xét các cặp (X, Y) với Y > X để tránh trùng lặp
                if (xor_target1 > current_num && divisor == calculate_gcd(current_num, xor_target1)) {
                    if (frequency_map.count(xor_target1)) {
                        total_pairs += (long long)current_num_count * frequency_map[xor_target1];
                    }
                }

                // Ước thứ hai: current_num / divisor (nếu khác divisor)
                if (divisor * divisor != current_num) {
                    long long other_divisor = current_num / divisor;
                    long long xor_target2 = current_num ^ other_divisor;
                    if (xor_target2 > current_num && other_divisor == calculate_gcd(current_num, xor_target2)) {
                        if (frequency_map.count(xor_target2)) {
                            total_pairs += (long long)current_num_count * frequency_map[xor_target2];
                        }
                    }
                }
            }
        }
    }
    std::cout << total_pairs << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    // int test_cases = 1;
    // std::cin >> test_cases;
    // while (test_cases--) {
        process_case();
    // }
    return 0;
}

H - Cửa Sổ Được Sắp Xếp

Mô tả bài toán: Cho `n` khoảng giá trị `[l_i, r_i]`. Ta cần xây dựng một hoán vị `P` của các số từ `1` đến `n` sao cho với mỗi `i` từ `1` đến `n`, phần tử `P[i]` phải nằm trong khoảng `[l_i, r_i]` tương ứng. Nếu có thể, in ra bất kỳ hoán vị nào thỏa mãn; ngược lại, in `-1`.

Ý tưởng giải pháp:

Đây là một bài toán greedy điển hình. Ta muốn gán các số `1, 2, ..., n` vào các khoảng một cách hợp lý.

Các bước thực hiện:

1. Lưu trữ các khoảng dưới dạng `(l_i, r_i, original_index_i)` và sắp xếp chúng tăng dần theo giá trị `l_i`. Việc lưu trữ `original_index_i` là cần thiết để khôi phục vị trí của số trong hoán vị cuối cùng.
2. Sử dụng một cấu trúc dữ liệu ưu tiên (như `std::set` hoặc `std::priority_queue`) để lưu trữ các khoảng đã sẵn sàng để được gán số. Cấu trúc này sẽ ưu tiên các khoảng có `r_i` nhỏ nhất lên đầu.
3. Duyệt qua các số `current_value` từ `1` đến `n` (đây là các số sẽ được gán vào hoán vị):
   • Trong khi vẫn còn các khoảng chưa xử lý và `l_j` của khoảng tiếp theo `j` nhỏ hơn hoặc bằng `current_value`: thêm khoảng `j` vào cấu trúc dữ liệu ưu tiên.
   • Nếu cấu trúc dữ liệu ưu tiên trống rỗng, điều đó có nghĩa là không còn khoảng nào hợp lệ để gán `current_value` vào. Trả về `-1`.
   • Lấy khoảng `(earliest_r, _, original_idx)` từ đầu cấu trúc dữ liệu ưu tiên (khoảng có `r_i` nhỏ nhất).
   • Nếu `earliest_r < current_value`, có nghĩa là khoảng này không thể chứa `current_value` và tất cả các khoảng khác có `r_i` lớn hơn cũng sẽ không chứa được. Trả về `-1`.
   • Ngược lại, gán `ans[original_idx] = current_value` và loại bỏ khoảng này khỏi cấu trúc dữ liệu ưu tiên.
4. Sau khi duyệt xong tất cả các số từ `1` đến `n`, nếu không có lỗi, in ra hoán vị `ans`.

Chiến lược này hoạt động vì ta luôn cố gắng gán số nhỏ nhất `current_value` cho khoảng có `r_i` nhỏ nhất trong số các khoảng đang "sẵn sàng" (tức là `l_i <= current_value`). Điều này giúp "giải phóng" các khoảng có `r_i` lớn hơn cho các số lớn hơn sau này, tối đa hóa khả năng tìm được một giải pháp.

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
#include <set>       // To simulate a min-priority queue based on r

// Cấu trúc để lưu trữ khoảng và chỉ số gốc
struct Interval {
    int left, right, original_idx;

    // Toán tử so sánh cho std::sort (sắp xếp theo left)
    bool operator<(const Interval& other) const {
        return left < other.left;
    }
};

// Cấu trúc để sử dụng trong std::set, ưu tiên right nhỏ nhất
// Nếu right bằng nhau, ưu tiên original_idx nhỏ nhất
struct SetEntry {
    int right, original_idx; // left is not needed for ordering in the set itself

    bool operator<(const SetEntry& other) const {
        if (right != other.right) {
            return right < other.right;
        }
        return original_idx < other.original_idx; // Tie-breaking
    }
};


void solve_window_problem() {
    int num_intervals;
    std::cin >> num_intervals;

    std::vector<Interval> intervals(num_intervals);
    for (int i = 0; i < num_intervals; ++i) {
        std::cin >> intervals[i].left >> intervals[i].right;
        intervals[i].original_idx = i + 1; // 1-based indexing for output
    }

    // Sắp xếp các khoảng theo điểm bắt đầu (left)
    std::sort(intervals.begin(), intervals.end());

    std::set<SetEntry> available_ranges; // Cấu trúc dữ liệu ưu tiên
    std::vector<int> permutation_result(num_intervals + 1); // Lưu kết quả hoán vị

    int interval_ptr = 0; // Con trỏ duyệt qua mảng intervals đã sắp xếp

    // Duyệt qua các số từ 1 đến n
    for (int current_value = 1; current_value <= num_intervals; ++current_value) {
        // Thêm tất cả các khoảng có left <= current_value vào tập hợp ưu tiên
        while (interval_ptr < num_intervals && intervals[interval_ptr].left <= current_value) {
            available_ranges.insert({intervals[interval_ptr].right, intervals[interval_ptr].original_idx});
            interval_ptr++;
        }

        // Nếu không có khoảng nào có thể được gán
        if (available_ranges.empty()) {
            std::cout << -1 << "\n";
            return;
        }

        // Lấy khoảng có right nhỏ nhất từ tập hợp ưu tiên
        SetEntry best_match = *available_ranges.begin();
        available_ranges.erase(available_ranges.begin());

        // Nếu right của khoảng nhỏ nhất không đủ lớn để chứa current_value
        if (best_match.right < current_value) {
            std::cout << -1 << "\n";
            return;
        }

        // Gán current_value vào vị trí gốc của khoảng này
        permutation_result[best_match.original_idx] = current_value;
    }

    // In kết quả hoán vị
    for (int i = 1; i <= num_intervals; ++i) {
        std::cout << permutation_result[i] << (i == num_intervals ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    // int test_cases = 1;
    // std::cin >> test_cases;
    // while (test_cases--) {
        solve_window_problem();
    // }
    return 0;
}

M - Vẻ Đẹp Của Sự Mở Rộng Giá Trị

Mô tả bài toán: Cho một mảng số nguyên. Ta phải thực hiện chính xác một thao tác: chọn một đoạn con `[l, r]` không rỗng (`l ≤ r`) và nhân tất cả các phần tử trong đoạn đó với 2. Mục tiêu là làm cho hiệu số giữa giá trị lớn nhất và nhỏ nhất trong mảng sau thao tác `(max - min)` trở nên nhỏ nhất có thể.

Ý tưởng giải pháp:

Để giảm thiểu `max - min`, ta cần cố gắng làm cho giá trị nhỏ nhất tăng lên và giá trị lớn nhất không tăng quá nhiều (hoặc giảm xuống). Rõ ràng, việc nhân giá trị nhỏ nhất hiện tại của mảng với 2 là một bước hợp lý để thu hẹp khoảng cách này.

Gọi `min_val` và `max_val` là giá trị nhỏ nhất và lớn nhất ban đầu của mảng. `min_idx` là chỉ số của `min_val`.

Ta sẽ xét các chiến lược mở rộng đoạn nhân 2 từ `min_idx`:

1. Chiến lược 1: Mở rộng đoạn sao cho `giá trị * 2` không vượt quá `max_val` ban đầu.
   • Tạo một bản sao của mảng gốc. Nhân phần tử tại `min_idx` với 2.
   • Mở rộng sang phải từ `min_idx + 1`: Với mỗi phần tử `a[i]`, nếu `a[i] * 2 ≤ max_val` ban đầu, ta nhân `a[i]` với 2. Nếu không, dừng mở rộng.
   • Mở rộng sang trái từ `min_idx - 1`: Tương tự, nếu `a[i] * 2 ≤ max_val` ban đầu, ta nhân `a[i]` với 2. Nếu không, dừng mở rộng.
   • Sau khi thực hiện, tính `max - min` cho mảng đã thay đổi.
2. Chiến lược 2: Mở rộng đoạn cho đến khi gặp `max_val` ban đầu.
   • Tạo một bản sao khác của mảng gốc. Nhân phần tử tại `min_idx` với 2.
   • Mở rộng sang phải từ `min_idx + 1`: Với mỗi phần tử `a[i]`, nếu `a[i] != max_val` ban đầu, ta nhân `a[i]` với 2. Nếu `a[i] == max_val`, dừng mở rộng.
   • Mở rộng sang trái từ `min_idx - 1`: Tương tự, nếu `a[i] != max_val` ban đầu, ta nhân `a[i]` với 2. Nếu `a[i] == max_val`, dừng mở rộng.
   • Sau khi thực hiện, tính `max - min` cho mảng đã thay đổi.
3. Chiến lược 3: Nhân toàn bộ mảng với 2.
   • Tính `2 * (max_val - min_val)` ban đầu. Đây là kết quả nếu ta nhân tất cả các phần tử với 2.

Kết quả cuối cùng là giá trị nhỏ nhất trong số các `max - min` thu được từ ba chiến lược trên.

#include <iostream>
#include <vector>
#include <algorithm> // For std::min, std::max, std::sort
#include <limits>    // For std::numeric_limits

void solve_expansion_problem() {
    int num_elements;
    std::cin >> num_elements;

    std::vector<long long> original_array(num_elements);
    long long initial_min = std::numeric_limits<long long>::max();
    long long initial_max = std::numeric_limits<long long>::min();
    int min_element_idx = 0;

    for (int i = 0; i < num_elements; ++i) {
        std::cin >> original_array[i];
        if (original_array[i] > initial_max) {
            initial_max = original_array[i];
        }
        if (original_array[i] < initial_min) {
            initial_min = original_array[i];
            min_element_idx = i;
        }
    }

    long long overall_min_diff = std::numeric_limits<long long>::max();

    // --- Chiến lược 1: Mở rộng đến khi giá trị nhân 2 vượt quá initial_max ---
    std::vector<long long> array_strategy1 = original_array;
    array_strategy1[min_element_idx] *= 2;

    for (int i = min_element_idx + 1; i < num_elements; ++i) {
        if (array_strategy1[i] * 2 <= initial_max) {
            array_strategy1[i] *= 2;
        } else {
            break;
        }
    }
    for (int i = min_element_idx - 1; i >= 0; --i) {
        if (array_strategy1[i] * 2 <= initial_max) {
            array_strategy1[i] *= 2;
        } else {
            break;
        }
    }
    long long current_max1 = 0, current_min1 = std::numeric_limits<long long>::max();
    for (long long val : array_strategy1) {
        current_max1 = std::max(current_max1, val);
        current_min1 = std::min(current_min1, val);
    }
    overall_min_diff = std::min(overall_min_diff, current_max1 - current_min1);

    // --- Chiến lược 2: Mở rộng đến khi gặp initial_max ---
    std::vector<long long> array_strategy2 = original_array;
    array_strategy2[min_element_idx] *= 2;

    for (int i = min_element_idx + 1; i < num_elements; ++i) {
        if (array_strategy2[i] != initial_max) { // Keep multiplying until we hit the original max
            array_strategy2[i] *= 2;
        } else {
            break;
        }
    }
    for (int i = min_element_idx - 1; i >= 0; --i) {
        if (array_strategy2[i] != initial_max) { // Keep multiplying until we hit the original max
            array_strategy2[i] *= 2;
        } else {
            break;
        }
    }
    long long current_max2 = 0, current_min2 = std::numeric_limits<long long>::max();
    for (long long val : array_strategy2) {
        current_max2 = std::max(current_max2, val);
        current_min2 = std::min(current_min2, val);
    }
    overall_min_diff = std::min(overall_min_diff, current_max2 - current_min2);

    // --- Chiến lược 3: Nhân toàn bộ mảng với 2 ---
    // Điều này tương đương với 2 * (initial_max - initial_min)
    // nếu không có tràn số và mọi số đều dương.
    // Nếu có số âm hoặc 0, cần cẩn thận hơn. Giả sử số dương.
    overall_min_diff = std::min(overall_min_diff, 2 * (initial_max - initial_min));

    std::cout << overall_min_diff << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    // int test_cases = 1;
    // std::cin >> test_cases;
    // while (test_cases--) {
        solve_expansion_problem();
    // }
    return 0;
}

E - Lỗi Song Sinh

Mô tả bài toán: Một mảng được gọi là "mảng song sinh" nếu nó có độ dài chẵn, chỉ chứa hai loại số khác nhau, và mỗi loại số xuất hiện đúng `(độ dài mảng) / 2` lần. Cho một mảng số nguyên, hỏi số phép toán tối thiểu (+1 hoặc -1 cho bất kỳ phần tử nào) để biến nó thành một mảng song sinh.

Ý tưởng giải pháp:

Để giảm thiểu tổng số phép toán `|x_i - k|`, ta cần di chuyển các số `x_i` về giá trị trung vị (`median`) của tập hợp đó. Trong bài toán này, ta muốn chia mảng thành hai nửa, mỗi nửa có `n/2` phần tử, và biến tất cả các phần tử trong nửa thứ nhất thành một giá trị `target1`, và tất cả các phần tử trong nửa thứ hai thành một giá trị `target2`. `target1` và `target2` phải là hai số khác nhau.

Các bước thực hiện:

1. Sắp xếp mảng: Sắp xếp mảng đầu vào tăng dần. Điều này giúp dễ dàng chia mảng thành hai nửa và tìm trung vị.
2. Kiểm tra trường hợp đặc biệt: Nếu tất cả các phần tử trong mảng đã giống nhau (`map.size() == 1`), ta cần `n/2` phép toán để biến `n/2` phần tử thành một giá trị khác (ví dụ, `X` và `X+1`).
3. Chia mảng và tìm trung vị:
   • Chia mảng đã sắp xếp thành hai nửa: nửa đầu `[0, n/2 - 1]` và nửa sau `[n/2, n - 1]` (sử dụng 0-based indexing).
   • Trung vị cho nửa đầu là phần tử ở vị trí `(n/2 - 1) / 2` trong nửa đó. Gọi giá trị này là `median1_val`.
   • Trung vị cho nửa sau là phần tử ở vị trí `(n/2 - 1) / 2` trong nửa đó (tức là phần tử ở vị trí `n/2 + (n/2 - 1) / 2` trong mảng gốc). Gọi giá trị này là `median2_val`.
   • Tính tổng chi phí `cost_base` để biến nửa đầu thành `median1_val` và nửa sau thành `median2_val`.
4. Xử lý trường hợp `median1_val == median2_val`:

   Nếu hai giá trị trung vị này bằng nhau, ta không thể chọn chúng làm hai giá trị mục tiêu vì chúng phải khác nhau. Ta cần xem xét các lựa chọn thay thế:

   • Lựa chọn A: Biến nửa đầu thành `median1_val - 1`, nửa sau thành `median2_val`. Chi phí là `cost_half1_minus1 + cost_half2`.
   • Lựa chọn B: Biến nửa đầu thành `median1_val`, nửa sau thành `median2_val + 1`. Chi phí là `cost_half1 + cost_half2_plus1`.

   Chọn kết quả tốt nhất trong số `cost_base`, Lựa chọn A, và Lựa chọn B.

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort, std::min
#include <map>       // For frequency count initially

// Hàm tính chi phí để biến một tập hợp số thành một giá trị target
long long calculate_cost(const std::vector<long long>& segment, long long target_value) {
    long long current_cost = 0;
    for (long long num : segment) {
        current_cost += std::abs(num - target_value);
    }
    return current_cost;
}

void solve_twin_array_problem() {
    int n;
    std::cin >> n;

    std::vector<long long> data_array(n);
    std::map<long long, int> freq_count;
    for (int i = 0; i < n; ++i) {
        std::cin >> data_array[i];
        freq_count[data_array[i]]++;
    }

    // Trường hợp đặc biệt: Nếu tất cả các phần tử giống nhau
    if (freq_count.size() == 1) {
        std::cout << n / 2 << "\n"; // Cần n/2 phép toán để đổi n/2 phần tử sang X+1 (hoặc X-1)
        return;
    }

    std::sort(data_array.begin(), data_array.end());

    // Chia mảng thành hai nửa (0-indexed)
    std::vector<long long> first_half(data_array.begin(), data_array.begin() + n / 2);
    std::vector<long long> second_half(data_array.begin() + n / 2, data_array.end());

    // Tìm trung vị cho mỗi nửa
    long long median1 = first_half[(first_half.size() - 1) / 2];
    long long median2 = second_half[(second_half.size() - 1) / 2];

    long long cost_half1 = calculate_cost(first_half, median1);
    long long cost_half2 = calculate_cost(second_half, median2);

    long long min_ops = cost_half1 + cost_half2;

    // Nếu hai trung vị bằng nhau, ta phải chọn hai giá trị mục tiêu khác nhau
    if (median1 == median2) {
        // Option 1: Half 1 -> median1-1, Half 2 -> median2
        long long alt_cost1 = calculate_cost(first_half, median1 - 1) + cost_half2;
        min_ops = std::min(min_ops, alt_cost1);

        // Option 2: Half 1 -> median1, Half 2 -> median2+1
        long long alt_cost2 = cost_half1 + calculate_cost(second_half, median2 + 1);
        min_ops = std::min(min_ops, alt_cost2);
    }
    
    std::cout << min_ops << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int test_cases = 1;
    std::cin >> test_cases; // Read number of test cases
    while (test_cases--) {
        solve_twin_array_problem();
    }
    return 0;
}

C - Di Chuyển Chăm Chỉ

Mô tả bài toán: Cho một ma trận vuông kích thước `n x n` chứa các ký tự '0' và '1'. Ta cần di chuyển tất cả các ký tự '1' vào vùng góc trên bên trái có kích thước `n/2 x n/2`. Yêu cầu xuất tổng số bước di chuyển và từng bước di chuyển. Mỗi bước di chuyển là một thao tác hoán đổi hai phần tử kề nhau theo chiều ngang hoặc dọc. Số bước di chuyển không cần phải tối thiểu.

Ý tưởng giải pháp:

Bài toán này yêu cầu di chuyển các ký tự '1' vào một vùng cụ thể (góc trên bên trái). Vì không yêu cầu số bước tối thiểu, ta có thể áp dụng một chiến lược đơn giản:

1. Duyệt qua từng ô `(target_r, target_c)` trong vùng đích `n/2 x n/2` theo thứ tự hàng-cột.
2. Nếu ô `grid[target_r][target_c]` hiện tại là '0':
   • Tìm một ô `(source_r, source_c)` bất kỳ trong ma trận mà `grid[source_r][source_c]` là '1'. Để đảm bảo tính đúng đắn và đơn giản, ta có thể tìm '1' đầu tiên gặp phải khi duyệt toàn bộ ma trận (ngoại trừ ô đích hiện tại) theo thứ tự hàng-cột.
   • Sau khi tìm thấy `(source_r, source_c)` chứa '1', ta di chuyển '1' đó đến `(target_r, target_c)` bằng cách thực hiện một chuỗi các phép hoán đổi kề nhau. Một chiến lược di chuyển đơn giản là:
     • Di chuyển '1' từ `(source_r, source_c)` đến `(source_r, target_c)` (di chuyển ngang).
     • Sau đó, di chuyển '1' từ `(source_r, target_c)` đến `(target_r, target_c)` (di chuyển dọc).

     Mỗi bước hoán đổi `(x1, y1)` với `(x2, y2)` sẽ được ghi lại. Sau khi '1' đã đến đích, ô ban đầu của '1' sẽ trở thành '0' thông qua các phép hoán đổi.

Chi tiết hàm di chuyển (record_and_move):

Để di chuyển một '1' từ `(src_r, src_c)` đến `(dest_r, dest_c)`:

• Di chuyển dọc: Nếu `src_r != dest_r`, ta hoán đổi `grid[src_r][src_c]` với `grid[src_r - 1][src_c]` (nếu `src_r > dest_r`) hoặc với `grid[src_r + 1][src_c]` (nếu `src_r < dest_r`), cho đến khi '1' đến hàng `dest_r`.
• Di chuyển ngang: Nếu `src_c != dest_c`, ta hoán đổi `grid[dest_r][src_c]` với `grid[dest_r][src_c - 1]` (nếu `src_c > dest_c`) hoặc với `grid[dest_r][src_c + 1]` (nếu `src_c < dest_c`), cho đến khi '1' đến cột `dest_c`.

Lưu ý: Các tọa độ đầu ra phải là 1-based. Trong code, ta sử dụng 0-based indexing và chuyển đổi khi in ra.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // For std::swap

// Cấu trúc để lưu một bước hoán đổi (x1, y1, x2, y2)
struct SwapMove {
    int r1, c1, r2, c2;
};

// Hàm thực hiện di chuyển một phần tử từ (src_r, src_c) đến (dest_r, dest_c)
// và ghi lại các bước hoán đổi
void record_and_move(int& src_r, int& src_c, int dest_r, int dest_c, 
                     std::vector<std::string>& grid, 
                     std::vector<SwapMove>& recorded_moves) {
    
    // Di chuyển dọc trước: từ src_r đến dest_r trong cột src_c
    while (src_r != dest_r) {
        if (src_r > dest_r) { // Cần di chuyển lên trên
            std::swap(grid[src_r][src_c], grid[src_r - 1][src_c]);
            recorded_moves.push_back({src_r + 1, src_c + 1, src_r - 1 + 1, src_c + 1});
            src_r--;
        } else { // Cần di chuyển xuống dưới
            std::swap(grid[src_r][src_c], grid[src_r + 1][src_c]);
            recorded_moves.push_back({src_r + 1, src_c + 1, src_r + 1 + 1, src_c + 1});
            src_r++;
        }
    }

    // Di chuyển ngang sau: từ src_c đến dest_c trong hàng dest_r (hiện là src_r)
    while (src_c != dest_c) {
        if (src_c > dest_c) { // Cần di chuyển sang trái
            std::swap(grid[dest_r][src_c], grid[dest_r][src_c - 1]);
            recorded_moves.push_back({dest_r + 1, src_c + 1, dest_r + 1, src_c - 1 + 1});
            src_c--;
        } else { // Cần di chuyển sang phải
            std::swap(grid[dest_r][src_c], grid[dest_r][src_c + 1]);
            recorded_moves.push_back({dest_r + 1, src_c + 1, dest_r + 1, src_c + 1 + 1});
            src_c++;
        }
    }
}


// Hàm tìm số '1' và di chuyển nó
void find_and_move_one(int target_r, int target_c, int n, 
                       std::vector<std::string>& grid, 
                       std::vector<SwapMove>& all_moves) {
    
    int source_r = -1, source_c = -1;

    // Tìm '1' đầu tiên không nằm ở ô đích hiện tại
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) {
            // Nếu ô này chứa '1' và không phải là ô đích đang xét
            // (để tránh trường hợp ô đích đã là '1' và ta cố gắng di chuyển nó đi)
            if (grid[r][c] == '1' && (r != target_r || c != target_c)) {
                source_r = r;
                source_c = c;
                break; 
            }
        }
        if (source_r != -1) break;
    }

    if (source_r != -1) {
        // Di chuyển '1' từ (source_r, source_c) đến (target_r, target_c)
        // src_r và src_c được truyền theo tham chiếu để cập nhật vị trí của '1'
        // sau mỗi bước hoán đổi trong record_and_move
        record_and_move(source_r, source_c, target_r, target_c, grid, all_moves);
        // Sau khi di chuyển, ô đích đã chứa '1', ô nguồn ban đầu đã thành '0' (do swap)
    }
}

void solve_matrix_move() {
    int n;
    std::cin >> n;
    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }

    std::vector<SwapMove> recorded_moves;

    int target_quadrant_size = n / 2;

    // Duyệt qua vùng đích n/2 x n/2
    for (int r = 0; r < target_quadrant_size; ++r) {
        for (int c = 0; c < target_quadrant_size; ++c) {
            if (grid[r][c] == '0') {
                // Nếu ô này là '0', tìm một '1' ở nơi khác và di chuyển nó đến đây
                find_and_move_one(r, c, n, grid, recorded_moves);
            }
        }
    }

    std::cout << recorded_moves.size() << "\n";
    for (const auto& move : recorded_moves) {
        std::cout << move.r1 << " " << move.c1 << " " << move.r2 << " " << move.c2 << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int test_cases = 1;
    std::cin >> test_cases; // Read number of test cases
    while (test_cases--) {
        solve_matrix_move();
    }
    return 0;
}