1 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bà Rịa – Vũng Tàu 2022 – 2023

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

Kỳ thi Học sinh giỏi (HSG) Tin học THCS luôn đòi hỏi học sinh không chỉ nắm vững tư duy thuật toán mà còn phải tối ưu hóa thời gian chạy và bộ nhớ. Dưới đây là lời giải chi tiết 3 bài toán trong đề thi HSG Tin học THCS tỉnh Bà Rịa – Vũng Tàu năm học 2022 – 2023 bằng ngôn ngữ Python, ứng dụng kỹ thuật đọc/ghi file siêu tốc với sys.stdin, phân tích độ phức tạp và chỉ ra các lỗi sai thường gặp khi làm bài.

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:

• 1 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bà Rịa – Vũng Tàu 2022 – 2023
• 2 Đề Thi & Đáp Án HSG Tin Học Lớp 9 Tỉnh Bình Định 2021 – 2022
• 3 Đề Thi [CÓ ĐÁP ÁN] HSG Tin Học Lớp 9 Tỉnh Bình Định 2022–2023
• 4 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Dương
• 5 Đề Học Lớp 9 Tỉnh Bình Phước 2018 – 2019

Đáp Án Bài 1: Tìm Ước Chung Lớn Nhất (CDIV.INP / CDIV.OUT)

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

Cho mảng A gồm N số nguyên dương (2 <= N <= 2 * 10^5, 1 <= a_i <= 10^6). Tìm hai số trong mảng sao cho Ước chung lớn nhất (GCD) của chúng là lớn nhất.

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

Thuật toán ngây thơ: Duyệt mọi cặp số (a_i, a_j) và tính gcd(a_i, a_j). Cách làm này tốn O(N^2 * log(max A)), với N = 2 * 10^5 sẽ bị quá thời gian (TLE).

Giải pháp tối ưu:

• Đếm tần suất xuất hiện của từng số trong mảng (tìm giá trị lớn nhất M = max A <= 10^6).

• Duyệt g ngược từ M giảm về 1 (với g là ứng viên cho GCD lớn nhất).

• Với mỗi g, đếm tổng số lượng phần tử trong mảng là bội số của g (các số g, 2g, 3g,…).

• Nếu tổng số lượng bội số >= 2, thì g chính là Ước chung lớn nhất của ít nhất một cặp số trong mảng. Vì duyệt từ lớn đến nhỏ, ngay khi tìm thấy g đầu tiên thỏa mãn, ta ghi nhận kết quả và dừng chương trình.

Độ phức tạp:

• Thời gian (Time Complexity): O(M * ln M + N) với M = max A. Tổng số lần duyệt các bội số là chuỗi Harmonic: M/1 + M/2 + … + 1 ≈ M * ln M. Số phép tính chưa tới 1.5 * 10^7, chạy dưới 0.3 giây.

• Không gian (Space Complexity): O(M + N) để lưu trữ mảng tần suất và danh sách dữ liệu.

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

• Quên xét trường hợp có 2 số giống nhau: Nếu mảng chứa hai số x bằng nhau, GCD của chúng chính là x. Mảng tần suất tan_suat cộng dồn đúng số lần xuất hiện của x giúp giải quyết triệt để lỗi này.

• Tạo mảng tần suất thiếu kích thước: Đặt kích thước mảng tần suất là gia_tri_lon_nhat + 1 để tránh lỗi IndexError khi truy cập tan_suat[gia_tri_lon_nhat].

4. Code Python Chuẩn

import sys

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

# Đọc toàn bộ dữ liệu đầu vào
du_lieu_vao = sys.stdin.read().split()

so_luong_phan_tu = int(du_lieu_vao[0])
danh_sach_so = [int(gia_tri) for gia_tri in du_lieu_vao[1:so_luong_phan_tu + 1]]

gia_tri_lon_nhat = max(danh_sach_so)
tan_suat = [0] * (gia_tri_lon_nhat + 1)

