HSG lớp 12 Đà Nẵng 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ ĐÀ NẴNG ĐỀ CHÍNH THỨC
(Đề thi có 02 trang)

KÌ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP THÀNH PHỐ Năm học 2023 - 2024
Môn: Tin học
Thời gian làm bài: 150 phút (không kể thời gian giao đề)

---

Tổng quan

Câu	Tên bài	File chương trình	Dữ liệu vào	Dữ liệu ra	Điểm
1	Tính tổng	TONG.*	TONG.INP	TONG.OUT	3.0
2	Shipper	SHIPPER.*	SHIPPER.INP	SHIPPER.OUT	3.0
3	Độ đẹp	DODEP.*	DODEP.INP	DODEP.OUT	2.0
4	Hội báo xuân	HBAOXUAN.*	HBAOXUAN.INP	HBAOXUAN.OUT	2.0

Chú ý: Dấu * có thể là pas, c, cpp hoặc py tùy theo ngôn ngữ và môi trường lập trình.

Câu 1. Tính tổng

Viết chương trình nhập vào một số nguyên dương N. Hãy cho biết tổng các số nguyên dương bé hơn N là bao nhiêu.

Dữ liệu vào: Đọc từ file văn bản TONG.INP một số nguyên dương N.

Dữ liệu ra: Ghi vào file văn bản TONG.OUT số nguyên theo yêu cầu đề bài.

Giới hạn

• Có 80% test tương ứng với N ≤ 10⁶;
• Có 20% test tương ứng với N ≤ 10⁹.

Ví dụ

TONG.INP	TONG.OUT	Giải thích
5	10	1 + 2 + 3 + 4 = 10

Câu 2. Shipper

Tý là một shipper, hàng ngày Tý đến kho hàng để nhận hàng và giao cho khách. Trong kho hàng có N gói hàng có nhiều màu sắc, các gói hàng có cùng màu sắc sẽ kí hiệu bằng một số giống nhau. Mỗi ngày Tý chỉ có thể giao tối đa M gói hàng, nếu Tý nhận nhiều hơn M gói hàng anh sẽ không thể giao hết và sẽ bị trừ lương. Tý có thể chọn một màu và quản lí sẽ đưa cho Tý tất cả các gói hàng có màu mà Tý đã chọn. Hãy giúp Tý tìm xem số gói hàng tối đa mà Tý có thể chọn để giao trong ngày hôm đó là bao nhiêu.

Dữ liệu vào: được đọc từ file văn bản SHIPPER.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương N và M.
• Dòng thứ 2 chứa N số nguyên dương lần lượt là kí hiệu các gói hàng.

Dữ liệu ra: Ghi vào file văn bản SHIPPER.OUT số nguyên theo yêu cầu đề bài.

Ví dụ

SHIPPER.INP	SHIPPER.OUT	Giải thích
15 5 1 3 1 4 1 2 3 2 3 2 1 1 1 3 1	4	Tý không thể chọn gói hàng số 1 vì có tất cả 7 gói, do đó Tý chọn gói hàng số 3 và có 4 gói

Giới hạn

• Có 40% test tương ứng với N, M ≤ 10;
• Có 60% test tương ứng với N ≤ 10⁵.

Câu 3. Độ đẹp

Có n viên bi bố trí cách đều theo hàng ngang và được đánh số thứ tự từ 1 đến n. Viên bi thứ i (1 ≤ i ≤ n) có độ đẹp là a_i. Tiến hành thực hiện q lần một trong hai loại thao tác sau trên dãy các viên bi này:

• 1 i x: Thay viên bi tại vị trí thứ i bằng một viên bi khác có độ đẹp x (1 ≤ i ≤ n, −10⁹ ≤ x ≤ 10⁹).
• 2 k: Dịch chuyển các viên bi sang phải k vị trí, nếu dãy các viên bi hiện tại là a₁, a₂, …, a_n thì sau khi dịch sẽ là dãy a_n-k+1, a_n-k+2, …, a₁, a₂, …, a_n-k (1 ≤ k ≤ n).

Yêu cầu: Sau mỗi lần thực hiện thao tác loại 1, hãy tính tổng độ đẹp của dãy các viên bi đang xuất hiện trên dãy.

Dữ liệu vào: Đọc từ tệp văn bản DODEP.INP có cấu trúc như sau:

