HSG THPT Tây Ninh 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO TÂY NINH ĐỀ THI CHÍNH THỨC
(Buổi 1: 4 trang, buổi 2: 5 trang)

KỲ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH Năm học 2024-2025
Môn thi: Tin học - Ngày thi: 25 và 26 tháng 09 năm 2024
Thời gian làm bài: 180 phút mỗi buổi (không kể thời gian giao đề)

---

Buổi thi thứ nhất (25/9/2024)

	Tên bài	File chương trình	File dữ liệu vào	File kết quả
Bài 1	Bản nhạc hoàn hảo	MUSIC.*	MUSIC.INP	MUSIC.OUT
Bài 2	Lễ hội bánh trung thu	CAKE.*	CAKE.INP	CAKE.OUT
Bài 3	Bảo tồn rừng quốc gia	TREE.*	TREE.INP	TREE.OUT

Dấu * có thể được thay thế bởi CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là C++ hoặc Python.

Bài 1. Bản nhạc hoàn hảo (6 điểm)

Tại thành phố T, nơi nổi tiếng với các bản nhạc đàn ca tài tử, một cuộc thi sáng tác nhạc đã được tổ chức nhằm tìm kiếm bản nhạc hay nhất để trình diễn trong Lễ hội Ánh Trăng. Các nghệ sĩ trong cuộc thi phải sáng tác những bản nhạc kết hợp từ hai loại nhạc cụ chính là đàn kìm và đàn tranh, bản nhạc là sự kết nối của nhiều đoạn nhạc, trong đó mỗi đoạn chỉ chơi 1 loại đàn và không có 2 đoạn liên tiếp nào có cùng loại đàn. Ban giám khảo đã đưa ra tiêu chí đánh giá độ hấp dẫn của mỗi bản nhạc dựa trên độ hấp dẫn của các đoạn nhạc liên tiếp sử dụng hai loại nhạc cụ này.

Có tổng cộng N đoạn nhạc được đánh số từ 1 đến N, đoạn thứ i được chơi bởi một trong hai loại nhạc cụ trên và có một độ hấp dẫn A_i (1 ≤ i ≤ N) tương ứng, được biểu diễn dưới dạng một số nguyên.

Một bản nhạc hoàn hảo phải thỏa mãn các điều kiện sau:

• Có ít nhất 4 đoạn nhạc liên tiếp.
• Số lượng đoạn nhạc sử dụng đàn kìm và đàn tranh phải bằng nhau.

Độ hấp dẫn của một bản nhạc hoàn hảo được tính bằng tổng độ hấp dẫn của các đoạn nhạc liên tiếp đó.

Yêu cầu: Hãy tìm và tính độ hấp dẫn lớn nhất của một bản nhạc hoàn hảo có thể được trình diễn.

Dữ liệu: Vào từ file MUSIC.INP có cấu trúc như sau:

• Dòng đầu chứa số nguyên dương N (4 ≤ N ≤ 3.10⁵) - số lượng đoạn nhạc.
• Dòng thứ hai chứa N số nguyên A₁, A₂, …, A_N (|A_i| ≤ 10⁹ với 1 ≤ i ≤ N), mỗi số đại diện cho độ hấp dẫn của một đoạn nhạc (có thể là dương hoặc âm). Hai số liên tiếp được ghi cách nhau bởi một dấu cách.

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

• Một số nguyên duy nhất là độ hấp dẫn lớn nhất của một bản nhạc hoàn hảo có thể được trình diễn.

Ví dụ:

MUSIC.INP	MUSIC.OUT
7 -3 6 4 -5 -2 7 1	11

Giải thích: Bản nhạc gồm 6 đoạn có số thứ tự 2, 3, 4, 5, 6, 7 sẽ có độ hấp dẫn là 6 + 4 + (−5) + (−2) + 7 + 1 = 11

Ràng buộc:

• Subtask 1 (50%): N ≤ 300
• Subtask 2 (30%): 300 < N ≤ 5000
• Subtask 3 (20%): 5000 < N ≤ 3.10⁵

Bài 2. Lễ hội bánh trung thu (7 điểm)

Trong lễ hội Trung thu tại một làng quê nổi tiếng với nghề làm bánh, có N loại bánh trung thu đặc biệt được bày bán, mỗi chiếc bánh được đánh số từ 1 đến N. Mỗi chiếc bánh trung thu không chỉ có vẻ ngoài đẹp mắt mà còn mang trong mình một giá trị đặc biệt về hương vị, được mô tả bằng giá trị A_i của bánh thứ i.

