[trustindex no-registration=google]

Tổng hợp 75 Đề thi HSG Tin học THCS Python Cấp Tỉnh (Có Code Giải Chi Tiết – Độ phức tạp) cập nhật mới nhất năm 2026 – 2027

Tải đề Thi Đề thi HSG Tin học THCS Python Cấp Tỉnh file PDF:

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

    1. Giải đề 1 và đáp án thi Học sinh giỏi tin học Python C++ THCS có tài liệu ôn thi
    2. Giải đề 2 và đáp án thi Học sinh giỏi tin học Python C++ THCS có tài liệu ôn thi
    3. Giải đề 3 thi học sinh giỏi tin học lập trình Python có đáp án
    4. Giải đề 4 ôn thi học sinh giỏi Tin Học THCS lập trình Python có đáp án
    5. Giải đề 5 và đáp án thi HSG Tin Python có số Pell.
    6. Giải đề 6 và đáp án bồi dưỡng học sinh giỏi tin 10 có số Armstrong
    7. Giải đề 7 và đáp án  thi học sinh giỏi tin học 10 Python có số Collatz
    8. Giải đề 8 trong 20 đề Bồi dưỡng học sinh giỏi Tin học lớp 9 có số Kaprekar.
    9. Giải đề 9 thi HSG Tin học lớp 8 lập trình Python có số Happy
    10. Giải đề 10 thi tin học trẻ THPT có bài  In các xâu con trong xâu s.
    11. Đề thi hsg tin 11 python có đáp án hay nhất 2024
    12. 12 đề và đáp án thi HSG tin Python có sắp xếp
    13. Đề 13 thi học sinh giỏi Tin học THCS có đáp án hay nhất năm 2024.
    14. 14 đề bồi dưỡng học sinh giỏi tin học lớp 7, 8, 9 THCS mới nhất !
    15. 15 Đề thi học sinh giỏi Tin học lớp 9 cấp huyện hay nhất 2024 – 2025
    16. 16 Đề bài tập Python có lời giải PDF thi HSG cấp huyện mới nhất
    17. 17 đề thi tin học trẻ có Đáp Án python THCS cấp huyện PDF
    18. 18 Đề thi học sinh giỏi Tin học THCS có đáp ÁN dễ học nhất năm 2025
    19. 19 thi HSG Tin 9 C ++ hoặc Python có đáp án
    20. 100 đề và đáp án thi HSG tin Python cấp huyện 2025

Thiết kế dạng hình:

Thiết kế dạng chữ :

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
TRUnG học Cơ Sở

Năm học 2022-2023 Môn: TIN HỌC

Thời gian: 150 phút (không kể thời gian giao đề) Ngày thi: 21/3/2023 ^

(Đề thi có 5 trang, gồm 5 bài)

TỔNG quan các BÀi thi

Thứ tự

Tên bài

File chương trình File dữ liệu vào File kết quả
Bài 1 Tương đồng SAME.* SAME.INP SAME.OUT
Bài 2 Tách xâu STRING.* STRING.INP STRING.OUT
Bài 3 May mắn LUCKY.* LUCKY.INP LUCKY.OUT
Bài 4 Tam giác TRIANGLE.* TRIANGLE.INP TRIANGLE.OUT
Bài 5 Chở hàng GOOD.* GOOD.INP GOOD.OUT
Dấu * được thay thế bởi PAS, CPP, PY của ngôn ngữ lập trình được sử dụng tương ứng là Free Pascal, C++, Python hoặc phần mở rộng tương ứng với NNLT khác.

 

 

Bài 1: (4 điểm) Tương đồng   Tên chương trình: SAME.*

Vườn bưởi nhà Alice có n cây. Để theo dõi sự phát triển của các cây bưởi của mình, Alice thường xuyên đo và ghi lại chiều cao của chúng. Trong tuần này, Alice có được bảng chiều cao của các cây bưởi là một dãy số nguyên a[1], a[2],…, a[n], trong đó a[i] là chiều cao của cây bưởi thứ i. Nhìn vào dãy số, Alice biết có những cây có chiều cao trùng nhau và Alice gọi mỗi tần số trùng nhau là tần số “tương đồng”.

