ĐỀ THI HSG MÔN TIN HỌC THÀNH PHỐ HÀ NỘI NĂM HỌC 2023-2024 (Có đáp án Full Code)

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

int main() {
    // Chuyển hướng nhập xuất sang file
    freopen("HOAHOC.INP", "r", stdin);
    freopen("HOAHOC.OUT", "w", stdout);

    // Đọc dữ liệu đầu vào
    unsigned long long A, B;
    cin >> A >> B;

    // Tính số mol Fe3O4 tối đa từ Fe và O2
    unsigned long long mol_from_Fe = A / 3;   // Số mol Fe3O4 từ Fe
    unsigned long long mol_from_O2 = B / 2;  // Số mol Fe3O4 từ O2

    // Số mol Fe3O4 tối đa là giá trị nhỏ hơn giữa hai giá trị trên
    unsigned long long mol_Fe3O4 = min(mol_from_Fe, mol_from_O2);

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

    return 0;
}

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

// Hàm tính GCD (Ước chung lớn nhất) bằng thuật toán Euclid
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Hàm kiểm tra xem một số có phải là số nguyên tố hay không
bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// Hàm tìm ước chung lớn thứ hai
long long secondLargestDivisor(long long n) {
    // Tìm ước nguyên tố nhỏ nhất của n
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return n / i; // Trả về n chia cho ước nguyên tố nhỏ nhất
        }
    }
    // Nếu không tìm thấy ước nào khác ngoài 1 và chính nó (n là số nguyên tố)
    return 1;
}

int main() {
    // Chuyển hướng nhập xuất sang file
    freopen("UOCCHUNG.INP", "r", stdin);
    freopen("UOCCHUNG.OUT", "w", stdout);

    long long A, B;
    cin >> A >> B;

    // Tính GCD của A và B
    long long g = gcd(A, B);

    // Tìm ước chung lớn thứ hai
    long long result = secondLargestDivisor(g);

    // In kết quả
    cout << result;

    return 0;
}

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

// Cấu trúc lưu thông tin về mỗi kỹ năng
struct Skill {
    long long s; // Giá trị s_i
    long long e; // Giá trị e_i
};

int main() {
    // Chuyển hướng nhập xuất sang file
    freopen("TROCHOI.INP", "r", stdin);
    freopen("TROCHOI.OUT", "w", stdout);

    // Đọc dữ liệu đầu vào
    long long N, M;
    cin >> N >> M;

    vector<Skill> skills(N);
    for (int i = 0; i < N; ++i) {
        cin >> skills[i].s >> skills[i].e;
    }

    // Sắp xếp các kỹ năng theo thứ tự giảm dần của (s_i + e_i)
    sort(skills.begin(), skills.end(), [&](const Skill &a, const Skill &b) -> bool {
        return (a.s + a.e) > (b.s + b.e);
    });

    long long result = 0;

    if (M <= N) {
        // Trường hợp M <= N: Chọn M kỹ năng đầu tiên
        for (int i = 0; i < M; ++i) {
            result += skills[i].s + skills[i].e;
        }
    } else {
        // Trường hợp M > N: Tăng cấp tất cả N kỹ năng ít nhất một lần
        for (int i = 0; i < N; ++i) {
            result += skills[i].s + skills[i].e;
        }

        // Sắp xếp các kỹ năng theo thứ tự giảm dần của e_i
        sort(skills.begin(), skills.end(), [&](const Skill &a, const Skill &b) -> bool {
            return a.e > b.e;
        });

        // Phân bổ M - N lần tăng cấp còn lại vào các kỹ năng có e_i lớn nhất
        long long remaining_upgrades = M - N;
        for (int i = 0; i < min(remaining_upgrades, (long long)N); ++i) {
            result += skills[i].e;
        }
    }

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

    return 0;
}

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

// Hằng số giới hạn
const int MAX_N = 1000;
const int MAX_K = 1e9;

