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

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH 
Năm học 2016 – 2017
MÔN: TIN HỌC
Ngày thi 13/10/2016
(Thời gian 180 phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 02 trang
Tổng quan đề thi:
Bài
Tên bài
Tên Chương trình
Input
Output
Thời gian/Test
1
Dãy con hoàn hảo
seq.*
seq.inp
seq.out
1 giây
2
Vòng ngọc
jewel.*
jewel.inp
jewel.out
1 giây
3
Tổ tiên chung gần nhất
lca.*
lca.inp
lca.out
1 giây
Trong đó * là “pas” hoặc “cpp” tùy theo ngôn ngữ lập trình là Pascal hay C++.
Bài 1 (6.0 điểm): Dãy con hoàn hảo.
Cho một dãy số nguyên dương a1, a2, a3, , an và một số nguyên k. 
Một dãy con 1 ≤ i ≤ j ≤ n được gọi là hoàn hảo nếu như:
ai + ai + 1 + ai + 2 +  + aj = k.
Yêu cầu: Hãy đếm xem có bao nhiêu dãy con hoàn hảo từ dãy đã cho.
Dữ liệu vào: File văn bản SEQ.INP gồm:
+ Dòng đầu tiên chứa số n và k cách nhau bởi dấu cách.
+ Dòng tiếp theo chứa n số nguyên ai (ai ≤ 103).
Dữ liệu ra: file văn bản SEQ.OUT một số duy nhất là kết quả tìm được.
Ví dụ:
SEQ.INP
SEQ.OUT
6 6
1 2 3 3 5 1
3
Ràng buộc:
+ 50% số Test, tương ứng với n ≤ 103, k ≤ 106.
+ 50% số Test, tương ứng với n ≤ 106, k ≤ 109.
Câu 2 (7.0 điểm): Vòng ngọc.
	Cửa hàng đồ trang sức nơi Bờm đang làm việc có các loại vòng ngọc được các bạn trẻ rất yêu thích. Trong đó có loại vòng ngọc trang sức gồm N hạt trên mỗi hạt ghi các chữ cái ‘a’.. ‘z’. Khi tháo vòng ngọc ở một vị trí bất kì ta sẽ thu được một xâu S là các kí tự ghi trên chuỗi ngọc. Một hôm, với bản tính nghịch ngợm của mình, Bờm đã tháo khóa tất cả các vòng ngọc. Tuy nhiên sau khi tháo ra Bờm rất khó phân biệt từng chuỗi ngọc thuộc loại nào để xếp lại lên giá. Bờm sẽ lấy ra một loại vòng ngọc mẫu, sau đó phân biệt xem trong các vòng ngọc đã tháo cái nào cùng loại với loại mẫu đó. Bạn hãy viết chương trình giúp Bờm việc này nhé. 
Yêu cầu: Tìm trong các vòng ngọc đã tháo cái nào cùng loại với mẫu, cái nào không cùng.
Dữ liệu vào: File văn bản JEWEL.INP.
+ Dòng thứ nhất chứa xâu S có độ dài N được tạo từ vòng ngọc mẫu.
+ K dòng tiếp theo: mỗi dòng chứa một xâu cần phân biệt.
Dữ liệu ra: File văn bản JEWEL.OUT gồm K dòng, trong đó dòng thứ i: ghi số 1 nếu chuỗi ngọc cùng loại vòng ngọc mẫu, ghi số 0 nếu không cùng loại.
jewel.inp
jewel.out
abcd
ab
abba
cdab
aaaaa
0
0
1
0
Ràng buộc:
50% số Test, tương ứng với N,K ≤ 100. 
50% số Test, tương ứng với N ≤ 103, K ≤ 104.
Bài 3 (7.0 điểm): Tổ tiên chung gần nhất.
	Xét một đồ thị cây N đỉnh, các đỉnh đánh số từ 1 đến N, đỉnh 1 là gốc. Cha của một đỉnh là đỉnh kề với đỉnh đó và gần gốc hơn. Có M cặp đỉnh (u, v) có đường nối với nhau.
Yêu cầu: Cho cặp đỉnh (u,v) bạn phải đưa ra đỉnh x nằm trên hai đường đi từ 1 đến u và từ 1 đến v sao cho tổng khoảng cách từ x đến u và v là nhỏ nhất.
Dữ liệu vào: Từ file văn bản LCA.INP.
+ Dòng 1: Ghi 3 số nguyên N, M, K (1 ≤ N, M, K ≤ 50,000).
+ M dòng tiếp: Ghi M cặp số nguyên dương (u,v) thể hiện một cạnh nối đỉnh u và v của cây (1 ≤ u, v ≤ N, u ≠ v).
+ K dòng tiếp: Ghi K cặp số nguyên dương (u,v) mà chúng ta cần tìm khoảng cách nhỏ nhất theo yêu cầu. (1 ≤ u, v ≤ N, u có thể trùng với v).
Dữ liệu ra: Ghi trong file văn bản LCA.OUT gồm K dòng mỗi dòng là một đỉnh x ứng với cặp đỉnh (u,v) tìm được.
Ví dụ:
lca.inp
lca.out
5 4 3
1 2
1 3
3 4
3 5
4 5
1 3
2 3
3
1
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:.............................................................................................