Bài A: Chọn số may mắn

Áp dụng thuật toán tìm kiếm theo chiều sâu (DFS) để sinh các tổ hợp số thỏa mãn điều kiện. Điểm chú ý là cần thêm lệnh return khi kết thúc quá trình đệ quy:

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

int numbers[100], selected[10], visited[100];
int total;

void generate(int depth) {
    if (depth > 6) {
        for(int i = 1; i <= 6; i++) 
            cout << selected[i] << " ";
        cout << endl;
        return;
    }

    for(int i = 1; i <= total; i++) {
        if (!visited[i] && selected[depth-1] < numbers[i]) {
            selected[depth] = numbers[i];
            visited[i] = true;
            generate(depth + 1);
            visited[i] = false;
        }
    }
}

int main() {
    while(cin >> total) {
        if(total == 99) break;
        
        for(int i = 1; i <= total; i++) 
            cin >> numbers[i];
            
        if(total > 6 && total < 13) 
            generate(1);
        else
            cout << "ERROR\n\n";
    }
}

Bài B: Thống kê ký tự

Đếm tần suất xuất hiện của các chữ cái trong chuỗi đầu vào:

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

int main() {
    string input;
    while(getline(cin, input)) {
        int freq[26] = {0};
        
        for(char c : input) {
            if(islower(c)) 
                freq[c-'a']++;
        }
        
        for(int i = 0; i < 26; i++) {
            cout << char(i+'a') << ':' << freq[i] << endl;
        }
        cout << endl;
    }
    return 0;
}

Bài C: Bài toán đồng tiền vàng

Sử dụng quy hoạch động để giải bài toán biến thể của bài toán cái túi với đồng tiền có mệnh giá bình phương:

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

int main() {
    int coins[18], dp[301] = {0};
    dp[0] = 1;
    
    for(int i = 1; i <= 17; i++) {
        coins[i] = i * i;
        for(int j = coins[i]; j <= 300; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    
    int target;
    while(cin >> target) {
        cout << dp[target] << endl;
    }
    return 0;
}

Bài D: Bài toán 2004 vui vẻ

Áp dụng kiến thức lý thuyết số để tính tổng các ước của số A^B theo mô-đun 29:

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

const int MOD = 29;

int power(int base, int exp) {
    int result = 1;
    while(exp) {
        if(exp & 1) result = (long long)result * base % MOD;
        base = (long long)base * base % MOD;
        exp >>= 1;
    }
    return result;
}

int geometric_sum(int prime, int terms) {
    if(terms == 1) return 1;
    if(terms % 2 == 0) {
        return (power(prime, terms/2) + 1) * geometric_sum(prime, terms/2) % MOD;
    }
    return (geometric_sum(prime, terms-1) + power(prime, terms-1)) % MOD;
}

int main() {
    int B;
    while(cin >> B) {
        if(B == 0) break;
        int result = 1, temp = 2004;
        
        for(int i = 2; i*i <= temp; i++) {
            if(temp % i == 0) {
                int count = 0;
                while(temp % i == 0) {
                    count++;
                    temp /= i;
                }
                result = (long long)result * geometric_sum(i, count*B + 1) % MOD;
            }
        }
        if(temp > 1)
            result = (long long)result * geometric_sum(temp, B + 1) % MOD;
            
        cout << result << endl;
    }
    return 0;
}