Kỳ thi chọn học sinh giỏi tỉnh lớp 11 năm học 2013 - 2014 môn thi: Tin học - THPT Bảng A

SỞ GD& ĐT NGHỆ AN
Đề thi chính thức 
KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 11
 NĂM HỌC 2013 - 2014
 (Đề thi gồm 2 trang)
Môn thi: TIN HỌC- THPT BẢNG A
Thời gian: 150 phút (không kể thời gian giao đề)
TỔNG QUAN BÀI THI
Bài
Tên file nguồn
File Input
File Output
Thời gian chạy
Điểm
Bài 1
THANHGO.PAS
THANHGO.INP
THANHGO.OUT
1 giây
5
Bài 2
MIN.PAS
MIN.INP
MIN.OUT
1 giây
6
Bài 3
SDD.PAS
SDD.INP
SDD.OUT
1 giây
5
Bài 4
SUBARR.PAS
SUBARR.INP
SUBARR.OUT
1 giây
4
Bài 1. (5 điểm)	 THANH GỖ
	Cha của Pinocchio muốn làm lại cho Pinocchio một cái mũi mới. Ông có N thanh gỗ, thanh gỗ i có độ dài ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để lấy ra thanh gỗ có độ dài cần thiết:
	- Nếu còn lại 1 thanh gỗ thì ông ta sẽ lấy thanh gỗ này làm mũi cho Pinocchio.
	- Nếu còn nhiều hơn một thanh gỗ thì ông ta sẽ làm như sau :
	Bước 1: Chọn ra thanh gỗ i có độ dài ai nhỏ nhất, tiếp theo chọn thanh gỗ j có độ dài aj nhỏ nhất trong các thanh còn lại.
 Bước 2: Nếu ai = aj thì vứt bỏ bớt một thanh, quay về bước 1.
 Bước 3: Nếu ai < aj thì ta sẽ cắt khỏi thanh aj đi một đoạn bằng ai, quay lại bước 1.
	Yêu cầu: Hãy tính độ dài thanh gỗ mà ông ta nhận được để làm mũi cho Pinocchio.
Giới hạn: 1 £ N £ 10000; 1 £ ai £ 109.
Dữ liệu: Vào từ file văn bản THANHGO.INP: Dòng đầu là số N, dòng sau là N số a1, a2,, an.
Kết quả: Ghi ra file văn bản THANHGO.OUT: Số X là độ dài thanh gỗ tìm được.
(Các số trên cùng một dòng của file dữ liệu vào ghi cách nhau ít nhất một ký tự trống)
Ví dụ:	
THANHGO.INP
THANHGO.OUT
3
2 3 4
1
Bài 2. (6 điểm) 	SỐ NHỎ NHẤT
Cho mét sè nguyªn d­¬ng K vµ mét x©u ký tù S. X©u S chØ gåm c¸c ký tù lµ c¸c ch÷ c¸i la tinh th­êng ‘a’..‘z’ vµ c¸c ch÷ sè ‘0’..‘9’, trong ®ã cã Ýt nhÊt K ký tù lµ ch÷ sè. B¹n h·y viÕt mét ch­¬ng tr×nh lo¹i bá mét sè ký tù ra khái x©u S sao cho K ký tù cßn l¹i theo ®óng thø tù ®ã t¹o nªn sè nhá nhÊt. Trong K ký tù cßn l¹i cã thÓ cho phÐp c¸c ch÷ sè 0 ®øng ®Çu.
D÷ liÖu: Vµo tõ file v¨n b¶n MIN.INP: Dßng thø nhÊt là sè nguyªn d­¬ng K (K ≤ 10). Dßng thø hai ghi x©u S cã ®é dµi nhá h¬n 250.
KÕt qu¶: Ghi ra file v¨n b¶n MIN.OUT: Gåm mét dßng ghi ra K ký tù cßn l¹i t¹o nªn sè nhá nhÊt.
Ví dụ:	
MIN.INP
MIN.OUT
4
307uv5x1y08mnp
0108
Bài 3. (5 điểm) 	SỐ ĐƠN ĐIỆU 
Số a1a2an được gọi là số đơn điệu nếu ai ai+2 hoặc ai > ai+1 < ai+2 (i=Số có một chữ số; số có hai chữ số khác nhau cũng được gọi là số đơn điệu lần lượt có độ dài bằng 1; 2.	
Ví dụ: Các số 5, 58, 3748, 32435465768 là số đơn điệu vì: 
Số 5 có 1 chữ số
Số 58 có 2 chữ số khác nhau.
Số 3748 có: 3 4 < 8
	Số 32435465768 ta thấy: 3 > 2 3 4 5 6 < 8
Yêu cầu: Viết chương trình xác định số chữ số lớn nhất tạo thành số đơn điệu của một số cho trước.
D÷ liÖu: Vµo tõ file v¨n b¶n SDD.INP: Gồm một số nguyên dương N có không quá 75 chữ số.
KÕt qu¶: Ghi ra file v¨n b¶n SDD.OUT: Chứa số nguyên là số chữ số lớn nhất tạo thành đoạn số đơn điệu của số N.
Ví dụ: 
SDD.INP
SDD.OUT
3748
4
Bài 4. (4 điểm)	 	SUBARRAY
	Cho một dãy gồm N số nguyên a1, a2,, aN và số nguyên dương K. Dãy con ai, ai+1,, aj (1 £ I £ j £ N) là dãy được tạo từ các phần tử liên tiếp của dãy A, bắt đầu từ phần tử thứ i và kết thúc ở phần tử thứ j.
Yêu cầu: Tìm số lượng dãy con của A có ít nhất K phần tử bằng nhau.
Dữ liệu: Vào từ file văn bản SUBARR.INP: 
Dòng đầu tiên chứa hai số nguyên N, K (1 £ K £ N £ 4.105). Dòng thứ hai chứa N số nguyên a1, a2,, aN (ai £ 109);
Kết quả: Ghi ra file văn bản SUBARR.OUT: Ghi ra số lượng dãy con tìm được.
(Các số trên cùng một dòng của file dữ liệu vào ghi cách nhau ít nhất một ký tự trống)
Ví dụ:	
SUBARR.INP
SUBARR.OUT
4 2
1 2 1 2
3
-------- Hết --------
Chú ý: Giám thị không giải thích gì thêm.
Họ và tên thí sinh:.........................................................................Số báo danh:.............................