HSG lớp 9 Hà Nội 2019-2020

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI ĐỀ CHÍNH THỨC

KỲ THI HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Năm học 2019 - 2020
Môn thi: Tin học - Ngày thi: 08/01/2020
Thời gian làm bài: 150 phút
(Đề thi gồm 02 trang)

---

Câu 1. Tìm k chữ số (6 điểm)

Tên tệp chương trình: CAU1.*

Cho hai số nguyên dương n và k. Ta định nghĩa n! = 1 × 2 × 3 × … × n.

Yêu cầu: Tìm k chữ số đầu tiên của n!, với k luôn nhỏ hơn hoặc bằng số chữ số của n!.

Dữ liệu: Vào từ tệp văn bản CAU1.INP chứa hai số n và k (1 ≤ k ≤ 18, 1 < n ≤ 10³).

Kết quả: Ghi ra tệp văn bản CAU1.OUT k chữ số đầu tiên của n!.

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
10 3	362	10! = 3628800, ba chữ số đầu tiên là 362.

Câu 2. Chủ đề (5 điểm)

Tên tệp chương trình: CAU2.*

Công ty HNP tổ chức một cuộc thi vẽ tranh cho thiếu nhi toàn thế giới và nhận được sự tham gia nhiệt tình của đông đảo thiếu nhi. Có n bức tranh tham gia cuộc thi. Tranh dự thi được đánh số từ 1 đến n và được phân loại theo chủ đề. Theo kết quả phân loại, bức tranh thứ i có chủ đề aᵢ (1 ≤ i ≤ n).

Ban giám khảo muốn biết có bao nhiêu chủ đề khác nhau để phân công giám khảo chấm. Vì số lượng bức tranh dự thi nhiều, nên công việc này tương đối khó khăn.

Yêu cầu: Hãy giúp Ban giám khảo xác định số chủ đề khác nhau trong cuộc thi.

Dữ liệu: Vào từ tệp văn bản CAU2.INP:

• Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 10⁶);
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶, 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp văn bản CAU2.OUT một số nguyên là số lượng chủ đề khác nhau.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
11 1 2 3 4 5 1 2 1 2 7 5	6	Các chủ đề trong cuộc thi là: 1, 2, 3, 4, 5, 7.

Câu 3. Số nguyên tố lớn nhất (5 điểm)

Tên tệp chương trình: CAU3.*

Trong giờ ra chơi, An nghĩ ra một câu đố như sau:

An chọn một số nguyên tố P và đem dấu vào xâu ký tự T sao cho P là số nguyên tố có giá trị lớn nhất trong số các số nguyên tố tạo được từ các xâu con của T (xâu con của một xâu ký tự T là một chuỗi liên tiếp các ký tự trong T).

An đố các bạn tìm số nguyên tố P mà An đã dấu trong xâu T.

Yêu cầu: Cho xâu ký tự T có độ dài không quá 10³ ký tự. Hãy tìm số nguyên tố P mà An đã dấu trong xâu T biết P có giá trị nhỏ hơn 10⁵. Dữ liệu cho đảm bảo T chứa ít nhất một số nguyên tố.

Dữ liệu: Vào từ tệp văn bản CAU3.INP chứa xâu T.

Kết quả: Ghi ra tệp văn bản CAU3.OUT số P tìm được.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
tt1234#abchgsjid5426	23	Số nguyên tố P là 23 vì T chứa các xâu con ứng với các số nguyên tố 2, 3, 23 và 5.

Câu 4. Mua hàng khuyến mãi (4 điểm)

Tên tệp chương trình: CAU4.*

Nhân dịp năm mới 2020, trung tâm mua sắm HN mở một đợt khuyến mãi lớn. Bình là một khách hàng thân thiết, nên trung tâm gửi cho Bình một danh sách n loại mặt hàng khuyến mãi, được đánh số từ 1 đến n. Mặt hàng thứ i có giá khuyến mãi xᵢ đồng, giá trị thực là yᵢ đồng và số lượng là zᵢ (1 ≤ i ≤ n).

Bình có số tiền m đồng để mua các loại mặt hàng khuyến mãi và mong muốn đạt được tổng giá trị thực của các loại mặt hàng có thể mua được là lớn nhất. Vì số lượng hàng khuyến mãi nhiều, nên Bình không biết phải chọn mua những loại mặt hàng nào, số lượng bao nhiêu cho phù hợp với số tiền của mình.

Yêu cầu: Hãy giúp Bình mua các loại mặt hàng của trung tâm mua sắm HN, sao cho không vượt quá số tiền m và đạt tổng giá trị thực của các loại mặt hàng có thể mua được là lớn nhất.

Dữ liệu: Vào từ tệp văn bản CAU4.INP:

• Dòng đầu tiên chứa hai số nguyên dương n và m (1 ≤ n ≤ 500, 1 < m ≤ 5×10⁴);
• Dòng thứ i trong n dòng tiếp theo ghi ba số nguyên dương xᵢ, yᵢ và zᵢ lần lượt là giá trị khuyến mãi, giá trị thực và số lượng của loại mặt hàng thứ i (1 ≤ xᵢ ≤ 10⁴, 1 ≤ yᵢ ≤ 10⁴, 1 ≤ zᵢ ≤ 100, 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp văn bản CAU4.OUT:

• Dòng đầu là tổng giá trị đạt được;
• Dòng thứ i trong n dòng tiếp theo ghi số kᵢ (1 ≤ i ≤ n) là số lượng loại mặt hàng thứ i được chọn mua. Nếu có nhiều cách chọn thỏa mãn, thì đưa ra cách chọn có chỉ số loại mặt hàng nhỏ nhất là nhiều nhất.

Ví dụ:

CAU4.INP	CAU4.OUT	Giải thích
5 14 9 10 1 2 3 3 2 3 3 3 6 4 5 10 4	28 0 0 0 3 1	Bình chọn ba loại mặt hàng thứ 4 và một loại mặt hàng thứ 5, tổng giá trị là: 28.

---

Chú ý:

• Giám thị không giải thích gì thêm;
• Các tệp dữ liệu vào là đúng đắn không cần kiểm tra;
• Làm bài với các tên tệp đúng như quy định trong đề, trong đó dấu * là phần mở rộng mặc định theo ngôn ngữ lập trình mà thí sinh sử dụng (ví dụ: CAU1.PAS hoặc CAU1.CPP, …).