Đề thi chọn học sinh giỏi quốc gia Lớp 12 THPT năm 2005 môn Tin học(Bảng B - Đề 1)

BỘ GIÁO DỤC VÀ ĐÀO TẠO 	 Kè THI CHỌN HỌC SINH GIỎI QUỐC GIA
	 LỚP 12 THPT NĂM HỌC 2004-2005
Đề Thi Chính thức
Mụn: Tin học - Bảng B
Thời gian: 180 phỳt (Khụng kể thời gian giao đề)
Ngày thi: 10/03/2005
TỔNG QUAN BÀI THI NGÀY THỨ NHẤT BẢNG B
Tờn bài
Tờn chương trỡnh
File dữ liệu vào
File kết quả
BÀI 1
Đúng gúi sản phẩm
ZXY.PAS
ZXY.INP
ZXY.OUT
BÀI 2
Chữ số
DIGIT.PAS
DIGIT.INP
DIGIT.OUT
Hóy lập trỡnh giải cỏc bài toỏn sau:
Bài 1. Đúng gúi sản phẩm	 Tờn file chương trỡnh: ZXY.PAS
Ở đầu ra của một dõy chuyền sản xuất trong nhà mỏy ZXY cú một mỏy xếp tự động. Sau khi kết thỳc việc gia cụng trờn dõy chuyền, cỏc sản phẩm sẽ được xếp vào cỏc hộp cú cựng dung lượng M. Sản phẩm rời khỏi dõy chuyền được xếp vào hộp đang mở (khi bắt đầu ca làm việc cú một hộp rỗng được mở sẵn) nếu như dung lượng của hộp cũn đủ để chứa sản phẩm. Trong trường hợp ngược lại, mỏy sẽ tự động đúng nắp hộp hiện tại, cho xuất xưởng rồi mở một hộp rỗng mới để xếp sản phẩm vào. Trong một ca làm việc cú n sản phẩm đỏnh số từ 1 đến n theo đỳng thứ tự mà chỳng rời khỏi dõy chuyền. Sản phẩm thứ i cú trọng lượng là ai, i = 1, 2, , n. Ban Giỏm đốc nhà mỏy qui định rằng sản phẩm xuất xưởng của mỗi ca làm việc phải được xếp vào trong khụng quỏ k hộp. 
Yờu cầu: Hóy giỳp người quản đốc của ca làm việc xỏc định giỏ trị M nhỏ nhất sao cho số hộp mà mỏy tự động cần sử dụng để xếp dóy n sản phẩm xuất xưởng của ca khụng vượt quỏ số k cho trước.
Dữ liệu: Vào từ file văn bản ZXY.INP:
Dũng đầu tiờn chứa hai số nguyờn n và k, (1≤ k ≤ n ≤ 15000);
Dũng thứ i trong n dũng tiếp theo chứa số nguyờn dương ai (ai ≤30000), i =1, 2, , n.
Cỏc số trờn một dũng cỏch nhau ớt nhất một dấu cỏch.
Kết quả: Ghi ra file ZXY.OUT một số nguyờn duy nhất là dung lượng của hộp.
Vớ dụ:	
ZXY.INP
ZXY.OUT
9 4
1
1
1
3
2
2
1
3
1
5
Bài 2. Chữ số	 Tờn chương trỡnh: DIGIT.PAS
Cho xõu M khụng quỏ 127 ký tự lấy từ tập F = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}và khụng bắt đầu bằng ký tự 0. Gọi S là xõu với giỏ trị ban đầu là xõu M. 
Người ta biến đổi M theo quy tắc sau: đếm số lần xuất hiện cỏc ký tự 0, 1, 2, . . . , F, gọi Ki là số lần xuất hiện ký tự i (với i lần lượt là 0, 1, 2, . . . F). Với cỏc Ki ạ 0 người ta viết liờn tiếp xõu biểu diễn số Ki trong cơ số 16 và ký tự i. Xõu kết quả thu được là giỏ trị mới của M. Sau mỗi lần biến đổi người ta lại viết tiếp M vào sau S.
Vớ dụ, với M = '150A', S nhận giỏ trị ban đầu là '150A'.
Sau lần biến đổi thứ nhất ta cú M là '1011151A' và S ='150A1011151A'.
Sau lần biến đổi thứ 2 ta cú M là '1051151A' và S ='150A1011151A1051151A'.
Sau lần biến đổi thứ 3 ta cú M là '1041251A' và S = ‘150A1011151A1051151A1041251A’.
Yờu cầu: Cho xõu M, số lần biến đổi L ( 0 ≤ L ≤ 107) và X là một ký tự từ tập F. Hóy đếm số lần xuất hiện X trong S thu được sau L lần biến đổi M.
Dữ liệu: Vào từ file văn bản DIGIT.INP :
Dũng thứ nhất chứa xõu M,
Dũng thứ 2 chứa số nguyờn L 
Dũng thứ 3 chứa ký tự X. 
Kết quả: Đưa ra file văn bản DIGIT.OUT một số nguyờn - số lần xuất hiện X.
Vớ dụ:
DIGIT.INP
DIGIT.OUT
150A
3
2
1
_________________________________________
Ghi chỳ: 
Thớ sinh khụng được sử dụng tài liệu
Giỏm thị khụng giải thớch gỡ thờm.