Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án)

 Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
 ĐỀ SỐ 1
SỞ GIÁO DỤC & ĐÀO TẠO HÀ NỘI KỲ THI CHỌN HỌC SINH GIỎI THÀNH 
 PHỐ LỚP 9 CẤP THCS
 ĐỀ CHÍNH THỨC NĂM HỌC 2024-2025
 (Đề thi gồm 04 trang) Môn thi: TIN HỌC
 Thời gian: 150 phút (không kể thời gian giao đề)
 TỔNG QUAN BÀI THI
 Tên file chương Tên file kết quả 
STT Tên bài Tên file dữ liệu vào Điểm
 trình ra
Bài I Cắt hình CATHINH.* CATHINH.INP CATHINH.OUT 5,0
 Mạch MACHDNA* ∗
Bài II MACHDNA.INP MACHDNA.OUT 5,0
 DNA
Bài 
 Dây đèn DAYDEN.* DAYDEN.INP DAYDEN.OUT 4,0
III
Bài 
 Trò chơi TROCHOI.* TROCHOI.INP TROCHOI.OUT 3,0
IV
 Mua 
Bài V MUAHANG.* MUAHANG.INP MUAHANG.OUT 3,0
 hàng
Chú ý: Dấu * đırơ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. Cắt hình (5,0 điểm)
Cho một tờ giấy hình chữ nhật kích thước M(cm) x N(cm) và một số tự nhiên K.
Yêu cầu: Nếu cắt những hình vuông có kích thước K(cm) x K(cm) từ tờ giấy này thì diện 
tích còn lại nhỏ nhất là bao nhiêu cm2 ?
Dữ liệu vào từ file văn bản CATHINH.INP: Gồm ba số tự nhiên M, N, K lần lượt mỗi số 
trên một dòng (1 ≤ M, N, K ≤ 109).
Kết quả ghi ra file văn bản CATHINH.OUT: Một số nguyên duy nhất là kết quả của bài 
toán.
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
Ví dụ:
 CATHINH.INP CATHINH.OUT GIẢI THÍCH
8 20
7
3
Bài II. Mạch DNA (5,0 điểm)
Cho mạch mã gốc DNA bốn loại nucleotide A, T, G, C. Để tiết kiệm bộ nhớ, mạch mã gốc 
đã được nén lại thành một chuỗi S gồm các cặp là số lần xuất hiện liên tiếp nucleotide và loại 
nucleotide tương úng.
Ví dụ: Mạch mã gốc AAACAATGGGGA nén thành 3A1C2A1T4G1A.
Các nucleotide ở hai mạch của phân tử DNA liên kết với nhau theo nguyên tắc bổ sung, 
trong đó liên kết với T, G liên kết với C. Do vậy, nếu biết trình tự nucleotide trên một mạch 
có thể suy ra trình tự của mạch còn lại.
Ví dụ: Một đoạn phân tử DNA ở sinh vật nhân thực có trình tự nucleotide trên mạch mã gốc 
là. Trình tư nucleotide trên mạch bổ sung của đoạn DNA này là:
Yêu cầu: Cho một chuỗi ký tự mô tả mạch mã gốc DNA sau khi đã nén. Hãy lập trình xác 
định mạch bổ sung của mạch mã góc sau khi giải nén.
Dữ liệu vào từ file văn bản MACHDNA.INP: Một chuỗi S có độ dài không vượt quá 1000. 
Dữ liệu đảm bảo chuổi sau khi giải nén có độ dài không vượt quá 105.
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
Kết quả ghi ra file văn bản MACHDNA.OUT: Chuỗi ký tự là mạch bổ sung của mạch mã 
gốc sau khi giải nén.
Ví dụ:
 MACHDNA.INP MACHDNA.OUT GIẢI THÍCH
 5A2G1A11T1C TTTTTCCTAAAAAAAAAAAG Mạch mã gốc sau khi giải nén là: 
 AAAAAGGATTTTTTTTTTTC.
 Mạch bổ sung là: 
 TTTTTCCTAAAAAAAAAAAG.
