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

 Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
 ĐỀ SỐ 1
 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 2024 – 2025
 (Đề thi gồm 3 trang) MÔN: TIN HỌC
 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ả
 SẮP XẾP SAPXEP.* SAPXEP.INP SAPXEP.OUT
 KHU VỰC KHUVUC.* KHUVUC.INP KHUVUC.OUT
 GIẢI ĐẤU GIAIDAU.* GIAIDAU.INP GIAIDAU.OUT
Dấu * được thay thế bởi PAS hoặc CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương 
ứng là Pascal hoặc C++ hoặc PYTHON. 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 và giải 3 bài toán sau:
Bài 1. Sắp xếp (7 điểm)
Sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán đơn giản và dễ hiểu. Thuật toán 
sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử bằng cách liên tục lập lại việc so sánh hai phần 
tử liền kề và hoán đổi vị trí của chúng nếu chung không theo thứ tự mong muốn. Quá trình 
này được lặp lại cho đến khi toàn bộ dãy đã được sắp xếp hoàn chỉnh.
Yêu cầu: Cho một dãy gồm n phần tử hãy viết chương trình đêm số lần hoán đổi vị trí các 
phần tử theo thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần.
Dữ liệu: Đọc từ file SAPXEP.INP gồm:
 5
- Dòng thứ nhất chứa số nguyên dương (1 ≤ ai ≤ 2.10 )
 9
- Dòng thứ hai chứa số nguyên dương cách nhau bằng khoảng trắng ai,... ,an (1 ≤ ai ≤ 10 )
Kết quả: Ghi ra file SAPXEP.OUT một số nguyên duy nhất cho biết số lần hoán đổi vị trí 
các phần tử theo thuật toán sắp xếp trên.
Ràng buộc:
- 80% số điểm bài thi: 1 ≤ n ≤ 103
- 100% số điểm bài thi: 1 ≤ n ≤ 2.105
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
Ví dụ:
 SAPXEP.INP SAPXEP.OUT Giải thích
4 3 Theo thuật toán sắp xếp nổi bọt có 3 lần 
3 2 1 4 hoán đổi vị trí các phần tử gồm:
 - Hoán đổi vị trí hai phần tử (3, 2), dãy phần 
 tử 2 3 1 4
 - Hoán đổi vị trí hai phần tử (3, 1), dãy phần 
 tử 2 1 3 4
 - Hoán đổi vị trí hai phần tử (2, 1), dãy phần 
 tử 1 2 3 4
Bài 2. Khu vực (6,5 điểm)
Vùng đất thần tiên AlphaLand rộng lớn được chia thành nhiều khu vực khác nhau. Các khu 
vực được đánh số 1, 2, 3...
Việc phân chia khu vực sinh sống, lao động,vui chơi cho người dân cũng khá kì lạ. Mỗi 
người dân được cấp một cái thẻ chứa một con số và họ chỉ được phép ra vào khu vực có số 
thứ tự là ước số của số thẻ. Các số trên thẻ của người dân được phép trùng nhau.
Mỗi dịp lễ hội thường niên, trưởng lão sẽ tập trung tât cả người dân về một khu vực để tổ 
chức tiệc mừng. Năm nay, ông quyết định mở tiệc tại khu vực mà tất cả người dân được 
phép ra vào khu vực đó có số thứ tự lớn nhất.
Nhận thấy rằng có một số thẻ đã cấp cho người dân làm ảnh hưởng đến việc chọn khu vực 
như trên, ông quyết định đổi cho một trong số họ cái thẻ mới để chọn được khu vực tổ chức 
tiệc có số thứ tự lớn hơn.
Yêu cầu: Cho danh sách n thẻ với các số tương ứng. Hãy viết chương trình tìm khu vực mà 
tất cả người dân được phép ra vào và khu vực đó có số thứ tự lớn nhất. Lưu ý, việc xác định 
khu vực thực hiện sau khi người dân được đổi thẻ.
Dữ liệu: Đọc từ file KHUVUC.INP gồm:
- Dòng thứ nhất chứa số nguyên dương n (1 ≤ n ≤ 105)
- Dòng thứ hai chứa số nguyên dương cách nhau bằng khoảng trắng ai,,a1,...,an (1 < ai < 
109)
Kết quả: Ghi file KHUCVUC.OUT một số nguyên duy nhất cho biết số thứ tự của khu vực 
tìm được theo yêu cầu trên
Ràng buộc:
- 40% số điểm bài thi: 1 ≤ n ≤ 100, 1 ≤ ai ≤ 100
- 80% số điểm bài thi: 1 ≤ n ≤ 103
- 100% số điểm bài thi: 1 ≤ n ≤ 105
Ví dụ:
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
 KHUVUC.INP KHUVUC.OUT Giải thích