for so in danh_sach_so:
    tan_suat[so] += 1

uoc_chung_lon_nhat = 0

for g in range(gia_tri_lon_nhat, 0, -1):
    dem_boi_so = 0
    for boi_so in range(g, gia_tri_lon_nhat + 1, g):
        dem_boi_so += tan_suat[boi_so]
        if dem_boi_so >= 2:
            uoc_chung_lon_nhat = g
            break
    if uoc_chung_lon_nhat > 0:
        break

print(uoc_chung_lon_nhat)

Đáp Án Bài 2: Đố Vui Tin Học (GIFT.INP / GIFT.OUT)

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

Cho N phần quà có giá trị a_1, a_2,…, a_N (N <= 10^4, K <= 10^5, a_i <= 10^6). Cần chọn ra dãy con các phần quà theo đúng thứ tự chỉ số tăng dần sao cho giá trị phần quà sau lớn hơn phần quà trước ít nhất K đơn vị (a_next >= a_prev + K). Yêu cầu: Tìm số lượng phần quà chọn được nhiều nhất.

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

Đây là bài toán biến thể của Dãy con tăng dài nhất (LIS – Longest Increasing Subsequence) ứng dụng kỹ thuật Quy hoạch động (Dynamic Programming).

• Gọi bang_phu[i] là số lượng phần quà chọn được nhiều nhất khi phần quà cuối cùng được chọn là danh_sach_qua[i].

• Mối liên hệ truy hồi: bang_phu[i] = 1 + max({bang_phu[j] | 0 <= j < i và danh_sach_qua[i] - danh_sach_qua[j] >= K} U {0})

Độ phức tạp:

• Thời gian (Time Complexity): O(N^2). Với N <= 10^4, số vòng lặp tối đa khoảng 5 * 10^7 phép tính, chạy tốt trong thời gian cho phép.

• Không gian (Space Complexity): O(N) để lưu trữ mảng quy hoạch động và danh sách quà.

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

• Nhầm lẫn điều kiện chênh lệch: Điều kiện đề bài là a_i – a_j >= K (lớn hơn hoặc bằng K), không phải > K. Nhầm lẫn này sẽ làm mất đi các phương án chọn quà hợp lệ.

• Không khởi tạo mảng DP bằng 1: Mỗi phần quà bản thân nó luôn tạo thành một dãy gồm 1 phần quà. Do đó, tất cả các phần tử trong bang_phu phải khởi tạo giá trị ban đầu là 1.

4. Code Python Chuẩn

import sys

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

# Đọc toàn bộ dữ liệu đầu vào
du_lieu_vao = sys.stdin.read().split()

so_luong_qua = int(du_lieu_vao[0])
chech_lech_toi_thieu = int(du_lieu_vao[1])

danh_sach_qua = [int(gia_tri) for gia_tri in du_lieu_vao[2:so_luong_qua + 2]]

bang_phu = [1] * so_luong_qua
so_qua_lon_nhat = 1

for i in range(so_luong_qua):
    for j in range(i):
        if danh_sach_qua[i] - danh_sach_qua[j] >= chech_lech_toi_thieu:
            if bang_phu[j] + 1 > bang_phu[i]:
                bang_phu[i] = bang_phu[j] + 1
    if bang_phu[i] > so_qua_lon_nhat:
        so_qua_lon_nhat = bang_phu[i]

print(so_qua_lon_nhat)

Đáp Án Bài 3: Trò Chơi (GAME.INP / GAME.OUT)

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

Có N ô vuông vẽ thẳng hàng (2 <= N <= 10^5), mỗi ô i có giá trị năng lượng h_i (1 <= h_i <= 10^4). Một học sinh đứng ở ô 1 cần nhảy đến ô N. Từ ô i, có thể nhảy tới các ô i+1, i+2,…, i+K (1 <= K <= 100). Chi phí năng lượng cho 1 lần nhảy từ ô i đến ô j là |h_j – h_i|. Yêu cầu: Tìm tổng chi phí năng lượng nhỏ nhất để di chuyển từ ô 1 đến ô N.

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

