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

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

KÌ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 Năm học 2020 - 2021
Môn thi: Tin học - Bảng B
Thời gian: 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	Thời gian	Giới hạn bộ nhớ
Đếm số ước dương (6 điểm)	DemUoc.*	DemUoc.Inp	DemUoc.Out	1 giây	1024Mb
Dãy hạt Cườm (5 điểm)	HatCuom.*	HatCuom.Inp	HatCuom.Out	1 giây	1024Mb
Chia kẹo (5 điểm)	ChiaKeo.*	ChiaKeo.Inp	ChiaKeo.Out	1 giây	1024Mb
Cặp số hạng nghịch thế (4 điểm)	NghichThe.*	NghichThe.Inp	NghichThe.Out	1 giây	1024Mb

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.

Bài 1. Đếm số ước dương

Cho số nguyên dương N. Hãy đếm số lượng các ước dương của N.

Dữ liệu cho trong tệp văn bản DemUoc.Inp gồm một số nguyên dương N.

Kết quả ghi ra tệp văn bản DemUoc.Out là số lượng các ước dương của N.

Ví dụ:

DemUoc.Inp	DemUoc.Out	Giải thích
6	4	6 có các ước dương: 1, 2, 3, 6. Số lượng các ước dương là 4.

Giới hạn:

• Có 75% số test ứng với 75% số điểm thỏa mãn 1 ≤ N ≤ 10⁶;
• Có 25% số test ứng với 25% số điểm thỏa mãn 10⁶ < N ≤ 10¹².

Bài 2. Dãy hạt Cườm

Bạn Hoa sưu tầm được N hạt Cườm có đủ hai màu: Xanh và Tím. Hiện tại, bạn Hoa đang xếp N hạt Cườm này thành một hàng ngang và màu của chúng thì xuất hiện khá lộn xộn. Hoa muốn các hạt Cườm màu Xanh được xếp về bên trái hàng và các hạt Cườm màu Tím được xếp về bên phải hàng.

Yêu cầu: Hãy giúp Hoa sắp xếp N hạt Cườm thành hàng ngang sao cho các hạt màu Xanh được xếp về bên trái hàng và các hạt màu Tím được xếp về bên phải hàng.

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

• Dòng thứ nhất ghi số nguyên dương N (2 ≤ N ≤ 255) là số hạt Cườm.
• Dòng thứ hai ghi N kí tự lần lượt mô tả màu của N hạt Cườm. Kí tự ‘X’ mô tả màu Xanh, kí tự ‘T’ mô tả màu Tím. Các kí tự được ghi liền kề nhau.
• Dữ liệu đảm bảo luôn có màu Xanh và màu Tím.

Kết quả: ghi ra tệp văn bản HatCuom.Out gồm N kí tự là màu của các hạt Cườm sau khi sắp xếp, hạt màu Xanh được xếp bên trái, hạt màu Tím được xếp bên phải. Các kí tự được ghi liền kề nhau.

Ví dụ:

hatcuom.inp	hatcuom.out
5 XTTXT	XXTTT

Giới hạn:

• Có 30% số test ứng với 30% số điểm thỏa mãn 2 ≤ N ≤ 3;
• Có 70% số test ứng với 70% số điểm thỏa mãn 3 ≤ N ≤ 255.

Bài 3. Chia kẹo

Có N gói kẹo được đánh số hiệu từ 1 đến N. Gói kẹo thứ i (i = 1, 2, 3, …, N) có Aᵢ chiếc kẹo. Cần phân chia N gói kẹo thành 2 phần:

• Phần 1 gồm các gói kẹo 1, 2, …, i. Tổng số chiếc kẹo của phần 1 là x = A₁ + A₂ + … + Aᵢ;
• Phần 2 gồm các gói kẹo i + 1, i + 2, …, N. Tổng số chiếc kẹo của phần 2 là y = Aᵢ₊₁ + Aᵢ₊₂ + … + A_N;
• Với 1 ≤ i < N.

Yêu cầu: Tìm cách phân chia N gói kẹo sao cho chênh lệch giữa số kẹo của hai phần là nhỏ nhất, tức là |x − y| đạt giá trị nhỏ nhất. Ta đặt giá trị T = |x − y|.

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

• Dòng thứ nhất ghi số nguyên dương N là số gói kẹo.
• Dòng thứ hai ghi N số nguyên dương A₁, A₂, …, A_N (1 ≤ Aᵢ ≤ 10³) là số chiếc kẹo của N gói kẹo.
• Các số ghi trên một dòng cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản ChiaKeo.Out là giá trị nhỏ nhất của T.

Ví dụ:

ChiaKeo.Inp	ChiaKeo.Out	Giải thích
5 1 2 3 4 3	1	Phần 1: Chọn các gói kẹo 1, 2, 3; x = A₁ + A₂ + A₃ = 1 + 2 + 3 = 6. Phần 2: Chọn các gói kẹo 4, 5; y = A₄ + A₅ = 4 + 3 = 7. Chênh lệch số kẹo giữa hai phần là 7 − 6 = 1. Đây là chênh lệch nhỏ nhất có thể phân chia được.

Giới hạn:

• Có 50% số test ứng với 50% số điểm thỏa mãn 3 ≤ N ≤ 1000;
• Có 50% số test ứng với 50% số điểm thỏa mãn 1000 < N ≤ 10⁵.

Bài 4. Cặp số hạng nghịch thế

Cho dãy số gồm N số nguyên A₁, A₂, …, A_N. Ta gọi cặp số hạng Aᵢ và Aⱼ là cặp số hạng nghịch thế nếu thỏa mãn:

• 1 ≤ i < j ≤ N;
• Aᵢ > Aⱼ.

Khi đó, hiệu Aᵢ − Aⱼ được gọi là độ chênh lệch của cặp số hạng nghịch thế Aᵢ và Aⱼ.

Yêu cầu: Tìm cặp số hạng nghịch thế có độ chênh lệch nhỏ nhất.

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

• Dòng thứ nhất ghi số nguyên dương N là số các số hạng của dãy.
• Dòng thứ hai ghi N số nguyên A₁, A₂, …, A_N (0 ≤ Aᵢ ≤ 10⁶).
• Dữ liệu đảm bảo luôn có ít nhất một cặp số hạng nghịch thế.

Kết quả: ghi ra tệp văn bản NghichThe.Out là độ chênh lệch của cặp số hạng nghịch thế có độ chênh lệch nhỏ nhất.

Ví dụ:

nghichthe.inp	nghichthe.out	Giải thích
4 2 3 1 5	1	Ta có các cặp số hạng nghịch thế: Cặp số hạng: A₁ = 2 và A₃ = 1; độ chênh lệch 2 − 1 = 1. Cặp số hạng: A₂ = 3 và A₃ = 1; độ chênh lệch 3 − 1 = 2. Độ chênh lệch của cặp số hạng nghịch thế có độ chênh lệch nhỏ nhất bằng 1.

Giới hạn:

• Có 50% test ứng với 50% số điểm thỏa mãn N ≤ 1000;
• Có 50% test ứng với 50% số điểm thỏa mãn 1000 < N ≤ 2×10⁵; 0 ≤ Aᵢ ≤ 100 với i = 1, 2, …, N.