Hiểu bài toán

Cho hai con kangaroo A và B trên trục tọa độ dương. A bắt đầu tại xA và mỗi bước nhảy vA đơn vị. B bắt đầu tại xB và mỗi bước nhảy vB đơn vị. Cả hai cùng nhảy về phía trước (cùng chiều). Cần xác định xem có tồn tại một số nguyên không âm k (số lần nhảy) sao cho vị trí của A bằng vị trí của B tại thời điểm đó hay không. Nói cách khác, tìm k >= 0 sao cho xA + k * vA = xB + k * vB.

Các cách tiếp cận

Cách Phương pháp giải phương trình tuyến tính

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        long long xA, vA, xB, vB;
        cin >> xA >> vA >> xB >> vB;

        // Truong hop van toc bang nhau
        if (vA == vB) {
            if (xA == xB) cout << "YES\n";
            else cout << "NO\n";
            continue;
        }

        // Giai phuong trinh: xA + k*vA = xB + k*vB
        // => k*(vA - vB) = xB - xA
        // => k = (xB - xA) / (vA - vB)

        long long dx = xB - xA;
        long long dv = vA - vB;

        // Kiem tra dieu kien:
        // 1. k phai la so nguyen duong hoac 0 (dx va dv cung dau)
        // 2. k phai la so nguyen (dx chia het cho dv)

        if (dx * dv < 0) {
            // Khac dau => k am => Khong the gap nhau
            cout << "NO\n";
        } else if (dx % dv == 0) {
            // Cung dau va chia het => k duong va la so nguyen
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Phương pháp này dựa trên việc thiết lập phương trình xA + kvA = xB + kvB và giải tìm k. Ta có k = (xB - xA)/(vA - vB). Điều kiện để hai con kangaroo gặp nhau là k phải là một số nguyên không âm.

1. Nếu vA = vB: Nếu xA = xB thì chúng luôn ở cùng vị trí (YES), ngược lại khoảng cách không đổi nên không bao giờ gặp (NO).
2. Nếu vA ≠ vB: Ta tính dx = xB - xA và dv = vA - vB.

• 'dx * dv < 0' nghĩa là dx và dv trái dấu. Tỷ số k = dx/dv sẽ là số âm, không thỏa mãn điều kiện k >= 0.
• 'dx % dv == 0' nghĩa là k là một số nguyên.
• Nếu cả hai điều kiện trên thỏa mãn (dx/dv >= 0 và là số nguyên), đáp án là YES.

Cách Phương pháp kiểm tra điều kiện trực tiếp

#include <bits/stdc++.h>
using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        long long xA, vA, xB, vB;
        cin >> xA >> vA >> xB >> vB;

        long long diff_v = vA - vB;
        long long diff_x = xB - xA;

        if (diff_v == 0) {
            if (diff_x == 0) cout << "YES\n";
            else cout << "NO\n";
        } else {
            // Kiem tra chia het va k duong
            if (diff_x % diff_v == 0 && diff_x / diff_v >= 0) 
                cout << "YES\n";
            else 
                cout << "NO\n";
        }
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Đây là biến thể của phương pháp 1, sử dụng phép chia trực tiếp để kiểm tra xem k có phải là số nguyên không âm hay không.

• Nếu diffv = 0 (vA = vB), kiểm tra diffx = 0 (xA = xB).
• Nếu diffv khác 0, kiểm tra diff_x % diff_v == 0 (để đảm bảo k nguyên) và diff_x / diff_v >= 0 (để đảm bảo k không âm). Lưu ý: Cú pháp diff_x / diff_v >= 0 trong C++ sẽ đúng cả khi diffx và diff_v cùng dương hoặc cùng âm (vì phép chia số nguyên giữa hai số cùng dấu cho kết quả dương).

Cách Phương pháp kiểm tra theo hướng di chuyển

#include <bits/stdc++.h>
using namespace std;

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

    int Q;
    cin >> Q;
    while (Q--) {
        long long x1, v1, x2, v2;
        cin >> x1 >> v1 >> x2 >> v2;

        if (v1 == v2) {
            cout << (x1 == x2 ? "YES\n" : "NO\n");
        } else if ((x2 - x1) % (v1 - v2) == 0 && ((x1 < x2 && v1 > v2) || (x1 > x2 && v1 < v2))) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Phương pháp này kiểm tra logic theo điều kiện vật lý:

1. Bằng vận tốc (v1 = v2): Kiểm tra vị trí ban đầu.
2. Khác vận tốc: Điều kiện gặp nhau là con sau phải nhanh hơn con trước nếu nó ở phía sau. Cụ thể:

• Nếu A ở sau B (x1 < x2) thì A phải nhanh hơn B (v1 > v2).
• Nếu A ở trước B (x1 > x2) thì A phải chậm hơn B (v1 < v2). Nếu điều kiện hướng đi đúng, ta tiếp tục kiểm tra xem số bước nhảy k = (x2 - x1)/(v1 - v2) có phải là một số nguyên hay không bằng phép chia lấy dư.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về nghiệm nguyên không âm k của phương trình tuyến tính: xA + kvA = xB + kvB.
• Nếu hai con có vận tốc bằng nhau, chúng chỉ có thể gặp nhau nếu bắt đầu cùng một vị trí.
• Nếu vận tốc khác nhau, cần kiểm tra hai điều: (1) Vị trí ban đầu và vận tốc phải có sự chênh lệch cho phép bắt kịp (cùng chiều và người sau nhanh hơn), (2) Thời gian gặp nhau (k) phải là một số nguyên.

Lỗi thường gặp

• Quên kiểm tra trường hợp vA = vB, dẫn đến lỗi chia cho 0 hoặc logic sai.
• Sai lệch trong việc kiểm tra k >= 0. Ví dụ: nếu dùng phép chia trực tiếp, cần đảm bảo phép chia giữa hai số âm vẫn cho kết quả dương. Việc dùng phép nhân (dx * dv < 0) để kiểm tra dấu là cách an toàn hơn.
• Bỏ qua điều kiện k phải là số nguyên (dư khác 0).