HSG THCS Điện Biên 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠOĐIỆN BIÊN

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP TỈNH Năm học: 2025 - 2026
Môn thi: Tin học

Tổng quan đề thi

TT	Tên bài	Tên file chương trình	Dữ liệu vào	Kết quả ra
Câu 1	Giai thừa	`DEM.*`	Nhập từ bàn phím	Ghi ra màn hình
Câu 2	Số đẹp	`SDEP.*`	Nhập từ bàn phím	Ghi ra màn hình
Câu 3	Xóa số	`XOASO.*`	Nhập từ bàn phím	Ghi ra màn hình
Câu 4	Đếm cặp	`CAP.*`	Nhập từ bàn phím	Ghi ra màn hình

Lưu ý: Thí sinh thay dấu * trong chương trình thành PY hoặc CPP của ngôn ngữ lập trình sử dụng tương ứng là Python hoặc C++.

Hãy lập trình giải các bài toán sau:

Câu 1 (5,0 điểm). Giai thừa

Người ta định nghĩa N giai thừa là tích 1 × 2 × … × N và kí hiệu là N! Nhập từ bàn phím số nguyên dương N (1 ≤ N ≤ 10¹⁸). Hiện trên màn hình chữ số bằng 0 cuối cùng (bên phải) của N! Ví dụ, nhập N = 5 thì kết quả trên màn hình là 1 (vì 5! = 1 × 2 × 3 × 4 × 5 = 120, chữ số 0 cuối cùng bên phải của 5! là 1).

Yêu cầu: Hãy đếm số lượng chữ số 0 ở cuối của N! (giai thừa của N).

Dữ liệu vào: Vào từ thiết bị vào chuẩn (bàn phím) một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 10¹⁸).

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) một dòng duy nhất là kết quả bài toán.

Ví dụ:

Dữ liệu vào	Kết quả in ra	Giải thích
`5`	`1`	5! = 120 → kết quả 1

Ràng buộc:

Có 80% số test ứng với 80% số điểm của câu: 1 ≤ N ≤ 10¹²;
Có 20% số test ứng với 20% số điểm của câu: 10¹² < N ≤ 10¹⁸.

Câu 2 (6,0 điểm). Số đẹp

Một số nguyên dương được gọi là số đẹp nếu nó lớn hơn 10, mỗi chữ số của nó là số lẻ hoặc là số chính phương. Có nghĩa là mỗi chữ số của nó đều thuộc tập: {0, 1, 3, 4, 5, 7, 9} và tổng tất cả các chữ số của số đó chia hết cho 3.

Yêu cầu: Cho một số nguyên dương N (1 ≤ N ≤ 10⁶). Hãy đếm có bao nhiêu số đẹp không vượt quá N. Nếu không có ghi -1.

Dữ liệu vào: Vào từ thiết bị vào chuẩn (bàn phím) có cấu trúc như sau: một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 10⁶).

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) một số nguyên duy nhất là số lượng các số đẹp nhỏ hơn hoặc bằng N.

Ví dụ:

Dữ liệu vào	Kết quả in ra
`100`	`12`

Ràng buộc:

Có 40% số test ứng với 40% số điểm của câu: 1 ≤ N ≤ 10⁴;
Có 30% số test ứng với 30% số điểm của câu: 10⁴ ≤ N ≤ 10⁵;
Có 30% số test ứng với 30% số điểm của câu: 10⁵ ≤ N ≤ 10⁶.

Câu 3 (6,0 điểm). Xoá số

Một buổi chiều đẹp trời, Tèo và Tý đang chơi với một dãy số gồm N phần tử, mỗi phần tử là một con số đầy bí ẩn. Tèo đố Tý: Viết chương trình chỉ giữ lại những số chia hết cho một số k mà Tý chọn, để dãy số trở nên “đẹp đẽ” và dễ nhìn hơn.

