Thẻ: giải đề thi hsg tin học lớp 9

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:

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

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

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

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

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

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

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.

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

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

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:

1. Dây bao quanh chu vi ngoài cùng của mảnh vườn:

   • Chu vi = 2 * (M + N).

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

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

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

 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

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:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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!

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

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

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

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

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

import sys

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

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

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

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

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

uoc_chung_lon_nhat = 0

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

print(uoc_chung_lon_nhat)

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

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

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

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

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

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

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

Độ phức tạp:

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

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

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

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

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

4. Code Python Chuẩn

import sys

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

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

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

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

bang_phu = [1] * so_luong_qua
so_qua_lon_nhat = 1

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

print(so_qua_lon_nhat)

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

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

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

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

Quy hoạch động:

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

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

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

Độ phức tạp:

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

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

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

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

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

4. Code Python Chuẩn

import sys

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

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

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

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

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

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

print(chi_phi[so_luong_o])

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

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

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

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

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

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

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

Hashtags

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

Nếu bạn thấy hay ! xin bạn 1 phút ! vui lòng đánh giá 5 sao cho trang website của chúng tôi ! để có động lực làm thêm nhiều bài hay nữa ! cảm ơn quý khách nhé !

 Thông Tin Liên Hệ:

• Website: vitinhtandan.com

• Hotline/Zalo: (0937.179.278)

• Địa chỉ: (Tổ 5, Ấp Tân Lược 1, xã Tân Hương, Đồng Tháp)

Chúc các bạn học sinh ôn luyện thật tốt và đạt kết quả cao nhất trong kỳ thi Học sinh giỏi Tin học lớp 9 sắp tới!