Đề thi chọn HSG Tin học 9 - 4 bài lập trình

TỔNG QUAN VỀ CÁC BÀI THI

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ụ:

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ụ:

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ụ:

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ụ:

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: ........................