HSG THCS cấp tỉnh 2023-2024 (chưa rõ tỉnh)

SỞ GIÁO DỤC VÀ ĐÀO TẠO (bản chụp không thấy tên tỉnh)
ĐỀ THI CHÍNH THỨC
(Đề thi có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI THCS CẤP TỈNH Năm học 2023 - 2024
Môn thi: Tin học
Thời gian làm bài: 150 phút (không kể thời gian giao đề)

---

Ghi chú

Bản chụp đề trong tài liệu sưu tầm không ghi tên Sở GD&ĐT nên chưa xác định được tỉnh. Nếu bạn biết đề này của tỉnh nào, hãy góp ý để chúng tôi cập nhật.

Tổng quan bài thi

Bài	Tên bài	Tên file chương trình	Tên file input	Tên file output	Điểm
1	Mua vé	TICKET.*	TICKET.INP	TICKET.OUT	6,0
2	Phân số	FRAC.*	FRAC.INP	FRAC.OUT	5,0
3	Tệp tin	FILEDEL.*	FILEDEL.INP	FILEDEL.OUT	5,0
4	Sưu tập bi	MARBLES.*	MARBLES.INP	MARBLES.OUT	4,0

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. Hãy lập trình giải các bài toán sau:

Bài 1. Mua vé (6,0 điểm)

Đỉnh Fansipan thuộc dãy Hoàng Liên Sơn nổi tiếng là đỉnh núi cao nhất Việt Nam và được mệnh danh là “Nóc nhà Đông Dương”. Fansipan đã trở thành điểm đến thu hút đông đảo khách du lịch trong và ngoài nước. Để lên đỉnh núi Fansipan cần mua vé cáp treo với giá a ngàn đồng một người lớn và b ngàn đồng với một trẻ em, vé xe điện u ngàn đồng một người lớn và v ngàn đồng một trẻ em.

Yêu cầu: Đoàn du lịch có x người, trong đó có y trẻ em. Hãy xác định số tiền ít nhất cần chuẩn bị để mua vé cho cả đoàn.

Dữ liệu vào: Cho trong tệp tin văn bản TICKET.INP gồm một dòng ghi sáu số nguyên a, b, u, v, x, y (1 ≤ a, b, u, v, x, y ≤ 100; x ≥ y).

Kết quả ra: Ghi ra tệp tin văn bản TICKET.OUT một số nguyên là số tiền ít nhất cần chuẩn bị để mua vé cho cả đoàn.

Ví dụ:

TICKET.INP	TICKET.OUT
60 30 50 25 40 10	3850

Bài 2. Phân số (5,0 điểm)

Phân số tối giản là phân số mà có tử số và mẫu số không thể cùng chia hết cho số nào ngoại trừ số 1 (hoặc −1 nếu là các số âm). Nói cách khác phân số a/b là tối giản nếu a và b là nguyên tố cùng nhau, nghĩa là ước chung lớn nhất là 1.

Cho tử số a và mẫu số b của một phân số là số nguyên.

Yêu cầu: Hãy viết một chương trình rút gọn phân số a/b về phân số tối giản.

Dữ liệu vào: Cho trong tệp tin văn bản FRAC.INP chỉ gồm một dòng ghi hai số nguyên tử số a và mẫu số b của phân số cần rút gọn.

Kết quả ra: Ghi ra tệp tin văn bản FRAC.OUT là phân số tối giản sau khi đã rút gọn.

• Nếu phân số được yêu cầu không hợp lệ, in ra INVALID.
• Nếu giá trị của phân số là một số nguyên, in ra số nguyên đó.
• Trường hợp khác, in ra tử số và mẫu số của phân số tối giản cách nhau 1 dấu cách; nếu phân số sau khi rút gọn có giá trị âm (dấu −) thì đưa dấu âm (dấu −) lên tử số.

Ví dụ:

FRAC.INP	FRAC.OUT
4 -8	-1 2
-5 20	-1 4

Giới hạn: |a|, |b| ≤ 10⁷.

Bài 3. Tệp tin (5,0 điểm)

Một hệ thống máy tính hiện đang lưu trữ n tệp tin, tệp tin thứ i được đặt tên là sᵢ. Nhận thấy rằng có nhiều tệp tin không cần thiết, người ta đã xóa đi một số tệp tin của hệ thống máy tính. Cụ thể người ta đã thực hiện q thao tác xóa tệp tin, mỗi thao tác được biểu diễn bởi một ký tự c, cho biết thao tác này xóa đi các tệp tin có tên chứa ít nhất một ký tự c.

Yêu cầu: Sau mỗi thao tác xóa, hãy cho biết còn lại bao nhiêu tệp tin trong hệ thống máy tính.

Dữ liệu vào: Cho trong tệp tin văn bản FILEDEL.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương n và q (1 ≤ n, q ≤ 10⁵).
• n dòng tiếp theo: dòng thứ i gồm xâu ký tự sᵢ có độ dài không vượt quá 8, chỉ gồm các kí tự Latin in thường cho biết tên của tệp tin thứ i.
• q dòng tiếp theo: mỗi dòng gồm một ký tự Latin in thường c mô tả một thao tác xóa.

Kết quả ra: Ghi ra tệp tin văn bản FILEDEL.OUT gồm q dòng, dòng thứ i gồm số tệp tin còn lại trong hệ thống máy tính sau khi thực hiện thao tác xóa thứ i.

Ví dụ:

FILEDEL.INP	FILEDEL.OUT
6 3 shoes split rect line vision walk o z s	4 4 3

Giải thích:

• Sau thao tác xóa thứ nhất, các tệp tin còn lại là ‘split’, ‘rect’, ‘line’ và ‘walk’.
• Thao tác xóa thứ hai không xóa đi tệp tin nào.
• Sau thao tác xóa thứ ba, các tệp tin còn lại là ‘rect’, ‘line’ và ‘walk’.

Giới hạn:

• Có 70% số test tương ứng 70% số điểm có n, q ≤ 100.
• 30% số test tương ứng 30% số điểm còn lại không có ràng buộc gì thêm.

Bài 4. Sưu tập bi (4,0 điểm)

Bắn bi là một trò chơi rất đơn giản và không kém phần thú vị trong giờ giải lao sau những giờ học căng thẳng. Ngoài việc đam mê trò chơi bắn bi giải trí, John còn là một học sinh rất thích sưu tầm bi.

Sau một thời gian sưu tầm, John có n viên bi đỏ, m viên bi xanh và p viên bi vàng, mỗi viên bi có một độ sáng nhất định, cụ thể: Viên bi đỏ thứ i có độ sáng là aᵢ, viên bi xanh thứ j có độ sáng là bⱼ, viên bi vàng thứ k có độ sáng là c_k.

John muốn chọn ra 3 viên bi, mỗi loại một viên sao cho chênh lệch độ sáng giữa ba viên bi được chọn là nhỏ nhất. Chênh lệch độ sáng của 3 viên bi được tính theo công thức:

s = (aᵢ − bⱼ)² + (bⱼ − c_k)² + (c_k − aᵢ)²

Yêu cầu: Cho trước độ sáng của tất cả viên bi. Tìm chênh lệch độ sáng nhỏ nhất giữa các viên bi.

Dữ liệu vào: Cho trong tệp tin văn bản MARBLES.INP gồm:

• Dòng đầu tiên chứa ba số nguyên dương n, m và p (1 ≤ n, m, p ≤ 10⁵).
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹ với i = 1..n).
• Dòng thứ ba chứa m số nguyên b₁, b₂, …, b_m (1 ≤ bⱼ ≤ 10⁹ với j = 1..m).
• Dòng thứ bốn chứa p số nguyên c₁, c₂, …, c_p (1 ≤ c_k ≤ 10⁹ với k = 1..p).

Kết quả ra: Ghi ra tệp tin văn bản MARBLES.OUT gồm một số nguyên duy nhất là chênh lệch độ sáng nhỏ nhất tìm được.

Ví dụ:

MARBLES.INP	MARBLES.OUT
2 2 3 7 8 6 3 3 1 4	14

Giới hạn:

• Có 40% số test tương ứng 40% số điểm có n, m, p ≤ 100.
• Có 40% số test tương ứng 40% số điểm có n, m, p ≤ 1000.
• Có 20% số test tương ứng 20% số điểm có n, m, p ≤ 10⁵.

(Đề gốc ghi “n, m, q” trong phần giới hạn và “40% số test tương ứng 30% số điểm” ở dòng thứ hai - nhiều khả năng là lỗi đánh máy.)

---

Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm!