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.

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

Rate this post

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

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ÁC GIẢ

thanhcong@kiennhan

MỜI BẠN ĐẶT CÂU HỎI ? MÌNH SẼ GIẢI ĐÁP HẾT !