Do số lượng cây bưởi nhiều nên Alice muốn nhờ các bạn lập trình tìm tần số tương đồng lớn nhất của các cây bưởi là bao nhiêu?

Dữ liệu vào: Đọc từ file SAME. INP gồm 2 dòng:

  • Dòng 1: gồm một số nguyên dương n (0 < n <106).
  • Dòng 2: gồm n số nguyên dương a[i] (0 < ai <106), mỗi số ứng với chiều cao của một cây bưởi, giữa các số được cách nhau bởi một khoảng trắng.

Kết quả: Ghi ra file SAME.OUT gồm duy nhất một số nguyên dương là tần số tương đồng lớn nhất.

Ví dụ:

SAME.INP same.out
7

9 8 6 8 5 6 10

2
2

3 10

1

 

 

Giải thích bộ test 1:

Có 1 chiều cao: 5;

Có 2 chiều cao: 6;

Có 2 chiều cao: 8;

Có 1 chiều cao: 9;

Có 1 chiều cao: 10

->Tần số tương đồng lớn nhất là: 2

Bài 2: (4 điểm) Tách xâu Tên chương trình: STRING.*

Hôm nay, mẹ và Cám đi dự dạ hội. Tấm cũng rất muốn được đi. Nhưng trước khi đi, mẹ Cám giao cho Tấm một công việc để làm khó Tấm như sau:

Cho một xâu s gồm các ký tự là các chữ cái in hoa hoặc in thường (trong bảng chữ cái Tiếng Anh) và các kí tự số. Mẹ kế yêu cầu Tấm hãy tách các ký tự trong xâu s thành hai phần như sau:

Phần 1: gồm các chữ cái có mặt trong s nhưng viết theo thứ tự ngược lại.

Phần 2: gồm các chữ số có mặt trong xâu s nhưng phải được sắp xếp theo thứ tự từ nhỏ đến lớn.

Nếu Tấm thực hiện xong công việc thì mới được đi dự tiệc. Nhưng Tấm có thời gian rất ít nên chưa giải được bài toán. Các bạn đội tuyển Tin học hãy giúp đỡ Tấm giải bài toán để Tấm còn được đi dự tiệc nhé!

Dữ liệu vào: Đọc từ file STRING.INP gồm 1 dòng chứa xâu s có độ dài không quá 103 ký tự. Dữ liệu vào đảm trong xâu s luôn có kí tự chữ cái và kí tự chữ số. Kết quả: Ghi ra fíle STRING.OUT gồm 2 dòng:

  • Dòng 1: gồm các chữ cái trong xâu s nhưng được viết theo thứ tự ngược lại.
  • Dòng 2: gồm các chữ số trong xâu s, nhưng phải được sắp xếp theo thứ tự từ nhỏ đến lớn.

Ví dụ:

STRING.INP STRING.OUT
m2aC0ma2T3 TamCam

0223

 

 

Bài 3: (4 điểm) May mắn Tên chương trình: LUCKY.*

Trong buổi tiệc liên hoan cuối năm của công ty cung cấp điện thoại Thế Giới Trẻ, ghế ngồi trong hội trường của khách mời được bố trí thành một ma trận hình chữ nhật gồm m hàng và n cột. Để buổi liên hoan thêm vui vẻ, ban tổ chức cho mỗi khách mời rút ngẫu nhiên một phiếu, trên phiếu có ghi một số nguyên dương trong phạm vi từ 1 đến 109.

Ban tổ chức sẽ trao cho những người may mắn mỗi người một phần quà là một chiếc điện thoại. Biết rằng người may mắn là người có số ghi trong phiếu của

mình lớn hơn trung bình cộng của số trong phiếu của những người ngồi xung quanh người đó.

Xung quanh một người được định nghĩa như sau:

Trường hợp 1: Người ngồi ở vị trí góc (trên trái, dưới trái, trên phải, dưới

phải) của hình chữ nhật thì chỉ có 2 người ngồi xung quanh.

