23 Đề Thi HSG Tin Học THCS Lời Giải Chi Tiết Huyện Cái Bè 2021-2022

Bạn đang ôn luyện thi Học sinh giỏi (HSG) Tin học THCS và muốn tìm đáp án chi tiết, tối ưu cho đề thi huyện Cái Bè năm học 2021 – 2022? Bài viết này chính là “cẩm nang” không thể bỏ qua dành cho bạn!

Hôm nay, chúng ta sẽ cùng nhau phân tích và giải trọn vẹn 4 bài tập trong đề thi bằng ngôn ngữ Python cực kỳ dễ hiểu, chuẩn hóa việc đọc/ghi tệp tệp input/output bằng thư viện sys chuyên nghiệp. Cùng bắt đầu ngay nhé!

Tổng Quan Đề Thi HSG Tin Học Cái Bè 2021 – 2022

• Thời gian làm bài: 150 phút

• Số lượng bài: 04 bài

• Hình thức đọc/ghi dữ liệu: Đọc từ file .INP và xuất ra file .OUT tương ứng.

Cấu Trúc Nhập/Xuất File Chuẩn Trong Python

Để chương trình Python đọc/ghi file tự động chuẩn như C++ khi nộp bài chấm tự động, chúng ta sử dụng kỹ thuật đổi hướng luồng dữ liệu chuẩn

Bài 1: Tổng Các Ước (USUM)

1. Đề bài & Phân tích

• Yêu cầu: Cho số nguyên $N$ ($1 \le N \le 10^9). Tìm tổng các ước số (mà ước số đó là số chính phương) của $N$.

• Định nghĩa: Một số là số chính phương nếu căn bậc hai của nó là một số nguyên (ví dụ: $1, 4, 9, 16, 25,…$).

• Ý tưởng thuật toán:

  1. Duyệt tìm các ước số $d$ của $N$. Vì $N \le 10^9$, ta chỉ duyệt $d$ từ $1$ đến $\sqrt{N}$ để đạt độ phức tạp $O(\sqrt{N}), đảm bảo không bị quá thời gian chạy (TLE).

  2. Với mỗi $d$ là ước của $N$:

     • Kiểm tra $d$ có phải là số chính phương hay không.

     • Kiểm tra ước tương ứng $N / d$ có phải là số chính phương hay không (lưu ý tránh tính trùng khi $d = N/d$).

  3. Cộng dồn vào biến tong. Nếu không tìm thấy ước chính phương nào (hoặc tổng bằng 0), xuất ra 0.

import sys
import math

sys.stdin = open('USUM.INP', 'r')
sys.stdout = open('USUM.OUT', 'w')

du_lieu = sys.stdin.read().split()

n = int(du_lieu[0])
tong_uoc_cp = 0
can_n = math.isqrt(n)

for d in range(1, can_n + 1):
    if n % d == 0:
        # Kiểm tra ước d
        if math.isqrt(d) ** 2 == d:
            tong_uoc_cp += d
        
        # Kiểm tra ước n // d
        uoc_con_lai = n // d
        if uoc_con_lai != d and math.isqrt(uoc_con_lai) ** 2 == uoc_con_lai:
            tong_uoc_cp += uoc_con_lai

print(tong_uoc_cp)

Bài 2: Dãy Ký Tự Số (STRING)

1. Đề bài & Phân tích

• Yêu cầu: Cho xâu ký tự $S$ (độ dài $\le 250$). Tìm chuỗi các ký tự số gõ liên tiếp dài nhất mà bé Bin đã gõ.

• Đầu ra:

  • Dòng 1: Độ dài của chuỗi số liên tiếp dài nhất.

  • Dòng 2: Chuỗi số liên tiếp đầu tiên đạt độ dài dài nhất đó.

• Ý tưởng thuật toán:

  1. Duyệt xâu $S$, gom các ký tự là chữ số (char.isdigit()) liên tiếp thành từng nhóm xâu số.

  2. Tìm độ dài lớn nhất của các nhóm xâu số này.

  3. Tìm xâu số đầu tiên đạt độ dài lớn nhất đó và in ra kết quả.

     import sys
     
     sys.stdin = open('STRING.INP', 'r')
     sys.stdout = open('STRING.OUT', 'w')
     
     s = sys.stdin.read().strip()
     
     danh_sach_so = []
     xau_hien_tai = ""
     
     for ch in s:
         if ch.isdigit():
             xau_hien_tai += ch
         else:
             if xau_hien_tai:
                 danh_sach_so.append(xau_hien_tai)
                 xau_hien_tai = ""
     
     if xau_hien_tai:
         danh_sach_so.append(xau_hien_tai)
     
     if not danh_sach_so:
         print(0)
     else:
         do_dai_max = max(len(xau) for xau in danh_sach_so)
         
         # Tìm xâu số đầu tiên đạt độ dài max
         xau_max_dau_tien = next(xau for xau in danh_sach_so if len(xau) == do_dai_max)
     
         print(do_dai_max)
         print(xau_max_dau_tien)
     
     

Bài 3: Tìm Vàng (GOLD)

1. Đề bài & Phân tích

