Đề khảo sát và chọn đội tuyển học sinh giỏi THPT - Lần 1 - Năm học 2023-2024 - Trường THPT Lê Lợi (Có đáp án)

 SỞ GD & ĐT THANH HÓA ĐỀ THI KSCL VÀ CHỌN ĐỘI TUYỂN HSG LẦN I 
 TRƯỜNG THPT LÊ LỢI NĂM HỌC 2023 – 2024
 Môn: TIN HỌC 
 Đề chính thức Thời gian: 150 phút (Không kể thời gian giao đề)
 Gồm 4 trang 
 TỔNG QUAN BÀI THI
 File chương Thời 
 TT Tên bài File Input File Output
 trình gian
 1 SỐ TÍ HON TIHON.* TIHON.INP TIHON.OUT 1 giây
 2 THỪA SỐ NT TSNT.* TSNT.INP TSNT.OUT 1 giây
 3 ĐẾM DÃY CON DDC. * DDC.INP DDC.OUT 1giây
 4 BIẾN ĐỔI XÂU KÍ TỰ STRING.* STRING.INP STRING.OUT 1giây
 5 XẾP BI VÀO HỘP Xepbi.* XepBi.Inp XepBi.Out 1giây
Dấu (*) trong tên file chương trình biểu thị đuôi file tùy vào ngôn ngữ lập trình sử dụng
 .
Câu 1. SỐ TÍ HON (6.0 điểm):
 Bình là học sinh rất thích khám phá và tìm hiểu những điều thú vị về các con số. Với mỗi số 
tự nhiên, Bình gọi các “ước thực sự” của nó là những ước số tự nhiên nhỏ hơn số đó. Chẳng 
hạn 1, 2, 3 là các “ước thực sự” của 6. Bình cũng gọi một số là “số tí hon” nếu nó nhỏ hơn tổng 
tất cả các ước thực sự của nó. Chẳng hạn ta có 20 là một số tí hon, vì 20 nhỏ hơn tổng các ước 
thực sự của nó: 1 + 2 + 4 + 5 + 10 = 22.
Bình có một dãy các số tự nhiên và muốn kiểm tra xem trong dãy có bao nhiêu số tí hon. Hãy 
giúp Bình kiểm tra xem có bao nhiêu số tí hon trong dãy của bạn ấy nhé!
Yêu cầu: Cho số nguyên n (1 < n ≤ 10 4), và dãy n số nguyên. Hãy đếm các số tí hon có trong 
dãy.
Dữ liệu vào: Đọc từ tệp văn bản TIHON.inp với cấu trúc như sau:
 - Dòng đầu tiên ghi số tự nhiên n là số lượng các số có trong dãy của Bình.
 8
 - Dòng tiếp theo ghi n số tự nhiên ai là các số trong dãy 1 ≤ ai ≤ 10
Kết quả: Ghi ra tệp văn bản TIHON.out gồm một dòng duy nhất chứa một số nguyên là số 
lượng các số tí hon trong dãy của Bình.
Ví dụ:
 TIHON.INP TIHON.OUT
 4 3
 20 68 12 18
Giới hạn:
 - Có 80% test tương ứng 80% số điểm thoả mãn n ≤ 103
 - Có 20% test tương ứng 20% số điểm thoả mãn 103 < n ≤ 104
 Trang 1/ 3 Câu 4: BIẾN ĐỔI XÂU KÍ TỰ(3 điểm):
Cho hai xâu X và Y chỉ gồm các ký tự in thường. Bạn được phép thực hiện 1 trong ba thao tác 
sau trên xâu X
 • Xoá một ký tự của xâu X. 
 • Chèn kí tự bất kỳ vào xâu X
 • Thay thế một kí tự bất kỳ trong xâu X 
Yêu cầu: Tìm số thao tác ít nhất để biến xâu X thành xâu Y
Dữ liệu vào cho trong file STRING.INP gồm hai dòng 
 • Dòng thứ nhất là xâu X
 • Dòng thứ hai là xâu Y
 Gồm các kí tự in thường có độ dài <=10^3
Kết quả ghi ra file STRING.OUT:
 • ghi số K là số thao tác ít nhất biến đổi xâu X thành xâu Y
Ví dụ:
 STRING.INP STRING.OUT
 ertrtyui 6
 tyuhj
Câu 5. XẾP BI VÀO HỘP (2 điểm):
 Vinh có N viên bi được xếp thành một hàng ngang, các viên bi được đánh số thứ tự từ 1 đến 
N (theo thứ tự từ trái sang phải). Mỗi viên trong N viên bi có màu trắng hoặc màu đen, viên bi 
thứ i,(i = 1,2,,N) có khối lượng là Ai. Vinh sẽ lần lượt chọn các viên bi có thứ tự 
1, 2, 3, ..., N để xếp chúng vào các hộp. Các viên bi được xếp trong một hộp phải thỏa mãn:
 • Tổng khối lượng các viên bi không quá M.
 • Các viên bi đều phải cùng màu.
Yêu cầu: Cho biết M, hãy tính xem Vinh cần ít nhất bao nhiêu hộp để xếp hết N viên bi mà 
Vinh đang có. 
Dữ liệu cho trong file văn bản XepBi.Inp gồm:
 • Dòng thứ nhất ghi 2 số nguyên dương N và M.
 • Dòng thứ hai ghi N số nguyên A1,A2,,AN(1 ≤ Ai ≤ M).
 • Dòng thứ ba ghi N số nguyên C1,C2,,CN mô tả màu của N viên bi, nếu Ci = 0 thì viên bi 
 thứ i có màu trắng, nếu Ci = 1 thì viên bi thứ i có màu đen.
Kết quả ghi ra file văn bản XepBi.Out gồm một số nguyên là số hộp ít nhất để Vinh có thể 
xếp hết N viên bi.
Ví dụ:
 XepBi.Inp XepBi.Out Giải thích
 Trang 3/ 3