SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH

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

ĐỀ THAM KHẢO

LỚP 9. TRUNG HỌC CƠ SỞ.
NĂM HỌC 2024-2025
Môn: TIN HỌC
Thời gian: 150 phút (không kể thời gian giao đề)
Ngày thi:

(Đề thi gồm 3 trang, 4 câu)
TỔNG QUAN ĐỀ THI
Tiêu đề

File chương trình

File dữ liệu

File kết quả

Sắp xếp hàng
Chữ số 0
tận cùng

SXHANG.*

SXHANG.INP

SXHANG.OUT

CS0TC.*

CS0TC.INP

CS0TC.OUT

Câu 3

Kinh doanh

KINHDOANH.*

Câu 4

Hiệu quả công
việc

HIEUQUA.*

Câu 1
Câu 2

KINHDOANH.INP KINHDOANH.OUT
HIEUQUA.INP

HIEUQUA.OUT

Dấu * được thay thế bởi PAS, PY, CPP tương ứng với ngôn ngữ lập trình Pascal, Python, C++
Câu 1. SẮP XẾP HÀNG (5 điểm)
Một cửa hàng bán nhiều loại sản phẩm, mỗi sản phẩm có các thuộc tính như giá, số lượng tồn
kho, và số lượng bán ra trong một khoảng thời gian. Cửa hàng muốn sắp xếp danh sách sản phẩm
để dễ dàng tìm ra các sản phẩm cần được nhập thêm hoặc các sản phẩm bán chạy.
Yêu cầu: Em hãy giúp cửa hàng sắp xếp giảm dần theo thứ tự ưu tiên như sau: Sản phẩm có số
lượng bán ra lớn hơn xếp trước, nếu số lượng bán bằng nhau thì sản phẩm có số lượng tồn kho
lớn hơn xếp trước, nếu số lượng tồn kho bằng nhau thì sản phẩm có giá cao xếp trước.
Dữ liệu đầu vào: Tệp SXHANG.INP có cấu trúc như sau:


Dòng đầu chứa số nguyên m là số lượng sản phẩm (1≤ m ≤105).



m dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương cách nhau bởi một khoảng trắng. Số
thứ nhất là giá của sản phẩm, số thứ hai là số lượng tồn kho, số thứ ba là số lượng bán ra
của sản phẩm, giá trị của mỗi số không vượt quá 105.

Dữ liệu đầu ra: Tệp SXHANG.OUT có cấu trúc như sau:


Dòng đầu là số m.



m dòng tiếp theo được xếp theo thứ tự giảm dần của số lượng bán ra.

Ví dụ:
SXHANG.INP

SXHANG.OUT
1

5

5

86000 4 10

45000 6 10

27000 9 4

17000 6 10

45000 6 10

86000 4 10

6000 3 3

27000 9 4

17000 6 10

6000 3 3

Ràng buộc:


50% số điểm tương ứng với m ≤ 103.



50% số điểm tương ứng với 103 < m ≤105.

Câu 2. Chữ số 0 tận cùng (5 điểm)
Biết giai thừa của một số tự nhiên n (ký hiệu là n!) được tính như sau:

n !  1 x 2 x 3 x  x n

0!  1!  1
Yêu cầu: Hãy tìm số chữ số 0 liên tiếp tận cùng của n!
Dữ liệu: Vào từ tệp CS0TC.INP gồm một số nguyên dương n (0< n <105)
Kết quả: Ghi ra tệp CS0TC.OUT một số nguyên là số chữ số 0 liên tiếp tận cùng của n giai thừa
Ví dụ:
CS0TC.INP
9

CS0TC.OUT
1

GIẢI THÍCH
9! = 1.2.3.4.5.6.7.8.9 = 362880
Vì có tích 2.5 tạo thành chữ số 0 tận cùng

Ràng buộc:



Subtask1: (30% số điểm): 1  n  20 .
Subtask2: (70% số điểm): Không có ràng buộc gì thêm

