Làm sao để giải bài toán sắp xếp trò chơi trùng thời gian đạt số lượng nhiều nhất?

Sử dụng Thuật toán Tham ăn (Greedy Algorithm) bằng cách sắp xếp tất cả trò chơi theo thời gian kết thúc tăng dần, sau đó chọn lần lượt các trò chơi không bị chồng lấp thời gian.

Tại sao dùng sys.stdin.read().split() lại tối ưu tốc độ đọc file trong Python?

Hàm sys.stdin.read() đọc toàn bộ file đầu vào vào RAM trong 1 thao tác I/O duy nhất, tránh việc phải truy xuất đĩa nhiều lần như hàm input() hay readline().

Làm sao để đếm số nguyên tố trong đoạn [1, N] với N = 10^6 nhanh nhất?

Sử dụng thuật toán Sàng Eratosthenes (Sieve of Eratosthenes) với độ phức tạp O(N log log N) để đánh dấu các số nguyên tố trong 0.1 giây.

Xử lý bài toán đếm tần suất số nguyên lớn lên tới 10^9 như thế nào?

Sử dụng cấu trúc dữ liệu Dictionary (Hash Map) trong Python để lưu trữ cặp (giá trị: số lần xuất hiện), giúp tối ưu bộ nhớ O(N) thay vì khởi tạo mảng kích thước 10^9.

Làm sao để đếm số nguyên tố trong đoạn [1, N] với N = 10^6 nhanh nhất?

Sử dụng thuật toán Sàng Eratosthenes (Sieve of Eratosthenes) với độ phức tạp O(N log log N) để đánh dấu các số nguyên tố trong 0.1 giây.

Xử lý bài toán đếm tần suất số nguyên lớn lên tới 10^9 như thế nào?

Sử dụng cấu trúc dữ liệu Dictionary (Hash Map) trong Python để lưu trữ cặp (giá trị: số lần xuất hiện), giúp tối ưu bộ nhớ O(N) thay vì khởi tạo mảng kích thước 10^9.

Làm thế nào để tối ưu bài toán tìm cặp số có tổng chữ số bằng nhau trong đoạn [l, r]?

Sử dụng mảng tần suất lưu giá trị nhỏ nhất và lớn nhất của mỗi tổng chữ số (từ 0 đến 63). Duyệt đoạn [l, r] một lần duy nhất để đạt độ phức tạp O(N).

Công thức tính tổng độ dài dây khoanh vùng vườn cây là gì?

Tổng độ dài dây bằng Chu vi ngoài 2*(M+N) cộng số ranh giới ngang giữa 2 ô khác loại và số ranh giới dọc giữa 2 ô khác loại.

Tại sao số có đúng 3 ước nguyên dương phải là bình phương của một số nguyên tố?

Số nguyên dương X = p^2 với p là số nguyên tố chỉ có đúng 3 ước nguyên dương phân biệt là 1, p, và p^2.

Khi nào nên dùng kỹ thuật Chia đôi tập dữ liệu (Meet-in-the-middle)?

Nên dùng kỹ thuật này khi N trong khoảng 30-40, khiến thuật toán duyệt trâu O(2^N) bị quá thời gian, còn O(2^(N/2)) thì chạy tối ưu trong 1 giây.

Tại sao nên dùng sys.stdin.read().split() thay cho input() trong Python khi thi HSG?

sys.stdin.read().split() đọc toàn bộ dữ liệu trong tệp vào bộ nhớ một lần duy nhất, giúp tốc độ xử lý nhanh hơn gấp 10-20 lần so với việc gọi hàm input() liên tục trong vòng lặp.

Làm thế nào để tránh lỗi TLE khi chạy quy hoạch động trên Python?

Cần tối ưu hóa phạm vi vòng lặp, sử dụng phép tính trực tiếp trên mảng và hạn chế các thao tác nhập xuất dữ liệu rải rác trong quá trình tính toán.

Khi nào nên dùng itertools.combinations trong các bài toán giải đề HSG Tin?

Bạn nên dùng itertools.combinations khi bài toán yêu cầu chọn các tổ hợp k phần tử (ví dụ bộ ba) từ một danh sách có kích thước nhỏ (N < 20). Hàm này giúp code ngắn gọn, không bị lặp bộ số và hạn chế lỗi logic.

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:

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_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).

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):
1. 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.
2. Chọn trò chơi đầu tiên có thời gian kết thúc sớm nhất.
3. 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ệ:

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 Đề Bí Quyết Trọn Bộ Thi HSG Tin Học Tỉnh Bình Phước 2018 – 2019

Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Phước (2018 – 2019) Bằng Python

Đề thi Học sinh giỏi Tin học THCS tỉnh Bình Phước năm học 2018 – 2019 quét qua toàn bộ các kỹ năng cốt lõi dành cho học sinh mới luyện thi: từ tính toán cơ bản, xử lý chuỗi ký tự, thuật toán Sàng nguyên tố Sieve of Eratosthenes cho đến tư duy đếm tần suất và tối ưu hóa mảng trên dữ liệu lớn.

Bài viết này mang đến đáp án chi tiết, mã nguồn Python chuẩn thi đấu, tối ưu hóa thuật toán đạt 100% điểm các test case và được định dạng thuần văn bản

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:

5 Đề Bí Quyết Trọn Bộ Lời Giải Thi HSG Tin Học Lớp 9 Tỉnh Bình Phước 2018 – 2019

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

Làm chủ kỹ thuật đọc/ghi File chuẩn thi đấu: Học sinh thực hành thành thạo việc xử lý dữ liệu qua tập tin .INP và .OUT bằng ngôn ngữ Python.
Xử lý chuỗi và đếm ký tự: Rèn luyện kỹ năng duyệt từng ký tự trong chuỗi, sử dụng các hàm kiểm tra chữ số có sẵn trong Python để tối ưu tốc độ lập trình.
Tối ưu hóa bài toán đếm số nguyên tố: Nắm vững thuật toán Sàng Eratosthenes thần tốc để giải quyết bài toán đếm số nguyên tố trong đoạn [1, N] với N <= 10^6 chỉ trong 0.1 giây.
Tư duy đếm tần suất bằng Dictionary/Hash Map: Học cách quản lý mảng với giá trị phần tử lên đến 10^9, tìm phần tử xuất hiện nhiều nhất và xử lý hòa điểm (tie-breaking) theo yêu cầu đề bài.

5 Đề Bí Quyết Trọn Bộ Lời Giải Thi HSG Tin Học Lớp 9 Tỉnh Bình Phước 2018 – 2019

Bài 1: Chu Vi Tam Giác (CHUVI.INP / CHUVI.OUT)

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

Cho độ dài ba cạnh của một tam giác lần lượt là a, b, c (1 <= a, b, c <= 1000).

Yêu cầu: Hãy tính chu vi của tam giác đó và ghi kết quả ra file.

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

Giải pháp:
- Chu vi tam giác có công thức đơn giản: P = a + b + c.
- Đọc trực tiếp 3 số nguyên a, b, c từ file CHUVI.INP và ghi tổng a + b + c vào file CHUVI.OUT.
Độ phức tạp:
- Thời gian (Time Complexity): O(1), thực hiện trong 0.001 giây.
- Không gian (Space Complexity): O(1).

3. Code Python Chuẩn

Python

import sys

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

du_lieu = sys.stdin.read().split()
a, b, c = map(int, du_lieu[:3])

chu_vi = a + b + c
print(chu_vi)

Bài 2: Số Lượng Chữ Số (SOCHUSO.INP / SOCHUSO.OUT)

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

Cho một xâu ký tự S gồm các chữ cái tiếng Anh in thường và các chữ số. Độ dài xâu S không quá 200 ký tự.

Yêu cầu: Đếm xem có bao nhiêu chữ số trong xâu S.

2. Phân tích thuật toán

Giải pháp:
- Duyệt qua từng ký tự c trong xâu S.
- Kiểm tra xem c có phải là chữ số hay không bằng phương thức c.isdigit().
- Nếu đúng là chữ số, tăng biến đếm lên 1.
Độ phức tạp:
- Thời gian (Time Complexity): O(|S|), với |S| <= 200 thì chương trình chạy tức thì.
- Không gian (Space Complexity): O(|S|) để lưu trữ xâu S.

3. Code Python Chuẩn

Python

import sys

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

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

dem_chu_so = sum(1 for ky_tu in s if ky_tu.isdigit())
print(dem_chu_so)

Bài 3: Đếm Số Nguyên Tố (DEMNT.INP / DEMNT.OUT)

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

Cho số nguyên dương N (N <= 10^6).

Yêu cầu: Xác định xem trong đoạn [1, N] có bao nhiêu số nguyên tố.

2. Phân tích thuật toán & Tối ưu hóa

Nhận xét:
- Nếu dùng thuật toán kiểm tra từng số xem có phải số nguyên tố hay không (với độ phức tạp O(căn(X)) cho mỗi số X), tổng thời gian sẽ là O(N * căn(N)), khi N = 10^6 sẽ thực hiện khoảng 10^9 phép tính -> Bị TLE (vượt quá thời gian cho phép).
Giải pháp tối ưu – Sàng Eratosthenes:
1. Khởi tạo mảng đánh dấu is_prime độ dài N + 1 với tất cả giá trị là True.
2. Gán is_prime[0] = is_prime[1] = False.
3. Duyệt i từ 2 đến căn(N):
  - Nếu is_prime[i] là True, đánh dấu tất cả các bội số của i từ i * i đến N là False.
4. Đếm số lượng giá trị True còn lại trong mảng is_prime từ 1 đến N.
Độ phức tạp:
- Thời gian (Time Complexity): O(N * log(log N)), với N = 10^6 chỉ tốn chưa đến 0.1 giây trong Python.
- Không gian (Space Complexity): O(N) lưu mảng boolean.

3. Code Python Chuẩn

Python

import sys

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

n = int(sys.stdin.read().split()[0])

if n < 2:
    print(0)
else:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1

    so_luong_nt = sum(is_prime)
    print(so_luong_nt)

Bài 4: Xuất Hiện Nhiều Nhất (XUATHIEN.INP / XUATHIEN.OUT)

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

Cho dãy A gồm N số nguyên a1, a2, …, an.

Yêu cầu: Tìm giá trị xuất hiện nhiều lần nhất trong dãy A và số lần xuất hiện của giá trị đó. Nếu có nhiều giá trị có cùng số lần xuất hiện nhiều nhất, hãy đưa ra giá trị nhỏ nhất trong số các giá trị đó.

Ràng buộc dữ liệu:

60% số test: N <= 10^3, ai <= 10^3.
20% số test: N <= 10^5, ai <= 10^4.
20% số test: N <= 10^6, ai <= 10^9.

2. Phân tích thuật toán & Xử lý Ràng buộc

Thách thức: Do ai <= 10^9, ta không thể dùng mảng đếm tần suất thông thường count[ai] vì sẽ tràn bộ nhớ.
Giải pháp tối ưu – Sử dụng Dictionary (Hash Map):
1. Dùng dict trong Python để lưu tần suất xuất hiện: tan_suat[val] = số_lần_xuất_hiện.
2. Tìm tần suất xuất hiện lớn nhất: max_freq = max(tan_suat.values()).
3. Tìm giá trị $x$ nhỏ nhất thỏa mãn tan_suat[x] == max_freq.
4. In ra giá trị min_val ở dòng 1 và max_freq ở dòng 2.
Độ phức tạp:
- Thời gian (Time Complexity): O(N) để duyệt và xây dựng dictionary. Với N = 10^6, Python xử lý trong khoảng 0.3 – 0.5 giây.
- Không gian (Space Complexity): O(N) lưu dictionary.

3. Code Python Chuẩn

Python

import sys

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

du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])

tan_suat = {}
for i in range(1, n + 1):
    val = int(du_lieu[i])
    tan_suat[val] = tan_suat.get(val, 0) + 1

max_freq = max(tan_suat.values())

gia_tri_thoaman = min(val for val, freq in tan_suat.items() if freq == max_freq)

print(gia_tri_thoaman)
print(max_freq)

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

Tại sao lại dùng `dict.get(val, 0) + 1` thay vì mảng danh sách trong Bài 4?

Giá trị phần tử ai có thể lên tới 10^9. Tạo một danh sách độ dài 10^9 trong Python sẽ tốn hàng GB RAM và gây ra lỗi tràn bộ nhớ (Memory Limit Exceeded). Dictionary trong Python hoạt động theo cơ chế Bảng băm (Hash Table), chỉ lưu các giá trị thực sự xuất hiện nên cực kỳ tiết kiệm bộ nhớ.

Thuật toán Sàng Eratosthenes trong Bài 3 chạy tốt đến phạm vi nào?

Sàng Eratosthenes hoạt động hiệu quả nhất trong phạm vi N <= 10^7. Với N = 10^6, thuật toán chỉ mất chưa đến 0.1 giây để chạy xong.

giải đề thi hsg tin học lớp 9 bình phước, đề thi hsg tin học bình phước 2018 2019, sàng nguyên tố python hsg tin, đếm số xuất hiện nhiều nhất python, đề thi hsg tin học thcs python, luyện thi học sinh giỏi tin học

Hashtags

