HSG THPT Khánh Hòa 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO KHÁNH HÒA ĐỀ THI CHÍNH THỨC
(Đề thi có 03 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: 06/12/2024
Thời gian: 180 phút (không kể thời gian phát đề)

---

Tổng quan về đề 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 kết quả	Thời gian
1	Dãy số	DAYSO.*	DAYSO.INP	DAYSO.OUT	1 giây/test
2	Số đẹp	SODEP.*	SODEP.INP	SODEP.OUT	1 giây/test
3	Di chuyển	DICHUYEN.*	DICHUYEN.INP	DICHUYEN.OUT	1 giây/test

• Dấu * được thay thế bởi PAS hoặc CPP, PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++, Python.
• Các số trên một dòng được phân cách nhau một dấu cách.

Câu 1 (7.00 điểm): Dãy số

Cho dãy số A gồm N số a₁, a₂, a₃, …, a_N. Từ dãy số này Tèo tạo ra dãy số B như sau: b₁ = a₁, b₂ = (a₁ + a₂) / 2, b₃ = (a₁ + a₂ + a₃) / 3, …, b_N = (a₁ + a₂ + a₃ + ⋯ + a_N) / N. Sau khi Tèo tạo xong dãy B thì xóa bỏ dãy A. Tèo liền đố Tí cách tìm lại dãy A ban đầu.

Yêu cầu: Hãy lập trình giúp Tí tìm lại dãy A ban đầu.

Dữ liệu vào: Trong tệp văn bản DAYSO.INP gồm:

Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 100) là số lượng số của dãy số B.

Dòng thứ hai chứa N số nguyên b_i (1 ≤ b_i ≤ 10⁹).

Dữ liệu ra: Ghi vào tệp văn bản DAYSO.OUT trên một dòng: Dãy số A tìm được.

Chú ý: Cả hai dãy số chỉ gồm các số nguyên dương.

Ví dụ:

DAYSO.INP	DAYSO.OUT
5 1 2 2 3 3	1 3 2 6 3

Ràng buộc dữ liệu:

• Có 30% số test ứng với 1 ≤ N ≤ 10.
• Có 70% số test không có ràng buộc gì thêm.

Câu 2 (7.00 điểm): Số đẹp

Trên thế giới có nhiều dân tộc, mỗi dân tộc có nền văn hóa của riêng họ. Dân tộc X có quan niệm về số đẹp và họ rất coi trọng số đẹp. Số đẹp của họ là số chỉ chứa chữ số 5 và chữ số 8. Được qui ước như sau: Số đẹp thứ nhất là 5, số đẹp thứ hai là 8, số đẹp thứ ba là 55, số đẹp thứ tư là 58, số đẹp thứ năm là 85, số đẹp thứ sáu là 88, …, số đẹp thứ mười là 588, …

Yêu cầu: Hãy tìm số đẹp thứ K.

Dữ liệu vào: Trong tệp văn bản SODEP.INP gồm: Duy nhất số K (1 ≤ K ≤ 10¹⁸).

Dữ liệu ra: Ghi vào tệp văn bản SODEP.OUT trên một dòng: Số đẹp thứ K tìm được.

Ví dụ:

SODEP.INP	SODEP.OUT
10	588

Ràng buộc dữ liệu:

• Có 60% số test 1 ≤ K ≤ 10⁸.
• Có 40% số test không ràng buộc gì thêm.

Câu 3 (6.00 điểm): Di chuyển

Trong thành phố Z có n trạm xe buýt, có m tuyến đường cho xe buýt chạy bắt đầu từ trạm a_i và kết thúc ở trạm b_i, tốn khoảng thời gian t_i.

Bình là một sinh viên mới vào thành phố, mỗi ngày Bình cần phải đi học bằng xe buýt từ trạm c_j đến trạm d_j. Bình muốn sử dụng nhiều nhất là k tuyến cho hành trình của mình. Bình có q truy vấn: Đi từ trạm c_j đến trạm d_j chỉ sử dụng nhiều nhất là k tuyến thì thời gian ngắn nhất là bao nhiêu?

Yêu cầu: Hãy tìm thời gian ngắn nhất để đi từ trạm c_j đến trạm d_j.

Dữ liệu vào: Trong tệp văn bản DICHUYEN.INP gồm:

Dòng đầu tiên chứa hai số nguyên dương n và m (2 ≤ n ≤ 70, 1 ≤ m ≤ 10⁶) số trạm xe buýt và số tuyến đường.

Dòng thứ i trong m dòng tiếp theo chứa ba số nguyên a_i, b_i và t_i tương ứng là đi từ trạm a_i đến trạm b_i tốn thời gian t_i (1 ≤ a_i, b_i ≤ n, 1 ≤ t_i ≤ 10⁶).

Dòng kế tiếp chứa hai số nguyên k và q (1 ≤ k ≤ 10⁹, 1 ≤ q ≤ n²), tương ứng với số tuyến đường nhiều nhất được sử dụng và số truy vấn.

q dòng tiếp theo mỗi dòng chứa hai số nguyên c_j và d_j (1 ≤ c_j, d_j ≤ n), tương ứng với truy vấn là đi từ trạm c_j và d_j.

Dữ liệu ra: Ghi vào tệp văn bản DICHUYEN.OUT gồm:

q dòng tương ứng, dòng thứ j in ra đường đi ngắn nhất của truy vấn thứ j hoặc −1 nếu không tìm thấy được đường đi.

Ví dụ 1:

DICHUYEN.INP	DICHUYEN.OUT
4 7 1 2 1 1 4 10 2 3 1 2 4 5 3 2 2 3 4 1 4 3 2 1 3 1 4 4 2 3 3	10 -1 0

Ví dụ 2:

DICHUYEN.INP	DICHUYEN.OUT
4 7 1 2 1 1 4 10 2 3 1 2 4 5 3 2 2 3 4 1 4 3 2 2 3 1 4 4 2 3 3	6 4 0

Hình minh họa cho ví dụ 1 và ví dụ 2.

Giải thích:

Trong ví dụ 1: Đi từ 1 đến 4 tốn chi phí 10, từ 4 tới 2 không có đường đi, từ 3 đến 3 chi phí là 0.

Ràng buộc dữ liệu:

• Có 20% số test k = 1.
• Có 30% số test 1 ≤ k < n ≤ 7.
• Có 50% số test không ràng buộc gì thêm.

---

Cán bộ coi thi không giải thích gì thêm.