Đề số 03 - Ôn thi HSG Tin học THCS

BỘ ĐỀ ÔN THI HỌC SINH GIỎI TIN HỌC THCS Bumbii Academy

ĐỀ SỐ 03 Thời gian làm bài: 150 phút
4 bài, tổng 20 điểm

---

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
1	Xếp chữ số	CHUSO.*	CHUSO.INP	CHUSO.OUT	3
2	Tích lớn nhất	TICHMAX.*	TICHMAX.INP	TICHMAX.OUT	5
3	Thống kê số lần xuất hiện	XUATHIEN.*	XUATHIEN.INP	XUATHIEN.OUT	6
4	Chia kẹo thành các đoạn	CHIADAY.*	CHIADAY.INP	CHIADAY.OUT	6

Dấu * được thay bằng py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng.

Bài 1. Xếp chữ số (3 điểm)

Cho số nguyên dương n. Dùng tất cả các chữ số của n (mỗi chữ số dùng đúng một lần), ta có thể xếp lại để được nhiều số khác nhau. Lưu ý một số có từ hai chữ số trở lên không được bắt đầu bằng chữ số 0.

Yêu cầu: Cho biết n có bao nhiêu chữ số, số lớn nhất và số nhỏ nhất có thể xếp được.

Dữ liệu vào: Từ file văn bản CHUSO.INP gồm một dòng chứa số nguyên dương n.

Kết quả: Ghi ra file văn bản CHUSO.OUT gồm ba dòng lần lượt là số chữ số của n, số lớn nhất và số nhỏ nhất xếp được.

Ví dụ:

CHUSO.INP	CHUSO.OUT	Giải thích
7168	4 8761 1678
30200	5 32000 20003	Số 00023 không hợp lệ vì bắt đầu bằng 0.

Ràng buộc:

• Có 50% số test với n ≤ 10⁶.
• Có 50% số test với n ≤ 10¹⁸.

Bài 2. Tích lớn nhất (5 điểm)

Trong trò chơi “Nhân đôi may mắn”, mỗi người chơi được phát một dãy n thẻ số, thẻ thứ i ghi số nguyên a_i (có thể âm). Người chơi chọn ra hai thẻ khác nhau và nhận số điểm bằng tích hai số ghi trên hai thẻ đó.

Yêu cầu: Tìm số điểm lớn nhất mà người chơi có thể đạt được.

Dữ liệu vào: Từ file văn bản TICHMAX.INP gồm:

• Dòng đầu tiên chứa số nguyên n (n ≥ 2).
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n.

Kết quả: Ghi ra file văn bản TICHMAX.OUT một số nguyên là số điểm lớn nhất.

Ví dụ:

TICHMAX.INP	TICHMAX.OUT	Giải thích
5 4 2 7 1 5	35	Chọn hai thẻ 7 và 5.
5 -6 3 -8 1 5	48	Chọn hai thẻ −6 và −8, tích là 48 lớn hơn 3 × 5 = 15.

Ràng buộc:

• Có 30% số test với n ≤ 1000, 0 ≤ a_i ≤ 10⁴.
• Có 30% số test với n ≤ 1000, |a_i| ≤ 10⁹.
• Có 40% số test với n ≤ 10⁵, |a_i| ≤ 10⁹.

Bài 3. Thống kê số lần xuất hiện (6 điểm)

Thư viện trường ghi lại mã số của n cuốn sách được mượn trong tháng: a₁, a₂, …, a_n (một cuốn sách có thể được mượn nhiều lần nên mã số có thể lặp lại). Cô thủ thư muốn biết mức độ được yêu thích của các đầu sách, nên đặt ra q câu hỏi. Câu hỏi thứ j có dạng: “Có bao nhiêu cuốn sách (mã số khác nhau) được mượn ít nhất k_j lần?”

Yêu cầu: Trả lời q câu hỏi của cô thủ thư.

Dữ liệu vào: Từ file văn bản XUATHIEN.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương n và q.
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (|a_i| ≤ 10⁹).
• q dòng tiếp theo, dòng thứ j chứa số nguyên dương k_j (k_j ≤ 10⁹).

Kết quả: Ghi ra file văn bản XUATHIEN.OUT gồm q dòng, dòng thứ j là câu trả lời cho câu hỏi thứ j.

Ví dụ:

XUATHIEN.INP	XUATHIEN.OUT	Giải thích
8 3 1 2 1 4 3 4 5 4 2 3 1	2 1 5	Số lần mượn: sách 1 là 2 lần, sách 4 là 3 lần, các sách 2, 3, 5 mỗi sách 1 lần.

Ràng buộc:

• Có 50% số test với n, q ≤ 1000.
• Có 50% số test với n, q ≤ 10⁵.

Bài 4. Chia kẹo thành các đoạn (6 điểm)

Cô giáo xếp n gói kẹo thành một hàng, gói thứ i có a_i viên kẹo. Cô muốn cắt hàng kẹo thành nhiều đoạn liên tiếp (mỗi gói thuộc đúng một đoạn, không được đổi thứ tự các gói) sao cho tổng số kẹo trong mỗi đoạn bằng nhau. Mỗi đoạn sẽ được tặng cho một tổ, nên cô muốn cắt được càng nhiều đoạn càng tốt.

Yêu cầu: Tìm số đoạn nhiều nhất có thể cắt được.

Dữ liệu vào: Từ file văn bản CHIADAY.INP gồm:

• Dòng đầu tiên chứa số nguyên dương n.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁴).

Kết quả: Ghi ra file văn bản CHIADAY.OUT một số nguyên là số đoạn nhiều nhất.

Ví dụ:

CHIADAY.INP	CHIADAY.OUT	Giải thích
8 10 2 6 2 5 2 1 2	3	Cắt thành (10), (2, 6, 2), (5, 2, 1, 2), mỗi đoạn 10 viên.
3 1 2 4	1	Không cắt được, cả hàng là một đoạn.

Ràng buộc:

• Có 40% số test với n ≤ 1000.
• Có 60% số test với n ≤ 10⁵.

Lời giải và bộ test của đề này (có phí)

Hướng dẫn giải chi tiết, code Python và C++ đã được kiểm chứng, cùng bộ test và công cụ chấm cham.py, có trong bộ tài liệu đầy đủ (có phí).

Thầy cô và các em muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.

Muốn xem trước cách trình bày lời giải, hãy xem Đề số 01 (có lời giải miễn phí).

Do số lượng đề bài, bài giải và bộ test rất nhiều nên tác giả đang kiểm tra từng bước. Thầy cô và các em học sinh nếu thấy sai sót xin vui lòng liên hệ tác giả qua Facebook hoặc Zalo (0972465159). Xin chân thành cảm ơn.