• Dòng thứ nhất chứa hai số nguyên dương n, q (1 ≤ n, q ≤ 5.10⁵) cách nhau một khoảng trắng.
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (−10⁹ ≤ a_i ≤ 10⁹) lần lượt là độ đẹp của các viên bi, các số cách nhau một khoảng trắng.
• q dòng tiếp theo, mỗi dòng mô tả một thao tác trên, các số cách nhau một khoảng trắng.

Dữ liệu ra: Tương ứng với mỗi phép toán loại 1 ghi ra tệp văn bản DODEP.OUT một số nguyên trên một dòng là tổng độ đẹp của dãy các viên bi xuất hiện trên dãy, thứ tự các kết quả theo đúng thứ tự các phép toán loại 1 trong tệp dữ liệu đầu vào.

Ví dụ:

DODEP.INP	DODEP.OUT	Giải thích
4 4 5 3 2 7 2 2 1 3 8 2 1 1 2 -6	20 12	Dãy ban đầu: 5 3 2 7 Sau phép toán thứ nhất (2 2) dãy mới sẽ là 2 7 5 3 Sau phép toán thứ hai (1 3 8) dãy mới sẽ là 2 7 8 3, có tổng bằng 20 Sau phép toán thứ ba (2 1) dãy mới sẽ là 3 2 7 8 Sau phép toán thứ tư (1 2 −6) dãy mới sẽ là 3 −6 7 8, có tổng bằng 12

Ràng buộc:

• Có 40% số test đầu với 2 ≤ n ≤ 1000 và chỉ gồm thao tác loại 1;
• Có 30% số test tiếp theo với 2 ≤ n ≤ 1000;
• Có 30% số test còn lại không giới hạn gì thêm.

Câu 4. Hội báo xuân

Thư viện Khoa học Tổng hợp Đà Nẵng phối hợp với Hội Nhà Báo TP. Đà Nẵng và CLB Nhiếp ảnh TP. Đà Nẵng tổ chức Hội Báo Xuân Giáp Thìn năm 2024, triển lãm tài nguyên thông tin và các tác phẩm nhiếp ảnh nghệ thuật chào Xuân. Những tác phẩm nhiếp ảnh nghệ thuật thường là mục tiêu của nhiều tổ chức trộm cắp chuyên nghiệp. Vì thế, ban tổ chức cần giải quyết bài toán bảo vệ an toàn cho các tác phẩm này. Theo kế hoạch, các tác phẩm được trưng bày trong n giờ, thời điểm bắt đầu cuộc triển lãm được tính bằng 0. Có m vệ sĩ nghiệp vụ cao có thể thuê để canh gác các tác phẩm. Để đơn giản, các vệ sĩ này được đánh số thứ tự từ 1 đến m. Vệ sĩ i chấp nhận đứng canh trong khoảng thời gian từ thời điểm s_i đến thời điểm t_i (0 ≤ s_i < t_i ≤ n) với tiền công là c_i (với i = 1, 2, …, n).

Yêu cầu: Hãy giúp ban tổ chức lựa chọn thuê các vệ sĩ nào trong số m vệ sĩ để bất cứ thời điểm nào diễn ra triển lãm luôn có ít nhất một vệ sĩ đứng canh, đồng thời tổng chi phí thuê trả cho các vệ sĩ đó là nhỏ nhất.

Dữ liệu vào: Đọc từ tệp văn bản HBAOXUAN.INP có cấu trúc như sau:

• Dòng đầu ghi hai số nguyên dương n và m (1 ≤ n, m ≤ 10⁵).
• Dòng thứ i trong m dòng tiếp theo chứa ba số nguyên không âm s_i, t_i, c_i (0 ≤ c_i ≤ 10⁵).

Các số trên một dòng cách nhau bởi một khoảng trắng. Dữ liệu đảm bảo luôn có lời giải.

Dữ liệu ra: Ghi ra tệp văn bản HBAOXUAN.OUT một số nguyên duy nhất là tổng chi phí nhỏ nhất để thuê các vệ sĩ.

Ví dụ:

HBAOXUAN.INP	HBAOXUAN.OUT	Giải thích
9 5 0 5 25 1 3 18 3 7 21 4 6 38 7 9 20	66	Lựa chọn ba vệ sĩ có số thứ tự lần lượt là 1, 3, 5. Tổng chi phí sử dụng để trả cho 3 vệ sĩ này là 25 + 21 + 20 = 66.

Ràng buộc:

• Có 50% số test đầu với 1 ≤ n, m ≤ 10³;
• Có 50% số test còn lại không giới hạn gì thêm.