#HSGTinHoc #PythonHSG #LuyenThiTinHoc #GiaiDeTinHoc #SieveOfEratosthenes #PythonProgramming #Algorithm

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!

3 Đề Thi [CÓ ĐÁP ÁN] HSG Tin Học Lớp 9 Tỉnh Bình Định 2022–2023

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 2022 – 2023) Bằng Python

Bộ đề thi Học sinh giỏi (HSG) Tin học THCS tỉnh Bình Định năm học 2022 – 2023 mang tính phân hóa cao, kiểm tra toàn diện tư duy lập trình từ tối ưu hóa mảng, hình học tọa độ nguyên, chiến thuật Tham ăn (Greedy) kết hợp xử lý chuỗi cho đến kỹ thuật duyệt lưới 2D. Bài viết này hướng dẫn chi tiết từng bước giải 4 bài toán bằng Python, viết mã nguồn tối ưu chuẩn thi đấu, loại bỏ hoàn toàn các ký tự công thức đặc biệt để dễ dàng chép/đăng tải lên website mà không bị lỗi giao diện.

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:

3 Đề Thi [CÓ ĐÁP ÁN] HSG Tin Học Lớp 9 Tỉnh Bình Định 2022–2023

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 2022 – 2023 mang đến lộ trình phát triển tư duy thuật toán vô cùng vững chắc cho học sinh THCS và các thầy cô huấn luyện đội tuyển:

Tối ưu hóa bài toán kiểm tra phạm vi lớn: Học sinh học cách xử lý bài toán tìm kiếm giá trị cực đại trên khoảng số nguyên lên tới 10^7 bằng mảng tần suất và bảng lưu vị trí min/max chỉ với độ phức tạp O(N).
Ứng dụng toán hình học tọa độ nguyên vào lập trình: Rèn luyện tư duy vét cạn có định hướng trên hình tròn, biết cách tận dụng tính đối xứng 4 góc phần tư để giảm số lần lặp tính toán diện tích hình chữ nhật.
Master tư duy Tham ăn (Greedy) và Chia phần trên chuỗi: Xử lý bài toán phân chia K xâu con liên tiếp bằng cách chia bài toán thành các phần kích thước đều nhau, đưa xâu có thứ tự từ điển lớn nhất về giá trị nhỏ nhất có thể.
Tư duy duyệt lưới và tính toán ranh giới: Nắm vững phương pháp duyệt từng ô lưới 2D, kiểm tra sự chênh lệch giá trị giữa 4 ô chung cạnh để tính tổng độ dài đường ranh giới khoanh vùng tự động.

3 Đề Thi [CÓ ĐÁP ÁN] HSG Tin Học Lớp 9 Tỉnh Bình Định 2022–2023

Bài 1: Cặp Số Tương Đồng (SIMILAR.INP / SIMILAR.OUT)

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

Hai số nguyên được gọi là “tương đồng” nếu chúng có tổng các chữ số bằng nhau. Cho hai số nguyên không âm l và r (l, r <= 10^7). Yêu cầu: Tìm hiệu lớn nhất (val2 – val1) của hai số val1, val2 nằm trong đoạn [l, r] sao cho val1 và val2 là hai số tương đồng.

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

Nhận xét quan trọng:
- Giá trị l, r <= 10^7. Một số <= 10^7 có tổng các chữ số tối đa là 9 + 9 + 9 + 9 + 9 + 9 + 9 = 63 (đối với số 9.999.999).
- Do đó, tổng các chữ số của mọi số trong đoạn [l, r] chỉ nhận các giá trị nguyên từ 0 đến 63.
Giải pháp tối ưu:
1. Khởi tạo 2 mảng cố định kích thước 64: min_val (lưu giá trị nhỏ nhất có tổng chữ số S) và max_val (lưu giá trị lớn nhất có tổng chữ số S).
2. Khởi tạo min_val chứa vô cùng, max_val chứa -1.
3. Duyệt số x chạy từ l đến r:
  - Tính tổng các chữ số S của x.
  - Cập nhật min_val[S] = min(min_val[S], x).
  - Cập nhật max_val[S] = max(max_val[S], x).
4. Duyệt qua tất cả các tổng S từ 0 đến 63: nếu max_val[S] > min_val[S], cập nhật hiệu lớn nhất hieu_max = max(hieu_max, max_val[S] - min_val[S]).
Độ phức tạp:
- Thời gian (Time Complexity): O(N * K) với N = r – l + 1 và K <= 7 (số chữ số của x). Tổng số phép tính <= 7 * 10^7, chạy hoàn thành trong khoảng 0.3 – 0.5 giây trong Python.
- Không gian (Space Complexity): O(1) vì chỉ dùng mảng kích thước cố định 64 phần tử.

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

Chạy 2 vòng lặp lồng nhau O(N^2): Thử mọi cặp số (val1, val2) trong đoạn [l, r] sẽ khiến chương trình bị TLE ngay lập tức khi r = 10^7.
Dùng chuyển đổi chuỗi str(x) để tính tổng chữ số: Trong Python, str(x) tạo ra object chuỗi mới liên tục làm chậm tốc độ. Nên viết hàm tính tổng chữ số bằng phép chia lấy dư % 10 và chia lấy nguyên // 10.

4. Code Python Chuẩn

Python

import sys

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

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

if du_lieu_vao:
    l = int(du_lieu_vao[0])
    r = int(du_lieu_vao[1])

    # Hàm tính tổng các chữ số siêu tốc
    def tinh_tong_chu_so(n):
        tong = 0
        while n > 0:
            tong += n % 10
            n //= 10
        return tong

    VO_CUNG = float('inf')
    min_val = [VO_CUNG] * 64
    max_val = [-1] * 64

    for x in range(l, r + 1):
        s = tinh_tong_chu_so(x)
        if x < min_val[s]:
            min_val[s] = x
        if x > max_val[s]:
            max_val[s] = x

    hieu_lon_nhat = 0
    for s in range(64):
        if max_val[s] > min_val[s]:
            hieu_tam = max_val[s] - min_val[s]
            if hieu_tam > hieu_lon_nhat:
                hieu_lon_nhat = hieu_tam

    print(hieu_lon_nhat)

Bài 2: Hình Chữ Nhật Lớn Nhất (DIENTICH.INP / DIENTICH.OUT)

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

Cho bán kính R (R < 10) của đường tròn tâm O(0,0). Tìm diện tích lớn nhất của một hình chữ nhật có các đỉnh mang tọa độ nguyên, nằm trong hoặc nằm trên đường tròn (x^2 + y^2 <= R^2) và các cạnh song song với các trục tọa độ. Nếu không tồn tại hình chữ nhật thỏa mãn, in 0.

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

Tính chất đối xứng hình học:
- Do đường tròn tâm O(0,0) và hình chữ nhật có các cạnh song song với trục tọa độ, một hình chữ nhật hợp lệ có thể xác định bởi điểm góc ở góc phần tư thứ nhất có tọa độ (x, y) với x > 0 và y > 0.
- Các đỉnh tương ứng của hình chữ nhật sẽ là: (x, y), (-x, y), (-x, -y), (x, -y).
- Tọa độ phải thỏa mãn nằm trong hoặc trên đường tròn: x^2 + y^2 <= R^2.
- Chiều dài và chiều rộng của hình chữ nhật lần lượt là 2x và 2y.
- Diện tích hình chữ nhật: S = (2x) * (2y) = 4 * x * y.
Giải pháp:
1. Duyệt tất cả các hoành độ nguyên x từ 1 đến R.
2. Duyệt tất cả các tung độ nguyên y từ 1 đến R.
3. Kiểm tra điều kiện x^2 + y^2 <= R^2. Nếu thỏa mãn, tính diện tích S = 4 * x * y và cập nhật giá trị lớn nhất.
Độ phức tạp:
- Thời gian (Time Complexity): O(R^2). Với R < 10, số vòng lặp tối đa không quá 100 phép tính, chạy trong thời gian 0.001 giây.
- Không gian (Space Complexity): O(1).

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

Bỏ sót trường hợp R nhỏ (R <= 1): Với R = 1, x^2 + y^2 <= 1 với x >= 1, y >= 1 là 1^2 + 1^2 = 2 > 1 (không thỏa mãn). Do đó không có hình chữ nhật tọa độ nguyên nào nội tiếp được, kết quả phải in ra 0.
Nhầm lẫn giữa diện tích và tọa độ thực: Đề bài yêu cầu đỉnh có tọa độ nguyên, không được áp dụng công thức hình chữ nhật nội tiếp đường tròn có diện tích lớn nhất là hình vuông bán kính căn(2)*R (vì đỉnh khi đó có thể không nguyên).

4. Code Python Chuẩn

Python

import sys

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

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

if du_lieu_vao:
    r = int(du_lieu_vao[0])

    dien_tich_lon_nhat = 0

    # Duyệt tọa độ nguyên x, y góc phần tư thứ nhất (x > 0, y > 0)
    for x in range(1, r + 1):
        for y in range(1, r + 1):
            if x * x + y * y <= r * r:
                dien_tich = 4 * x * y
                if dien_tich > dien_tich_lon_nhat:
                    dien_tich_lon_nhat = dien_tich

    print(dien_tich_lon_nhat)

Bài 3: Trò Chơi Xâu Ký Tự (STRGAME.INP / STRGAME.OUT)

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

Cho xâu ký tự S gồm N ký tự tiếng Anh in thường và một số nguyên dương K (1 <= K <= N <= 100). Được phép sắp xếp lại các ký tự trong S thành một xâu mới, sau đó chia xâu mới này thành chính xác K xâu ký tự liên tiếp không rỗng. Yêu cầu: Hãy tìm phương án sắp xếp và chia xâu sao cho xâu ký tự có thứ tự từ điển lớn nhất trong K xâu con đạt giá trị nhỏ nhất có thể, và in ra xâu lớn nhất đó.

2. Phân tích thuật toán & Chiến thuật Tham ăn (Greedy)

Để xâu có thứ tự từ điển lớn nhất trong K xâu là nhỏ nhất có thể, ta cần ưu tiên chia các ký tự nhỏ nhất vào đầu của K xâu.

Bước 1: Sắp xếp xâu gốc theo thứ tự tăng dần từ điển. Giả sử xâu sau khi sắp xếp là S_sort.
Bước 2: Xét ký tự đầu tiên của K xâu con.
- K xâu con bắt buộc phải nhận K ký tự đầu tiên của S_sort làm ký tự khởi đầu: S_sort[0], S_sort[1], ..., S_sort[K-1].
- Trường hợp 1: Nếu S_sort[0] != S_sort[K-1]. Do xâu đã sắp xếp, ký tự S_sort[K-1] là ký tự lớn nhất trong nhóm K ký tự đầu. Xâu bắt đầu bằng S_sort[K-1] chắc chắn sẽ là xâu có thứ tự từ điển lớn nhất. Vì mục tiêu là tối thiểu hóa xâu lớn nhất, ta không ghép thêm bất kỳ ký tự nào vào sau S_sort[K-1]. Đáp án chính là S_sort[K-1].
- Trường hợp 2: Nếu S_sort[0] == S_sort[K-1] (Tất cả K xâu con đều bắt đầu bằng cùng 1 ký tự).
  - Trường hợp 2a: Nếu tất cả các ký tự còn lại từ vị trí K đến N-1 đều giống hệt nhau (ví dụ: các ký tự từ K đến N-1 đều là ‘b’). Để xâu lớn nhất là nhỏ nhất, ta phân phối đều các ký tự còn lại này cho K xâu con. Xâu lớn nhất sẽ nhận được số ký tự nhiều nhất là căn_trên((N - K) / K) ký tự.
  - Trường hợp 2b: Nếu các ký tự còn lại từ vị trí K đến N-1 chứa từ 2 loại ký tự khác nhau trở lên. Ta sẽ dồn toàn bộ phần ký tự còn lại từ K đến N-1 vào sau xâu thứ nhất. Lý do: xâu đầu tiên khi nối thêm phần đuôi đã sắp xếp tăng dần sẽ vẫn có thứ tự từ điển nhỏ hơn việc phân tán ký tự lớn hơn sang các xâu khác. Đáp án là S_sort[0] + S_sort[K:N].

Độ phức tạp:
- Thời gian (Time Complexity): O(N log N) do thao tác sắp xếp xâu ký tự.
- Không gian (Space Complexity): O(N) để lưu trữ xâu kết quả.

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

Hiểu sai khái niệm thứ tự từ điển: Xâu “ab” nhỏ hơn xâu “abb”, xâu “aba” nhỏ hơn xâu “b”.
Bỏ qua trường hợp chia đều ký tự dư: Khi K xâu đầu tiên bằng nhau và phần còn lại chỉ có 1 loại ký tự độc nhất, nếu dồn hết vào 1 xâu sẽ làm xâu đó dài ra vô ích và làm tăng thứ tự từ điển so với cách chia đều.

4. Code Python Chuẩn

Python

import sys

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

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

