Đề thi chọn học sinh giỏi cấp Thành phố môn Tin học Lớp 12 - Bảng B - Sở GD&ĐT Thành phố Đà Nẵng

SỞ GIÁO DỤC& ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI THÀNH PHỐ
 THÀNH PHỐ ĐÀ NẴNG LỚP 12 THPT NĂM HỌC 2006-2007 
 --------------------- -----------------------------------
 Môn: TIN HỌC Bảng B
 Thời gian: 180 phút (không tính thời gian giao đề)
 Ngày thi: 24.01.2007
ĐỀ THI CHÍNH THỨC Chú ý: Bài thi gồm có 2 bài trong 2 trang
Tổng quan đề thi
Lá bài
Phân phối kênh
Tên bài làm
BL1.PAS
BL2.PAS
Dữ liệu vào
Labai.inp
Kenh.inp
Dữ liệu ra
Labai.out
Kenh.out
Giới hạn
1 giây
2 giây
Bài 1:(5 điểm) 	Lá bài
	Có N lá bài với các số hiệu là 1, 2, ..., N (N £ 50). Trên lá bài i ghi một số nguyên dương F[i], 1 £ F[i] £ N. 
	Yêu cầu: Hãy tìm nhiều lá bài nhất sao cho tập các số hiệu của chúng bằng với tập các số ghi trên các lá bài đó.
	Dữ liệu vào: Đọc từ file text LABAI.INP có cấu trúc như sau:
	·	Dòng thứ nhất chứa số nguyên dương N.
	·	Các dòng tiếp theo, mỗi dòng chứa 10 số (cho đến khi hết N số) lần lượt là các số ghi trên các lá bài, từ lá bài 1 đến lá bài N, mỗi số cách nhau ít nhất một dấu cách.
	Dữ liệu ra: Kết quả ghi ra file text LABAI.OUT có cấu trúc như sau:
	·	Dòng thứ nhất ghi số lượng lá bài.
	·	Các dòng tiếp theo, mỗi dòng ghi 10 số hiệu của các lá bài được chọn, các số hiệu ghi theo thứ tự tăng dần cho đến hết, mỗi số cách nhau ít nhất một dấu cách.
	Ví dụ:
LABAI.INP
LABAI.OUT
14
6 5 1 3 4 2 8 10 7 9
3 2 1 9
10
1 2 3 4 5 6 7 8 9 10
Bài 2:(5 điểm) 	Phân phối kênh
	Công ty dịch vụ mạng máy tính cần phân phối kênh hoạt động phục vụ cho N (N <1000) yêu cầu của khách hàng đánh số từ 1 đến N. Với mỗi khách hàng thứ i, ta biết khoảng thời gian yêu cầu sử dụng kênh là (Si, Ti), i = 1, 2 , ..., N (khách hàng sẽ sử dụng kênh từ thời điểm Si đến thời điểm Ti). Thời gian chuyển giao quyền sử dụng kênh từ khách hàng này cho khách hàng khác là không đáng kể. Như vậy, nếu hai khách hàng nào đó được bố trí làm việc trên cùng một kênh thì các khoảng thời gian sử dụng của họ chỉ có thể có nhiều nhất một thời điểm chung.
	Yêu cầu: Hãy tìm cách phân phối sao cho sử dụng ít kênh nhất mà vẫn đảm bảo phục vụ cho N yêu cầu của khách hàng.
	Dữ liệu vào: Đọc từ file text KENH.INP có cấu trúc như sau:
Dòng đầu tiên chứa số N.
Dòng thứ i trong số N dòng tiếp theo chứa hai số nguyên dương Si, Ti, i = 1, 2, ..., N mỗi số cách nhau ít nhất một dấu cách.
Dữ liệu ra: Kết quả ghi ra file text KENH.OUT có cấu trúc như sau:
Dòng đầu tiên ghi số lượng kênh cần sử dụng p.
Dòng thứ i trong số p dòng tiếp theo ghi các chỉ số của các khách hàng sử dụng kênh thứ i, i = 1, 2, ..., p.
Ví dụ:
KENH.INP
KENH.OUT
7
0 3
3 5
6 8
0 7
7 8
0 2
2 6
3
4 5
6 7 3
1 2
-------------------------------------------------HẾT-------------------------------------------------
Chú ý: Cán bộ coi thi không giải thích gì thêm