int main() {
    // Chuyển hướng nhập xuất sang file
    freopen("ROBOT.INP", "r", stdin);
    freopen("ROBOT.OUT", "w", stdout);

    // Đọc dữ liệu đầu vào
    int N, M, Q, K;
    cin >> N >> M >> Q >> K;

    // Đọc bảng A và tính A[i][j] % K
    vector<vector<int>> modValues(N + 1, vector<int>(M + 1));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            long long value;
            cin >> value;
            modValues[i][j] = value % K;
        }
    }

    // Lưu trữ kết quả cho từng truy vấn
    vector<int> results(Q);

    // Đọc và xử lý từng truy vấn
    for (int q = 0; q < Q; ++q) {
        int X;
        cin >> X;

        // Khởi tạo bảng quy hoạch động
        vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));

        // Điền bảng DP
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= M; ++j) {
                // Số lượng ô thỏa mãn điều kiện tại (i, j)
                int count = (modValues[i][j] == X) ? 1 : 0;

                // Lấy giá trị lớn nhất từ các ô liền kề
                dp[i][j] = count;
                if (i > 1 && j > 1) {
                    dp[i][j] += max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                } else if (i > 1) {
                    dp[i][j] += dp[i-1][j];
                } else if (j > 1) {
                    dp[i][j] += dp[i][j-1];
                }
            }
        }

        // Kết quả cho truy vấn hiện tại
        results[q] = dp[N][M];
    }

    // Ghi kết quả ra file
    for (int q = 0; q < Q; ++q) {
        cout << results[q] << "\n";
    }

    return 0;
}

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

// Hằng số MOD
const int MOD = 1e9 + 7;

// Cấu trúc Disjoint Set Union (DSU)
struct DSU {
    vector<int> parent;
    vector<int> size;

    DSU(int n) : parent(n + 1), size(n + 1, 1) {
        for (int i = 0; i <= n; ++i) {
            parent[i] = i;
        }
    }

    // Tìm gốc của tập hợp chứa x
    int find_set(int x) {
        if (parent[x] != x) {
            parent[x] = find_set(parent[x]);
        }
        return parent[x];
    }

    // Gộp hai tập hợp chứa x và y
    void union_set(int x, int y) {
        int root_x = find_set(x);
        int root_y = find_set(y);
        if (root_x != root_y) {
            if (size[root_x] < size[root_y]) {
                swap(root_x, root_y);
            }
            parent[root_y] = root_x;
            size[root_x] += size[root_y];
        }
    }

    // Lấy kích thước của tập hợp chứa x
    int get_size(int x) {
        return size[find_set(x)];
    }
};

int main() {
    // Chuyển hướng nhập xuất sang file
    freopen("DOANTOT.INP", "r", stdin);
    freopen("DOANTOT.OUT", "w", stdout);

    // Đọc dữ liệu đầu vào
    int N;
    cin >> N;

    // Lưu trữ các đoạn thẳng
    vector<pair<int, int>> segments(N);
    for (int i = 0; i < N; ++i) {
        cin >> segments[i].first >> segments[i].second;
    }

    // Khởi tạo DSU
    DSU dsu(N);

    // Sắp xếp các đoạn thẳng theo thứ tự tăng dần của Lᵢ và Rᵢ
    sort(segments.begin(), segments.end());

    // Lưu trữ kết quả
    vector<long long> results(N);

    // Biến lưu tích độ tốt hiện tại
    long long product = 1;

    // Duyệt qua từng đoạn thẳng
    for (int i = 0; i < N; ++i) {
        int L = segments[i].first;
        int R = segments[i].second;

        // Kiểm tra xem đoạn thẳng này có thể gộp vào tập hợp nào không
        bool merged = false;
        for (int j = 0; j < i; ++j) {
            int prev_L = segments[j].first;
            int prev_R = segments[j].second;

            // Nếu có điểm chung, gộp hai tập hợp
            if (!(R < prev_L || L > prev_R)) {
                dsu.union_set(i, j);
                merged = true;
            }
        }

        // Nếu không thể gộp, tạo tập hợp mới
        if (!merged) {
            product = (product * 1) % MOD;
        } else {
            // Cập nhật tích độ tốt
            product = 1;
            for (int j = 0; j <= i; ++j) {
                if (dsu.find_set(j) == j) {
                    product = (product * dsu.get_size(j)) % MOD;
                }
            }
        }

        // Lưu kết quả
        results[i] = product;
    }

    // Ghi kết quả ra file
    for (int i = 0; i < N; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}