3 4 Thẻ số 4 đến được các khu vực {1, 2, 4}
4 2 8 Thẻ số 2 đến được các khu vực {1, 2}
 Thẻ số 8 đến được các khu vực {1, 2, 4, 8}
 Ban đầu khu vực dự kiến chọn là 2. Có thể đổi số thẻ 
 2 thành số 4 với các thẻ 4, 4, 8 chọn khu vực có số 
 thứ tự lớn hơn 4.
Bài 3: Giải đấu (6,5 điểm)
Trong mùa hè năm nay, công ty game AlphaNet sẽ tổ chức giải đấu trực tuyến cho tất cả 
game thủ của mình. Danh sách tên các game thủ được đánh số thứ tự từ 1 đến n. Mỗi game 
thủ có một ranking (thứ hạng trong game) khác nhau. Trước khi bắt đầu giải, ban tổ chức sẽ 
cho các game thủ giao lưu với nhau thông qua q lượt đấu đồng đội bằng cách ghép đôi ngẫu 
nhiên ở mỗi lượt đấu, ban tổ chức thực hiện ghép đôi ngẫu như sau:
- Cho hệ thống sinh ngẫu hiện hai số u, v (u < v) để xác định nhóm các thành viên được chọn 
tham gia là các game thủ trong danh sách có số thứ tự từ u đến v.
- Tiếp theo ban tổ chức sẽ chia nhóm các thành viên được chọn thành 2 đội tương đối đều 
nhau về ranking.
Ranking của 1 đội là tổng ranking của các thành viên trong đội. Do đó, ban tổ chức phải tính 
toán để xác định 1 vị trí sao cho đội lệch ranking giữa 2 đội là nhỏ nhất và các thành viên 
trong đội phải có số thứ tự liên tiếp nhau trong danh sách (không quan trọng số lượng thành 
viên trong đội).
Yêu cầu: Cho một dãy n game thử với ranking tương ứng và q cặp số nguyên u,v được hệ 
thông sinh ngẫu nhiên, hãy viết chương trình cho biết độ lệch ranking nhỏ nhất cuả từng lượt 
sau khi ban tổ chức thực hiện ghép đội ngẫu nhiên.
Dữ liệu: Đọc từ file GIAIDAU.INP gồm:
- Dòng thứ nhất chứa hai số nguyên dương n, q (1 ≤ n, q ≤ 105)
- Dòng thứ hai chứa n số nguyên dương cách nhau bằng khoảng trắng a1,...,ai,...,an (1 ≤ ai ≤ 
109). Trên q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v (1 ≤ u, u ≤ v) các số 
trên cùng một dòng cách nhau bằng khoảng trống. 
Kết quả: Ghi ra file GIAIDAU.OUT gồm: q dòng, dòng thứ i là kết quả tìm được ở lượt thứ 
i.
Rằng buộc:
- 40% số điểm bài thi: 1 ≤ n, q ≤ 100
- 80% số điểm bài thi: 1 ≤ n ≤ 103, 1 ≤ q ≤ 104
- 100% số điểm bài thi: 1 ≤ q ≤ 105
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
Ví dụ:
 GIAIDAU.INP GIAIDAU.OUT Giải thích
