Đề số 01 - Ôn thi HSG Tin học THCS

BỘ ĐỀ ÔN THI HỌC SINH GIỎI TIN HỌC THCS Bumbii Academy

ĐỀ SỐ 01 Thời gian làm bài: 150 phút
4 bài, tổng 20 điểm

---

Đề mẫu có lời giải

Đây là đề được mở miễn phí lời giải để thầy cô và các em xem cách trình bày. Lời giải của các đề khác có trong bộ tài liệu đầy đủ (có phí).

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
1	Bãi giữ xe	XEDAP.*	XEDAP.INP	XEDAP.OUT	4
2	Con số chủ đạo	CHUDAO.*	CHUDAO.INP	CHUDAO.OUT	5
3	Mật mã chia hết cho 5	SOCHIA5.*	SOCHIA5.INP	SOCHIA5.OUT	5
4	Tỉa hàng cây	TIACAY.*	TIACAY.INP	TIACAY.OUT	6

Dấu * được thay bằng py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng.

Bài 1. Bãi giữ xe (4 điểm)

Bãi giữ xe của trường chỉ nhận hai loại xe: xe đạp (2 bánh) và xe đạp ba bánh (3 bánh) của các em mẫu giáo. Cuối buổi, bác bảo vệ đếm được tất cả có m chiếc xe và n bánh xe.

Yêu cầu: Hãy cho biết trong bãi có bao nhiêu chiếc xe đạp và bao nhiêu chiếc xe ba bánh.

Dữ liệu vào: Từ file văn bản XEDAP.INP gồm một dòng chứa hai số nguyên dương m, n.

Kết quả: Ghi ra file văn bản XEDAP.OUT:

• Nếu tìm được, ghi hai số nguyên lần lượt là số xe đạp và số xe ba bánh, cách nhau một dấu cách (có thể có loại xe nào đó bằng 0).
• Nếu bác bảo vệ đã đếm nhầm (không có cách nào thỏa mãn), ghi -1.

Ví dụ:

XEDAP.INP	XEDAP.OUT	Giải thích
5 12	3 2	3 xe đạp và 2 xe ba bánh: 3 + 2 = 5 xe, 3 × 2 + 2 × 3 = 12 bánh.
4 7	-1	4 xe có ít nhất 8 bánh, không thể chỉ có 7 bánh.

Ràng buộc:

• Có 60% số test với 1 ≤ m, n ≤ 10⁵.
• Có 40% số test với 1 ≤ m, n ≤ 10¹⁸.

Bài 2. Con số chủ đạo (5 điểm)

Con số chủ đạo của một số nguyên dương được tính như sau: cộng các chữ số của số đó, nếu kết quả có nhiều hơn một chữ số thì lại cộng các chữ số của kết quả, cứ thế cho đến khi chỉ còn một chữ số. Chữ số cuối cùng chính là con số chủ đạo.

Ví dụ: 59 → 5 + 9 = 14 → 1 + 4 = 5, vậy con số chủ đạo của 59 là 5.

Yêu cầu: Cho dãy n số nguyên dương a₁, a₂, …, a_n. Hãy tìm con số chủ đạo xuất hiện nhiều lần nhất trong dãy (nếu có nhiều con số như vậy thì chọn con số nhỏ nhất), và liệt kê các số trong dãy có con số chủ đạo đó.

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

• Dòng đầu tiên chứa số nguyên dương n.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n, các số cách nhau một dấu cách.

Kết quả: Ghi ra file văn bản CHUDAO.OUT gồm:

• Dòng đầu tiên ghi hai số: con số chủ đạo tìm được và số lượng số trong dãy có con số chủ đạo đó.
• Dòng thứ hai ghi các số trong dãy có con số chủ đạo đó, theo đúng thứ tự trong dãy.

Ví dụ:

CHUDAO.INP	CHUDAO.OUT	Giải thích
5 23 7 59 26 50	5 3 23 59 50	Con số chủ đạo của các số lần lượt là 5, 7, 5, 8, 5. Số 5 xuất hiện 3 lần.

Ràng buộc:

• Có 50% số test với n ≤ 1000, a_i ≤ 10⁹.
• Có 50% số test với n ≤ 10⁵, a_i ≤ 10¹⁸.

Bài 3. Mật mã chia hết cho 5 (5 điểm)

Bạn Nam nhận được một mảnh giấy ghi xâu kí tự S chỉ gồm chữ cái in thường (a…z) và chữ số (0…9). Trong S, mỗi đoạn gồm các chữ số đứng liền nhau (không thể kéo dài thêm về hai phía) được gọi là một số của xâu. Ví dụ, xâu hsg8ngay21thang4nam2023 có các số 8, 21, 4, 2023.

Để mở khóa két bí mật, Nam cần trả lời hai câu hỏi:

1. Tổng T của tất cả các số trong xâu S là bao nhiêu?
2. Viết liên tiếp tất cả các chữ số của S theo đúng thứ tự, ta được dãy chữ số a. Xóa đi một số chữ số của a (giữ nguyên thứ tự các chữ số còn lại) để được số b lớn nhất chia hết cho 5. Số b là bao nhiêu?

Dữ liệu vào: Từ file văn bản SOCHIA5.INP gồm một dòng chứa xâu S. Mỗi số trong S có không quá 9 chữ số.

Kết quả: Ghi ra file văn bản SOCHIA5.OUT gồm hai dòng:

• Dòng thứ nhất ghi tổng T (nếu S không có chữ số nào thì T = 0).
• Dòng thứ hai ghi số b (không ghi các chữ số 0 vô nghĩa ở đầu). Nếu không có cách nào để được một số chia hết cho 5 thì ghi -1.

Ví dụ:

SOCHIA5.INP	SOCHIA5.OUT	Giải thích
hsg8ngay21thang4nam2023	2056 821420	T = 8 + 21 + 4 + 2023 = 2056. Dãy chữ số là 82142023; giữ lại 821420 (xóa 2, 3 ở cuối).
lop9a2x7	18 -1	T = 9 + 2 + 7 = 18. Dãy chữ số 927 không có chữ số 0 hay 5 nên không tạo được số chia hết cho 5.

Ràng buộc: Gọi L là độ dài xâu S.

• Có 30% số test với L ≤ 16.
• Có 30% số test với L ≤ 1000.
• Có 40% số test với L ≤ 10⁶.

Bài 4. Tỉa hàng cây (6 điểm)

Dọc con đường vào trường có n cây xanh, cây thứ i cao h_i mét. Trước mùa mưa bão, nhà trường thuê một xe tỉa cành. Xe có một lưỡi cắt nằm ngang được đặt ở độ cao H mét (H là số nguyên không âm): khi xe chạy dọc hàng cây, mọi phần cây cao hơn H đều bị cắt đi, cây nào không cao hơn H thì giữ nguyên. Như vậy cây cao h_i > H cho ra h_i − H mét cành.

Nhà trường cần thu được ít nhất k mét cành để làm phân bón, nhưng muốn các cây được giữ lại càng cao càng tốt.

Yêu cầu: Tìm độ cao H lớn nhất để tổng số mét cành cắt được không nhỏ hơn k.

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

• Dòng đầu tiên chứa hai số nguyên dương n và k.
• Dòng thứ hai chứa n số nguyên dương h₁, h₂, …, h_n.

Dữ liệu bảo đảm k ≤ h₁ + h₂ + … + h_n.

Kết quả: Ghi ra file văn bản TIACAY.OUT một số nguyên duy nhất là độ cao H tìm được.

Ví dụ:

TIACAY.INP	TIACAY.OUT	Giải thích
4 7 20 15 10 17	15	Đặt H = 15 cắt được (20 − 15) + (17 − 15) = 7 mét. Nếu H = 16 chỉ cắt được 4 + 1 = 5 mét, không đủ.

Ràng buộc:

• Có 40% số test với n ≤ 1000, h_i ≤ 1000.
• Có 60% số test với n ≤ 10⁵, h_i ≤ 10⁹.

Hướng dẫn giải và đáp án

Bài 1. Bãi giữ xe (4 điểm)

Hướng dẫn giải

Gọi x là số xe đạp, y là số xe ba bánh. Ta có hệ:

• x + y = m
• 2x + 3y = n

Lấy phương trình thứ hai trừ 2 lần phương trình thứ nhất: y = n − 2m, suy ra x = m − y = 3m − n. Bài toán có nghiệm khi và chỉ khi x ≥ 0 và y ≥ 0.

• Cách vét cạn (đạt 60%): thử mọi x từ 0 đến m, tính y = m − x rồi kiểm tra 2x + 3y = n. Độ phức tạp O(m), không chạy kịp khi m tới 10¹⁸.
• Cách dùng công thức (đạt 100%): O(1).

Lưu ý với C++: m, n tới 10¹⁸ nên phải dùng long long; giá trị 2m tới 2 × 10¹⁸ vẫn nằm trong giới hạn của long long (khoảng 9,2 × 10¹⁸).

Python

with open("XEDAP.INP") as f:
    m, n = map(int, f.read().split())

# x xe đạp, y xe ba bánh: x + y = m, 2x + 3y = n
y = n - 2 * m
x = m - y

with open("XEDAP.OUT", "w") as f:
    if x >= 0 and y >= 0:
        f.write(f"{x} {y}\n")
    else:
        f.write("-1\n")

C++

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