if du_lieu_vao:
    n = int(du_lieu_vao[0])
    k = int(du_lieu_vao[1])
    s = du_lieu_vao[2]

    # Sắp xếp toàn bộ ký tự theo thứ tự từ điển tăng dần
    s_sap_xep = sorted(s)

    # Trường hợp 1: K ký tự đầu tiên không giống nhau hoàn toàn
    if s_sap_xep[0] != s_sap_xep[k - 1]:
        print(s_sap_xep[k - 1])
    else:
        # Trường hợp 2: K ký tự đầu tiên giống hệt nhau
        # Kiểm tra xem các ký tự còn lại từ vị trí k đến n-1 có giống nhau không
        la_giong_nhau_het = True
        for i in range(k, n - 1):
            if s_sap_xep[i] != s_sap_xep[i + 1]:
                la_giong_nhau_het = False
                break

        if la_giong_nhau_het:
            # Chia đều phần còn lại cho K xâu
            so_ky_tu_them = (n - k + k - 1) // k
            ket_qua = s_sap_xep[0] + "".join(s_sap_xep[k:k + so_ky_tu_them])
            print(ket_qua)
        else:
            # Dồn toàn bộ phần còn lại vào xâu đầu tiên
            ket_qua = s_sap_xep[0] + "".join(s_sap_xep[k:])
            print(ket_qua)

Bài 4: Khoanh Vùng Phân Loại (VUONCAY.INP / VUONCAY.OUT)

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

Một mảnh vườn hình chữ nhật kích thước M x N ô đất. Mỗi ô (i, j) được trồng một loại cây mã hóa bằng một số nguyên a[i][j]. Người làm vườn giăng dây ranh giới quanh chu vi mảnh vườn và giữa các ô chung cạnh nếu 2 ô đó trồng hai loại cây khác nhau. Yêu cầu: Tính tổng độ dài dây cần dùng để khoanh vùng các loại cây.

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

Độ dài dây cần giăng bao gồm 3 thành phần chính:

Dây bao quanh chu vi ngoài cùng của mảnh vườn:
- Chu vi = 2 * (M + N).
Dây giăng theo các cạnh dọc bên trong:
- Xét từng hàng i từ 0 đến M-1, với mọi cặp ô kề nhau theo chiều ngang (j và j+1):
- Nếu a[i][j] != a[i][j+1], cộng thêm 1 đơn vị độ dài dây.
Dây giăng theo các cạnh ngang bên trong:
- Xét từng cột j từ 0 đến N-1, với mọi cặp ô kề nhau theo chiều dọc (i và i+1):
- Nếu a[i][j] != a[i+1][j], cộng thêm 1 đơn vị độ dài dây.

Tổng chiều dài dây = Chu vi ngoài + Dây dọc bên trong + Dây ngang bên trong.
Độ phức tạp:
- Thời gian (Time Complexity): O(M * N). Với M, N < 100, số ô tối đa là 10.000, thời gian tính toán chưa tới 0.01 giây.
- Không gian (Space Complexity): O(M * N) để lưu ma trận vườn cây.

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

Đếm lặp dây ranh giới: Căng dây giữa ô A và ô B chỉ tính 1 lần cho cạnh chung của chúng. Việc duyệt theo hướng cố định (trái sang phải, trên xuống dưới) giúp tránh bị đếm trùng lặp.
Quên tính chu vi ngoài mảnh vườn: Đề bài ghi rõ “Dây được căng xung quanh mảnh vườn và cạnh của ô nếu 2 ô chứa cạnh đó ươm hai loại cây khác nhau”. Cần cộng thêm 2*(M + N) vào kết quả final.

4. Code Python Chuẩn

Python

import sys

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

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

if du_lieu_vao:
    m = int(du_lieu_vao[0])
    n = int(du_lieu_vao[1])

    idx = 2
    luoi_cay = []
    for i in range(m):
        hang = []
        for j in range(n):
            hang.append(int(du_lieu_vao[idx]))
            idx += 1
        luoi_cay.append(hang)

    # 1. Chu vi bên ngoài mảnh vườn
    chu_vi_ngoai = 2 * (m + n)

    # 2. Đếm dây dọc bên trong (giữa cột j và cột j+1)
    day_doc_inside = 0
    for i in range(m):
        for j in range(n - 1):
            if luoi_cay[i][j] != luoi_cay[i][j + 1]:
                day_doc_inside += 1

    # 3. Đếm dây ngang bên trong (giữa hàng i và hàng i+1)
    day_ngang_inside = 0
    for i in range(m - 1):
        for j in range(n):
            if luoi_cay[i][j] != luoi_cay[i + 1][j]:
                day_ngang_inside += 1

    # Tổng độ dài dây cần dùng
    tong_chieu_dai_day = chu_vi_ngoai + day_doc_inside + day_ngang_inside

    print(tong_chieu_dai_day)

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

Tại sao lại dùng mảng cố định 64 phần tử ở Bài 1?

Một số <= 10^7 có nhiều nhất 7 chữ số. Tổng chữ số lớn nhất có thể đạt được là 9 * 7 = 63. Do đó mảng có kích thước 64 (chỉ số từ 0 đến 63) cover đủ mọi tổng chữ số có thể xuất hiện, giúp truy cập vị trí min/max với tốc độ cực nhanh O(1).

Làm thế nào để giải các bài toán ma trận lưới 2D không bị vượt quá thời gian (TLE) trong Python?

Thay vì dùng các hàm tìm kiếm phức tạp, hãy đọc toàn bộ file đầu vào bằng sys.stdin.read().split(), phẳng hóa dữ liệu đầu vào rồi nạp vào ma trận 2D bằng List Comprehension để tối ưu bộ nhớ và thời gian chạy.

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ệ:

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!

SEO Keywords

giải đề thi hsg tin học lớp 9, đề thi hsg tin học bình định 2022 2023, giải bài toán cặp số tương đồng python, diện tích hình chữ nhật lớn nhất đường tròn python, trò chơi xâu ký tự hsg tin, khoanh vùng phân loại vườn cây python

Hashtags

#HSGTinHoc #PythonHSG #LuyenThiTinHoc #GiaiDeTinHoc #LapTrinhPython #GreedyAlgorithm #Matrix2D

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

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

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

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

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!

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

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

Đá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

Python

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

Python

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

Python

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?

Tránh viết câu lệnh I/O (input, print) bên trong vòng lặp lớn.
É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.
Ư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é !

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!

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

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

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

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.

Bài	Tên bài	File dữ liệu vào	File kết quả	Điểm
Bài 1	Tổng các ước	`USUM.INP`	`USUM.OUT`	5.0
Bài 2	Dãy ký tự số	`STRING.INP`	`STRING.OUT`	5.0
Bài 3	Đào vàng	`GOLD.INP`	`GOLD.OUT`	5.0
Bài 4	Bộ ba hoàn hảo	`HOANHAO.INP`	`HOANHAO.OUT`	5.0

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:

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ố.
Tìm độ dài lớn nhất của các nhóm xâu số này.

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 $\rightarrow 3 + 34 = 37$
- 3a34-123-> $\rightarrow 3 + 34 + 123 = 160$
- Virus $\rightarrow 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é !

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!

❓ 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.

22 Đề Thi Học Sinh Giỏi Tin Học THCS Tân Phước 2021–2022 (Kèm Lời Giải & Link Tải PDF/Code)

Bạn đang tìm kiếm tài liệu ôn thi Học sinh giỏi (HSG) Tin học cấp THCS chất lượng, bám sát cấu trúc đề thi thực tế? Bộ Đề thi Học sinh giỏi Tin học THCS Huyện Tân Phước năm học 2021–2022 chính là tài liệu vàng giúp học sinh rèn luyện tư duy thuật toán và bứt phá điểm số trong các kỳ thi sắp tới.

Cấu Trúc Đề Thi HSG Tin Học THCS Tân Phước 2021–2022

22-De-Thi-Hoc-Sinh-Gioi-Tin-Hoc-THCS-Tan-Phuoc-2021–2022-Kem-Loi-Giai-Link-Tai-PDF ta

22-De-Thi-Hoc-Sinh-Gioi-Tin-Hoc-THCS-Tan-Phuoc-2021–2022-Kem-Loi-Giai-Link-Tai-PDF

Đề thi được thiết kế nhằm đánh giá toàn diện kỹ năng lập trình, tư duy logic và khả năng tối ưu thuật toán của học sinh lớp 8, lớp 9 với các dạng bài từ cơ bản đến nâng cao:

Bài 1: Xử lý số học & Tính toán cơ bản – Kiểm tra kỹ năng sử dụng vòng lặp, câu lệnh điều kiện và các phép toán chia lấy phần nguyên/dư.
Bài 2: Xử lý Chuỗi & Ký tự – Bài toán đếm ký tự, tách từ, đảo ngược hoặc kiểm tra chuỗi đối xứng (Palindrome).
Bài 3: Mảng 1 chiều & Thuật toán Tối ưu – Tìm sub-array, đếm phần tử thỏa mãn điều kiện hoặc bài toán sắp xếp/tìm kiếm.
Bài 4: Bài toán Tư duy & Thuật toán Nâng cao – Đòi hỏi học sinh biết áp dụng kỹ thuật duyệt, quy hoạch động đơn giản hoặc tối ưu độ phức tạp thời gian $O(N)$ .

🟢 ĐÁP ÁN BÀI 1: SỐ NGUYÊN TỐ VÀ ƯCLN

1. Phân tích đề

Cho hai số nguyên dương:

0 < A < B < 100

Yêu cầu:

a) Tìm các số nguyên tố từ A đến B

Ví dụ:

A = 10

B = 25

Các số nguyên tố là:

11 13 17 19 23

b) Tìm ƯCLN của A và B

UCLN(10, 25) = 5

2. Phần a — Kiểm tra số nguyên tố

Số nguyên tố là gì?

Một số nguyên tố là số:

Lớn hơn 1
Chỉ chia hết cho 1 và chính nó.

Ví dụ:

2, 3, 5, 7, 11, 13, 17…

Không phải số nguyên tố:

…

Cách kiểm tra số nguyên tố

Ta có thể thử chia n cho các số từ 2 đến √n.

Tại sao chỉ cần đến √n?

Nếu:

n = a × b

thì ít nhất một trong hai số a, b phải:

≤ √n

Ví dụ:

36 = 4 × 9

Ta chỉ cần kiểm tra đến:

√36 = 6

Hàm kiểm tra nguyên tố

def la_so_nguyen_to(n):
    if n < 2:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True

Giải thích

Nếu:

n < 2

thì chắc chắn không phải số nguyên tố.

for i in range(2, int(n ** 0.5) + 1):

Thử các ước từ 2 đến √n.

Nếu:

n % i == 0

thì n chia hết cho i, nghĩa là n có ước khác 1 và chính nó.

→ Không phải số nguyên tố.

3. Duyệt từ A đến B

Ta dùng:

for i in range(A, B + 1):

Vì range() không lấy giá trị cuối nên phải dùng B + 1.

Ví dụ:

A = 10

B = 25

for i in range(A, B + 1):

print(i)

sẽ duyệt:

…

Sau đó kiểm tra từng số:

if la_so_nguyen_to(i):

print(i, end=” “)

4. Phần b — Tìm ƯCLN

Có nhiều cách tìm ƯCLN.

Cách rất quan trọng trong lập trình là thuật toán Euclid.

Công thức:

UCLN(a, b) = UCLN(b, a % b)

Lặp lại cho đến khi:

b = 0

Khi đó:

UCLN = a

Ví dụ UCLN(10, 25)

Ta có:

25 % 10 = 5

nên:

UCLN(10, 25)

= UCLN(25, 10)

= UCLN(10, 5)

= UCLN(5, 0)

= 5

5. GIẢI Code hoàn chỉnh Bài 1

def la_so_nguyen_to(n):
    if n < 2:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

    return True


def ucln(a, b):
    while b != 0:
        a, b = b, a % b

    return a


A = int(input())
B = int(input())

# Tìm các số nguyên tố từ A đến B
for i in range(A, B + 1):
    if la_so_nguyen_to(i):
        print(i, end=" ")

print()

# Tìm UCLN
print(ucln(A, B))

Với:

Input

Kết quả:

11 13 17 19 23

Đúng với ví dụ trong đề.

6. Độ phức tạp Bài 1

Có:

B – A + 1

số cần kiểm tra.

Mỗi số kiểm tra đến căn bậc hai của nó.

Do đó độ phức tạp khoảng:

O((B-A)√B)

Với B < 100 thì cực kỳ nhanh.

Thuật toán ƯCLN

Thuật toán Euclid có độ phức tạp:

O(log(min(A, B)))

Đây là cách tìm ƯCLN rất hiệu quả.

🟠ĐÁP ÁN BÀI 2: ĐÁNH SỐ CÂY

Đây là bài rất hay vì nhìn đề có vẻ phải mô phỏng rất nhiều cây, nhưng thực ra không cần mô phỏng.

Theo đề:

Cây thứ 1 được đánh số 1
Hai cây tiếp theo được đánh số 2
Ba cây tiếp theo được đánh số 3
Bốn cây tiếp theo được đánh số 4
…

Tức là:

Số 1 xuất hiện 1 lần

Số 2 xuất hiện 2 lần

Số 3 xuất hiện 3 lần

Số 4 xuất hiện 4 lần

…

1. Viết thử ra giấy

Ta có:

Cây: 1 2 3 4 5 6 7 8 9 10 …

