Bài A: Xử Lý Số Nguyên

Yêu cầu: Với số nguyên n và số lần thao tác tối đa max_ops, mỗi lần có thể bình phương hoặc lấy căn bậc hai làm tròn xuống. Đếm số lượng giá trị khác nhau có thể tạo ra.

Phương pháp: Phép bình phương luôn sinh ra giá trị mới. Khi thực hiện căn bậc hai, nếu kết quả không phải số nguyên thì mỗi lần thao tác tiếp theo có thể tạo ra giá trị mới bằng cách bình phương rồi căn. Số giá trị mới được tính bằng số lần thao tác còn lại.

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

void solve() {
    int n, max_ops;
    cin >> n >> max_ops;
    if (n == 1) {
        cout << 1;
        return;
    }
    int distinct_count = 1;
    for (int op = 0; op < max_ops; op++) {
        int root = sqrt(n);
        if (root == 1) break;
        if (root * root != n) {
            distinct_count += (max_ops - op - 1);
        }
        n = root;
        distinct_count++;
    }
    cout << distinct_count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Bài D: Trò Chơi Đá Cầu

Yêu cầu: Với n viên đá, mỗi lượt chọn 1-3 viên. Người bắt đầu (brz) thắng nếu chọn viên đá cuối. Xác định liệu brz có thắng được không.

Phương pháp: Trò chơi thuộc dạng nim với quy tắc đặc biệt. Khi số đá chia hết cho 4, người đi đầu luôn thua do đối thủ có thể điều chỉnh số đá để giữ trạng thái chia hết cho 4.

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

void solve() {
    int stone_count;
    cin >> stone_count;
    cout << "lose";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Bài E: Tính Tổng Bit

Yêu cầu: Với chuỗi nhị phân a độ dài n, xây dựng chuỗi b độ dài k sao cho k bit đầu của tổng số 1 trong a+b (biểu diễn nhị phân) khớp với b.

Phương pháp: Duyệt qua tất cả số lượng bit 1 có thể (0 đến k). Với mỗi giá trị i, tính tổng bit 1 = count_1 + i, chuyển thành nhị phân, so sánh k bit đầu với i. Chọn chuỗi b nhỏ nhất thỏa mãn.

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

void solve() {
    int n, k, count_1 = 0;
    cin >> n >> k;
    string a;
    cin >> a;
    for (char c : a) if (c == '1') count_1++;
    
    string result = string(k, '2');
    for (int ones = 0; ones <= k; ones++) {
        int total = count_1 + ones;
        string bin_repr;
        while (total) {
            bin_repr += (total & 1) ? '1' : '0';
            total >>= 1;
        }
        while (bin_repr.size() < k) bin_repr += '0';
        reverse(bin_repr.begin(), bin_repr.end());
        if (bin_repr.size() >= k && bin_repr.substr(0, k) == string(ones, '1')) {
            result = min(result, bin_repr.substr(0, k));
        }
    }
    cout << (result == string(k, '2') ? "None" : result);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Bài L: Tạo Dãy Dấu Ngoặc

Yêu cầu: Với chuỗi dấu ngoặc hợp lệ, đếm số cách sinh chuỗi mới bằng hai thao tác: thêm () vào cuối hoặc thêm () vào một đoạn hợp lệ. Kết quả modulo 998244353.

Phương pháp: Dùng stack để đánh dấu vị trí. Với mỗi cặp ngoặc, ghi nhận loại (liên tiếp hoặc không). Đảo ngược dãy đánh dấu, nhân kết quả với chỉ số hiện tại khi gặp loại không liên tiếp.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

void solve() {
    string s;
    cin >> s;
    stack<int> st;
    vector<int> op_types;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') st.push(i);
        else {
            if (st.top() == i - 1) op_types.push_back(1);
            else op_types.push_back(2);
            st.pop();
        }
    }
    reverse(op_types.begin(), op_types.end());
    long long ways = 1;
    for (int i = 0; i < op_types.size(); i++) {
        if (op_types[i] == 2) {
            ways = (ways * (i + 1)) % MOD;
        }
    }
    cout << ways;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}