Trong lễ hội, người tham gia được phép chọn bánh trong K lượt chơi. Mỗi lượt, người chơi sẽ chọn một chiếc bánh để thưởng thức và họ sẽ nhận được một điểm thưởng dựa trên giá trị của chiếc bánh đã chọn. Điểm số trong lượt thứ i của người chơi sẽ là i × giá trị của chiếc bánh đã chọn trong lượt đó.

Tuy nhiên, có một điều kiện đặc biệt: người chơi không thể chọn những chiếc bánh quá xa nhau. Cụ thể, nếu ở lượt thứ i người chơi chọn chiếc bánh có số thứ tự p_i, thì phải đảm bảo 1 ≤ p_i − p_i-1 ≤ M.

Nhiệm vụ của bạn là tính tổng điểm thưởng cao nhất mà người chơi có thể đạt được sau K lượt chọn bánh.

Dữ liệu: Vào từ tệp văn bản CAKE.INP trong đó:

• Dòng đầu tiên ghi 3 số nguyên N, M, K (M ≤ N ≤ 2×10⁵, K ≤ min(N, 200)) - số bánh, khoảng cách chọn bánh và số lượt chọn.
• Dòng tiếp theo gồm N số nguyên dương A₁, A₂, …, A_N (1 ≤ A_i ≤ 10⁹) - các giá trị của mỗi cái bánh.

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

• In ra một số nguyên duy nhất là tổng điểm thưởng cao nhất mà người chơi có thể đạt được.

Ví dụ:

CAKE.INP	CAKE.OUT
7 6 3 1 10 1 4 6 3 8	46
7 6 3 3 10 1 4 6 3 8	47

Giải thích

• Test 1: Ta chọn các cái bánh ở vị trí 2, 5 và 7. Tổng điểm sẽ là 1×10 + 2×6 + 3×8 = 46
• Test 2: Ta chọn các cái bánh ở vị trí 1, 2 và 7. Tổng điểm sẽ là 1×3 + 2×10 + 3×8 = 47

Ràng buộc:

• Subtask 1 (50%): N ≤ 20
• Subtask 2 (30%): M ≤ 100, K ≤ 20
• Subtask 3 (20%): Không có ràng buộc gì thêm.

Bài 3. Bảo tồn rừng quốc gia (7 điểm)

Rừng quốc gia CR đang được chính quyền địa phương và các tổ chức bảo tồn môi trường theo dõi chặt chẽ để đảm bảo sự phát triển bền vững. Khu rừng này bắt đầu từ một khu bảo tồn ban đầu, được đánh số 0, số khu bảo tồn n bằng 1, từ đó các khu vực rừng mới dần dần được mở rộng. Mỗi khi một khu vực rừng mới được phát triển, nó sẽ được kết nối với một khu vực rừng hiện có.

Tuy nhiên, các tổ chức bảo tồn cũng cần quản lý rừng một cách khoa học. Đôi khi, một số khu vực rừng sẽ bị tách ra khỏi hệ thống quản lý do thiên tai hoặc can thiệp từ bên ngoài và toàn bộ hệ thống con của nó cũng bị tách ra khỏi hệ thống quản lý. Ngoài ra, họ cần thường xuyên kiểm tra số lượng cây xanh và khu vực còn được bảo vệ trong một khu vực rừng cụ thể. Có thể hình dung hệ thống quản lý rừng giống như đồ thị dạng cây nhưng luôn biến đổi một cách tự nhiên.

Cụ thể, có q truy vấn về việc quản lý rừng, bao gồm các hoạt động sau:

• 1: + u (0 ≤ u < n): Mở rộng thêm một khu vực rừng mới có nhãn i = n, và n tăng thêm 1. Nối khu vực i vào khu vực u, và lúc này u sẽ là cha (tổ tiên trực tiếp) của i.
• 2: − u (0 ≤ u < n): Xóa bỏ khu vực u và hệ thống con của u.
• 3: ? u (0 ≤ u < n): Báo cáo số lượng khu vực rừng u và hệ thống con của nó, bao gồm chính khu vực u.

Với mỗi truy vấn loại 3, bạn hãy in ra kết quả của câu hỏi đó.

Dữ liệu: Vào từ tệp văn bản TREE.INP trong đó:

• Dòng đầu tiên gồm số q (1 < q ≤ 10⁵) - số lượng truy vấn.
• q dòng tiếp theo dòng thứ i lần lượt chứa ký tự c và số u cho biết nội dung của truy vấn. Đề bài bảo đảm các điều kiện tại ngay trước thời điểm hỏi của mỗi truy vấn: c thuộc ”+, −, ?”, 0 ≤ u < n và u chưa bị xóa.

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

• Với mỗi lượt truy vấn loại 3, in ra một số nguyên duy nhất là số khu vực rừng đang được bảo vệ trong hệ thống con của khu vực u bao gồm cả chính u.

Ví dụ:

TREE.INP	TREE.OUT
8 + 0 + 0 + 0 - 1 ? 0 + 2 - 3 ? 2	3 2

Giải thích: Với truy vấn loại 3 đầu tiên (? 0), cây gốc 0 chỉ còn 2 nút con là 2 và 3, xuất ra 3 vì đếm cả nút 0.

Ràng buộc:

• Subtask 1 (50%): q ≤ 10³
• Subtask 2 (30%): Không tồn tại truy vấn loại 2
• Subtask 3 (20%): q ≤ 10⁵

Buổi thi thứ hai (26/9/2024)

	Tên bài	File chương trình	File dữ liệu vào	File kết quả
Bài 1	Cứu trợ khẩn cấp trong bão lũ	COVER.*	COVER.INP	COVER.OUT
Bài 2	Đánh giá hiệu quả doanh nghiệp	GROUP.*	GROUP.INP	GROUP.OUT
Bài 3	Cuộc đua khám phá vùng đất bí ẩn	SHORTEST.*	SHORTEST.INP	SHORTEST.OUT

Dấu * có thể được thay thế bởi CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là C++ hoặc Python.

Bài 1. Cứu trợ khẩn cấp trong bão lũ (6 điểm)

Thành phố X vừa trải qua một trận lũ lớn do ảnh hưởng của cơn bão Y, gây ngập lụt nhiều khu vực dọc theo sông H. Chính quyền địa phương đã huy động lực lượng cứu hộ và các đoàn tình nguyện để triển khai công tác cứu trợ tại các khu vực bị ngập lụt nặng nhất. Các đội cứu trợ sẽ thực hiện phân phát nhu yếu phẩm và hỗ trợ người dân dọc theo các đoạn đê bảo vệ thành phố.

Có tổng cộng N đoạn đê được theo dõi, các đoạn đê được đánh số từ 1 đến N, đoạn thứ i có độ dài nhất định và được mô tả bằng hai tọa độ: tọa độ L_i (đầu mút bên trái) và tọa độ R_i (đầu mút bên phải). Đoạn đê từ tọa độ L_i đến R_i là khu vực mà lực lượng cứu hộ có thể tiếp cận và triển khai cứu trợ. Ta nói rằng, một điểm có tọa độ x được bao phủ bởi đoạn i khi và chỉ khi x nằm giữa hai đầu mút của i (tức là L_i ≤ x ≤ R_i).

Có Q yêu cầu cứu trợ khẩn cấp được chính quyền gửi tới. Mỗi yêu cầu là một đoạn dọc theo hệ thống đê từ a đến b, mô tả phạm vi các khu vực đang chịu thiệt hại nghiêm trọng và cần được cứu trợ ngay lập tức.

Nhiệm vụ của bạn là tính toán số lượng ít nhất các đoạn đê cần triển khai lực lượng cứu trợ để có thể bao phủ toàn bộ các điểm có toạ độ nguyên từ a đến b. Nếu không thể thực hiện được, hãy trả về −1.

Dữ liệu: Vào từ tệp văn bản COVER.INP trong đó:

• Dòng đầu tiên gồm số nguyên N (1 ≤ N ≤ 200000) - số đoạn đê.
• N dòng tiếp theo, dòng thứ i gồm hai số nguyên L_i và R_i (0 ≤ L_i ≤ R_i ≤ 10⁹) - tọa độ hai đầu mút của đoạn đê thứ i.
• Dòng tiếp theo gồm số nguyên Q (1 ≤ Q ≤ 200000) - số yêu cầu cứu trợ.
• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên a và b (0 ≤ a ≤ b ≤ 10⁹) mô tả một truy vấn.

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

• Với mỗi truy vấn, in ra một dòng gồm một số nguyên duy nhất là số đoạn đê ít nhất cần lựa chọn. Trong trường hợp không có cách chọn, hãy in ra −1.

