HSG THPT Trà Vinh 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH TRÀ VINH ĐỀ THI CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH CẤP THPT Năm học 2024-2025
Môn thi: Tin học
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
(Đề thi gồm có 03 trang, 03 câu)

---

Tổng quan đề thi

Câu	Tên bài	Tên tệp chương trình	Tên tệp dữ liệu vào	Tên tệp dữ liệu ra	Điểm
1	Chiến thắng	CHIENTHANG.*	CHIENTHANG.INP	CHIENTHANG.OUT	6,0
2	Số kho báu	KHOBAU.*	KHOBAU.INP	KHOBAU.OUT	7,0
3	Sóc	SOC.*	SOC.INP	SOC.OUT	7,0

Ghi chú: Dấu * là CPP hoặc PY hoặc PAS tùy theo ngôn ngữ lập trình là C++, PYTHON hoặc PASCAL.

Câu 1 (6,0 điểm). Chiến thắng

Để tiêu diệt một vật thể có dạng khối lập phương, người chơi cần tiêu tốn một năng lượng tương ứng bằng thể tích của khối lập phương đó. Ví dụ: Để tiêu diệt khối lập phương có cạnh là 2, người chơi cần tiêu tốn 8 năng lượng.

Ban đầu, trên màn hình xuất hiện khối lập phương có độ dài cạnh là 1 để người chơi tiêu diệt. Sau khi tiêu diệt xong, màn hình tiếp tục hiển thị khối vật thể lập phương có độ dài cạnh tăng lên 1 đơn vị so với độ dài cạnh của khối lập phương được tiêu diệt trước đó. Quá trình này lặp đi lặp lại cho đến khi người chơi tiêu diệt được khối lập phương có độ dài cạnh là N thì giành chiến thắng.

Hãy cho biết người chơi cần tiêu tốn bao nhiêu năng lượng để vượt qua thử thách và giành chiến thắng?

Dữ liệu vào: Đọc từ tệp văn bản CHIENTHANG.INP chứa duy nhất một số nguyên dương N (0 < N ≤ 10¹⁶) là độ dài cạnh của khối lập phương cuối cùng cần phải tiêu diệt.

Dữ liệu ra: Ghi vào tệp văn bản CHIENTHANG.OUT một số nguyên duy nhất là tổng năng lượng cần phải tiêu tốn để giành chiến thắng trò chơi. Do tổng năng lượng có thể khá lớn nên chỉ ghi nhận kết quả sau khi chia lấy dư cho 10⁸.

Ví dụ:

CHIENTHANG.INP	CHIENTHANG.OUT	Giải thích
2	9	Thể tích từ khối thứ nhất đến khối thứ hai là 13 + 23 = 9 nên cần tiêu tốn 9 năng lượng để giành chiến thắng.
3	36	Thể tích từ khối thứ nhất đến khối thứ ba là 13 + 23 + 33 = 36 nên cần tiêu tốn 36 năng lượng để giành chiến thắng.

Giới hạn:

• Subtask 1: Có 10/12 số test tương ứng 5,0 điểm với 0 < N ≤ 10⁴.
• Subtask 2: Có 2/12 số test tương ứng 1,0 điểm với 10⁴ < N ≤ 10¹⁶.

Câu 2 (7,0 điểm). Số kho báu

Vào một ngày đẹp trời, nhà vua của vương quốc Toán học triệu tập các hiền triết và nhà thông thái để tìm ra một nhóm số bí ẩn mà ông gọi là “số kho báu”. Theo truyền thuyết, những con số này chứa đựng một sức mạnh đặc biệt: tổng tất cả các yếu tố (ước số) của chúng, ngoại trừ chính chúng, luôn lớn hơn bản thân chúng.

Nghe được điều này, Hoàng tử Toán Trí quyết định lên đường truy tìm những con số kho báu trong khoảng từ L đến R. Tuy nhiên, chàng không thể làm điều đó một mình và cần sự trợ giúp của bạn. Nhiệm vụ của bạn là giúp Hoàng tử đếm xem có bao nhiêu số kho báu trong đoạn số này.

Một số nguyên dương được gọi là số kho báu nếu tổng các ước số của nó (không tính chính nó) lớn hơn chính nó. Ví dụ, số 12 là một số kho báu vì tổng các ước số của nó là:

1 + 2 + 3 + 4 + 6 = 16 > 12

