2 Đề thi học sinh giỏi Tin học THCS cấp tỉnh Tiền Giang có đáp án

SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH TIỀN GIANG

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH

TrUnG học Cơ Sở

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

Thời gian làm bài: 150 phút, không kể thời gian phát đề
Ngày thi: 27/3/2024

ĐỀ THI CHÍNH THỨC

(Đề thi có 04 trang, gồm 05 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é!

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ả
1	Tiền điện	ELCOST.*	ELCOST.INP	ELCOST.OUT
2	Độ mạnh của xâu	STRONG.*	STRONG.INP	STRONG.OUT
3	Tổng dòng cột	SUM.*	SUM.INP	SUM.OUT
4	Xâu lặp	SUBSTR.*	SUBSTR.INP	SUBSTR.OUT
5	Phần thưởng	GIFT.*	GIFT.INP	GIFT.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.

Học sinh chỉ được chọn một trong các môi trường quy định ở trên lập trình để làm toàn bộ bài thi.

Bài 1: Tiền điện (4,0 điểm) Tên chương trình: ELCOST.*

Giá bán lẻ điện sinh hoạt được tính theo 3 bậc gồm:

Bậc 1: 100 Kwh đầu tiên, có giá là 2500 đồng/Kwh
Bậc 2: Từ Kwh 101 đến 200, có giá là 3000 đồng/Kwh
Bậc 3: Từ Kwh 201 trở lên, có giá là 3500 đồng/Kwh

Yêu cầu: Tính tổng tiền điện phải trả của một khu phố gồm n hộ gia đình.

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

Dòng 1: Chứa số nguyên dương n (1 < n < 10⁴) là số lượng hộ gia đình.
Dòng 2: Chứa n số nguyên dương ai (1 < i < n, 1 < ai < 10⁴), với mỗi ai là số Kwh sử dụng của hộ gia đình thứ i. Giữa hai số liên tiếp được cách nhau bởi một dấu cách.

Kết quả: Ghi ra file văn bản ELCOST.OUT một số nguyên dương là tổng tiền điện của n hộ gia đình.

Ví dụ:

ELCOST.INP	ELCOST.OUT
3 15 165 205	1050000

Giải thích:

Có 3 hộ gia đình sử dụng số Kwh lần lượt là: 15, 165 và 205

Số tiền hộ thứ nhất: 15*2500 = 37500

Số tiền hộ thứ hai: 100*2500 + 65*3000 = 445000

Số tiền hộ thứ ba: 100*2500 + 100*3000 + 5*3500 = 567500

Nên tổng số tiền là: 37500 + 445000 + 567500 = 1050000

Bài 2: Độ mạnh của xâu (4,0 điểm) Tên chương trình: STRONG.*

Cho xâu s chỉ gồm các kí tự in thường trong bảng chữ cái Tiếng Anh và kí tự số từ ‘0’ đến ‘9’.

Yêu cầu: Tìm độ mạnh của xâu. Biết rằng độ mạnh của xâu là tích của số kí tự phân biệt xuất hiện trong xâu với số lần xuất hiện nhiều nhất của một kí tự trong xâu.

Dữ liệu vào: Đọc từ file văn bản STRONG.INP gồm một dòng chứa xâu s có chiều dài không quá 10³ kí tự. Trong xâu không chứa khoảng trắng và kí tự đặc biệt.

Kết quả: ghi ra file văn bản STRONG.OUT một số nguyên dương là độ mạnh của xâu.

Ví dụ:

STRONG.INP	STRONG.OUT
xy11z2yyzxy0y	30
ggggg__________________	5

Giải thích:

Ở test 1: Xâu s = ‘xy11z2yyzxy0y’. Số kí tự phân biệt trong xâu s là 6 (gồm ‘x’, ‘y’, ‘1’, ‘z’, ‘2’, ‘0’) và số lần xuất hiện nhiều nhất của một kí tự là 5 (kí tự ‘y’). Nên độ mạnh của xâu là 6 * 5 = 30.

Ở test 2: Xâu s = ‘ggggg’. Số kí tự phân biệt trong xâu s là 1 (kí tự ‘g’) và số lần xuất hiện nhiều nhất là 5. Nên độ mạnh của xâu là 1 * 5 = 5.

Bài 3: Tổng dòng cột (4,0 điểm) Tên chương trình: SUM.*

Cho ma trận a gồm m dòng và n cột. Ma trận b được tạo bằng cách: bij = (tổng dòng i trên ma trận a + tổng cột j trên ma trận a) – aij Yêu cầu: Tìm giá trị nhỏ nhất trong ma trận b.

Dữ liệu vào: Đọc từ file văn bản SUM.INP gồm nhiều dòng:

Dòng 1: Chứa hai số nguyên dương theo thứ tự là m, n (1 < m, n < 10²). Giữa hai số cách nhau bởi một dấu cách.
m dòng tiếp theo, mỗi dòng chứa n số nguyên dương aij (0 < a_ij < 10⁹). Giữa hai số liên tiếp được cách nhau bởi một dấu cách.

Kết quả: Ghi ra file văn bản SUM.OUT một số nguyên dương là giá trị nhỏ nhất tìm được trong ma trận b.

Ví dụ:

SUM.INP	SUM.OUT
2 3	10
3 2 4
2 1 5

Giải thích: Ma trận b là 11 10 14 11 10 12

Nên giá trị nhỏ nhất trong ma trận b là 10.

Bài 4: Xâu lặp (4,0 điểm) Tên chương trình: SUBSTR.*

Xâu lặp là một xâu có đoạn đầu ngắn nhất của nó được lặp lại nhiều lần. Ví dụ ‘xyxyxyxy’ là một xâu lặp vì nó có đoạn đầu ngắn nhất là ‘xy’ được lặp lại nhiều lần. ‘xyxy’ cũng được lặp lại nhưng không được tính là đoạn đầu vì nó không ngắn nhất.

Yêu cầu: Cho n xâu. Hãy ghép đoạn đầu của mỗi xâu lặp theo thứ tự xuất hiện của xâu (nếu xâu đó là xâu lặp).

Dữ liệu vào: Đọc từ file văn bản SUBSTR.INP gồm nhiều dòng:

Dòng 1: Chứa số nguyên dương n (1 < n < 10³) là số lượng xâu.
n dòng tiếp theo, mỗi dòng chứa một xâu có độ dài không quá 10³ kí tự.

Lưu ý: Trong xâu chỉ chứa kí tự thường từ ‘a’ đến ‘z’ trong bảng chữ cái Tiếng Anh (không chứa khoảng trắng, kí tự số và các kí tự đặc biệt). Dữ liệu vào đảm bảo luôn có xâu lặp.

Kết quả: Ghi ra file văn bản SUBSTR.OUT là xâu ghép thu được.

Ví dụ:

SUBSTR.INP	SUBSTR.OUT
4	xyabach
xyxyxyxy
abcab
abacabac
hhh

Giải thích:

Trong 4 xâu, có 3 xâu lặp theo thứ tự là: ‘xyxyxyxy’, ‘abacabac’, ‘hhh’. Ba đoạn đầu tương ứng là ‘xy’, ‘abac’, ‘h’. Nên xâu ghép là: ‘xyabach’.

Bài 5: Phần thưởng (4,0 điểm) Tên chương trình: GIFT.*

An được mẹ cho một số phần thưởng. Có nhiều phần thưởng được xếp thành một hàng, mỗi phần thưởng có giá trị trong khoảng từ 1 đến 10⁹. An muốn chọn những phần thưởng có giá trị tăng dần liên tiếp nhiều nhất.

Yêu cầu: Cho biết số lượng phần thưởng mà An chọn được như mong muốn.

Dữ liệu vào: Đọc từ file văn bản GIFT.INP gồm một dòng chứa các số nguyên dương là giá trị của các phần thưởng. Giữa hai số liên tiếp nhau cách nhau bởi một dấu cách.

Kết quả: Ghi ra file văn bản GIFT.OUT một số nguyên dương là số lượng phần thưởng An chọn được.

Ví dụ:

GIFT.INP	GIFT.OUT
2 4 3 5 7 8 6	4
1 5 4 3 5 6 6 5 8 6	3

Giải thích:

Ở test 1: Độ dài phần thưởng liên tiếp tăng dần nhiều nhất là 4 (2 4 3 5 7 8 6)

Ở test 2: Độ dài phần thưởng liên tiếp tăng dần nhiều nhất là 3 (1 5 4 3 5 6 6 58 6) ……. -…………… ……………….. HET……… –

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:

PDF Loading...

Đáp án bài 1: Tiền điện (ELCOST)

Ý tưởng tối ưu

Tính tiền theo từng mức giá:
- 100 Kwh đầu tiên: 2500 đ/Kwh
- 101 → 200 Kwh: 3000 đ/Kwh
- 201 Kwh trở lên: 3500 đ/Kwh
Duyệt qua từng hộ gia đình, tính tổng tiền.

Code Python

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

Đáp án bài 2: Độ mạnh của xâu (STRONG)

Ý tưởng tối ưu

Sử dụng dictionary (hash map) để đếm số lần xuất hiện của từng ký tự.
Tìm số ký tự phân biệt (O(1) mỗi ký tự).
Tìm số lần xuất hiện nhiều nhất (O(1) mỗi lần cập nhật).

Code Python

import sys
from collections import Counter

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

s = input().strip()
tan_suat = Counter(s)

so_ky_tu_phan_biet = len(tan_suat)
tan_suat_max = max(tan_suat.values())

print(so_ky_tu_phan_biet * tan_suat_max)

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

Đáp án bài 3: Tổng dòng cột (SUM)

Ý tưởng tối ưu

Tiền xử lý tổng hàng và tổng cột để tính giá trị của ma trận B trong O(1).
Duyệt nhanh để tìm giá trị nhỏ nhất.

Code Python

import sys

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

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

tong_dong = [sum(hang) for hang in ma_tran]
tong_cot = [sum(ma_tran[i][j] for i in range(m)) for j in range(n)]

gia_tri_nho_nhat = float('inf')
for i in range(m):
    for j in range(n):
        b_ij = tong_dong[i] + tong_cot[j] - ma_tran[i][j]
        gia_tri_nho_nhat = min(gia_tri_nho_nhat, b_ij)

print(gia_tri_nho_nhat)

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

Đáp án bài 4: Xâu lặp (SUBSTR)

Ý tưởng tối ưu

Duyệt từ 1 → len(s)//2 để tìm đoạn lặp ngắn nhất.
Kiểm tra nhanh bằng cách ghép đoạn lặp nhiều lần.

Code Python

import sys

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

def tim_doan_dau(xau):
    n = len(xau)
    for do_dai in range(1, n + 1):
        if n % do_dai == 0 and xau == xau[:do_dai] * (n // do_dai):
            return xau[:do_dai]
    return xau

n = int(input().strip())
ket_qua = []
for _ in range(n):
    xau = input().strip()
    ket_qua.append(tim_doan_dau(xau))

print("".join(ket_qua))

⏳ Độ phức tạp: O(n²) trong trường hợp xấu nhất, nhưng thường nhanh hơn.

Đáp án bài 5: Phần thưởng (GIFT)

Ý tưởng tối ưu

Duyệt 1 lần qua danh sách để tìm dãy tăng dần dài nhất (O(n)).

Code Python

import sys

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

phan_thuong = list(map(int, input().split()))

max_do_dai = 1
do_dai_hien_tai = 1

for i in range(1, len(phan_thuong)):
    if phan_thuong[i] > phan_thuong[i - 1]:
        do_dai_hien_tai += 1
    else:
        max_do_dai = max(max_do_dai, do_dai_hien_tai)
        do_dai_hien_tai = 1  

print(max(max_do_dai, do_dai_hien_tai))

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

Tóm tắt độ phức tạp

Bài toán	Tối ưu chính	Độ phức tạp
ELCOST	Duyệt danh sách tính tiền nhanh	O(n)
STRONG	Hash map để đếm tần suất	O(n)
SUM	Tiền xử lý tổng hàng/cột	O(m × n)
SUBSTR	Kiểm tra xâu lặp nhanh	O(n²) (trường hợp xấu nhất)
GIFT	Duyệt 1 lần để tìm dãy tăng dài nhất	O(n)

Tất cả các bài toán đều chạy tối ưu và có thể xử lý nhanh dữ liệu lớn!

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

Vui lòng Chấm điểm 5 sao trang cho bài viết hay !

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

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 !