4 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Dương (2021 – 2022)
Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Dương (2021 – 2022) Bằng Python
Đề 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
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
4 Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Dương
Giá Trị Bổ Ích & Lợi Ích Lớn Khi Nghiên Cứu Đề Thi Này
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
Câu 1: Chở Hàng Giúp Mẹ (Chohang.inp / Chohang.out)
1. Tóm tắt đề bài
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.
2. Phân tích thuật toán & Độ phức tạp
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).
3. Code Python Chuẩn
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)
Câu 2: Tìm Dãy Hạt Mẫu (Vongtay.inp / Vongtay.out)
1. Tóm tắt đề bài
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.
2. Phân tích thuật toán
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.
3. Code Python Chuẩn
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
Câu 3: Tính Toán Chi Phí & Bước Đi (Tinhtoan.inp / Tinhtoan.out)
1. Tóm tắt đề bài
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.
2. Phân tích thuật toán
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_buoctă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).
3. Code Python Chuẩ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)
Câu 4: Sắp Xếp Trò Chơi Lễ Hội (Lehoi.inp / Lehoi.out)
1. Tóm tắt đề bài
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.
2. Phân tích thuật toán & Chiến lược Tham ăn (Greedy)
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.
3. Code Python Chuẩn
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)
Câu Hỏi Thường Gặp (FAQ)
Vì sao Bài 4 phải sắp xếp theo thời gian kết thúc thay vì thời gian bắt đầu?
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.
Làm thế nào để code Python chạy nhanh hơn trên các test bài tập lớn?
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.
Từ khoá SEO
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
Hashtags
#HSGTinHoc #PythonHSG #LuyenThiTinHoc #GiaiDeTinHoc #GreedyAlgorithm #PythonProgramming #Algorithm
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é !
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ệ:
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!
