HSG lớp 9 Bình Định 2020-2021

SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH Lớp 9 THCS - Khóa ngày 18/3/2021
Môn thi: Tin học
Thời gian: 150 phút (không kể thời gian phát đề)
(Đề thi có 02 trang)

---

Tổng quan bài thi

Bài	Tên bài, điểm	Tên tệp chương trình	Dữ liệu vào	Dữ liệu ra
1	Số có nhiều ước nguyên tố nhất (5,0đ)	UOCNGTO.*	UOCNGTO.INP	UOCNGTO.OUT
2	Chữ số tận cùng (5,0đ)	TANCUNG.*	TANCUNG.INP	TANCUNG.OUT
3	Tam giác vuông lớn nhất (5,0đ)	TGVUONG.*	TGVUONG.INP	TGVUONG.OUT
4	Phục hồi dãy số (5,0đ)	DAYSO.*	DAYSO.INP	DAYSO.OUT

Chú ý:

• Phần mở rộng tên tệp chương trình theo ngôn ngữ lập trình của thí sinh (.pas; .cpp).
• Khi chấm thi có xét đến thời gian xử lý bài toán của chương trình nên thí sinh không sử dụng các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm.
• Thời gian chạy mỗi test của chương trình không quá 02 giây.

Bài 1. Số có nhiều ước nguyên tố nhất (5,0 điểm)

Cho trước hai số nguyên dương A và B (1 < A < B < 10⁵). Trong các số nguyên dương X mà A < X ≤ B tìm số lớn nhất có nhiều ước nguyên tố nhất.

Dữ liệu vào: từ file UOCNGTO.INP gồm một dòng chứa hai số nguyên dương A và B (1 < A < B < 10⁵).

Dữ liệu ra: ghi ra file UOCNGTO.OUT gồm 2 số K, C (với A < K ≤ B) thể hiện số K tìm được và số ước nguyên tố C của nó tương ứng với cặp số (A, B).

Ví dụ:

UOCNGTO.INP	UOCNGTO.OUT	Giải thích
2 13	12 2	(vì 12 = 2.2.3, có 2 ước nguyên tố là 2, 3)
1000 2000	1995 4	(vì 1995 = 3.5.7.19)

Bài 2. Chữ số tận cùng (5,0 điểm)

Cho hai số nguyên dương P và Q (1 < P, Q < 10⁹). Yêu cầu xác định chữ số tận cùng của số P^Q.

Dữ liệu vào: từ file TANCUNG.INP gồm một dòng chứa 2 số P và Q (1 < P, Q < 10⁹).

Dữ liệu ra: ghi ra file TANCUNG.OUT gồm một dòng có một chữ số C (0 ≤ C ≤ 9) thể hiện chữ số tận cùng của số P^Q tương ứng với cặp số (P, Q).

Ví dụ:

TANCUNG.INP	TANCUNG.OUT	Giải thích
13 2	9	13² = 169 (tận cùng bằng 9)
26 3	6	26³ = 17576 (tận cùng bằng 6)
2 10	4	2¹⁰ = 1024 (tận cùng bằng 4)

Ghi chú

Dòng “Dữ liệu vào” trong đề gốc ghi 1 < P < Q < 10⁹, nhưng ví dụ có P > Q, nên hiểu theo điều kiện 1 < P, Q < 10⁹ ở phần mô tả.

Bài 3. Tam giác vuông lớn nhất (5 điểm)

Cho trước hai số nguyên dương M và N (M < N). Xác định tam giác vuông có diện tích lớn nhất với các cạnh a, b, c là các số nguyên dương thỏa mãn: M < a + b + c ≤ N.

Dữ liệu vào: từ file TGVUONG.INP gồm một dòng chứa hai số nguyên dương M và N cách nhau một dấu cách với (3 < M < N < 10000).

Dữ liệu ra: ghi ra file TGVUONG.OUT chứa một số nguyên duy nhất là diện tích của tam giác vuông tìm được (định dạng 1 chữ số thập phân). Nếu không tìm được tam giác vuông nào thỏa mãn thì ghi số 0.0.

Ví dụ:

TGVUONG.INP	TGVUONG.OUT	Giải thích
3 20	6.0	Δvuông: 3, 4, 5
15 20	0.0	Không có tam giác vuông nào thỏa mãn

Ghi chú

Đề gốc ghi tên tệp vào là “TGVUONG.INT” (lỗi đánh máy) và ví dụ 1 có M = 3 trong khi ràng buộc ghi 3 < M. Giữ nguyên văn để đối chiếu.

Bài 4. Phục hồi dãy số (5 điểm)

Bạn An sắp xếp các số từ 1, 2, …, n một cách tùy ý vào n vị trí và được dãy số P (hay còn gọi P là một hoán vị của các số 1, 2, …, n). Quan sát dãy số P, lần lượt với mỗi giá trị i (i = 1, 2, …, n) An thực hiện ghi lại số các số lớn hơn i và đứng bên trái i trong dãy P và được dãy T gồm n số. An đưa dãy số T cho bạn Thắng và yêu cầu phục hồi dãy P ban đầu từ dãy T này. Em hãy lập trình giúp Thắng giải quyết bài toán này.

Dữ liệu vào: từ file DAYSO.INP gồm 2 dòng:

• Dòng đầu chứa số tự nhiên N (1 < N < 100).
• Dòng thứ hai chứa N số tự nhiên mô tả dãy T, các số cách nhau 1 dấu cách.

Dữ liệu ra: ghi ra file DAYSO.OUT là một dãy gồm N số mô tả dãy P ban đầu, các số ghi cách nhau một dấu cách.

Ví dụ:

DAYSO.INP	DAYSO.OUT	Giải thích
4 2 1 0 0	3 2 1 4	- Số 1 có 2 số lớn hơn bên trái (3, 4) - Số 2 có 1 số lớn hơn bên trái (3) - Số 3 không có số lớn hơn bên trái - Số 4 không có số lớn hơn bên trái
6 5 1 0 1 1 0	3 2 6 4 5 1	- Số 1 có 5 số lớn hơn bên trái (3, 2, 6, 4, 5) - Số 2 có 1 số lớn hơn bên trái (3) - Số 3 không có số lớn hơn bên trái - Số 4 có 1 số lớn hơn bên trái (6) - Số 5 có 1 số lớn hơn bên trái (6) - Số 6 không có số lớn hơn bên trái

Chú ý

Giải thích ví dụ 1 trong đề ghi “Số 1 có 2 số lớn hơn bên trái (3, 4)”, trong khi với P = 3 2 1 4 thì các số lớn hơn 1 đứng bên trái là 3 và 2. Giữ nguyên văn.