Ràng buộc:
- Có 20% số test ứng với 20% số điểm của bài thỏa mãn: Độ dài chuỗi S là 2, trong đó ký tự 
đầu tiên là chữ số, ký tự thứ hai là một trong 4 chữ cái A, T, G, C;
- Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: Có duy nhất một loại 
nucleotide;
- Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: Số lần xuất hiện liên tiếp 
nucleotide A, T, G, C nhỏ hơn 10;
- 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.
Bài III. Dây đèn (4,0 điểm)
Để trang trí Tết, Nam treo một dây đèn gồm N bóng đèn, được đánh số từ 1 đến N, từ trái 
sang phải. Mỗi bóng đèn khi bật sẽ có hai màu vàng hoặc đỏ. Dây đèn được nhúng một mã 
lệnh cho phép nhận một số tự nhiên X. Khi đó, màu của bóng đèn thứ X và các bóng đèn 
cách bóng đèn thứ X không quá K bóng đèn sẽ đều đổi từ vàng thành đỏ hoặc ngược lại.
Ban đầu các bóng đèn đều có màu vàng. Để dây đèn trông đẹp mắt, Nam đã lập trình để điều 
khiển màu của các bóng đèn. Chương trình của Nam có M dòng lệnh, mỗi dòng lệnh tương 
ứng với một lần gọi mã lệnh của dây đèn. Vì số lượng bóng đèn quá lớn, sau khi lập trình 
xong, Nam muốn kiểm tra ngẫu nhiên màu một số bóng đèn xem có đúng như ý tưởng ban 
đầu không.
Yêu cầu: Cho các số tự nhiên X là tham số của M dòng lệnh trong chương trình của Nam. 
Hãy lập trình để trả lời Q câu hỏi tương ứng với các lần kiểm tra của Nam. Biết rằng mỗi câu 
hỏi chứa một số nguyên dương P để xác định xem bóng đèn thứ P trong dây đèn có màu 
vàng hay đỏ.
Dữ liệu vào từ file văn bản DAYDEN.INP:
- Dòng đầu tiên gồm bốn số nguyên dương lần lượt là: M, N, Q, K (1 ≤ N ≤ 109 ; 1 ≤ M ≤ 
105 ; 1 ≤ Q ≤ 105 ; 0 ≤ K ≤ N);
- Dòng thứ hai gồm M số nguyên dương Xi mô tả tham số của lệnh thứ i (1 ≤ Xi ≤ N);
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
- Dòng thứ ba gồm Q số nguyên dương Pi mô tả câu hỏi thứ i (1 ≤ Pi ≤ N).
Kết quả ghi ra file văn bản DAYDEN.OUT: Gồm Q dòng, dòng thứ là câu trả lời cho câu 
hỏi thứ i. Nếu bóng đèn tại vị trí Pi đang có màu vàng thì ghi ra ký tự " V ", ngược lại ghi ra 
ký tự " D ".
Ví dụ:
DAYDEN.INP DAYDEN.OUT GIẢI THÍCH
7 2 4 1 D - Sau lần gọi mã lệnh thứ nhất, các bóng trong dây đèn 
3 5 V có màu là: V, D, D, D, V, V, V;
2 7 4 5 V - Sau lần gọi mã lệnh thứ hai, các bóng trong dây đèn 
 D có màu là: V, D, D, V, D, D, V;
Ràng buộc:
- Có 60% số test ứng với 60% số điểm của bài thoả mãn: N, M, Q ≤ 103;
- 20% số test khác ứng với 20% số điểm của bài thoả mãn: N, M ≤ 105;
- 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.
Bài IV. Trò chơi (3,0 điểm)
Cho một bảng vuông kích thước N x N, N là số lẻ. Các hàng của bảng được đánh số từ 1 tới 
N, từ trên xuống dưới; các cột của bảng được đánh số từ 1 tới N, từ trái sang phải. Ban đầu, 
các số từ 1 đến N2 được ghi vào bảng này lần lượt từ trái sang phải, từ trên xuống dưới. Khi 
N = 5 thì bàng vuông sẽ có dạng như Hình 1.
 1 2 3 4 5
 1 1 2 3 4 5
 2 6 7 8 9 10
 3 11 12 13 14 15
 4 16 17 18 19 20
 5 21 22 23 24 25
 Hình 1
