HSG lớp 9 Đồng Tháp 2022-2023

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐỒNG THÁP ĐỀ CHÍNH THỨC
(Đề gồm có 2 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP TỈNH Năm học 2022 - 2023
Môn: Tin học - Ngày thi: 12/3/2023
Thời gian làm bài: 150 phút, không kể thời gian phát đề

---

Tổng quan đề thi

Tên bài	Tên tệp bài làm	Tên tệp dữ liệu vào	Tên tệp kết quả
Bài 1. Liên hoan	LIENHOAN.*	LIENHOAN.INP	LIENHOAN.OUT
Bài 2. Chợ nổi	CHONOI.*	CHONOI.INP	CHONOI.OUT
Bài 3. Đèn trang trí	TRANGTRI.*	TRANGTRI.INP	TRANGTRI.OUT

Ghi chú: dấu * đại diện cho phần mở rộng, tùy theo ngôn ngữ lập trình có thể là PAS hoặc CPP hoặc PY. Thời gian thực hiện chương trình không quá 1 giây, bộ nhớ không quá 1024MB.

Bài 1. Liên hoan (6,0 điểm)

Nhân dịp ngày lễ Quốc Tế Phụ Nữ, lớp 9A1 tổ chức buổi liên hoan để các bạn nam chế biến các món ăn ngon dành cho các bạn nữ thưởng thức. Bạn An được phân công chiên n chiếc bánh. Cái chảo dùng để chiên bánh chỉ chiên được nhiều nhất k chiếc bánh cùng một lúc. Các chiếc bánh cần phải chiên đủ hai mặt, mỗi lần chiên một mặt trong 3 phút để bánh đạt được độ giòn ngon nhất.

Yêu cầu: Hãy xác định thời gian ít nhất để bạn An chiên đủ hai mặt của n chiếc bánh.

Dữ liệu vào: Cho từ tệp văn bản LIENHOAN.INP gồm một dòng ghi hai số nguyên dương n, k (1 ≤ n, k ≤ 10⁶).

Kết quả: Ghi vào tệp văn bản LIENHOAN.OUT gồm một dòng ghi một số nguyên dương là tổng thời gian (tính theo phút) ít nhất để bạn An chiên đủ hai mặt của n chiếc bánh.

Ví dụ:

LIENHOAN.INP	LIENHOAN.OUT
10 5	12
8 6	9

Ràng buộc:

• Có 70% số test tương ứng 70% số điểm có n, k ≤ 10³;
• Có 30% số test tương ứng 30% số điểm có n, k ≤ 10⁶.

Bài 2. Chợ nổi (7,0 điểm)

Chợ nổi là một nét văn hóa lâu đời của Khu vực Đồng bằng sông Cửu Long, cũng là điểm du lịch đẹp mà nhiều đoàn tham quan ghé thăm. Đến với Chợ nổi bạn có thể thuê những chiếc xuồng tham quan mua sắm và thưởng thức các món ăn ngon đậm chất miền Tây.

Một đoàn khách tham quan có n người được đánh số thứ tự từ 1 đến n, du khách thứ i có cân nặng là aᵢ. Do hiện tại có nhiều du khách nên đoàn tham quan chỉ thuê được một chiếc xuồng có tải trọng là k và chỉ chở được hai du khách có cân nặng không được vượt quá k để đảm bảo an toàn cho du khách. Hướng dẫn viên muốn bố trí cho hai du khách xuống xuồng trước, các du khách còn lại sẽ chờ để xuống xuồng tham quan trong các lượt tiếp theo hoặc có thể tản bộ dọc theo bờ sông để tham quan và thư giãn.

Yêu cầu: Hãy cho biết có bao nhiêu cách chọn ra hai du khách bố trí xuống xuồng để tham quan mà vẫn phải đảm bảo an toàn (tổng cân nặng không vượt quá k).

Dữ liệu vào: Cho từ tệp văn bản CHONOI.INP gồm hai dòng:

• Dòng thứ nhất ghi hai số nguyên dương n, k (1 ≤ n, k ≤ 10⁶).
• Dòng thứ hai ghi n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶, i = 1..n).

Kết quả: Ghi vào tệp văn bản CHONOI.OUT gồm một dòng ghi một số nguyên dương là số cách chọn ra hai du khách bố trí xuống xuồng để tham quan mà vẫn phải đảm bảo an toàn.

Ví dụ:

CHONOI.INP	CHONOI.OUT
5 90 40 45 55 42 52	3

Ràng buộc:

• Có 70% số test tương ứng 70% số điểm có n ≤ 10³;
• Có 30% số test tương ứng 30% số điểm có n ≤ 10⁶.

Bài 3. Đèn trang trí (7,0 điểm)

Dọc theo con đường trung tâm thành phố có trồng một hàng cây gồm n cây đánh số từ 1 đến n theo thứ tự từ đầu đến cuối con đường, cây thứ i có chiều cao aᵢ. Để tăng vẻ đẹp của con đường khi về đêm, Ban quản lí công trình đô thị dự định lắp thêm đèn trang trí trên các cây. Tuy nhiên, do chiều cao của các cây không đều nhau nên Ban quản lí không lắp đèn trang trí lên tất cả các cây mà chỉ lắp đèn lên một số cây sao cho hai cây được lắp đèn trang trí kế tiếp nhau có chiều cao chênh lệch nhau không quá k.

Yêu cầu: Hãy giúp Ban quản lí chọn ra các cây để lắp đèn trang trí sao cho số cây được lắp đèn là nhiều nhất.

Dữ liệu vào: Cho từ tệp văn bản TRANGTRI.INP gồm hai dòng:

• Dòng thứ nhất ghi hai số nguyên dương n, k (1 ≤ n ≤ 50000, 0 ≤ k ≤ 10⁶).
• Dòng thứ hai ghi n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶, i = 1..n).

Kết quả: Ghi vào tệp văn bản TRANGTRI.OUT gồm một dòng ghi một số nguyên dương là số cây được chọn nhiều nhất để lắp đèn trang trí.

Ví dụ:

TRANGTRI.INP	TRANGTRI.OUT
8 2 4 10 9 3 8 4 7 9	5

Giải thích: Các cây được chọn có chiều cao lần lượt là 10, 9, 8, 7, 9.

Ràng buộc:

• Có 80% số test tương ứng 80% số điểm có n ≤ 1000 và k ≤ 10⁶;
• Có 10% số test tương ứng 10% số điểm có n ≤ 50000 và k ≤ 10²;
• Có 10% số test tương ứng 10% số điểm có n ≤ 50000 và k ≤ 10⁶.