Số ghi: 1 2 2 3 3 3 4 4 4 4 …

Ví dụ:

N = 12

Ta có:

1 cây số 1

2 cây số 2

3 cây số 3

4 cây số 4

Tổng số cây:

1 + 2 + 3 + 4 = 10

Chưa đến cây thứ 12.

5 cây số 5

Các cây:

11 → 5

12 → 5

13 → 5

14 → 5

15 → 5

Do đó:

N = 12

→ kết quả = 5

Đúng với ví dụ của đề.

2. Cách 1 — Mô phỏng đơn giản

Vì đề cho:

N ≤ 10^9

Ta không nên duyệt từ 1 đến N nếu muốn thuật toán tối ưu.

Nhưng để hiểu bài, có thể viết cách đơn giản:

N = int(input())

so = 1
tong = 0

while tong < N:
    tong += so
    if tong >= N:
        print(so)
        break

    so += 1

Ví dụ N = 12:

so = 1 → tong = 1

so = 2 → tong = 3

so = 3 → tong = 6

so = 4 → tong = 10

so = 5 → tong = 15

Vì:

10 < 12 ≤ 15

nên đáp án là:

3. Độ phức tạp cách 1

Ta cần tìm k sao cho:

1 + 2 + 3 + … + k ≥ N

Mà:

1 + 2 + … + k = k(k+1)/2

nên:

k(k+1)/2 ≥ N

Suy ra:

k ≈ √(2N)

Vì vậy cách mô phỏng có độ phức tạp:

O(√N)

Với:

N = 10^9

thì khoảng:

√10^9 ≈ 31623

Chỉ khoảng vài chục nghìn vòng lặp → vẫn rất nhanh.

🟢 ĐÁP ÁN BÀI 3: TRÒ CHƠI VỚI BĂNG SỐ?

1. Đề bài

Trên một cuộn giấy dài, người ta lần lượt viết N số nguyên dương.

Yêu cầu: Cắt cuộn giấy thành nhiều đoạn nhất sao cho tổng các số trong mỗi đoạn bằng nhau.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương N.
Dòng thứ hai chứa N số nguyên dương a1, a2, ..., aN.

Dữ liệu ra:

In ra số đoạn nhiều nhất có thể chia được.

Theo đề, N ≤ 10^3, vì vậy thuật toán O(N²) hoàn toàn phù hợp.

2. Hiểu đề bằng ví dụ

Ta có dãy:

10 2 6 2 5 2 1 2

Tổng tất cả các số là:

10 + 2 + 6 + 2 + 5 + 2 + 1 + 2 = 30

Có thể chia thành 3 đoạn:

Đoạn 1: 10
Đoạn 2: 2 + 6 + 2 = 10
Đoạn 3: 5 + 2 + 1 + 2 = 10

Như vậy:

10 | 2 6 2 | 5 2 1 2

Mỗi đoạn đều có tổng bằng 10.

Vì vậy kết quả là:

3. Nhận xét quan trọng

Gọi tổng toàn bộ dãy là:

Nếu chia được thành k đoạn bằng nhau thì tổng mỗi đoạn bắt buộc phải là:

S / k

Do đó:

S % k == 0

Nếu S không chia hết cho k thì chắc chắn không thể chia thành k đoạn có tổng bằng nhau.

Ví dụ:

S = 30

Ta có thể thử:

k = 8 → 30 không chia hết cho 8
k = 7 → 30 không chia hết cho 7
k = 6 → 30 chia hết cho 6
k = 5 → 30 chia hết cho 5
k = 3 → 30 chia hết cho 3
k = 2 → 30 chia hết cho 2
k = 1 → 30 chia hết cho 1

Nhưng mục tiêu là nhiều đoạn nhất, nên phải thử k từ lớn xuống nhỏ.

4. Tại sao thử số đoạn từ lớn xuống nhỏ?

Đề yêu cầu:

Chia thành nhiều đoạn nhất.

Giả sử có thể chia thành:

1 đoạn
2 đoạn
3 đoạn

thì đáp án phải là 3.

Vì vậy ta thử:

N, N-1, N-2, ..., 1

Ngay khi tìm được số đoạn hợp lệ đầu tiên thì đó chính là đáp án lớn nhất.

5. Cách kiểm tra một giá trị k

Giả sử:

S = 30
k = 3

Khi đó tổng mỗi đoạn phải là:

muc_tieu = S // k
       = 30 // 3
       = 10

Ta duyệt dãy từ trái sang phải.

Ban đầu:

tong = 0

Đọc 10:

tong = 10

Đủ 10 nên tạo được đoạn thứ nhất:

Reset:

tong = 0

Đọc tiếp:

2
6
2

Ta có:

2 + 6 + 2 = 10

Tạo đoạn thứ hai.

Tiếp tục:

5 + 2 + 1 + 2 = 10

Tạo đoạn thứ ba.

Như vậy k = 3 hợp lệ.

6. Vì sao không được để tổng vượt mục tiêu?

Giả sử:

muc_tieu = 10

nhưng trong quá trình cộng ta có:

tong = 8

và phần tử tiếp theo là:

thì:

8 + 5 = 13 > 10

Đoạn hiện tại đã vượt quá 10.

Vì tất cả các số đều là số nguyên dương, ta không thể thêm hoặc bớt số nào để tổng quay lại bằng 10.

Do đó trường hợp này chắc chắn thất bại.

7. Thuật toán Bài 3

Các bước thực hiện:

Bước 1

Đọc N và dãy số.

Bước 2

Tính tổng toàn bộ dãy:

S = a1 + a2 + ... + aN

Bước 3

Thử số đoạn k từ N giảm xuống 1.

Bước 4

Nếu:

S % k != 0

thì bỏ qua k.

Bước 5

Tính:

muc_tieu = S // k

Bước 6

Duyệt toàn bộ dãy.

Nếu:

tong + a[i] > muc_tieu

thì k không hợp lệ.

Nếu:

tong + a[i] == muc_tieu

thì hoàn thành một đoạn và đặt:

tong = 0

Bước 7

Nếu tạo được đúng k đoạn thì in k và kết thúc.

8. Code Python Bài 3

import sys

sys.stdin = open("BL3.INP", "r")
sys.stdout = open("BL3.OUT", "w")

# Đọc số lượng phần tử
n = int(input())

# Đọc dãy số
a = list(map(int, input().split()))

# Tính tổng tất cả các phần tử
tong = sum(a)

# Thử số đoạn từ n xuống 1
for so_doan in range(n, 0, -1):

    # Nếu tổng không chia hết cho số đoạn
    # thì không thể chia đều
    if tong % so_doan != 0:
        continue

    # Tổng của mỗi đoạn
    tong_moi_doan = tong // so_doan

    # Nếu một phần tử đã lớn hơn tổng mỗi đoạn
    # thì chắc chắn không thể chia
    if max(a) > tong_moi_doan:
        continue

    # Bắt đầu kiểm tra từng đoạn
    tong_doan = 0
    dem_doan = 0
    co_the_chia = True

    for x in a:

        # Cộng phần tử hiện tại vào đoạn
        tong_doan += x

        # Nếu tổng đoạn vượt quá yêu cầu
        if tong_doan > tong_moi_doan:
            co_the_chia = False
            break

        # Nếu tổng đoạn vừa đủ
        if tong_doan == tong_moi_doan:
            dem_doan += 1
            tong_doan = 0

    # Nếu chia được đúng so_doan đoạn
    if co_the_chia and tong_doan == 0 and dem_doan == so_doan:
        print(so_doan)
        break

9. Giải thích từng phần code Bài 3

Đọc dữ liệu

import sys

sys.stdin = open("BL3.INP", "r")
sys.stdout = open("BL3.OUT", "w")

Hai dòng:

sys.stdin = open("BL3.INP", "r")
sys.stdout = open("BL3.OUT", "w")

giúp chương trình đọc dữ liệu từ file BL3.INP và ghi kết quả vào BL3.OUT.

Đây là cách thường dùng trong các bài thi lập trình sử dụng file.

Đọc N và dãy số

n = int(input())
a = list(map(int, input().split()))

Ví dụ:

8
10 2 6 2 5 2 1 2

thì:

n = 8
a = [10, 2, 6, 2, 5, 2, 1, 2]

Tính tổng toàn bộ dãy

tong_all = sum(a)

Ta có:

tong_all = 30

Thử số đoạn từ lớn xuống

for k in range(n, 0, -1):

Nếu:

n = 8

thì:

Mục đích là tìm số đoạn lớn nhất.

Kiểm tra tổng có chia hết cho k

if tong_all % k != 0:
    continue

Ví dụ:

30 % 7 != 0

nên không thể chia thành 7 đoạn bằng nhau.

Ta bỏ qua:

continue

Tính tổng mỗi đoạn

target = tong_all // k

Ví dụ:

30 / 3 = 10

Do đó mỗi đoạn phải có tổng bằng 10.

Biến tổng

tong = 0

Biến này lưu tổng của đoạn hiện tại.

Ví dụ đang xét:

2 6 2

thì:

tong = 2
tong = 8
tong = 10

Khi bằng target thì hoàn thành một đoạn.

Kiểm tra vượt quá target

if tong > target:
    ok = False
    break

Ví dụ:

target = 10
tong = 8
x = 5

thì:

tong = 13

vượt quá 10.

Do các số đều dương nên không thể sửa lại được.

Khi đủ một đoạn

if tong == target:
    dem += 1
    tong = 0

Ta tăng số đoạn:

dem += 1

sau đó bắt đầu đoạn mới:

tong = 0

10. Chạy thử Bài 3

Input:

8
10 2 6 2 5 2 1 2

Tổng:

Thử:

k = 8
30 không chia hết 8

k = 7
30 không chia hết 7

k = 6
target = 5

Phần tử đầu tiên là 10, lớn hơn 5 nên không thể.

Tiếp tục:

k = 5
target = 6

Phần tử đầu tiên 10 > 6, không thể.

Tiếp tục:

k = 3
target = 10

Ta chia được:

10
2 + 6 + 2 = 10
5 + 2 + 1 + 2 = 10

Vậy:

Đáp án = 3

Output:

11. Độ phức tạp Bài 3

Với mỗi giá trị k, ta có thể phải duyệt toàn bộ N phần tử.

Có tối đa N giá trị k cần thử.

Do đó độ phức tạp trong trường hợp xấu nhất là:

O(N²)

Bộ nhớ:

O(N)

do cần lưu dãy số.

Với N ≤ 1000 như đề bài, O(N²) tương đương khoảng tối đa một triệu phép kiểm tra, hoàn toàn phù hợp.

🟢GIẢI ĐÁP ÁN BÀI 4: XẾP HÀNG HÓA?

1. Đề bài

Tại một bến cảng, công nhân lần lượt bốc các kiện hàng từ tàu lên xe container.

Các kiện hàng phải được xử lý theo đúng thứ tự:

kiện 1 → kiện 2 → kiện 3 → ... → kiện n

Mỗi xe container có tải trọng tối đa là M.

Khi kiện hàng tiếp theo không thể đặt vào xe hiện tại vì tổng trọng lượng sẽ vượt quá M, phải chuyển sang xe tiếp theo.

Yêu cầu:

Tìm số chuyến xe ít nhất để vận chuyển hết hàng hóa.

Đây là bài toán tham lam – Greedy rất điển hình.

2. Ví dụ

Giả sử:

n = 10
M = 15

Các kiện hàng:

7 6 8 8 7 5 2 4 3 9

Ta xếp lần lượt.

Xe 1

7 + 6 = 13

Thêm 8:

13 + 8 = 21 > 15

Không được.

Xe 1:

7 + 6 = 13

Xe 2

Đặt:

Kiện tiếp theo 8:

8 + 8 = 16 > 15

Không được.

Xe 2:

Xe 3

Đặt:

Tiếp tục 7:

8 + 7 = 15

Vừa đủ.

Sau đó 5:

15 + 5 > 15

nên dừng.

Xe 3:

8 + 7 = 15

Tiếp tục tương tự:

Xe 4: 5 + 2 + 4 + 3 = 14
Xe 5: 9

Vậy cần:

5 chuyến xe

3. Ý tưởng Greedy

Điểm quan trọng nhất của bài này là:

Không được đổi thứ tự các kiện hàng.

Mỗi kiện hàng phải được đưa lên xe theo đúng thứ tự ban đầu.

Vì vậy ta chỉ cần quan tâm đến:

Xe hiện tại đang chở bao nhiêu?

Gọi:

tong

là tổng trọng lượng hàng đang nằm trên xe hiện tại.

Với mỗi kiện hàng x:

Trường hợp 1

Nếu:

tong + x <= M

thì kiện hàng vẫn đặt được lên xe hiện tại.

Ta thực hiện:

tong += x

Trường hợp 2

Nếu:

tong + x > M

thì kiện hàng không thể đặt lên xe hiện tại.

Bắt buộc phải sử dụng xe mới.

Ta:

so_xe += 1
tong = x

4. Tại sao cách Greedy là tối ưu?

Đây là phần rất quan trọng khi giải bài thi.

Giả sử xe hiện tại đang chứa tổng trọng lượng:

tong

và kiện tiếp theo có trọng lượng:

Nếu:

tong + x > M