Câu 3. Kinh doanh (5 điểm)
Anh Minh là một người kinh doanh. Anh ghi lại lợi nhuận hàng ngày của mình trong N
ngày liên tiếp, có ngày lãi (giá trị dương) và ngày lỗ (giá trị âm). Anh muốn biết có bao nhiêu
đoạn thời gian liên tiếp (một chuỗi các ngày) mà tổng lợi nhuận trong khoảng thời gian đó bằng
0 ( aL  aL1  ...  aR  0 , với 1  L  R  N ). Điều này giúp anh đánh giá các giai đoạn kinh
doanh không sinh lời.
Dữ liệu: Vào từ file KINHDOANH.INP có cấu trúc như sau:
-

Dòng đầu chứa số nguyên dương N (1  N  105 ) .

-

Dòng thứ hai chứa N số nguyên a1 , a2 ,..., aN (ai  109 ) .
2

Kết quả: Ghi ra file KINHDOANH.OUT duy nhất một số, là số đoạn con (Một chuỗi
các ngày liên tiếp) thỏa đề bài.
Ví dụ:
KINHDOANH.INP
4

KINHDOANH.OUT
2

3 4 -7 3
Ràng buộc:


3
Có 50% số điểm tương ứng với 1  N  10 .



3
5
Có 50% số điểm tương ứng với 10  N  10 .

Câu 4. Hiệu quả công việc (5 điểm)
Một nhân viên muốn theo dõi hiệu suất làm việc của mình trong N ngày liên tiếp. Anh ta
đánh giá mỗi ngày bằng cách tự chấm điểm:
- 1 điểm: Ngày anh ấy làm hiệu quả.
- 0 điểm: Ngày anh ấy không làm việc hiệu quả.
Tuy nhiên, anh nhận thấy luôn có một ngày đặc biệt (ngày đặc biệt là một ngày có thể làm
việc hiệu quả hoặc không hiệu quả tức là điểm 0 hoặc điểm 1) gây ảnh hưởng xấu đến chuỗi
ngày làm việc hiệu quả. Nhiệm vụ của anh là phải loại bỏ một ngày đặc biệt, thì chuỗi ngày làm
việc hiệu quả nhất liên tiếp của anh (toàn điểm 1) sẽ có độ dài là bao nhiêu.
Dữ liệu: Vào từ file HIEUQUA.INP có cấu trúc như sau:
Một dòng duy nhất là dãy liên tiếp N số 0, 1 (1  N  105 ) .
Kết quả: Ghi ra file HIEUQUA.OUT duy nhất một số, là chuỗi ngày hiệu quả dài nhất thỏa
đề bài, nếu không có chuỗi ngày hiệu quả nào thì trả về 0.
Ví dụ:
HIEUQUA.INP

HIEUQUA.OUT

1111

3 (Giải thích: Anh ấy xóa bất kì
một ngày đặc biệt nào thì độ
dài toàn điểm 1 là 3).

0111101110011

7 (Giải thích: Anh ấy xóa một
ngày đặc biệt thứ 6 thì được độ
dài toàn điểm 1 là 7).

Ràng buộc:


3
Có 50% số điểm tương ứng với 1  N  10 .



3
5
Có 50% số điểm tương ứng với 10  N  10 .

3

