Hướng dẫn giải

Cho ~n~ số 1 và ~m~ số 2, cần đặt dấu +/- trước mỗi số để tổng bằng 0. Bài chỉ cần một nhận xét về tính chẵn lẻ.

Sub 1: Vét cạn — ~O(n \cdot m)~ mỗi bộ dữ liệu, dùng khi ~(n+1)(m+1) \le 10^6~

Thử mọi cách chọn ~x~ số 1 mang dấu + (còn ~n-x~ số mang dấu -) và ~y~ số 2 mang dấu + (còn ~m-y~ số mang dấu -), kiểm tra tổng ~(2x-n) + 2(2y-m)~ có bằng 0 không. Nếu chỉ nộp sub này: đúng 1/20 test (các test còn lại quá lớn nên bị quá thời gian).

Sub 2: Nhận xét chẵn lẻ — ~O(1)~ mỗi bộ dữ liệu

Các số 2 luôn đóng góp một số chẵn, nên tổng bằng 0 đòi hỏi ~n~ chẵn. Khi ~n~ chẵn và ~n > 0~, ta chia các số 1 thành hai nhóm bằng nhau (dấu + và -), rồi xử lý các số 2: nếu ~m~ chẵn thì chia đôi; nếu ~m~ lẻ thì dùng hai số 1 cùng dấu để bù cho số 2 dư (ví dụ ~+1+1-2~). Khi ~n = 0~ thì cần ~m~ chẵn. Bẫy: ~n = 0~ và ~m~ lẻ thì đáp án là NO dù ~n~ chẵn. Nếu chỉ nộp sub này: đúng 20/20 test.

Chương trình hoàn chỉnh

Hàm main đọc ~t~, với mỗi bộ dữ liệu nhỏ thì gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

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

int t, n, m;

// Sub 1: vét cạn — thử mọi số lượng số 1 mang dấu '+' và số 2 mang dấu '+'
void sub1() {
    for (int x = 0; x <= n; x++)
        for (int y = 0; y <= m; y++) {
            // x số 1 dương, n-x số 1 âm, y số 2 dương, m-y số 2 âm
            if ((x - (n - x)) + 2 * (y - (m - y)) == 0) {
                puts("YES");
                return;
            }
        }
    puts("NO");
}

// Sub 2: nhận xét — n phải chẵn; nếu n = 0 thì m phải chẵn
void sub2() {
    if (n % 2 == 0 && (n > 0 || m % 2 == 0)) puts("YES");
    else puts("NO");
}

int main() {
    freopen("EXP.INP", "r", stdin);
    freopen("EXP.OUT", "w", stdout);
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        if ((long long)(n + 1) * (m + 1) <= 1000000) sub1();
        else sub2();
    }
}