Danh mục: 22 Đề Thi Học Sinh Giỏi Tin Học THCS Tân Phước 2021–2022

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

Đề 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.

Giải Bài 3 Trò chơi với băng số và Bài 4 Xếp hàng hóa bằng Python

Trong bài viết này, chúng ta sẽ cùng giải chi tiết hai bài toán lập trình Python thường gặp trong các đề thi học sinh giỏi Tin học:

Bài 3: Trò chơi với băng số
Bài 4: Xếp hàng hóa

Mỗi bài đều được trình bày theo hướng dễ hiểu, phù hợp cho học sinh mới học thuật toán, đồng thời có phân tích ý tưởng, thuật toán, code Python, ví dụ minh họa và độ phức tạp.

PHẦN 1. 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à:

target = 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 target?

Giả sử:

target = 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:

target = S // k

Bước 6

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

Nếu:

tong + a[i] > target

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

Nếu:

tong + a[i] == target

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")

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

tong_all = sum(a)

# Thử số đoạn từ lớn xuống nhỏ
for k in range(n, 0, -1):

    # Tổng không chia hết cho k
    if tong_all % k != 0:
        continue

    target = tong_all // k

    # Nếu target nhỏ hơn phần tử lớn nhất
    # thì chắc chắn không thể chia
    if target < max(a):
        continue

    tong = 0
    dem = 0
    ok = True

    for x in a:

        tong += x

        # Tổng một đoạn đã vượt target
        if tong > target:
            ok = False
            break

        # Hoàn thành một đoạn
        if tong == target:
            dem += 1
            tong = 0

    # Kiểm tra có đúng k đoạn hay không
    if ok and tong == 0 and dem == k:
        print(k)
        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 tong

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.

PHẦN 2. 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