Nhận xét

• Nếu ~a < b~, ta luôn có thể đổi trạng thái một ấm đun nước bất kỳ.
• Nếu ~a = b~, ta xét các trường hợp sau:
  • ~a = n~: Khi đó ta chỉ có thể bật tất cả các đèn hoặc tắt tất cả các đèn.
  • ~a < n~ và ~a~ lẻ: Dùng 3 thao tác có thể bật / tắt một đèn bất kỳ. Do đó kết quả luôn là YES.
  • ~a < n~ và ~a~ chẵn: Chỉ có thể bật tất cả các đèn nếu số đèn tắt ban đầu là chẵn.

Cài đặt

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

#define REP(i,a) for(int i=0,_##i##_a=(a); i<_##i##_a; i++)

int main() {
    int ntest; cin >> ntest;
    while (ntest--) {
        int n, a, b; cin >> n >> a >> b;
        assert(a <= b && b <= n);
        string s; cin >> s;

        auto can = [&] () {
            if (b > a) return true;
            int cnt = 0;
            REP(i,n) cnt += s[i] == '0';
            if (n == a) {
                return cnt % a == 0;
            }
            if (a % 2 == 1) return true;

            return cnt % 2 == 0;
        };

        cout << (can() ? "YES" : "NO") << '\n';
    }
    return 0;
}