HSG lớp 9 TP. Hồ Chí Minh 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ HỒ CHÍ MINH ĐỀ THEO TRÍ NHỚ CỦA ĐỘI TUYỂN CỦ CHI
(Đề thi gồm 3 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Năm học 2024 - 2025
Môn: Tin học - Ngày thi: 14/03/2025
Thời gian làm bài: 120 phút (không tính thời gian phát đề)

---

Chú ý

Đây là đề được đội tuyển Củ Chi ghi lại theo trí nhớ sau kỳ thi, không phải bản đề chính thức, nên một số chi tiết (ràng buộc, ví dụ) có thể chưa chính xác hoàn toàn.

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<số báo danh>. 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 chúng 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:

• Dòng thứ nhất chứa số nguyên dương n (1 ≤ n ≤ 2.10⁵)
• Dòng thứ hai chứa n số nguyên dương cách nhau bằng khoảng trắng a₁, …, aᵢ, …, aₙ (1 ≤ aᵢ ≤ 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 ≤ 10³
• 100% số điểm bài thi: 1 ≤ n ≤ 2.10⁵

Ví dụ:

SAPXEP.INP	SAPXEP.OUT	Giải thích
4 3 2 1 4	3	Theo thuật toán sắp xếp nổi bọt có 3 lần 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 ≤ 10⁵)
• Dòng thứ hai chứa n số nguyên dương cách nhau bằng khoảng trắng a₁, …, aᵢ, …, aₙ (1 ≤ aᵢ ≤ 10⁹)

Kết quả: Ghi file KHUVUC.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 ≤ aᵢ ≤ 100
• 80% số điểm bài thi: 1 ≤ n ≤ 10³
• 100% số điểm bài thi: 1 ≤ n ≤ 10⁵

Ví dụ:

KHUVUC.INP	KHUVUC.OUT	Giải thích
3 4 2 8	4	Thẻ số 4 đến được các khu vực {1, 2, 4} 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 là 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 nhiên như sau:

• Cho hệ thống sinh ngẫu nhiê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 độ 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 của 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 ≤ 10⁵)
• Dòng thứ hai chứa n số nguyên dương cách nhau bằng khoảng trắng a₁, …, aᵢ, …, aₙ (1 ≤ aᵢ ≤ 10⁹).
• 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 ≤ 10³, 1 ≤ q ≤ 10⁴
• 100% số điểm bài thi: 1 ≤ q ≤ 10⁵

Ví dụ:

GIAIDAU.INP	GIAIDAU.OUT	Giải thích
6 2 4 2 2 1 5 6 1 4 2 5	1 0	Ở lượt thứ 1, ranking của các game thủ có số thứ tự từ 1 đến 4 là: 4 2 2 1 ta có thể chia được như sau: - {4} và {2, 2, 1} độ lệch ranking giữa 2 đội là 1 - {4, 2} và {2, 1} độ lệch ranking giữa 2 đội là 3 - {4, 2, 2} và {1} độ lệch ranking 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 game thủ có số thứ tự từ 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.

---

(Cán bộ coi thi không giải thích gì thêm)