Luật chơi: Có Q lượt chơi, mỗi lượt chơi quản trò sẽ cấp cho người chơi thông tin là ba số 
nguyên P, X, Y (1 ≤ P ≤ N2 ; 1 ≤ X, Y ≤ N). Người chơi cần đưa số nguyên P đến vị trí hàng 
X cột Y với số lần dịch bảng nhỏ nhất bằng cách sau:
- Dịch các số trên hàng chứa số P sang phải hoặc sang trái một ô theo vòng tròn cho đến khi 
số P nằm trên cột Y;
- Dịch các số trên cột Y lên trên hoặc xuống dưới một ô theo vòng tròn cho đến khi số P nằm 
trên hàng X;
- Mỗi thao tác dịch hàng hoặc cột như trên được tính là một lần dịch bàng. Bảng đầu tiên của 
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
lượt chơi sau chính là bảng kết thúc của lượt chơi trước.
Ví dụ: Xét bảng vuông 5 x 5, cần dịch số 17 trên bảng ban đầu đến vị trí hàng 2 cột 5. Để số 
lần dịch bảng nhỏ nhất thực hiện như Hình 2.
 Bảng ban đầu – Lượt 1 Lần 1 – Dịch sang trái Lần 2 – Dịch sang trái
 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
 6 7 8 9 10 6 7 8 9 10 6 7 8 9 10
 11 12 13 14 15 11 12 13 14 15 11 12 13 14 15
 16 17 18 19 20 17 18 19 20 16 18 19 20 16 17
 21 22 23 24 25 21 22 23 24 25 21 22 23 24 25
 Lần 3 – Dịch lên trên Lần 4 – Dịch lên trên
 1 2 3 4 10 1 2 3 4 15
 6 7 8 9 15 6 7 8 9 17
 11 12 13 14 17 11 12 13 14 25
 18 19 20 16 25 18 19 20 16 5
 21 22 23 24 5 21 22 23 24 10
 Hình 2
Yêu cầu: Cho thông tin của Q lượt chơi. Hãy lập trình đưa ra số lần dịch bảng nhỏ nhất tìm 
được tương ứng với mỗi lượt.
Dữ liệu vào từ file văn bản TROCHOI.INP:
- Dòng đầu tiên chứa hai số nguyên dương N, Q (1 ≤ N < 30000 ; 1 ≤ Q ≤ 2000);
- Q dòng sau, mỗi dòng chứa ba số nguyên dương P, X, Y (1 ≤ P ≤ N2 ; 1 ≤ X, Y ≤ N) mô tả 
thông tin của một lượt chơi.
Kết quả ghi ra file văn bản TROCHOI.OUT: Gồm 푄 dòng, dòng thứ 푖 tương úng là số lần 
dịch bảng nhỏ nhất tìm được trong lượt chơi thứ 푖.
Ví dụ:
TROCHOI.INP TROCHOI.OUT GIẢI THÍCH
5 3 4 - Lượt chơi đầu tiên được mô tả bởi Hình 2;
17 2 5 2 - Lượt chơi thứ hai thực hiện 2 lần dịch bảng như sau: 
5 4 2 4
18 1 1
 - Lượt chơi thứ ba thực hiện 2 lần dịch hàng 4 sang 
 trái và 2 lần dịch cột 1 xuống dưới.
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
Ràng buộc:
- Có 40% số test ứng với 40% số điểm của bài thoả mãn: N < 100 ; Q ≤ 100;
- 40% số test khác úng với 40% số điểm của bài thoả mãn: N < 1500 ; Q ≤ 1500;
- 20 % số test còn lại ưng với 20 % số điểm không có ràng buộc gì thêm.
Bài V. Mua hàng (3,0 điểm)
An đi mua M sản phẩm khác nhau, các sản phẩm được đánh số từ 1 đến M. Ở chợ có N quầy 
hàng xếp thành hàng ngang được đánh số từ 1 đến N, từ trái sang phải. Quầy hàng thứ i chỉ 
bán một loại sản phẩm duy nhất là Ai (1 ≤ Ai ≤ M) và với mỗi sản phẩm trong M sản phẩm 
luôn tồn tại it nhất một quầy hàng bán sản phẩm loại đó. Thời gian để An mua sản phẩm tại 
quầy hàng thứ I là Ti phút. Thời gian để di chuyển giữa hai quầy hàng liền kề là 1 phút.
Yêu cầu: Tìm cách mua hàng sao cho
- Mua đủ M sản phẩm theo đúng thứ tự 1, 2, 3,, M. Có thể bắt đầu từ một quầy hàng bất kì 
bán sản phẩm 1;
- Thời gian tính từ lúc bắt đầu mua sản phẩm 1 đến khi mua xong sản phẩm M là nhỏ nhất;
Dữ liệu vào từ file văn bản MUAHANG.INP:
- Dòng đầu tiên gồm hai số nguyên dương N, M (1 ≤ M ≤ N ≤ 105);
- Dòng thứ hai gồm N số nguyên dương A1, A2,, AN (1 ≤ Ai ≤ M ; 1 ≤ i ≤ N). Dữ liệu đảm 
bảo các số từ 1 đến M xuất hiện ít nhất một lần;
 9
