Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án)

 Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
 ĐỀ SỐ 3
SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP 
 NỘI THÀNH PHỐ - NĂM HỌC 2022-2023
 ĐỀ CHÍNH THỨC Môn: TIN HỌC
 (Đề thi gồm 03 trang) Thời gian: 150 phút (không kể thời gian giao đề)
 TỔNG QUAN ĐỀ THI
 Tên tệp Tên tệp Tên tệp 
STT Tên bài Điểm
 chương trình dữ liệu vào kết quả ra
 1 Thời gian TG.* TG.INP TG.OUT 5
 2 Mật mã MM.* MM.INP MM.OUT 5
 3 Trạm phát sóng TPS.* TPS.INP TPS.OUT 4
 4 Triễn lãm TL. TL.INP TL.OUT 3
 5 Dãy đẹp DD.* DD.INP DD.OUT 3
Chú ý: Dấu * được thay thế bởi PAS, CPP, PY của ngôn ngữ lập trình được sử dụng tương 
ứng là Pascal, C/C++ hoặc Python.
Bài I (5,0 điểm). Thời gian
Trung tâm lái xe tổ chức một đợt sát hạch vào lúc 8 giờ 00 phút sáng. Thời gian thực hiện 
bài sát hạch tối đa là 100 phút. Đợt sát hạch gồm N thí sinh được đánh số từ 1 đến N. Thí 
sinh thứ i hoàn thành bài sát hạch trong Ti phút (1 ≤ i ≤ N). 
Yêu cầu: Hãy lập trình đưa ra thời điểm kết thúc bài sát hạch của mỗi thí sinh giúp trung 
tâm.
Dữ liệu vào từ tệp văn bản TG.INP:
- Dòng đầu tiên chứa một số nguyên N là số lượng thí sinh (1 ≤ N ≤ 20).
- Dòng thứ i trong N dòng tiếp theo chứa một số nguyên Ti là thời gian hoàn thành bài sát 
hạch của thi sinh thứ i (0 < Ti ≤ 100, 1 ≤ i ≤ N).
Kết quả ghi ra tệp văn bàn TG.OUT: Gồm N dòng, mỗi dòng là thời điểm bài sát hạch kết 
thúc của từng thí sinh có cấu trúc giờ:phút (không chứa dấu cách). Nếu giờ và phút nhỏ hơn 
10 thì ghi thêm một chữ số 0 trên đầu (ví dụ: 8 giờ 5 phút viết là 08:05).
Ví du:
 TG.INP TG.OUT
3 08:05
5 08:10
10 09:05
65
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
Bài II (5,0 điểm). Mật mã
Một mật thư chứa mật mã bí ẩn được tạo ra là một xâu kí tự chỉ gồm các chữ số và các kí tự 
in thường. Mật mã bí ẩn là số lượng các số nguyên phân biệt xuất hiện trong thư.
Ví dụ: Với mật thư as 00023 dkrf23smk1asd23sam09aa9 chứa 3 số nguyên phân biệt 23, 
1, 9. Nên mật mã là 3.
Yêu cầu: Hãy lập trình đưa ra mật mã bí ẩn.
Dữ liệu vào từ tệp văn bản MM.INP: Một xâu (độ dài xâu ≤ 100) gồm các chữ số và các kí 
tự in thường. Tất cả các số nguyên trong xâu có nhiều nhất 3 chữ số.
Kết quả ghi ra tệp văn bản MM.OUT: Một số nguyên duy nhất là kết quả của bài toán.
Ví dụ: 
 MM.INP MM.OUT