HƯỚNG DẪN CHẤM
Câu 1.
Subtask 1. N  103 (2.5 điểm)
Subtask 2. N  105 (2.5 điểm)
Chương trình minh họa:
#include
using namespace std;
struct sp {
int x,y,z;
};
bool ss(const sp &a, const sp &b) {
if (a.z != b.z)
return a.z > b.z;
else
if (a.y != b.y)
return a.y > b.y;
return a.z > b.z;
}
int main() {
freopen("SXHANG.INP","r",stdin);
freopen("SXHANG.OUT","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n;
cin >> n;
vector sanpham;
for (int i = 1; i <= n; i++) {
sp temp;
cin >> temp.x >> temp.y >> temp.z;
sanpham.push_back(temp);
}
sort(sanpham.begin(), sanpham.end(), ss);
for (const auto &i : sanpham)
cout << i.x << " " << i.y << " " << i.z << endl;
return 0;
}
Câu 2. Giải thuật đề xuất
Ta có số chữ số 0 tận cùng của n! được tạo thành từ các cặp thừa số 2 và 5. Giả sử có m số 2 và
n số 5, vậy số chữ số 0 của n! là min(m, n)  n (số chữ số 5).
-

Đọc vào số tự nhiên từ tệp Input
Đếm các thừa số 5 (cần phân tích các giá trị là bội của 5 ra thừa số 5)
Số các thừa số 5 phân tích được từ dãy thừa số trên chính là số chữ số 0 tận cùng của n!
4

Subtask 1. N  103 (1.5 điểm)
Subtask 2. N  105 (3.5 điểm)
Chương trình minh họa:
#include
#include
using namespace std;
int main() {
freopen("CS0TC.INP","r",stdin);
freopen("CS0TC.OUT","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n;
cin >> n;
int d = 0;
for (int i = 1; i <= n; i++) {
int t = i;
while (t % 5 == 0) {
t /= 5;
d++;
}
}
cout << d;
return 0;
}
Câu 3. Giải thuật đề xuất
Gọi Pr efix[i] là tổng các phần tử từ đầu dãy tới i: vậy Pr efix[i]  a1  a2  ...  ai .
Ta có (a1  a2  ...  aL1 )  aL  aL1  ...  aR  (a1  a2  ...  aL1 )  aL  aL1  ...  aR

 Pr efix[ R]  Pr efix[ L 1]  aL  aL1  ...  aR
Để aL  aL1  ...  aR  0  Pr efix[ R]  Pr efix[ L  1]  0  Pr efix[ R]  Pr efix[ L  1]
Bài toán trở thành đếm số cặp ( L, R) sao cho aL  aL1  ...  aR  0 .
Dùng cấu trúc dữ liệu map trong C++ để đếm số cặp ( L, R) sao cho aL  aL1  ...  aR  0 thì độ
phức tạp O( N *log N ) .
Subtask 1. N  103 (2.5 điểm)
Subtask 2. N  105 (2.5 điểm)
Chương trình minh họa:
#include
#include
using namespace std;
int main()
5

{
freopen("KINHDOANH.INP","r",stdin);
freopen("KINHDOANH.OUT","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
long long prefix,ans;int n,number;
map mp;
cin>>n;
mp[0]=1;ans=0;prefix=0;
for(int i=1;i<=n;i++)
{
cin>>number;
prefix=prefix+number;
ans=ans+mp[prefix];
mp[prefix]=mp[prefix]+1;
}
cout<return 0;
}
Câu 4. Giải thuật đề xuất
Subtask 1. (2.5 điểm)
-

-

Duyệt i với i  0, n  1 ( n là độ dài dãy số)
o Dùng 2 biến l, r. Với l xa i nhất về bên trái sao cho s[l]='1' và s[l-1]='0', với r
xa i nhất về bên phải sao cho s[r+1]='0' và s[r]='1'
o Cập nhật ans=max(ans,r-l).
Độ phức tạp O( N 2 ) .

Subtask 2. (2.5 điểm)
Dùng kĩ thuật hai con trỏ.
Gọi l là vị trí xa i nhất về bên trái mà đoạn [l...i ] có nhiều nhất một số '0'.
-

Đầu tiên cho l=0, countZero=0 ( biến countZero dùng để đếm số lượng số 0; Duyệt i
với i  0, n  1 ( n là độ dài dãy số).
Nếu s[i]='0' thì
o Tăng countZero lên 1
o Nếu đoạn [l...i ] có countZero  1 thì độ dài đoạn [l...i ] toàn số '1' là i-l.
o Nếu đoạn [l...i ] có countZero  1 thì nếu a[l]='1' thì tăng l lên 1 ngược lại l=i
và giảm countZero đi 1.
6

Độ phức tạp O( N ) .
Chương trình minh họa:
#include
#include
using namespace std;
int main()
{
freopen("SUBONE.INP","r",stdin);
freopen("SUBONE.OUT","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
string s;int l=0,countZero=0,ans=0;
cin>>s;
for (int i=0;i{
if (s[i]=='0')
{
countZero=countZero+1;
if (countZero>1)
{
countZero=countZero-1;
if(s[l]=='1') l=i;
else l=l+1;
}
}
ans=max(ans,i-l);
}
cout<return 0;
}
---//---

7