thì xe hiện tại chắc chắn không thể chứa kiện x.

Không có cách nào khác để đưa x vào xe hiện tại, bởi vì:

Không được bỏ kiện hàng trước đó.
Không được đổi thứ tự.
Không được đưa kiện x sang trước.
Xe chỉ được chở tối đa M.

Do đó, bắt buộc phải mở xe mới.

Đây chính là lý do thuật toán tham lam hoạt động.

5. Thuật toán Bài 4

Bước 1

Đọc:

n, M

Bước 2

Đọc n trọng lượng.

Bước 3

Khởi tạo:

so_xe = 1
tong = 0

Vì n ≥ 1 nên ban đầu chắc chắn cần ít nhất một xe.

Bước 4

Duyệt từng kiện hàng x.

Nếu:

tong + x <= M

thì:

tong += x

Ngược lại:

so_xe += 1
tong = x

Bước 5

In:

so_xe

6. Code Python Bài 4

import sys

sys.stdin = open("BL4.INP", "r")
sys.stdout = open("BL4.OUT", "w")

n, M = map(int, input().split())
a = list(map(int, input().split()))

so_xe = 1
tong = 0

for x in a:

    if tong + x <= M:
        # Kiện hàng vẫn đặt được vào xe hiện tại
        tong += x
    else:
        # Không đủ chỗ, chuyển sang xe mới
        so_xe += 1
        tong = x

print(so_xe)

7. Giải thích code Bài 4

Đọc dữ liệu

n, M = map(int, input().split())

Ví dụ:

10 15

thì:

n = 10
M = 15

Trong đó:

n: số kiện hàng.
M: tải trọng tối đa của một xe.

Đọc trọng lượng

a = list(map(int, input().split()))

Ví dụ:

7 6 8 8 7 5 2 4 3 9

Khởi tạo

so_xe = 1
tong = 0

Ban đầu:

Chưa có hàng trên xe
Đang sử dụng xe số 1

Duyệt từng kiện

for x in a:

Mỗi vòng lặp lấy một kiện hàng.

Ví dụ:

x = 7

sau đó:

x = 6

rồi:

x = 8

Kiểm tra sức chứa

if tong + x <= M:

Nếu vẫn còn đủ tải trọng thì cho kiện hàng vào xe.

Ví dụ:

M = 15
tong = 7
x = 6

Ta có:

7 + 6 = 13 <= 15

nên:

tong += x

Kết quả:

tong = 13

Khi xe không chứa được kiện tiếp theo

Ví dụ:

tong = 13
x = 8
M = 15

Ta có:

13 + 8 = 21 > 15

Không thể đặt 8 vào xe hiện tại.

Ta mở xe mới:

so_xe += 1
tong = x

Kết quả:

so_xe = 2
tong = 8

8. Chạy thử Bài 4

Input:

10 15
7 6 8 8 7 5 2 4 3 9

Quá trình:

Xe 1:
7 + 6 = 13

Xe 2:
8

Xe 3:
8 + 7 = 15

Xe 4:
5 + 2 + 4 + 3 = 14

Xe 5:
9

Kết quả:

Output:

Ví dụ này cũng trùng với ví dụ được đăng lại từ đề bài.

9. Độ phức tạp Bài 4

Ta chỉ duyệt qua dãy đúng một lần.

Nếu có N kiện hàng:

Thời gian: O(N)

Bộ nhớ ngoài mảng đầu vào:

O(1)

Nếu lưu toàn bộ dãy:

O(N)

Có thể viết chương trình tiết kiệm bộ nhớ hơn bằng cách đọc từng số, nhưng với đề thi thông thường thì lưu mảng như trên rất dễ hiểu.

10. So sánh hai bài toán

Nội dung	Bài 3 – Trò chơi với băng số	Bài 4 – Xếp hàng hóa
Dạng bài	Chia đoạn	Chia nhóm liên tiếp
Điều kiện	Tổng các đoạn bằng nhau	Tổng mỗi xe không vượt M
Kỹ thuật	Duyệt thử số đoạn	Greedy
Thứ tự phần tử	Giữ nguyên	Giữ nguyên
Độ phức tạp	O(N²)	O(N)
Bộ nhớ	O(N)	O(N) nếu lưu mảng
Điểm quan trọng	Tổng toàn bộ phải chia hết cho số đoạn	Khi kiện tiếp theo không vừa thì mở xe mới

11. Những lỗi thường gặp

Lỗi 1: Bài 3 chỉ tìm một cách chia

Đề yêu cầu:

nhiều đoạn nhất

Do đó không được dừng ở cách chia đầu tiên tìm thấy nếu đang thử số đoạn từ nhỏ lên.

Cách tốt hơn là:

N → N-1 → N-2 → ... → 1

Lỗi 2: Quên kiểm tra tổng chia hết

Ví dụ:

S = 30
k = 7

Không thể có tổng mỗi đoạn là:

30 / 7

vì không phải số nguyên.

Do đó cần:

if tong_all % k != 0:
    continue

Lỗi 3: Bài 3 cho phép tổng vượt target

Không được.

Nếu:

target = 10
tong = 8
x = 5

thì:

tong = 13

Đoạn đó thất bại ngay.

Lỗi 4: Bài 4 sắp xếp các kiện hàng

Không được viết:

a.sort()

Bởi vì đề yêu cầu các kiện hàng phải được bốc lần lượt theo thứ tự ban đầu.

Ví dụ:

7 6 8 8 7

không được biến thành:

6 7 7 8 8

Lỗi 5: Dùng bài toán ba lô hoặc tìm mọi cách kết hợp

Bài 4 không yêu cầu tìm cách sắp xếp tối ưu tùy ý.

Thứ tự kiện hàng đã cố định.

Vì vậy chỉ cần:

nhét được → nhét
không nhét được → xe mới

Đây là tư duy Greedy.

12. Mẹo ghi nhớ nhanh

Bài 3

Hãy nhớ 4 bước:

TỔNG → THỬ k → TÍNH TARGET → KIỂM TRA

Trong đó:

target = Tổng / k

và thử:

k từ lớn xuống nhỏ

Bài 4

Chỉ cần nhớ:

Còn chỗ → cho vào
Hết chỗ → xe mới

Công thức kiểm tra:

tong + x <= M

Nếu đúng:

tong += x

Nếu sai:

so_xe += 1
tong = x

13. Phiên bản code ngắn gọn Bài 3

Sau khi đã hiểu thuật toán, có thể viết ngắn hơn:

import sys

sys.stdin = open("BL3.INP", "r")
sys.stdout = open("BL3.OUT", "w")

n = int(input())
a = list(map(int, input().split()))

S = sum(a)

for k in range(n, 0, -1):
    if S % k != 0:
        continue

    target = S // k
    tong = 0
    dem = 0

    for x in a:
        tong += x

        if tong > target:
            break

        if tong == target:
            dem += 1
            tong = 0

    if dem == k and tong == 0:
        print(k)
        break

14. Phiên bản code ngắn gọn Bài 4

import sys

sys.stdin = open("BL4.INP", "r")
sys.stdout = open("BL4.OUT", "w")

n, M = map(int, input().split())
a = list(map(int, input().split()))

xe = 1
tong = 0

for x in a:
    if tong + x <= M:
        tong += x
    else:
        xe += 1
        tong = x

print(xe)

15. Kết luận

Hai bài toán nhìn qua khá giống nhau vì đều yêu cầu chia một dãy số thành các nhóm liên tiếp, nhưng cách tư duy hoàn toàn khác nhau.

Bài 3 – Trò chơi với băng số:

Tính tổng toàn bộ dãy.
Muốn chia thành k đoạn thì tổng mỗi đoạn phải là S/k.
Thử k từ lớn xuống nhỏ.
Dùng tổng tích lũy để kiểm tra.
Với N ≤ 1000, thuật toán O(N²) là phù hợp.

Bài 4 – Xếp hàng hóa:

Không được thay đổi thứ tự kiện hàng.
Duyệt từ trái sang phải.
Nếu kiện tiếp theo vẫn vừa xe thì cho vào.
Nếu không vừa thì mở xe mới.
Thuật toán Greedy có độ phức tạp O(N).

Đây là hai dạng bài rất đáng học vì giúp hình thành hai kỹ thuật quan trọng trong lập trình thi đấu:

Bài 3 → Duyệt các khả năng + kiểm tra tổng
Bài 4 → Thuật toán tham lam (Greedy)

Nếu nắm chắc hai mẫu tư duy này, bạn sẽ gặp rất nhiều bài tương tự trong các đề thi học sinh giỏi Tin học.

Tại Sao Bạn Nên Luyện Đề Thi Này?

Bám sát thực tế: Đề thi phản ánh đúng độ khó và xu hướng ra đề của các huyện trong khu vực.
Rèn tư duy tối ưu: Giúp học sinh chuyển dịch từ tư duy “viết code cho chạy được” sang “viết code tối ưu thời gian $O(N)$ và bộ nhớ”.
Đa dạng ngôn ngữ: Đề bài hỗ trợ giải bằng cả Python, Pascal, hoặc C++.

Tải Xuống Trọn Bộ Đề Thi & Đáp Án Chi Tiết

Bộ file tải về bao gồm:

File đề thi gốc định dạng PDF (sắc nét, dễ in ấn).
Đáp án chi tiết và hướng dẫn chấm điểm.
Bộ Test mẫu (Input/Output) và Code mẫu (C++ / Python) đã qua kiểm thử thành công.

👉 LINK TẢI VỀ TRỌN BỘ ĐỀ THI & CODE MẪU (GOOGLE DRIVE) (Nhấp vào để tải miễn phí)

Bí Quyết Ôn Luyện HSG Tin Học Đạt Giải Cao

Nắm chắc nền tảng: Ôn tập kỹ kiến thức mảng, chuỗi, các hàm toán học và câu lệnh lặp.
Tối ưu thời gian chạy: Luôn chú ý đến giới hạn $N$ của đề bài để chọn thuật toán phù hợp, tránh lỗi TLE (Time Limit Exceeded).
Luyện tập thường xuyên: Làm lại đề thi các năm trước và tham gia giải bài trên các hệ thống chấm công khai (Online Judge).

Vi Tính Tấn Dân – Đồng Hành Cùng Tri Thức & Công Nghệ

Bên cạnh việc chia sẻ kiến thức và tài liệu học tập miễn phí, Vi Tính Tấn Dân tự hào là đơn vị uy tín chuyên cung cấp:

Dàn máy tính PC Lập trình – Học tập – Chơi game cấu hình tối ưu, giá rẻ.
Dịch vụ sửa chữa, nâng cấp Laptop & PC nhanh chóng, tận tâm tại Đồng Tháp.
Linh phụ kiện máy tính chính hãng (Bàn phím, chuột, màn hình, SSD…).

Nếu bạn đang tìm kiếm một chiếc máy tính mượt mà để phục vụ việc học lập trình C++, Python hay Pascal, hãy liên hệ ngay với Vi Tính Tấn Dân để nhận được sự tư vấn chu đáo nhất!

7. Cách thức đăng ký và đóng học phí như thế nào?

Bạn có thể liên hệ trực tiếp với Thầy qua các kênh sau để được tư vấn và nhận báo giá ưu đãi:

Số điện thoại / Zalo: 0937.179.278
Hình thức đóng phí: Chuyển khoản ngân hàng hoặc nộp trực tiếp tại cơ sở (nếu học offline).

Đạt giải 3 học sinh giỏi tin học cấp tỉnh

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ệ:

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!

#HSGTinHoc #DeThiHSGTinHoc #TinHocTHCS #TanPhuoc #LapTrinhPython #LapTrinhCPP #HocSinhGioiTinHoc #OnThiHSG #KhungThuatToan #ViTinhTanDan #TinHocTanDan

Bộ 21 Đề Thi HSG Tin Học Lớp 9 Đồng Tháp 2026 – 2027 (Có Đáp Án)

Kỳ thi Học sinh giỏi (HSG) Tin học lớp 9 cấp xã và tỉnh luôn là một trong những thử thách lớn đối với các bạn học sinh đam mê lập trình và thuật toán. Để đạt được thành tích cao, việc luyện đề và cọ xát với các dạng bài thi thực tế từ các năm trước là phương pháp ôn luyện vô cùng hiệu quả.

Nhằm đồng hành cùng các bạn học sinh và quý thầy cô trên địa bàn tỉnh, Vi Tính Tấn Dân xin chia sẻ Bộ 21 Đề thi HSG Tin học lớp 9 Đồng Tháp năm học 2026 – 2027 (Kèm đáp án và hướng dẫn giải chi tiết).

📌 Tổng Quan Tệp Tài Liệu Đề Thi HSG Tin Học Lớp 9 Đồng Tháp

Bộ tài liệu được sưu tầm, tuyển chọn và biên soạn kỹ lưỡng, bám sát cấu trúc đề thi chính thức của Sở GD&ĐT Tỉnh Đồng Tháp qua các kỳ thi gần đây.

Thông Tin Tài Liệu	Chi Tiết
Môn thi	Tin học (Khối 9)
Khu vực	Tỉnh Đồng Tháp
Năm học	2026 – 2027
Số lượng	21 Đề thi hoàn chỉnh
Định dạng	File PDF / Word (Dễ dàng tải & in ấn)
Đính kèm	Đáp án, Test case & Code mẫu (Pascal / C++ / Python)