6 2 1 Ở lượt thứ 1, ranking của các gmae thủ có số thứ tự 
4 2 2 1 5 6 0 từ 1 đến 4 là: 4 2 2 1 ta có thể chia được như sau:
1 4 - {4} và {2, 2, 1} độ lệchranking giữa 2 đội là 1
2 5 - {4, 2} và {2, 1} độ lệchranking giữa 2 đội là 3
 - {4, 2, 2} và {1} độ lệchranking giữa 2 đội là 7
 Ban tổ chức sẽ chia đội theo cách chia đầu tiên với 
 độ lệch ranking nhỏ nhất là 1
 Ở lượt thứ 2, ranking của các gmae thủ có số 2 đến 5 
 là: 2 2 1 5
 Ban tổ chức sẽ chia đội thành {2, 2, 1} và {5} với độ 
 lệch ranking nhỏ nhất là 0
 -------------HẾT-------------
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
 ĐÁP ÁN
Bài 1: SAPXEP.cpp
Tóm tắt: cho một dãy a gồm n phần tử, ta thực hiện sắp xế'p nổi bọt (bubble sort) lên dãy 
đó. Hãy đếm xem có bao nhiêu cặp phần tử bị đổi chỗ trong quá trình sắp xếp.
 5 9
Giới hạn: 1 < n < 2.10 ,1 < ai < 10
Vét cạn:
Để vét cạn thì tương đối dễ, ta chỉ cần thực hiện bubble sort xong đếm xem có bao nhiêu cặp 
vị trí i, j thỏa ai > aj là được.
Code:
#include 
using namespace std;
// An optimized version of Bubble Sort
int bubblesort(vector& arr ) {
 int n = arr.size();
 bool swapped;
 long long ans=0;
 for (int i = 0; i < n - 1; i + +) { swapped = false;
 for (int j = 0; j < n - i - 1; j++) {
 if (ar r [j] > arr[j + 1]) {
 swap(arr[j], arr [ j + 1]);
 swapp ed = true;
 ++ans;
 }
 }
 // If no two elements were swapped, then break if (1 swapped)
 break;
 }
 return ans;
}
int main() {
 ios base::sync with stdio(0);cin. tie(0) ;
 int n;
 cin>>n;
 vector arr(n);
 for(int i=0;i>arr[i] ;
 }
 cout << bubbleSort (arr ) << ' \n' ;
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
 return 0;
}
Tối ưu:
Nhận thấy rằng khi sắp xếp xong thì các phần tử được sắp xếp tăng dần, nghĩa là nếu ta đang 
ở vị trí i thì trong các phần tử ai+1, ai+2,, an, số lần hoán đổi mà có phần tử u, sẽ chính là số 
phần tử trong đó mà bé hơn ai. Nghĩa là với mỗi u, mình sẽ đếm xem có bao nhiêu vị trí j 
thỏa mãn ai > aj và i < j ≤ n. Trong lúc thi thì mình nghĩ ngược lại, giả sử phần tử ta đang xét 
hiện tại là aj, thì ta sẽ đếm xem có bao nhiêu i thỏa mãn aj < ai, và 1 < i < j. Để làm điều đó 
thì ta sẽ dùng mảng đánh dấu: gọi markk là số lượng phần tử trong mảng a có giá trị bằng k. 
Lúc này số phần tử bé hơn ai, sẽ là mark1 + mark2 +  + mark ai-1. Sau đó ta sẽ cập nhật lại 
giá trị của markai = markai + 1. Dễ thấy đây chính là bài toán ứng dụng cơ bản của Fenwick 
 9 5
