Bài viết này trình bày các phương pháp giải quyết cho một loạt các bài toán lập trình thi đấu, bao gồm các vấn đề về xử lý chuỗi ký tự, mảng, đếm tần suất, lý thuyết đồ thị và phương trình Diophantine. Mỗi bài toán sẽ được phân tích, trình bày ý tưởng giải quyết và cung cấp mã nguồn minh họa.

Bài toán 1: Sắp xếp chuỗi số

Mô tả: Cho một chuỗi các chữ số. Yêu cầu sắp xếp các chữ số này theo thứ tự giảm dần để tạo ra số lớn nhất có thể.

Ý tưởng giải quyết:

Để tạo ra số lớn nhất từ các chữ số đã cho, chúng ta chỉ cần đếm tần suất xuất hiện của mỗi chữ số (0-9) và sau đó in chúng ra theo thứ tự từ lớn nhất (9) đến nhỏ nhất (0), mỗi chữ số được in ra số lần tương ứng với tần suất của nó. Ví dụ, nếu chuỗi đầu vào là "31415", chúng ta đếm được một chữ số '5', một chữ số '4', một chữ số '3', và hai chữ số '1'. Khi in ra theo thứ tự giảm dần, kết quả sẽ là "54311".

Mã nguồn C++:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // Không bắt buộc cho cách tiếp cận này, nhưng thường hữu ích