Ví dụ:

COVER.INP	COVER.OUT
5 1 4 2 3 3 5 9 11 6 9 4 2 5 1 11 9 12 6 8	2 4 -1 1

Giải thích

• Với truy vấn thứ nhất, có thể chọn các đoạn thẳng 1 và 3 (hoặc 2 và 3).
• Với truy vấn thứ hai, có thể chọn các đoạn thẳng 1, 3, 4 và 5.
• Với truy vấn thứ ba, không thể chọn được các đoạn thẳng để phủ toạ độ 12 trong [9; 12].
• Với truy vấn thứ tư, có thể chọn đoạn thẳng 5.

Ràng buộc:

• Subtask 1 (50%): n ≤ 20, Q ≤ 20
• Subtask 2 (30%): n ≤ 200000, Q ≤ 20
• Subtask 3 (20%): n ≤ 200000, Q ≤ 200000.

Bài 2. Đánh giá hiệu quả doanh nghiệp (7 điểm)

Công ty XYZ vừa hoàn thành báo cáo tài chính quý và ban giám đốc đang muốn đánh giá hiệu quả hoạt động của từng chi nhánh trong công ty. Công ty có n chi nhánh, và mỗi chi nhánh i có một giá trị ước lượng a_i về hiệu quả kinh doanh (giá trị này có thể âm nếu chi nhánh thua lỗ).

Ban giám đốc sẽ dựa vào các giá trị ước lượng này để tính toán độ chênh lệch hiệu quả kinh doanh như sau:

1. Ban giám đốc chia công ty thành các nhóm, mỗi nhóm sẽ gồm một số các chi nhánh liên tiếp nhau a_l, a_l+1, …, a_r nào đó. Mỗi chi nhánh sẽ thuộc đúng một nhóm.
2. Với mỗi nhóm, ban giám đốc sẽ chọn một chi nhánh để đưa vào danh sách kinh doanh tốt, và một chi nhánh để đưa vào danh sách kinh doanh kém (một chi nhánh có thể thuộc cả hai nhóm kinh doanh này).
3. Độ chênh lệch của một cách chia và chọn sẽ bằng tổng số giá trị ước lượng của các chi nhánh kinh doanh tốt, trừ cho tổng số giá trị ước lượng của các chi nhánh kinh doanh kém.
4. Độ chênh lệch của công ty sẽ bằng độ chênh lệch tối đa của mọi cách chia nhóm và danh sách chi nhánh kinh doanh tốt, kém.

Công việc của ban giám đốc là tối ưu hóa việc chia nhóm và chọn chi nhánh để tối đa hóa độ chênh lệch này.

Trong quá trình phân tích, có q sự kiện diễn ra, bao gồm:

1. Một số chi nhánh nhận thấy kết quả kinh doanh của họ thay đổi do điều kiện thị trường và điều chỉnh lại giá trị ước lượng của mình.
2. Ban giám đốc muốn tính toán lại độ chênh lệch của công ty dựa trên thông tin hiện tại.

Dữ liệu: Vào từ tệp văn bản GROUP.INP trong đó:

• Dòng đầu chứa hai số nguyên n, q (1 ≤ n, q ≤ 200000) là số chi nhánh và số sự kiện.
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (|a_i| ≤ 10⁸) mô tả giá trị ước lượng hiệu quả kinh doanh của từng chi nhánh.
• Tiếp theo là q dòng, mỗi dòng mô tả một sự kiện:
  • 1 l r x: Giá trị ước lượng hiệu quả kinh doanh của các chi nhánh từ l đến r tăng lên x.
  • 2: Ban giám đốc muốn tính toán lại độ chênh lệch của công ty.

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

• Với mỗi sự kiện loại 2, in ra kết quả là độ chênh lệch của công ty.

Ví dụ:

GROUP.INP	GROUP.OUT
4 4 -1 5 -6 10 1 4 4 3 2 1 1 2 -5 2	25 25

Giải thích

Với sự kiện loại 2 đầu tiên, hiệu quả kinh doanh của từng chi nhánh là [−1, 5, −6, 13]. Được chia thành 2 nhóm liên tiếp là [−1, 5] và [−6, 13]. Nhóm đầu tiên chọn mẫu tốt nhất là 5, mẫu kém nhất là −1, nhóm thứ hai chọn mẫu tốt nhất là 13, mẫu kém nhất là −6. Độ chênh lệch kinh doanh của công ty là 5 + 13 − (−1 − 6) = 25.