Trường hợp 2: Người ngồi ở vị trí bìa (trừ góc) thì có 3 người xung quanh. Trường hợp 3: Người ngồi ở các vị trí còn lại có 4 người xung quanh.

 

 

Trường hợp 1                                                  Trường hợp 2                                                  Trường hợp 3

Ô gạch sọc chỉ vị trí xung quanh của vị trí được tô đen.

Bạn hãy giúp ban tổ chức xác định số lượng điện thoại cần phải chuẩn bị để trao cho những người may mắn.

Dữ liệu vào: Đọc từ file LUCKY.INP gồm:

  • Dòng 1: gồm hai số nguyên dương theo thứ tự m, n (0 < m, n <103), giữa m và n được cách nhau bởi dấu cách.
  • m dòng tiếp theo, mỗi dòng gồm n số nguyên dương có giá trị không quá 109, giữa hai số cách nhau bởi một dấu cách.

Kết quả: Ghi ra file LUCKY.OUT gồm một số nguyên là số điện thoại ban tổ chức cần chuẩn bị.

Ví dụ:

LUCKY.INP LUCKY.OUT
3 4 3
1 4 3 1
1 1 5 2
2 1 2 1

 

 

Giải thích:

Số lượng điện thoại cần chuẩn bị là 3, vì có ba người may mắn:

+ Người thứ nhất ngồi ở hàng 1, cột 2, có số phiếu là 4 (có 3 người xung quanh) + Người thứ hai ngồi ở hàng 2, cột 3, có số phiếu là 5 (có 4 người xung quanh) + Người thứ ba ngồi ở hàng 3, cột 1, có số phiếu là 2 (có 2 người xung quanh)

Bài 4: (4 điểm) Tam giác Tên chương trình: TRIANGLE.*

Alice có n que tính, mỗi que có độ dài là một số nguyên dương. Alice muốn tạo ra các tam giác bằng cách ghép ba que tính lại với nhau, độ dài mỗi cạnh là một que tính.

Em hãy giúp Alice đếm xem có bao nhiêu tam giác được tạo thành từ các que tính này và cho biết diện tích lớn nhất trong các diện tích của các tam giác ghép được là bao nhiêu?

Biết rằng:

+ Hai tam giác được gọi là khác nhau nếu có ít nhất một que tính khác nhau.

+ Ta có thể tính diện tích tam giác theo công thức sau :

s=Vp * (p — à) * (p — b) * (p — c)

Trong đó a,b,c là độ dài 3 cạnh của tam giác, và p là nửa chu vi của tam giác.

Dữ liệu vào: Đọc từ file TRIANGLE.INP gồm:

  • Dòng 1: gồm một số nguyên dương n (3 < n < 100)
  • Dòng 2: gồm n số nguyên dương a[1], a[2], …, a[n] là độ dài của n que tính (1 < a[i] < 106 1<i<n). Giữa các số được cách nhau bởi một khoảng trắng.

Kết quả: Ghi ra file TRIANGLE.OUT gồm:

  • Dòng 1: Ghi số lượng tam giác có thể ghép được.
  • Dòng 2: Ghi một số thực là diện tích lớn nhất của tam giác, kết quả làm tròn đến 2 chữ số ở phần thập phân. Trường hợp không có tam giác nào thì dòng này ghi -1.
TRIANGLE.INP TRIANGLE.OUT Giải thích
5 3 Có 3 tam giác được tạo từ 5 que tính trên:
1 4 5 2 3 6.00 Tam giác 1: Que thứ 2, 3, 4 Tam giác 2: Que thứ 2, 3, 5 Tam giác 3: Que thứ 2, 4, 5 Trong đó tam giác thứ 2 có 3 độ dài là 4 5 3 có có diện tích lớn nhất là 6.00
4 4 Có 4 tam giác được tạo từ 4 que tính trên:
2 2 2 2 1.73 Tam giác 1: Que thứ 1, 2, 3

Tam giác 2: Que thứ 1, 2, 4

Tam giác 3: Que thứ 1, 3, 4