abc123abc2a3a1 4
as00023dkrf23smk1asd23sam09aa9 3
Bài III (4,0 điểm). Trạm phát sóng
Các trạm thu, phát sóng viễn thông của thành phố được đặt trên một đường tròn. Đường tròn 
này được chia thành 106 điểm cách đều nhau theo chiều kim đồng hồ. Một vị trí trên đường 
tròn được chọn là mốc 0. Có N trạm thu sóng được đánh thứ tự từ 1 đến N, trạm thứ i đạt ở 
vị trí ai (1 ≤ i ≤ N)
Thành phố dự kiến sẽ đầu tư K trạm phát sóng với phạm vi phát như nhau. Tuy nhiên, một 
trạm phát sóng với phạm vi phát càng dài thì chi phí càng cao. Vì vậy, thành phố cần tính 
toán để đầu tư các trạm phát sóng có phạm vi phát ngắn nhất và phải đảm bảo các trạm thu 
sóng đều nhận được tín hiệu.
Khi một trạm phát sóng có phạm vi phát là R thì các trạm thu sóng trong khoảng cách R theo 
cả hai chiều kim đồng hồ đều nhận được tín hiệu. Ví dụ: Trạm phát sóng tại vị trí 3 với phạm 
vi phát 1 thì cả trạm thu sóng ở vị trí 2 và 4 đều nhận được tín hiệu.
Yêu cầu: Tìm phạm vi phát ngắn nhất của K trạm phát sóng sẽ đầu tư để N trạm thu sóng 
đều nhận dược tín hiệu.
Dữ liệu vào từ từ tệp văn bản TPS.INP:
- Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 103).
- Dòng thứ i trong N dòng tiếp theo chứa một số nguyên ai là vị trí trạm thu sóng thứ i. 
 6
Không có hai trạm nào cùng vị trí (0 ≤ ai ≤10 , 1 ≤ i ≤ N).
- Dòng cuối cùng chứa số nguyên K là số trạm phát sóng (1 ≤ K ≤ N). Chú ý, vị trí trạm phát 
có thể được đặt cùng vị trí của một trạm thu nào đó.
Kết quả ghi ra tệp văn bản TPS.OUT: Số nguyên duy nhất là phạm vi phát sóng ngắn nhất 
của K trạm phát.
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
Ví dụ: 
 TPS.INP TPS.OUT Giải thích
4 498 Đặt một trạm phát sóng ở vị trí 503 và một trạm 
5 phát sóng ở vị trí 12340 có phạm vi phát sóng là 
1000 498.
12345
987
2
2 1 Đặt một trạm phát sóng ở vị trí 0 có phạm vi phát 
1 sóng là 1.
999999
1
Bài IV (3,0 điểm). Triển lãm
Bảo tàng thành phố có N bức tranh được đánh số thứ tự từ 1 đến N. Bức tranh thứ i có kích 
thước là Ai và được định giá là Bi (1 ≤ i ≤ N)
Giám đốc bảo tàng muốn chọn một số bức tranh trưng bày trong buổi triển lãm để thu được 
lợi nhuận lớn nhất thỏa mãn các tiêu chí:
- Phải trưng bày ít nhất một bức tranh.
- Chênh lệch về kích thước giữa các bức tranh được trưng bày càng nhỏ càng tốt.
- Tổng giá trị các bức tranh được trưng bày là lớn nhất.
Gọi Amin là kích thước nhỏ nhất, Amax là kích thước lớn nhất, S là tổng giá trị của các bức 
tranh được lựa chọn trưng bày. Lợi nhuận của bảo tàng được tính theo công thức
H = S – (Amax – Amin)
Yêu cầu: Hãy giúp Giám đốc bảo tàng tìm H lớn nhất?
Dữ liệu vào từ tệp văn bản TL.INP:
- Dòng đầu tiên chứa số nguyên N là số lượng các bức tranh (2 ≤ N ≤ 500000).
- Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên Ai và Bi là kích thước và định giá của 
 15 9
bức tranh thứ i (1 ≤ Ai ≤ 10 , 1 ≤ Bi ≤ 10 , 1 ≤ i ≤ N).
Kết quả ghi ra tệp văn bản TL.OUT: Số nguyên H lớn nhất tìm được.
Ràng buộc:
- Có 25% số test tương ứng 25% số điểm có n ≤ 16.
- 25% số test tương ứng 25% số điểm có n ≤ 300.
- 25% số test tương ứng 25% số điểm có n ≤ 5000.
- 25% số test còn lại tương ứng 25% số điểm không có ràng buộc gì thêm.
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
Ví dụ:
 TL. INP TL. OUT Giải thích
