Trang chủKhoá học lập trình Python20 Đề thi từ dễ đến nâng cao2 Đề Tỉnh Bình Định 2021 – 20222 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021–2022

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021–2022

By 31/08/2026 2 Đề Tỉnh Bình Định 2021 – 2022 Không có bình luận

Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Định (Năm Học 2021 – 2022) Bằng Python

Kỳ thi Học sinh giỏi (HSG) Tin học THCS tỉnh Bình Định năm học 2021 – 2022 mang đến cấu trúc đề thi đa dạng, đi từ lý thuyết Số học, thuật toán Tham ăn (Greedy), kỹ thuật Quay đúp / Chia đôi tập dữ liệu (Meet-in-the-middle) cho đến thuật toán Loang đồ thị (BFS). Bài viết này sẽ phân tích chi tiết lời giải 4 bài toán bằng Python, ứng dụng kỹ thuật I/O siêu tốc với sys.stdin, đồng thời chỉ ra các lỗi sai dễ mắc phải giúp học sinh tối ưu điểm số.

Trọn bộ các đề bao gồm các bí quyết thuật toán hay nhất chuẩn bị thi HSG Tin Học các Tỉnh:

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

Giá Trị Bổ Ích & Lợi Ích Lớn Khi Nghiên Cứu Đề Thi Này

Nghiên cứu bộ đề thi HSG Tin học THCS tỉnh Bình Định mang lại nhiều lợi ích quan trọng cho học sinh và phụ huynh định hướng chuyên Tin:

  • Làm chủ tư duy Số học căn bản: Học sinh hiểu rõ bản chất của một số có 3 ước nguyên dương thực chất là bình phương của một số nguyên tố (p^2), từ đó áp dụng thuật toán Sàng số nguyên tố Eratosthenes để giải quyết triệt me.

  • Thành thạo chiến lược Tham ăn (Greedy Strategy): Bài toán sắp xếp thời gian phát nhạc rèn luyện tư duy tối ưu tổng thời gian chờ (đưa các bài hát có thời lượng ngắn lên trước).

  • Nắm vững kỹ thuật nâng cao “Chia đôi tập dữ liệu” (Meet-in-the-middle): Bài toán chọn số với N <= 40 giúp học sinh vượt qua rào cản của thuật toán quay đúp thông thường O(2^N) để rút gọn thời gian tính toán xuống O(2^(N/2)).

  • Thành thạo thuật toán BFS tìm đường đi ngắn nhất: Học sinh nắm chắc kỹ thuật duyệt theo chiều rộng (BFS) trên lưới ô vuông để tìm lối thoát ngắn nhất và truy vết đường đi thực tế.

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022

Bài 1: Số Có Ba Ước Nguyên Dương (BAUOC.INP / BAUOC.OUT)

1. Tóm tắt đề bài

Cho số nguyên dương N. Đếm số lượng các số tự nhiên <= N có đúng 3 ước số nguyên dương phân biệt.

2. Phân tích thuật toán & Độ phức tạp

  • Tính chất số học: Một số nguyên dương X có đúng 3 ước số phân biệt (1, p, X) khi và chỉ khi X = p^2, trong đó p là một số nguyên tố.

  • Giải pháp:

    1. Yêu cầu X <= N tương đương p^2 <= N hay p <= căn bậc hai của N.

    2. Sử dụng thuật toán Sàng số nguyên tố (Sieve of Eratosthenes) đếm các số nguyên tố p <= căn bậc hai của N.

    3. Số lượng số nguyên tố p <= căn bậc hai của N chính là số lượng số có đúng 3 ước số <= N.

  • Độ phức tạp:

    • Thời gian (Time Complexity): O(căn(N) * log(log(căn(N)))). Rất nhanh, chạy dưới 0.1 giây ngay cả với N = 10^12.

    • Không gian (Space Complexity): O(căn(N)) để lưu trữ mảng đánh dấu sàng số nguyên tố.

