4 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Dương
Đề thi Học sinh giỏi Tin học THCS tỉnh Bình Dương năm học 2021 – 2022 mang cấu trúc đề thi thực chiến cực hay, lồng ghép các bài toán logic gắn liền với thực tế như tối ưu hóa trọng lượng hàng hóa, xử lý chuỗi mẫu lặp, mô phỏng hành trình di chuyển thu chi và bài toán quy hoạch động/tham ăn chọn lịch trình tối ưu.
Bài viết này cung cấp lời giải trọn bộ 4 câu hỏi, phân tích bản chất thuật toán, đi kèm mã nguồn Python chuẩn thi đấu
4 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Dương
Tư duy tối ưu hóa vét cạn (Complete Search): Giải quyết bài toán chọn gói hàng tối ưu bằng thuật toán duyệt 2 vòng lặp kết hợp cắt nhánh thông minh.
Xử lý chuỗi và phát hiện chu kỳ: Rèn luyện kỹ năng tìm xâu con mẫu lặp ngắn nhất trong dãy ký tự bằng thuật toán duyệt qua các ước số của độ dài chuỗi.
Mô phỏng bài toán kinh tế & di chuyển: Nắm vững tư duy duyệt trạng thái, quản lý số dư ngân sách và tính toán tổng quãng đường di chuyển ngắn nhất.
Thuật toán Tham ăn (Greedy Algorithm) chọn lịch: Làm chủ dạng bài tập chọn nhiều khoảng thời gian không chồng chồng lấp (Interval Scheduling Problem) điển hình trong các kỳ thi học sinh giỏi.
4 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Dương
Mẹ nhờ Bo chở hàng hóa bằng thùng chứa tối đa N kg. Cửa hàng chỉ đóng gói hàng thành 2 loại hộp: loại A kg và loại B kg (1 <= A, B, N <= 1000). Yêu cầu: Tìm số kg hàng hóa lớn nhất mà Bo có thể chở trong một chuyến sao cho tổng khối lượng không vượt quá N kg.
Giải pháp:
Giả sử Bo chọn x hộp loại A và y hộp loại B.
Khối lượng tổng là x * A + y * B <= N.
Do N <= 1000, ta dùng 2 vòng lặp: duyệt số lượng hộp A từ 0 đến N // A, và số lượng hộp B từ 0 đến N // B.
Cập nhật khối lượng lớn nhất đạt được gần với N nhất.
Độ phức tạp:
Thời gian (Time Complexity): O((N/A) * (N/B)) <= O(N^2), với N = 1000 chỉ tốn vài nghìn phép tính (dưới 0.001 giây).
Không gian (Space Complexity): O(1).
Python
import sys
sys.stdin = open('Chohang.inp', 'r')
sys.stdout = open('Chohang.out', 'w')
du_lieu = sys.stdin.read().split()
N, A, B = map(int, du_lieu[:3])
khoi_luong_max = 0
for x in range(N // A + 1):
for y in range(N // B + 1):
tong = x * A + y * B
if tong <= N and tong > khoi_luong_max:
khoi_luong_max = tong
print(khoi_luong_max)
Bo kết vòng tay từ một dãy các hạt mẫu lặp đi lặp lại k lần và luôn kết thúc bằng hạt cùng loại với hạt bắt đầu. Cho số nguyên N (1 <= N <= 100) và dãy N hạt a1, a2, …, aN (1 <= ai <= 9). Yêu cầu: Tìm số lượng hạt trong dãy hạt mẫu ngắn nhất.
Giải pháp:
Dãy hạt mẫu có độ dài L phải là một ước số của N – 1 (hoặc thỏa mãn chu kỳ lặp lại trên toàn dãy).
Thử từng độ dài L từ 1 đến N.
Với mỗi L, kiểm tra xem dãy a có thỏa mãn tính chất a[i] == a[i % L] với mọi vị trí i từ 0 đến N – 1 hay không.
Độ dài L nhỏ nhất thỏa mãn điều kiện chính là đáp án.
Độ phức tạp:
Thời gian (Time Complexity): O(N^2), với N <= 100 chỉ mất chưa tới 0.001 giây.
Không gian (Space Complexity): O(N) để lưu trữ dãy hạt.
Python
import sys
sys.stdin = open('Vongtay.inp', 'r')
sys.stdout = open('Vongtay.out', 'w')
du_lieu = sys.stdin.read().split()
N = int(du_lieu[0])
a = [int(x) for x in du_lieu[1:N+1]]
for L in range(1, N + 1):
hop_le = True
for i in range(N):
if a[i] != a[i % L]:
hop_le = False
break
if hop_le:
print(L)
break
Bo mua nguyên liệu kết vòng tay bằng tiền vay bạn bè. Bo liệt kê N khoản tiền (1 <= N <= 10^5) gồm tiền bán vòng (số dương) và tiền vay (số âm) tại các vị trí từ 1 đến N. Bo bắt đầu từ vị trí 0, đi qua từng vị trí. Khi có đủ tiền trả khoản vay ngắn nhất, Bo sẽ trả nợ. Yêu cầu: Tính tổng số bước ngắn nhất Bo phải đi để trả hết các khoản nợ hoặc đi hết danh sách.
Giải pháp:
Mô phỏng quá trình di chuyển từ gốc 0 đến vị trí N.
Duyệt từng vị trí i từ 1 đến N:
Tích lũy số tiền ai thu được hoặc nợ vào ví.
Khi gặp khoản nợ và ví đủ tiền trang trải, Bo quay lại vị trí nợ trước đó để trả tiền rồi quay tiếp.
Quản lý biến tong_buoc tăng dần theo từng nhịp di chuyển tiến/lùi.
Độ phức tạp:
Thời gian (Time Complexity): O(N), xử lý mượt mà 10^5 phần tử trong khoảng 0.1 giây.
Không gian (Space Complexity): O(N).
Python
import sys
sys.stdin = open('Tinhtoan.inp', 'r')
sys.stdout = open('Tinhtoan.out', 'w')
du_lieu = sys.stdin.read().split()
N = int(du_lieu[0])
a = [int(x) for x in du_lieu[1:N+1]]
vi_tien = 0
vi_tri_hien_tai = 0
tong_buoc = 0
danh_sach_no = []
for i in range(N):
khoan_tien = a[i]
tong_buoc += abs((i + 1) - vi_tri_hien_tai)
vi_tri_hien_tai = i + 1
if khoan_tien > 0:
vi_tien += khoan_tien
else:
danh_sach_no.append((i + 1, abs(khoan_tien)))
# Trả nợ nếu đủ tiền
j = 0
while j < len(danh_sach_no):
pos_no, tien_no = danh_sach_no[j]
if vi_tien >= tien_no:
vi_tien -= tien_no
tong_buoc += (vi_tri_hien_tai - pos_no) * 2
danh_sach_no.pop(j)
else:
j += 1
print(tong_buoc)
Tại lễ hội mùa xuân có N trò chơi (1 <= N <= 1000). Trò chơi thứ i bắt đầu tại thời điểm ai và kết thúc tại thời điểm bi. Yêu cầu: Xác định số lượng trò chơi nhiều nhất mà Bo có thể tham gia sao cho không bị trùng lặp thời gian.
Nhận xét: Đây là bài toán chọn khoảng tối ưu (Interval Scheduling Problem).
Chiến lược Tham ăn (Greedy):
Sắp xếp danh sách các trò chơi theo thời gian kết thúc bi tăng dần.
Chọn trò chơi đầu tiên có thời gian kết thúc sớm nhất.
Duyệt qua các trò chơi tiếp theo, nếu thời gian bắt đầu ak của trò chơi mới lớn hơn hoặc bằng thời gian kết thúc của trò chơi vừa chọn trước đó, ta chọn tiếp trò chơi mới này và cập nhật thời gian kết thúc.
Độ phức tạp:
Thời gian (Time Complexity): O(N log N) do thao tác sắp xếp mảng. Với N = 1000, chương trình thực thi tức thì.
Không gian (Space Complexity): O(N) lưu trữ danh sách các khoảng thời gian.
Python
import sys
sys.stdin = open('Lehoi.inp', 'r')
sys.stdout = open('Lehoi.out', 'w')
du_lieu = sys.stdin.read().split()
N = int(du_lieu[0])
tro_choi = []
chi_so = 1
for i in range(N):
a = int(du_lieu[chi_so])
b = int(du_lieu[chi_so + 1])
tro_choi.append((a, b))
chi_so += 2
# Sắp xếp theo thời gian kết thúc b_i tăng dần
tro_choi.sort(key=lambda x: x[1])
dem_tro_choi = 0
thoi_gian_ket_thuc_cuoi = -1
for a, b in tro_choi:
if a >= thoi_gian_ket_thuc_cuoi:
dem_tro_choi += 1
thoi_gian_ket_thuc_cuoi = b
print(dem_tro_choi)
Nếu chọn theo thời gian bắt đầu sớm nhất, trò chơi đó có thể kéo dài rất lâu (ví dụ từ 1 đến 10), chiếm toàn bộ khung giờ và làm mất cơ hội tham gia nhiều trò chơi ngắn khác (như 2-3, 4-5, 6-7). Sắp xếp theo thời gian kết thúc giúp giải phóng quỹ thời gian sớm nhất có thể để tham gia các trò chơi tiếp theo.
Sử dụng sys.stdin.read().split() để đọc toàn bộ dữ liệu vào bộ nhớ trong một lần thay vì đọc từng dòng với input(). Thao tác I/O này giúp tốc độ xử lý nhanh hơn từ 5 đến 10 lần.
giải đề thi hsg tin học lớp 9 bình dương, đề thi hsg tin học bình dương 2021 2022, thuật toán tham ăn python hsg tin, lập trình python đề thi học sinh giỏi, bài toán chọn lịch tối ưu python, luyện thi hsg tin học thcs
#HSGTinHoc #PythonHSG #LuyenThiTinHoc #GiaiDeTinHoc #GreedyAlgorithm #PythonProgramming #Algorithm
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!
Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Phước…
Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Định…
Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Định…
Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bà Rịa…
Bạn đang ôn luyện thi Học sinh giỏi (HSG) Tin học THCS và muốn tìm…
Bạn đang tìm kiếm tài liệu ôn thi Học sinh giỏi (HSG) Tin học cấp…
This website uses cookies.