Editorial for VO 16 Bài 4 - Trò chơi với những viên bi


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Dựa theo luật chơi có thể phát hiện ra một bất biến: "tính chẵn lẻ của số bi màu đỏ là không đổi". Vì vậy nến kết quả của bài toán chính là số bi màu đỏ modulo 2!!! Để giải quyết trọn vẹn bài toán ta chỉ cần để ý là dãy ~A~ được sinh ra theo quy tắc trong đề tuẩn hoàn theo chu kỳ ~(D + 1)~, nhờ vậy có thể tính ra số bi đỏ trong ~O(D)~.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, d;
int a[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int nTest; cin >> nTest;
    while (nTest--) {
        cin >> n >> d;
        for (int i = 1; i <= d; ++i) cin >> a[i];
        for (int i = d + 1; i <= d + 1; ++i) {
            int x = 0;
            for (int j = i - 1; j >= i - d; --j)
                x ^= a[j];
            a[i] = x;
        }
        int one = 0;
        for (int i = 1; i <= d + 1; ++i) one ^= a[i] == 1;
        int loop = d + 1;
        int cnt = n / loop;
        if (cnt % 2 == 0) one = 0;
        int mod = n % loop;
        if (mod != 0) {
            for (int i = 1; i <= mod; ++i)
                one ^= a[i] == 1;
        }
        cout << one << '\n';
    }
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.