HSG THPT Sóc Trăng 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO SÓC TRĂNG ĐỀ CHÍNH THỨC
(Đề thi này có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH Năm học: 2024-2025
Môn: Tin học
Thời gian làm bài 180 phút, không kể thời gian phát đề

---

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả
1	Số nguyên tố lớn nhất	NTMAX.*	NTMAX.INP	NTMAX.OUT
2	Chia việc	CHIAVIEC.*	CHIAVIEC.INP	CHIAVIEC.OUT
3	Di chuyển robot	RMOVING.*	RMOVING.INP	RMOVING.OUT
4	Drone xếp hàng	DRONE.*	DRONE.INP	DRONE.OUT

Dấu * được thay thế bởi PAS hoặc CPP hoặc PY tương ứng với ngôn ngữ lập trình Pascal hoặc C++ hoặc Python. Yêu cầu đặt tên file giống bảng trên.

Hãy lập trình giải các bài toán sau:

Bài 1. Số nguyên tố lớn nhất (5,0 điểm)

Cho xâu S chỉ gồm các ký tự là chữ cái và chữ số. Hãy thực hiện các yêu cầu sau:

• Cho biết trong xâu S có bao nhiêu ký tự số.
• Tìm số P trong xâu S là số nguyên tố lớn nhất. Số P là tất cả các ký tự số liên tiếp trong xâu S và không có số 0 vô nghĩa.

Ví dụ: S = “Tin011hoc230lop124muoi17” có các số P là 11, 230, 124 và 17. Số nguyên tố P lớn nhất là 17.

Dữ liệu: vào từ file văn bản NTMAX.INP gồm một xâu ký tự S.

Kết quả: ghi ra file văn bản NTMAX.OUT gồm:

• Dòng 1: ghi số lượng ký tự số trong xâu S.
• Dòng 2: ghi ra số nguyên tố P lớn nhất, nếu không có số P nguyên tố thì ghi ra số 0.

Ví dụ:

NTMAX.INP	NTMAX.OUT
Tin011hoc230lop124muoi17	11 17

Ràng buộc:

• Có 60% số test ứng với 60% số điểm của bài với độ dài xâu S ≤ 255 và P ≤ 10³.
• Có 20% số test ứng với 20% số điểm của bài với độ dài xâu S ≤ 255 và P ≤ 10⁶.
• Có 20% số test ứng với 20% số điểm của bài với độ dài xâu S ≤ 5.10⁶ và P ≤ 5.10⁶.

Bài 2. Chia việc (5,0 điểm)

Lan và Mai là hai bạn học sinh năng nổ trong một hoạt động tình nguyện do lớp tổ chức. Trong một buổi phân công nhiệm vụ, Lan hoàn thành được a/b phần công việc, còn Mai hoàn thành được c/d phần công việc. (Với 1 ≤ a, b, c, d ≤ 10⁹ là các số nguyên dương và b, d khác 0).

Yêu cầu: Hãy viết chương trình thực hiện tính tổng phần công việc mà hai bạn Lan và Mai đã hoàn thành (dạng phân số tối giản) và sự chênh lệch giữa hai bạn trong việc hoàn thành công việc được giao (hiệu tuyệt đối, rút gọn tối giản).

Dữ liệu: Vào từ file văn bản CHIAVIEC.INP gồm:

• Dòng 1: Chứa hai số nguyên dương a, b.
• Dòng 2: Chứa hai số nguyên dương c, d.

Kết quả: Ghi ra file văn bản CHIAVIEC.OUT gồm:

• Dòng 1: Hai số nguyên dương m, n biểu diễn phân số tối giản của tổng a/b + c/d.
• Dòng 2: Hai số nguyên dương p, q biểu diễn phân số tối giản của hiệu tuyệt đối |a/b − c/d|.

Ví dụ:

CHIAVIEC.INP	CHIAVIEC.OUT
7 8 3 9	29 24 13 24

Ràng buộc:

• Có 60% số test ứng với 60% số điểm của bài có a, b, c, d ≤ 10³.
• Có 20% số test ứng với 20% số điểm của bài có a, b, c, d ≤ 10⁶.
• Có 20% số test ứng với 20% số điểm của bài có a, b, c, d ≤ 10⁹.

Bài 3. Di chuyển robot (5,0 điểm)

Bản đồ một kho hàng là hình chữ nhật kích thước m × n được chia làm lưới ô vuông đơn vị. Các hàng của bảng được đánh số từ 1 tới m từ trên xuống dưới và các cột của bảng được đánh số từ 1 tới n từ trái qua phải. Ô nằm trên giao của hàng i và cột j gọi là ô (i, j). Trong kho có một số kiện hàng được xếp sẵn, mỗi kiện hàng xếp sẵn chiếm đúng 1 ô.

Robot là một hình chữ nhật chiếm trọn một số ô trống trong kho hàng. Tại mỗi bước, bạn có thể ra lệnh cho robot di chuyển theo một trong bốn hướng song song với cạnh nhà kho. Khi nhận mỗi lệnh di chuyển, robot sẽ đi theo đúng hướng được yêu cầu cho tới khi:

• Hoặc robot đi ra khỏi nhà kho (chính xác là khi robot không chiếm ô nào trong nhà kho nữa), nhiệm vụ của bạn hoàn thành.
• Hoặc robot vướng vào một kiện hàng đã xếp sẵn theo hướng di chuyển (tức là kiện hàng đó sẽ bị robot đè lên nếu robot di chuyển tiếp), robot dừng lại và đợi lệnh di chuyển tiếp theo của bạn.

Yêu cầu: Tìm một dãy ngắn nhất các lệnh di chuyển đưa robot ra khỏi nhà kho.

Dữ liệu: Vào từ file văn bản RMOVING.INP

• Dòng 1 chứa hai số nguyên dương m, n ≤ 1000 cách nhau bởi dấu cách.
• m dòng tiếp theo, dòng thứ i chứa n ký tự liền nhau, ký tự thứ j thể hiện tình trạng ô (i, j) của nhà kho theo ý nghĩa sau:
  • Dấu thăng ”#”: Ô (i, j) có một kiện hàng xếp sẵn
  • Dấu chấm ”.”: Ô (i, j) là ô trống
  • Chữ R “R”: Ô (i, j) đang bị robot chiếm chỗ

Kết quả: Ghi ra file văn bản RMOVING.OUT một số nguyên duy nhất là số lệnh di chuyển để đưa robot ra khỏi nhà kho. Nếu không tồn tại dãy lệnh di chuyển để đưa robot ra khỏi nhà kho, ghi ra số −1.

Dữ liệu vào đảm bảo các ô chứa chữ R tạo thành một hình chữ nhật ứng với vị trí khởi đầu của robot.

Ví dụ:

RMOVING.INP	RMOVING.OUT
8 8 ######## .RRR...# #RRR.... ####...# .......# .......# #......# #...#..#	4
6 8 ........ ..#...#. #.RR.... ..RR...# ..#...#. ........	-1

Giải thích ví dụ thứ nhất: Dãy lệnh di chuyển ngắn nhất để đưa robot ra khỏi nhà kho là: Sang phải, Đi xuống, Sang trái, Đi xuống.

Ràng buộc: Có 50% số test ứng với 50% số điểm của bài với m, n ≤ 100.

Bài 4. Drone xếp hàng (5,0 điểm)

Một kho hàng thông minh được thiết kế theo dạng khối lập phương 3 chiều có kích thước X × Y × Z. Mỗi điểm trong không gian 3 chiều này được mô tả bởi tọa độ (x, y, z) trong đó 0 ≤ x < X; 0 ≤ y < Y; 0 ≤ z < Z. Nơi các drone bay tự động đảm nhận nhiệm vụ vận chuyển hàng hóa. Drone có thể di chuyển đến 6 vị trí lân cận (trên, dưới, trái, phải, trước, sau) nếu vị trí đó không bị vật cản. Mỗi drone xuất phát từ một vị trí trong kho và cần đến đúng kệ chứa hàng được chỉ định.

Yêu cầu: Hãy viết chương trình để tìm số bước di chuyển ít nhất để drone đến được đích.

Dữ liệu: Vào từ file văn bản DRONE.INP gồm:

• Dòng 1: 3 số nguyên X, Y, Z là kích thước kho hàng (1 ≤ X, Y, Z ≤ 1000).
• Dòng 2: 6 số nguyên x_s, y_s, z_s, x_d, y_d, z_d là vị trí xuất phát và đích đến.
• Tiếp theo là X × Y dòng mô tả không gian 3 chiều: Mỗi dòng gồm chuỗi nhị phân có độ dài Z, trong đó ‘1’ là vật cản, ‘0’ là ô trống.

Dữ liệu được đưa theo thứ tự: x = 0 → X − 1, với mỗi x, các dòng tương ứng với y = 0 → Y − 1.

Kết quả: Ghi ra file văn bản DRONE.OUT gồm:

• Ghi ra số bước ít nhất để drone đi từ vị trí xuất phát đến đích.
• Nếu không thể đến nơi, ghi −1.

Ví dụ:

DRONE.INP	DRONE.OUT
1 1 2 0 0 0 0 0 1 00	1
2 2 2 0 0 0 1 1 1 01 01 10 10	-1

Ràng buộc: Có 50% số test ứng với 50% số điểm của bài có X, Y, Z ≤ 10.