Tài liệu Bồi dưỡng học sinh giỏi Tin học bậc THCS - Chuyên đề: Giải đề thi học sinh giỏi bằng ngôn ngữ lập trình Python 3.x - Nguyễn Tấn Phong

Tác giả: NGƯT Nguyễn Tấn Phong – Trường THCS Đồng Nai, Cát Tiên, Lâm Đồng 
TÀI LIỆU BỒI DƯỠNG HỌC SINH GIỎI TIN HỌC BẬC THCS 
CHUYÊN ĐỀ 
GIẢI ĐỀ THI HỌC SINH GIỎI 
BẰNG NNLT PYTHON 3.x 
Tác giả: NGƯT Nguyễn Tấn Phong 
 Đơn vị: Trường THCS Đồng Nai, huyện Cát Tiên, tỉnh Lâm Đồng 
1. ĐỀ THI HSG HUYỆN CÁT TIÊN – NĂM HỌC 2020 – 2021 
Câu 1: Tính tổng 
Viết chương trình tính tổng: 
2 2 2
1 1 1
S=1+ + +...+
2 3 n
* Dữ liệu vào từ file: TONG.INP 
 - Dòng đầu tiên ghi số tự nhiên n. 
 * Kết quả ra file: TONG.OUT 
 - Dòng đầu tiên ghi số thực là tổng S, làm tròn đến hai chữ số thập phân. 
 Ví dụ: 
TONG.INP TONG.OUT 
3 1,361 
4 1,424 
Phân tích: Kết quả file OUT dùng dấu phẩy (,) để ngăn cách phần nguyên và phần 
thập phân và làm tròn 3 chữ số thập phân. 
Đây được xem là một “bẩy” kĩ năng đọc và phân tích đề bài (còn gọi là “bẩy” 
cá tính thí sinh). 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
#Đọc dữ liệu vào từ file INP 
fi = open('tong.inp') 
n = int(fi.read()) 
fi.close() 
#Thuật toán 
tong = 0 
2 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
7 
8 
9 
10 
11 
12 
13 
14 
15 
for i in range(1,n+1): 
 tong = tong + 1/(i**2) 
#Xử lý dấu thập phân 
tong = str(round(tong,3)) #làm tròn 3 chữ số thập phân 
tong=tong.replace('.',',',1) #thay dấu chấm . bởi dấu phẩy , 
#Ghi vào file OUT 
fo = open('tong.out','w') 
fo.write(tong) 
fo.close() 
☼Tìm hiểu: .replace(); round(); str() 
Câu 2: Tìm số tự mãn trong dãy 
Qui ước: Số tự mãn bậc 3 là những số bằng tổng lập phương các chữ số 
của nó. Ví dụ: Số 153 là số tự mãn vì 153 = 13 + 53 + 33. 
Cho dãy gồm N phần tử là số nguyên dương A1, A2, ... , An; (0<N<=103; 
0<Ai<=10
6). Viết chương trình tìm những số tự mãn trong dãy số đã cho? 
* Dữ liệu vào từ file: SOTUMAN.INP 
- Dòng đầu tiên chứa số nguyên dương N. 
- Dòng thứ hai chứa N số nguyên dương, các số cách nhau một khoảng trắng. 
* Kết quả ra file: SOTUMAN.OUT 
- Dòng đầu tiên ghi các số tự mãn tìm được theo thứ tự tăng dần, các số cách 
nhau một khoảng trắng. 
Ví dụ: 
SOTUMAN.INP SOTUMAN.OUT 
5 
6 371 18 153 28 
153 371 
Phân tích: Kiểm tra lần lượt các phần tử trong dãy đã cho có là số tự mãn bậc 3 
hay không? Nếu có thì lưu số đó ra một mảng kết quả. 
Thuật toán: xây dựng hàm kiểm tra số tự mãn bậc 3 hoặc tính trực tiếp. 
Code tham khảo: 
Cách 1: Xây dựng hàm kiểm tra số tự mãn 
3 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
#Đọc dữ liệu vào từ file INP 
fi = open('SOTUMAN.INP') 
n = int(fi.readline()) 
a = fi.readline().split() 
for i in range(n): a[i] = int(a[i]) #chuyển mảng a về số nguyên 
fi.close() 
#Xây dựng hàm kiểm tra số tự mãn (True/False) 
def sotuman(m): 
 tlp=0 
 for i in str(m): tlp = tlp + int(i)**3 
 if tlp==m: return True 
 return False 
#Thuật toán xử lý 
b=[] 
for i in a: 
 if sotuman(i): b.append(i) 
b.sort() #Sắp xếp mảng b tăng dần 
#Ghi kết quả vào file OUT 
fo = open('SOTUMAN.OUT','w') 
for i in b: fo.write(str(i)+' ') 
fo.close() 
Cách 2: Tối ưu cách 1 bằng kĩ thuật sử dụng List Comprehension 
1 
2 
3 
4 
5 
6 
7 
#đọc dữ liệu vào 
fi = open('SOTUMAN.INP') 
n = int(fi.readline()) 
a = list(map(int,fi.readline().split())) 
fi.close() 
#Thuật toán với List Comprehension 
b = [] 
4 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
8 
9 
10 
11 
12 
13 
14 
for i in a: 
 if i == sum([int(x)**3 for x in str(i)]): b.append(i) 