Hoàng tử cần đếm số lượng các số kho báu trong đoạn [L, R]. Liệu bạn có thể giúp Hoàng tử tìm ra những con số kho báu để mở cánh cổng bí mật của vương quốc Toán học không?

Dữ liệu vào: Đọc từ tệp văn bản KHOBAU.INP gồm một dòng chứa hai số nguyên dương L và R (1 ≤ L ≤ R ≤ 3×10⁶), mỗi số cách nhau một dấu cách.

Dữ liệu ra: Ghi vào tệp văn bản KHOBAU.OUT, chứa một số nguyên duy nhất là số lượng số kho báu trong đoạn [L, R].

Ví dụ:

KHOBAU.INP	KHOBAU.OUT	Giải thích
1 50	9	Có 9 số kho báu trong đoạn này: 12, 18, 20, 24, 30, 36, 40, 42, 48.

Giới hạn:

• Subtask 1: Có 8/28 test tương ứng với 2,0 điểm có: 1 ≤ L ≤ R ≤ 10³.
• Subtask 2: Có 16/28 test tương ứng với 4,0 điểm có: 1 ≤ L ≤ R ≤ 9×10⁴.
• Subtask 3: Có 4/28 test tương ứng với 1,0 điểm có: 1 ≤ L ≤ R ≤ 3×10⁶.

Câu 3 (7,0 điểm). Sóc

Sóc là một loài động vật rất nhanh nhẹn, thông minh. Mỗi khi di chuyển chú thường nhảy lên, xuống một cách nhanh chóng. Hôm nay Sóc định dạo chơi trên một dãy đồi núi nhấp nhô, đoạn lên cao, đoạn xuống thấp. Địa hình đồi núi được xác định là một dãy các bậc từ trái sang phải với độ cao khác nhau. Giữa các dãy độ cao này có một mốc qui định là điểm cân bằng, nếu độ cao trên điểm cân bằng thì được gọi là độ cao dương, ngược lại dưới điểm cân bằng thì được gọi là độ cao âm.

Dãy đồi núi bao gồm N (N ≤ 10⁵) bậc, mỗi bậc có một giá trị độ cao có thể âm hoặc dương nằm trong khoảng [−10⁹, 10⁹]. Ban đầu Sóc ở vị trí điểm cân bằng (độ cao 0), mỗi bước nhảy Sóc có thể nhảy sang phải tối thiểu là 1 bước và tối đa là K bước (K ≤ 100). Khi dừng lại ở một bậc nào thì độ cao của bậc đó được cộng vào tổng độ cao mà Sóc đã nhảy. Bởi vì có ý định dạo chơi trên dãy núi, nên Sóc sẽ dừng lại ở bất cứ bậc nào miễn sao Sóc đạt được tổng độ cao lớn nhất có thể.

Bạn hãy xác định xem Sóc sẽ đạt được tổng độ cao lớn nhất là bao nhiêu?

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

• Dòng đầu tiên chứa 2 số nguyên dương N (N ≤ 10⁵) và K (K ≤ 100), mỗi số cách nhau một dấu cách.
• Dòng thứ hai chứa N số nguyên A₁, A₂, … A_N (−10⁹ ≤ A_i ≤ 10⁹, 1 ≤ i ≤ N) là dãy độ cao của các bậc, các số cách nhau ít nhất một dấu cách.

Dữ liệu ra: Ghi vào tệp SOC.OUT gồm một dòng duy nhất chứa một số nguyên là tổng độ cao lớn nhất mà Sóc đạt được.

Ví dụ:

SOC.INP	SOC.OUT	Giải thích
5 2 -5 2 -7 -1 5	6	Với 5 bậc, số bước nhảy là 2, Sóc nhảy như sau: 0 → 2 → 4 → 5 tổng độ cao đạt được là 2 + (−1) + 5 = 6.

Giới hạn:

• Subtask 1: Có 10/28 test tương ứng với 2,5 điểm có N ≤ 10⁴ và K ≤ 100.
• Subtask 2: Có 12/28 test tương ứng với 3,0 điểm có N ≤ 9×10⁴ và K ≤ 100.
• Subtask 3: Có 6/28 test tương ứng với 1,5 điểm có N ≤ 10⁵ và K ≤ 100.

---

• Thí sinh không được sử dụng tài liệu.
• Giám thị không được giải thích gì thêm.