- Dòng thứ ba gồm N số nguyên dương T1, T2,, TN (1 ≤ Ti ≤ 10 ; 1 ≤ i ≤ N). 
Kết quả ghi ra file văn bản MUAHANG.OUT: Một số nguyên duy nhất là số phút nhỏ 
nhất để An mua M sản phẩm theo yêu cầu đề bài.
Ví dụ:
MUAHANG.INP MUAHANG.OUT GIẢI THÍCH
5 2 11 Cách mua sao cho tổng số phút nhỏ nhất là:
1 2 1 1 2 - Mua sản phẩm 1 ở quầy hàng thứ 3 mất 6 phút;
5 10 6 8 3 - Di chuyển sang quầy hàng thứ 5 mất 2 phút;
 - Mua sản phẩm 2 ở quầy hàng thứ 5 mất 3 phút; 
 Tổng số phút là: 6 + 2 + 3 = 11
Ràng buộc:
- Có 10% số test ứng với 10% số điểm của bài thoả mãn: M = 1;
- 30% số test khác úng với 30% số điểm của bài thoả mãn: M = N;
- 30% số test khác úng với 30% số điểm của bài thoả mãn: N ≤ 2000;
- 30% số test còn lại úng với 30% số điểm không có ràng buộc gì thêm.
 ----------HẾT----------
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
 ĐÁP ÁN
Bài I. Cắt hình (5,0 điểm)
#include // Để nhập xuất dữ liệu
int main() {
 // Chuyển hướng nhập xuất từ console sang file theo yêu cầu của đề bài
 freopen("CATHINH.INP", "r", stdin); // Mở file input
 freopen("CATHINH.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);
 long long M, N, K; // Khai báo các biến với kiểu long long để tránh tràn số
 std::cin >> M >> N >> K;
 // Tính số lượng hình vuông K x K có thể cắt được theo chiều M
 long long num_M = M / K;
 // Tính số lượng hình vuông K x K có thể cắt được theo chiều N
 long long num_N = N / K;
 // Tổng số hình vuông K x K có thể cắt được
 long long total_squares = num_M * num_N;
 // Diện tích mỗi hình vuông K x K
 long long square_area = K * K;
 // Tổng diện tích bị cắt
 long long cut_area = total_squares * square_area;
 // Diện tích ban đầu của tờ giấy
 long long initial_area = M * N;
 // Diện tích còn lại nhỏ nhất
 long long remaining_area = initial_area - cut_area;
 // In kết quả ra file output
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
 std::cout << remaining_area << std::endl;
 return 0;
}
Bài II. Mạch DNA (5,0 điểm)
#include // Để nhập xuất dữ liệu
#include // Để làm việc với chuỗi
#include // Có thể dùng nếu muốn lưu trữ tạm thời các cặp (count, char), nhưng 
không cần thiết
#include // Để sử dụng isdigit()
int main() {
 // Chuyển hướng nhập xuất từ console sang file theo yêu cầu của đề bài
 freopen("MACHDNA.INP", "r", stdin); // Mở file input
 freopen("MACHDNA.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);
 std::string s_compressed; // Chuỗi DNA đã nén
 std::cin >> s_compressed;
 std::string s_decompressed = ""; // Chuỗi DNA gốc sau khi giải nén
 int i = 0; // Biến dùng để duyệt qua chuỗi nén
 while (i < s_compressed.length()) {
 int count = 0;
 // Đọc số lượng lặp lại (có thể là số có nhiều chữ số)
 while (i < s_compressed.length() && std::isdigit(s_compressed[i])) {
 count = count * 10 + (s_compressed[i] - '0');
 i++;
 }
 // Ký tự nucleotide cần lặp lại
 char char_to_repeat = s_compressed[i];
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.Hà Nội (Có đáp án) - DeThiTinHoc.net
 i++; // Di chuyển con trỏ tới ký tự tiếp theo sau nucleotide
 // Thêm ký tự vào chuỗi giải nén 'count' lần
 for (int j = 0; j < count; ++j) {
 s_decompressed += char_to_repeat;
 }
 }
 // In chuỗi DNA gốc ra file output
 std::cout << s_decompressed << std::endl;
 return 0;
}
Bài III. Dây đèn (4,0 điểm)
#include // Để nhập xuất dữ liệu
#include // Để sử dụng std::vector
#include // Để sử dụng std::map cho sweep line
#include // Để sử dụng std::min, std::max, 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("DAYDEN.INP", "r", stdin); // Mở file input
 freopen("DAYDEN.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);
 long long N, K;
 int M, Q;
 std::cin >> N >> M >> Q >> K; // Đọc N, M, Q, K
 // Map để lưu trữ các sự kiện thay đổi trạng thái (sweep line points)
 // Key: vị trí bóng đèn, Value: số lần lật thay đổi tại vị trí đó
 std::map changes;
 // Xử lý M lệnh điều khiển đèn
 DeThiTinHoc.net