Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết)

Nội dung text: Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết)

1. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn for (int i = 0; i < M; ++i) { long long X; std::cin >> X; // Đọc tham số X cho lệnh thứ j // Xác định khoảng ảnh hưởng: [X-K, X+K] // Đảm bảo không vượt ra ngoài biên của N bóng đèn [1, N] long long left_bound = std::max(1LL, X - K); long long right_bound = std::min(N, X + K); // Ghi nhận sự kiện tăng số lần lật tại left_bound changes[left_bound]++; // Ghi nhận sự kiện giảm số lần lật tại (right_bound + 1) // Điều này đảm bảo các bóng đèn từ left_bound đến right_bound được lật, // còn bóng đèn tại right_bound + 1 trở đi thì không bị ảnh hưởng bởi lệnh này. changes[right_bound + 1]--; } // Lưu trữ các truy vấn cùng với chỉ số gốc của chúng để in kết quả đúng thứ tự std::vector > queries(Q); for (int i = 0; i < Q; ++i) { std::cin >> queries[i].first; // Đọc P cho câu hỏi thứ i queries[i].second = i; // Lưu chỉ số gốc của truy vấn } // Sắp xếp các truy vấn theo vị trí bóng đèn để duyệt theo sweep line std::sort(queries.begin(), queries.end()); // Vector để lưu trữ kết quả theo đúng thứ tự ban đầu của truy vấn std::vector answers(Q); long long current_flips = 0; // Số lần lật tích lũy auto it_changes = changes.begin(); // Iterator cho map changes // Duyệt qua các truy vấn đã sắp xếp for (const auto& query_pair : queries) { long long query_pos = query_pair.first; int query_idx = query_pair.second; // Áp dụng tất cả các thay đổi từ map 'changes' cho đến vị trí query_pos while (it_changes != changes.end() && it_changes->first <= query_pos) { DeThi.edu.vn
2. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn current_flips += it_changes->second; it_changes++; } // Kiểm tra trạng thái bóng đèn tại query_pos // Nếu current_flips là số chẵn, đèn là Vàng. Ngược lại, là Đỏ. if (current_flips % 2 == 0) { answers[query_idx] = 'V'; } else { answers[query_idx] = 'D'; } } // In kết quả ra file output theo thứ tự gốc của truy vấn for (int i = 0; i < Q; ++i) { std::cout << answers[i] << std::endl; } return 0; } Bài IV. Trò chơi (3,0 điểm) #include // Để nhập xuất dữ liệu #include // Để sử dụng std::vector #include // Để sử dụng std::sort int main() { // Chuyển hướng nhập xuất từ console sang file theo yêu cầu của đề bài freopen("MUAHANG.INP", "r", stdin); // Mở file input freopen("MUAHANG.OUT", "w", stdout); // Mở file output // Tối ưu hóa hiệu suất nhập xuất trong C++ std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int N; // Số lượng mặt hàng long long T; // Số tiền ban đầu std::cin >> N >> T; DeThi.edu.vn
3. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn std::vector A(N); // Vector lưu giá trị các mặt hàng for (int i = 0; i < N; ++i) { std::cin >> A[i]; // Đọc giá trị từng mặt hàng } // Sắp xếp giá các mặt hàng theo thứ tự tăng dần std::sort(A.begin(), A.end()); int count_items = 0; // Số mặt hàng đã mua long long remaining_money = T; // Số tiền còn lại // Duyệt qua các mặt hàng đã sắp xếp và mua nếu đủ tiền for (int i = 0; i < N; ++i) { if (remaining_money >= A[i]) { remaining_money -= A[i]; count_items++; } else { // Không đủ tiền để mua mặt hàng hiện tại, cũng sẽ không đủ cho các mặt hàng đắt hơn break; } } // In kết quả ra file output std::cout << count_items << " " << remaining_money << std::endl; return 0; } Bài V. Mua hàng (3,0 điểm) #include // Để nhập xuất dữ liệu #include // Để sử dụng std::vector #include // Để sử dụng std::min, std::max, std::sort #include // Để sử dụng std::numeric_limits // Sử dụng một giá trị INF (vô cực) đủ lớn để tránh tràn số, // nhưng không quá lớn để khi cộng trừ vẫn nằm trong giới hạn của long long const long long INF = std::numeric_limits ::max() / 2; int main() { DeThi.edu.vn
4. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn // Chuyển hướng nhập xuất từ console sang file theo yêu cầu của đề bài freopen("MUAHANG.INP", "r", stdin); // Mở file input freopen("MUAHANG.OUT", "w", stdout); // Mở file output // Tối ưu hóa hiệu suất nhập xuất trong C++ std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int N; // Số quầy hàng int M; // Số sản phẩm cần mua (theo thứ tự 1..M) std::cin >> N >> M; std::vector A(N); // A[i] là loại sản phẩm quầy i+1 bán (0-indexed A, quầy 1- indexed) for (int i = 0; i < N; ++i) { std::cin >> A[i]; } std::vector T(N); // T[i] là thời gian mua tại quầy i+1 (0-indexed T, quầy 1- indexed) for (int i = 0; i < N; ++i) { std::cin >> T[i]; } // product_quays_info[p] sẽ lưu danh sách các cặp {vị_trí_quầy_hàng, thời_gian_mua_tại_quầy_hàng_đó} // cho sản phẩm 'p'. Vị trí quầy hàng là 1-indexed. std::vector >> product_quays_info(M + 1); for (int i = 0; i < N; ++i) { product_quays_info[A[i]].push_back({i + 1, T[i]}); } // Sắp xếp các quầy hàng theo vị trí (chỉ số) để sweep-line hiệu quả for (int p = 1; p <= M; ++p) { std::sort(product_quays_info[p].begin(), product_quays_info[p].end()); } // dp_vals[j] là thời gian tối thiểu để hoàn thành mua sản phẩm hiện tại tại quầy j. DeThi.edu.vn
5. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn // Index 0 không dùng, các quầy là 1-indexed. std::vector dp_vals(N + 1, INF); // Bước 1: Khởi tạo DP cho sản phẩm 1 // Duyệt qua tất cả các quầy bán sản phẩm 1 for (const auto& quay_info : product_quays_info[1]) { int quay_idx = quay_info.first; long long time_at_quay = quay_info.second; dp_vals[quay_idx] = time_at_quay; // Thời gian mua SP1 tại quầy quay_idx là time_at_quay } // Bước 2: Lặp qua các sản phẩm từ 2 đến M for (int p = 2; p <= M; ++p) { std::vector prev_dp_vals = dp_vals; // Lưu trữ DP của sản phẩm trước (p-1) dp_vals.assign(N + 1, INF); // Khởi tạo lại DP cho sản phẩm hiện tại (p) const auto& prev_quays_info = product_quays_info[p - 1]; // Thông tin các quầy bán SP (p-1) const auto& current_quays_info = product_quays_info[p]; // Thông tin các quầy bán SP (p) // Pass 1: Duyệt từ trái sang phải để tính min(prev_dp_vals[k] - k) long long min_cost_minus_pos = INF; int prev_quay_ptr = 0; // Con trỏ cho prev_quays_info for (const auto& curr_quay_info : current_quays_info) { int current_quay_idx = curr_quay_info.first; long long time_at_current_quay = curr_quay_info.second; // Cập nhật min_cost_minus_pos với các quầy prev_product (k) mà k <= current_quay_idx while (prev_quay_ptr < prev_quays_info.size() && prev_quays_info[prev_quay_ptr].first <= current_quay_idx) { int k_idx = prev_quays_info[prev_quay_ptr].first; if (prev_dp_vals[k_idx] != INF) { min_cost_minus_pos = std::min(min_cost_minus_pos, prev_dp_vals[k_idx] - DeThi.edu.vn
6. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn k_idx); } prev_quay_ptr++; } // Nếu có đường đi hợp lệ từ bên trái if (min_cost_minus_pos != INF) { // dp_vals[current_quay_idx] = time_at_current_quay + (current_quay_idx + min_{k<=j}(prev_dp_vals[k] - k)) dp_vals[current_quay_idx] = std::min(dp_vals[current_quay_idx], time_at_current_quay + min_cost_minus_pos + current_quay_idx); } } // Pass 2: Duyệt từ phải sang trái để tính min(prev_dp_vals[k] + k) long long min_cost_plus_pos = INF; prev_quay_ptr = prev_quays_info.size() - 1; // Đặt con trỏ về cuối prev_quays_info for (int i = current_quays_info.size() - 1; i >= 0; --i) { const auto& curr_quay_info = current_quays_info[i]; int current_quay_idx = curr_quay_info.first; long long time_at_current_quay = curr_quay_info.second; // Cập nhật min_cost_plus_pos với các quầy prev_product (k) mà k >= current_quay_idx while (prev_quay_ptr >= 0 && prev_quays_info[prev_quay_ptr].first >= current_quay_idx) { int k_idx = prev_quays_info[prev_quay_ptr].first; if (prev_dp_vals[k_idx] != INF) { min_cost_plus_pos = std::min(min_cost_plus_pos, prev_dp_vals[k_idx] + k_idx); } prev_quay_ptr--; } // Nếu có đường đi hợp lệ từ bên phải if (min_cost_plus_pos != INF) { // dp_vals[current_quay_idx] = time_at_current_quay + (-current_quay_idx + min_{k>=j}(prev_dp_vals[k] + k)) DeThi.edu.vn
7. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn dp_vals[current_quay_idx] = std::min(dp_vals[current_quay_idx], time_at_current_quay + min_cost_plus_pos - current_quay_idx); } } } // Tìm giá trị nhỏ nhất trong dp_vals cho sản phẩm M (sản phẩm cuối cùng) long long min_total_time = INF; for (const auto& quay_info : product_quays_info[M]) { min_total_time = std::min(min_total_time, dp_vals[quay_info.first]); } std::cout << min_total_time << std::endl; return 0; } DeThi.edu.vn
8. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn ĐỀ SỐ 2 SỞ GIÁO DỤC VÀ ĐÀO TẠO KÌ THI CHỌN HỌC SINH GIỎI LỚP 9 HÀ NỘI CẤP THÀNH PHỐ - NĂM HỌC 2023-2024 ĐỀ CHÍNH THỨC Môn: TIN HỌC (Đề thi gồm 03 trang) Thời gian làm bài: 150 phút TỔNG QUAN ĐỀ THI STT Tên bài Tên tệp chương trình Tên tệp dữ liệu vào Tên tệp kết quả ra Điểm 1 Hóa học HOAHOC.* HOAHOC.INP HOAHOC.0UT 5 2 Ước chung UOCCHUNG.* UOCCHUNG.INP ƯOCCHUNG.OUT 5 3 Trò chơi TROCHOI.* TROCHOI.INP TROCHOI.OUT 4 4 Robot ROBOT.’ ROBOT.INP ROBOT.OUT 3 5 Đoạn tốt DOANTOT.’ DOANTOT.INP DOANTOT.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 1 (5,0 điểm). Hóa học Cho phương trình hóa học sau: 3Fe + 2O2 → Fe3O4. Cho biết số mol của Fe là A, số mol của O là B. Yêu cầu: Hãy lập trình đưa ra phần nguyên số mol của chất sản phẩm Fe3O4. Dữ liệu vào từ tệp văn bản HOAHOC.INP: Một dòng duy nhất chứa hai số tự nhiên A (A ≤ 1018) và B (B ≤ 1018). Kết quả ghi ra tệp văn bản HOAHOC.OUT: - Một số tự nhiên duy nhất là kết quả của bài toán. Ví dụ: HOAHOC.INP HOAHOC.OUT 10 10 3 Bài 2 (5,0 điểm). Uớc chung Cho trước hai số nguyên dương A và B. Yêu cầu: Hãy lập trình đưa ra ước chung lớn thứ hai của A và B. Dữ liệu vào từ tệp văn bản UOCCHUNG.INP: - Một dòng duy nhất chứa hai số tự nhiên A và B (A ≤ 1012, B ≤ 1012). Kết quả ghi ra tệp văn bản UOCCHUNG.OUT: - Một số nguyên dương duy nhất là kết quả của bài toán. Ràng buộc: - Có 80% số test tương ứng 80% số điểm có A ≤ 1000, B ≤ 1000. DeThi.edu.vn
9. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn - 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ụ: UOCCHUNG.INP UOCCHUNG.OUT 30 40 5 Bài 3 (4,0 điểm). Trò chơi Bạn có một nhân vật cần được tăng chỉ số sức mạnh. Nhân vật của bạn có N kĩ năng được đánh thứ tự từ 1 đến N. Kĩ năng thứ i (1 ≤ i ≤ N) có hai loại chỉ số tăng tiến là S i và Ci. Trong lần đầu tiên tăng cấp kì năng thứ i, nhân vật của bạn nhận được (S i + ei) chỉ số sức mạnh. Trong các lần tiếp theo tăng cấp kĩ năng thứ i, nhân vật của bạn chỉ nhận được thêm e i chỉ số sức mạnh. Bạn có thể tăng cấp một kĩ năng bất kì không giới hạn số lần. Trò chơi diễn ra trong M phút, mỗi phút nhân vật của b; nhận được một lần tăng cấp kĩ năng. Yêu cầu: Hãy tìm chỉ số sức mạnh lớn nhất mà nhân vật của bạn có thể đạt được sau M phút cho. Dữ liệu vào từ tệp văn bản TROCHOI.INP: - Dòng đầu tiên chứa hai số nguyên dương N và M (1 < N < 105,1 < M < 109). 9 9 - Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên dương Si và Ci (Si < 10 , ei < 10 ). Kết quả ghi ra tệp văn bản TROCHOI.OUT: - Một số nguyên dương duy nhất là chỉ số sức mạnh lớn nhất mà nhân vật của bạn có thể đạt được. Ràng buộc: Có 40% số test tương ứng 40% số điểm có M = 2. 40% số test tương ứng 40% số điểm có M s 100. 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ụ: TROCHOI.INP TROCHOI.OUT Giải thích 3 4 23 Cách nâng cấp tối ưu nhất là: 2 2 - Nâng cấp 3 lần kĩ năng 2. 2 5 - Nâng cấp 1 lần kĩ năng 3. 5 1 Bài 4 (3,0 điểm). Robot Cho một bảng số nguyên dương A có N hàng, M cột và một số nguyên dương K. Số nằm ở hàng i, cột j có tọa độ là (i, j) và có giá trị là Aij. Một con robot đang đứng ở ô (1, 1) và cần di chuyển đến ô (M, N). Khi đứng ở ô (i, j), robot chỉ có thể di chuyển vào ba ô (i, j + 1), (i + 1, j) hoặc (i + l, j + 1). Cho Q truy vấn, mỗi truy vấn gồm một số tự nhiên X (X < K). Với mỗi truy vấn, hãy cho biết đường đi của robot từ ô (1, 1) đến ô (M, N) có thể đi qua nhiều DeThi.edu.vn
10. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.Hà Nội (Có đáp án chi tiết) - DeThi.edu.vn nhất bao nhiêu ô (i, j) thỏa mãn Ai,j mod K = X. Yêu cầu: Hãy trả lời Q truy vấn của đề bài. Dữ liệu vào từ tệp văn bản ROBOT.INP: - Dòng đầu tiên chứa ba số nguyên dương N, M, Q, K (1 ≤ N, M ≤ 1000, 1 ≤ Q ≤ 105, 1 ≤ K ≤ 109). - Trong N dòng tiếp theo, dòng thứ i chứa M số nguyên dương biểu diễn bảng A (1 ≤ Ai,j ≤ 109) - Trong Q dòng tiếp theo, mồi dòng chứa một số tự nhiên X thể hiện truy vấn tương ứng. Kết quả ghi ra tệp văn bản ROBOT.OUT: - Gồm Q dòng, mỗi dòng chứa một số tự nhiên là kết quả của truy vấn tương ứng. Ràng buộc: - Có 20% số test tương ứng 20% số điểm có M = 1. - 20% số test tương ứng 20% số điểm có M = 2, Q ≤ 1000. - 30% số test tương ứng 30% số điểm có M, N, K ≤ 300. - 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm. Ví dụ: ROBOT.INP ROBOT.OUT GIẢI THÍCH 3 4 2 6 5 Ở lần lượt hai truy vấn, robot có thể đi như sau: 1 1 1 7 3 1 1 1 7 1 1 1 7 2 8 9 1 2 8 9 1 2 8 9 1 1 3 4 2 1 1 3 4 2 1 3 4 2 2 Bài 5 (3,0 điểm). Đoạn tốt Một đoạn thẳng trên trục số được biểu diễn bởi hai số L, R lần lượt là điểm đầu và điểm cuối của đoạn thẳng đó. Một tập hợp đẹp là tập hợp mà mỗi đoạn thẳng trong tập hợp đó có ít nhất 1 điểm chung với một đoạn khác trong tập. Tập hợp chỉ có 1 đoạn thẳng là tập hợp đẹp. Độ tốt của một tập hợp đẹp là số lượng đoạn thẳng trong tập hợp đó. Ví dụ: - Tập hợp {(1, 2)} là tập hợp đẹp có độ tốt là 1. - Tập hợp {(1, 5), (4, 7), (5, 8)} là tập hợp đẹp có độ tốt là 3. - Tập hợp {(1,4), (3, 5), (6, 8)} không là tập hợp đẹp. Có N đoạn thẳng được đánh số từ 1 đến N. Đoạn thẳng thứ i được biểu diễn bởi hai số nguyên Li và Ri. Người ta thực hiện như sau: Thêm lần lượt các đoạn thẳng theo thứ tự từ 1 đến N, quy tắc như sau: - Nếu đoạn (Li, Ri) có điểm chung với một tập hợp đẹp đã có thì thêm (Li, Ri) vào tập hợp DeThi.edu.vn