Bộ 21 Đề Thi HSG Tin Học Lớp 9 Đồng Tháp 2026 – 2027 (Có Đáp Án)

Các đề ôn thi để chuẩn bị thi Cấp Huyện thì các em vào đường dẫn phía dưới để tham khảo giúp thầy nhé!

Bộ 21 Đề Thi HSG Tin Học Lớp 9 Đồng Tháp 2026 – 2027 (Có Đáp Án)

Đáp án đề thi HSG Tin học lớp 9 cấp thị xã Gò Công:

Đây là một đề HSG THCS khá hay, gồm 5 bài với mức độ từ cơ bản → vận dụng. Mình sẽ phân tích từng bài theo đúng phong cách luyện HSG:

Ý tưởng
Thuật toán
Độ phức tạp
Lưu ý dễ sai
Code Python dùng sys.stdin=open(...)
Giải thích từng dòng

Đáp Án Bài 1: DAY – Ngày lắng nghe:

Đề bài

Cho một ngày dạng

dd/mm

So sánh với

14/02

In ra

BEFORE

nếu trước

AFTER

nếu sau

EXACTLY

nếu đúng.

Phân tích

Ví dụ

15/01

Ngày 15 tháng 1

thì

15/1 < 14/2

=> BEFORE

Ví dụ

01/03

tháng 3

lớn hơn tháng 2

=> AFTER

Ý tưởng

Có hai trường hợp

Nếu tháng nhỏ hơn 2

BEFORE

Nếu tháng lớn hơn 2

AFTER

Nếu tháng bằng 2

So tiếp ngày.

day<14

BEFORE

day==14

EXACTLY

day>14

AFTER

Thuật toán

Đọc chuỗi
Tách ngày và tháng
Nếu month<2
      BEFORE
Nếu month>2
      AFTER
Nếu month==2
      day<14
            BEFORE
      day==14
            EXACTLY
      day>14
            AFTER

Độ phức tạp

Đọc đúng 1 lần

O(1)

Bộ nhớ

O(1)

Nhanh gần như tức thì.

Code Python

import sys
sys.stdin = open("DAY.INP", "r")
sys.stdout = open("DAY.OUT", "w")
s = input()
ngay, thang = map(int, s.split("/"))
if thang < 2:
    print("BEFORE")
elif thang > 2:
    print("AFTER")
else:
    if ngay < 14:
        print("BEFORE")
    elif ngay == 14:
        print("EXACTLY")
    else:
        print("AFTER")

Chú ý

Nhiều bạn so sánh

dd/mm

dưới dạng chuỗi

Ví dụ

9/2
14/2

sẽ sai.

Phải chuyển sang số nguyên.

Đáp Án Bài 2: SUNFLOWER

Đề

Có n bông hoa.

Hoa đặc biệt nếu số hạt là số nguyên tố.

Đếm có bao nhiêu hoa đặc biệt.

1≤n≤10000

ai≤10^12

Phân tích

Ví dụ

1 4 3

chỉ có

là nguyên tố.

Đáp án

Khó ở đâu?

ai≤10^12

Không thể sàng Eratosthenes.

Ta phải kiểm tra nguyên tố từng số.

Kiểm tra nguyên tố

Một số nguyên tố chỉ cần thử đến

√n

Ví dụ

√97≈9

chỉ thử

là đủ.

Thuật toán kiểm tra

Nếu

n<2

không nguyên tố.

Nếu

nguyên tố.

Nếu

chia hết cho 2

không nguyên tố.

Sau đó

3
5
7
9
11
...

tăng

đến

√n

Nếu chia hết

không nguyên tố.

Ngược lại

nguyên tố.

Vì sao đúng?

Nếu

n=a×b

thì luôn tồn tại

a≤√n

nên chỉ cần thử tới căn.

Thuật toán

ans=0
lặp qua từng ai
      nếu nguyên tố
             ans+=1
in ans

Độ phức tạp

Giả sử

M=max(ai)

Mỗi số

O(√M)

Ở đây

√10^12=10^6

Nên

O(n√M)

Trong thực tế rất nhanh vì:

gặp ước sẽ dừng sớm
nhiều số chẵn
n chỉ 10000

Code Python

 import sys
import math

sys.stdin = open("SUNFLOWER.INP", "r")
sys.stdout = open("SUNFLOWER.OUT", "w")


def nguyen_to(x):
    if x < 2:
        return False

    if x == 2:
        return True

    if x % 2 == 0:
        return False

    i = 3

    while i <= math.isqrt(x):
        if x % i == 0:
            return False
        i += 2

    return True


n = int(input())

a = list(map(int, input().split()))

dem = 0

for x in a:
    if nguyen_to(x):
        dem += 1

print(dem)
 

Vì sao dùng `math.isqrt()`

Thay vì

int(math.sqrt(x))

ta dùng

math.isqrt(x)

Ưu điểm

Chính xác với số rất lớn.
Không bị sai số số thực.
Nhanh hơn.

Các lỗi thường gặp

Sai 1

không phải số nguyên tố.

Sai 2

Quên xét

Sai 3

Thử đến

thay vì

√n

→ quá chậm.

Sai 4

Dùng

for i in range(2, x):

với

10^12

sẽ không chạy được.

Tổng kết

Bài	Thuật toán	Độ phức tạp	Độ khó
DAY	So sánh ngày, tháng	O(1)	★☆☆☆☆
SUNFLOWER	Kiểm tra số nguyên tố đến √n	O(n√M)	★★☆☆☆

Đáp Án Bài 3: ROBOT (4 điểm)

Đề bài

Có

n cây
vị trí robot là p
pin đủ đi được k đơn vị chỉ từ trái sang phải

Có n cây tại các vị trí

a1 < a2 < ... < an

Đếm xem robot thu hoạch được bao nhiêu cây.

Ví dụ

3 4

5 6 9

Robot

ở vị trí

đi được

đơn vị

nên tới

Các cây nằm trong đoạn

[3 ; 7]

là

5
6

=> đáp án

Phân tích

Robot KHÔNG quay lại.

Robot chỉ đi

p → p+k

Vậy cây được thu hoạch khi

p ≤ ai ≤ p+k

Bài toán trở thành:

Đếm bao nhiêu số nằm trong đoạn [L,R].

Ý tưởng 1 (dễ hiểu)

Duyệt toàn bộ mảng.

Nếu

p<=ai<=p+k

thì

dem+=1

Thuật toán

 Đọc dữ liệu

dem=0

For mỗi cây

    nếu p<=ai<=p+k

          dem++

In dem

Độ phức tạp

Có

n≤10^6

Chỉ duyệt đúng một lần.

Thời gian

O(n)

Bộ nhớ

O(n)

(vì lưu mảng)

Nếu đọc từng số cũng chỉ O(1) bộ nhớ.

Vì sao đúng?

Mỗi cây chỉ có hai khả năng

nằm trong đoạn
không nằm trong đoạn

Duyệt hết một lần sẽ không bỏ sót.

Code Python

import sys
sys.stdin = open("ROBOT.INP", "r")
sys.stdout = open("ROBOT.OUT", "w")
n, p, k = map(int, input().split())
a = list(map(int, input().split()))
dem = 0
for x in a:
    if p <= x <= p + k:
        dem += 1
print(dem)

Nếu muốn nhanh hơn?

Do dãy đã tăng dần

Có thể dùng

binary search

tìm

vị trí đầu tiên ≥ p
vị trí cuối cùng ≤ p+k

Độ phức tạp

O(log n)

nhưng đề này O(n) đã đủ.

Các lỗi thường gặp

Sai

if x>p and x<p+k

Sẽ bỏ mất cây ở

hoặc

p+k

Phải là

if p<=x<=p+k

Đáp Án Bài 4: LAVENDER

Đề

Có

m dòng

n cột

Ma trận

Đếm số phần tử

>=T

Ví dụ

Có

=>3

Phân tích

Không yêu cầu tìm vị trí.

Không yêu cầu sắp xếp.

Chỉ cần đếm.

Ý tưởng

Đọc từng số

Nếu

>=T

thì tăng biến đếm.

Thuật toán

Đọc
m n T
dem=0
Lặp m lần
      đọc một dòng
      duyệt n số
            nếu >=T
                  dem++
In dem

Độ phức tạp

Có

m,n≤1000

Nhiều nhất

10^6

phần tử.

Thời gian

O(mn)

Bộ nhớ

O(n)

vì chỉ lưu từng dòng.

Vì sao đúng?

Mỗi phần tử được xét đúng một lần.

Không bỏ sót.

Code

import sys

sys.stdin = open("LAVENDER.INP", "r")
sys.stdout = open("LAVENDER.OUT", "w")

m, n, T = map(int, input().split())

dem = 0

for _ in range(m):

    dong = list(map(int, input().split()))

    for x in dong:

        if x >= T:
            dem += 1

print(dem)

Tối ưu bộ nhớ

Không cần

a=[]

vì đề không yêu cầu dùng lại.

Đọc từng dòng là tốt nhất.

Lỗi thường gặp

Viết

if x>T

sai.

Đề là

>=T

Đáp Án Bài 5: ESSENCE

Đề

Cho chuỗi

Ví dụ

ABCCDZDC

Độ đậm đặc

số lần xuất hiện nhiều nhất của một ký tự.

Ví dụ

A :1

B :1

C :3

D :2

Z :1

Đáp án

Phân tích

Đây chính là

tần số lớn nhất.

Cách 1 (đơn giản)

Dùng Dictionary.

Ý tưởng

Duyệt chuỗi.

Nếu ký tự chưa có

thêm vào.

Nếu có

tăng lên 1.

Sau đó lấy giá trị lớn nhất.

Thuật toán

Đọc chuỗi

Dictionary rỗng

For ký tự

      tăng số lần xuất hiện

In max(dictionary.values())

Độ phức tạp

Chuỗi dài

Thời gian

O(n)

Bộ nhớ

O(26)

vì chỉ có chữ cái tiếng Anh in hoa.

Vì sao đúng?

Dictionary lưu đúng số lần xuất hiện từng ký tự.

Giá trị lớn nhất chính là đáp án.

Code Python

import sys

sys.stdin = open("ESSENCE.INP", "r")
sys.stdout = open("ESSENCE.OUT", "w")

s = input()

dem = {}

for ch in s:

    if ch not in dem:
        dem[ch] = 1
    else:
        dem[ch] += 1

print(max(dem.values()))

Cách 2 (đẹp hơn)

Dùng mảng 26 phần tử.

Ý tưởng

A ->0

B ->1

...

Z ->25

Mỗi lần gặp

ord(ch)-ord('A')

thì tăng lên.

Code Python

import sys

sys.stdin = open("ESSENCE.INP", "r")
sys.stdout = open("ESSENCE.OUT", "w")

s = input()

cnt = [0] * 26

for ch in s:

    cnt[ord(ch) - ord('A')] += 1

print(max(cnt))

Vì sao mảng nhanh hơn Dictionary?

Truy cập trực tiếp theo chỉ số (O(1) với hằng số rất nhỏ).
Không cần băm (hash).
Chỉ có 26 chữ cái nên rất phù hợp.

Tổng kết cả đề

Bài	Ý tưởng	Độ phức tạp	Bộ nhớ	Mức độ
Bài 1 – DAY	So sánh ngày, tháng	O(1)	O(1)	⭐
Bài 2 – SUNFLOWER	Kiểm tra số nguyên tố đến √n	O(n√M)	O(1)	⭐⭐
Bài 3 – ROBOT	Đếm số vị trí trong đoạn `[p, p+k]`	O(n)	O(n) (hoặc O(1) nếu đọc từng số)	⭐⭐
Bài 4 – LAVENDER	Duyệt ma trận, đếm số ≥ T	O(mn)	O(n)	⭐
Bài 5 – ESSENCE	Đếm tần suất ký tự (Dictionary hoặc mảng 26 phần tử)	O(n)	O(26)	⭐

🎯 Nhận xét về Cấu Trúc Trọng Tâm Trong Đề Thi HSG Tin Học 9 Đồng Tháp

Đây là đề HSG THCS thiên về kỹ năng lập trình cơ bản, chưa yêu cầu các thuật toán nâng cao như quy hoạch động, đồ thị hay cây dữ liệu.

Các kiến thức chính được kiểm tra gồm:

Bài 1: Rẽ nhánh (if...elif...else).
Bài 2: Hàm kiểm tra số nguyên tố và tối ưu đến √n.
Bài 3: Duyệt mảng, xử lý đoạn giá trị; có thể mở rộng bằng tìm kiếm nhị phân.
Bài 4: Duyệt ma trận và đếm theo điều kiện.
Bài 5: Đếm tần suất bằng dict hoặc mảng đếm.

Đây là một đề rất phù hợp để ôn luyện cho học sinh mới bắt đầu thi HSG Tin học vì bao quát nhiều kỹ năng nền tảng quan trọng.