3. Lỗi thường gặp & Cách khắc phục

  • Duyệt trâu đếm ước: Duyệt từng số từ 1 đến N rồi đếm số ước của từng số sẽ làm thuật toán rơi vào O(N * căn(N)), dẫn đến lỗi quá thời gian (TLE).

  • Tràn bộ nhớ: Nhầm lẫn khởi tạo mảng sàng kích thước N thay vì căn bậc hai của N. Với N lớn, mảng kích thước N sẽ làm tràn bộ nhớ (Memory Limit Exceeded).

4. Code Python Chuẩn

Python

import sys

# Đọc và ghi file tự động
sys.stdin = open('BAUOC.INP', 'r')
sys.stdout = open('BAUOC.OUT', 'w')

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

if du_lieu_vao:
    n = int(du_lieu_vao[0])
    
    # Tính căn bậc hai của N
    gioi_han_p = int(n ** 0.5)
    
    if gioi_han_p < 2:
        print(0)
    else:
        # Sàng số nguyên tố từ 2 đến gioi_han_p
        la_nguyen_to = [True] * (gioi_han_p + 1)
        la_nguyen_to[0] = la_nguyen_to[1] = False
        
        for i in range(2, int(gioi_han_p ** 0.5) + 1):
            if la_nguyen_to[i]:
                for j in range(i * i, gioi_han_p + 1, i):
                    la_nguyen_to[j] = False
                    
        dem_so_nguyen_to = sum(1 for i in range(2, gioi_han_p + 1) if la_nguyen_to[i])
        print(dem_so_nguyen_to)

Bài 2: Nghe Nhạc (NHAC.INP / NHAC.OUT)

1. Tóm tắt đề bài

Có N bài hát với thời lượng lần lượt là d1, d2, …, dN phút (mã số ban đầu từ 1 đến N). Máy phát quay băng từ đầu để phát bài thứ i. Giả sử tần suất nghe các bài hát là như nhau, tìm thứ tự ghi các bài hát lên băng sao cho tổng thời gian quay băng trong ngày là ít nhất.

2. Phân tích thuật toán & Độ phức tạp

  • Thời gian quay băng đến bài thứ k trên băng: Nếu thứ tự sắp xếp bài hát trên băng có thời lượng là t1, t2, …, tN, thì thời gian tìm và phát bài thứ k là S_k = t1 + t2 + … + tk.

  • Tổng thời gian quay băng: T = S1 + S2 + … + SN = (N)*t1 + (N-1)t2 + … + 1tN.

  • Chiến thuật Tham ăn (Greedy): Để T nhỏ nhất, các bài hát có thời lượng t_i nhỏ hơn phải được xếp trước (nhân với hệ số lớn hơn). Do đó, ta chỉ cần sắp xếp các bài hát theo thời lượng tăng dần.

  • Độ phức tạp:

    • Thời gian (Time Complexity): O(N log N) do thao tác sắp xếp mảng N phần tử.

    • Không gian (Space Complexity): O(N) để lưu mảng danh sách bài hát và thời gian dồn.

3. Lỗi thường gặp & Cách khắc phục

  • Quên lưu vết chỉ số ban đầu: Đề bài yêu cầu in ra mã số ban đầu của bài hát. Do đó cần lưu cặp (thời_lượng, mã_số_gốc) trước khi thực hiện sắp xếp.

  • Tính sai thời gian phát dồn: Dòng thứ i cần in ra thời gian quay băng S_i để tìm tới bài đó, chứ không phải chỉ in thời lượng gốc của riêng bài đó.

4. Code Python Chuẩn

Python

import sys

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

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