3 6 Chọn các bức tranh là 1 và 3 thì:
2 3 H = (3 + 5) – (4 – 2) = 6 là lớn nhất
9 2
4 5
Bài V (3,0 điểm). Dãy đẹp
Trong giờ số học, cô giáo đưa ra dãy A gồm N số nguyên dương từ 1 đến N. Cô cho mỗi học 
sinh chọn một dãy con B gồm các phần tử liên tiếp của A. Dãy con B đươc gọi là dãy đẹp 
nếu ta sấp xếp B theo thứ tự tăng dần thì được một dãy số nguyên liên tiếp. Dãy con chỉ gồm 
một phần tử cũng được gọi là dãy đẹp. Ví dụ, B = {2, 4, 3} là dãy đẹp trong khi B = {2,3,2} 
thì không.
Yêu cầu: Hãy giúp cả lớp đếm số lượng dãy con đẹp của A theo yêu cầu của cô giáo.
Dữ liệu vào từ tệp văn bản DD.INP:
- Dòng đầu tiên là số nguyên dương N (1 ≤ N ≤ 105).
- Dòng thứ hai chứa N số nguyên dương A1, A2, , AN (1 ≤ Ai ≤ N, 1 ≤ i ≤ N).
Kết quả ghi ra tệp văn bản DD.OUT: 
Một số nguyên duy nhất là số lượng dãy con đẹp của A.
Ràng buộc:
- Có 30% số test tương ứng 30% số điểm có N ≤ 200.
- 30% số test tương ứng 30% số điểm có N ≤ 2000 và các phần tử của A đôi một phân biệt.
- 20% số test tương ứng 20% số điểm có N ≤ 105 và các phần tử của A đôi một phân biệt.
- 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.
Ví dụ:
 DD. INP DD. OUT Giải thích
3 6 Có 6 con dãy đẹp là:
1 2 3 {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3},
3 4 Có 4 con dãy đẹp là:
2 2 1 {2}, {2},{1}, {2,1}
 ----------HẾT----------
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
 ĐÁP ÁN
