NỘI DUNG

Phần đề thi

Câu 1. Số phong phú (6,0 điểm)

Masha là một cô bé thông minh và tinh nghịch sống cùng một chú gấu trong bộ phim hoạt hình nổi tiếng “Masha và chú gấu xiếc”. Tuy mới 6 tuổi nhưng Masha rất ham mê các con số. Hôm nay, gấu đưa ra một bài toán và hứa sẽ thưởng cho Masha một hộp kẹo nếu giải được bài toán đó.

Bài toán được phát biểu như sau: Số phong phú là số có tổng các ước nguyên dương (không kể chính nó) lớn hơn nó. Ví dụ: 12 là số phong phú vì tổng các ước nguyên dương của nó là 1 + 2 + 3 + 4 + 6 > 12. Cho hai số nguyên dương 𝑎, 𝑏 (a ≤ b) hỏi trong đoạn [𝑎, 𝑏] có bao nhiêu số phong phú?

Yêu cầu: Hãy đếm số lượng số phong phú trong đoạn [𝑎, 𝑏].

Dữ liệu: Vào từ tệp văn bản SOPP.INP gồm một dòng duy nhất chứa hai số 𝑎, 𝑏 cách nhau bởi dấu cách (0 ≤ a ≤ b ≤ 10⁵)

Kết quả: Ghi ra tệp văn bản SOPP.OUT một số là số lượng số phong phú trong đoạn [𝑎, 𝑏].

Ví dụ:

SOPP.INP	SOPP.OUT	Giải thích
1 25	4	Trong đoạn [1,25] có 4 số phong phú là: 12, 18, 20, 24

Ràng buộc:

Có50% số test ứng với 50% số điểm thỏa mãn 𝑎, 𝑏 ≤ 10³
50% số test còn lại ứng với 50% số điểm thỏa mãn 𝑎, 𝑏 ≤ 10⁵

Câu 2. Nhanh trí (6,0 điểm)

Người ta định nghĩa: Số đảo ngược của một số nguyên dương 𝑋 là số được tạo ra bằng cách viết các chữ số của nó theo chiều từ phải sang trái. Ví dụ: Số đảo ngược của số 537 là số 735.

Hùng và Nam là hai người bạn thân học cùng lớp, trong giờ ra chơi Hùng đố Nam: Cho hai số nguyên dương khác nhau 𝐴 và 𝐵, hỏi số nào có số đảo ngược lớn hơn?

Yêu cầu: Cho hai số nguyên dương khác nhau 𝐴 và 𝐵, hãy đưa ra số có số đảo ngược lớn hơn. Dữ liệu: Vào từ tệp văn bản BNGUOC.INP gồm hai số nguyên dương khác nhau 𝐴, 𝐵 cách nhau bởi một dấu cách (10 < 𝐴, 𝐵 ≤ 10²⁰).

Kết quả: Ghi ra tệp văn bản BNGUOC.OUT một số nguyên là kết quả của bài toán.

Ví dụ:

BNGUOC.INP	BNGUOC.OUT
532 117	117
122 109	109

Ràng buộc:

Có 60% số test tương ứng với 60% số điểm ứng với 𝐴, 𝐵 ≤ 10⁹.
30% số test tương ứng với 30% số điểm ứng với 𝐴, 𝐵 ≤ 10¹⁸.
10% số test tương ứng với 10% số điểm ứng với 𝐴, 𝐵 ≤ 10²⁰.

Câu 3. Khiêu vũ (5,0 điểm)

Ở thành phố Anpha xinh đẹp mọi người sống rất bình yên và hạnh phúc. Cuối tuần họ thường tổ chức các buổi tiệc khiêu vũ cho cư dân trong thành phố. Sắp tới họ sẽ tổ chức một buổi tiệc khiêu vũ mang tên “Vũ điệu mùa xuân”. Điều đặc biệt trong buổi tiệc này là chỉ những cặp đôi có chiều cao chênh lệch nhau đúng bằng số 𝑘 cho trước thì mới được khiêu vũ cùng nhau (không phân biệt giới tính). Có 𝑛 người tham gia buổi tiệc khiêu vũ, chiều cao của 𝑛 người này lần lượt là ℎ₁, ℎ₂, … , ℎ_𝑛.

Yêu cầu: Hãy đếm xem có tất cả bao nhiêu cặp đôi có thể khiêu vũ cùng nhau.

Dữ liệu: Vào từ tệp văn bản KHIEUVU.INP gồm 2 dòng

Dòng đầu ghi 2 số nguyên 𝑛, 𝑘 với 𝑛 là số lượng người tham gia buổi tiệc, 𝑘 là độ chênh lệch chiều cao yêu cầu (2 ≤ 𝑛 ≤ 10⁵, 0 ≤ 𝑘 ≤ 10⁹).
Dòng thứ 2 ghi 𝑛 số ℎ₁, ℎ₂, … , ℎ_𝑛 là chiều cao của 𝑛 người tham gia buổi tiệc (ℎ_𝑖≤ 10⁹). Các số trên một dòng cách nhau bởi dấu cách.

Kết quả: Ghi vào tệp văn bản KHIEUVU.OUT một số duy nhất là kết quả của bài toán. Ví dụ

KHIEUVU.INP	KHIEUVU.OUT	Giải thích
7 2 10 7 5 12 1 9 8	4	Có 4 cặp đôi có độ chênh lệch chiều cao bằng 2 là: (1,4), (1,7), (2,3), (2,6)

Ràng buộc:

