Giải đề thi HSG TP Tin học 9 Hải Dương năm học 2023-2024 bằng Python
Giải đề thi HSG TP Tin học 9 Hải Dương năm học 2023-2024 bằng Python
Câu 1. 
Câu 1. (2,5 điểm) Tam giác cân
Bạn Nam có hai thanh gỗ với chiều dài lần lượt là và (). Nam muốn tìm thêm một thanh gỗ nữa với chiều dài là để dựng thành một tam giác cân với độ dài ba cạnh lần lượt là .
Yêu cầu: Hãy xác định giá trị để diện tích tam giác tạo được là lớn nhất.
Dữ liệu: Nhập từ bàn phím hai số nguyên dương lần lượt là và . Dữ liệu đảm bảo rằng và (không cần kiểm tra dữ liệu nhập vào).
Kết quả: In ra màn hình duy nhất số nguyên dương .
Ví dụ:
| Dữ liệu nhập vào | Kết quả in ra |
|---|---|
| 10 | 10 |
| 5 |
HƯỚNG DẪN GIẢI BÀI TẬP: TAM GIÁC CÂN (PYTHON)
1. Phân tích đề bài
Đề bài: Cho độ dài hai thanh gỗ và (). Cần tìm độ dài thanh gỗ thứ ba là để tạo thành một tam giác cân có diện tích lớn nhất.
Dữ liệu vào: Hai số nguyên dương .
Kết quả: In ra số nguyên dương .
2. Tư duy thuật toán
Để ba cạnh tạo thành một tam giác cân, cạnh chỉ có thể nhận một trong hai giá trị:
Tuy nhiên, ba cạnh của một tam giác phải thỏa mãn Bất đẳng thức tam giác: Tổng độ dài hai cạnh bất kỳ luôn lớn hơn cạnh còn lại.
Xét trường hợp cụ thể:
Giả sử ta có hai số (số lớn) và (số nhỏ).
Nếu chọn cạnh thứ ba bằng cạnh nhỏ (): Ba cạnh là . Để tồn tại tam giác thì . Điều này không phải lúc nào cũng đúng.
Nếu chọn cạnh thứ ba bằng cạnh lớn (): Ba cạnh là . Bất đẳng thức là (Luôn đúng vì ).
Về diện tích:
Trong tam giác cân, nếu hai cạnh bên càng dài thì tam giác càng cao, dẫn đến diện tích càng lớn. Do đó, việc chọn cạnh thứ ba bằng cạnh lớn hơn trong hai cạnh sẽ vừa đảm bảo điều kiện tồn tại tam giác, vừa đảm bảo diện tích lớn nhất.
Kết luận: Giá trị cần tìm chính là số lớn nhất trong hai số và .
3. Cài đặt chương trình (Python)
Dưới đây là mã nguồn tham khảo:
Cách 1: Sử dụng câu lệnh điều kiện IF-ELSE (Dễ hiểu)
“`python
# Nhập dữ liệu từ bàn phím
# Giả sử a và b được nhập trên 2 dòng khác nhau như ví dụ
try:
# Đọc a và ép kiểu sang số nguyên
a = int(input())
# Đọc b và ép kiểu sang số nguyên
b = int(input())
# So sánh để tìm số lớn nhất
if a > b:
c = a
else:
c = b
# In kết quả ra màn hình
print(c)
except ValueError:
print(“Vui lòng nhập số nguyên hợp lệ”)
“`
Cách 2: Sử dụng hàm max() tìm giá trị lớn nhất (Tối ưu)
# Nhập dữ liệu
a = int(input())
b = int(input())
# Tìm c là số lớn nhất trong a và b, sau đó in ra ngay lập tức
print(max(a, b))
4. Kiểm thử (Test case)
| Input (Dữ liệu vào) | Output (Kết quả mong muốn) | Giải thích |
|---|---|---|
| 10
5 |
10 | Chọn cạnh 10 tạo thành tam giác (10, 10, 5) hợp lệ và diện tích lớn nhất. |
| 3
7 |
7 | Chọn cạnh 7 tạo thành tam giác (3, 7, 7). |
| 100
100 |
100 | Trường hợp a=b (dù đề nói a khác b nhưng code vẫn chạy đúng). |
Hãy thử chạy code với dữ liệu trong ảnh (Input: 10, 5):
1. Logic: .
2. Ta cần tìm .
o Nếu chọn (tạo thành 5, 5, 10): (Không lớn hơn 10) Không tạo thành tam giác (đây là đoạn thẳng).
o Nếu chọn (tạo thành 10, 10, 5): (Đúng) Tạo thành tam giác.
3. Code: max(10, 5) trả về 10.
4. Kết quả: In ra 10. (Chính xác với yêu cầu đề bài).
5. Gợi ý mở rộng cho giáo viên/học sinh
Nếu bài toán yêu cầu nhập và trên cùng một dòng (ví dụ: 10 5), bạn cần sửa lại phần nhập liệu như sau:
# Nhập a và b trên cùng 1 dòng, cách nhau bởi dấu cách
a, b = map(int, input().split())
print(max(a, b))
Câu 2. (2,5 điểm) Tổng các chữ số
Cho số nguyên dương . Hãy tính tổng các chữ số của biểu diễn trong hệ thập phân.
Dữ liệu: Nhập vào từ bàn phím duy nhất số nguyên dương . Dữ liệu đảm bảo rằng (không cần kiểm tra dữ liệu nhập vào)
Kết quả: In ra màn hình duy nhất một số nguyên là tổng các chữ số của viết trong hệ thập phân.
Ví dụ:
| Dữ liệu nhập vào | Kết quả in ra |
|---|---|
| 193 | 13 |
Ghi chú:
Có 60% số lần kiểm tra ứng với 60% số điểm của bài có
40% số lần kiểm tra còn lại có
Với học sinh cấp 2, chúng ta nên giới thiệu 2 cách giải:
- Cách 1 (Tư duy Toán học): Dùng phép chia lấy dư để tách từng chữ số (cách này giúp rèn tư duy logic và áp dụng được cho mọi ngôn ngữ như Pascal, C++).
- Cách 2 (Tư duy Python): Xử lý xâu chuỗi (cách này cực nhanh, đặc trưng của Python).
Dưới đây là lời giải chi tiết để bạn hướng dẫn cho học sinh.
1. Phân tích đề bài
- Yêu cầu: Tính tổng các chữ số của .
- Ví dụ: . Các chữ số là 1, 9, 3. Tổng .
- Giới hạn: (tức là có tối đa 10 chữ số). Với máy tính, việc cộng 10 con số là việc “nháy mắt” là xong, nên ta không lo về thời gian chạy.
2. Hướng dẫn giải (Dành cho học sinh)
Cách 1: Sử dụng mẹo “Xử lý xâu ký tự” (Cách dễ nhất)
Thay vì coi số 193 là một con số để tính toán cộng trừ nhân chia, hãy coi nó là một “dòng chữ” gồm 3 ký tự ‘1’, ‘9’, ‘3’.
- Bước 1: Nhập nhưng giữ nguyên ở dạng chữ (string).
- Bước 2: Duyệt qua từng ký tự trong dòng chữ đó.
- Bước 3: Đổi ký tự đó thành số rồi cộng vào tổng.
Code Python (Cách 1):
# Nhập n dưới dạng xâu ký tự (không ép kiểu int ngay)
n_str = input()
tong = 0
# Duyệt qua từng ký tự trong xâu n
for chu_so in n_str:
# Đổi ký tự sang số nguyên và cộng vào tổng
tong = tong + int(chu_so)
print(tong)
Cách 2: Sử dụng Toán học (Phép chia lấy dư)
Cách này giúp học sinh hiểu bản chất của các con số.
- Để lấy chữ số cuối cùng của một số: Ta chia số đó cho 10 lấy dư (% 10).
- Ví dụ: 193 % 10 bằng 3.
- Để bỏ chữ số cuối cùng đi: Ta chia số đó cho 10 lấy phần nguyên (// 10).
- Ví dụ: 193 // 10 bằng 19.
Thuật toán:
- Lặp lại quá trình khi vẫn còn lớn hơn 0.
- Lấy chữ số cuối cộng vào tổng.
- Cắt bỏ chữ số cuối đi.
Mô phỏng với n = 193:
- Lần 1: 193 chia 10 dư 3 ->Tổng = 3. n còn lại 19.
- Lần 2: 19 chia 10 dư 9 -> Tổng = 3 + 9 = 12. n còn lại 1.
- Lần 3: 1 chia 10 dư 1 -> Tổng = 12 + 1 = 13. n còn lại 0.
- Dừng lại (vì n=0). Kết quả 13.
Code Python (Cách 2):
# Nhập n và chuyển sang số nguyên
n = int(input())
tong = 0
while n > 0:
# Lấy chữ số cuối cùng
chu_so_cuoi = n % 10
# Cộng vào tổng
tong = tong + chu_so_cuoi
# Cắt bỏ chữ số cuối đi (chia lấy nguyên)
n = n // 10
print(tong)
3. Lời khuyên sư phạm cho giáo viên
- Nên dạy cách nào?
- Nếu mục tiêu chỉ là giải bài nhanh: Cách 1 (Xâu ký tự).
- Nếu mục tiêu là rèn tư duy thuật toán để sau này học C++/Pascal hoặc thi học sinh giỏi các bài khó hơn: Cách 2 (Toán học). Giáo viên nên khuyến khích học sinh hiểu Cách 2.
- Giải thích về giới hạn : Giáo viên giải thích cho học sinh rằng kiểu số nguyên (int) trong Python tự động xử lý số lớn rất tốt, nên dù có lớn đến hàng tỷ thì chương trình vẫn chạy đúng, không sợ bị lỗi “tràn số” như các ngôn ngữ cũ.
Câu III. (2,0 điểm). Số nguyên tố nhỏ nhất
Cho số nguyên dương . Hãy tìm số nguyên tố nhỏ nhất lớn hơn hoặc bằng .
Dữ liệu: Nhập vào từ bàn phím duy nhất số nguyên dương . Dữ liệu đảm bảo rằng (không cần kiểm tra dữ liệu nhập vào).
Kết quả: In ra màn hình duy nhất một số nguyên dương là số nguyên tố nhỏ nhất lớn hơn hoặc bằng .
Ví dụ:
| Dữ liệu nhập vào | Kết quả in ra |
|---|---|
| 20 | 23 |
Ghi chú:
Có 60% số lần kiểm tra ứng với 60% số điểm của bài có
40% số lần kiểm tra còn lại có
1. Phân tích đề bài
- Số nguyên tố là gì? Là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 13…
- Yêu cầu: Nhập vào n.
- Nếu n là số nguyên tố $\rightarrow$ in ra n.
- Nếu n không phải là số nguyên tố $\rightarrow$ ta tăng n lên 1 đơn vị (n + 1), rồi kiểm tra tiếp. Cứ làm thế cho đến khi gặp số nguyên tố đầu tiên thì dừng lại và in ra.
- Ví dụ: Nhập 20.
- 20 không phải nguyên tố $\rightarrow$ thử 21.
- 21 không phải nguyên tố (chia hết cho 3) $\rightarrow$ thử 22.
- 22 không phải nguyên tố (chia hết cho 2) $\rightarrow$ thử 23.
- 23 là số nguyên tố $\rightarrow$ Kết quả: 23.
2. Kiến thức quan trọng (Để chạy nhanh)
Đề bài cho $n$ lên tới $10^9$ (1 tỷ). Nếu em kiểm tra số nguyên tố theo cách thông thường (chia từ 2 đến $n-1$) thì máy tính sẽ chạy rất chậm và bị quá thời gian (Time Limit Exceeded).
Mẹo tối ưu: Để kiểm tra số $k$ có phải nguyên tố không, ta chỉ cần chia thử từ 2 đến căn bậc hai của k ($\sqrt{k}$).
- Ví dụ: Kiểm tra số 100. Thay vì chia đến 99, ta chỉ cần chia đến $\sqrt{100} = 10$. Nếu từ 2 đến 10 không có ai chia hết 100 thì chắc chắn nó là số nguyên tố.
3. Code Python
Đây là đoạn code chuẩn:
# Hàm kiểm tra một số k có phải là số nguyên tố hay không
def kiem_tra_nguyen_to(k):
if k < 2:
return False # Số nhỏ hơn 2 không phải là số nguyên tố
# Chỉ cần kiểm tra từ 2 đến căn bậc hai của k
# k**0.5 nghĩa là căn bậc hai của k
can_bac_hai = int(k**0.5)
for i in range(2, can_bac_hai + 1):
if k % i == 0:
return False # Nếu chia hết cho i thì không phải số nguyên tố
return True # Nếu chạy hết vòng lặp mà không chia hết cho ai thì là số nguyên tố
# — CHƯƠNG TRÌNH CHÍNH —
# Nhập dữ liệu n từ bàn phím
n = int(input())
# Vòng lặp vô hạn để tìm số nguyên tố
while True:
if kiem_tra_nguyen_to(n) == True:
print(n) # Tìm thấy rồi thì in ra
break # Và thoát khỏi vòng lặp ngay
else:
n = n + 1 # Chưa thấy thì tăng n lên 1 đơn vị để kiểm tra số tiếp theo
4. Giải thích chi tiết từng dòng
- Hàm kiem_tra_nguyen_to(k):
- Đây là một công cụ giúp em trả lời câu hỏi “Có/Không”.
- Dòng for i in range(2, int(k**0.5) + 1):: Đây là công thức “thần thánh” giúp bài toán chạy nhanh, đáp ứng được yêu cầu $n \le 10^9$. Nếu không có int(k**0.5) (căn bậc 2), em sẽ chỉ được 60% số điểm.
- while True::
- Đây là vòng lặp “chạy mãi mãi”.
- Nó sẽ lấy số n hiện tại đem đi kiểm tra.
- Nếu n là nguyên tố $\rightarrow$ In ra và dùng lệnh break để phá vỡ vòng lặp (dừng chương trình).
- Nếu n chưa phải nguyên tố $\rightarrow$ n = n + 1 (nhảy sang số kế tiếp) và vòng lặp lại quay lại từ đầu để kiểm tra số mới này.
5. Lưu ý cho học sinh
- Với bài này, khoảng cách giữa các số nguyên tố không quá xa. Ngay cả với số lớn cỡ 1 tỷ, máy tính chỉ cần lặp vài chục hoặc vài trăm lần là tìm thấy số nguyên tố tiếp theo, nên cách làm “tăng dần tìm kiếm” này là hoàn toàn chính xác và hiệu quả.
- Nhớ ép kiểu dữ liệu đầu vào bằng int() vì dữ liệu nhập từ bàn phím mặc định là chuỗi ký tự.
Câu IV. (2,0 điểm). Bánh Trung thu Lớp 9A có bạn học sinh, thật tình cờ lại là số nguyên tố lẻ. Nhân dịp Tết Trung thu cô giáo chủ nhiệm quyết định mua một hộp bánh lớn về liên hoan cả lớp. Các cửa hàng bánh trung thu đều bố trí hộp bánh trung thu có dạng một tam giác cân với tầng dưới cùng xếp gói bánh, tiếp theo số gói bánh của tầng trên luôn nhỏ hơn số gói bánh của tầng dưới 1 gói, tầng trên cùng có 1 gói bánh. Ví dụ hộp bánh trung thu với có dạng: [không rõ] và số lượng gói bánh trong hộp bánh trên là 15. Yêu cầu: Biết giá của hộp bánh tăng dần theo số gói bánh ở tầng dưới cùng. Quỹ lớp chỉ còn lại số tiền đủ để mua một hộp bánh có kích thước tầng dưới tối đa là . Hãy giúp cô giáo tính xem có bao nhiêu loại hộp bánh có thể mua được mà số gói bánh trong hộp chia đều được cho bạn học sinh. Dữ liệu: Nhập từ bàn phím lần lượt hai số nguyên dương . Dữ liệu đảm bảo rằng (không cần kiểm tra dữ liệu nhập). Kết quả: In ra màn hình số loại hộp bánh có kích thước tầng dưới không quá mà số gói bánh trong hộp chia đều được cho bạn học sinh.
Trang 2
Ví dụ:
| Dữ liệu nhập vào | Kết quả in ra |
|---|---|
| 7 | 5 |
| 20 | |
| Giải thích ví dụ: Trong ví dụ trên các kích cỡ hộp bánh phù hợp để số gói bánh trong | |
| hộp chia đều được cho 7 bạn là 6, 7, 13, 14, 20 |
Ghi chú:
Có 60% số lần kiểm tra với 60% số điểm của bài có
20% số lần kiểm tra tiếp theo ứng với 20% số điểm của bài có
20% số lần kiểm tra còn lại có
1. Phân tích đề bài (Dành cho học sinh dễ hiểu)
Câu chuyện:
Cô giáo muốn mua một hộp bánh xếp thành hình tháp (tam giác).
- Tầng trên cùng có 1 cái.
- Tầng dưới luôn nhiều hơn tầng trên 1 cái.
- Gọi số bánh ở tầng đáy là $k$.
- Tổng số bánh trong hộp phải chia hết cho số học sinh $m$ (với $m$ là số nguyên tố lẻ).
- Kích thước tầng đáy $k$ không được vượt quá $n$.
Nhiệm vụ: Đếm xem có bao nhiêu kích thước hộp (giá trị $k$) thỏa mãn yêu cầu trên.
2. Giải mã toán học
Đầu tiên, chúng ta cần công thức tính tổng số bánh trong hộp nếu tầng đáy có $k$ cái. Đây là tổng dãy số tự nhiên liên tiếp:
$$Tổng = 1 + 2 + 3 + … + k = \frac{k \times (k + 1)}{2}$$
Đề bài yêu cầu: Tổng phải chia hết cho $m$.
Tức là: $\frac{k \times (k + 1)}{2}$ chia hết cho $m$.
Vì $m$ là số nguyên tố lẻ (ví dụ 3, 5, 7, 11…), nên số 2 không chia hết cho $m$. Do đó, để biểu thức trên chia hết cho $m$, thì tử số $k \times (k + 1)$ phải chia hết cho $m$.
Quy tắc số nguyên tố:
Nếu tích của hai số $A \times B$ chia hết cho số nguyên tố $P$, thì bắt buộc $A$ phải chia hết cho $P$ hoặc $B$ phải chia hết cho $P$.
Áp dụng vào bài: $k \times (k + 1)$ chia hết cho $m$.
Sẽ xảy ra 2 trường hợp:
- Trường hợp 1: $k$ chia hết cho $m$. (Nghĩa là $k$ là bội số của $m$: $m, 2m, 3m…$)
- Trường hợp 2: $(k + 1)$ chia hết cho $m$. (Nghĩa là $k$ chia cho $m$ dư $m-1$: ví dụ $m-1, 2m-1, 3m-1…$)
3. Thuật toán giải
Cách 1: Dùng vòng lặp (Cách cơ bản – Chỉ được khoảng 60% số điểm)
Ta chạy vòng lặp $i$ từ $1$ đến $n$. Kiểm tra từng số xem có thỏa mãn công thức không.
- Nhược điểm: Với $n = 10^9$ (1 tỷ), máy tính sẽ chạy rất lâu (bị quá thời gian – Time Limit Exceeded). Cách này chỉ tốt để hiểu bài, không tốt để đi thi.
Cách 2: Tính toán công thức (Cách tối ưu – 100% số điểm)
Thay vì đếm thủ công, ta dùng phép tính chia.
Ta cần đếm trong khoảng từ $1$ đến $n$:
- Có bao nhiêu số chia hết cho $m$?
$\rightarrow$ Công thức: sl1 = n // m (Phép chia lấy phần nguyên).
- Có bao nhiêu số chia cho $m$ dư $m-1$ (tức là $k+1$ chia hết cho $m$)?
$\rightarrow$ Công thức: sl2 = (n + 1) // m
Đáp án cuối cùng = sl1 + sl2.
- Ưu điểm: Máy tính ra kết quả ngay lập tức bất kể $n$ lớn thế nào ($O(1)$).
Kiểm chứng với ví dụ đề bài ($m=7, n=20$):
- Các số $k$ sao cho $k$ chia hết cho 7: 7, 14 $\rightarrow$ có 2 số (20 // 7 = 2).
- Các số $k$ sao cho $k+1$ chia hết cho 7 (tức là $k$ chia 7 dư 6): 6, 13, 20 $\rightarrow$ có 3 số ((20+1) // 7 = 3).
- Tổng cộng: $2 + 3 = 5$ loại hộp. (Khớp với ví dụ!).
4. Code Python chi tiết
Đây là đoạn code tối ưu, đã xử lý việc đọc dữ liệu và tính toán theo công thức Toán học.
# Hướng dẫn:
# Để chạy chương trình, em có thể nhập 2 số trên cùng 1 dòng hoặc 2 dòng đều được.
import sys
def giai_bai_toan():
# Phần đọc dữ liệu đầu vào
# sys.stdin.read().split() giúp đọc tất cả các số trong input bất kể xuống dòng hay cách trống
try:
input_data = sys.stdin.read().split()
# Kiểm tra nếu không có dữ liệu thì dừng
if not input_data:
return
m = int(input_data[0])
n = int(input_data[1])
except ValueError:
return
# — BẮT ĐẦU XỬ LÝ (Thuật toán O(1)) —
# Đếm số lượng k thỏa mãn trường hợp 1: k chia hết cho m
# Trong đoạn [1, n], số lượng bội số của m là n chia nguyên cho m
count_case_1 = n // m
# Đếm số lượng k thỏa mãn trường hợp 2: (k + 1) chia hết cho m
# Điều này tương đương với việc tìm số lượng số j trong đoạn [1, n] sao cho j chia m dư (m-1).
# Mẹo toán học: Số lượng này bằng (n + 1) chia nguyên cho m
count_case_2 = (n + 1) // m
# Tổng kết quả
result = count_case_1 + count_case_2
# In ra màn hình
print(result)
# Gọi hàm để chạy chương trình
if __name__ == “__main__”:
giai_bai_toan()
5. Giải thích code cho học sinh
- sys.stdin.read().split(): Lệnh này giúp đọc toàn bộ dữ liệu nhập vào và tách chúng ra thành một danh sách các từ (hoặc số). Nó rất mạnh vì nó xử lý tốt cả khi đề bài cho $m$ và $n$ nằm trên 1 dòng hay 2 dòng khác nhau.
- n // m: Đây là phép chia lấy phần nguyên trong Python. Ví dụ 20 // 7 bằng 2. Nó giúp ta đếm nhanh có bao nhiêu số chia hết cho $m$.
- (n + 1) // m: Đây là công thức mẹo để đếm các số chia cho $m$ bị thiếu 1 đơn vị (dư $m-1$).
- Độ phức tạp: Code này chỉ thực hiện vài phép tính cộng trừ nhân chia cơ bản, không dùng vòng lặp, nên nó chạy cực nhanh ngay cả khi $n = 10^9$ (đáp ứng yêu cầu 20% số điểm cuối cùng của bài thi).
Câu V. (1,0 điểm). Giải phương trình Ký hiệu là hàm cho tổng các chữ số của viết trong hệ thập phân. Ví dụ . Viết chương trình tìm số nghiệm nguyên dương của phương trình: Ở đây là số nguyên dương cho trước, còn là ẩn số. Dữ liệu: Nhập từ bàn phím duy nhất số nguyên dương . Dữ liệu đảm bảo rằng (không cần kiểm tra dữ liệu nhập vào). Kết quả: In ra một số nguyên không âm là số nghiệm nguyên dương của phương trình trên.
Ví dụ:
| Dữ liệu nhập vào | Kết quả in ra |
|---|---|
| 216 | 2 |
| Giải thích: Trong ví dụ trên phương trình có 2 nghiệm là 198 và 207 |
Ghi chú:
Có 60% số lần kiểm tra ứng với 60% số điểm của bài có
40% số lần kiểm tra còn lại có -Hết- 2 2
\
1. Phân tích đề bài
- Đề bài: Tìm số lượng số nguyên dương $x$ sao cho: $x + s(x) = n$.
- Trong đó:
- $s(x)$ là tổng các chữ số của $x$.
- $n$ là số nguyên dương nhập vào ($n \le 10^9$).
- Ví dụ: Với $n = 216$.
- Thử $x = 198$: $198 + (1+9+8) = 198 + 18 = 216$ (Đúng).
- Thử $x = 207$: $207 + (2+0+7) = 207 + 9 = 216$ (Đúng).
- Kết quả là 2 nghiệm.
2. Hướng giải quyết (Tư duy thuật toán)
Cách 1: Cách “Ngây thơ” (Duyệt trâu) – Chỉ ăn được 60% số điểm
Cách đơn giản nhất mà chúng ta nghĩ đến là: Vì $x + s(x) = n$ nên chắc chắn $x$ phải nhỏ hơn $n$. Ta sẽ cho vòng lặp chạy từ $1$ đến $n$. Gặp số nào thỏa mãn thì đếm.
- Ưu điểm: Dễ hiểu, dễ code.
- Nhược điểm: $n$ có thể lên tới 1 tỷ ($10^9$). Máy tính không thể chạy 1 tỷ vòng lặp trong 1 giây được (thường chỉ chạy được khoảng 10-100 triệu phép tính/giây). Cách này sẽ bị Time Limit Exceeded (Quá thời gian) với các test lớn.
Cách 2: Cách Tối ưu (Dựa vào toán học) – Ăn trọn 100% điểm
Ta cần thu hẹp phạm vi tìm kiếm lại. Hãy quan sát:
$$x = n – s(x)$$
Vì $s(x)$ là tổng các chữ số của $x$, mà $x \le 10^9$ (theo đề bài $n$ tối đa là $10^9$), nên số $x$ lớn nhất có thể xét là $999,999,999$.
Tổng các chữ số lớn nhất có thể có là: $9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 = 81$.
Nghĩa là: $s(x)$ lớn nhất chỉ khoảng 81 đơn vị.
Từ phương trình $x = n – s(x)$, ta suy ra $x$ chỉ có thể nằm trong khoảng từ $(n – 90)$ đến $n$ mà thôi.
=> Chiến thuật: Thay vì chạy từ 1 đến $n$, ta chỉ cần chạy vòng lặp từ n – 90 đến n. Số lần lặp tối đa chỉ là 90 lần (rất rất nhanh, máy tính xử lý trong nháy mắt kể cả $n = 1$ tỷ).
3. Cài đặt chương trình bằng Python
Dưới đây là code Python hoàn chỉnh:
# Hàm tính tổng các chữ số của một số k
def tinh_tong_chu_so(k):
# Chuyển số thành chuỗi để duyệt từng ký tự số
chuoi_so = str(k)
tong = 0
for chu_so in chuoi_so:
tong = tong + int(chu_so)
return tong
# — CHƯƠNG TRÌNH CHÍNH —
# 1. Nhập dữ liệu n
# Dùng try-except để tránh lỗi nếu nhập liệu sai định dạng (thói quen tốt)
try:
n_input = input()
if not n_input: # Kiểm tra nếu nhập rỗng
exit()
n = int(n_input)
except ValueError:
exit()
# 2. Xử lý bài toán (Thuật toán tối ưu)
dem_nghiem = 0
# Xác định điểm bắt đầu duyệt.
# Ta chỉ cần duyệt ngược lại khoảng 90 đơn vị so với n.
# Tuy nhiên phải đảm bảo điểm bắt đầu >= 1 (vì đề yêu cầu nghiệm nguyên dương)
start = n – 90
if start < 1:
start = 1
# Duyệt x từ start đến n
for x in range(start, n + 1):
# Tính s(x)
sx = tinh_tong_chu_so(x)
# Kiểm tra điều kiện đề bài: x + s(x) = n
if x + sx == n:
dem_nghiem += 1
# 3. In kết quả
print(dem_nghiem)
4. Giải thích chi tiết mã nguồn cho học sinh
- Hàm tinh_tong_chu_so(k):
- Ví dụ $k = 198$.
- Lệnh str(k) biến số 198 thành chuỗi văn bản “198”.
- Vòng lặp for sẽ lấy từng ký tự ‘1’, ‘9’, ‘8’.
- Lệnh int(chu_so) biến ký tự thành số để cộng vào tong. Kết quả là $1+9+8=18$.
- Đoạn start = n – 90:
- Đây là “chìa khóa” để giải bài toán này.
- Với $n=216$, thay vì tìm từ 1, máy sẽ bắt đầu tìm từ $216 – 90 = 126$.
- Với $n=1.000.000.000$, máy sẽ tìm từ $999.999.910$. Khối lượng công việc giảm đi hàng triệu lần.
- Điều kiện if start < 1: start = 1:
- Để phòng trường hợp $n$ quá nhỏ (ví dụ $n=10$). Khi đó $10 – 90 = -80$.
- Nghiệm phải là số nguyên dương ($x > 0$), nên ta phải ép nó bắt đầu từ 1.
5. Test thử với ví dụ đề bài
- Input: 216
- Chạy vòng lặp:
- Chương trình sẽ duyệt các số gần 216.
- Khi x = 198: Tổng chữ số là 18. $198 + 18 = 216$ (Thỏa mãn -> đếm = 1).
- …
- Khi x = 207: Tổng chữ số là 9. $207 + 9 = 216$ (Thỏa mãn -> đếm = 2).
- Các số khác trong khoảng đó sẽ không thỏa mãn.
- Output: 2
Cách giải này đảm bảo chính xác, ngắn gọn và đạt điểm tối đa về hiệu suất thời gian.
