Đề thi HSG môn Tin học tỉnh Thái Bình năm học 2024-2025

Phần 1. Đề thi

Bài 1. (5,0 điểm)  Số đặc biệt

Nam rất yêu thích các con số, đặc biệt là số nguyên tố. Một lần, trong giờ học, Nam nhận được câu hỏi của thầy như sau:

Số đặc biệt là một số nguyên dương mà có tổng các chữ số là một số nguyên tố.

Cho số nguyên dương N, hãy kiểm tra xem N có phải là số đặc biệt hay không?

Yêu cầu: Hãy lập trình giúp Nam giải bài toán trên.

Dữ liệu vào: Từ tệp văn bản SODB.INP gồm: Một dòng ghi số nguyên dương N (0 < N ≤ 10²⁵⁵).

Kết quả: Ghi vào tệp văn bản SODB.OUT một dòng gồm:

• Thông báo: "YES" nếu N là số đặc biệt.
• Thông báo: "NO" trong trường hợp ngược lại.

Ví dụ:

Ràng buộc:

• 50% số test có 0 < N ≤ 10⁹
• 40% số test có 10⁹ < N ≤ 10¹⁸
• 10% số test có 10¹⁸ < N ≤ 10²⁵⁵

Bài 2. (5,0 điểm) Vườn cây

Một mảnh vườn hình chữ nhật được chia thành các ô đất nhỏ gồm M hàng, N cột. Trên các ô đất đó, bác Ba trồng các loại cây ăn quả, cây ở hàng i, cột j có sản lượng quả là aᵢⱼ.

Mỗi đợt cuối năm, bác Ba muốn xem tổng sản lượng quả của các cây trên mỗi hàng dọc (cột) của khu vườn để bác có biện pháp chăm sóc hàng cây đó cho phù hợp.

Yêu cầu: Tính tổng sản lượng trái cây của các cây trên các hàng dọc (cột) trong khu vườn giúp bác Ba.

Dữ liệu vào: Từ tệp văn bản VUONCAY.INP có cấu trúc như sau:

• Dòng đầu chứa 2 số nguyên dương M, N (0 < M, N ≤ 10⁴).
• M dòng tiếp theo, mỗi dòng chứa N số nguyên không âm.
  • Giá trị ở dòng thứ i, cột thứ j là aᵢⱼ (1 ≤ i ≤ M; 1 ≤ j ≤ N) mô tả sản lượng tại thời điểm thống kê của cây được trồng ở ô hàng i, cột j của mảnh vườn.

Kết quả: Ghi vào tệp văn bản VUONCAY.OUT một dòng duy nhất chứa N số nguyên dương, mỗi số ghi cách nhau một khoảng trắng là tổng sản lượng trái cây của các cây trên các hàng dọc (cột) theo thứ tự.

Ví dụ:

Ràng buộc:

• 50% số test có 0 < M, N ≤ 10², 0 ≤ aᵢⱼ ≤ 10³.
• 40% số test có 10² < M, N ≤ 10³, 0 ≤ aᵢⱼ ≤ 10⁸.
• 10% số test có 10³ < M, N ≤ 10⁴, 0 ≤ aᵢⱼ ≤ 10¹².

Bài 3. (5,0 điểm) Dãy con thịnh vượng

Xét dãy số nguyên gồm nnn phần tử a1,a2,…,an​. Một dãy con liên tiếp của dãy a1,a2,…,an​ là dãy số nguyên có dạng ai,ai+1,…,aj, ​ (1≤i≤j≤n).

Một dãy con liên tiếp được gọi là dãy con thịnh vượng nếu tổng của các phần tử trong dãy con liên tiếp đó là lớn nhất trong tất cả các dãy con liên tiếp.

Yêu cầu: Cho trước một dãy số nguyên a1,a2,…,an​. Hãy tìm tổng của một dãy con thịnh vượng của dãy đã cho.

Ví dụ: Cho dãy 5, -3, 7, -9 . Một dãy con thịnh vượng có các phần tử là 5, -3, 7 . Khi đó, tổng của dãy con thịnh vượng là S = 5+3-7 = 9 là tổng các phần tử liên tiếp lớn nhất.

Dữ liệu vào:

Từ tệp văn bản DAYCON.INP gồm:

• Dòng đầu tiên chứa số nguyên dương nnn (1≤n≤10^6).
• Dòng thứ hai chứa n số nguyên a1,a2,…,an. các số trên cùng dòng viết cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản DAYCON.OUT một số duy nhất là tổng các phần tử của dãy con thịnh vượng của dãy đã cho.

Ví dụ:

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm của bài có n≤100.
• Có 30% số test tương ứng với 30% số điểm của bài có n≤5000.
• Có 20% số test tương ứng với 20% số điểm của bài có n≤10⁶.

Bài 4. (5,0 điểm) Mã mặt hàng

Trong hệ thống quản lý mặt hàng của một siêu thị, mã mặt hàng được lưu trữ dưới dạng một xâu ký tự hỗn hợp chỉ gồm các chữ cái (in hoa hoặc in thường) và chữ số (các số có mặt trong mã mặt hàng không vượt quá 10²⁵⁵).