b.sort() #Sắp xếp mảng b tăng dần 
#ghi file OUT 
fo = open('SOTUMAN.OUT','w') 
for i in b: fo.write(str(i)+' ') 
fo.close() 
☼Tìm hiểu: - Thay 2 dòng lệnh 4, 5 bằng dòng lệnh dùng hàm list(map()): 
a = list(map(int,fi.readline().split())) 
- Bằng kĩ thuật dùng List Comprehension ta sửa lại hàm sotuman(m) của cách 1 
như sau: 
def sotuman(m): 
return m==sum([int(i)**3 for i in str(m)]) 
Câu 3: Xếp hàng 
Trong giờ sinh hoạt tập thể, lớp 9A có n học sinh (n <=45) xếp thành hàng 
dọc. Mỗi học sinh có chiều cao a[i]. Em hãy viết chương trình đếm số bạn có chiều 
cao bằng nhau nhiều nhất. 
* Dữ liệu vào từ file: XEPHANG.INP 
 - Dòng thứ nhất chứa số tự nhiên n. 
 - Dòng thứ hai gồm n số tự nhiên a[i], mỗi số ứng với chiều cao của từng bạn 
(đơn vị cm), các số cách nhau một khoảng trắng. 
 * Kết quả ra file: XEPHANG.OUT 
 - Gồm một dòng ghi 2 số tự nhiên. Số thứ nhất ghi tổng số bạn có chiều cao 
bằng nhau nhiều nhất, số thứ 2 ghi chiều cao tương ứng, các số cách nhau một 
khoảng trắng. 
Ví dụ: 
XEPHANG.INP XEPHANG.OUT 
10 
160 158 158 160 159 158 159 160 158 161 
4 158 
5 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
Code tham khảo: 
Cách 1: Lọc phần tử không trùng nhau đôi một bằng List Comprehension 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
fi = open('xephang.inp') 
n = int(fi.readline()) 
a = list(map(int,fi.readline().split())) 
fi.close() 
#Thuật toán 
b=[] 
[b.append(x) for x in a if x not in b] #lọc lấy các số khác nhau trong a 
dem = 0 
chieucao = 0 
for i in b: 
 if dem < a.count(i): 
 dem = a.count(i) 
 chieucao=i 
