Đề thi chọn học sinh giỏi tỉnh Quảng Bình năm học 2015 - 2016 môn: Tin học lớp 11 thpt – vòng II

SỞ GD&ĐT QUẢNG BÌNH KÌ THI CHỌN HSG TỈNH NĂM HỌC 2015-2016
	Khóa thi ngày 23 - 3 - 2016
 ĐỀ CHÍNH THỨC	Môn: Tin học
	LỚP 11 THPT - VÒNG II	
Họ và tên: .. Thời gian: 180 phút (không kể thời gian giao đề)
Số báo danh: .....	 Đề gồm có 02 trang
ĐỀ RA
Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau:
Câu 1: (3,0 điểm) Lặp xâu	LAPXAU.PAS
Cho hai xâu St1 và St2, Các xâu không quá 255 ký tự được lấy từ tập ‘A’..’Z’.
Yêu cầu: Hãy tìm K là số lần xuất hiện của xâu St1 trong xâu St2.
Dữ liệu vào: Cho trong file văn bản LAPXAU.INP có cấu trúc như sau:
	- Dòng 1: Ghi xâu St1
	- Dòng 2: Ghi xâu St2
Dữ liệu ra: Ghi ra file văn bản LAPXAU.OUT theo cấu trúc sau:
- Dòng 1: Ghi số K tìm được
Ví dụ:
LAPXAU.INP 
LAPXAU.OUT
ABA
ABABABBA
2
Câu 2: (3,5 điểm) Xóa số	XOASO.PAS
Trong giờ học tự chọn môn toán, giáo viên tổ chức cuộc thi cho tất cả các học sinh trong lớp. Học sinh đạt được giải nhất sẽ được thưởng điểm 10, luật thi như sau:
Giáo viên đưa ra một số nguyên dương X có n chữ số, các học sinh cần thực hiện xóa đi k chữ số trong n chữ số đã cho và giữ nguyên vị trí các chữ số còn lại, học sinh nào có số còn lại lớn nhất là người chiến thắng. “Nam” là một học sinh giỏi toán đã suy nghĩ “Muốn chiến thắng trong cuộc thi, mình phải tìm được số lớn nhất có thể tạo ra bằng cách trên”. Tuy nhiên để tìm số lớn nhất được tạo ra cũng không đơn giản.
Yêu cầu: Hãy giúp “Nam” tìm số nguyên Y lớn nhất.
Dữ liệu vào: Cho trong file văn bản XOASO.INP có cấu trúc như sau:
	- Dòng 1: Ghi hai số nguyên dương n và k, hai số được ghi cách nhau ít nhất một dấu cách. (0<k<n<32000)
- Dòng 2: Ghi số X.
Dữ liệu ra: Ghi ra file văn bản XOASO.OUT theo cấu trúc sau:
- Dòng 1: Ghi số Y tìm được.
Ví dụ: 
XOASO.INP 
XOASO.OUT 
9 4
944876268
98768
Câu 3: (3,5 điểm) Đếm nhóm bạn trong Hội trại	NHOMBAN.PAS
	Trong một Hội trại chào nừng 26/3 do Tỉnh Đoàn tổ chức, có N học sinh tham gia, trong đó có một số học sinh quen nhau. Một số học sinh được gọi là cùng 1 nhóm bạn, nếu bất kì một học sinh nào thuộc nhóm đều có quen ít nhất 1 học sinh khác trong cùng nhóm đó.
Yêu cầu: Hãy đếm xem có bao nhiêu nhóm bạn trong N học sinh tham gia Hội trại.
Dữ liệu vào: Cho trong file văn bản NHOMBAN.INP, có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N, là số lượng học sinh tham gia Hội trại. 
(1 ≤ N ≤ 100).
- Trong N dòng tiếp theo: Mỗi dòng ghi N số nguyên dương a[i,j] với ý nghĩa:
a[i,j] = 1 nếu học sinh i quen học sinh j (với i ≠j).
a[i,j] = 0 nếu học sinh i không quen học sinh j (với i ≠j). 
a[i,i] = 1 (học sinh i được xem là quen bản thân nó).
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. 
Dữ liệu ra: Ghi ra file văn bản NHOMBAN.OUT, theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương K, là số lượng nhóm bạn tìm được trong N học sinh tham gia Hội trại.
Ví dụ:
NHOMBAN.INP
NHOMBAN.OUT
5
1 0 0 1 1
0 1 1 0 0
0 1 1 0 0
1 0 0 1 1
1 0 0 1 1
2
==HẾT==