Đề thi chọn học sinh giỏi lớp 12 cấp tỉnh môn Tin học - Năm học 2015-2016 - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI, HỌC VIÊN GIỎI
 LỚP 12 CẤP TỈNH NĂM HỌC 2015 – 2016
MÔN: TIN HỌC - THPT
Ngày thi: 02/12/2015
(Thời gian 180 phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 03 trang
Tổng quan đề thi:
Câu 1: Khiêu vũ
KHIEUVU.PAS
KHIEUVU.INP
KHIEUVU.OUT
Câu 2: Hiếu thảo
HIEUTHAO.PAS
HIEUTHAO.INP
HIEUTHAO.OUT
Câu 3: Chào hỏi
CHAOHOI.PAS
CHAOHOI.INP
CHAOHOI.OUT
(Yêu cầu các thí sinh đặt tên file bài thi và tên file dữ liệu đúng như trên)
Câu 1 (7 điểm): Khiêu vũ. 
	Trong lớp học khiêu vũ có N học viên gồm các học viên nam và các học viên nữ, các học viên được xếp thành một hàng. Giáo viên muốn chọn ra một nhóm gồm những học viên đứng liền nhau và có số lượng học viên nam bằng số lượng học viên nữ để hướng dẫn. 
Yêu cầu: Viết chương trình đưa ra số cách chọn thỏa mãn yêu cầu của giáo viên.
Dữ liệu vào: Tệp văn bản KHIEUVU.INP gồm hai dòng:
	- Dòng 1 ghi số nguyên dương N (N £ 105).
	- Dòng 2 ghi mô tả các học viên đứng trong hàng, là một chuỗi gồm N chữ số 1 và 0 viết liền nhau trong đó 1 tương ứng với học viên nam và 0 tương ứng với học viên nữ.
Dữ liệu ra: Tệp văn bản KHIEUVU.OUT ghi một số duy nhất là số cách chọn thỏa mãn yêu cầu đề bài.
Ví dụ:
KHIEUVU.INP
KHIEUVU.OUT
8
10010101
13
Câu 2 (8 điểm): Hiếu thảo.
Ngày mùng 6 tháng Giêng âm lịch hàng năm, khu du lịch tâm linh chùa Bái Đính tổ chức khai mạc lễ hội đầu năm cầu cho quốc thái dân an. Nhân dân cả nước cũng như du khách quốc tế nô nức tìm đến chùa Bái Đính để dự lễ hội. Ai đi lễ cũng đều mua các món quà lưu niệm mang về làm quà cho người thân trong gia đình mình. Phương quyết định cũng đi chùa Bái Đính để mua một món quà tặng bà cầu mong bà luôn khỏe mạnh và sống lâu. Biết rằng để đến được chùa Bái Đính từ nơi học Phương phải đi qua một số huyện và từ chùa Bái Đính cũng phải đi qua một số huyện để về quê nơi bà sống. Biết rằng hệ thống giao thông có N huyện, hai huyện cạnh nhau có tối đa một đường nối trực tiếp và luôn tìm được ít nhất một đường đi giữa hai huyện bất kì.
Yêu cầu: Hãy viết một chương trình giúp Phương tìm ra đường đi ngắn nhất từ nơi Phương học đến chùa Bái Đính để mua quà và mang quà về tặng bà.
Dữ liệu vào: File văn bản HIEUTHAO.INP. 
	Dòng đầu là 5 số N, M, A, B, C trong đó N là số lượng các huyện, M là số lượng các đường đi nối trực tiếp giữa hai huyện bất kì. A là nơi Phương học, B là địa điểm của chùa Bái Đính và C là nơi bà Phương sống. 
( 5 £ N £ 20000, 1 £ A, B, C £ N);
M dòng tiếp theo mỗi dòng gồm có 3 số X, Y, Z trong đó X và Y là mã của hai huyện có đường nối trực tiếp và Z là độ dài của con đường này.
	(1 £ X, Y £ N, 1 £ Z £ 20 );
	Dữ liệu ra: File văn bản HIEUTHAO.OUT chỉ ghi một số duy nhất là độ dài đường đi ngắn nhất.
Ví dụ:
HIEUTHAO.INP
HIEUTHAO.OUT
6 7 2 1 4
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
6
Câu 3 (5 điểm): Chào hỏi.
	Trong triều đình phong kiến ngày xưa, các quan được phong phẩm hàm từ cao xuống thấp. Cao nhất là nhất phẩm, sau đó là nhị phẩm, tam phẩm Qui ước đánh số các phẩm hàm đó ương ứng là 1, 2, 3,, N.
	Có N viên quan với các phẩm hàm khác nhau trong số N phẩm hàm {1, 2, 3, , N}. Mỗi viên quan được Nhà Vua phong cho cai quản một vùng nào đó trong số N vùng {1, 2, 3, N}. Cung điện của Nhà Vua luôn đặt ở vùng 1.
	Theo tục lệ của triều đình, mỗi khi một viên quan có phẩm hàm nhỏ hơn đi qua vùng đất do viên quan có phẩm hàm cao hơn cai quản thì phải vào chào hỏi (tất nhiên mỗi lần như vậy vị quan có phẩm hàm nhỏ hơn đều phải sắm một lễ vật chào hỏi). 
	Hệ thống giao thông là các đường đi hai chiều đảm bảo hai vùng bất kì đều có thể đi được đến nhau. Hơn nữa, con đường này là duy nhất (hệ thống giao thông có dạng một cây).
	Yêu cầu: Viết chương trình để chỉ ra trên hành trình từ vùng mình cai quản đi vào chầu Nhà Vua mỗi vị quan phải chuẩn bị bao nhiêu lễ vật.
	Dữ liệu vào: File văn bản CHAOHOI.INP.
Dòng đầu tiên ghi N (N £ 2.105).
N-1 dòng tiếp theo, dòng thứ i ghi hai số ai, bi là số hiệu hai vùng đất ở hai đầu của một con đường, mỗi số cách nhau một khoảng trắng (1 £ ai,bi £ N).
N dòng cuối, dòng thứ i ghi số hiệu vùng đất mà viên quan có phẩm hàm thứ i cai quản. 
	Dữ liệu ra: File văn bản CHAOHOI.OUT gồm N dòng, dòng thứ i ghi số lễ vật mà vị quan có phẩm hàm i phải chuẩn bị khi vào chầu Vua.
	Ví dụ:
CHAOHOI.INP
CHAOHOI.OUT
5
1 4
5 4
1 3
2 4
4
2
1
5
3
0
1
0
2
1
___________Hết___________
Họ và tên thí sinh :..................................................... Số báo danh ................................
Họ và tên, chữ ký: 	Giám thị 1:........................................................................................
Giám thị 2:........................................................................................