Quy hoạch động:

• Gọi chi_phi[i] là chi phí năng lượng nhỏ nhất để đi từ ô 1 tới ô i.

• Ban đầu: chi_phi[1] = 0, các ô từ 2 đến N gán giá trị vô cùng (float('inf')).

• Công thức chuyển trạng thái: Với mỗi ô i từ 2 đến N, xét bước nhảy xuất phát từ các ô j trước đó (i – K <= j < i): chi_phi[i] = min_{j = max(1, i-K)}^{i-1} (chi_phi[j] + |h[i] - h[j]|)

Độ phức tạp:

• Thời gian (Time Complexity): O(N * K). Với N = 10^5 và K = 100, số phép tính khoảng 10^7, chạy dưới 0.2 giây.

• Không gian (Space Complexity): O(N) dùng để lưu mảng năng lượng và mảng chi phí.

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

• • Tràn chỉ số mảng (Index Out of Bounds): Khi i < K, vạch xuất phát i – K sẽ bị âm. Khắc phục bằng cách dùng max(1, i - K) để giữ cho chỉ số j không vượt quá biên trái (ô 1).

  • Quên giá trị tuyệt đối: Chi phí là |h_i – h_j|, nếu không dùng hàm abs() kết quả sẽ tính sai khi năng lượng ô sau nhỏ hơn ô trước.

4. Code Python Chuẩn

import sys

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

# Đọc toàn bộ dữ liệu đầu vào
du_lieu_vao = sys.stdin.read().split()

so_luong_o = int(du_lieu_vao[0])
khoang_cach_nhay_toi_da = int(du_lieu_vao[1])

nang_luong = [0] + [int(gia_tri) for gia_tri in du_lieu_vao[2:so_luong_o + 2]]

VO_CUNG = float('inf')
chi_phi = [VO_CUNG] * (so_luong_o + 1)
chi_phi[1] = 0

for i in range(2, so_luong_o + 1):
    o_bat_dau = max(1, i - khoang_cach_nhay_toi_da)
    chi_phi_nho_nhat = VO_CUNG
    for j in range(o_bat_dau, i):
        chi_phi_tam = chi_phi[j] + abs(nang_luong[i] - nang_luong[j])
        if chi_phi_tam < chi_phi_nho_nhat:
            chi_phi_nho_nhat = chi_phi_tam
    chi_phi[i] = chi_phi_nho_nhat

print(chi_phi[so_luong_o])

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

Tại sao không dùng lệnh input() mà phải dùng sys.stdin.read().split()?

Hàm input() đọc dữ liệu theo từng dòng và chạy rất chậm trong Python khi gặp tệp đầu vào chứa hàng chục nghìn dòng. Sử dụng sys.stdin.read().split() giúp nạp toàn bộ bộ dữ liệu vào bộ nhớ chỉ trong 1 lần đọc và tự động tách các số phân cách bởi khoảng trắng hoặc dòng mới, giúp tối ưu thời gian chạy gấp 10-20 lần.

Làm thế nào để khắc phục lỗi quá thời gian (TLE) khi giải đề bằng Python?

1. Tránh viết câu lệnh I/O (input, print) bên trong vòng lặp lớn.

2. Ép kiểu dữ liệu chuỗi sang số nguyên theo hàng loạt bằng List Comprehension thay cho vòng lặp for.

3. Ưu tiên sử dụng các cấu trúc dữ liệu và giải thuật có độ phức tạp thấp ($O(N)$ hoặc $O(N \log N)$) thay vì duyệt trâu $O(N^2)$.

Hashtags

#HSGTinHoc #PythonHSG #LuyenThiTinHoc #GiaiDeTinHoc #LapTrinhPython #QuyHoachDong

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!