SỞ GIÁO DỤC VÀ ĐÀO TẠO
BÌNH ĐỊNH
ĐỀ CHÍNH THỨC
(Đề gồm có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9
KHÓA NGÀY: 18 - 3 – 2025
Môn thi:
TIN HỌC
Thời gian: 150 phút (không kể thời gian phát đề)
Ngày thi: 18/3/2025
TỔNG QUAN ĐỀ THI

Bài
1
2
3
4

Tên tệp chương
trình
Số mật mã (5,0 điểm)
SOMM.*
Quản lý bến xe (5,0 điểm) QLBX.*
Số đặc biệt (5,0 điểm)
SODB.*
Chọn số (5,0 điểm)
CHONSO.*
Tên bài, điểm

Tên tệp
dữ liệu vào
SOMM.INP
QLBX.INP
SODB.INP
CHONSO.INP

Tên tệp
dữ liệu ra
SOMM.OUT
QLBX.OUT
SODB.OUT
CHONSO.OUT

Chú ý:
- Phần mở rộng tên tệp chương trình theo ngôn ngữ lập trình của thí sinh (.pas; .cpp; .py).
- Khi chấm thi có xét đến thời gian xử lí bài toán của chương trình nên thí sinh không sử dụng
các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm.
- Tệp input và output ở trong thư mục hiện hành, thí sinh không khai báo đường dẫn đến
tệp input và output.
- Thời gian chạy mỗi test của chương trình không quá 01 giây.
- Bộ nhớ cần dùng cho mỗi test của chương trình không quá 1024MB.
Bài 1. SỐ MẬT MÃ (5,0 điểm)
Vào một đợt hội trại,các bạn học sinh tham gia một trò chơi giải mật mã. Các mật mã
của trò chơi được tạo ra theo quy tắc như sau: Dãy mật mã chỉ gồm hai loại ký tự 'a' hoặc 'b',
trong dãy không có từ hai ký tự 'a' trở lên đứng cạnh nhau. Ví dụ:
- Các dãy mật mã viết đúng quy tắc: abbbbbabb, bbbababa, ababba, a, b, bb, …
- Các dãy mật mã viết sai quy tắc: aa, aaa, abbbaabbb, aabbbabbb, abbbabbbaa, …
Yêu cầu: Hãy cho biết số lượng các dãy mật mã đúng có độ dài N?
Dữ liệu vào: Đọc từ tệp văn bản SOMM.INP gồm một số nguyên duy nhất N (1 ≤ N ≤ 50).
Kết quả: Ghi ra tệp văn bản SOMM.OUT gồm một số nguyên duy nhất là số lượng
dãy mật mã đúng có độ dài N.
Ví dụ:
SOMM.INP
4
2

SOMM.OUT
8
3

Giải thích:
- 8 dãy mật mã đúng có độ dài 4 là: bbbb, bbba, bbab, babb, abbb, baba, abba, abab.
- 3 dãy mật mã đúng có độ dài 2 là: bb, ba, ab.
Ràng buộc:
• Subtask 1: 60% số điểm ứng với 1 ≤ n ≤ 20.
• Subtask 2: 40% số điểm ứng với 20 < n ≤ 50.
Trang 1

Bài 2. QUẢN LÝ BẾN XE (5,0 điểm)
Thành phố QN có một hệ thống xe buýt chạy theo lịch trình cố định. Mỗi tuyến xe
buýt có các đặc điểm:
- Tuyến A: Cứ sau mỗi A giây sẽ có một chuyến xe buýt khởi hành.
- Tuyến B: Cứ sau mỗi B giây sẽ có một chuyến xe buýt khởi hành.
- Tuyến C: Cứ sau mỗi C giây sẽ có một chuyến xe buýt khởi hành.
Các tuyến xe buýt hoạt động liên tục. Người quản lý bến xe muốn biết rằng trong
khoảng thời gian từ 1 đến T giây có thời điểm nào mà xe buýt của cả ba tuyến A, B, C cùng
khởi hành hay không?
Yêu cầu: Hãy tìm thời điểm sớm nhất trong khoảng thời gian từ 1 đến T giây mà xe
buýt ở cả ba tuyến A, B, C cùng khởi hành hay không?
Dữ liệu vào: Đọc từ tệp văn bản QLBX.INP có cấu trúc:
- Dòng đầu tiên là một số nguyên dương T (0 < T ≤ 1018) ;
- Dòng thứ hai chứa ba số nguyên dương A, B, C (10 ≤ A, B, C ≤ 1018);
- Các số nguyên trên một dòng được ghi cách nhau một khoảng trắng.
Kết quả: Ghi ra tệp văn bản QLBX.OUT gồm một số duy nhất:
- Nếu không có thời điểm nào mà xe buýt cả ba tuyến cùng khởi hành thi ghi -1;
- Ngược lại ghi ra thời điểm sớm nhất mà mà xe buýt cả ba tuyến A, B, C cùng khởi hành.
Ví dụ:
QLBX.INP
1800
10 15 20
25
12 20 14

QLBX.OUT
600
-1

Ràng buộc:
• Subtask 1: 60% số điểm ứng với 10 ≤ A, B, C ≤ 1018, 0 < T ≤ 108.
• Subtask 2: 40% số điểm ứng với 10 ≤ A, B, C ≤ 1018, 108 < T ≤ 1018.
Bài 3. SỐ ĐẶC BIỆT (5,0 điểm)
Trong một buổi học lập trình, thầy giáo đưa ra một bài toán thú vị về các con số đặc
biệt. Biết rằng số đặc biệt là số có giá trị chia hết cho tổng các chữ số của nó. Chẳng hạn số 5
là số đặc biệt vì 5 chia hết cho 5, số 20 là số đặc biệt vì 20 chia hết cho 2 (2 + 0 = 2), số 13
không phải là số đặc biệt vì 13 không chia hết cho 4 (1 + 3 = 4).
Thầy muốn kiểm tra khả năng lập trình của học sinh bằng cách cho trước một dãy số
nguyên dương, học sinh cần xác định có bao nhiêu số đặc biệt trong một dãy con liên tiếp của
dãy số đã cho.
Yêu cầu: Cho dãy A có N số nguyên dương: A1, A2, …AN. Có Q dãy con, mỗi dãy
con được giới hạn bởi hai số nguyên dương L, R. Hãy cho biết trong mỗi dãy con AL, …, AR
có bao nhiêu phần tử là số đặc biệt.
Dữ liệu vào: Đọc từ tệp văn bản SODB.INP có cấu trúc:
- Dòng đầu chứa hai số nguyên dương N, Q (1 ≤ N, Q ≤ 105);
- Dòng thứ hai chứa dãy A gồm N số nguyên dương A1, A2, …AN (1 ≤ Ai ≤ 109, i = 1...N ).
Kết quả: Ghi ra tệp văn bản SODB.OUT gồm Q dòng, mỗi dòng là số lượng số đặc
biệt trong dãy con AL, …, AR tương ứng.
Trang 2

Ví dụ:
SODB.INP
83
2 18 26 20 5 28 36 39
15
33
38

SODB.OUT
4
0
3

Giải thích:
- Dãy con A1, …, A5 có 4 số đặc biệt là: 2, 18, 20, 5; vì: 2 chia hết cho 2, 18 chia hết
cho 9 (1 + 8 = 9), 20 chia hết cho 2 (2 + 0 = 2), 5 chia hết cho 5;
- Dãy con A3 không có số đặc biệt;
- Dãy con A3, …, A8 có 3 số đặc biệt là: 20, 5, 36.
Ràng buộc:
• Subtask 1: 30% số điểm ứng với Q = 1, L = 1, R = N;
• Subtask 2: 40% số điểm ứng với Q ≤ 103;
• Subtask 3: 30% số điểm còn lại không ràng buộc gì thêm.
Bài 4. CHỌN SỐ (5,0 điểm)
Cho một ma trận hai chiều kích thước N x 3 gồm N dòng và 3 cột, mỗi dòng gồm 3 số
nguyên dương ai, bi, ci (i = 1 …N).
Yêu cầu: Hãy chọn mỗi dòng một phần tử (không được phép chọn hai phần tử liên
tiếp ở cùng một cột) sao cho tổng các phần tử được chọn trên N dòng là lớn nhất.
Dữ liệu vào: Đọc từ tệp văn bản CHONSO.INP có cấu trúc:
- Dòng đầu chứa số nguyên dương N (1 ≤ N ≤ 105);
- Dòng thứ i (i = 1…N) trong N dòng tiếp theo chứa ba số nguyên dương a i, bi, ci
(ai, bi, ci ≤ 107).
- Các số nguyên trên một dòng được ghi cách nhau một khoảng trắng.
Kết quả: Ghi ra tệp văn bản CHONSO.OUT một số nguyên duy nhất biểu thị tổng
các phần tử được chọn trên N dòng là lớn nhất.
Ví dụ:
CHONSO.INP
4
743
257
369
453

CHONSO.OUT
26

Giải thích
743
257
369
453
- Dòng thứ nhất: chọn số 7
- Dòng thứ hai: chọn số 5
- Dòng thứ ba: chọn số 9
- Dòng thứ tư: chọn số 5
- Tổng các số được chọn:
7 + 5 + 9 + 5 = 26
Trang 3

Ràng buộc:
• Subtask 1: 50% số điểm ứng với 1 ≤ N ≤ 25.
• Subtask 2: 50% số điểm ứng với 25 < N ≤ 105.
---------- Hết ----------

Trang 4

Bài 1: SỐ MẬT MÃ (5,0 điểm)
Subtask 1. n ≤ 20 (3,0 điểm)
Subtask 2. 20 < n ≤ 50 (2,0 điểm)
Chương trình minh họa:
#include
using namespace std;
using ll =long long;
int main() {
freopen("SOMM.INP", "r", stdin);
freopen("SOMM.OUT", "w", stdout);
int N;
cin >> N;
ll a = 1, b = 2, c;
for (int i = 2; i <= N; ++i) {
c = a + b;
a = b;
b = c;
}
cout << (N == 0 ? a : b);
}

Bài 2: QUẢN LÝ BẾN XE (5,0 điểm)
Subtask 1: 10 ≤ A, B, C ≤ 1018, 0 < T ≤ 108 (3,0 điểm).
Subtask 2: 40% số điểm ứng với 10 ≤ A, B, C ≤ 1018, 108 < T ≤ 1018 (2,0 điểm).
Chương trình minh họa:
#include
using namespace std;
using ll = long long;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main() {
freopen("QLBX.INP", "r", stdin);
freopen("QLBX.OUT", "w", stdout);
ll T, A, B, C;
cin >> T >> A >> B >> C;
ll res = lcm(lcm(A, B), C);
cout << (res <= T ? res : -1);
}

Bài 3: SỐ ĐẶC BIỆT (5,0 điểm)
Giải thuật đề xuất: Tiền xử lý mảng Prefix Sum
1. Bước 1: Đánh dấu đặc biệt: Duyệt mảng A và đánh dấu phần tử nào là số đặc biệt:
M[i] = 1 nếu A[i] đặc biệt, ngược lại 0.
2. Bước 2: Tính prefix sum: Tính mảng P[i] = số lượng số đặc biệt từ A[1] đến A[i].
3. Bước 3: Trả lời truy vấn: Với mỗi truy vấn (L, R), ta có: res = P[R] - P[L - 1]
4. Độ phức tạp: O(N+Q)
Subtask 1. Q = 1, L = 1, R = N (1,5 điểm).
Subtask 2. Q ≤ 103 (2,0 điểm).
Subtask 3. Không ràng buộc (1,5 điểm).
Chương trình minh họa:
#include
using namespace std;
using ll = long long;
int TongCS(int x) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
int main() {
freopen("SODB.INP", "r", stdin);
freopen("SODB.OUT", "w", stdout);
int N, Q;
cin >> N >> Q;
int A[100005], M[100005], P[100005];
for (int i = 1; i <= N; ++i) {
cin >> A[i];
int sum = TongCS(A[i]);
M[i] = (A[i] % sum == 0) ? 1 : 0;
}
F[0] = 0;
for (int i = 1; i <= N; ++i)
P[i] = P[i - 1] + M[i];
while (Q--) {
int L, R;
cin >> L >> R;
cout << P[R] - P[L - 1] <}
}

Bài 4: CHỌN SỐ (5,0 điểm)
Giải thuật đề xuất: Sử dụng tư duy DP
1. Khởi tạo tổng tối đa ở dòng đầu: p[3] = {}
p[0], p[1], p[2]: Tổng lớn nhất tại dòng trước khi chọn cột 0/1/2
2. Tính tổng mới lớn nhất cho mỗi lựa chọn cột:
int x = a + max(p[1], p[2]);
int y = b + max(p[0], p[2]);
int z = c + max(p[0], p[1]);
3. Cập nhật mảng p[] với giá trị mới tính được cho dòng hiện tại
p[0] = x; p[1] = y; p[2] = z;
4. In ra kết quả cuối cùng
max({p[0], p[1], p[2]})
5. Độ phức tạp: O(N) – Duyệt qua N dòng.
Subtask 1. 1 ≤ N ≤ 25 (2,5 điểm).
Subtask 2. 25 < N ≤ 105 (2,5 điểm).
Chương trình minh họa:
#include
using namespace std;
int main() {
freopen("CHONSO.INP", "r", stdin);
freopen("CHONSO.OUT", "w", stdout);
int n, a, b, c, p[3] = {};
cin >> n;
while (n--) {
cin >> a >> b >> c;
int x = a + max(p[1], p[2]);
int y = b + max(p[0], p[2]);
int z = c + max(p[0], p[1]);
p[0] = x, p[1] = y, p[2] = z;
}
cout << max({p[0], p[1], p[2]});
}
---------- Hết ----------