💡 Lời khuyên từ Vi Tính Tấn Dân: Đề thi Tin học lớp 9 hiện nay hướng nhiều đến tư duy thuật toán tối ưu thời gian ( $O(N \log N)$ hoặc $O(N)$ ). Luyện tập thường xuyên với bộ đề này sẽ giúp bạn làm quen với áp lực thời gian và hạn chế tối đa các lỗi quá thời gian (Time Limit Exceeded).
73 Đề thi HSG Tin học Python THCS cấp tỉnh Tiền Giang có ĐÁP ÁN (Mới & Chọn Lọc)

📥 Link Tải Bộ 21 Đề Thi HSG Tin Học 9 Đồng Tháp (File Chuẩn)

Các bạn học sinh và thầy cô có thể tải trọn bộ đề thi hoàn toàn miễn phí theo đường dẫn dưới đây:

👉 [LINK TẢI TRỌN BỘ 21 ĐỀ THI HSG TIN HỌC LỚP 9 ĐỒNG THÁP (PDF/WORD)]

(Lưu ý: Nếu gặp bất kỳ lỗi nào trong quá trình tải file, vui lòng để lại bình luận bên dưới để Vi Tính Tấn Dân hỗ trợ kịp thời!)

🖥️ Vi Tính Tấn Dân – Đồng Hành Cùng Tri Thức & Công Nghệ

Bên cạnh việc chia sẻ kiến thức và tài liệu học tập miễn phí, Vi Tính Tấn Dân tự hào là đơn vị uy tín chuyên cung cấp:

💻 Dàn máy tính PC Lập trình – Học tập – Chơi game cấu hình tối ưu, giá rẻ.
🛠️ Dịch vụ sửa chữa, nâng cấp Laptop & PC nhanh chóng, tận tâm tại Đồng Tháp.
🎧 Linh phụ kiện máy tính chính hãng (Bàn phím, chuột, màn hình, SSD…).

7. Cách thức đăng ký và đóng học phí như thế nào?

Bạn có thể liên hệ trực tiếp với Thầy qua các kênh sau để được tư vấn và nhận báo giá ưu đãi:

Số điện thoại / Zalo: 0937.179.278
Hình thức đóng phí: Chuyển khoản ngân hàng hoặc nộp trực tiếp tại cơ sở (nếu học offline).

Đạt giải 3 học sinh giỏi tin học cấp tỉnh

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ệ:

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!

Dưới đây là phần Câu Hỏi Thường Gặp (FAQ) chuẩn SEO dành riêng cho bài viết. Đoạn này không chỉ giúp giữ chân người đọc lâu hơn mà còn rất dễ được Google đưa lên vị trí Featured Snippet (Top 0) hoặc hiển thị trong mục “Mọi người cũng hỏi”:

❓ Câu Hỏi Thường Gặp (FAQ) – Đề Thi HSG Tin Học 9 Đồng Tháp

1. Bộ đề thi HSG Tin học lớp 9 Đồng Tháp có đáp án chi tiết không?

Trả lời: Có. Bộ 21 đề thi HSG Tin học 9 Đồng Tháp do Vi Tính Tấn Dân tổng hợp đều đi kèm đáp án, hướng dẫn giải chi tiết, test case mẫu và code tham khảo bằng các ngôn ngữ phổ biến như C++, Python và Pascal.

2. Tải bộ đề thi HSG Tin học 9 Đồng Tháp 2026 – 2027 có mất phí không?

Trả lời: Hoàn toàn MIỄN PHÍ. Bạn chỉ cần bấm vào đường link Google Drive được đính kèm trong bài viết là có thể tải toàn bộ file PDF/Word về máy để in ấn và học tập dễ dàng.

3. Đề thi HSG Tin học lớp 9 Đồng Tháp thường sử dụng ngôn ngữ lập trình nào?

Trả lời: Hiện nay, các kỳ thi Học sinh giỏi Tin học THCS tại Đồng Tháp ưu tiên sử dụng ngôn ngữ C++ và Python nhờ tối ưu tốc độ và thư viện phong phú. Tuy nhiên, một số bài thi vẫn chấp nhận Pascal. Học sinh nên tập trung luyện tập kĩ năng tư duy thuật toán trên C++ hoặc Python để đạt điểm tối đa.

4. Học sinh lớp 9 cần tập trung những dạng thuật toán nào để thi HSG Tin học?

Trả lời: Cấu trúc đề thi HSG Tin học 9 Đồng Tháp thường xoay quanh các dạng bài trọng tâm:

Xử lý chuỗi, mã hóa và số học cơ bản.
Thuật toán tìm kiếm nhị phân, kỹ thuật hai con trỏ, mảng cộng dồn.
Sắp xếp tối ưu $O(N \log N)$ .
Quy hoạch động cơ bản (Đếm cách, Tối ưu hóa).

5. Học lập trình nên chọn cấu hình máy tính/laptop như thế nào?

Trả lời: Để phục vụ tốt việc học lập trình C++, Python và chạy các phần mềm như Code::Blocks, VS Code, PyCharm…, bạn nên chọn PC/Laptop có cấu hình tối thiểu:

CPU: Core i3/Ryzen 3 trở lên (thế hệ mới).
RAM: Tối thiểu 8GB.
Ổ cứng: SSD 256GB để khởi động phần mềm mượt mà.

📌 Nếu bạn cần tư vấn chọn máy tính học tập – lập trình phù hợp với ngân sách, hãy liên hệ ngay hotline của Vi Tính Tấn Dân để được hỗ trợ tốt nhất!

6 BÀI TẬP C++ CHUẨN THI HỌC SINH GIỎI MỚI NHẤT 2026

Tài liệu này tổng hợp các bài toán lập trình C++ từ căn bản đến nâng cao được thiết kế hoàn toàn theo format các kỳ thi Học sinh giỏi (HSG) các cấp. Mỗi bài toán đều quy định rõ ràng tệp dữ liệu vào, tệp kết quả ra, giới hạn dữ liệu (subtasks) và kèm theo mã nguồn giải mẫu tối ưu, sử dụng định danh biến bằng tiếng Việt trực quan, giúp học sinh nắm vững bản chất thuật toán.

Bài 1: Tính toán kích thước hình học (HCN)

Bài toán: Cho hai số thực dương là chiều dài và chiều rộng của một mảnh vườn hình chữ nhật. Tính chu vi và diện tích mảnh vườn. Kết quả làm tròn đến 2 chữ số thập phân.

Thời gian chạy: 1.0 giây
Dữ liệu vào (HCN.INP): Một dòng chứa hai số thực $a$ và $b$ (0 < a, b ≤ 10^6).
Dữ liệu ra (HCN.OUT): Một dòng chứa chu vi và diện tích, cách nhau một khoảng trắng.

Ví dụ:

Input (HCN.INP): 5.5 3.2
Output (HCN.OUT): 17.40 17.60

Code C++ tham khảo:

C++

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    freopen("HCN.INP", "r", stdin);
    freopen("HCN.OUT", "w", stdout);

    double dai, rong;
    if (cin >> dai >> rong) {
        double chu_vi = (dai + rong) * 2;
        double dien_tich = dai * rong;
        cout << fixed << setprecision(2) << chu_vi << " " << dien_tich << endl;
    }
    return 0;
}

Bài 2: Khảo sát số nguyên tố lớn (SNT)

Bài toán: Kiểm tra số nguyên dương $N$ có phải là số nguyên tố hay không.

Thời gian chạy: 1.0 giây
Dữ liệu vào (SNT.INP): Số nguyên dương $N$ .
- Subtask 1 (60%): N ≤ 10^6
- Subtask 2 (40%): N ≤ 10^12
Dữ liệu ra (SNT.OUT): In ra YES nếu là số nguyên tố, ngược lại in NO.

Ví dụ:

Input (SNT.INP): 97
Output (SNT.OUT): YES

Code C++ tham khảo:

C++

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    freopen("SNT.INP", "r", stdin);
    freopen("SNT.OUT", "w", stdout);

    long long n; 
    cin >> n;

    if (n < 2) {
        cout << "NO\n";
        return 0;
    }

    bool la_snt = true;
    long long can_bac_hai = sqrt(n);
    
    for (long long i = 2; i <= can_bac_hai; i++) {
        if (n % i == 0) {
            la_snt = false;
            break;
        }
    }

    if (la_snt) cout << "YES\n";
    else cout << "NO\n";
    
    return 0;
}

Bài 3: Thống kê ký tự nguyên âm (CHUOI)

Bài toán: Đếm số lượng nguyên âm (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) trong một chuỗi ký tự.

Thời gian chạy: 1.0 giây
Dữ liệu vào (CHUOI.INP): Chuỗi ký tự $S$ (chiều dài ≤ 1000).
Dữ liệu ra (CHUOI.OUT): Số lượng nguyên âm đếm được.

Ví dụ:

Input (CHUOI.INP): Lap trinh C++ Chuan HSG
Output (CHUOI.OUT): 5

Code C++ tham khảo:

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    freopen("CHUOI.INP", "r", stdin);
    freopen("CHUOI.OUT", "w", stdout);

    string van_ban;
    getline(cin, van_ban); 

    int bien_dem = 0;
    for (int i = 0; i < van_ban.length(); i++) {
        char ky_tu = tolower(van_ban[i]);
        if (ky_tu == 'a' || ky_tu == 'e' || ky_tu == 'i' || ky_tu == 'o' || ky_tu == 'u') {
            bien_dem++;
        }
    }

    cout << bien_dem << endl;
    return 0;
}

Bài 4: Sắp xếp và tối ưu mảng số (SAPXEP)

Bài toán: Sắp xếp mảng $N$ số nguyên theo thứ tự tăng dần.

Thời gian chạy: 1.0 giây
Dữ liệu vào (SAPXEP.INP): * Dòng 1: Số nguyên $N$ (N ≤ 10^5).
- Dòng 2: $N$ số nguyên cách nhau một dấu cách.
Dữ liệu ra (SAPXEP.OUT): Mảng đã sắp xếp tăng dần.

Ví dụ:

Input (SAPXEP.INP):
5
12 -3 7 0 5
Output (SAPXEP.OUT): -3 0 5 7 12