Có 50% số test ứng với 50% số điểm thỏa mãn 𝑛 ≤ 10³, ℎ_𝑖≤ 10⁶.
50% số test còn lại ứng với 50% số điểm thỏa mãn 𝑛 ≤ 10⁵, ℎ_𝑖≤ 10⁹.

Câu 4. Dãy hình nón (3,0 điểm)

Một dãy số có độ dài (số phần tử) là 𝑚 được gọi là dãy hình nón nếu nó là một dãy gồm các số nguyên dương và có các đặc điểm sau:

Số lượng phần tử của dãy là một số lẻ (hay 𝑚 = 2 ∗ 𝑥 + 1);
Không có hai số nào đứng cạnh nhau trong dãy có giá trị bằng nhau;
𝑥 + 1 số đầu tiên của dãy là một dãy tăng;
𝑥 + 1 số cuối của dãy là một dãy giảm.

Ví dụ: Dãy 3 6 9 5 2 là một dãy hình nón có độ dài bằng 5; dãy 1 8 3 6 9 không phải là dãy hình nón.

Cho dãy 𝐴 gồm 𝑛 số nguyên dương 𝑎₁, 𝑎₂, … , 𝑎_𝑛. Một dãy con của 𝐴 là một dãy được tạo ra bằng cách lấy ra một số phần tử trong 𝐴 nhưng giữ nguyên thứ tự (các phần tử có thể không liên tiếp nhau).

Yêu cầu: Trong các dãy con của 𝐴 hãy tìm độ dài của dãy con hình nón dài nhất. Dữ liệu: Vào từ tệp văn bản SPSEQ.INP gồm 2 dòng:

Dòng đầu ghi số nguyên dương 𝑛 là độ dài dãy số ban đầu (𝑛 ≤ 10⁵).
Dòng thứ 2 chứa 𝑛 số nguyên dương 𝑎₁, 𝑎₂, … , 𝑎_𝑛 (𝑎_𝑖≤ 10⁹). Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả: Ghi ra tệp văn bản SPSEQ.OUT một số duy nhất là độ dài của dãy con hình nón dài nhất.

Ví dụ:

SPSEQ.INP	SPSEQ.OUT	Giải thích
7 5 4 5 9 7 4 5	5	Độ dài dãy con hình nón dài nhất là 5, có hai dãy là: 4 5 9 7 4 4 5 9 7 5

Ràng buộc:

Có 50% số test ứng với 50% số điểm thỏa mãn 𝑛 ≤ 20, 𝑎_𝑖≤ 10⁹.
50% số test còn lại ứng với 50% số điểm thỏa mãn 𝑛 ≤ 10⁵, 𝑎_𝑖≤ 10⁹.

Code tham khảo

Câu 1. Số phong phú (6,0 điểm)

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

// Hàm tính tổng các ước thực sự của một số
int sumProperDivisors(int n) {
    int sum = 1; // 1 luôn là ước thực sự
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) {
                sum += n / i;
            }
        }
    }
    return sum;
}

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

    int A, B;
    cin >> A >> B;

    int count = 0;
    for (int i = A; i <= B; ++i) {
        if (sumProperDivisors(i) > i) {
            count++;
        }
    }

    cout << count;

    return 0;
}

Câu 2. Nhanh trí (6,0 điểm)

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

// Hàm đảo ngược một số dưới dạng chuỗi
string reverseNumber(string s) {
    reverse(s.begin(), s.end());
    return s;
}

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

    string A, B;
    cin >> A >> B;

    string revA = reverseNumber(A);
    string revB = reverseNumber(B);

    if (revA > revB) {
        cout << A;
    } else {
        cout << B;
    }

    return 0;
}

Câu 3. Khiêu vũ (5,0 điểm)

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

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

    int n, k;
    cin >> n >> k;

    vector<int> heights(n);
    for (int &x : heights) {
        cin >> x;
    }

    // Sử dụng map để đếm số lần xuất hiện của mỗi chiều cao
    unordered_map<int, int> freq;
    int count = 0;

    for (int h : heights) {
        if (freq.count(h + k)) {
            count += freq[h + k];
        }
        if (freq.count(h - k)) {
            count += freq[h - k];
        }
        freq[h]++;
    }

    cout << count;

    return 0;
}

Câu 4. Dãy hình nón (3,0 điểm)

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

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }

    vector<int> inc(n, 1), dec(n, 1);

    // Tính mảng inc
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i]) {
                inc[i] = max(inc[i], inc[j] + 1);
            }
        }
    }

    // Tính mảng dec
    for (int i = n - 2; i >= 0; --i) {
        for (int j = n - 1; j > i; --j) {
            if (a[j] < a[i]) {
                dec[i] = max(dec[i], dec[j] + 1);
            }
        }
    }

    // Tìm kết quả
    int result = 1;
    for (int i = 0; i < n; ++i) {
        if (inc[i] > 1 && dec[i] > 1) {
            result = max(result, inc[i] + dec[i] - 1);
        }
    }

    cout << result;

    return 0;
}

CHÚC CÁC BẠN HỌC TỐT!

Lập trình C/C++

Đề thi học sinh giỏi môn Tin học tỉnh Yên Bái năm học 2022 – 2023 (có đáp án Full Code)

Phần đề thi

Câu 1. Số phong phú (6,0 điểm)

Câu 2. Nhanh trí (6,0 điểm)

Câu 3. Khiêu vũ (5,0 điểm)

Câu 4. Dãy hình nón (3,0 điểm)

Code tham khảo

Câu 1. Số phong phú (6,0 điểm)

Câu 2. Nhanh trí (6,0 điểm)

Câu 3. Khiêu vũ (5,0 điểm)

Câu 4. Dãy hình nón (3,0 điểm)

Đỗ Thành