Ví dụ, một mã mặt hàng có thể là: “789Abc123xyZ456defF789acb1235656”.

Hệ thống quản lý mặt hàng của siêu thị cần tìm ra số lớn nhất xuất hiện trong mã mặt hàng này để phục vụ công tác phân tích và quản lý của siêu thị.

Yêu cầu: Bằng khả năng lập trình của mình, em hãy giúp siêu thị thực hiện yêu cầu trên.

Dữ liệu vào: Từ tệp văn bản MAMH.INP gồm:

• Một xâu ký tự chỉ gồm chữ cái và số có độ dài không quá 10⁶. Xâu nhập vào đảm bảo luôn có chữ số.

Kết quả: Ghi ra tệp văn bản MAMH.OUT:

• Một số nguyên thỏa mãn yêu cầu đề bài.

Ví dụ:

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm của bài có độ dài của xâu không quá 255 ký tự và số xuất hiện trong xâu không quá 10⁹.
• Có 40% số test tương ứng với 40% số điểm của bài có độ dài của xâu không quá 10⁴ ký tự và số xuất hiện trong xâu không quá 10¹⁸.
• Có 10% số test tương ứng với 10% số điểm của bài có độ dài của xâu không quá 10⁶ và số xuất hiện trong xâu không quá 10²⁵⁵.

Phần 2. Code tham khảo (C++)

Bài 1. (5,0 điểm)  Số đặc biệt

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

// Hàm kiểm tra số nguyên tố
bool isPrime(int x) {
    if (x <= 1) return false; // Số nguyên tố phải lớn hơn 1
    for (int i = 2; i <= sqrt(x); ++i) {
        if (x % i == 0) return false; // Nếu x chia hết cho i, không phải số nguyên tố
    }
    return true;
}

int main() {
    // Mở file input và output
    freopen("SODB.INP", "r", stdin);
    freopen("SODB.OUT", "w", stdout);

    string N;
    cin >> N; // Đọc số N dưới dạng chuỗi

    int sumDigits = 0;
    for (char c : N) {
        sumDigits += c - '0'; // Chuyển ký tự thành số và cộng vào tổng
    }

    // Kiểm tra xem tổng các chữ số có phải là số nguyên tố hay không
    if (isPrime(sumDigits)) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

Bài 2. (5,0 điểm) Vườn cây

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

int main() {
    // Mở file input và output
    freopen("VUONCAY.INP", "r", stdin);
    freopen("VUONCAY.OUT", "w", stdout);

    int M, N;
    cin >> M >> N;

    // Khởi tạo mảng sumCol để lưu tổng sản lượng của từng cột
    vector<long long> sumCol(N, 0);

    // Đọc dữ liệu và tính tổng cho từng cột
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            long long value;
            cin >> value;
            sumCol[j] += value; // Cộng giá trị vào cột tương ứng
        }
    }

    // Ghi kết quả vào file output
    for (int j = 0; j < N; ++j) {
        cout << sumCol[j] << " ";
    }

    return 0;
}

Bài 3. (5,0 điểm) Dãy con thịnh vượng

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

int main() {
    // Mở file input và output
    freopen("DAYCON.INP", "r", stdin);
    freopen("DAYCON.OUT", "w", stdout);

    int n;
    cin >> n;

    long long current_sum = 0, max_sum = -1e18; // Khởi tạo max_sum rất nhỏ
    for (int i = 0; i < n; ++i) {
        long long value;
        cin >> value;

        // Cập nhật current_sum và max_sum theo thuật toán Kadane
        current_sum = max(value, current_sum + value);
        max_sum = max(max_sum, current_sum);
    }

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

    return 0;
}

Bài 4. (5,0 điểm) Mã mặt hàng

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

// Hàm so sánh hai số lớn dưới dạng chuỗi
bool isGreater(const string& a, const string& b) {
    if (a.length() != b.length()) {
        return a.length() > b.length(); // Số nào dài hơn thì lớn hơn
    }
    return a > b; // Nếu cùng độ dài, so sánh theo thứ tự từ điển
}

int main() {
    // Mở file input và output
    freopen("MAMH.INP", "r", stdin);
    freopen("MAMH.OUT", "w", stdout);

    string input;
    cin >> input; // Đọc chuỗi đầu vào

    string maxNumber = ""; // Lưu số lớn nhất
    string currentNumber = ""; // Lưu số đang xét

    for (char c : input) {
        if (isdigit(c)) {
            currentNumber += c; // Nếu là chữ số, thêm vào số hiện tại
        } else {
            if (!currentNumber.empty()) {
                // Nếu gặp ký tự không phải chữ số, kiểm tra số hiện tại
                if (isGreater(currentNumber, maxNumber)) {
                    maxNumber = currentNumber; // Cập nhật số lớn nhất
                }
                currentNumber.clear(); // Reset số hiện tại
            }
        }
    }

    // Kiểm tra số cuối cùng sau khi duyệt xong chuỗi
    if (!currentNumber.empty() && isGreater(currentNumber, maxNumber)) {
        maxNumber = currentNumber;
    }

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

    return 0;
}