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

ĐỀ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 TỈNH NGHỆ AN Năm học 2020 - 2021

MÔN TIN HỌC - BẢNG A 4 bài: DemUoc, KhaoSatGia, ChiaKeo, TichBaSo

---

Ghi chú

Đề được đánh máy lại theo tài liệu “50 đề thi HSG THCS” (không kèm phần tiêu đề, thời gian làm bài và thang điểm của đề gốc).

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. Khảo sát giá

Trong dịp cuối năm 2020, một đội khảo sát giá ở tỉnh Nghệ An đã tiến hành khảo sát giá bán của N (1 ≤ N ≤ 26) mặt hàng đang được bán tại nhiều cửa hàng trên toàn tỉnh.

Tên của mỗi mặt hàng được đặt bằng một chữ cái in hoa thuộc tập chữ cái từ ‘A’ đến ‘Z’. Giá bán của mỗi mặt hàng là 1 số nguyên từ 1 đến 9.

Để kích thích tiêu dùng, đội khảo sát cần đưa ra cho khách hàng thông tin giá bán thấp nhất của từng mặt hàng được bán trên địa bàn.

Yêu cầu: Bạn hãy giúp đội khảo sát đưa ra giá bán thấp nhất của từng mặt hàng đang được bán tại các cửa hàng và tổng chi phí để mua các mặt hàng với giá thấp nhất đó.

Dữ liệu vào từ tệp văn bản KhaoSatGia.Inp gồm:

• Dòng thứ nhất ghi số nguyên dương N (1 ≤ N ≤ 26) là số lượng các mặt hàng được khảo sát giá bán.
• N dòng tiếp theo mỗi dòng ghi một xâu kí tự (số lượng kí tự thuộc phạm vi từ 2 đến 255) mô tả thông tin về tên mặt hàng và các giá bán của mặt hàng đó tại một số cửa hàng khác nhau. Ví dụ: xâu A572 nghĩa là tên mặt hàng là A, giá bán tại các cửa hàng lần lượt là 5, 7, 2. Dữ liệu đảm bảo tên của N mặt hàng là khác nhau.

Kết quả ghi ra tệp văn bản KhaoSatGia.Out gồm N + 1 dòng:

• N dòng đầu tiên mỗi dòng gồm tên mặt hàng và giá bán thấp nhất của mặt hàng đó (các mặt hàng được đưa ra tương ứng với thứ tự trong tệp dữ liệu vào, tên mặt hàng và giá được ghi liền nhau).
• Dòng cuối là tổng chi phí để mua tất cả các mặt hàng với giá bán thấp nhất (mỗi loại mặt hàng chỉ được tính mua một lần với giá thấp nhất).

Ví dụ:

khaosatgia.inp	khaosatgia.out	Giải thích
3 A86722 D765 B2	A2 D5 B2 9	Có 3 mặt hàng: - Chuỗi kí tự A86722 mô tả: Tên mặt hàng là A, các giá bán: 8, 6, 7, 2, 2 → giá thấp nhất là 2. - Chuỗi kí tự D765 mô tả: Tên mặt hàng là D, các giá bán: 7, 6, 5 → giá thấp nhất là 5. - Chuỗi kí tự B2 mô tả: Tên mặt hàng là B, có 1 giá bán: 2 → giá thấp nhất là 2. → Tổng chi phí để mua 3 mặt hàng với giá thấp nhất: 2 + 5 + 2 = 9.

Giới hạn:

• Có 20% số test ứng với 20% số điểm thỏa mãn N = 1, tức là chỉ khảo sát 1 mặt hàng;
• Có 30% số test ứng với 30% số điểm thỏa mãn mỗi mặt hàng chỉ có 1 giá, tức là chỉ có 1 cửa hàng bán mặt hàng đó;
• Có 50% số test ứng với 50% số điểm không có ràng buộc gì thêm.

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 3 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, …, j. Tổng số chiếc kẹo của phần 2 là y = Aᵢ₊₁ + Aᵢ₊₂ + … + Aⱼ;
• Phần 3 gồm các gói kẹo j + 1, j + 2, …, N. Tổng số chiếc kẹo của phần 3 là z = Aⱼ₊₁ + Aⱼ₊₂ + … + A_N;
• Với 1 ≤ i < j < 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 phần có tổng số kẹo nhiều nhất và phần có tổng số kẹo ít nhất là nhỏ nhất, tức là max(x, y, z) − min(x, y, z) đạt giá trị nhỏ nhất. Ta đặt giá trị T = max(x, y, z) − min(x, y, z).

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 2	3	Phần 1: Chọn các gói 1, 2: x = A₁ + A₂ = 1 + 2 = 3. Phần 2: Chọn gói 3: y = A₃ = 3. Phần 3: Chọn các gói 4, 5: z = A₄ + A₅ = 4 + 2 = 6. → Chênh lệch số kẹo giữa phần nhiều kẹo nhất và phần ít kẹo nhất là 3. Đâ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 ≤ 200;
• Có 25% số test ứng với 25% số điểm thỏa mãn 200 < N ≤ 2000;
• Có 25% số test ứng với 25% số điểm thỏa mãn 2000 < N ≤ 2×10⁵.

Bài 4. Tích ba số nguyên với ba số hạng của dãy

Cho dãy số A gồm N số nguyên A₁, A₂, …, A_N (N ≥ 3) và 3 số nguyên x, y, z. Trong dãy số A, hãy chọn 3 số hạng Aᵢ, Aⱼ, A_k (1 ≤ i < j < k ≤ N) sao cho S = x × Aᵢ + y × Aⱼ + z × A_k đạt giá trị lớn nhất.

Ví dụ, với dãy A gồm 4 số hạng: [1, 3, 2, 4]; x = 1, y = 1, z = 2, ta có 4 cách chọn 3 số hạng trong dãy A:

• Chọn 3 số hạng: A₁, A₂, A₃ = [1, 3, 2] thì tích S = 1×1 + 1×3 + 2×2 = 8;
• Chọn 3 số hạng: A₁, A₂, A₄ = [1, 3, 4] thì tích S = 1×1 + 1×3 + 2×4 = 12;
• Chọn 3 số hạng: A₁, A₃, A₄ = [1, 2, 4] thì tích S = 1×1 + 1×2 + 2×4 = 11;
• Chọn 3 số hạng: A₂, A₃, A₄ = [3, 2, 4] thì tích S = 1×3 + 1×2 + 2×4 = 13;

Như vậy giá trị lớn nhất của S có thể đạt được là 13.

Dữ liệu cho trong tệp văn bản TichBaSo.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 A.
• Dòng thứ hai ghi N số nguyên A₁, A₂, …, A_N (|Aᵢ| ≤ 10⁵ với i = 1, 2, 3, …, N).
• Dòng thứ ba ghi 3 số nguyên x, y, z (|x|, |y|, |z| ≤ 10⁵).

Các số ghi trên một dòng được cách nhau bởi dấu cách.

Kết quả: ghi ra file văn bản TichBaSo.Out gồm một số nguyên là giá trị lớn nhất của S có thể đạt được.

Ví dụ:

tichbaso.inp	tichbaso.out
4 1 3 2 4 1 1 2	13

Giới hạn:

• Có 50% số test ứng với 50% số điểm thỏa mãn N ≤ 200;
• Có 25% số test ứng với 25% số điểm thỏa mãn 200 < N ≤ 2×10⁵ và x = y = z;
• Có 25% số test ứng với 25% số điểm thỏa mãn 200 < N ≤ 2×10⁵ và |x|, |y|, |z| ≤ 10⁵.