Code C++ tham khảo:

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    freopen("SAPXEP.INP", "r", stdin);
    freopen("SAPXEP.OUT", "w", stdout);

    int so_luong;
    if (cin >> so_luong) {
        vector<int> danh_sach(so_luong);
        
        for (int i = 0; i < so_luong; i++) {
            cin >> danh_sach[i];
        }

        sort(danh_sach.begin(), danh_sach.end());

        for (int i = 0; i < so_luong; i++) {
            cout << danh_sach[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

Bài 5: Tối giản phân số bằng OOP (PHANSO)

Bài toán: Dùng lập trình hướng đối tượng xây dựng lớp Phân số để cộng 2 phân số và in ra kết quả tối giản.

Thời gian chạy: 1.0 giây
Dữ liệu vào (PHANSO.INP): 4 số nguyên: Tử 1, Mẫu 1, Tử 2, Mẫu 2 (trong khoảng -10^4 đến 10^4).
Dữ liệu ra (PHANSO.OUT): Phân số tổng tối giản (nếu mẫu là 1 chỉ in tử số).

Ví dụ:

Input (PHANSO.INP): 1 6 2 3
Output (PHANSO.OUT): 5/6

Code C++ tham khảo:

C++

#include <iostream>
#include <cmath>
using namespace std;

class PhanSo {
private:
    long long tu, mau;

    long long tim_ucln(long long a, long long b) {
        a = abs(a); b = abs(b);
        while (b != 0) {
            long long tam = b;
            b = a % b;
            a = tam;
        }
        return a;
    }

public:
    PhanSo(long long t = 0, long long m = 1) {
        tu = t;
        mau = (m == 0) ? 1 : m;
    }

    void toi_gian() {
        long long ucln = tim_ucln(tu, mau);
        tu /= ucln;
        mau /= ucln;
        if (mau < 0) { 
            tu = -tu;
            mau = -mau;
        }
    }

    PhanSo cong(PhanSo doi_tac) {
        PhanSo ket_qua;
        ket_qua.tu = this->tu * doi_tac.mau + doi_tac.tu * this->mau;
        ket_qua.mau = this->mau * doi_tac.mau;
        ket_qua.toi_gian();
        return ket_qua;
    }

    void in_ket_qua() {
        if (mau == 1) cout << tu << endl;
        else cout << tu << "/" << mau << endl;
    }
};

int main() {
    freopen("PHANSO.INP", "r", stdin);
    freopen("PHANSO.OUT", "w", stdout);

    long long t1, m1, t2, m2;
    if (cin >> t1 >> m1 >> t2 >> m2) {
        PhanSo ps1(t1, m1), ps2(t2, m2);
        PhanSo tong = ps1.cong(ps2);
        tong.in_ket_qua();
    }
    return 0;
}

Bài 6: Tìm số xuất hiện nhiều nhất (TIMSO)

Bài toán: Tìm số xuất hiện nhiều nhất trong dãy. Nếu có nhiều số cùng số lần xuất hiện, chọn số nhỏ nhất.

Thời gian chạy: 1.0 giây
Dữ liệu vào (TIMSO.INP): * Dòng 1: $N$ (N ≤ 10^5).
- Dòng 2: $N$ số nguyên.
Dữ liệu ra (TIMSO.OUT): Giá trị số tìm được và số lần xuất hiện.

Ví dụ:

Input (TIMSO.INP):
7
2 3 5 2 3 8 2
Output (TIMSO.OUT): 2 3

Code C++ tham khảo:

C++

#include <iostream>
#include <map>
using namespace std;

int main() {
    freopen("TIMSO.INP", "r", stdin);
    freopen("TIMSO.OUT", "w", stdout);

    int n;
    if (cin >> n) {
        map<int, int> bo_dem;
        int so_nhap;
        
        for (int i = 0; i < n; i++) {
            cin >> so_nhap;
            bo_dem[so_nhap]++; 
        }

        int max_tan_suat = 0;
        int gia_tri_toi_uu = 0;

        for (auto phan_tu : bo_dem) {
            if (phan_tu.second > max_tan_suat) {
                max_tan_suat = phan_tu.second;
                gia_tri_toi_uu = phan_tu.first;
            }
        }

        cout << gia_tri_toi_uu << " " << max_tan_suat << endl;
    }
    return 0;
}

Tags: #HocLapTrinhC #LapTrinhC++ #ThiHSGTinHoc #CodeC++CoBan #GiaiThuatC++ #DeThiTinHoc #TuHocC++

10 CHƯƠNG HƯỚNG DẪN HỌC LẬP TRÌNH C++ TỪ CƠ BẢN ĐẾN NÂNG CAO

1. Giới thiệu về C++

C++ là ngôn ngữ lập trình được phát triển bởi Bjarne Stroustrup vào năm 1985 dựa trên ngôn ngữ C. Đây là một trong những ngôn ngữ mạnh mẽ và phổ biến nhất hiện nay, được sử dụng để phát triển:

Phần mềm máy tính
Game
Hệ điều hành
Trí tuệ nhân tạo (AI)
Ứng dụng tài chính
Phần mềm nhúng

Ưu điểm của C++

Tốc độ xử lý nhanh.
Hỗ trợ lập trình hướng đối tượng (OOP).
Có thư viện phong phú.
Được sử dụng rộng rãi trong công nghiệp.

CHƯƠNG 1: LÀM QUEN VỚI C++

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

Trong các kỳ thi Học sinh giỏi Tin học, hệ thống chấm thi tự động 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 đọc/ghi file chính xác và nhanh chóng.

Q: 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?

Thay vì duyệt từ 1 đến N, chúng ta chỉ cần duyệt từ 1 đến căn bậc hai của N. Với mỗi ước d tìm được, xác định thêm ước N/d và kiểm tra xem có phải là số chính phương hay không bằng math.isqrt(). Cách này giúp độ phức tạp giảm xuống O(sqrt(N)), chạy mượt mà với N lên đến 10^9.

1. Cấu trúc chương trình C++

Ví dụ:

#include <iostream>
using namespace std;

int main() {
    cout << "Xin chao C++";
    return 0;
}

Giải thích

#include <iostream>: Thư viện nhập xuất.
using namespace std;: Sử dụng không gian tên chuẩn.
main(): Hàm chính của chương trình.
cout: Xuất dữ liệu ra màn hình.
return 0;: Kết thúc chương trình.

2. Biến và kiểu dữ liệu

Các kiểu dữ liệu cơ bản

Kiểu	Ý nghĩa	Ví dụ
int	Số nguyên	5
float	Số thực	3.14
double	Số thực độ chính xác cao	3.141592
char	Ký tự	‘A’
bool	Đúng/Sai	true
string	Chuỗi ký tự	“Hello”

Ví dụ

int age = 18;
float diem = 8.5;
char grade = 'A';
string name = "Tan";

Bài tập

Bài 1

Nhập tên và tuổi của một người rồi xuất ra màn hình.

Ví dụ

Input

Tan
18

Output

Ten: Tan
Tuoi: 18

CHƯƠNG 2: CÂU LỆNH ĐIỀU KIỆN

1. Câu lệnh if

if (dieu_kien)
{
    // câu lệnh
}

Ví dụ:

int a;

cin >> a;

if (a > 0)
{
    cout << "So duong";
}

2. Câu lệnh if…else

if(a % 2 == 0)
{
    cout << "So chan";
}
else
{
    cout << "So le";
}

3. Câu lệnh switch

switch(n)
{
    case 1:
        cout<<"Mot";
        break;

    case 2:
        cout<<"Hai";
        break;

    default:
        cout<<"Khong hop le";
}

Bài tập

Bài 2

Nhập số nguyên n.

Nếu n > 0 in “So duong”
Nếu n < 0 in “So am”
Nếu n = 0 in “So 0”

CHƯƠNG 3: VÒNG LẶP

1. Vòng lặp for

for(int i=1;i<=10;i++)
{
    cout<<i<<" ";
}

Kết quả:

1 2 3 4 5 6 7 8 9 10

2. Vòng lặp while

int i=1;

while(i<=5)
{
    cout<<i<<" ";
    i++;
}

Bài tập

Bài 3

Tính tổng:

S = 1 + 2 + 3 + ... + n

Ví dụ:

Input

Output

CHƯƠNG 4: HÀM (FUNCTION)

Hàm giúp chia chương trình thành các phần nhỏ.

Ví dụ:

int tong(int a, int b)
{
    return a+b;
}

int main()
{
    cout<<tong(3,5);

    return 0;
}

Kết quả:

Bài tập

Viết hàm:

Tính giai thừa n!
Kiểm tra số nguyên tố.
Tính UCLN của hai số.

CHƯƠNG 5: MẢNG (ARRAY)

Khai báo

int a[100];

Nhập mảng

int n;

cin>>n;

for(int i=0;i<n;i++)
{
    cin>>a[i];
}

Xuất mảng

for(int i=0;i<n;i++)
{
    cout<<a[i]<<" ";
}

Bài tập

Cho mảng n số nguyên.

Hãy:

Tính tổng các phần tử.
Tìm số lớn nhất.
Tìm số nhỏ nhất.
Sắp xếp tăng dần.

CHƯƠNG 6: CHUỖI (STRING)

Ví dụ:

string s;

getline(cin,s);

cout<<s;

Một số hàm thường dùng

s.length();      // độ dài
s.substr(0,3);   // cắt chuỗi
s.find("abc");   // tìm chuỗi

Bài tập

Nhập một chuỗi.

Đếm số ký tự.
Đếm số chữ cái.
Đếm số từ.
Đảo ngược chuỗi.

CHƯƠNG 7: CON TRỎ

Con trỏ là biến lưu địa chỉ của biến khác.

Ví dụ:

int a=10;

int *p=&a;

cout<<a<<endl;
cout<<&a<<endl;
cout<<p<<endl;
cout<<*p<<endl;

CHƯƠNG 8: LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG (OOP)

1. Class

class Student
{
public:

    string name;
    int age;

    void display()
    {
        cout<<name<<" "<<age;
    }
};

2. Tạo đối tượng

Student s;

s.name="Tan";

s.age=18;

s.display();

Các khái niệm OOP quan trọng

Encapsulation (Đóng gói)

Ẩn dữ liệu bằng từ khóa:

private

Inheritance (Kế thừa)

class Animal
{
};

class Dog : public Animal
{
};

Polymorphism (Đa hình)

Cho phép cùng tên hàm nhưng hoạt động khác nhau.

Abstraction (Trừu tượng)

Ẩn chi tiết cài đặt và chỉ cung cấp chức năng cần thiết.

CHƯƠNG 9: THƯ VIỆN STL

STL (Standard Template Library) là thư viện cực kỳ quan trọng trong C++.

Vector

vector<int> a;

a.push_back(10);

a.push_back(20);

cout<<a.size();

Stack

stack<int> st;

st.push(1);

st.push(2);

st.pop();

Queue

queue<int> q;

q.push(5);

q.push(10);

q.pop();

Map

map<string,int> mp;

mp["Tan"]=18;

cout<<mp["Tan"];

CHƯƠNG 10: THUẬT TOÁN NÂNG CAO

Sau khi học xong C++ cơ bản, bạn nên học:

1. Đệ quy (Recursion)

Ví dụ tính giai thừa:

int gt(int n)
{
    if(n==0)
        return 1;

    return n*gt(n-1);
}

2. Sắp xếp

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

3. Tìm kiếm

Linear Search
Binary Search

4. Quy hoạch động (Dynamic Programming)

Ví dụ:

Dãy Fibonacci
Balo 0/1
Đường đi ngắn nhất

BÀI TẬP TỔNG HỢP

Bài 1

Nhập n.

Tính:

S = 1² + 2² + 3² + ... + n²

Bài 2

Nhập mảng n số nguyên.

In ra:

Số lớn nhất
Số nhỏ nhất
Trung bình cộng
Mảng sau khi sắp xếp

Bài 3

Viết chương trình quản lý sinh viên gồm:

Mã sinh viên
Họ tên
Tuổi
Điểm trung bình

Chức năng:

Thêm sinh viên
Xóa sinh viên
Sửa thông tin
Tìm kiếm
Sắp xếp theo điểm
Lưu dữ liệu ra file

LỘ TRÌNH HỌC C++ ĐỀ XUẤT

Tuần 1

Biến
Kiểu dữ liệu
if, switch
for, while

Tuần 2

Hàm
Mảng
Chuỗi
Con trỏ

Tuần 3

Struct
Class
OOP

Tuần 4

Vector
Stack
Queue
Map
Thuật toán cơ bản

Tuần 5 trở đi

Đệ quy
Thuật toán nâng cao
Quy hoạch động
Giải bài tập trên các trang OJ như Codeforces, LeetCode, VNOI.

Kết luận

C++ là ngôn ngữ mạnh mẽ, phù hợp cho cả người mới bắt đầu và lập trình viên chuyên nghiệp. Hãy học theo thứ tự:

Cơ bản → Hàm → Mảng → Chuỗi → Con trỏ → OOP → STL → Thuật toán → Dự án thực tế

Kiên trì luyện tập mỗi ngày sẽ giúp bạn thành thạo C++ và có nền tảng tốt để học các lĩnh vực như AI, lập trình game, phát triển phần mềm và thi lập trình cạnh tranh.

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

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:

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

Câu 1: Chở Hàng Giúp Mẹ (Chohang.inp / Chohang.out)

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

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

3. Code Python Chuẩn

Câu 2: Tìm Dãy Hạt Mẫu (Vongtay.inp / Vongtay.out)

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

2. Phân tích thuật toán

3. Code Python Chuẩn

Câu 3: Tính Toán Chi Phí & Bước Đi (Tinhtoan.inp / Tinhtoan.out)

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

2. Phân tích thuật toán

3. Code Python Chuẩn

Câu 4: Sắp Xếp Trò Chơi Lễ Hội (Lehoi.inp / Lehoi.out)

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

2. Phân tích thuật toán & Chiến lược Tham ăn (Greedy)

3. Code Python Chuẩn

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?

Làm thế nào để code Python chạy nhanh hơn trên các test bài tập lớn?

Từ khoá SEO

Hashtags

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ệ:

Hướng Dẫn Giải Chi Tiết Đề Thi HSG Tin Học Lớp 9 Tỉnh Bình Phước (2018 – 2019) Bằng Python

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:

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

Bài 1: Chu Vi Tam Giác (CHUVI.INP / CHUVI.OUT)

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

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

3. Code Python Chuẩn

Bài 2: Số Lượng Chữ Số (SOCHUSO.INP / SOCHUSO.OUT)

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

2. Phân tích thuật toán

3. Code Python Chuẩn

Bài 3: Đếm Số Nguyên Tố (DEMNT.INP / DEMNT.OUT)

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

2. Phân tích thuật toán & Tối ưu hóa

3. Code Python Chuẩn

Bài 4: Xuất Hiện Nhiều Nhất (XUATHIEN.INP / XUATHIEN.OUT)

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

2. Phân tích thuật toán & Xử lý Ràng buộc

3. Code Python Chuẩn

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

Tại sao lại dùng dict.get(val, 0) + 1 thay vì mảng danh sách trong Bài 4?

Thuật toán Sàng Eratosthenes trong Bài 3 chạy tốt đến phạm vi nào?

Hashtags

Thông Tin Liên Hệ:

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 2022 – 2023) Bằng Python

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:

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

Bài 1: Cặp Số Tương Đồng (SIMILAR.INP / SIMILAR.OUT)

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

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

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

4. Code Python Chuẩn

Bài 2: Hình Chữ Nhật Lớn Nhất (DIENTICH.INP / DIENTICH.OUT)

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

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

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

4. Code Python Chuẩn

Bài 3: Trò Chơi Xâu Ký Tự (STRGAME.INP / STRGAME.OUT)

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

2. Phân tích thuật toán & Chiến thuật Tham ăn (Greedy)

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

4. Code Python Chuẩn

Bài 4: Khoanh Vùng Phân Loại (VUONCAY.INP / VUONCAY.OUT)

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

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

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

4. Code Python Chuẩn

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

Tại sao lại dùng mảng cố định 64 phần tử ở Bài 1?

Làm thế nào để giải các bài toán ma trận lưới 2D không bị vượt quá thời gian (TLE) trong Python?

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ệ:

SEO Keywords

Hashtags

Tại sao lại dùng `dict.get(val, 0) + 1` thay vì mảng danh sách trong Bài 4?

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