Tam giác 4: Que thứ 2, 3, 4

Trong đó 4 tam giác đều có cùng diện

tích là: 1.73

3 0 Không ghép được tam giác nào
1 2 3 -1

 

 

Bài 5: (4 điểm) Hàng hóa Tên chương trình: GOOD.*

Cửa hàng tạp hóa XYZ cần chở n kiện hàng giao cho khách. Kiện hàng thứ i có trọng lượng là a[i] tấn. Cửa hàng có một xe tải có trọng tải là m tấn. Trong

chuyến hàng đầu tiên, cửa hàng muốn chở những kiện hàng đi giao thỏa mãn các yêu cầu sau:

  • Yêu cầu 1: Ưu tiên kiện hàng có trọng lượng lớn hơn sẽ được chở đi.
  • Yêu cầu 2: Xe còn đủ trọng tải chở được thì chọn tiếp kiện hàng khác thỏa mãn yêu cầu 1.

Em hãy lập trình giúp cửa hàng xác định trọng lượng các kiện hàng của chuyến xe đầu tiên.

Dữ liệu vào: Đọc từ file GOOD.INP gồm hai dòng:

  • Dòng 1: gồm số nguyên dương n (1 <n<103) là số kiện hàng và số nguyên dương m (0 < m < 109) là trọng lượng của xe tải. Giữa n và m được cách nhau bởi dấu cách.
  • Dòng 2: gồm n số nguyên dương a[i] (0 < a[i] <109, a[i] < m, 1<i<n) thể hiện trọng lượng của kiện hàng thứ i. Giữa các số được cách nhau bởi dấu cách.

Kết quả: Ghi ra file GOOD.OUT các số nguyên dương là trọng lượng của các kiện hàng trong chuyến xe đầu tiên theo trọng lượng giảm dần.

GOOD.INP GOOD.OUT
5 10

7 5 1 3 8

8 1
5 12

2 8 2 4 1

8 4

 

 

Giải thích bộ test 1:

Có n = 5 kiện hàng và xe có trọng tải m = 10 tấn Các kiện hàng có trọng lượng lần lượt là: 7 5 1 3 8 Vậy các kiện hàng được chở đi trong chuyến đầu tiên có trọng lượng lần lượt là 8 và 1.

Vì kiện hàng có trọng lượng là 8 lớn hơn trọng lượng các kiện hàng còn lại và 8 < m=10 nên được ưu tiên chọn. Trọng tải xe còn có thể chứa được là 10 – 8 = 2, nên chọn tiếp kiện hàng có trọng lượng là 1.

…………………………………………………… HẾT…………………………………………………….

Thí sinh không được sử dụng tài liệu. Giám thị không giải thích gì thêm.

Họ và tên thí sinh: …………………………………………………………. Số báo danh:……………………………………………………………..

 

 

Đáp án bài 1: Tương đồng – SAME.*

1.1 Đáp án bài 1:

import sys
from collections import Counter
sys.stdin = open("SAME.INP", "r")
sys.stdout = open("SAME.OUT", "w")
n = int(sys.stdin.readline().strip())  # Đọc số lượng phần tử (không cần dùng)
a = list(map(int, sys.stdin.readline().split()))  # Đọc danh sách số
tanso = Counter(a)  # Đếm tần số xuất hiện của từng số
tansolonnhat = max(tanso.values())  # Tìm tần số lớn nhất
print(tansolonnhat)  # Ghi kết quả ra file

1.2 CÁCH GIẢI 1:

1️⃣  Đọc dữ liệu từ file:

  • Vì bạn muốn dùng sys.stdin, ta mở file bằng sys.stdin = open(“SAME.INP”, “r”).
  • Đọc số n (số lượng phần tử) nhưng không cần dùng đến.
  • Đọc danh sách số nguyên từ file.

2️⃣ Đếm tần số xuất hiện của từng số:

  • Dùng collections.Counter để đếm số lần xuất hiện của mỗi phần tử.

3️⃣ Tìm tần số lớn nhất:

  • Duyệt qua các giá trị trong Counter và lấy giá trị lớn nhất bằng max(freq.values()).