int main() {
    freopen("XEDAP.INP", "r", stdin);
    freopen("XEDAP.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long m, n;
    cin >> m >> n;
    // x xe đạp, y xe ba bánh: x + y = m, 2x + 3y = n
    long long y = n - 2 * m;
    long long x = m - y;
    if (x >= 0 && y >= 0)
        cout << x << " " << y << "\n";
    else
        cout << -1 << "\n";
    return 0;
}

Bài 2. Con số chủ đạo (5 điểm)

Hướng dẫn giải

Cách làm trực tiếp là cộng chữ số lặp lại cho đến khi còn một chữ số. Cách này đủ nhanh cho cả hai subtask, vì một số tới 10¹⁸ chỉ có 19 chữ số.

Có một tính chất đẹp hơn: một số và tổng các chữ số của nó có cùng số dư khi chia cho 9. Vì vậy con số chủ đạo của x > 0 chính là 1 + (x − 1) mod 9 (kết quả nằm trong 1…9).

Sau khi có con số chủ đạo của từng số, dùng mảng dem[1..9] để đếm. Duyệt c từ 1 đến 9 và chỉ cập nhật khi dem[c] lớn hơn hẳn, để khi bằng nhau thì giữ con số nhỏ hơn. Cuối cùng duyệt lại dãy để in các số có con số chủ đạo đó theo đúng thứ tự.

Độ phức tạp O(n).

Python

with open("CHUDAO.INP") as f:
    data = f.read().split()
n = int(data[0])
a = data[1:1 + n]

# Con số chủ đạo của x > 0 chính là 1 + (x - 1) mod 9
cs = [1 + (int(x) - 1) % 9 for x in a]

dem = [0] * 10
for c in cs:
    dem[c] += 1
best = 1
for c in range(2, 10):
    if dem[c] > dem[best]:
        best = c

with open("CHUDAO.OUT", "w") as f:
    f.write(f"{best} {dem[best]}\n")
    f.write(" ".join(a[i] for i in range(n) if cs[i] == best) + "\n")

C++

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

int main() {
    freopen("CHUDAO.INP", "r", stdin);
    freopen("CHUDAO.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    vector<int> cs(n);
    int dem[10] = {0};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        // Con số chủ đạo của x > 0 chính là 1 + (x - 1) mod 9
        cs[i] = 1 + (a[i] - 1) % 9;
        dem[cs[i]]++;
    }
    int best = 1;
    for (int c = 2; c <= 9; c++)
        if (dem[c] > dem[best]) best = c;
    cout << best << " " << dem[best] << "\n";
    bool first = true;
    for (int i = 0; i < n; i++)
        if (cs[i] == best) {
            if (!first) cout << " ";
            cout << a[i];
            first = false;
        }
    cout << "\n";
    return 0;
}

Bài 3. Mật mã chia hết cho 5 (5 điểm)

Hướng dẫn giải

Câu 1. Duyệt xâu, dùng biến so để ghép các chữ số liên tiếp: gặp chữ số thì so = so * 10 + chữ số, gặp chữ cái thì cộng so vào tổng rồi đặt lại so = 0. Mẹo: thêm một kí tự không phải chữ số vào cuối xâu để số cuối cùng cũng được cộng.

Câu 2. Số chia hết cho 5 phải tận cùng bằng 0 hoặc 5. Gọi p là vị trí cuối cùng của chữ số 0 hoặc 5 trong dãy a.

• Nếu không có vị trí nào như vậy thì đáp án là -1.
• Ngược lại, đáp án là toàn bộ phần đầu a[0..p], bỏ các chữ số 0 ở đầu.

Vì sao? Mọi số tạo được đều là một dãy con của a[0..p], mà xóa bớt chữ số thì số chỉ có thể nhỏ đi hoặc giữ nguyên. Vậy giữ lại nhiều nhất có thể là tốt nhất.

Bẫy thường gặp:

• Phần đầu toàn chữ số 0 (ví dụ a = 0071): đáp án là 0, không phải xâu rỗng.
• Dãy a rất dài (tới 10⁶ chữ số): không đổi a ra số nguyên, mà in ra dạng xâu.

Độ phức tạp O(L).

Python

with open("SOCHIA5.INP") as f:
    s = f.read().strip()

# Câu 1: tổng các số (dãy chữ số liên tiếp dài nhất) trong S
tong = 0
so = 0
for ch in s + "#":
    if ch.isdigit():
        so = so * 10 + int(ch)
    else:
        tong += so
        so = 0

# Câu 2: a là dãy tất cả chữ số của S. Kết quả phải tận cùng bằng 0 hoặc 5.
# Lấy trọn phần đầu của a đến vị trí 0/5 cuối cùng là tốt nhất, vì xóa thêm
# chữ số nào cũng làm số nhỏ đi.
a = "".join(ch for ch in s if ch.isdigit())
p = max(a.rfind("0"), a.rfind("5"))
if p == -1:
    b = "-1"
else:
    b = a[:p + 1].lstrip("0") or "0"

with open("SOCHIA5.OUT", "w") as f:
    f.write(f"{tong}\n{b}\n")

C++

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

int main() {
    freopen("SOCHIA5.INP", "r", stdin);
    freopen("SOCHIA5.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;

    // Câu 1: tổng các số (dãy chữ số liên tiếp dài nhất) trong S
    long long tong = 0, so = 0;
    for (char ch : s + "#") {
        if (isdigit(ch))
            so = so * 10 + (ch - '0');
        else {
            tong += so;
            so = 0;
        }
    }

    // Câu 2: a là dãy tất cả chữ số của S. Kết quả phải tận cùng bằng 0 hoặc 5.
    // Lấy trọn phần đầu của a đến vị trí 0/5 cuối cùng là tốt nhất, vì xóa thêm
    // chữ số nào cũng làm số nhỏ đi.
    string a;
    for (char ch : s)
        if (isdigit(ch)) a += ch;
    int p = -1;
    for (int i = 0; i < (int)a.size(); i++)
        if (a[i] == '0' || a[i] == '5') p = i;

    cout << tong << "\n";
    if (p == -1) {
        cout << -1 << "\n";
    } else {
        int i = 0;
        while (i < p && a[i] == '0') i++;   // bỏ các số 0 ở đầu
        cout << a.substr(i, p - i + 1) << "\n";
    }
    return 0;
}

Bài 4. Tỉa hàng cây (6 điểm)

Hướng dẫn giải

Gọi f(H) là tổng số mét cành cắt được khi đặt lưỡi cắt ở độ cao H. Khi H tăng thì f(H) giảm (không tăng). Ta cần H lớn nhất có f(H) ≥ k, đây là dạng điển hình của chặt nhị phân theo kết quả.

• Cách thử lần lượt (đạt 40%): cho H giảm dần từ max(h_i) cho đến khi f(H) ≥ k. Mỗi lần tính f mất O(n), tổng O(n × max h_i), chỉ chạy kịp khi h_i ≤ 1000.
• Chặt nhị phân (đạt 100%):
  • Giữ hai đầu lo, hi với f(lo) ≥ k và f(hi) < k. Ban đầu lo = 0 (đề bảo đảm f(0) = tổng h_i ≥ k) và hi = max(h_i) (vì f(max h_i) = 0).
  • Mỗi bước thử mid ở giữa, rồi thu hẹp một nửa.
  • Cần khoảng 30 bước, mỗi bước O(n), tổng O(n log max h_i).

Lưu ý với C++: tổng f(H) có thể tới 10⁵ × 10⁹ = 10¹⁴, phải dùng long long.

Python

with open("TIACAY.INP") as f:
    data = list(map(int, f.read().split()))
n, k = data[0], data[1]
h = data[2:2 + n]


def cat_duoc(H):
    """Tổng số mét cành cắt được khi đặt máy tỉa ở độ cao H."""
    return sum(x - H for x in h if x > H)


# cat_duoc(H) giảm dần khi H tăng -> chặt nhị phân tìm H lớn nhất có cat_duoc(H) >= k
lo, hi = 0, max(h)          # cat_duoc(0) >= k (đề bảo đảm), cat_duoc(max(h)) = 0 < k
while hi - lo > 1:
    mid = (lo + hi) // 2
    if cat_duoc(mid) >= k:
        lo = mid
    else:
        hi = mid

with open("TIACAY.OUT", "w") as f:
    f.write(f"{lo}\n")

C++

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

int n;
long long k;
vector<long long> h;

// Tổng số mét cành cắt được khi đặt máy tỉa ở độ cao H
long long catDuoc(long long H) {
    long long s = 0;
    for (long long x : h)
        if (x > H) s += x - H;
    return s;
}

int main() {
    freopen("TIACAY.INP", "r", stdin);
    freopen("TIACAY.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    h.resize(n);
    for (auto &x : h) cin >> x;

    // catDuoc(H) giảm dần khi H tăng -> chặt nhị phân tìm H lớn nhất có catDuoc(H) >= k
    long long lo = 0, hi = *max_element(h.begin(), h.end());
    while (hi - lo > 1) {
        long long mid = (lo + hi) / 2;
        if (catDuoc(mid) >= k)
            lo = mid;
        else
            hi = mid;
    }
    cout << lo << "\n";
    return 0;
}

Do số lượng đề bài, bài giải và bộ test rất nhiều nên tác giả đang kiểm tra từng bước. Thầy cô và các em học sinh nếu thấy sai sót xin vui lòng liên hệ tác giả qua Facebook hoặc Zalo (0972465159). Xin chân thành cảm ơn.