#ghi file OUT 
fo = open('xephang.out','w') 
fo.write(str(dem)+' ' + str(chieucao)) 
fo.close() 
☼Tìm hiểu: phương thức .count() 
Cách 2: Dùng hàm có sẵn max(set(),key = .count) 
1 
2 
3 
4 
5 
6 
7 
8 
9 
fi = open('xephang.inp') 
n = int(fi.readline()) 
a = list(map(int,fi.readline().split())) 
fi.close() 
#Thuật toán 
chieucao = max(set(a), key = a.count) 
dem=a.count(chieucao) 
#ghi file OUT 
fo = open('xephang.out','w') 
6 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
10 
11 
fo.write(str(dem)+' ' + str(chieucao)) 
fo.close() 
☼Tìm hiểu: set(), max(set(), key = .count) 
Câu 4: Kangaroo 
Một chú Kangaroo muốn đi thăm một người bạn trên cùng tuyến đường cách 
đó một khoảng n (đơn vị dm). Kangaroo chỉ có hai cách di chuyển, một là nhảy 
ngắn a (đơn vị dm), hai là nhảy dài b (đơn vị dm). Hỏi chú Kangaroo cần nhảy ít 
nhất bao nhiêu bước nhảy để đến được nhà người bạn (phải nhảy vừa đủ, không nhảy 
quá nhà bạn). 
* Dữ liệu vào từ file: KANGAROO.INP 
- Gồm ba số nguyên dương n, a, b. Các số cách nhau một khoảng trắng (1 <= 
n <= 109, 1 <= a < b <= 20). 
* Kết quả ra file: KANGAROO.OUT 
- Ghi tổng số bước nhảy ít nhất của chú Kangaroo. 
Ví dụ: 
KANGAROO.INP KANGAROO.OUT 
21 2 5 6 
Phân tích: file OUT không nêu ra trường hợp Kangaroo nhảy không được, như vậy 
dữ liệu được cho hoàn toàn phù hợp (chắc chắn có đáp số đúng). 
Lý thuyết số: Nếu gọi x, y lần lượt là số bước nhảy ngắn và số bước nhảy dài thì ta 
sẽ có phương trình nghiệm nguyên: n = ax + by. 
Code tham khảo: 
Cách 1: Dùng khái niệm lát cắt trên iterrator 
1 
2 
3 
4 
5 
6 
7 
#Đọc dữ liệu từ file INP 
fi = open('kangaroo.inp') 
n,a,b = map(int,fi.readline().split()) 
fi.close() 
#Thuật toán với lát cắt trên list 
c = [b]*(n//b) + [a]*(n//a) #khai báo mảng c 
sobuoc = -1 
7 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
for i in range(len(c)-1): 
 for j in range(i+1,len(c)): 
 if sum(c[i:j])==n: 
 sobuoc = len(c[i:j]) 
 break 
 if sobuoc != -1: break 
#Ghi file OUT 
fo = open('kangaroo.out','w') 
fo.write(str(sobuoc)) 
fo.close() 
Cách 2: Áp dụng tính chất chia hết của số nguyên 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
#Đọc dữ liệu từ file INP 
fi = open('kangaroo.inp') 
n,a,b = map(int,fi.readline().split()) 
fi.close() 
#Thuật toán tính chất chia hết số nguyên 
sobuoc=-1 
for i in range(n//b,-1,-1): 
 if (n-i*b)%a==0: 
 sobuoc = i + ((n-i*b)//a) 
 break 
#Ghi file OUT 
fo = open('kangaroo.out','w') 
fo.write(str(sobuoc)) 
fo.close() 
8 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
2. ĐỀ THI HSG HUYỆN ĐẠ TẺH – NĂM HỌC 2020 – 2021 
Câu 1: (6 điểm) Ước chung lớn nhất 
 Cho hai số tự nhiên N, M (1 < N, M < 109). Viết chương trình tìm ước chung lớn 
nhất của hai số N và M? 
 Dữ liệu vào từ file: UCLN.INP 
 - Dòng đầu tiên ghi hai số N và M, cách nhau một khoảng trắng. 
Kết quả ra file: UCLN.OUT 
 - Dòng đầu tiên ghi ước chung lớn nhất tìm được. 
 Ví dụ: 
UCLN.INP UCLN.OUT 
2 4 2 
11 17 1 
Phân tích: 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
#Đọc file INP 
fi = open('UCLN.INP') 
n,m = map(int,fi.readline().split()) 
fi.close() 
#Hàm tìm UCLN 
def ucln(a,b): 
 while a!=b: 
 if a > b: a = a - b 
 else: b = b - a 
 return a 
#ghi file OUT 
fo = open('UCLN.OUT','w') 
print(ucln(m,n),file=fo) 
fo.close() 
9 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
Câu 2: (7 điểm) Đếm các số nguyên tố 
 Cho dãy số nguyên gồm N phần tử Ai (0 < N < 103, 0 < Ai < 106). Viết chương 
trình đếm xem trong dãy số đã cho có bao nhiêu phần tử là số nguyên tố? 
 Dữ liệu vào từ file: NGUYENTO.INP 
 - Dòng đầu tiên ghi hai số N 
- Dòng thứ hai ghi N số nguyên, các số cách nhau một khoảng trắng. 
Kết quả ra file: NGUYENTO.OUT 
 - Dòng đầu tiên ghi kết quả đếm được. 
 Ví dụ: 
NGUYENTO.INP NGUYENTO.OUT 
2 
2 4 
1 
5 
7 13 27 13 29 
4 
Phân tích: 
Code tham khảo: 
Cách 1: Dùng thuật toán tìm kiếm trên dãy số 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
# Ham kiem tra so nguyen to 
def ktnt(a): 
 if(a<2): return False 
 for i in range(2,a//2+1): 
 if a%i==0: return False 
 return True 
#đọc file INP 
fi = open('NGUYENTO.INP') 
n = int(fi.readline()) 
dayso = list(map(int,fi.readline().split())) 
fi.close() 
#Thuật toán tìm kiếm 
10 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
13 
14 
15 
16 
17 
18 
19 
dem=0 
for i in dayso: 
 if ktnt(i): dem += 1 
#ghi file out 
fo = open('NGUYENTO.OUT','w') 
fo.write(str(dem)) 
fo.close() 
☼Tìm hiểu: Với cách viết câu lệnh dòng 14, 15 thì n được cho không dùng đến. 
Cách 2: Dùng List Comprehension 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
# Ham kiem tra so nguyen to trong python 
def ktnt(a): 
 if(a<2): return False 
 for i in range(2,a//2+1): 
 if a%i==0: return False 
 return True 
#đọc file INP 
fi = open('NGUYENTO.INP') 
n = int(fi.readline()) 
dayso = list(map(int,fi.readline().split())) 
fi.close() 
# thuật toán 
b = [x for x in dayso if ktnt(x)] 
#ghi file out 
fo = open('NGUYENTO.OUT','w') 
fo.write(str(len(b))) 
fo.close() 
☼Tìm hiểu: hàm len() 
Câu 3: (7 điểm) Dãy theo quy luật 
Quy ước: Ứng với mỗi số tự nhiên x (0 < x < 106), ta có số tự nhiên f(x) bằng 
tổng bình phương các chữ số của x. 
11 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
Chẳng hạn: x = 12 thì f(x) = 12 + 22 = 5. 
Từ x ta xây dựng dãy Xn theo quy ước như sau: 
 X1 = x ; X2 = f(X1) ; X3 = f(X2) ; ; Xi = f(Xi - 1) (với 1 <= i <= n < 102) 
Viết chương trình in ra dãy (Xn)? 
Dữ liệu vào từ file: DAYXN.INP 
- Dòng đầu tiên ghi số tự nhiên x và n, cách nhau một khoảng trắng. 
Kết quả ra file: DAYXN. OUT 
- Dòng đầu tiên ghi n phần tử đầu tiên của dãy, các số cách nhau một khoảng 
trắng. 
Ví dụ: 
DAYXN.INP DAYXN. OUT 
12 4 12 5 25 29 
Phân tích: 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
#Hàm tính tổng bình phương các chữ số 
def f(x): 
 return sum([int(i)**2 for i in str(x)]) 
#Đọc file INP 
fi=open('DAYXN.INP') 
x,n=map(int,fi.readline().split()) 
fi.close() 
#Thuật toán_Ghi file OUT 
fo=open('DAYXN.OUT','w') 
for i in range(n): 
 fo.write(str(x)+' ') 
 x=f(x) 
fo.close() 
☼Tìm hiểu: 
12 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
3. ĐỀ THI HSG HUYỆN ĐẠ HOAI – NĂM HỌC 2020 – 2021 
Câu 1: (5 điểm) Tính tổng 
 Viết chương trình tính và xuất ra màn hình tổng sau: 
1 1 1 1
S= + + ...+
1.3 2.4 3.5 .( 2)a a
+
+
 Với a là số nguyên dương nhập từ bàn phím. Kết quả làm tròn 1 chữ số thập 
phân. 
 Ví dụ: 
Dữ liệu vào (a) Kết quả 
1 0.3 
2 0.5 
Phân tích: Bài này đề yêu cầu nhập/xuất chuẩn, không yêu cầu dữ liệu vào ra từ 
file. 
Code tham khảo: 
1 
2 
3 
4 
a = int(input('- Nhập a = ')) 
s = 0 
for i in range(1,a+1): s += 1/(i*(i+2)) 
print('%.1f'%s) 
☼Tìm hiểu: - Định dạng số thập phân trong python theo chuẩn '%.1f'% 
- Khi a là số lớn (từ 7 chữ số trở lên) thì thời gian chạy của vòng lặp (for, while) là 
rất lâu, đây được xem là một bài tập có “bẫy” về thời gian chạy và kiến thức toán 
học. 
Kiến thức số học: Các tổng mà mỗi số hạng có tử số nhỏ hơn mẫu số (hay số hạng 
của tổng nhỏ hơn 1) thì tổng đó sẽ hội tụ về gần một giá trị cố định nào đó. Trong 
câu trên, với a>=10 thì S làm tròn 1 chữ số thập phân sẽ luôn bằng 0.7; Do vậy, để 
tránh “bẩy” thời gian chạy với số lớn ta sửa lại đoạn code như sau: 
1 
2 
3 
a = int(input('- Nhập a = ')) 
if a>=10: s = 0.7 
else: 
13 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
4 
5 
 for i in range(1,a+1): s += 1/(i*(i+2)) 
print('%.1f'%s) 
Câu 2: (5 điểm) Tổng chẵn 
 Cho một dãy số nguyên có n số (0<n<10000). Viết chương trình xuất ra các 
số chẵn có trong dãy và tổng các chữ số chẵn đó. 
* Dữ liệu vào từ file: TONGCHAN.INP 
- Dòng 1: Ghi số tữ nhiên n. 
- Dòng 2: Ghi n số nguyên của dãy, mỗi số cách nhau một khoảng trắng. 
* Kết quả ra file: TONGCHAN.OUT 
- Dòng 1: Ghi các số chẵn có trong dãy, các số cách nhau một khoảng trắng. 
- Dòng 2: Ghi tổng các số chẵn có trong dãy. 
Ví dụ: 
TONGCHAN.INP TONGCHAN. OUT 
5 
2 3 6 8 7 
2 6 8 
16 
7 
8 9 6 12 20 25 45 
8 6 12 20 
46 
Phân tích: 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
#Đọc dữ liệu từ file INP 
fi=open('TONGCHAN.INP') 
n=int(fi.readline()) 
a=list(map(int,fi.readline().split())) 
fi.close() 
#Thuật toán tìm kiếm, tính tổng và ghi file OUT 
fo=open('TONGCHAN.OUT','w') 
s=0 
for i in a: 
 if i%2==0: 
14 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
11 
12 
13 
14 
15 
 fo.write(str(i)+' ') 
 s=s+i 
fo.write('\n') 
fo.write(str(s)) 
fo.close() 
 Có thể dùng List Comprehension để thay thế đoạn code từ dòng 8 đến dòng 
12 như sau: 
b = [x for x in a if x%2==0] 
for i in b: fo.write(str(i)+' ') 
fo.write('\n') 
fo.write(str(sum(b))) 
Câu 3: (5 điểm) Số thân thiện 
 Số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó. Hai số tự nhiên 
được gọi là cặp số thân thiện với nhau nếu có chung ước nguyên tố lớn nhất. 
 Ví dụ số 14 và 21 là hai số thân thiện với nhau vì cùng có ước nguyên tố lớn 
nhất là 7. 
 Viết chương trình tìm 5 số thân thiện với số tự nhiên a (1<a<105). 
 * Dữ liệu vào từ file: THANTHIEN.INP 
- Dòng 1: Ghi số tự nhiên a. 
Kết quả ra file: THANTHIEN.OUT 
- Dòng 1: Ghi 5 số thân thiện của số a, các số cách nhau một khoảng trắng. 
Ví dụ: 
THANTHIEN.INP THANTHIEN.OUT 
25 5 10 15 20 25 
14 7 14 21 28 35 
Phân tích: 
 -“Hai số tự nhiên được gọi là cặp số thân thiện với nhau nếu có chung ước 
nguyên tố lớn nhất” hiểu đây là một quy ước, không phải là khái niệm của lý thuyết 
số. 
15 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
- Qua 2 ví dụ ta thấy kết quả file OUT là ghi 5 số thân thiện từ bé đến lớn bao 
gồm cả chính số. Thoạt nhìn có vẻ rất đơn giản! Nhưng bài toán này được xem là 
một dạng “bẩy” về kiến thức toán học! 
Chúng ta sẽ phân tích và tìm vấn đề nhé! 
Dựa vào quy ước và file OUT, ta dễ dàng xây dựng thuật toán chỉ đơn giản 
như sau: tìm ước nguyên tố lớn nhất của a, sau đó ghi vào file OUT lần lượt tích của 
ước nguyên tố lớn nhất với các số từ 1 đến 5. Như đoạn code dưới đây! 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
#Hàm kiểm tra số nguyên tố 
def ktnt(n): 
 if n<2: return False 
 for i in range(2,n//2+1): 
 if n%i==0: return False 
 return True 
#Đọc dữ liệu file INP 
fi=open('THANTHIEN.INP') 
a=int(fi.readline()) 
fi.close() 
#Tìm ước nguyên tố lớn nhất của a 
unt = 1 
for i in range(a,1,-1): 
 if a%i==0 and ktnt(i): unt=i;break 
#Ghi file OUT 
fo=open('THANTHIEN.OUT','w') 
for i in range(1,6): fo.write(str(i*unt)+' ') 
fo.close() 
Bây giờ ta xét với bộ dữ liệu: 
THANTHIEN.INP THANTHIEN.OUT 
2 2 4 6 8 10 
16 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
Ta thấy, số 6 và 10 có ước nguyên tố lớn nhất là 3 và 5; như vậy số 6, 10 và 2 
không phải là cặp số thân thiết theo quy ước. Hay nói cách khác thì bộ dữ liệu được 
tạo ra từ code trên là sai. 
 Bây giờ ta cải tiến lại code như sau: 
Cách 1: Kĩ thuật tìm kiếm với hàm tự tạo 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
#Hàm kiểm tra số nguyên tố 
def ktnt(n): 
 if n<2: return False 
 for i in range(2,n//2+1): 
 if n%i==0: return False 
 return True 
#Hàm tìm ước nguyên tố lớn nhất của một số 
def uocnt(n): 
 if ktnt(n): return n 
 for i in range(n//2+1,1,-1): 
 if n%i==0 and ktnt(i): return i 
#Đọc dữ liệu file INP 
fi=open('THANTHIEN.INP') 
a=int(fi.readline()) 
fi.close() 
#Tìm ước nguyên tố lớn nhất của a 
unt = uocnt(a) 
dem=1 
i = 1 
#Ghi file OUT 
fo=open('THANTHIEN.OUT','w') 
fo.write(str(unt)+' ') 
while dem<5: 
 i = i + 1 
 if uocnt(unt*i)==unt: 
17 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
26 
27 
28 
 fo.write(str(unt*i)+' ') 
 dem = dem + 1 
fo.close() 
Bây giờ ta kiểm chứng lại với các bộ dữ liệu: 
THANTHIEN.INP THANTHIEN.OUT 
25 5 10 15 20 25 
14 7 14 21 28 35 
2 2 4 8 16 32 
 Cách 2: Cải tiến thuật toán với List Comprehension 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
#Hàm kiểm tra số nguyên tố 
def ktnt(n): 
 if n<2: return False 
 for i in range(2,n//2+1): 
 if n%i==0: return False 
 return True 
#Hàm tìm ước nguyên tố lớn nhất của một số 
def uocnt(n): 
 if ktnt(n): return n 
 for i in range(n//2+1,1,-1): 
 if n%i==0 and ktnt(i): return i 
#Đọc dữ liệu file INP 
fi=open('THANTHIEN.INP') 
a=int(fi.readline()) 
fi.close() 
#Tìm ước nguyên tố lớn nhất của a 
unt = uocnt(a) 
b=[] 
[b.append(unt*i) for i in range(100) if (uocnt(unt*i)==unt) and len(b)<5] 
#Ghi file OUT 
18 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
21 
22 
23 
24 
fo=open('THANTHIEN.OUT','w') 
for i in b: 
 fo.write(str(i)+' ' ) 
fo.close() 
Bài 4: (5.0 điểm) Phần tử yên ngựa 
Một bảng A gồm m hàng và n cột được gọi là một ma trận m×n (m≠0, n≠0). 
Phần tử tại hàng thứ i cột thứ j được ký hiệu là A[i,j] hoặc A[i][j]. Phần tử A[i,j] 
được gọi là phần tử yên ngựa nếu nó bé nhất trong hàng i và lớn nhất trong cột j. 
Viết chương trình các tìm phần tử yên ngựa (nếu có) của ma trận A có m hàng 
n cột. 
* Dữ liệu vào từ file: PTYN.INP 
- Dòng đầu ghi hai số tự nhiên m, n, mỗi số cách nhau 1 khoảng trắng. 
- m dòng tiếp theo, mỗi dòng ghi n số nguyên là các phần tử của ma trận ma trận 
A, mỗi số cách nhau 1 khoảng trắng. 
Dữ liệu ghi ra file: PTYN.OUT 
- Ghi các cặp số (i,j) là chỉ số hàng, cột của phần tử A[i,j] nếu A[i,j] là phần tử 
yên ngựa. Mỗi cặp số ghi trên một dòng. Nếu không có phần tử yên ngựa thì ghi 
“khong co”. 
Ví dụ: 
PTYN.INP PTYN.OUT 
3 3 
1 2 3 
4 5 6 
7 8 9 
(3,1) 
3 3 
15 10 5 
55 4 6 
76 1 2 
khong co 
19 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
Phân tích: 
Code tham khảo: 
Cách 1: Tìm kiếm trên ma trận 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
#Đọc dữ liệu từ file INP 
fi=open('PTYN.INP') 
m,n=map(int,fi.readline().split())#m = hàng, n = cột 
a=[] 
for i in fi: a.append(list(map(int,i.split()))) 
fi.close() 
#lấy min hàng đưa vào mảng 1 chiều 
min_h=[0]*m 
for j,i in enumerate(a): 
 min_h[j] = min(i) 
#lấy max cột đưa vào mảng 1 chiều 
max_c=[0]*n 
for i in range(n): 
 cot=[0]*n 
 for j in range(m): 
 cot[j] = a[j][i] 
 max_c[i]=max(cot) 
#duyệt so sánh, nếu min_h[i]==max_c[j] thì xuất i+1,j+1 
fo=open('PTYN.OUT','w') 
kt = False 
for i in range(m): #min_h 
 for j in range(n): #max_c 
 if min_h[i]==max_c[j]: 
 fo.write('('+str(i+1)+','+str(j+1)+')\n') 
 kt = True 
#trường hợp không có 
if not kt: fo.write('khong co') 
20 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
28 fo.close() 
☼Tìm hiểu: - Hàm enumerate() 
 - Đọc ma trận vào mảng a và chuyển các phần tử thành int: 
a=[] 
for i in fi: a.append(list(map(int,i.split()))) 
Cách 2: Cải tiến cách 1 bằng kĩ thuật List Comprehension 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
#Đọc dữ liệu từ file INP 
fi=open('PTYN.INP') 
m,n=map(int,fi.readline().split())#m = hàng, n = cột 
a=[] 
for i in fi: a.append(list(map(int,i.split()))) 
fi.close() 
#lấy min hàng đưa vào mảng 1 chiều 
min_h=[min(i) for i in a] 
#lấy max cột đưa vào mảng 1 chiều 
_a=[list(i) for i in zip(*a)] #chuyển vị ma trận a thành _a 
max_c=[max(i) for i in _a] 
#duyệt so sánh, nếu min_h[i]==max_c[j] thì xuất i+1,j+1 
fo=open('PTYN.OUT','w') 
kt = False 
for i in range(m): #min_h 
 for j in range(n): #max_c 
 if min_h[i]==max_c[j]: 
 fo.write('('+str(i+1)+','+str(j+1)+')\n') 
 kt = True 
#trường hợp không có 
if not kt: fo.write('khong co') 
fo.close() 
☼Tìm hiểu: - hàm zip(*a) 
21 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
4. ĐỀ THI HSG HUYỆN BẢO LỘC – NĂM HỌC 2020 – 2021 
Câu 1: (5 điểm) Tính tổng 
 Cho ba số nguyên dương A, B và K (0 < A < B < 106, 1 < K < 103). Viết 
chương trình tính tổng tất cả các số M (A < M < B), sao cho M chia hết cho K. 
 Dữ liệu vào từ file: TONG.INP 
 - Dòng đầu tiên ghi ba số nguyên A, B và K, cách nhau một khoảng trắng. 
 Kết quả ra file: TONG.OUT 
 - Dòng đầu tiên ghi kết quả tính được. 
 Ví dụ: 
TONG.INP TONG.OUT 
2 8 2 10 
3 4 3 0 
Phân tích: 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
#Đọc dữ liệu từ file INP 
fi = open('TONG.INP') 
a,b,k=map(int,fi.readline().split()) 
fi.close() 
#Thuật toán 
tong=0 
for m in range(a+1,b): 
 if m%k==0: tong = tong+m 
#Ghi file OUT 
fo = open('TONG.OUT','w') 
fo.write(str(tong)) 
fo.close() 
☼Tìm hiểu: 
Cải tiến cách 1 bằng kĩ thuật List Comprehension, bằng cách thay các dòng 
lệnh 6, 7, 8 bằng dòng lệnh sau: 
22 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
tong = sum([x for x in range(a+1,b) if x%k==0]) 
Câu 2: (5 điểm) Tìm số đường khép kín 
 Ta qui ước: 
+ Các chữ số: 1, 2, 3, 5, 7 có 0 đường khép kín. 
 + Các chữ số: 0, 4, 6, 9 có 1 đường khép kín; 
+ Chữ số: 8 có 2 đường khép kín; 
 Viết chương trình tính tổng số đường khép kín của một số nguyên dương N 
(N <1010). 
 Dữ liệu vào từ file: KHEPKIN.INP 
 - Dòng đầu tiên ghi số N. 
 Kết quả ra file: KHEPKIN.OUT 
 - Dòng đầu tiên ghi tổng số đường khép kín tính được. 
 Ví dụ: 
KHEPKIN.INP KHEPKIN.OUT 
2369524 3 
Phân tích: 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
#Đọc dữ liệu từ file INP 
fi = open('KHEPKIN.INP') 
n = int(fi.read()) 
fi.close() 
#Thuật toán 
dkk = 0 
for i in str(n): 
 if i in '0469': dkk = dkk + 1 
 elif i=='8': dkk = dkk + 2 
#Ghi file OUT 
fo = open('KHEPKIN.OUT','w') 
fo.write(str(dkk)) 
fo.close() 
23 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
☼ Tìm hiểu: 
Câu 3: (5 điểm) Xóa ký tự trong xâu 
Cho xâu có N ký tự chữ số (0 < N < 255). Viết chương trình xóa đi K ký tự 
(0 < K < N) để xâu còn lại biểu diễn một số bé nhất. 
Dữ liệu vào từ file: XAU.INP 
- Dòng đầu tiên chứa xâu có N ký tự chữ số, các ký tự chữ số viết liền nhau. 
- Dòng thứ hai chứa số K. 
Kết quả ra file: XAU.OUT 
- Dòng đầu tiên ghi xâu ký tự tìm được theo yêu cầu. 
Ví dụ: 
XAU.INP XAU.OUT 
65278934 
3 
27834 
Phân tích: 
Code tham khảo: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
fi = open('XAU.INP') 
s = list(fi.readline()) 
k = int(fi.readline()) 
fi.close() 
#Thuật toán 
for i in range(k): 
 j=0 
 while (j<len(s)) and (s[j]<=s[j+1]): j += 1 
 del(s[j]) 
#Ghi file OUT 
fo = open('XAU.OUT','w') 
fo.write(''.join(s)) 
fo.close() 
☼ Tìm hiểu: 
- Hàm del(), ''.join() 
24 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
- Trong đề bài cho “xâu có N ký tự chữ số” nhưng tại dòng lệnh 2: 
s=list(fi.readline()) là đọc từng chữ số và gán vào một mảng một chiều s, thay vì 
lệnh đọc s=fi.readline(). Vì trong NNLT python qui định chuỗi str là dữ liệu có tính 
“bất biến”, do vậy không có hàm hay phương thức nào cho phép xóa một ký tự bất 
kỳ trong chuỗi s. Vì vậy, ta phải đọc vào mảng một chiều s để áp dụng hàm del(). 
- Tại dòng lệnh 8: while (j<len(s)) and (s[j]<=s[j+1]): j += 1 nếu thay đổi dấu 
“ =” thì bài toán trở thành là tìm “số lớn nhất”. 
Câu 4: (5 điểm) Bộ ba số 
Cho dãy N (1 <= N <= 103) số nguyên dương A1, A2, ..., AN (Ai <= 103). Với 
bộ ba chỉ số i, j và k (1 <= i < j < k <= N), hãy tìm giá trị S = 2Ai – 3Aj + 5Ak sao 
cho S đạt giá trị lớn nhất. 
Dữ liệu vào từ file: BOBASO.INP 
- Dòng đầu tiên chứa số N 
- Dòng thứ hai chứa N số nguyên dương A1, A2, ..., AN; các số cách nhau một 
khoảng trắng. 
Kết quả ra file: BOBASO.OUT 
- Dòng đầu tiên ghi giá trị của S tìm được. 
Ví dụ: 
BOBASO.INP BOBASO.OUT 
3 
3 2 1 
5 
7 
3 5 2 6 4 5 7 
39 
Phân tích: 
Code tham khảo: 
1 
2 
3 
4 
#Đọc dữ liệu từ file INP 
fi=open('BOBASO.INP') 
n=int(fi.readline()) 
a=list(map(int,fi.readline().split())) 
25 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
fi.close() 
#Thuật toán 
s=0 
for i in range(0,n-2): 
 for j in range(i+1,n-1): 
 for z in range(j+1,n): 
 if 2*a[i]-3*a[j]+5*a[z]>s: s=2*a[i]-3*a[j]+5*a[z] 
#Ghi file OUT 
fo=open('BOBASO.OUT','w') 
fo.write(str(s)) 
fo.close() 
☼ Tìm hiểu: 
5. ĐỀ THI HSG HUYỆN BẢO LÂM – NĂM HỌC 2020 – 2021 
Câu 1: (6 điểm) Diện tích tam giác vuông 
 Cho ba số tự nhiên a, b, c (0 < a, b, c < 106). Hãy viết chương tính diện tích 
tam giác nếu ba số đã cho là số đo ba cạnh của một tam giác vuông. 
 Dữ liệu vào từ file: TAMGIAC.INP 
 - Dòng đầu tiên ghi ba số tự nhiên a, b và c, các số cách nhau khoảng trắng. 
 Kết quả ra file: TAMGIAC.OUT 
 - Dòng đầu tiên ghi diện tích tính được (làm tròn một chữ số thập phân), nếu 
nếu ba số đã cho không phải là ba cạnh của tam giác vuông thì ghi số -1. 
 Ví dụ: 
TAMGIAC.INP TAMGIAC.OUT 
3 4 5 6.0 
3 4 9 -1 
Phân tích: 
Code tham khảo: 
1 
2 
#Đọc dữ liệu từ file INP 
fi = open('TAMGIAC.INP') 
26 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
a,b,c = map(int,fi.readline().split()) 
fi.close() 
#Thuật toán 
s = -1 
if a*a == b*b + c*c: s = round(0.5*b*c,1) 
elif b*b == a*a + c*c: s = round(0.5*a*c,1) 
elif c*c == b*b + a*a: s= round(0.5*a*b,1) 
#Ghi file OUT 
fo = open('TAMGIAC.OUT','w') 
fo.write(str(s)) 
fo.close() 
Cải tiến code trên bằng cách sử dụng mảng một chiều như sau: 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
#Đọc dữ liệu từ file INP 
fi = open('TAMGIAC.INP') 
a = list(map(int,fi.readline().split())) 
fi.close() 
#Thuật toán 
a.sort() 
s = -1 
if a[2]**2 == a[0]**2 + a[1]**2: s = round(0.5*a[0]*a[1],1) 
#Ghi file OUT 
fo = open('TAMGIAC.OUT','w') 
fo.write(str(s)) 
fo.close() 
☼ Tìm hiểu: 
Câu 2: (7 điểm) Tính số ngày 
Với lịch dương thì các tháng có 31 ngày là: 1, 3, 5, 7, 8, 10, 12 và các tháng 
có 30 ngày là: 4, 6, 9, 11. Riêng tháng 2 có thể có 28 hoặc 29 ngày tùy theo năm. Từ 
năm 2012 đến năm 2099, các năm chia hết cho 4 đều là năm nhuận và tháng 2 của 
năm nhuận có thêm ngày thứ 29. 
27 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
Cho hai bộ ba số {d1, m1, y1} và {d2, m2, y2}, mỗi bộ ba số là lần lượt là 
ngày, tháng, năm (2012 <= y1, y2 <=2099). Hãy viết chương trình tính số ngày trong 
khoảng thời gian được cho. 
 Dữ liệu vào từ file: SONGAY.INP 
 - Hai dòng đầu, mỗi dòng ghi lần lượt ba số là ngày, tháng và năm, các số 
cách nhau khoảng trắng. 
 Kết quả ra file: SONGAY.OUT 
 - Dòng đầu tiên ghi số ngày tính được. 
 Ví dụ: 
SONGAY.INP SONGAY.OUT 
25 1 2012 
26 3 2012 
61 
20 1 2018 
20 11 2020 
1035 
Phân tích: 
Code tham khảo: 
Cách 1: Dựa theo cách tính toán số học (phép đếm) 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
#Đọc dữ liệu vào từ file INP 
fi = open('SONGAY.INP') 
d1,m1,y1 = map(int,fi.readline().split()) 
d2,m2,y2 = map(int,fi.readline().split()) 
fi.close() 
#Thuật toán 
a=[0,31,28,31,30,31,30,31,31,30,31,30,31] 
songay=0 
if y1==y2: 
 if y1%4==0: a[2] = 29 
 a[m1] = a[m1] - d1 
 a[m2] = d2 
28 
Tài liệu bồi dưỡng học sinh giỏi môn tin THCS – Giải đề thi bằng ngôn ngữ python 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
 if m2==m1: songay = d2 - d1 
 else: songay = sum(a[m1:m2+1]) 
elif y1<y2: 
 #(1) Tính số ngày từ d1/m1 đến cuối năm y1 
 if y1%4==0: a[2] = 29 
 a[m1] = a[m1] - d1 
 songay=sum(a[m1:]) 
 #(2) Tính số ngày từ đầu năm y2 đến d1/m1 đến cuối năm y1 
 a=[0,31,28,31,30,31,30,31,31,30,31,30,31] 
 if y2%4==0: a[2] = 29 
 else: a[2] =