if du_lieu_vao:
    n = int(du_lieu_vao[0])
    thoi_luong = [int(x) for x in du_lieu_vao[1:n+1]]
    
    # Lưu cặp (thời lượng, mã số gốc 1-indexed)
    danh_sach_bai = []
    for i in range(n):
        danh_sach_bai.append((thoi_luong[i], i + 1))
        
    # Sắp xếp thời lượng tăng dần
    danh_sach_bai.sort(key=lambda x: x[0])
    
    tong_thoi_gian_ngay = 0
    thoi_gian_quay_don = 0
    
    ket_qua_bai = []
    for thoi_luong_bai, ma_so in danh_sach_bai:
        thoi_gian_quay_don += thoi_luong_bai
        tong_thoi_gian_ngay += thoi_gian_quay_don
        ket_qua_bai.append((ma_so, thoi_gian_quay_don))
        
    # In ra N dòng kết quả bài hát
    for ma_so, t_quay in ket_qua_bai:
        print(f"{ma_so} {t_quay}")
        
    # In tổng thời gian quay băng trong ngày
    print(tong_thoi_gian_ngay)

Bài 3: Chọn Số (CHONSO.INP / CHONSO.OUT)

1. Tóm tắt đề bài

Cho dãy số nguyên a1, a2, …, an và số nguyên M (5 <= n <= 40). Tìm dãy bit t1, t2, …, tn thuộc {0, 1} sao cho t1a1 + t2a2 + … + tn*an = M. Đề bài đảm bảo có nghiệm duy nhất.

2. Phân tích thuật toán & Độ phức tạp

  • Nhận xét giới hạn: n <= 40. Thuật toán Quay lui (Backtracking) thử mọi trường hợp 2^40 xấp xỉ 10^12 sẽ bị TLE.

  • Kỹ thuật Chia đôi tập dữ liệu (Meet-in-the-middle):

    1. Chia dãy a thành 2 nửa: nửa đầu N1 = n // 2 phần tử, nửa sau N2 = n – N1 phần tử.

    2. Sinh tất cả các tổng có thể tạo ra từ nửa đầu (2^N1 <= 2^20 xấp xỉ 10^6), lưu dưới dạng dictionary: tong_x -> chuoi_bit.

    3. Sinh các tổng từ nửa sau. Với mỗi tong_y tạo ra từ nửa sau, kiểm tra xem M – tong_y có tồn tại trong dictionary của nửa đầu hay không.

    4. Nếu tìm thấy, ghép chuỗi bit nửa đầu và nửa sau lại để thu được dãy bit kết quả.

  • Độ phức tạp:

    • Thời gian (Time Complexity): O(2^(N/2)). Với n = 40, 2^20 xấp xỉ 10^6 phép tính, chạy trong chưa đầy 0.3 giây.

    • Không gian (Space Complexity): O(2^(N/2)) để lưu dictionary nửa đầu.

3. Lỗi thường gặp & Cách khắc phục

  • Dùng mảng/list để tìm kiếm: Thay vì dùng dict hay hashmap có tốc độ tìm kiếm O(1), việc dùng list khiến độ phức tạp tăng lên O(2^(N/2) * 2^(N/2)) = O(2^N), làm mất tác dụng của thuật toán Meet-in-the-middle.

  • Sai thứ tự chuỗi bit: Cần chú ý giữ đúng vị trí chỉ số gốc của các phần tử khi chia đôi mảng.

4. Code Python Chuẩn

Python

import sys

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

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

if du_lieu_vao:
    n = int(du_lieu_vao[0])
    a = [int(x) for x in du_lieu_vao[1:n+1]]
    m = int(du_lieu_vao[n+1])
    
    n1 = n // 2
    n2 = n - n1
    
    a1 = a[:n1]
    a2 = a[n1:]
    
    # Sinh nửa đầu
    tap_nua_dau = {}
    for mask in range(1 << n1):
        tong_tam = 0
        bit_list = []
        for i in range(n1):
            if (mask >> i) & 1:
                tong_tam += a1[i]
                bit_list.append('1')
            else:
                bit_list.append('0')
        tap_nua_dau[tong_tam] = "".join(bit_list)
        
    # Sinh nửa sau và đối chiếu
    ket_qua = ""
    for mask in range(1 << n2):
        tong_tam = 0
        bit_list = []
        for i in range(n2):
            if (mask >> i) & 1:
                tong_tam += a2[i]
                bit_list.append('1')
            else:
                bit_list.append('0')
                
        can_tim = m - tong_tam
        if can_tim in tap_nua_dau:
            ket_qua = tap_nua_dau[can_tim] + "".join(bit_list)
            break
            
    print(ket_qua)