4️⃣ Ghi kết quả ra file:

  • In kết quả ra sys.stdout, kết quả sẽ được lưu vào “SAME.OUT”.

⏳ Độ phức tạp

  • Đọc dữ liệu: O(n)
  • Đếm tần số: O(n)
  • Tìm max: O(n)
  • Tổng: O(n) (rất tối ưu ✅).

👉 Tóm lại, ta chỉ cần duyệt danh sách 1 lần để đếm tần số và 1 lần để tìm giá trị lớn nhất. 🚀

 

Đáp án bài 2: Tách xâu – STRING.*

2.1 Đáp án bài 2:

import sys
sys.stdin = open("STRING.INP", "r")
sys.stdout = open("STRING.OUT", "w")
s = sys.stdin.readline().strip()
chu = []
so = []
# Phân loại ký tự
for i in s:
    if i.isalpha():
        chu.append(i)
    elif i.isdigit():
        so.append(i)
# Xử lý yêu cầu bài toán
chu.reverse()  # Đảo ngược thứ tự chữ cái
so.sort()  # Sắp xếp các chữ số theo thứ tự tăng dần
# Ghi kết quả ra file
print("".join(chu))
print("".join(so))

2.2 CÁCH GIẢI:

Phân tích bài toán

Bài toán yêu cầu:

  1. Tách các chữ cái trong xâu và đảo ngược thứ tự xuất hiện của chúng.
  2. Tách các chữ số trong xâu và sắp xếp chúng theo thứ tự tăng dần.

Cách giải

  • Duyệt qua từng ký tự của xâu:
    • Nếu là chữ cái, thêm vào danh sách chu.
    • Nếu là chữ số, thêm vào danh sách so.
  • Đảo ngược danh sách letters.
  • Sắp xếp danh sách digits theo thứ tự tăng dần.
  • Ghi kết quả ra file.

Độ phức tạp

  • Duyệt chuỗi O(n)
  • Đảo ngược danh sách chữ O(n)
  • Sắp xếp danh sách số O(k log k) (với k là số lượng chữ số, k ≤ n)
  • Tổng thể: O(n log n) ~ O(n) trong thực tế.

 

Đáp án Bài 3:  May mắn – LUCKY.*

3.1 Đáp án :

 

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

def tinh_trung_binh_lan_can(ma_tran, i, j, m, n):
    lan_can = []
    huong = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Trái, phải, trên, dưới

    for dx, dy in huong:
        ni, nj = i + dx, j + dy
        if 0 <= ni < m and 0 <= nj < n:
            lan_can.append(ma_tran[ni][nj])

    return sum(lan_can) / len(lan_can) if lan_can else 0
m, n = map(int, sys.stdin.readline().split())
ma_tran = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

so_nguoi_may_man = 0

# Kiểm tra từng ô trong ma trận
for i in range(m):
    for j in range(n):
        trung_binh_lan_can = tinh_trung_binh_lan_can(ma_tran, i, j, m, n)
        if ma_tran[i][j] > trung_binh_lan_can:
            so_nguoi_may_man += 1

print(so_nguoi_may_man)

 

3.2 CÁCH GIẢI

Cách giải bài toán:

  1. Đọc dữ liệu đầu vào:
    • Đọc kích thước ma trận m x n.
    • Đọc các giá trị của ma trận từ file.
  2. Tính toán số người may mắn:
    • Với mỗi vị trí (i, j), tính trung bình cộng của các ô xung quanh (trái, phải, trên, dưới).
    • Nếu giá trị ở (i, j) lớn hơn trung bình đó, thì người ở vị trí đó là người may mắn.
  3. Xuất kết quả:
    • Ghi số lượng người may mắn ra file kết quả.

 

Đáp án bài 4:  Tam giác -TRIANGLE.*

4.1 Đáp án:

 

import math,sys
sys.stdin=open("TRIANGLE.INP",'r')
sys.stdout=open('TRIANGLE.OUT','w')
def dien_tich_heron(a, b, c):
    s = (a + b + c) / 2
    return math.sqrt(s * (s - a) * (s - b) * (s - c))

