Chọn đội tuyển HSG quốc gia Quảng Ngãi 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO QUẢNG NGÃI ĐỀ CHÍNH THỨC
(Ngày 1: 04 trang, ngày 2: 03 trang)

KỲ THI CHỌN HSG CẤP TỈNH THAM DỰ KỲ THI CHỌN HSG QUỐC GIA THPT Năm học 2025 - 2026
Môn: Tin học - Ngày thi: 18/9/2025 và 19/9/2025
Thời gian làm bài: 180 phút mỗi ngày

---

Ngày thi thứ nhất (18/9/2025)

Tên bài	File chương trình	File dữ liệu vào	File kết quả	Thời gian
Bài 1	SDB.*	SDB.INP	SDB.OUT	1 giây/test
Bài 2	THUHOACH.*	THUHOACH.INP	THUHOACH.OUT	1 giây/test
Bài 3	THUENV.*	THUENV.INP	THUENV.OUT	1 giây/test

Dấu * là PAS hoặc CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++ hoặc Python.

Bài 1. Số đặc biệt (7,0 điểm)

Một số nguyên dương x bất kỳ luôn phân tích được ra thành tích các thừa số nguyên tố. Nghĩa là ta sẽ có x = p1^k1 × p2^k2 × … × pz^kz với p_i (1 ≤ i ≤ z) là số nguyên tố.

Số x được gọi là đặc biệt nếu GCD(k₁, k₂, …, kz) = 1, với GCD(k₁, k₂, …, kz) là ước chung lớn nhất của k₁, k₂, …, kz.

Yêu cầu: Cho M truy vấn, với mỗi truy vấn, cho số nguyên N, tính số lượng các số đặc biệt trong phạm vi từ 2 đến N.

Dữ liệu vào từ file văn bản SDB.INP có cấu trúc:

• Dòng thứ nhất chứa số nguyên M (M ≤ 10⁴).
• M dòng tiếp theo, mỗi dòng chứa số nguyên N (2 ≤ N ≤ 10¹⁸).

Kết quả ghi ra file văn bản SDB.OUT có cấu trúc:

• In ra trên M dòng, mỗi dòng ghi một số nguyên là số lượng số đặc biệt trong phạm vi từ 2 đến N ứng với truy vấn tương ứng.

Ví dụ:

SDB.INP	SDB.OUT
2 10 6	6 4

Ràng buộc:

• Subtask 1: 40% số test có M = 1, N ≤ 10⁴.
• Subtask 2: 30% số test có M ≤ 10⁴, N ≤ 10⁶.
• Subtask 3: 30% số test có M ≤ 10⁴, N ≤ 10¹⁸.

Bài 2. Thu hoạch (7,0 điểm)

An chuyên trồng một loại cây ăn quả, mỗi đợt từ lúc trồng cho đến khi thu hoạch sẽ mất 3 năm. Vào đầu năm thứ nhất, sẽ bắt đầu trồng cây. Đến năm thứ hai, cây phát triển đến một chiều cao nhất định. Vào năm thứ ba, một số cây ra quả sẽ được thu hoạch.

Vườn của An chia làm n khu đất, đánh số từ 1 đến n từ trái sang phải. Mỗi khu đất được trồng một cây, cây được trồng tại khu đất i có chiều cao h_i. Cuối năm thứ hai cây không tăng chiều cao nữa. Cây i nếu ra quả sẽ bán được p_i đồng. Ngược lại nó không có giá trị.

Cuối năm thứ hai, An quyết định chọn chặt bỏ một số cây để tăng lợi sau này. Vì cây cần rất nhiều ánh sáng để phát triển và ra quả vào năm thứ ba. Để chặt bỏ cây thứ i mất chi phí là c_i đồng. Cây i không ra quả nếu đồng thời thỏa hai điều kiện sau:

• Tồn tại cây j (1 ≤ j < i) sao cho h_j > h_i.
• Tồn tại cây k (i < k ≤ n) sao cho h_i < h_k.

Lợi nhuận An kiếm được là tổng tiền thu được từ việc thu hoạch các cây ra quả trừ đi tiền chặt cây vào cuối năm thứ hai.

Yêu cầu: Xác định lợi nhuận tối đa mà An có thể thu được.

Dữ liệu vào từ file văn bản THUHOACH.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên dương n (3 ≤ n ≤ 10⁵).
• n dòng tiếp theo chứa 3 số nguyên dương h_i, p_i, c_i (1 ≤ h_i, p_i, c_i ≤ 10⁹, 1 ≤ i ≤ n).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả ghi ra file văn bản THUHOACH.OUT có cấu trúc:

• Ghi ra một số nguyên là lợi nhuận tối đa mà An thu được.

Ví dụ:

THUHOACH.INP	THUHOACH.OUT
3 3 4 2 7 2 5 9 4 8	10
5 6 5 3 5 9 6 15 3 3 7 15 4 8 2 6	20

Ràng buộc:

