1 Đề Thi Học Sinh Giỏi Tin học THCS cấp Tỉnh có đáp án mới nhất

1 Đề Thi Học Sinh Giỏi Tin học THCS cấp Tỉnh Tiền Giang có đáp án mới nhất

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)

Các đề ôn thi để chuẩn bị thi Cấp Huyện 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.

TỔNG quan các BÀi thi

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 <10⁶).
• Dòng 2: gồm n số nguyên dương a[i] (0 < ai <10⁶), 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ụ:

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á 10³ 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ụ:

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 10⁹.

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

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 <10³), 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á 10⁹, 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ụ:

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] < 10⁶ 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.

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<10³) là số kiện hàng và số nguyên dương m (0 < m < 10⁹) 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] <10⁹, 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.

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:……………………………………………………………………..

Download File

Đáp Án 5 bài Đề Thi Học Sinh Giỏi Tin học THCS cấp Tỉnh Tiền Giang

Đáp án bài 1: Tương đồng (SAME)

Ý tưởng tối ưu

• Sử dụng dictionary (hash map) để đếm số lần xuất hiện của mỗi số (O(n)).
• Duyệt qua dictionary để tìm giá trị xuất hiện nhiều nhất (O(n)).

Code Python

def tim_so_pho_bien_nhat(n, danh_sach):
    tan_suat = {}  # Tạo một dictionary để đếm số lần xuất hiện
    for so in danh_sach:
        tan_suat[so] = tan_suat.get(so, 0) + 1  # Tăng đếm số lần xuất hiện
    
    return max(tan_suat, key=tan_suat.get)  # Trả về số xuất hiện nhiều nhất

# Đọc input
n = int(input())  
danh_sach = list(map(int, input().split()))

# Xuất kết quả
print(tim_so_pho_bien_nhat(n, danh_sach))

Tối ưu: Sử dụng dictionary giúp truy xuất nhanh (O(1) mỗi lần cập nhật).
⏳ Độ phức tạp: O(n).

Đáp án bài 2: Tách xâu (STRING)

Ý tưởng tối ưu

• Duyệt chuỗi để tách chữ và số (O(n)).
• Đảo ngược danh sách chữ (O(n)).
• Sắp xếp danh sách số (O(n log n)).
• Ghép lại thành chuỗi (O(n)).

Code Python

def tach_xau(s):
    chu = []
    so = []
    
    for c in s:
        if c.isdigit():
            so.append(int(c))  # Thêm vào danh sách số
        else:
            chu.append(c)  # Thêm vào danh sách chữ
    
    chu.reverse()  # Đảo ngược chữ
    so.sort()  # Sắp xếp số
    
    return ''.join(chu) + ''.join(map(str, so))

# Đọc input
s = input()
print(tach_xau(s))

Tối ưu: Tách chữ và số trong 1 lần duyệt giúp tiết kiệm thời gian.
⏳ Độ phức tạp: O(n log n) do sắp xếp số.

Đáp án bài 3: May mắn (LUCKY)

Ý tưởng tối ưu

• Duyệt từng phần tử của ma trận (O(m × n)).
• Kiểm tra 8 ô xung quanh bằng danh sách dx, dy (O(1) mỗi lần kiểm tra).

Code Python

def dem_so_may_man(m, n, ma_tran):
    dx = [-1, -1, -1, 0, 0, 1, 1, 1]
    dy = [-1, 0, 1, -1, 1, -1, 0, 1]
    
    dem = 0
    for i in range(m):
        for j in range(n):
            tong = 0
            dem_lan_can = 0
            
            for k in range(8):  # Kiểm tra 8 ô xung quanh
                x, y = i + dx[k], j + dy[k]
                if 0 <= x < m and 0 <= y < n:
                    tong += ma_tran[x][y]
                    dem_lan_can += 1
            
            if dem_lan_can > 0 and ma_tran[i][j] > tong / dem_lan_can:
                dem += 1
    
    return dem

# Đọc input
m, n = map(int, input().split())
ma_tran = [list(map(int, input().split())) for _ in range(m)]

# Xuất kết quả
print(dem_so_may_man(m, n, ma_tran))

Tối ưu: Sử dụng dx, dy để kiểm tra 8 hướng nhanh chóng.
⏳ Độ phức tạp: O(m × n).

Đáp án bài 4: Tam giác lớn nhất (TRIANGLE)

Ý tưởng tối ưu

• Sắp xếp trước (O(n log n)).
• Dùng hai con trỏ để tìm bộ ba thỏa mãn (O(n²)).

Code Python

import math

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ệ

# Đọc input
n = int(input())
canh = list(map(int, input().split()))

# Xuất kết quả
print(f"{tam_giac_lon_nhat(n, canh):.2f}")

 
⏳ Độ phức tạp: O(n²).

Đáp án bài 5: Chở hàng (GOOD)

Ý tưởng tối ưu

• Sắp xếp kiện hàng (O(n log n)).
• Duyệt danh sách để chọn kiện hàng (O(n)).

Code Python

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

# Doc so kien hang n va tai trong m
n, m = map(int, sys.stdin.readline().split())

# Doc danh sach trong luong cac kien hang
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 = []  # Danh sach cac kien hang duoc chon
tong_trong_luong = 0  # Tong trong luong cac kien hang duoc chon

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

Tối ưu: Dùng sắp xếp + duyệt tuyến tính, tránh thử mọi khả năng (O(2ⁿ)).
⏳ Độ phức tạp: O(n log n).

Tóm tắt tối ưu

Nhận xét:

• Các bài O(n log n) chạy tốt cho n ≤ 10⁶.
• Bài tam giác O(n²) cần tối ưu hơn nếu n > 10⁵.
• Tránh thuật toán O(n³) nếu có thể.

Tất cả bài đều chạy tốt với dữ liệu lớn, trừ bài tam giác có thể cần cải tiến hơn nữa.

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

Khóa học Python online từ cơ bản đến nâng cao