Đề thi học sinh giỏi môn Tin học tỉnh Yên Bái năm học 2021-2022 (Full Code)

#include <iostream>
#include <string>
using namespace std;

int main() {
    freopen("CHAR.INP", "r", stdin);
    freopen("CHAR.OUT", "w", stdout);

    string St;
    getline(cin, St); // Đọc toàn bộ dòng từ file

    int countUppercase = 0; // Biến đếm số ký tự in hoa

    // Duyệt qua từng ký tự trong xâu St
    for (char c : St) {
        if (c >= 'A' && c <= 'Z') { // Kiểm tra ký tự in hoa
            countUppercase++;
        }
    }

    // Ghi kết quả vào file
    if (countUppercase > 0) {
        cout << countUppercase; // Ghi số lượng ký tự in hoa
    } else {
        cout << -1; // Không có ký tự in hoa
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // Mở file đầu vào và đầu ra
    freopen("GIFT.INP", "r", stdin);
    freopen("GIFT.OUT", "w", stdout);

    int n;
    cin >> n; // Đọc số lượng khách hàng

    // Vector lưu thông tin {giá trị quà, số hiệu khách hàng}
    vector<pair<int, int>> gifts(n);

    for (int i = 0; i < n; ++i) {
        cin >> gifts[i].first; // Giá trị quà
        gifts[i].second = i + 1; // Số hiệu khách hàng (1-based)
    }

    // Sắp xếp theo yêu cầu:
    // 1. Giảm dần theo giá trị quà
    // 2. Tăng dần theo số hiệu khách hàng nếu giá trị quà bằng nhau
    sort(gifts.begin(), gifts.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first != b.first) {
            return a.first > b.first; // Sắp xếp giảm dần theo giá trị quà
        }
        return a.second < b.second; // Sắp xếp tăng dần theo số hiệu khách hàng
    });

    // Ghi kết quả vào file
    for (int i = 0; i < n; ++i) {
        cout << gifts[i].second << " "; // In số hiệu khách hàng
    }

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Hàm sàng Eratosthenes để tìm các số nguyên tố
vector<bool> sieve(int maxLimit) {
    vector<bool> isPrime(maxLimit + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 và 1 không phải số nguyên tố
    for (int i = 2; i * i <= maxLimit; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxLimit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

int main() {
    // Mở file đầu vào và đầu ra
    freopen("PMIN.INP", "r", stdin);
    freopen("PMIN.OUT", "w", stdout);

    int T;
    cin >> T; // Số lượng câu hỏi

    // Sàng Eratosthenes để tìm các số nguyên tố
    const int MAX_LIMIT = 1e5;
    vector<bool> isPrime = sieve(MAX_LIMIT);

    while (T--) {
        int X, A, B;
        cin >> X >> A >> B;

        // Kiểm tra X có phải số nguyên tố không
        if (!isPrime[X]) {
            cout << 0 << "\n"; // Nếu X không phải số nguyên tố, kết quả là 0
            continue;
        }

        int count = 0; // Biến đếm số lượng số thỏa mãn

        // Duyệt qua các số trong đoạn [A, B]
        for (int n = A; n <= B; ++n) {
            if (n % X == 0) { // Kiểm tra n có chia hết cho X không
                bool isValid = true;
                // Kiểm tra không có số nguyên tố nào nhỏ hơn X mà n chia hết
                for (int p = 2; p < X; ++p) {
                    if (isPrime[p] && n % p == 0) {
                        isValid = false;
                        break;
                    }
                }
                if (isValid) {
                    count++;
                }
            }
        }

        // Ghi kết quả cho câu hỏi hiện tại
        cout << count << "\n";
    }

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Mở file đầu vào và đầu ra
    freopen("BUY.INP", "r", stdin);
    freopen("BUY.OUT", "w", stdout);

    int n, S;
    cin >> n >> S; // Đọc số món đồ và số tiền

    vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        cin >> prices[i]; // Đọc giá trị của từng món đồ
    }

    // Khởi tạo bảng DP
    const int INF = -1; // Giá trị khởi tạo cho trường hợp không thể mua
    vector<int> dp(S + 1, INF);
    dp[0] = 0; // Trường hợp tổng giá trị là 0, số món đồ là 0

    // Xây dựng bảng DP
    for (int i = 0; i < n; ++i) {
        int price = prices[i];
        for (int s = S; s >= price; --s) {
            if (dp[s - price] != INF && dp[s - price] + 1 > dp[s]) {
                dp[s] = dp[s - price] + 1;
            }
        }
    }

    // Ghi kết quả vào file
    cout << dp[S];

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Biến toàn cục để lưu kết quả tối ưu
int maxItems = -1;

// Hàm quay lui để tìm số món đồ nhiều nhất
void backtrack(int index, int currentSum, int count, const vector<int>& prices, int S) {
    // Nếu tổng hiện tại bằng S, cập nhật kết quả tối ưu
    if (currentSum == S) {
        maxItems = max(maxItems, count);
        return;
    }

    // Nếu vượt quá S hoặc đã duyệt hết danh sách, dừng lại
    if (currentSum > S || index >= prices.size()) {
        return;
    }

    // Thử chọn món đồ hiện tại
    backtrack(index + 1, currentSum + prices[index], count + 1, prices, S);

    // Thử bỏ qua món đồ hiện tại
    backtrack(index + 1, currentSum, count, prices, S);
}

int main() {
    // Mở file đầu vào và đầu ra
    freopen("BUY.INP", "r", stdin);
    freopen("BUY.OUT", "w", stdout);

    int n, S;
    cin >> n >> S; // Đọc số món đồ và số tiền

    vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        cin >> prices[i]; // Đọc giá trị của từng món đồ
    }

    // Gọi hàm quay lui để tìm số món đồ nhiều nhất
    backtrack(0, 0, 0, prices, S);

    // Ghi kết quả vào file
    cout << maxItems;

    return 0;
}