• Subtask 1: 20% số test có h₁ ≤ h₂ ≤ … ≤ h_n.
• Subtask 2: 20% số test có n ≤ 300.
• Subtask 3: 30% số test có n ≤ 5000.
• Subtask 4: 30% số test còn lại không có ràng buộc gì thêm.

Bài 3. Thuê nhân viên (6,0 điểm)

Công ty XYZ có n nhân viên được đánh số từ 1 đến n, trong đó có một người được chọn làm ông chủ. Để tăng độ hài lòng của các khách hàng, ông chủ quyết định thuê chính nhân viên đang làm việc trong công ty của mình đến trao đổi và giao dịch với khách hàng của mình.

Ngoài ông chủ thì mỗi nhân viên khác có đúng một sếp. Để nhiệm vụ được bảo mật, mọi chỉ thị chỉ được truyền từ sếp xuống cấp dưới và không có chiều ngược lại. Ông chủ chỉ trả tiền cho nhân viên được thuê.

Để giao nhiệm vụ, ông chủ hoặc là người quản lý hoặc nhờ nhân viên làm quản lý. Người quản lý này phải có khả năng truyền thông tin về nhiệm vụ cho tất cả các nhân viên được thuê. Khi nhiệm vụ được giao, một nhân viên không được thuê có thể làm trung gian để truyền đạt nhiệm vụ. Nhân viên được nhờ làm quản lý không nhất thiết phải được thuê làm nhân viên giao dịch.

Với số tiền để thuê nhân viên trong đợt này là M, ông chủ muốn thuê nhân viên sao cho khách hàng hài lòng nhất có thể. Độ hài lòng của khách hàng được tính bằng số lượng nhân viên được thuê nhân với kinh nghiệm quản lý của người quản lý.

Yêu cầu: Biết nhân viên thứ i có sếp là B_i, số tiền phải trả khi thuê là C_i, kinh nghiệm quản lý là L_i. Tính độ hài lòng tối đa đạt được khi thuê nhân viên của ông chủ.

Dữ liệu vào từ file văn bản THUENV.INP có cấu trúc:

• Dòng thứ nhất chứa hai số nguyên dương n, M (1 ≤ n ≤ 10⁵, 1 ≤ M ≤ 10⁹).
• Dòng thứ i trong n dòng tiếp theo chứa ba số nguyên B_i, C_i, L_i lần lượt là sếp, số tiền thuê, và kinh nghiệm quản lý của nhân viên i. Ông chủ là người có B_i bằng 0. Vì B_i < i nên với mỗi nhân viên, chỉ số của sếp luôn nhỏ hơn chỉ số của nhân viên (0 ≤ B_i < i, 1 ≤ C_i ≤ M, 1 ≤ L_i ≤ 10⁹, 1 ≤ i ≤ n).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả ghi ra file văn bản THUENV.OUT có cấu trúc:

• Ghi một số nguyên là độ hài lòng tối đa đạt được.

Ví dụ:

THUENV.INP	THUENV.OUT
5 4 0 3 3 1 3 5 2 2 2 1 2 4 2 3 1	6

Giải thích: Ông chủ là 1 và ông làm quản lý thuê hai nhân viên 3, 4.

Ràng buộc:

• Subtask 1: 40% số test có n ≤ 300.
• Subtask 2: 30% số test có n ≤ 10⁴.
• Subtask 3: 30% số test có n ≤ 10⁵.

Ngày thi thứ hai (19/9/2025)

Tên bài	File chương trình	File dữ liệu vào	File kết quả	Thời gian
Bài 4	QNROAD.*	QNROAD.INP	QNROAD.OUT	1s/test
Bài 5	ROBOT.*	ROBOT.INP	ROBOT.OUT	1s/test
Bài 6	SPECK.*	SPECK.INP	SPECK.OUT	1s/test

Dấu * là 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 4 (7 điểm)

Giám đốc công ty XYZ xây dựng kế hoạch thuê nhân công để làm dự án đường cao tốc kết nối Đông - Tây của tỉnh Quảng Ngãi. Dự án cần triển khai trong n tháng được đánh số từ 1 đến n. Biết rằng bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí trả cho nhà tuyển dụng là H. Mỗi tháng, mỗi nhân công được thuê sẽ được trả một khoản lương S kể cả không làm việc. Kết thúc một tháng, dự án có quyền sa thải nhân công hoặc không. Để sa thải mỗi nhân công cần trả một khoản chi phí D.

Trước khi dự án bắt đầu thì chưa có nhân công nào. Tháng thứ i của dự án cần tối thiểu a_i nhân công. Kết thúc tháng thứ n, toàn bộ nhân công bị sa thải.

Yêu cầu: Hãy giúp Giám đốc xây dựng kế hoạch thuê nhân công để dự án hoàn thành với chi phí thuê nhân công ít nhất có thể.

Dữ liệu: Vào từ file văn bản QNROAD.INP có cấu trúc:

• Dòng thứ nhất chứa số nguyên n (1 ≤ n ≤ 4 × 10⁵).
• Dòng thứ hai chứa ba số nguyên H, S, D (H, S, D ≤ 10⁶).
• Dòng thứ ba chứa n số nguyên dương a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁶).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản QNROAD.OUT có cấu trúc:

• Một số nguyên là chi phí tối thiểu tìm được.

Ví dụ:

QNROAD.INP	QNROAD.OUT
4 7 8 9 22 24 29 34	1416

Ràng buộc:

• Subtask 1 (40% số điểm): n ≤ 10³.
• Subtask 2 (30% số điểm): n ≤ 10⁵.
• Subtask 3 (30% số điểm): Không có ràng buộc nào thêm.

Bài 5 (7 điểm)

Trên sân hình vuông có n × n ô vuông, các dòng và cột được đánh số từ 1 đến n. Tại mỗi ô (i, j) hoặc chứa chướng ngại vật hoặc ghi số nguyên a_i,_j (1 ≤ i, j ≤ n; −1 ≤ a_i,_j ≤ 10⁶). Nếu a_i,_j = −1 thì ô đó là chướng ngại vật. Robot nhận nhiệm vụ di chuyển từ ô (1, 1) đến ô (n, n). Tại ô (i, j) robot chỉ được di chuyển sang ô (i, j + 1) hoặc (i + 1, j), không được di chuyển ra khỏi sân, không được di chuyển vào ô có chướng ngại vật. Nếu đến được đích thì điểm thưởng sẽ được tính bằng tích của tất cả các số ghi trên các ô mà nó đi qua. Để tăng độ khó, người ta yêu cầu điểm thưởng phải là bội của một số nguyên k cho trước.

Yêu cầu: Đếm số đường đi mà robot đi đến được đích sao cho điểm thưởng là bội số của một số nguyên k cho trước, kết quả lấy modulo 998244353.

Dữ liệu: Vào từ file văn bản ROBOT.INP có cấu trúc:

• Dòng thứ nhất chứa 2 số nguyên n, k (1 ≤ n ≤ 500; 1 ≤ k ≤ 10⁶).
• n dòng tiếp theo, dòng thứ i chứa n số nguyên a_i,_j (1 ≤ i, j ≤ n).

Các số trên một dòng cách nhau bởi một dấu cách.

Kết quả: Ghi ra file văn bản ROBOT.OUT có cấu trúc:

• Ghi số lượng đường đi thỏa mãn yêu cầu sau khi modulo 998244353.

Ví dụ:

ROBOT.INP	ROBOT.OUT
2 2 3 6 3 2	2
4 3 2 6 -1 6 7 -1 3 5 7 1 5 1 2 3 3 5	3

Ràng buộc:

• Subtask 1 (40% số điểm): n ≤ 500; k = 1.
• Subtask 2 (15% số điểm): n ≤ 500; k = 2.
• Subtask 3 (15% số điểm): n ≤ 100; k ≤ 20.
• Subtask 4 (30% số điểm): Không có ràng buộc nào thêm.

Bài 6 (6 điểm)

Cho đồ thị n đỉnh được đánh số từ 1 đến n và m cạnh. Cạnh thứ i nối hai đỉnh u_i, v_i (1 ≤ i ≤ m). Đồ thị đảm bảo luôn có đường đi giữa hai đỉnh bất kì và giữa hai đỉnh có thể có nhiều cạnh nối giữa chúng.

Đường đi từ a đến b được biểu diễn bằng dãy các đỉnh a = x₁x₂…x_p = b, với 1 ≤ x_i ≤ n, (x_i, x_i+1) là một cạnh của đồ thị (1 ≤ i ≤ p − 1). Cạnh (x_i, x_i+1) được gọi là cạnh đặc biệt trên đường đi từ a đến b nếu mọi đường đi từ a đến b phải qua cạnh (x_i, x_i+1).

Yêu cầu: Cho số nguyên k. Tính số lượng cặp đỉnh (a, b) (a < b) sao cho mọi đường đi từ a đến b qua ít nhất k cạnh đặc biệt.

Dữ liệu: Vào từ file văn bản SPECK.INP có cấu trúc:

• Dòng thứ nhất chứa 3 số nguyên n, m, k (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵, k ≤ 10⁵).
• Dòng thứ i trong m dòng tiếp theo chứa hai số nguyên u_i, v_i (u_i ≠ v_i; 1 ≤ i ≤ m).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản SPECK.OUT có cấu trúc:

• Ghi một số nguyên là số lượng cặp đỉnh (a, b) (a < b) sao cho mọi đường đi từ a đến b qua ít nhất k cạnh đặc biệt.

Ví dụ:

SPECK.INP	SPECK.OUT
6 6 3 3 6 6 5 4 5 4 6 2 1 5 1	1

Ràng buộc:

• Subtask 1 (70% số điểm): n ≤ 100.
• Subtask 2 (30% số điểm): Không có ràng buộc nào thêm.

---

Giám thị không giải thích gì thêm.