def tam_giac_lon_nhat(n, canh):
    canh.sort(reverse=True)  # Sắp xếp giảm dần
    for i in range(n - 2):
        if canh[i] < canh[i + 1] + canh[i + 2]:  # Điều kiện tam giác
            return dien_tich_heron(canh[i], canh[i + 1], canh[i + 2])
    return 0  # Không tìm được tam giác hợp lệ

n = int(input())
canh = list(map(int, input().split()))
print(f"{tam_giac_lon_nhat(n, canh):.2f}")

1. Bài toán đang làm gì?

Yêu cầu:
Cho n đoạn thẳng có độ dài cho trước.
→ Hãy chọn 3 đoạn để tạo thành tam giác có diện tích lớn nhất.
→ In ra diện tích tam giác đó (làm tròn 2 chữ số thập phân).
→ Nếu không tạo được tam giác, in ra 0.


2. Phân tích từng phần của chương trình

🔹 Hàm dien_tich_heron(a, b, c)

def dien_tich_heron(a, b, c):
s = (a + b + c) / 2
return math.sqrt(s * (s - a) * (s - b) * (s - c))
  • Áp dụng công thức Heron để tính diện tích tam giác khi biết 3 cạnh.

  • snửa chu vi tam giác.

  • Diện tích:

S=s(s−a)(s−b)(s−c)S = \sqrt{s(s-a)(s-b)(s-c)}

⏱️ Độ phức tạp: O(1)


🔹 Hàm tam_giac_lon_nhat(n, canh)

canh.sort(reverse=True)
  • Sắp xếp các cạnh giảm dần

  • Mục đích:

    • Xét các tam giác có cạnh lớn nhất trước

    • Khi chu vi lớn → diện tích thường lớn hơn


for i in range(n - 2):
if canh[i] < canh[i + 1] + canh[i + 2]:
return dien_tich_heron(canh[i], canh[i + 1], canh[i + 2])

Ý tưởng thuật toán 💡

  • Sau khi sắp xếp:

    • canh[i] là cạnh lớn nhất

  • Kiểm tra điều kiện tồn tại tam giác:

cạnh lớn nhaˆˊt<tổng hai cạnh coˋn lại\text{cạnh lớn nhất} < \text{tổng hai cạnh còn lại}

  • Vì đã sắp giảm dần:

    • Tam giác đầu tiên hợp lệ sẽ có chu vi lớn nhất

    • Diện tích cũng lớn nhất

  • Khi tìm được → tính diện tích và kết thúc luôn


return 0
  • Nếu duyệt hết mà không có bộ 3 cạnh nào hợp lệ
    → Không tạo được tam giác


3. Tóm tắt thuật toán

👉 Các bước:

  1. Đọc số cạnh n và danh sách độ dài.

  2. Sắp xếp các cạnh theo thứ tự giảm dần.

  3. Duyệt từng bộ 3 cạnh liên tiếp:

    • Kiểm tra điều kiện tam giác.

    • Nếu hợp lệ → tính diện tích bằng công thức Heron → kết thúc.

  4. Nếu không có tam giác → in 0.


4. Độ phức tạp của chương trình

⏱️ Thời gian

Công đoạn Độ phức tạp
Sắp xếp O(n log n)
Duyệt kiểm tra O(n)
Tính diện tích O(1)

➡️ Tổng:

O(nlog⁡n)\boxed{O(n \log n)}


💾 Bộ nhớ

  • Lưu danh sách n cạnh
    ➡️ O(n)


5. Vì sao thuật toán này tối ưu?

✅ Không duyệt tất cả bộ 3 cạnh (O(n³))
✅ Dựa vào tính chất sắp xếp để tìm nhanh tam giác lớn nhất
✅ Phù hợp bài thi HSG cấp huyện / tỉnh

 

 

Đáp án bài 5: Hàng hóa – GOOD.*

5.1 Đáp án bài Hàng Hóa:

import sys
sys.stdin = open("GOOD.INP", "r")
sys.stdout = open("GOOD.OUT", "w")
n, m = map(int, sys.stdin.readline().split())
trong_luong = list(map(int, sys.stdin.readline().split()))

# Sap xep danh sach kien hang theo thu tu tang dan
trong_luong.sort()
trong_luong=trong_luong[::-1]
chon = []
tong_trong_luong = 0

# Duyet qua tung kien hang theo thu tu tang dan
for w in trong_luong:
    if tong_trong_luong + w <= m:  # Neu them kien hang vao van khong vuot tai trong
        chon.append(w)
        tong_trong_luong += w
    elif tong_trong_luong>m:
        break  # Neu qua tai thi dung

# Ghi ket qua ra file theo thu tu giam dan
print(*chon)

1. Mô tả bài toán (hiểu từ chương trình)

  • n kiện hàng, mỗi kiện có trọng lượng cho trước.

  • Xe có tải trọng tối đa là m.

  • Hãy chọn các kiện hàng sao cho:

    • Tổng trọng lượng không vượt quá m

    • Ưu tiên lấy các kiện nặng trước

  • In ra danh sách các kiện hàng được chọn.


2. Phân tích từng phần chương trình

🔹 Đọc dữ liệu

n, m = map(int, sys.stdin.readline().split())
trong_luong = list(map(int, sys.stdin.readline().split()))
  • n: số kiện hàng

  • m: tải trọng tối đa

  • trong_luong: danh sách trọng lượng các kiện


🔹 Sắp xếp danh sách kiện hàng

trong_luong.sort()
trong_luong = trong_luong[::-1]
  • Ban đầu sắp xếp tăng dần

  • Sau đó đảo ngược → giảm dần

  • Mục đích:

    • Xét kiện nặng trước

    • Áp dụng chiến lược tham lam (Greedy)


🔹 Biến hỗ trợ

chon = []
tong_trong_luong = 0
  • chon: lưu các kiện được chọn

  • tong_trong_luong: tổng trọng lượng hiện tại


🔹 Thuật toán chọn kiện hàng (Greedy)

for w in trong_luong:
if tong_trong_luong + w <= m:
chon.append(w)
tong_trong_luong += w
elif tong_trong_luong > m:
break

Ý tưởng thuật toán 💡

  • Duyệt từng kiện theo thứ tự trọng lượng giảm dần

  • Với mỗi kiện:

    • Nếu thêm vào không vượt quá tải trọng → chọn

    • Nếu đã vượt tải → dừng lại

👉 Đây là thuật toán tham lam:

  • Ở mỗi bước, chọn kiện nặng nhất có thể

  • Không quay lui, không xét lại


🔹 In kết quả

print(*chon)
  • In danh sách các kiện hàng được chọn

  • Thứ tự đã là giảm dần


3. Tóm tắt thuật toán

👉 Các bước chính:

  1. Đọc dữ liệu đầu vào.

  2. Sắp xếp các kiện hàng theo trọng lượng giảm dần.

  3. Lần lượt xét từng kiện:

    • Nếu thêm vào vẫn không vượt tải → chọn.

    • Nếu vượt tải → dừng.

  4. In ra các kiện đã chọn.


4. Độ phức tạp của chương trình

⏱️ Độ phức tạp thời gian

Công đoạn Độ phức tạp
Sắp xếp danh sách O(n log n)
Duyệt chọn kiện O(n)
In kết quả O(n)

➡️ Tổng thời gian:

O(nlog⁡n)


💾 Độ phức tạp bộ nhớ

  • Danh sách trọng lượng: O(n)

  • Danh sách chọn: O(n)

➡️ Tổng bộ nhớ:

O(n)


5. Nhận xét theo chuẩn bài thi

✅ Thuật toán đơn giản – hiệu quả
✅ Phù hợp với bài toán có ràng buộc nhỏ và trung bình
✅ Dễ cài đặt, dễ hiểu, dễ chấm điểm

⚠️ Lưu ý:

  • Đây là bài toán tham lam, không đảm bảo tối ưu trong mọi trường hợp nếu đề yêu cầu tối đa tổng trọng lượng (bài toán cái túi 0/1).

  • Tuy nhiên, nếu đề yêu cầu ưu tiên kiện nặng, thuật toán là đúng.

 