Bài 4: Rừng Nguy Hiểm (RUNG.INP / RUNG.OUT)

1. Tóm tắt đề bài

Một con hổ ở vị trí (x, y) trong khu rừng hình vuông N x N gồm các ô 0 (đi được) và 1 (chướng ngại vật/nguy hiểm). Mỗi bước hổ nhảy sang 1 trong 4 ô chung cạnh có địa hình cùng tính chất (cùng giá trị 0 hoặc 1 với ô đang đứng). Hổ thoát khỏi khu rừng khi di chuyển ra tới một ô nằm trên biên của lưới N x N. Yêu cầu: Tìm số bước ngắn nhất và in tọa độ đường đi để hổ thoát ra ngoài. Nếu không thoát được, in 0.

2. Phân tích thuật toán & Độ phức tạp

  • Thuật toán Duyệt theo chiều rộng (BFS): BFS là lựa chọn tối ưu tuyệt đối để tìm đường đi ngắn nhất trên đồ thị lưới không trọng số.

  • Quy trình thực hiện:

    1. Nếu vị trí xuất phát (x, y) đã nằm trên biên khu rừng, số bước ngắn nhất là 1 (chính vị trí đó).

    2. Khởi tạo hàng đợi queue chứa tọa độ điểm bắt đầu, mảng truy_vet[r][c] lưu ô cha và mảng khoang_cach[r][c].

    3. Duyệt 4 hướng (Đông, Tây, Nam, Bắc). Bước đi hợp lệ khi ô tiếp theo nằm trong bảng, chưa thăm, và có giá trị ô trùng với ô xuất phát (ma_tran[r_moi][c_moi] == ma_tran[x][y]).

    4. Khi chạm tới một ô nằm trên biên (r = 1 hoặc r = N hoặc c = 1 hoặc c = N), dừng BFS và quay ngược mảng truy_vet để thu được đường đi.

  • Độ phức tạp:

    • Thời gian (Time Complexity): O(N^2) vì mỗi ô trong lưới N x N chỉ được đưa vào hàng đợi BFS tối đa một lần. Với N <= 50, số phép tính chưa tới 2,500, chạy ngay lập tức.

    • Không gian (Space Complexity): O(N^2) để lưu ma trận và mảng truy vết.

3. Lỗi thường gặp & Cách khắc phục

  • Nhầm lẫn hệ tọa độ (1-based vs 0-based): Đề bài dùng tọa độ dòng/cột từ 1 đến N. Cần chuyển đổi tương thích trong code để tránh lỗi lệch chỉ số.

  • Quên điều kiện cùng loại địa hình: Đề bài ghi rõ “ô có cùng tính chất địa hình (giá trị) với ô nó đang đứng”. Quên điều kiện này sẽ dẫn đến kết quả tìm đường sai.

4. Code Python Chuẩn

Python

import sys
from collections import deque

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

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