Tý đồng ý, nhưng cậu cũng muốn biết số nguyên dương nhỏ nhất mà chưa xuất hiện trong dãy ban đầu là gì, để biết con số nào còn thiếu trong trò chơi.

Yêu cầu: Hãy viết chương trình giúp bạn Tý:

a. Đếm số lượng và liệt kê các phần tử còn lại.
b. Tìm số nguyên dương nhỏ nhất không xuất hiện trong dãy.

Dữ liệu vào: Vào từ thiết bị vào chuẩn (bàn phím) có cấu trúc:

Dòng 1: Hai số nguyên dương N và k (1 ≤ N ≤ 10⁶, 1 ≤ k ≤ 10⁹).
Dòng 2: N số nguyên a₁, a₂, …, a_N (1 ≤ a_i ≤ 10⁹).

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) cấu trúc như sau:

Dòng 1: Số lượng phần tử còn lại sau khi loại bỏ các số không chia hết cho k.
Dòng 2: In ra các phần tử còn lại theo thứ tự tăng dần, mỗi phần tử cách nhau bởi dấu cách.
Dòng 3: Số nguyên dương nhỏ nhất chưa xuất hiện trong dãy ban đầu.

Ví dụ:

Dữ liệu vào	Kết quả in ra
`10 5` `1 2 4 5 7 15 30 55 8 25`	`5` `5 15 25 30 55` `3`

Ràng buộc:

Có 40% số test ứng với 40% số điểm của câu: 1 ≤ N ≤ 10⁴;
Có 30% số test ứng với 30% số điểm của câu: 10⁴ < N ≤ 10⁵;
Có 30% số test ứng với 30% số điểm của câu: 10⁵ < N ≤ 10⁶.

Lưu ý: Trong trường hợp học sinh làm được yêu cầu a thì đạt 70% số điểm của câu.

Câu 4 (3,0 điểm). Đếm cặp

Nam rất thích dãy những con số, đặc biệt dãy số nguyên dương. Cậu tò mò muốn biết sau khi dãy đã sắp xếp tăng dần thì có bao nhiêu cặp chỉ số (i, j) với 1 ≤ i < j ≤ N, sao cho a[j] − a[i] ≤ K. Hãy giúp Nam tính số lượng các cặp (i, j) thỏa mãn điều kiện trên.

Dữ liệu vào: Vào từ thiết bị vào chuẩn (bàn phím) có cấu trúc:

Dòng đầu tiên chứa số nguyên T - số bộ dữ liệu kiểm tra (1 ≤ T ≤ 60).
Mỗi bộ dữ liệu gồm:
1. Dòng đầu chứa hai số nguyên N và K (1 ≤ N ≤ 10⁵; 0 ≤ K ≤ 10⁹).
2. Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, a_N (1 ≤ a_i ≤ 10⁹).

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) với mỗi bộ dữ liệu, in ra số lượng cặp (i, j) thỏa mãn điều kiện của bài toán.

Ví dụ:

Dữ liệu vào	Kết quả in ra	Giải thích
`2` `5 2` `1 5 3 4 2` `4 1` `1 2 2 3`	`7` `5`	Bộ dữ liệu 1: Sau sắp xếp tăng dần: (1, 2, 3, 4, 5); có các cặp chỉ số (1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5) thỏa mãn → tổng = 7. Bộ dữ liệu 2: Các cặp chỉ số (1,2), (1,3), (2,3), (2,4), (3,4) thỏa mãn → tổng = 5.

Ràng buộc:

Có 50% số test ứng với 50% số điểm của câu: 1 ≤ T ≤ 40; 1 ≤ N ≤ 10³;
Có 30% test khác ứng với 30% số điểm của câu: 1 ≤ T ≤ 10; 10³ < N ≤ 10⁴;
Có 20% test còn lại ứng với 20% số điểm của câu: 1 ≤ T ≤ 10; 10⁴ < N ≤ 10⁵.

--- HẾT ---

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English