void xu_ly_bai_tap_chuoi_so() {
    std::string chuoi_chu_so;
    std::cin >> chuoi_chu_so;

    std::vector<int> dem_tan_suat(10, 0); // Sử dụng vector để lưu tần suất từ 0 đến 9
    for (char ky_tu : chuoi_chu_so) {
        dem_tan_suat[ky_tu - '0']++; // Tăng tần suất cho chữ số tương ứng
    }

    // In các chữ số theo thứ tự giảm dần
    for (int chu_so = 9; chu_so >= 0; --chu_so) {
        for (int i = 0; i < dem_tan_suat[chu_so]; ++i) {
            std::cout << chu_so;
        }
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int so_luong_test_cases;
    std::cin >> so_luong_test_cases;
    while (so_luong_test_cases--) {
        xu_ly_bai_tap_chuoi_so();
    }
    return 0;
}

Bài toán 2: Chọn đoạn con tối ưu trong mảng

Mô tả: Cho một mảng gồm N số nguyên và một số nguyên K. Hãy tìm giá trị "độ rộng" (phần tử lớn nhất trừ phần tử nhỏ nhất cộng 1) của một đoạn con gồm K+1 phần tử được chọn từ giữa mảng sau khi mảng đã được sắp xếp.

Ý tưởng giải quyết:

Đầu tiên, chúng ta cần sắp xếp mảng các số nguyên theo thứ tự tăng dần. Sau khi sắp xếp, các phần tử có giá trị nhỏ nhất sẽ ở đầu mảng và các phần tử có giá trị lớn nhất sẽ ở cuối mảng. Bài toán yêu cầu tính độ rộng của một đoạn con gồm K+1 phần tử, được chọn bằng cách loại bỏ một số lượng phần tử bằng nhau từ cả hai đầu của mảng đã sắp xếp. Cụ thể, số lượng phần tử bị loại bỏ từ mỗi phía là (N - (K+1)) / 2. Giả sử num_removed_each_side = (N - K - 1) / 2. Khi đó, phần tử nhỏ nhất của đoạn con sẽ là arr[num_removed_each_side] (sử dụng chỉ số 0) và phần tử lớn nhất là arr[N - 1 - num_removed_each_side]. Độ rộng của đoạn con là (arr[max_idx] - arr[min_idx] + 1).

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <algorithm>

void xu_ly_lua_chon_can_ho() {
    int so_luong_can_ho, so_luong_du_kien;
    std::cin >> so_luong_can_ho >> so_luong_du_kien;

    std::vector<long long> chi_phi_can_ho(so_luong_can_ho);
    for (int i = 0; i < so_luong_can_ho; ++i) {
        std::cin >> chi_phi_can_ho[i];
    }

    std::sort(chi_phi_can_ho.begin(), chi_phi_can_ho.end()); // Sắp xếp chi phí

    // Tính toán số lượng phần tử cần loại bỏ từ mỗi phía.
    // Độ dài của đoạn con cần xét là K_selected + 1.
    // Ví dụ: N=5, K=1. Đoạn con cần xét là 1+1=2 phần tử.
    // Số phần tử còn lại sau khi chọn đoạn con là N - (K_selected+1).
    // Số phần tử loại bỏ từ mỗi phía là (N - (K_selected + 1)) / 2.
    // Chỉ số 0-based của phần tử đầu tiên của đoạn con là 'so_pt_loai_bo_moi_phia'.
    // Chỉ số 0-based của phần tử cuối cùng của đoạn con là 'so_luong_can_ho - 1 - so_pt_loai_bo_moi_phia'.
    
    int so_pt_loai_bo_moi_phia = (so_luong_can_ho - (so_luong_du_kien + 1)) / 2;
    
    long long gia_tri_min_doan_con = chi_phi_can_ho[so_pt_loai_bo_moi_phia];
    long long gia_tri_max_doan_con = chi_phi_can_ho[so_luong_can_ho - 1 - so_pt_loai_bo_moi_phia];

    std::cout << gia_tri_max_doan_con - gia_tri_min_doan_con + 1 << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int so_luong_test_cases;
    std::cin >> so_luong_test_cases;
    while (so_luong_test_cases--) {
        xu_ly_lua_chon_can_ho();
    }
    return 0;
}

Bài toán 3: Quy tắc đặt cược thể thao

Mô tả: Cho một danh sách N số nguyên. Cần xác định xem có thể thắng cược hay không dựa trên hai quy tắc sau:

1. Có ít nhất một số xuất hiện từ 4 lần trở lên trong danh sách.
2. Có hai số nguyên liên tiếp X và X+1, mà cả X và X+1 đều xuất hiện ít nhất 2 lần trong danh sách.

Nếu một trong hai quy tắc trên được thỏa mãn, kết quả là "Yes"; ngược lại, kết quả là "No".

Ý tưởng giải quyết:

Để giải quyết bài toán này, chúng ta cần đếm tần suất xuất hiện của mỗi số. Một bản đồ (std::map) hoặc một mảng tần suất (nếu phạm vi giá trị đủ nhỏ) có thể được sử dụng cho mục đích này. Sau khi đếm tần suất, chúng ta duyệt qua tất cả các số phân biệt để kiểm tra hai điều kiện:

1. Duyệt qua bản đồ tần suất: Nếu bất kỳ số nào có tần suất >= 4, thì điều kiện 1 được thỏa mãn và kết quả là "Yes".
2. Nếu điều kiện 1 không thỏa mãn, chúng ta trích xuất tất cả các số phân biệt vào một vector và sắp xếp nó. Sau đó, duyệt qua vector này: nếu có hai số current_val và next_val liên tiếp (next_val == current_val + 1), và cả frequencies[current_val] >= 2 lẫn frequencies[next_val] >= 2, thì điều kiện 2 được thỏa mãn và kết quả là "Yes".

Nếu không có điều kiện nào được thỏa mãn sau khi kiểm tra cả hai, kết quả là "No".

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

void xu_ly_quy_tac_dat_cuoc() {
    int so_luong_so;
    std::cin >> so_luong_so;

    std::map<int, int> tan_suat;
    for (int i = 0; i < so_luong_so; ++i) {
        int gia_tri;
        std::cin >> gia_tri;
        tan_suat[gia_tri]++;
    }

    bool co_the_thang = false;

    // Điều kiện 1: Bất kỳ số nào xuất hiện 4 lần trở lên
    for (auto const& [gia_tri, dem] : tan_suat) {
        if (dem >= 4) {
            co_the_thang = true;
            break;
        }
    }

    if (co_the_thang) {
        std::cout << "Yes\n";
        return;
    }

    // Điều kiện 2: Hai số liên tiếp, mỗi số xuất hiện ít nhất 2 lần
    std::vector<int> cac_gia_tri_phan_biet;
    for (auto const& [gia_tri, dem] : tan_suat) {
        cac_gia_tri_phan_biet.push_back(gia_tri);
    }
    std::sort(cac_gia_tri_phan_biet.begin(), cac_gia_tri_phan_biet.end());

    for (size_t i = 0; i + 1 < cac_gia_tri_phan_biet.size(); ++i) {
        int gia_tri_hien_tai = cac_gia_tri_phan_biet[i];
        int gia_tri_tiep_theo = cac_gia_tri_phan_biet[i+1];

        if (gia_tri_tiep_theo == gia_tri_hien_tai + 1) { // Kiểm tra xem chúng có liên tiếp không
            if (tan_suat[gia_tri_hien_tai] >= 2 && tan_suat[gia_tri_tiep_theo] >= 2) {
                co_the_thang = true;
                break;
            }
        }
    }

    if (co_the_thang) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int so_luong_test_cases;
    std::cin >> so_luong_test_cases;
    while (so_luong_test_cases--) {
        xu_ly_quy_tac_dat_cuoc();
    }
    return 0;
}

Bài toán 4: Kiểm tra hành lý

Mô tả: Cho một lưới N x M và một đường đi gồm K+1 điểm ảnh (x, y). Đường đi này được tạo thành từ K bước. Mỗi bước di chuyển từ (x_prev, y_prev) đến (x_curr, y_curr) có thể là một trong các loại sau:

1. Di chuyển chéo (|dx| = 1, |dy| = 1): Tạo ra một cạnh giữa (x_prev, y_curr) và (x_curr, y_prev) trong đồ thị.
2. Di chuyển thẳng qua 2 ô (|dx| = 2, dy = 0 hoặc dx = 0, |dy| = 2): Ô nằm giữa đường đi này ((x_prev+x_curr)/2, y_curr) hoặc (x_curr, (y_prev+y_curr)/2) được đánh dấu là "ô đặc biệt". Nếu ô này đã là đặc biệt, đường đi không hợp lệ.
3. Mọi loại di chuyển khác đều không hợp lệ.

Sau khi xây dựng đồ thị và đánh dấu các ô đặc biệt, bài toán yêu cầu tính số cách hợp lệ để gán hướng cho các cạnh trong mỗi thành phần liên thông của đồ thị, tuân thủ các quy tắc sau (tính theo modulo 10^9 + 7):

• Với một thành phần liên thông không chứa ô đặc biệt:
  • Nếu là một chu trình đơn (số đỉnh = số cạnh): nhân kết quả với 2.
  • Nếu là một cây (số đỉnh = số cạnh + 1): nhân kết quả với số đỉnh.
  • Nếu cấu trúc khác (ví dụ: nhiều chu trình): kết quả là 0.
• Với một thành phần liên thông chứa đúng một ô đặc biệt:
  • Nếu là một chu trình (số đỉnh = số cạnh): kết quả là 0.
  • Nếu là một cây (số đỉnh = số cạnh + 1): kết quả không đổi (nhân với 1).
• Với một thành phần liên thông chứa nhiều hơn một ô đặc biệt: kết quả là 0.

Ý tưởng giải quyết:

Bài toán này yêu cầu xây dựng một đồ thị và sau đó phân tích cấu trúc của các thành phần liên thông. Các bước chính bao gồm:

1. Mã hóa ô lưới: Chuyển đổi tọa độ (r, c) từ 1-based thành một chỉ số nguyên duy nhất, ví dụ: (r-1)*M + c.
2. Xây dựng đồ thị: Duyệt qua K bước di chuyển. Dựa vào loại di chuyển, thêm cạnh vào danh sách kề (adj) hoặc đánh dấu ô đặc biệt (special_cell). Nếu một ô đặc biệt bị đánh dấu lần thứ hai hoặc gặp một bước di chuyển không hợp lệ, toàn bộ đường đi là không hợp lệ (kết quả là 0).
3. Duyệt DFS các thành phần liên thông: Sử dụng Depth First Search (DFS) để tìm và phân tích từng thành phần liên thông. Trong quá trình DFS, đếm số đỉnh (nodes_in_component), tổng bậc của các đỉnh (edges_sum_degree, từ đó tính số cạnh edges_in_component = edges_sum_degree / 2), và số ô đặc biệt (special_cells_in_component) trong mỗi thành phần.
4. Tính toán kết quả: Dựa trên các quy tắc đã nêu, cập nhật biến final_answer. Nếu bất kỳ thành phần nào vi phạm quy tắc, final_answer trở thành 0.
5. Khởi tạo lại: Đảm bảo các cấu trúc dữ liệu (adj, visited_node, special_cell) được xóa hoặc khởi tạo lại cho mỗi trường hợp thử nghiệm.

Mã nguồn C++:

#include <iostream>
#include <vector>
#include <numeric> // Dành cho std::gcd, mặc dù không trực tiếp dùng ở đây
#include <algorithm> // Dành cho std::abs

const int MOD = 1000000007;

std::vector<std::vector<int>> danh_sach_ke;
std::vector<bool> da_tham;
std::vector<bool> la_o_dac_biet;

int so_hang, so_cot, do_dai_duong_di;

// Chuyển đổi tọa độ 1-based (r, c) thành chỉ số nguyên 1-based
int ma_hoa_o(int r, int c) {
    return (r - 1) * so_cot + c;
}

void duyet_dfs(int u,
               int& so_dinh_trong_tp,
               long long& tong_bac_canh,
               int& so_o_dac_biet_trong_tp) {
    da_tham[u] = true;
    so_dinh_trong_tp++;
    tong_bac_canh += danh_sach_ke[u].size();
    if (la_o_dac_biet[u]) {
        so_o_dac_biet_trong_tp++;
    }
    for (int v : danh_sach_ke[u]) {
        if (!da_tham[v]) {
            duyet_dfs(v, so_dinh_trong_tp, tong_bac_canh, so_o_dac_biet_trong_tp);
        }
    }
}

void xu_ly_kiem_tra_hanh_ly() {
    std::cin >> so_hang >> so_cot >> do_dai_duong_di;

    std::vector<std::pair<int, int>> toa_do_duong_di(do_dai_duong_di + 1);
    for (int i = 0; i <= do_dai_duong_di; ++i) {
        std::cin >> toa_do_duong_di[i].first >> toa_do_duong_di[i].second;
    }

    int tong_so_o = so_hang * so_cot;
    danh_sach_ke.assign(tong_so_o + 1, std::vector<int>()); // Chỉ số 1-based
    da_tham.assign(tong_so_o + 1, false);
    la_o_dac_biet.assign(tong_so_o + 1, false);

    long long ket_qua_cuoi = 1;
    bool duong_di_khong_hop_le = false;

    for (int i = 1; i <= do_dai_duong_di; ++i) {
        int hang_truoc = toa_do_duong_di[i-1].first;
        int cot_truoc = toa_do_duong_di[i-1].second;
        int hang_hien_tai = toa_do_duong_di[i].first;
        int cot_hien_tai = toa_do_duong_di[i].second;

        int chi_so_o_giua = -1;

        // Kiểm tra di chuyển "thẳng qua 2 ô" và đánh dấu ô giữa là đặc biệt
        if (std::abs(hang_hien_tai - hang_truoc) == 2 && cot_hien_tai == cot_truoc) {
            chi_so_o_giua = ma_hoa_o((hang_hien_tai + hang_truoc) / 2, cot_hien_tai);
        } else if (std::abs(cot_hien_tai - cot_truoc) == 2 && hang_hien_tai == hang_truoc) {
            chi_so_o_giua = ma_hoa_o(hang_hien_tai, (cot_hien_tai + cot_truoc) / 2);
        }

        if (chi_so_o_giua != -1) {
            if (la_o_dac_biet[chi_so_o_giua]) {
                duong_di_khong_hop_le = true; // Không thể đánh dấu một ô đã đặc biệt lần nữa
                break;
            }
            la_o_dac_biet[chi_so_o_giua] = true;
        } else {
            // Kiểm tra di chuyển chéo (1 đơn vị cả x và y)
            if (std::abs(hang_hien_tai - hang_truoc) == 1 && std::abs(cot_hien_tai - cot_truoc) == 1) {
                // Các ô tạo cạnh là hai ô "góc" xung quanh ô trung gian
                int o_u = ma_hoa_o(hang_truoc, cot_hien_tai);
                int o_v = ma_hoa_o(hang_hien_tai, cot_truoc);
                danh_sach_ke[o_u].push_back(o_v);
                danh_sach_ke[o_v].push_back(o_u);
            } else {
                duong_di_khong_hop_le = true; // Mọi loại di chuyển khác đều không hợp lệ
                break;
            }
        }
    }

    if (duong_di_khong_hop_le) {
        ket_qua_cuoi = 0;
    } else {
        for (int i = 1; i <= tong_so_o; ++i) {
            if (!da_tham[i]) {
                int so_dinh_tp = 0;
                long long tong_bac_tp = 0;
                int so_o_dac_biet_tp = 0;

                duyet_dfs(i, so_dinh_tp, tong_bac_tp, so_o_dac_biet_tp);

                long long so_canh_tp = tong_bac_tp / 2; // Mỗi cạnh được đếm hai lần

                if (so_o_dac_biet_tp == 0) {
                    if (so_dinh_tp == so_canh_tp) { // Thành phần liên thông là một chu trình
                        ket_qua_cuoi = (ket_qua_cuoi * 2) % MOD;
                    } else if (so_dinh_tp == so_canh_tp + 1) { // Thành phần liên thông là một cây
                        ket_qua_cuoi = (ket_qua_cuoi * so_dinh_tp) % MOD;
                    } else { // Cấu trúc không hợp lệ (ví dụ: nhiều chu trình)
                        ket_qua_cuoi = 0;
                        break;
                    }
                } else if (so_o_dac_biet_tp == 1) {
                    if (so_dinh_tp == so_canh_tp) { // Chu trình chứa đúng một ô đặc biệt
                        ket_qua_cuoi = 0;
                        break;
                    }
                    // Nếu là cây chứa một ô đặc biệt, kết quả không đổi (nhân 1).
                } else { // so_o_dac_biet_tp > 1 (nhiều hơn một ô đặc biệt)
                    ket_qua_cuoi = 0;
                    break;
                }
            }
        }
    }
    std::cout << ket_qua_cuoi << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int so_luong_test_cases;
    std::cin >> so_luong_test_cases;
    while (so_luong_test_cases--) {
        xu_ly_kiem_tra_hanh_ly();
    }
    return 0;
}

Bài toán 5: Tam giác Bermuda

Mô tả: Mô phỏng đường đi của một vật thể trong một lưới vuông N x N, bắt đầu từ (x, y) với vận tốc (vx, vy). Các cạnh của lưới phản xạ vật thể. Yêu cầu tìm một giá trị liên quan đến số lần va chạm hoặc quãng đường di chuyển trong một trạng thái cụ thể.

Ý tưởng giải quyết:

Bài toán này thường được giải bằng kỹ thuật "gấp đối xứng" (symmetric folding), biến đường đi zig-zag thành một đường thẳng trong một không gian lớn hơn vô hạn. Về cơ bản, thay vì phản xạ ở biên, chúng ta tưởng tượng lưới được nhân bản vô hạn theo mọi hướng, và vật thể đi thẳng qua các bản sao. Tọa độ của vật thể trong không gian "gấp" này có thể được biểu diễn bằng các phương trình Diophantine.

Cụ thể, phương trình có dạng A*p + B*q = C, trong đó A = vy*N, B = -vx*N, và C = vx*(N-y) - vy*(N-x). Chúng ta cần tìm các nghiệm nguyên không âm (p, q) cho phương trình này. Thuật toán Euclid mở rộng (Extended Euclidean Algorithm - exgcd) được sử dụng để tìm một nghiệm riêng cho A*p' + B*q' = gcd(A, B). Sau đó, nghiệm riêng này được nhân với C / gcd(A, B) để tìm một nghiệm riêng cho phương trình ban đầu. Các nghiệm tổng quát có dạng p = p_0 + k * (B/g) và q = q_0 - k * (A/g), trong đó g = gcd(A, B).

Sau khi có nghiệm riêng (p, q), chúng ta cần điều chỉnh nó để tìm cặp (p, q) không âm nhỏ nhất có thể, sử dụng các bước di chuyển tương ứng với vận tốc đã đơn giản hóa (vx, vy). Việc này thường liên quan đến việc tìm một số nguyên k sao cho p và q nằm trong các khoảng mong muốn.

Công thức tính kết quả cuối cùng là: p + q + |p - q| / 2 + (p + q + 2) / 2.

Mã nguồn C++:

#include <iostream>
#include <numeric> // Dành cho std::gcd
#include <utility> // Dành cho std::pair
#include <algorithm> // Dành cho std::max, std::min, std::abs

// extended_gcd tìm x, y sao cho a*x + b*y = gcd(a, b)
// g_out sẽ lưu trữ gcd(a, b)
std::pair<long long, long long> extended_gcd(long long a, long long b, long long& g_out) {
    if (b == 0) {
        g_out = a;
        return {1, 0};
    } else {
        std::pair<long long, long long> res = extended_gcd(b, a % b, g_out);
        long long x_prev = res.first;
        long long y_prev = res.second;
        return {y_prev, x_prev - (a / b) * y_prev};
    }
}

void xu_ly_tam_giac_bermuda() {
    long long kich_thuoc_luoi_N, vi_tri_x, vi_tri_y, van_toc_vx, van_toc_vy;
    std::cin >> kich_thuoc_luoi_N >> vi_tri_x >> vi_tri_y >> van_toc_vx >> van_toc_vy;

    // Đơn giản hóa vận tốc bằng cách chia cho ước chung lớn nhất
    long long ucln_van_toc = std::gcd(std::abs(van_toc_vx), std::abs(van_toc_vy));
    van_toc_vx /= ucln_van_toc;
    van_toc_vy /= ucln_van_toc;

    // Phương trình Diophantine: A*p + B*q = C
    // A = van_toc_vy * N
    // B = -van_toc_vx * N
    // C = van_toc_vx * (N - vi_tri_y) - van_toc_vy * (N - vi_tri_x)
    long long he_so_A = van_toc_vy * kich_thuoc_luoi_N;
    long long he_so_B = -van_toc_vx * kich_thuoc_luoi_N;
    long long ve_phai_C = van_toc_vx * (kich_thuoc_luoi_N - vi_tri_y) - van_toc_vy * (kich_thuoc_luoi_N - vi_tri_x);

    long long ucln_he_so;
    // extended_gcd tìm p_tmp, q_tmp sao cho he_so_A * p_tmp + he_so_B * q_tmp = ucln_he_so
    std::pair<long long, long long> nghiem_rieng_co_so = extended_gcd(he_so_A, he_so_B, ucln_he_so);
    long long p_hien_tai = nghiem_rieng_co_so.first;
    long long q_hien_tai = nghiem_rieng_co_so.second;

    if (ve_phai_C % ucln_he_so != 0) {
        std::cout << -1 << "\n"; // Không có nghiệm nguyên
    } else {
        // Mở rộng nghiệm riêng để khớp với vế phải C
        p_hien_tai *= (ve_phai_C / ucln_he_so);
        q_hien_tai *= (ve_phai_C / ucln_he_so);

        // Điều chỉnh p_hien_tai và q_hien_tai để chúng không âm và nhỏ nhất
        // Các bước điều chỉnh này dựa trên mối quan hệ đặc biệt của p, q với vận tốc van_toc_vx, van_toc_vy
        // trong không gian gấp.

        // Pha 1: Đảm bảo p_hien_tai và q_hien_tai không âm.
        long long buoc_tang_k = 0; // Giá trị k cần thiết để điều chỉnh
        
        if (van_toc_vx != 0) {
            if (p_hien_tai < 0) {
                if (van_toc_vx > 0) buoc_tang_k = std::max(buoc_tang_k, (-p_hien_tai + van_toc_vx - 1) / van_toc_vx);
                else /* van_toc_vx < 0 */ buoc_tang_k = std::max(buoc_tang_k, p_hien_tai / (-van_toc_vx));
            }
        } else if (p_hien_tai < 0) { std::cout << -1 << "\n"; return; } 

        if (van_toc_vy != 0) {
            if (q_hien_tai < 0) {
                if (van_toc_vy > 0) buoc_tang_k = std::max(buoc_tang_k, (-q_hien_tai + van_toc_vy - 1) / van_toc_vy);
                else /* van_toc_vy < 0 */ buoc_tang_k = std::max(buoc_tang_k, q_hien_tai / (-van_toc_vy));
            }
        } else if (q_hien_tai < 0) { std::cout << -1 << "\n"; return; }

        p_hien_tai += buoc_tang_k * van_toc_vx;
        q_hien_tai += buoc_tang_k * van_toc_vy;

        // Pha 2: Tìm nghiệm không âm nhỏ nhất bằng cách lùi bước nếu có thể.
        // Điều này đảm bảo rằng chúng ta đang ở nghiệm (p, q) gần gốc (0,0) nhất.
        long long abs_vx = std::abs(van_toc_vx);
        long long abs_vy = std::abs(van_toc_vy);
        
        if (abs_vx != 0 && abs_vy != 0) {
            // Số bước lùi tối đa mà vẫn giữ p và q không âm.
            long long buoc_lui_k_max = std::min(p_hien_tai / abs_vx, q_hien_tai / abs_vy);
            
            p_hien_tai -= buoc_lui_k_max * van_toc_vx;
            q_hien_tai -= buoc_lui_k_max * van_toc_vy;
        }

        // Công thức tính kết quả cuối cùng
        std::cout << p_hien_tai + q_hien_tai + std::abs(p_hien_tai - q_hien_tai) / 2 + (p_hien_tai + q_hien_tai + 2) / 2 << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int so_luong_test_cases;
    std::cin >> so_luong_test_cases;
    while (so_luong_test_cases--) {
        xu_ly_tam_giac_bermuda();
    }
    return 0;
}