Kỳ thi chọn học sinh giỏi cấp tỉnh lớp 12 năm học 2010 – 2011 môn thi: tin học lớp 12 THPT - Bảng B

 SỞ GD&ĐT NGHỆ AN
Đề chớnh thức
 (Đề thi cú 03 trang)
KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 12
NĂM HỌC 2010 – 2011
Mụn thi: TIN HỌC LỚP 12 THPT - BẢNG B
Thời gian làm bài: 180 phỳt
Bài 1. (5,5 điểm)	 tần số
	Cho dãy số nguyên dương, số lần xuất hiện của một số được gọi tần số của số nguyên đó. Hãy tìm số nguyên dương có tần số cao nhất và tần số tương ứng của nó.
	 Dữ liệu vào: Cho từ file văn bản MAX.INP bao gồm:
Dòng đầu tiên chứa một số nguyên N( 1≤ N ≤ 10000) là số lượng các số nguyên trong dãy.
Mỗi dòng trong N dòng tiếp theo chứa số nguyên M( 1≤ M ≤ 1000) trong dãy.
 Kết quả: Ghi ra file văn bản MAX.OUT, gồm 2 số nguyên viết trên một dòng, số thứ nhất ghi số nguyên có tần số cao nhất, số thứ 2 là tần số của nó( trong trường hợp có nhiều số nguyên có tần số cao nhất bằng nhau, hãy đưa ra số nguyên nhỏ nhất và tần số của nó). Hai số cách nhau một ký tự trắng.
MAX.INP
MAX.OUT
MAX.INP
MAX.OUT
9
1
2
5
6
3
7
2
5
2
2 3
7
2
4
6
7
7
2
4
2 2
 Bài 2. (5,5 điểm) Mã Số
	Để tiện trong công tác quản lý, một công ty đã gắn mã số cho các nhân viên của mình. Mã số của mỗi nhân viên bao gồm bảy chữ số( gọi là phần đầu của mã nhân viên) và một chữ cái in hoa nối phía sau. Chữ cái này được tính toán từ bảy chữ số phần đầu của mã theo các bước như sau: 
	1. Chữ số thứ I được gắn một số nguyên dương aI được gọi là trọng lượng của nó( thứ tự các chữ số trong phần đầu của mã tính từ trái qua phải). Người ta lấy lần lượt các chữ số trong mã nhân với trọng lượng tương ứng của nó. 
	2.Cộng tất cả các kết quả. 
	3. Tìm số dư của phép chia tổng trên cho số nguyên dương K ( 1≤ K ≤ 11) 
	4. Mỗi số dư tương ứng với một chữ cái in hoa. Chữ cái in hoa tương ứng tìm được là chữ cái nối phía sau của mã nhân viên.
	Cho trước phần đầu của mã nhân viên, hãy tìm chữ cái in hoa nối phía sau.
 Dữ liệu vào: Từ file văn bản MASO.INP có cấu trúc như sau:
Dòng đầu tiên ghi số nguyên dương K. 
Dòng thứ 2 ghi một xâu gồm 7 chữ số là phần đầu của mã nhân viên
Dòng thứ 3 ghi 7 số nguyên dương, số thứ I là trọng lượng của chữ số thứ I trong phần đầu của mã. Các số cách nhau một ký tự trắng.
Dòng cuối cùng ghi một xâu có độ dài Kgồm các chữ cái tiếng Anh in hoa, chữ cái thứ I tương ứng với số I-1 là số dư của phép chia của tổng tìm được cho K.
 Kết quả: Ghi ra file văn bản MASO.OUT, chứa chữ cái tìm được.
	Ví dụ: 
MASO.IN 
MASO.OUT
11
6830907
2 7 6 5 4 3 2
JABCDEFGHIZ
D 
Bài 3. (4,5 điểm) Sa mạc
	Sa mạc là lưới ô vuông cấp MxN ( 1≤ N,M ≤ 100). Trên mỗi ô của lưới người ta ghi một số nguyên a( 1≤ a ≤ 100) được gọi là năng lượng của ô đó. Một con lạc đà đang ở ô (i,j) của lưới chỉ được đi đến một trong hai ô (i+1,j) hoặc ô (i,j+1). Lạc đà đi đến ô nào thì hấp thụ được nguồn năng lượng tại ô đó. Hãy tìm cho lạc đà một đường đi từ ô (1,1) đến ô (M,N) theo nguyên tắc trên và hấp thụ được nhiều năng lượng nhất.
	Dữ liệu vào: Từ file văn bản SAMAC.INP, dòng đầu tiên ghi 2 số nguyên dương theo thứ tự M, N.
	Dòng thứ I trong M dòng tiếp theo ghi N số nguyên dương, số thứ J là năng lượng trên ô (I , J) của sa mạc. (số thứ tự của các số trên một dòng tính từ trái qua phải)
	Kết quả: Ghi ra file văn bản SAMAC.OUT, dòng đầu tiên ghi số S là năng lượng mà lạc đà hấp thụ được. Từ dòng thứ 2 trở đi mỗi dòng ghi 2 số nguyên dương là toạ độ các ô theo thứ tự trên đường đi của lạc đà.
Ví dụ:
SAMAC.INP
SAMAC.OUT
5
5 1 3 4
6 7 9 1 5
1 1 8 4 1
1 3 4 3 3
 41
1
1
2 2
2 3
3 3
3 4
4 4
4 5 
Cả hai file dữ liệu, các số trên một dòng cách nhau một ký tự trắng.
Bài 4. (4,5 điểm) Hội trại
	Nhân dịp ngày thành lập công ty, ban Giám đốc công ty X tổ chức cho cán bộ công nhân viên một cuộc hội trại. Thời điểm tính trong ngày hội trại là phút, thời điểm ban đầu là 0. Công ty có N cán bộ công nhân viên. Người thứ I có mặt tại hội trại từ thời điểm aI đến thời điểm bI. Hãy lập trình giải quyết các công việc sau đây:
Tìm cho ban Giám đốc một thời điểm sớm nhất đến thăm hội trại để gặp được nhiều cán bộ nhất.
Tìm một khoảng thời gian dài nhất tại địa điểm hội trại không có ai cả, nếu có nhiều khoảng thời gian như thế hãy đưa ra khoảng thời gian sớm nhất.
Dữ liệu vào: Từ file văn bản: HOITRAI.INP, có cấu trúc như sau:
Dòng đầu tiên ghi số N là số cán bộ của công ty (1≤ N ≤ 10000) .
Dòng thứ I trong N dòng tiếp theo ghi 2 số nguyên dương aI và bI là khoảng thời gian có mặt tại hội trại của cán bộ thứ I.
 Kết quả: Ghi ra file văn bản HOITRAI.OUT như sau:
Dòng đầu tiên ghi số T là thời điểm ban Giám đốc đến thăm hội trại.
Dòng thứ 2 ghi 2 số nguyên a, b là khoảng thời gian từ a đến b không có ai ở hội trại. Nếu không tìm được ghi số 32675 hai lần.
Cả hai file dữ liệu, các số trên một dòng cách nhau một ký tự trắng.
	Ví dụ:
HOITRAI.INP
HOITRAI.OUT
7
1 320
400 1000
351 1200
380 1336
452 1430
512 1230
623 1105
623
321 350
- - - Hết - - -
Họ và tên thí sinh . Số báo danh 
Chú ý: - Chương trình giải các bai1, bài 2, bài 3, bài 4 lần lượt ghi lên đĩa với các tên Bai1.pas; Bai2.pas; Bai3.pas; Bai4.pas.
 - Giám thị không phải giải thích gì thêm.