if du_lieu_vao:
    n = int(du_lieu_vao[0])
    x_bd = int(du_lieu_vao[1]) - 1  # Chuyển về 0-indexed
    y_bd = int(du_lieu_vao[2]) - 1
    
    idx = 3
    luoi = []
    for i in range(n):
        hang = []
        for j in range(n):
            hang.append(int(du_lieu_vao[idx]))
            idx += 1
        luoi.append(hang)
        
    gia_tri_goc = luoi[x_bd][y_bd]
    
    # Các hướng di chuyển: Đông, Tây, Nam, Bắc
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    vong_lap_bfs = deque([(x_bd, y_bd)])
    truy_vet = {}
    truy_vet[(x_bd, y_bd)] = None
    
    o_dich = None
    
    # Kiểm tra ngay nếu điểm bắt đầu đã ở biên
    if x_bd == 0 or x_bd == n - 1 or y_bd == 0 or y_bd == n - 1:
        o_dich = (x_bd, y_bd)
    else:
        while vong_lap_bfs:
            r, c = vong_lap_bfs.popleft()
            
            if r == 0 or r == n - 1 or c == 0 or c == n - 1:
                o_dich = (r, c)
                break
                
            for k in range(4):
                nr, nc = r + dx[k], c + dy[k]
                if 0 <= nr < n and 0 <= nc < n:
                    if (nr, nc) not in truy_vet and luoi[nr][nc] == gia_tri_goc:
                        truy_vet[(nr, nc)] = (r, c)
                        vong_lap_bfs.append((nr, nc))
                        
    if o_dich is None:
        print(0)
    else:
        # Reconstruct đường đi
        duong_di = []
        hien_tai = o_dich
        while hien_tai is not None:
            duong_di.append(hien_tai)
            hien_tai = truy_vet[hien_tai]
            
        duong_di.reverse()
        
        print(1)
        print(len(duong_di))
        for r, c in duong_di:
            print(f"{r + 1} {c + 1}")

Câu Hỏi Thường Gặp (FAQ)

Làm sao để biết khi nào dùng thuật toán Sàng Eratosthenes hay duyệt kiểm tra số nguyên tố?

Khi bài toán yêu cầu đếm hoặc xử lý các số nguyên tố trong phạm vi liên tục lên đến 10^6 hoặc 10^7, hãy luôn dùng Sàng Eratosthenes. Duyệt kiểm tra từng số chỉ phù hợp khi số lượng truy vấn nhỏ hoặc giá trị N cực lớn không thể lưu mảng.

Kỹ thuật Meet-in-the-middle có thể áp dụng cho các dạng bài nào?

Kỹ thuật này áp dụng hiệu quả cho các bài toán kết hợp tập hợp, chọn tập con có tổng bằng M, hoặc tìm chuỗi thao tác ngắn nhất mà N nằm trong khoảng 30 đến 40.

giải đề thi hsg tin học lớp 9, đề thi hsg tin học bình định, sàng số nguyên tố python, tham ăn greedy python, meet in the middle python, bfs tìm đường đi ngắn nhất python

Hashtags

#HSGTinHoc #PythonHSG #LuyenThiTinHoc #GiaiDeTinHoc #LapTrinhPython #BFS #MeetInTheMiddle

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é !

Vui lòng Chấm điểm 5 sao trang cho bài viết hay !

 

 

2 Khóa Học Tin Học Online Thầy Dân Luyện Thi Chuyên Tin Tin Văn Phòng Cấp Tốc

2 Khóa Học Tin Học Online Thầy Dân Luyện Thi Chuyên Tin Tin Văn Phòng Cấp Tốc

📞 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!

5/5 - (1 bình chọn)

TÁC GIẢ

thanhcong@kiennhan

Mình rất đam mê về máy vi tính và máy in. Và mình đã đeo đuổi ước mơ và làm việc về máy vi tính mới đây mà đã 15 năm. Mình thích chia sẻ mọi kiến thức và kinh nghiệm mà mình có được cho tất cả các bạn ! Trong khi mình viết nếu có điều gì thiếu sót mong các bạn thông cảm cho mình nhé ! Mình Cám ơn trước !

CÁC BÀI VIẾT KHÁC CỦA thanhcong@kiennhan

MỜI BẠN ĐẶT CÂU HỎI ? MÌNH SẼ GIẢI ĐÁP HẾT !