Bài I (5,0 điểm). Thời gian
#include // For input/output operations
#include // Not strictly needed for this problem, but useful for arrays
#include // For std::setw and std::setfill to format output
int main() {
 // Tối ưu hóa I/O trong C++ để chương trình chạy nhanh hơn
 std::ios_base::sync_with_stdio(false);
 std::cin.tie(NULL);
 int N; // Số lượng thí sinh
 std::cin >> N;
 // Thời gian bắt đầu sát hạch: 8 giờ 00 phút
 int start_hour = 8;
 int start_minute = 0;
 for (int i = 0; i < N; ++i) {
 int Ti; // Thời gian hoàn thành của thí sinh thứ i
 std::cin >> Ti;
 // Tính tổng số phút từ 00:00 của ngày bắt đầu
 int total_minutes_at_start = start_hour * 60 + start_minute;
 // Tính tổng số phút tại thời điểm kết thúc
 int total_minutes_at_end = total_minutes_at_start + Ti;
 // Chuyển tổng số phút về giờ và phút
 int end_hour = total_minutes_at_end / 60;
 int end_minute = total_minutes_at_end % 60;
 // In kết quả theo định dạng HH:MM
 // std::setw(2) đảm bảo in ra 2 ký tự, std::setfill('0') điền ký tự '0' nếu thiếu
 std::cout << std::setw(2) << std::setfill('0') << end_hour << ":"
 << std::setw(2) << std::setfill('0') << end_minute << std::endl;
 }
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
 return 0;
}
Bài II (5,0 điểm). Mật mã
#include // For input/output operations
#include // For std::string
#include // For std::set to store unique numbers
#include // Not strictly needed, but useful generally
int main() {
 // Optimize C++ standard streams for faster input/output.
 std::ios_base::sync_with_stdio(false);
 std::cin.tie(NULL);
 std::string s; // Chuỗi đầu vào
 std::cin >> s;
 std::set distinct_positive_numbers; // Tập hợp để lưu các số nguyên dương phân biệt
 std::string current_number_str; // Chuỗi tạm để xây dựng số hiện tại
 // Duyệt qua từng ký tự trong chuỗi
 for (char c : s) {
 if (isdigit(c)) { // Nếu ký tự là một chữ số
 current_number_str += c;
 } else { // Nếu ký tự không phải là chữ số hoặc đã đến cuối chuỗi
 if (!current_number_str.empty()) { // Nếu có một chuỗi số đang chờ xử lý
 int num = std::stoi(current_number_str); // Chuyển chuỗi số thành số nguyên
 if (num > 0) { // Nếu số nguyên là dương
 distinct_positive_numbers.insert(num); // Thêm vào tập hợp
 }
 current_number_str.clear(); // Xóa chuỗi tạm để chuẩn bị cho số tiếp theo
 }
 }
 }
 // Xử lý số cuối cùng trong chuỗi (nếu chuỗi kết thúc bằng chữ số)
 if (!current_number_str.empty()) {
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
 int num = std::stoi(current_number_str);
 if (num > 0) {
 distinct_positive_numbers.insert(num);
 }
 }
 // In kích thước của tập hợp (số lượng số nguyên dương phân biệt)
 std::cout << distinct_positive_numbers.size() << std::endl;
 return 0;
}
Bài III (4,0 điểm). Trạm phát sóng
#include // Cung cấp cin, cout cho nhập xuất
#include // Cung cấp cấu trúc dữ liệu vector
#include // Cung cấp các hàm sort và unique
#include // Có thể dùng để loại bỏ trùng lặp dễ dàng hơn, nhưng unique trên vector 
đã sắp xếp là hiệu quả.
using namespace std; // Sử dụng namespace std để không phải gõ std::
// Hàm kiểm tra xem với bán kính R cho trước, có thể phủ tất cả các trạm không
// Main station at 0 degrees, K auxiliary stations
bool check(int R, const vector & initial_locations, int K) {
 // Nếu R quá lớn (>= 180 độ), một trạm có thể phủ toàn bộ đường tròn.
 // Trong trường hợp này, mọi trạm đều được phủ, không cần trạm phụ.
 if (R >= 180) {
 return true;
 }
 // Chuẩn hóa vị trí các trạm về phạm vi [0, 359] và loại bỏ các vị trí trùng lặp.
 vector locations_mod;
 for (int loc : initial_locations) {
 locations_mod.push_back(loc % 360); // Chuẩn hóa về 0-359 độ
 }
 sort(locations_mod.begin(), locations_mod.end()); // Sắp xếp để dễ dàng xử lý và loại bỏ 
trùng lặp
 locations_mod.erase(unique(locations_mod.begin(), locations_mod.end()), 
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
locations_mod.end()); // Loại bỏ trùng lặp
 // Nếu không có trạm nào cần phủ (danh sách rỗng sau khi loại bỏ trùng lặp), thì đã phủ 
được.
 if (locations_mod.empty()) {
 return true;
 }
 // Xác định các điểm KHÔNG được phủ bởi trạm chính (tại 0 độ, bán kính R).
 // Trạm chính phủ các góc trong [0, R] và [360 - R, 359].
 vector uncovered_points;
 for (int p : locations_mod) {
 if (!(p = 360 - R)) { // Nếu p KHÔNG nằm trong phạm vi phủ của trạm chính
 uncovered_points.push_back(p);
 }
 }
 // Nếu tất cả các điểm đã được phủ bởi trạm chính, không cần trạm phụ.
 if (uncovered_points.empty()) {
 return true;
 }
 // Áp dụng thuật toán tham lam để phủ các điểm còn lại bằng K trạm phụ.
 // Các điểm trong 'uncovered_points' đã được sắp xếp và nằm trong một đoạn thẳng
 // (từ R+1 đến 360-R-1), không có vấn đề vòng tròn ở đây.
 int current_aux_stations_needed = 0;
 int last_covered_angle = -1; // Góc xa nhất đã được phủ bởi trạm phụ trước đó
 for (int p : uncovered_points) {
 if (p > last_covered_angle) {
 // Điểm 'p' chưa được phủ bởi trạm phụ gần nhất, cần đặt một trạm phụ mới.
 current_aux_stations_needed++;
 // Trạm phụ đặt để phủ 'p' sẽ phủ một cung dài 2*R.
 // Để tối ưu, nó sẽ phủ từ 'p' đến 'p + 2*R'.
 last_covered_angle = p + 2 * R;
 }
 }
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
 // Trả về true nếu số trạm phụ cần dùng không vượt quá K.
 return current_aux_stations_needed <= K;
}
int main() {
 // Tối ưu hóa nhập xuất
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int N; // Số lượng trạm thu sóng
 cin >> N;
 vector A(N); // Vị trí của các trạm thu sóng
 for (int i = 0; i < N; ++i) {
 cin >> A[i];
 }
 int K; // Số lượng trạm phát sóng phụ
 cin >> K;
 // Tìm kiếm nhị phân cho R
 int low = 0;
 // Giá trị R có thể lên tới 360 (hoặc lớn hơn nếu theo ví dụ 498).
 // Nếu N=1, A=[179], K=0, cần R=179.
 // Nếu N=2, A=[0, 180], K=0, cần R=180.
 // Để bao phủ trường hợp ví dụ 498, high phải ít nhất là 498.
 // Để an toàn, có thể dùng một giới hạn trên lớn hơn hẳn, ví dụ 1000.
 // Bởi vì, nếu các trạm thu sóng rất gần nhau và trải đều, thì R nhỏ.
 // Nhưng nếu chỉ có 2 trạm ở 1 độ và 359 độ, và K=0, thì R=1 sẽ phủ được (hoặc 359).
 // Nếu có 2 trạm ở 100 và 101, và K=0, R cần 101.
 // Với K trạm phụ, nó có thể kéo giãn R.
 // Dựa vào ví dụ 498, R có thể vượt quá 360.
 // Max R có thể là: khoảng cách lớn nhất giữa 2 điểm (ví dụ 180) cộng thêm K lần 2R.
 // Một upper bound an toàn hơn: 360 * N (nếu mỗi trạm cách nhau 360 độ).
 // Nhưng R chỉ là bán kính của một trạm. Max R có thể là 360.
 // Vấn đề 498 có thể do một sai lệch trong đơn vị hoặc yêu cầu.
 // Nếu 498 là đáp án hợp lệ, R có thể là 498.
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.Hà Nội (15 Đề Kèm đáp án) - De-Thi.com
 // Tôi sẽ đặt high là 500 để bao gồm 498.
 int high = 500; // Giới hạn trên cho R.
 int ans = high; // Biến lưu trữ kết quả cuối cùng
 while (low <= high) {
 int mid = low + (high - low) / 2; // Tính giá trị giữa để thử
 if (check(mid, A, K)) {
 ans = mid; // mid là một R khả thi, thử tìm R nhỏ hơn
 high = mid - 1;
 } else {
 low = mid + 1; // mid quá nhỏ, cần R lớn hơn
 }
 }
 cout << ans << endl; // In ra phạm vi ngắn nhất tìm được
 return 0;
}
Bài IV (3,0 điểm). Triển lãm
#include // Cung cấp cin, cout
#include // Cung cấp vector
#include // Cung cấp sort và max
#include // Cung cấp deque
using namespace std;
// Cấu trúc để lưu thông tin về mỗi bức tranh
struct Picture {
 int A; // Kích thước
 int B; // Giá trị
};
// Hàm so sánh để sắp xếp các bức tranh theo kích thước A tăng dần
bool comparePictures(const Picture& p1, const Picture& p2) {
 return p1.A < p2.A;
}
 De-Thi.com