Hiểu bài toán

Bài toán yêu cầu xác định con mèo nào (A hay B) sẽ đến được vị trí của con chuột C sớm hơn. Có hai con mèo A và B đang ở vị trí x và y trên trục tọa độ. Con chuột C ở vị trí z. Cả hai con mèo chạy với tốc độ như nhau. Để so sánh thời gian đến được chuột, ta chỉ cần so sánh khoảng cách từ vị trí của mỗi con mèo đến vị trí của con chuột vì tốc độ bằng nhau. Nếu A gần chuột hơn (khoảng cách nhỏ hơn), A bắt được trước. Nếu B gần hơn, B bắt được trước. Nếu cả hai cùng khoảng cách, chúng bắt được đồng thời.

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

Cách So sánh khoảng cách 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--) {
        int x, y, z;
        cin >> x >> y >> z;
        int da = abs(z - x);
        int db = abs(z - y);
        if (da < db) {
            cout << "Cat A\n";
        } else if (db < da) {
            cout << "Cat B\n";
        } else {
            cout << "Mouse C\n";
        }
    }

    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Với mỗi bộ dữ liệu đầu vào (x, y, z), ta tính khoảng cách từ A đến chuột là |z - x| và từ B đến chuột là |z - y|. Sử dụng hàm abs để lấy giá trị tuyệt đối. Sau đó so sánh hai khoảng cách này để in ra kết quả tương ứng: 'Cat A' nếu khoảng cách A nhỏ hơn, 'Cat B' nếu khoảng cách B nhỏ hơn, và 'Mouse C' nếu hai khoảng cách bằng nhau.

Cách Giải mã vị trí tương đối

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        int x, y, z;
        cin >> x >> y >> z;

        // Kiểm tra xem A hoặc B có nằm giữa hai người còn lại không
        // Hoặc đơn giản là so sánh vị trí
        if ((x < z && z < y) || (y < z && z < x)) {
             // Chuột nằm giữa A và B
             // Ai gần hơn?
             cout << (abs(x - z) < abs(y - z) ? "Cat A" : "Cat B") << "\n";
        } else if (x == z && y == z) {
             cout << "Mouse C\n";
        } else {
             // Chuột ở một đầu mút
             // Tính khoảng cách như thường
             cout << (abs(x - z) < abs(y - z) ? "Cat A" : (abs(x - z) > abs(y - z) ? "Cat B" : "Mouse C")) << "\n";
        }
    }
    return 0;
}

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

Cách này phân tích sâu hơn về mặt logic vị trí. Tuy nhiên, về bản chất vẫn là so sánh khoảng cách, nhưng được viết lại dưới dạng kiểm tra điều kiện vị trí tương đối (ví dụ: chuột nằm giữa A và B). Các giải pháp thực tế trong danh sách (Solution 1, 2, 3) đều sử dụng phương pháp tính khoảng cách tuyệt đối vì nó ngắn gọn và hiệu quả nhất. Cách tiếp cận này cho thấy có nhiều cách diễn đạt logic nhưng kết quả toán học (khoảng cách) là không đổi.

Cách Bộ lọc Logic

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        int x, y, z;
        cin >> x >> y >> z;

        int cata = abs(x - z);
        int catb = abs(y - z);

        if (cata > catb) cout << "Cat B\n";
        else if (cata < catb) cout << "Cat A\n";
        else cout << "Mouse C\n";
    }
    return 0;
}

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

Đây là một biến thể của cách tiếp cận đầu tiên, chỉ khác biệt trong thứ tự kiểm tra điều kiện if-else. Thay vì kiểm tra da < db trước, nó kiểm tra cata > catb (nếu A xa hơn, in B). Logic này hoàn toàn tương đương về mặt toán học. Code tối ưu hóa nhập/xuất bằng ios_base::sync_with_stdio(false); và cin.tie(nullptr); để tăng tốc độ chạy.

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

Bài học kinh nghiệm

• Vì tốc độ của cả hai con mèo là như nhau, ta chỉ cần so sánh khoảng cách (đường đi) chứ không cần tính thời gian thực sự. Khoảng cách là giá trị tuyệt đối của hiệu tọa độ (|z - x| và |z - y|).
• Bài toán này có độ phức tạp thời gian O(1) cho mỗi test case, vì nó chỉ bao gồm các phép toán số học cơ bản và so sánh.

Lỗi thường gặp

• Quên sử dụng hàm abs() (giá trị tuyệt đối) khi tính khoảng cách, dẫn đến kết quả sai nếu vị trí con mèo nằm bên phải hoặc trái của con chuột.
• Lỗi nhập xuất: Trong các bài toán có số lượng test case lớn (mặc dù t <= 100 ở đây), việc tắt đồng bộ hóa nhập xuất (ios::sync_with_stdio(false); cin.tie(nullptr);) là thói quen tốt để tránh trễ hạn.