• Yêu cầu: Cho xâu ký tự không quá 255 ký tự. Hãy tách các số tự nhiên xuất hiện trong xâu và tính tổng của chúng (“tổng số vàng”). Nếu trong xâu không có số nào, xuất ra 0.

• Ví dụ:

  • B3a34afc -> 3 + 34 = 37

  • 3a34-123-> 3 + 34 + 123 = 160

  • Virus -> 0

• Ý tưởng thuật toán:

  1. Duyệt từng ký tự trong xâu, nếu là chữ số thì ghép vào biến tạm.

  2. Khi gặp ký tự không phải chữ số, chuyển biến tạm thành số nguyên int() rồi cộng vào tổng.

  3. Cuối xâu, kiểm tra và cộng nốt số còn lại (nếu có).

import sys

sys.stdin = open('GOLD.INP', 'r')
sys.stdout = open('GOLD.OUT', 'w')

s = sys.stdin.read().strip()

tong_vang = 0
so_hien_tai = ""

for ch in s:
    if ch.isdigit():
        so_hien_tai += ch
    else:
        if so_hien_tai:
            tong_vang += int(so_hien_tai)
            so_hien_tai = ""

if so_hien_tai:
    tong_vang += int(so_hien_tai)

print(tong_vang)

Bài 4: Bộ Ba Hoàn Hảo (HOANHAO)

1. Đề bài & Phân tích

• Yêu cầu: Cho danh sách $N$ số nguyên ($N < 20$). Tìm tất cả các bộ ba số có tổng đúng bằng 100.

• Lưu ý quan trọng:

  • Không phân biệt vị trí các phần tử trong bộ ba (ví dụ bộ 10, 30, 60 hay 30, 60, 10 là như nhau).

  • In ra danh sách các bộ ba thỏa mãn.

• Ý tưởng thuật toán:

  • Vì N < 20 rất nhỏ, chúng ta có thể dùng 3 vòng lặp lồng nhau $O(N^3)$ hoặc dùng module itertools.combinations trong Python để duyệt qua tất cả các tổ hợp 3 phần tử cực kỳ ngắn gọn và chính xác.

import sys
from itertools import combinations

sys.stdin = open('HOANHAO.INP', 'r')
sys.stdout = open('HOANHAO.OUT', 'w')

du_lieu = sys.stdin.read().split()

n = int(du_lieu[0])
a = [int(x) for x in du_lieu[1:n+1]]

# Tạo tất cả các tổ hợp 3 số và kiểm tra tổng
for combo in combinations(a, 3):
    if sum(combo) == 100:
        print(combo[0], combo[1], combo[2])

Nếu bạn thấy hay ! xin bạn 1 phút ! vui lòng đánh giá 5 sao cho trang website của chúng tôi ! để có động lực làm thêm nhiều bài hay nữa ! cảm ơn quý khách nhé !

Thông Tin Liên Hệ:

• Website: vitinhtandan.com

• Hotline/Zalo: (0937.179.278)

• Địa chỉ: (Tổ 5, Ấp Tân Lược 1, xã Tân Hương, Đồng Tháp)

Chúc các bạn học sinh ôn luyện thật tốt và đạt kết quả cao nhất trong kỳ thi Học sinh giỏi Tin học lớp 9 sắp tới!

❓ FAQ – Câu Hỏi Thường Gặp (Hiển thị trên bài viết)

1. Tại sao cần dùng sys.stdin = open(...) và sys.stdout = open(...) khi giải đề thi HSG Tin học?

Trả lời: Trong các kỳ thi Học sinh giỏi Tin học, hệ thống chấm thi tự động (như Themis, CMS) sẽ đọc dữ liệu từ tệp .INP và ghi kết quả ra tệp .OUT. Việc sử dụng sys.stdin và sys.stdout giúp đổi hướng luồng vào/ra chuẩn của Python, giúp bạn sử dụng các lệnh quen thuộc như input() hay print() mà vẫn đọc/ghi file chính xác tuyệt đối.

2. Bài toán tìm ước chính phương (Bài 1 USUM) chạy tối ưu nhất như thế nào?

Trả lời: Thay vì duyệt từ $1$ đến $N$ tốn thời gian $O(N)$, chúng ta chỉ cần duyệt từ $1$ đến $\sqrt{N}$. Với mỗi ước $d$ tìm được, ta xác định thêm ước $N / d$, sau đó kiểm tra xem hai ước này có phải là số chính phương hay không bằng hàm math.isqrt(). Cách này giảm độ phức tạp xuống $O(\sqrt{N})$, đảm bảo chạy dưới 1 giây ngay cả khi $N = 10^9$.

3. Khi nào nên dùng itertools.combinations trong các bài toán liệt kê bộ ba?

Trả lời: Bạn nên dùng itertools.combinations(a, 3) khi bài toán yêu cầu tìm các bộ 3 phần tử phân biệt từ một danh sách và số lượng phần tử $N$ nhỏ (ví dụ $N < 20$). Hàm này giúp mã nguồn ngắn gọn, tối ưu và tránh được việc viết nhiều vòng lặp for lồng nhau.