tree. Tuy nhiên do ai có thể lên tới 10 mà n chỉ lên tới 2.10 nên ta cần phải nén mảng lại để 
giữ nguyên độ lớn của các phần tử. 
Code:
#include
ttdefine int long long
using namespace std;
const int MAXN=2e5;
int a[MAXN+5],n;
int temp[MAXN+5];
void compress(){
 for(int i=l;i<=n;++i) 
 { temp[i]=a[i] ;
 }
 so rt(temp+1,temp+n+1) ;
 for(int i=l;i<=n;++i) 
 { a[i]=lower bound(temp+1,temp+n+1,a[i ])-temp;
 }
}
int BIT[MAXN+5];
void update(int idx,int value){
 while(idx<=n){
 BIT[idx]+=value; 
 idx+=idx&(-idx) ;
 }
}
int get(int idx) {
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
 int res=0;
 while(idx>0){
 res+=BIT[idx]; 
 idx-=idx&(-idx) ;
 }
 return res;
}
void solve(){
 int ans=0;
 for(int i=l;i<=n;++i) { ans+=get(n)-get(a[i]) ; update(a[i], 1);
 }
 cout << ans << '\n' ;
}
signed main(){
 ios base::sync with stdio(0);cin.tie (0); 
 cin >> n;
 for(int i=l;i<=n;++i) 
 { cin >> a[i] ;
 }
 compress (); 
 solve ();
 return 0;
}
Bài 2: KHUVUC.cpp
Tóm tắt: Cho một dãy a có n phần tử. Hãy thay đổi giá trị của 1 phần tử bất kì sao cho 
ƯCLN của dãy sau khi thay đổi là lớn nhất.
 5 9 
Giới hạn: 1 ≤ n ≤ 10 ,1 ≤ ai ≤ 10
Vét cạn:
Nhận thấy rằng việc thay đổi phần tử ai tương đương với việc loại bỏ phần tử đó ra khỏi dãy, 
sau đó thêm một phần tử khác vào. Mà phần tử khác đó khi thêm vào thì để ƯCLN còn lại 
lớn nhất thì nó phải là bội của ƯCLN của n - 1 phần tử còn lại sau khi xóa phần tử cũ đi. Vậy 
ta đưa về bài toán: loại bỏ 1 phần tử sao cho ƯCLN của n - 1 phần tử còn lại của dãy là lớn 
nhất. Để vét cạn thì cũng khá đơn giản, đó chính là tại mỗi vị trí ta thử loại bỏ phần tử đó đi 
và tính ƯCLN của dãy. 
Code:
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
#include
#define int long long
using namespace std;
const int MAXN=le5;
vectora;
int n;
int gcd(vectorarr,int pop idx) {
 an. erase (begin(arr) +pop_idx) ;
 if(arr.empty())return 0;
 int res=arr[0] ;
 for(int element:arr){ res = gcd(res,element);
 }
 return res;
}
void solve(){
 int ans=0;
 for(int 1=0;i<n;++i) {
 ans=max(ans, gcd( a, i) ) ;
 } cout«ans<<' \n' ;
}
signed main(){
 ios_base::sync_with_stdio(0);cin.tie(0); cm>>n;
 a.resize(n);
 for(int i=0;i<n;++i){ cin»a [1] ;
 }
 solve () ;
 return 0;
}
Tối ưu:
Gọi lefti là gcd (a1, a2,..., ai), và righti là gcd (ai, ai+1,..., an)
Dễ thấy rằng sau khi loại bỏ phần tử tại vị trí í thì ƯCLN của các phần tử còn lại là gcd (lefti-
1, righti+1). Vậy ta chỉ cần 1 vòng lặp duyệt qua dãy và cập nhật giá trị lớn nhất là được.
Code:
#include
#define left sussy
#define right baka
 DeThiTinHoc.net Bộ 16 Đề thi HSG Tin học Lớp 9 TP.HCM (Có đáp án) - DeThiTinHoc.net
#define int long long
using namespace std;
const int MAXN=1e5;
int a[MAXN+5],n,left[MAXN+5],right[MAXN+5];
void compute() {
 left[1]=a[1];
 for(int i=2;i<=n;++i){
 left[i]= gcd(left[i-1],a[i]);
 }
 right[n]=a[n];
 for(int i=n-1;i>=1;--i){
 right[i]= gcd(right[i+1],a[i]);
 }
}
void solve() {
 compute();
 int ans=0;
 for(int i=1;i<=n;++i){
 ans=max(ans, gcd(left[i-1],right[i+1]));
 }
 cout<<ans<<'\n';
}
signed main() {
 ios_base::sync_with_stdio(0);cin.tie(0);
 cin>>n;
 for(int i=1;i<=n;++i){
 cin>>a[i];
 }
 solve();
 return 0;
}
 DeThiTinHoc.net