Ràng buộc:

• Subtask 1 (50%): 1 ≤ n, q ≤ 200
• Subtask 2 (30%): 1 ≤ n, q ≤ 1000
• Subtask 3 (20%): không có ràng buộc gì thêm.

Bài 3. Cuộc đua khám phá vùng đất bí ẩn (7 điểm)

Nam là một nhà thám hiểm trẻ đầy nhiệt huyết, luôn khao khát khám phá những vùng đất mới. Một ngày nọ, Nam nhận được lời mời tham gia vào một cuộc đua khám phá đặc biệt từ Hội Địa lý Quốc tế. Mục tiêu của cuộc đua là đi qua các thành phố chưa ai từng khám phá, và hoàn thành hành trình từ thành phố U tới thành phố V.

Nhưng đây không phải là một cuộc đua bình thường. Để tăng thêm thử thách và trải nghiệm, Hội yêu cầu các thám hiểm gia phải kết hợp cả hai phương tiện di chuyển: đường bộ và đường sắt. Hành trình của Nam phải tuân theo những nguyên tắc sau:

1. Nam phải bắt đầu từ thành phố U và kết thúc ở thành phố V.
2. Trên đường đi, Nam phải chọn một thành phố Z để làm điểm trung chuyển.
3. Từ U đến Z, Nam có thể chọn đi bằng đường bộ hoặc đường sắt.
4. Từ Z đến V, Nam phải sử dụng phương tiện khác so với chặng đầu tiên (nếu chặng đầu đi bằng đường bộ, thì chặng sau phải đi bằng đường sắt và ngược lại).

Đặc biệt, Hội Địa lý Quốc tế đã chuẩn bị sẵn một bản đồ mật chứa các thông tin chi tiết về khoảng cách giữa các thành phố thông qua cả đường bộ và đường sắt. Nhưng chỉ những người thông minh và nhanh nhạy mới có thể tính toán được khoảng cách ngắn nhất để hoàn thành hành trình.

Nam rất háo hức tham gia vào cuộc đua này, nhưng anh ấy cần sự trợ giúp để tìm ra con đường ngắn nhất và giành chiến thắng trước các đối thủ. Bạn có sẵn sàng giúp Nam tìm ra lộ trình hoàn hảo để chinh phục cuộc đua này không?

Dữ liệu: Vào từ tệp văn bản SHORTEST.INP trong đó:

• Dòng đầu tiên gồm 3 số nguyên dương N, M1, M2 (3 ≤ N ≤ 3×10⁴, M1, M2 ≤ 3×10⁵), tương ứng với số thành phố, số đường bộ và số đường sắt.
• M1 dòng tiếp theo mô tả các con đường bộ có hướng, mỗi con đường gồm 3 số nguyên a_i, b_i, w_i (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i, 0 < w_i ≤ 100) con đường bộ từ a_i đến b_i có khoảng cách w_i.
• M2 dòng tiếp theo mô tả các con đường sắt có hướng, mỗi con đường gồm 3 số nguyên a_j, b_j, w_j (1 ≤ a_j, b_j ≤ N, a_j ≠ b_j, 0 < w_j ≤ 100) con đường sắt từ a_j đến b_j có khoảng cách w_j.
• Dòng cuối gồm 2 số nguyên phân biệt U và V (1 ≤ U, V ≤ N, U ≠ V), là điểm bắt đầu và điểm kết thúc. Nó đảm bảo rằng bài toán đã cho có nghiệm.

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

• Đưa ra số nguyên, khoảng cách nhỏ nhất thỏa mãn các điều kiện trên khi đi từ U tới V.

Ví dụ:

SHORTEST.INP	SHORTEST.OUT	Giải thích
3 6 6 1 2 1 1 3 2 2 1 3 2 3 4 3 1 5 3 2 6 1 2 6 1 3 5 2 1 1 2 3 4 3 1 3 3 2 2 1 2	4	Đi từ 1 tới 3 bằng đường bộ, từ 3 tới 2 bằng đường sắt. Khoảng cách giữa 1 và 3 bằng đường bộ là 2. Khoảng cách giữa 3 và 2 bằng đường sắt là 2. Tổng khoảng cách bằng 4.

Ràng buộc:

• Subtask 1 (50%): N ≤ 300
• Subtask 2 (30%): N ≤ 3000
• Subtask 3 (20%): N ≤ 30000

---

Hết