Câu hỏi thường gặp về Tổng hợp 75 Đề thi HSG Tin học THCS Python

1. Bộ 75 đề thi HSG Tin học này có lời giải chi tiết (Full Code) không? Có. Toàn bộ 75 đề thi trong bài viết này đều đi kèm đáp án và mã nguồn (Source Code) được viết bằng ngôn ngữ lập trình Python. Chúng tôi cũng bổ sung các giải thích về thuật toán để các em học sinh hiểu rõ cách tư duy giải quyết vấn đề chứ không chỉ copy code.

2. Tài liệu này phù hợp cho học sinh lớp mấy? Bộ tài liệu này được biên soạn bám sát cấu trúc đề thi Học sinh giỏi cấp Huyện và cấp Tỉnh, phù hợp nhất cho học sinh khối THCS (Lớp 8, Lớp 9). Ngoài ra, học sinh lớp 6, 7 bắt đầu làm quen với Python nâng cao cũng có thể sử dụng để rèn luyện tư duy logic.

3. Tôi có thể tải file PDF đề thi và đáp án về máy tính không? Được. Ở cuối bài viết, Vi Tính Tấn Dân có cung cấp liên kết tải xuống trọn bộ tài liệu định dạng PDF để thầy cô và các em học sinh tiện in ấn và ôn tập offline.

4. Code Python trong bài viết sử dụng phiên bản nào? Các bài giải mẫu được viết tương thích tốt nhất với Python 3.x (phiên bản phổ biến nhất hiện nay trong giáo dục và thi cử). Bạn có thể chạy code trên các IDE thông dụng như Thonny, PyCharm, hoặc VS Code.

5. Ngoài Python, đề thi có đáp án bằng C++ hay Pascal không? Hiện tại, bài viết này tập trung chuyên sâu vào ngôn ngữ Python. Tuy nhiên, cấu trúc thuật toán là giống nhau. Nếu bạn cần tài liệu C++ hoặc Pascal, vui lòng tham khảo các chuyên mục khác trên website vitinhtandan.com hoặc để lại bình luận để chúng tôi hỗ trợ.

 

 

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

 

5/5 - (1 bình chọn)
Vi Tính Tấn Dân

Mình rất đam mê về máy vi tính và máy in. Và mình đã đeo đuổi ước mơ và làm việc về máy vi tính mới đây mà đã 15 năm. Mình thích chia sẻ mọi kiến thức và kinh nghiệm mà mình có được cho tất cả các bạn ! Trong khi mình viết nếu có điều gì thiếu sót mong các bạn thông cảm cho mình nhé ! Mình Cám ơn trước !

Recent Posts

6 Kinh nghiệm làm bài thi Học sinh giỏi Tin học Tỉnh 2026-2027

6 Kinh nghiệm làm bài thi Học sinh giỏi Tin học Tỉnh 2026- 2027 &…

18 giờ ago

Tài liệu ôn thi HSG Tin học Tỉnh 2026-2027: 5 Bí kíp chinh phục Python

Cách Tải Tài liệu 5 Bí kíp chinh phục Python Tài liệu ôn thi HSG…

2 ngày ago

100 bài lập trình python có lời giải cơ bản đến nâng cao pdf

100 Bài Lập Trình Python Có Lời Giải Cơ Bản Đến Nâng Cao PDF –…

4 tuần ago

100 Đề Tổng Hợp Thi Tin Học Ứng Dụng Cơ Bản 2026 – 2027

100 Đề Tổng Hợp Thi Tin Học Ứng Dụng Cơ Bản – Đại học Khoa…

1 tháng ago

7 MẸO SỬA PC TẠI NHÀ NHANH GỌN CHO NGƯỜI KHÔNG RÀNH CÔNG NGHỆ

✅ Giới thiệu Bạn đang dùng PC thì đột nhiên đơ, chậm, xoay vòng mãi…

1 tháng ago

This website uses cookies.