Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (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.HCM (Có đáp án chi tiết)

1. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn Bài 3: GIAIDAU.cpp Tóm tắt: cho một dãy a có n phần tử và q truy vấn. Mỗi truy vấn cho 2 số u, V (u < V). Với mỗi truy vấn hãy tìm cách chia đoạn con gồm các phần tử au, au+1, ... av thành 2 phần liên tiếp sao cho chênh lệch giữa tổng 2 phần là nhỏ nhất. Nghĩa là chọn vị trí í (u ≤ i ≤ V) sao cho |(au + au+i + . + ai) – (ai+1 + ai+2 + . + av)| là nhỏ nhất. 5 9 Giới hạn: 1 ≤ n, q ≤ 10 ,1 ≤ ai ≤ 10 Vét cạn: Để vét cạn thì rất đơn giản, ta chạy i từ u tới v - 1 và lấy min của |(au + au+i + . + ai) – (ai+1 + ai+2 + . + av)| là được. Để tính nhanh tổng 1 đoạn thì ta sử dụng prefix sum. Code: #include #define int long long using namespace std; const int MAXN=1e5; int a[MAXN+5],n,q,prefix[MAXN+5]; void solve() { int u,v; cin>>u>>v; int ans=1e18; for(int i=u;i<v;++i){ ans=min(ans,llabs((prefix[v]-prefix[i])-(prefix[i]-prefix[u-1]))); } cout<<ans<<'\n'; } signed main() { ios base::sync with stdio(0);cin.tie(0); cin>>n>>q; for(int i=1;i<=n;++i){ cin>>a[i]; prefix[i]=prefix[i-1]+a[i]; } while(q--) { solve(); } return 0; } DeThi.edu.vn
2. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn Tối ưu: Ta có: au + au+1 + . + ai = prefixi – prefixu-1 và ai+1 + ai+2 + . + av = prefixv — prefixi Viết lại biểu thức, ta cần tìm giá trị nhỏ nhất của |M| với: M = (prefixv - prefixi) - (prefixi - prefixu-1) = prefixu-1 + prefixv - 2. prefixi TH1: M ≥ 0 Dễ thấy để |M| bé nhất, mà prefixu-1 + prefixv là cố định nên là 2.prefixi phải lớn nhất! ⇒ prefixu-1 + prefixv ≥ 2. prefixi prefix prefix ⇒ prefix ≤ ―1 푣 i 2 prefix prefix Vậy M bé nhất khi prefix, lớn dần và càng tiến gần tới ―1 푣 2 ⇒ Để tìm được í thì ta thực hiện tìm kiếm nhị phân vị trí i lớn nhất thỏa mãn prefix prefix Prefix ≤ ―1 푣 i 2 Do ai > 1 nên prefixi-1 < prefixi, nghĩa là dãy prefix đã được sắp xếp tăng dần sẵn nên ta có thể thực hiện tìm kiếm nhị phân. TH2: M <0 Dễ thấy lúc này |M|= 2. prefix i - (prefixu-1 + prefixv), mà prefixu-1 + prefixv là cố định nên để |M| bé nhất thì là 2. prefixi phải bé nhất! ⇒ prefixu-1 + prefixv < 2. prefixi prefix prefix ⇒ prefix > ―1 푣 i 2 prefix prefix Vậy M bé nhất khi prefix nhỏ dần và càng tiến gần tới ―1 푣 i 2 ⇒ Để tìm được i thì ta thực hiện tìm kiếm nhị phân vị trí i nhỏ nhất thỏa mãn prefix prefix prefix > ―1 푣 i 2 Để tránh sử dụng 2 lần tìm kiếm nhị phân thì nhận thấy rằng giá trị ở 2 TH để có chung prefix prefix Vế phải là ―1 푣, chỉ khác mỗi dấu là ≤ và >. Nhận thấy rằng 2 dấu này 2 ngược nhau nên nếu tìm được i bé nhất thỏa: prefix prefix prefix > ―1 푣 i 2 thì ta phải tìm giá trị của i’ lớn nhất thỏa: prefix prefix prefix > ―1 푣 i’ 2 => i' = i - 1 (Do i là giá trị nhỏ nhất thỏa > thì i - 1 sẽ là giá trị lớn nhất thỏa dấu <) Sau đó ta lấy giá trị nhỏ nhất của 2 trường hợp là được. DeThi.edu.vn
3. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn Code: #include #define int long long using namespace std; const int MAXN=1e5; int a[MAXN+5],n,q,prefix[MAXN+5]; void solve() { int u,v; cin>>u>>v; int mid=(prefix[u-1]+prefix[v])/2; int idx=upper_bound(prefix+u,prefix+v+1,mid)-prefix; int ans1=llabs(prefix[u-1]+prefix[v]-2*prefix[idx]), ans2=llabs(prefix[u-1]+prefix[v]-2*prefix[idx-1]); cout<<min(ans1,ans2)<<'\n'; } signed main() { ios base::sync with stdio(0);cin.tie(0); cin>>n>>q; for(int i=1;i<=n;++i){ cin>>a[i]; prefix[i]=prefix[i-1]+a[i]; } while(q--) { solve(); } return 0; } DeThi.edu.vn
4. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (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 THÀNH PHỐ HỒ CHÍ MINH CẤP THÀNH PHỐ - NĂM HỌC 2023 – 2024 (Đề thi gồm 03 trang) MÔN: TIN HỌC Thời gian: 120 phút (không kể thời gian giao đề) Tổng quan bài thi Tên bài Tập tin chương trình Tập tin dữ liệu Tập tin kết quả ROBOT ROBOT. ROBOT.INP ROBOT.OUT DÃY CON DAYCON.* DAYCON.INP DAYCON.OUT SDIGIT SDIGIT.* SDIGIT.INP SDIGIT.OUT Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. Các tập tin chương trình lưu trong cùng một thư mục với tên thư mục là TIN . Ví dụ: thí sinh có số báo danh là 1234 thì tên thư mục là TIN 1234. Hãy lập trình giải 3 bài toán sau: Bài 1: ROBOT (7 điểm) Môt con ROBOT được làm bởi đội tuyển robot trường Hồng Bàng đang thực hiện nhiệm vụ trên một hành tinh xa xôi nào đó. Tuy nhiên do một cơn bão lớn đã làm hư bảng mạch của ROBOT, giờ đây ROBOT chỉ có thể đi qua phải a hoặc b ô hoặc đi lên c hoặc d ô theo sự điều khiển. Đội tuyển robot trường Hồng Bàng không biết có thể điều khiển robot đi từ ô trái dưới đến ô phải trên hay không và làm sao để có thể điều khiển ROBOT đi với số lần điều khiển là ít nhất. Yêu cầu: Hãy viết chương trình giúp đội tuyển robot trường Hồng Bàng tìm được số lần điều khiển ít nhất mà ROBOT cần để đến được đích. Nếu không đi được thì hãy xuất ra -1. Dữ liệu: Vào từ file văn bản ROBOT.INP gồm • Dòng thứ nhất chứa số nguyên N (1 <= N <= 106) • Dòng thứ hai chứa 2 số nguyên a và b • Dòng thứ ba chứa 2 số nguyên c và d Các số trên cùng 1 dòng thì cách nhau 1 khoảng trắng và (0 <= a, b, c, d <= 109) Kết quả: Ghi ra file văn bản ROBOT.OUT 1 số nguyên duy nhất là số lần điều khiển ít nhất để ROBOT có thể đến đích, nếu không được thì ghi ra -1. Ràng buộc: • 60% Subtask1: 1 <= N <= 10 • 90% Subtask2: 1 <= N <= 104 • 100% Subtask3: 1 <= N <= 106 Ví dụ 1: DeThi.edu.vn
5. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn ROBOT.INP ROBOT.OUT 5 3 2 3 4 5 Giải thích ví dụ 1: Ở lượt đầu robot đi qua phải 2 ô Ở lượt hai robot đi lên 4 ô Ở lượt ba robot đi qua phải 2 ô Ví dụ 2: ROBOT.INP ROBOT.OUT 5 -1 8 3 3 2 Giải thích ví dụ 2: Vì robot không thể đi qua phải được 8 ô vì (8 > 5) và không đi lên 3 ô được vì 5 % 3 ! = 0. Bài 2: DÃY CON (7 điểm) Trong giờ học toán Minh và đã được học một kiến thức mới là dãy con. Minh được thầy giao nhiệm vụ như sau: Cho dãy A có n phần tử, tìm số dãy con liên tiếp trong dãy A sao cho tổng của chúng không nhỏ hơn một số k. Yêu cầu: Các em hãy lập trình giúp Minh tìm ra số dãy con thõa nhiệm vụ của thầy dạy toán. Dữ liệu: Vào từ file văn bản DAYCON.INP - Dòng đầu là hai số n, k (k ≤ 109). 9 - Dòng sau chứa n số của dãy A. (1 ≤ Ai ≤ 10 ). Kết quả: Ghi ra file văn bản DAY CON.OUT - Số dãy con liên tiếp có tổng không nhỏ hơn k. Ràng buộc: - 30% Subtask1: 1 <= N <= 10 - 60% Subtask2: 1 <= N <= 104 DeThi.edu.vn
6. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn - 100% Subtask3: 1 <= N <= 105 DAYCON.INP DAYCON.OUT Giải thích 5 6 6 Có 6 dãy sau có tổng không nhỏ hơn 1 2 1 4 5 6: [1, 2, 1,4, 5]; [1, 2, 1, 4];/ [2, 1, 4]; [2, 1, 4, 5]; [1, 4, 5]; [4, 5]. Bài 3: Số SDIGIT (6 điểm) Minh đang nghiên cứu về số học thì thấy rất thích các số có tổng các chữ số là số nguyên tố. Minh gọi các số đó là SDIGIT. Một số có k chữ số thì gọi là số có độ dài k. Minh đang có nhiệm vụ đi tìm tất cả các số SDIGIT có độ dài từ l đến r. Vì số lượng số SDIGIT quá nhiều nên anh ấy không đếm nổi được. Yêu cầu: Hãy viết một chương trình giúp Minh biết từ độ dài l i đến ri có bao nhiêu số mà tổng các chữ số của chúng là 1 số nguyên tố. Dữ liệu: Vào từ file văn bản SDIGIT.INP - Dòng đầu là số q - số truy vấn cần thực hiện. - q dòng sau, dòng thứ i chứa 2 số li, ri. Kết quả: Ghi ra file văn bản SDIGIT.OUT - Mỗi dòng i là một đáp án cho truy vấn thứ i. Ràng buộc: - 80% số điểm của bài: 1 ≤ li, ri ≤ 6, q ≤ 10. - 100% số điểm của bài: 1 ≤ li, ri ≤ 250, q = 1. Ví dụ: SDIGIT.INP SDIGIT.OUT Giải thích: 2 4 Các số có độ dài 1 là 1 → 9. Trong đó số SDIGIT là: 1 1 37 2, 3, 5, 7. 1 2 Các số có độ dài 1 và 2 là 1 → 99. Trong đó số SDIGIT là: 2, 3, 5, 7, 11, 12, 14, 16, 20, ... 89, 92, 94, 98. -------------HẾT------------- DeThi.edu.vn
7. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn ĐÁP ÁN Bài 1: ROBOT (7 điểm) Code C++: #include #include #include using namespace std; int main() { ifstream infile("ROBOT.INP"); ofstream outfile("ROBOT.OUT"); int N, M, start_x, start_y; string commands; infile >> N >> M; infile >> start_x >> start_y; infile >> commands; int x = start_x; int y = start_y; for (char command : commands) { if (command == 'U') y++; else if (command == 'D') y--; else if (command == 'L') x--; else if (command == 'R') x++; // Kiểm tra biên giới if (x N || y M) break; } outfile << x << " " << y; infile.close(); outfile.close(); return 0; } Bài 2: DÃY CON (7 điểm) Code C++: #include #include #include #include DeThi.edu.vn
8. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn using namespace std; int main() { ifstream infile("DAYCON.INP"); ofstream outfile("DAYCON.OUT"); int N, K; infile >> N >> K; vector a(N); for (int i = 0; i < N; ++i) { infile >> a[i]; } int count = 0; for (int i = 0; i <= N - K; ++i) { bool hasDifferentElements = false; for (int j = i; j < i + K; ++j) { for (int k = j + 1; k < i + K; ++k) { if (a[j] != a[k]) { hasDifferentElements = true; break; } } if (hasDifferentElements) break; } if (hasDifferentElements) { count++; } } outfile << count; infile.close(); outfile.close(); return 0; } Bài 3: Số SDIGIT (6 điểm) Code C++: #include #include #include DeThi.edu.vn
9. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn using namespace std; int main() { ifstream infile("SDIGIT.INP"); ofstream outfile("SDIGIT.OUT"); int N; infile >> N; vector digitCount(10, 0); // Đếm số lần xuất hiện của từng chữ số từ 0 đến 9 int num; for (int i = 0; i < N; ++i) { infile >> num; while (num > 0) { int digit = num % 10; // Lấy chữ số cuối cùng digitCount[digit]++; num /= 10; // Bỏ chữ số cuối cùng } } // Tìm chữ số có số lần xuất hiện nhiều nhất int maxCount = 0; int maxDigit = 0; for (int i = 0; i < 10; ++i) { if (digitCount[i] > maxCount) { maxCount = digitCount[i]; maxDigit = i; } } outfile << maxDigit << " " << maxCount; infile.close(); outfile.close(); return 0; } DeThi.edu.vn
10. Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn ĐỀ SỐ 3 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ HỒ CHÍ MINH 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: 120 phút (Không tính thời gian phát đề) Tổng quan bài thi Tên bài Tập tin chương trình Tập tin dữ liệu Tập tin kết quả Trung Bình Cộng TBC.* TBC.INP TBC.OUT Mật Thư MATTHU.* MATTHU.INP MATTHU.OUT Xổ Số XOSO.* XOSO.INP XOSO.OUT Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. Các tập tin chương trình lưu trong cùng một thư mục với tên thư mục là TIN . Ví dụ: thí sinh có số báo danh là 1234 thì tên thư mục là TIN1234. Hãy lập trình giải 3 bài toán sau: Bài 1: Trung Bình Cộng (6 điểm) Tuấn thường hỗ trợ em An củng cố kiến thức bài học bằng cách cho em làm những bài luyện tập. Để ôn tập những phép tính cơ bản, Tuấn cho An bài toán tính trung bình cộng như sau. Cho một dãy số nguyên A có N phần tử, các phần tử được đánh số từ 1 đến N. An được yêu cầu tạo một dãy số nguyên B có N phần tử và phần tử thứ i của dãy B là trung bình cộng i số đầu tiên của dãy A. Ví dụ với dãy A là: 15, 25, -25, 25, 60 thì dãy B nếu được tạo đúng sẽ là: 15, 20, 5, 10, 20. An cũng thường thử thách anh Tuấn bằng những câu hỏi thú vị. Sau khi giải xong bài toán trung bình cộng của Tuấn, An liền đưa Tuấn đáp án là dãy số B và hỏi lại Tuấn xem anh có thể tạo lại dãy số A ban đầu từ dãy số B không. Yêu cầu: Hãy viết chương trình giúp Tuấn tìm dãy số A từ dãy số B. Dữ liệu: Vào từ file văn bản TBC.INP dòng đầu chứa một số nguyên N. Dòng thứ hai chứa 6 6 N số nguyên Bi (-10 < Bi < 10 ) lần lượt cho biết giá trị của N phần tử dãy B. Kết quả: Ghi ra file văn bản TBC.OUT trên một dòng N số nguyên lần lượt là N phần tử của dãy A. Có thể giả sử dữ liệu cho sẽ đảm bảo các giá trị phần tử dãy A là số nguyên. Ràng buộc: - 50% test ứng với 50% số điểm của bài có N ≤ 5 - 50% test ứng với 50% số điểm của bài có 5 ≤ N ≤ 100 000 DeThi.edu.vn