Đề thi HSG tin 11 tỉnh Nghệ An năm 2014 - 2015

Thứ sáu - 19/05/2023 23:25 2.036 0

Đây là đề thi học sinh giỏi tin học 11 tỉnh Nghệ An năm học 2014 - 2015.
Dưới bài viết mình đã gửi các test của các bài, các bạn làm và lấy các test chạy xem có full test không nhé. Hôm sau mình sẽ giải các bài này để các bạn tham khảo, hiện tại mình chưa giải được vì do chưa sắp xếp được thời gian.

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Thời gian chạy
Số anh em	ANHEM.PAS	ANHEM.INP	ANHEM.OUT	1 giây
Dãy nguyên tố	DAYNT.PAS	DAYNT.INP	DAYNT.OUT	1 giây
Xâu con	XAU.PAS	XAU.INP	XAU.OUT	1 giây
Tích riêng	TICH.PAS	TICH.INP	TICH.OUT	1 giây

Bài 1. Số anh em. (5 điểm)

Ước thực sự của số tự nhiên N là ước khác 1 và chính nó. Hai số được gọi là anh em nếu chúng có tổng các ước thực sự bằng nhau.
Ví dụ: 6 và 25 được gọi là hai số anh em vì các ước thực sự của 6 là 2 và 3 có tổng bằng 5 và các ước thực sự của 25 là 5 có tổng là 5.
Yêu cầu: Viết chương trình để kiểm tra hai số có phải là hai số anh em không?
Dữ liệu vào từ file văn bản ANHEM.INP: Chỉ gồm một dòng duy nhất chứa hai số nguyên dương M, N (0 < M, N < 10⁴) cách nhau ít nhất một ký tự trống.
Kết quả ghi file văn bản ANHEM.OUT: Chỉ một dòng duy nhất chứa xâu ‘YES’ nếu M, N là hai số anh em, ngược lại ghi ra xâu ‘NO’.
Ví dụ:

ANHEM.INP	ANHEM.OUT	ANHEM.INP	ANHEM.OUT
6 25	YES	12 13	NO

Bài 2 (6 điểm) Dãy nguyên tố.

Cho số tự nhiên k và dãy A gồm N (N < 10⁴) số tự nhiên không vượt quá 32000.
Yêu cầu: Tìm k số nguyên tố nhỏ nhất khác nhau xuất hiện trong dãy A.
Dữ liệu vào từ file văn bản DAYNT.INP:

Dòng đầu tiên chứa một số tự nhiên k (1 < k < N).
N dòng tiếp theo, mỗi dòng chứa một số tự nhiên là một phần tử của dãy A.

Kết quả ghi ra file văn bản DAYNT.OUT: Đưa ra trên cùng một dòng k số nguyên tố tìm được theo thứ tự tăng dần, các số cách nhau ít nhất một ký tự trống.
Lưu ý: Dữ liệu vào đảm bảo luôn tìm được k số nguyên tố thỏa mãn.
Ví dụ:

DAYNT.INP	DAYNT.OUT
3 12 13 17 9 3 1 12	3 13 17

Bài 3. (6 điểm) Xâu con.

Cho trước một xâu có độ dài L (1 < L < 2.10⁵) chỉ chứa các chữ cái thường trong bảng chữ cái tiếng Anh.
Yêu cầu: Hãy tìm xâu con dài nhất xuất hiện ít nhất 2 lần trong xâu đã cho.
Dữ liệu vào từ file XAU.INP:

Dòng đầu là một số nguyên L.
Dòng sau là một xâu có độ dài L.

Kết quả ghi ra file XAU.OUT: Chỉ một số duy nhất là độ dài của xâu con tìm được, nếu không tìm được thì ghi ra 0.
Ví dụ:

XAU.INP	XAU.OUT	XAU.INP	XAU.OUT	XAU.INP	XAU.OUT
11 sabcabcfabc	3	18 trutrutiktiktappop	4	6 abcdef	0

Lưu ý: Có 60% số test của bài có độ dài xâu L < 255
Có 40% số test của bài có độ dài xâu L >255

Bài 4. (3 điểm) Tích riêng

Tích_chữ số của một số nguyên dương là tích các chữ số thập phân của số đó.
Ví dụ: Tích_chữ số của số 2612 là 2.6.1.2 = 24.
Tích_riêng của một số là tích của số đó với Tích_chữ số của nó.
Ví dụ: Tích_riêng của số 2612 là 2612.24 = 62688.
Yêu cầu: Cho 2 số nguyên dương A và B. Hãy tính số các số nguyên dương có Tích_riêng của nó thuộc đoạn [A, B].
Dữ liệu vào từ file TICH.INP: Chỉ một dòng duy nhất chứa 2 số nguyên dương A và B cách nhau ít nhất một ký tự trống (1 < A < B < 10¹⁸).
Kết quả ghi ra file TICH.OUT: Chỉ chứa một số duy nhất là số tìm được.
Ví dụ:

TICH.INP	TICH.OUT	TICH.INP	TICH.OUT	TICH.INP	TICH.OUT
20 30	2	145 192	4	2224222 2224222	1

Lưu ý: Có 50% số test của bài có A và B không vượt quá 10¹².

Giải thích test thứ 2: Có 4 số 19, 24, 32 và 41 có Tích_riêng lần lượt là 171, 192, 192 và 164 thuộc đoạn [145, 192].