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
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:
Yêu cầu:
a) Tìm các số nguyên tố từ A đến B
Ví dụ:
Các số nguyên tố là:
b) Tìm ƯCLN của A và B
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ụ:
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:
thì ít nhất một trong hai số a, b phải:
Ví dụ:
Ta chỉ cần kiểm tra đến:
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 TrueGiải thích
Nếu:
thì chắc chắn không phải số nguyên tố.
Thử các ước từ 2 đến √n.
Nếu:
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:
Vì range() không lấy giá trị cuối nên phải dùng B + 1.
Ví dụ:
sẽ duyệt:
Sau đó kiểm tra từng số:
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:
Lặp lại cho đến khi:
Khi đó:
Ví dụ UCLN(10, 25)
Ta có:
nên:
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:
Kết quả:
Đúng với ví dụ trong đề.
6. Độ phức tạp Bài 1
Có:
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:
Với B < 100 thì cực kỳ nhanh.
Thuật toán ƯCLN
Thuật toán Euclid có độ phức tạp:
Đâ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à:
1. Viết thử ra giấy
Ta có:
Ví dụ:
Ta có:
Tổng số cây:
Chưa đến cây thứ 12.
Tiếp theo:
Các cây:
Do đó:
Đúng với ví dụ của đề.
2. Cách 1 — Mô phỏng đơn giản
Vì đề cho:
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:
Ví dụ N = 12:
Vì:
nên đáp án là:
3. Độ phức tạp cách 1
Ta cần tìm k sao cho:
Mà:
nên:
Suy ra:
Vì vậy cách mô phỏng có độ phức tạp:
Với:
thì khoảng:
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
3. Nhận xét quan trọng
Gọi tổng toàn bộ dãy là:
S
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:
10
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à:
5
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ì:
k = 8
7
6
5
4
3
2
1
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:
30
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:
3
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:
8
Kiện tiếp theo 8:
8 + 8 = 16 > 15
Không được.
Xe 2:
8
Xe 3
Đặt:
8
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:
x
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ả:
5
Output:
5
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:
Đạ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
Thông Tin Liên Hệ:
ta
Vi Tính Tấn Dân – Đồng Hành Cùng Tri Thức & Công Nghệ
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…).
