HSG lớp 9 Nghệ An 2021-2022 (Bảng A)

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN ĐỀ CHÍNH THỨC
(Đề thi gồm 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 Năm học 2021 - 2022
Môn thi: Tin học - Bảng A
Thời gian làm bài: 150 phút (không kể thời gian giao đề)

---

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Bộ nhớ tối đa	Thời gian
Số ước nguyên tố	UocNT.*	UocNT.Inp	UocNT.Out	1024MB	1 giây
Mật khẩu	MatKhau.*	MatKhau.Inp	MatKhau.Out	1024MB	1 giây
Cặp vé trúng thưởng	TrungThuong.*	TrungThuong.Inp	TrungThuong.Out	1024MB	1 giây
Chọn sách	ChonSach.*	ChonSach.Inp	ChonSach.Out	1024MB	1 giây

Phần mở rộng .* được thay thế bằng Pas, Cpp, Py ứng với các ngôn ngữ lập trình Pascal, C++, Python.

(Công thức toán lấy theo bản đánh máy trong tài liệu “50 đề thi HSG THCS” vì bản chụp đề gốc bị mất các công thức.)

Câu 1. Số ước nguyên tố (6.0 điểm)

Trong buổi ôn tập cho đội tuyển dự thi học sinh giỏi, thầy giáo đã ra cho bạn An một bài tập về số học như sau:

Cho số nguyên dương n. Hãy tính xem, trong các ước của n có bao nhiêu ước là số nguyên tố?

Bạn An đã dễ dàng đưa ra kết quả đúng của bài toán.

Yêu cầu: Hãy đưa ra kết quả mà bạn An tìm được.

Dữ liệu cho trong tệp văn bản UocNT.Inp gồm một số nguyên dương n (2 ≤ n ≤ 10¹²).

Kết quả ghi ra tệp văn bản UocNT.Out một số duy nhất là số lượng các ước của số n là số nguyên tố.

Ví dụ:

UocNT.Inp	UocNT.Out	Giải thích
10	2	n = 10 có 4 ước là: 1, 2, 5, 10. Trong đó, có 2 ước: 2 và 5 là các số nguyên tố.

Giới hạn:

• Có 60% số test ứng với 60% số điểm thoả mãn 2 ≤ n ≤ 10³;
• Có 20% số test ứng với 20% số điểm thoả mãn 10³ < n ≤ 10⁶;
• Có 20% số test ứng với 20% số điểm thoả mãn 10⁶ < n ≤ 10¹².

Câu 2. Mật khẩu (5.0 điểm)

Bạn An rất đam mê lập trình. Một hôm, An nhận được thông báo nhận thưởng từ công ty phần mềm mà An thường xuyên sử dụng sản phẩm của công ty đó. Phần thưởng là phiên bản mới của phần mềm trò chơi trí tuệ mà An rất yêu thích. Tuy nhiên, để tải phần mềm này về máy tính thì An cần phải nhập mật khẩu. Mật khẩu là một xâu kí tự nhận được khi An giải xong bài toán mà công ty đã gửi cho An như sau:

Cho n xâu kí tự S₁, S₂, …, Sₙ chỉ chứa các kí tự thuộc tập chữ cái latinh hoa từ ‘A’ đến ‘Z’. Với mỗi xâu kí tự Sᵢ (i = 1, 2, …, n) có một kí tự xuất hiện 1 lần, các kí tự còn lại xuất hiện ít nhất 2 lần. Mật khẩu là một xâu gồm n kí tự, trong đó kí tự thứ i (i = 1, 2, …, n) là kí tự xuất hiện 1 lần trong xâu Sᵢ.

Yêu cầu: Hãy đưa ra mật khẩu mà An cần tìm.

Dữ liệu cho trong tệp văn bản MatKhau.Inp gồm:

• Dòng đầu tiên ghi số nguyên dương n (1 ≤ n ≤ 1000) là số lượng xâu kí tự.
• Dòng thứ i trong n dòng tiếp theo ghi một xâu kí tự Sᵢ có độ dài không quá 1000.

Kết quả ghi ra tệp văn bản MatKhau.Out gồm một xâu kí tự là mật khẩu tìm được.

Ví dụ:

MatKhau.Inp	MatKhau.Out	Giải thích
3 ACADD FAAA ABBBBAFAAA	CFF	Có 3 xâu kí tự: - Xâu “ACADD”: Kí tự C xuất hiện 1 lần. - Xâu “FAAA”: Kí tự F xuất hiện 1 lần. - Xâu “ABBBBAFAAA”: Kí tự F xuất hiện 1 lần. Ta có mật khẩu là: “CFF”.

Giới hạn:

• Có 60% số test ứng với 60% số điểm thoả mãn n = 1 và độ dài của xâu không quá 255;
• Có 20% số test ứng với 20% số điểm thoả mãn n ≤ 100 và độ dài của mỗi xâu không quá 255;
• Có 20% số test ứng với 20% số điểm còn lại không có giới hạn gì thêm.

Câu 3. Cặp vé trúng thưởng (5.0 điểm)

Công ty xổ số BlueCode phát hành n vé số đặc biệt để chào mừng ngày thành lập. Các vé được đánh số thứ tự từ 1 đến n. Hệ thống quay thưởng sẽ tạo ra ngẫu nhiên một dãy gồm n số nguyên dương c₁, c₂, …, cₙ là mã của n vé. Vé thứ i (i = 1, 2, …, n) có mã là cᵢ. Cặp vé (i, j) với 1 ≤ i < j ≤ n, sẽ trúng thưởng nếu trong hai mã của hai vé đó là cᵢ và cⱼ sẽ có một số bằng số lớn nhất, số còn lại bằng số nhỏ nhất trong các số cᵢ, cᵢ₊₁, …, cⱼ. Tức là khi đặt x = min(cᵢ, cᵢ₊₁, …, cⱼ); y = max(cᵢ, cᵢ₊₁, …, cⱼ) thì trong hai số cᵢ và cⱼ sẽ có một số bằng x, số còn lại bằng y. Công ty muốn biết có bao nhiêu cặp vé sẽ trúng thưởng nên đã nhờ bạn An lập trình để tính số cặp vé trúng thưởng.

Yêu cầu: Cho biết dãy gồm n số nguyên dương c₁, c₂, …, cₙ, hãy đưa ra số cặp vé trúng thưởng.

Dữ liệu cho trong tệp văn bản TrungThuong.Inp gồm:

• Dòng 1 ghi số nguyên dương n (2 ≤ n ≤ 2×10⁵).
• Dòng 2 ghi n số nguyên dương c₁, c₂, …, cₙ (1 ≤ cᵢ ≤ 10⁸, i = 1, 2, …, n).
• Các số ghi trên một dòng được phân cách nhau bởi dấu cách trống.

Kết quả ghi ra tệp văn bản TrungThuong.Out một số nguyên duy nhất là số cặp vé trúng thưởng.

Ví dụ:

TrungThuong.Inp	TrungThuong.Out
5 3 3 1 6 5	5

Giải thích: Ta có 5 cặp vé trúng thưởng

Cặp vé (i, j)	cᵢ	cⱼ	x = min(cᵢ, …, cⱼ)	y = max(cᵢ, …, cⱼ)	Điều kiện
i = 1; j = 2	3	3	3	3	cᵢ = x; cⱼ = y
i = 2; j = 3	3	1	1	3	cᵢ = y; cⱼ = x
i = 3; j = 4	1	6	1	6	cᵢ = x; cⱼ = y
i = 4; j = 5	6	5	5	6	cᵢ = y; cⱼ = x
i = 1; j = 3	3	1	1	3	cᵢ = y; cⱼ = x

Giới hạn:

• 40% số test ứng với 40% số điểm thỏa mãn 2 ≤ n ≤ 200;
• 40% số test ứng với 40% số điểm thỏa mãn 200 < n ≤ 2000;
• 20% số test ứng với 20% số điểm thỏa mãn 2000 < n ≤ 2×10⁵; 1 ≤ cᵢ ≤ 3; i = 1, 2, …, n.

Câu 4. Chọn sách (4.0 điểm)

Thư viện trường học của bạn An có n quyển sách, mỗi quyển sách có dạng hình chữ nhật. Các quyển sách được đánh số thứ tự từ 1 đến n. Quyển sách thứ i (i = 1, 2, …, n) có chiều dài là dᵢ, chiều rộng là rᵢ (đơn vị độ dài). Bạn An muốn chọn một số quyển sách trong n quyển sách để xếp thành một chồng sao cho quyển sách được xếp ở trên có kích thước nhỏ hơn quyển sách được xếp ở dưới, tức là nếu quyển sách i được xếp trên quyển sách j thì dᵢ < dⱼ và rᵢ < rⱼ.

Yêu cầu: Hãy đưa ra số sách lớn nhất mà bạn An có thể chọn để xếp được chồng sách theo yêu cầu trên. Ta gọi số quyển sách nhiều nhất có thể chọn được là S.

Dữ liệu cho trong tệp văn bản ChonSach.Inp gồm:

• Dòng đầu tiên ghi số nguyên dương n (2 ≤ n ≤ 2×10⁵) là số lượng quyển sách.
• Dòng thứ i trong n dòng tiếp theo ghi 2 số nguyên dương dᵢ và rᵢ (1 ≤ dᵢ, rᵢ ≤ 10⁸) tương ứng là chiều dài và chiều rộng của quyển sách thứ i.

Kết quả ghi ra tệp văn bản ChonSach.Out số nguyên S tìm được.

Ví dụ:

ChonSach.Inp	ChonSach.Out	Giải thích
2 6 3 5 3	1	Chỉ có thể chọn được 1 quyển sách (quyển 1 hoặc quyển 2).
5 3 2 4 1 10 6 8 4 7 5	3	Chọn được nhiều nhất 3 quyển sách: có thể chọn quyển 1, 3, 5. Cách xếp theo thứ tự từ trên xuống dưới: Quyển 1 → Quyển 5 → Quyển 3.
2 5 4 3 1	2	Chọn được 2 quyển sách: quyển 1 và quyển 2. Cách xếp theo thứ tự từ trên xuống dưới: Quyển 2 → Quyển 1.

Giới hạn:

• Có 25% số test ứng với 25% số điểm thỏa mãn 2 ≤ n ≤ 200 và S ≤ 2;
• Có 25% số test ứng với 25% số điểm thỏa mãn 2 ≤ n ≤ 2×10³; dᵢ ≠ dⱼ và rᵢ ≠ rⱼ với mọi cặp i ≠ j; 1 ≤ i, j ≤ n;
• Có 25% số test ứng với 25% số điểm thỏa mãn 2×10³ < n ≤ 2×10⁵; dᵢ ≠ dⱼ và rᵢ ≠ rⱼ với mọi cặp i ≠ j; 1 ≤ i, j ≤ n;
• Có 25% số test ứng với 25% số điểm còn lại thỏa mãn 2×10³ < n ≤ 2×10⁵.