Editorial for gacho: Gà và Chó

Hiểu bài toán

Bài toán yêu cầu tìm số lượng gà (mỗi con 2 chân) và chó (mỗi con 4 chân) sao cho tổng số con là m và tổng số chân là n. Cho trước m và n, ta cần xác định xem có tồn tại nghiệm nguyên không. Nếu có, in ra số gà và số chó; ngược lại in -1.

Đặt:

• G: số gà
• C: số chó

Ta có hệ phương trình: 1) G + C = m 2) 2G + 4C = n

Từ (1) và (2), ta có thể suy ra các điều kiện cần và đủ cho nghiệm.

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

Cách Phương trình tuyến tính

#include <stdio.h>

int main()
{
    int m,n;
    scanf("%d %d",&m,&n);
    if(n<2*m || n>4*m)
    printf("-1");
    else if(n%2==0)
    printf("%d %d",(4*m-n)/2,(n-2*m)/2);
    else printf("-1");
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này giải trực tiếp hệ phương trình. Từ G + C = m => G = m - C Thay vào 2G + 4C = n => 2(m - C) + 4C = n => 2m + 2C = n => C = (n - 2m)/2 Sau đó G = m - C.

Các điều kiện:

1. n phải chia hết cho 2 (vì tổng số chân phải chẵn).
2. Số chó C >= 0 => n - 2m >= 0 => n >= 2m.
3. Số gà G >= 0 => m - C >= 0 => C <= m => (n - 2m)/2 <= m => n - 2m <= 2m => n <= 4m.

Code kiểm tra n%2==0 và khoảng range của n (2m <= n <= 4m) để đảm bảo nghiệm tồn tại là số nguyên không âm.

Cách Phương pháp tham số

#include <stdio.h>

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int chicken = 4*n - m;
    int dog = m - 2*n;
    if (chicken % 2 == 0 && dog % 2 == 0 && chicken >= 0 && dog >= 0) printf("%d %d",chicken/2,dog/2);
    else printf("-1");
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này tính toán các biến tạm từ m và n:

• Số gà (trước khi chia 2): chicken = 4n - m
• Số chó (trước khi chia 2): dog = m - 2n

Nếu chicken và dog đều chia hết cho 2 và dương thì chia cho 2 để ra đáp án.

Lý do: Ta đang xét các tích số (để đảm bảo nguyên). G = (4m - n)/2 C = (n - 2m)/2

Biến chicken thực chất là 2G, dog là 2C. Code kiểm tra tính chẵn và dương của các biến này.

Cách Phương pháp kiểm tra điều kiện số học

#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    if(n%2!=0){
        printf("-1");
        return 0;
    }
    int d=(n-2*m)/2;
    int p=m-d;
    if(d<0||p<0){
        printf("-1");
        return 0;
    }
    printf("%d %d",p,d);
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này chia làm 2 giai đoạn kiểm tra:

1. Kiểm tra tính hợp lệ về tính chẵn của n (n%2==0).
2. Tính trực tiếp số chó d = (n - 2m)/2 và số gà p = m - d (hoặc p = (4m - n)/2).
3. Kiểm tra tính dương của nghiệm (d >= 0 và p >= 0). Nếu cả hai đều dương, in kết quả.

Đây là cách diễn đạt trực quan nhất của công thức toán học.

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

Bài học kinh nghiệm

• Bài toán quy về giải hệ phương trình 2 ẩn với điều kiện nghiệm nguyên và không âm.
• Chỉ có 1 nghiệm duy nhất (nếu tồn tại) nên không cần dùng vòng lặp hay brute force.
• Điều kiện cần và đủ: n chia hết cho 2, 2m <= n <= 4m.

Lỗi thường gặp

• Quên kiểm tra n chia hết cho 2 (tổng số chân phải chẵn).
• Quên kiểm tra số gà hoặc số chó âm (ví dụ n < 2m hoặc n > 4m).
• Lỗi thứ tự in ra (gà trước, chó sau).
• Lỗi tràn số nếu dùng phép nhân lớn (với m, n <= 10^6 thì int 32-bit vẫn an toàn, nhưng cần cẩn thận nếu dùng phép nhân lớn hơn).