SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 Đề chính thức | ĐỀ THI MÔN: TIN HỌC Thời gian làm bài: 150 phút (không kể thời gian giao đề) Ngày thi: Năm học 2024 – 2025 |
TỔNG QUAN VỀ CÁC BÀI THI
| Bài | Tên bài | Tên tệp chương trình | Tệp dữ liệu vào | Tệp dữ liệu ra | Điểm |
|---|---|---|---|---|---|
| 1 | Số may mắn | SOMAY.* | SOMAY.INP | SOMAY.OUT | 6,0 |
| 2 | Cặp phần thưởng | CAPQUA.* | CAPQUA.INP | CAPQUA.OUT | 5,0 |
| 3 | Chọn quà lưu niệm | CHONQUA.* | CHONQUA.INP | CHONQUA.OUT | 5,0 |
| 4 | Trạm phát sóng | TRAMPHAT.* | TRAMPHAT.INP | TRAMPHAT.OUT | 4,0 |
Dấu trong tên tệp được thay thế bằng đuôi PAS, CPP hoặc PY tùy theo ngôn ngữ lập trình thí sinh sử dụng.*
Bài 1 (6,0 điểm). Số may mắn
Một số nguyên dương $M$ được gọi là số may mắn nếu $M$ có đúng 3 ước số nguyên dương phân biệt và tổng các chữ số của $M$ là một số nguyên tố.
Ví dụ:
- Số $4$ có 3 ước số là $1, 2, 4$; tổng các chữ số là $4$ (không phải số nguyên tố) $\rightarrow$ không là số may mắn.
- Số $9$ có 3 ước số là $1, 3, 9$; tổng các chữ số là $9$ (không phải số nguyên tố) $\rightarrow$ không là số may mắn.
- Số $25$ có 3 ước số là $1, 5, 25$; tổng các chữ số là $2 + 5 = 7$ (là số nguyên tố) $\rightarrow$ $25$ là số may mắn.
Yêu cầu: Cho hai số nguyên dương $L, R$ ($1 \le L \le R$). Hãy đếm số lượng số may mắn trong đoạn $[L, R]$.
Dữ liệu vào: Nhập từ tệp SOMAY.INP gồm một dòng duy nhất chứa hai số nguyên dương $L, R$ cách nhau bởi dấu cách.
Dữ liệu ra: Ghi ra tệp SOMAY.OUT một số nguyên duy nhất là số lượng số may mắn tìm được.
Ví dụ:
SOMAY.INP | SOMAY.OUT | Giải thích |
|---|---|---|
1 50 | 2 | Trong đoạn $[1; 50]$, có 2 số may mắn là $25$ và $49$ (có ước là $1, 7, 49$; tổng chữ số $4 + 9 = 13$ là số nguyên tố). |
Ràng buộc:
- Subtask 1 (60% số điểm): $1 \le L \le R \le 10^6$.
- Subtask 2 (40% số điểm): $1 \le L \le R \le 10^{12}$.
Bài 2 (5,0 điểm). Cặp phần thưởng
Trong buổi dã ngoại, thầy giáo chuẩn bị $N$ gói quà xếp thành một hàng ngang. Gói quà thứ $i$ có giá trị là $A_i$ ($1 \le i \le N$). Thầy muốn chọn ra hai gói quà ở hai vị trí khác nhau $i$ và $j$ ($1 \le i < j \le N$) để trao cho hai bạn đội trưởng sao cho tổng giá trị của hai gói quà chia hết cho một số nguyên dương $K$ cho trước.
Yêu cầu: Cho dãy $A_1, A_2, \ldots, A_N$ và số nguyên dương $K$. Hãy đếm số cặp chỉ số $(i, j)$ thỏa mãn:
$$1 \le i < j \le N \quad \text{và} \quad (A_i + A_j) \text{ chia hết cho } K$$
Dữ liệu vào: Nhập từ tệp CAPQUA.INP:
- Dòng đầu chứa hai số nguyên dương $N, K$ ($2 \le N \le 10^5; 1 \le K \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 10^9$) cách nhau bởi dấu cách.
Dữ liệu ra: Ghi ra tệp CAPQUA.OUT một số nguyên duy nhất là số lượng cặp $(i, j)$ thỏa mãn.
Ví dụ:
CAPQUA.INP | CAPQUA.OUT | Giải thích |
|---|---|---|
5 41 3 4 7 5 | 3 | Các cặp thỏa mãn là: • Cặp $(1, 2)$: $A_1 + A_2 = 1 + 3 = 4$ chia hết cho $4$. • Cặp $(1, 4)$: $A_1 + A_4 = 1 + 7 = 8$ chia hết cho $4$. • Cặp $(2, 5)$: $A_2 + A_5 = 3 + 5 = 8$ chia hết cho $4$. |
Ràng buộc:
- Subtask 1 (50% số điểm): $N \le 2000; K \le 1000$.
- Subtask 2 (50% số điểm): $N \le 10^5; K \le 10^5$.
Bài 3 (5,0 điểm). Chọn quà lưu niệm
Tại một hội chợ, có $N$ món đồ lưu niệm được bày bán. Món đồ thứ $i$ có giá mua là $C_i$ đồng và mức độ yêu thích là $V_i$ điểm ($1 \le i \le N$). Bạn An có ngân sách tối đa là $S$ đồng. An chỉ có thể mua mỗi món đồ nhiều nhất một lần.
Tuy nhiên, có một ưu đãi đặc biệt: nếu An mua món đồ thứ $i$ và chọn món đồ này làm món quà may mắn, An sẽ được giảm một nửa giá mua của món đồ đó (tức là chỉ cần trả $\lfloor C_i / 2 \rfloor$ đồng, lấy phần nguyên). An chỉ được chọn tối đa một món đồ để áp dụng ưu đãi này.
Yêu cầu: Hãy giúp An chọn một tập hợp các món đồ sao cho tổng số tiền phải trả không vượt quá $S$ và tổng mức độ yêu thích đạt được là lớn nhất có thể.
Dữ liệu vào: Nhập từ tệp CHONQUA.INP:
- Dòng đầu chứa hai số nguyên dương $N, S$ ($1 \le N \le 1000; 1 \le S \le 2000$).
- $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $C_i, V_i$ ($1 \le C_i \le 2000; 1 \le V_i \le 10^6$) lần lượt là giá mua và mức độ yêu thích của món đồ thứ $i$.
Dữ liệu ra: Ghi ra tệp CHONQUA.OUT một số nguyên duy nhất là tổng mức độ yêu thích lớn nhất tìm được.
Ví dụ:
CHONQUA.INP | CHONQUA.OUT | Giải thích |
|---|---|---|
3 108 156 104 7 | 25 | An chọn giảm giá món thứ nhất: trả $\lfloor 8 / 2 \rfloor = 4$ đồng (nhận $15$ điểm). An mua thêm món thứ hai với giá nguyên $6$ đồng (nhận $10$ điểm). Tổng chi phí: $4 + 6 = 10 \le 10$. Tổng độ yêu thích: $15 + 10 = 25$. |
Ràng buộc:
- Subtask 1 (40% số điểm): $N \le 20; S \le 100$.
- Subtask 2 (30% số điểm): $N \le 500; S \le 1000$; không có ưu đãi giảm giá (An phải mua đúng giá niêm yết $C_i$).
- Subtask 3 (30% số điểm): $N \le 1000; S \le 2000$; có áp dụng ưu đãi giảm giá tối đa 1 món.
Bài 4 (4,0 điểm). Trạm phát sóng
Trên một trục đường thẳng nối dài từ cổng trường, có $N$ phòng học được đánh dấu vị trí bởi tọa độ nguyên $X_1, X_2, \ldots, X_N$ ($X_1 < X_2 < \ldots < X_N$). Nhà trường dự định lắp đặt $K$ trạm phát sóng Wi-Fi tại một số vị trí trên trục đường này (trạm phát sóng có thể lắp tại vị trí bất kỳ trên đường thẳng, không nhất thiết trùng với vị trí phòng học).
Mỗi trạm phát sóng có bán kính phủ sóng là $R$. Một phòng học tại tọa độ $X_i$ được xem là bắt được sóng nếu tồn tại ít nhất một trạm phát sóng đặt tại vị trí $P$ sao cho $|X_i - P| \le R$.
Yêu cầu: Cho biết tọa độ của $N$ phòng học và số lượng trạm phát sóng $K$. Hãy tìm bán kính phủ sóng $R$ nhỏ nhất có thể (với $R$ là một số thực, làm tròn lấy đúng 1 chữ số sau dấu phẩy thập phân) sao cho tất cả $N$ phòng học đều bắt được sóng Wi-Fi.
Dữ liệu vào: Nhập từ tệp TRAMPHAT.INP:
- Dòng đầu chứa hai số nguyên dương $N, K$ ($1 \le K \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên dương $X_1, X_2, \ldots, X_N$ ($1 \le X_i \le 10^9$) đã được sắp xếp tăng dần.
Dữ liệu ra: Ghi ra tệp TRAMPHAT.OUT một số thực duy nhất là bán kính $R$ nhỏ nhất tìm được, in ra với đúng 1 chữ số sau dấu phẩy thập phân.
Ví dụ:
TRAMPHAT.INP | TRAMPHAT.OUT | Giải thích |
|---|---|---|
3 21 4 10 | 1.5 | Đặt 2 trạm phát sóng: • Trạm 1 tại vị trí $2.5$: phủ sóng đoạn $[1.0; 4.0]$ $\rightarrow$ phủ được phòng $1$ và $4$. • Trạm 2 tại vị trí $10.0$: phủ phòng $10$. Bán kính nhỏ nhất là $1.5$. |
Ràng buộc:
- Subtask 1 (40% số điểm): $N \le 2000; K = 1$.
- Subtask 2 (30% số điểm): $N \le 2000; 1 \le K \le N$.
- Subtask 3 (30% số điểm): $N \le 10^5; 1 \le K \le N$.
--------- HẾT ---------
Cán bộ coi thi không giải thích gì thêm.
Họ và tên thí sinh: ................................................................ Số báo danh: ........................