Đề 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 (Đề 1) (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 12/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
Tìm số
Number.*
Number.inp
Number.out
1 giây
2
Những đồng xu
Coins.*
Coins.inp
Coins.out
1 giây
3
Cây cầu dừa
Friend.*
Friend.inp
Friend.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): Tìm số.
Khi viết các số tự nhiên lẻ tăng dần từ 1, 3, 5, 7 liên tiếp nhau, ta nhận được một dãy các chữ số thập phân vô hạn, đoạn đầu của dãy sẽ là: 13579111315171921232527 Yêu cầu: Hãy tìm chữ số thứ N của dãy vô hạn trên.
Dữ liệu: Cho trong file NUMBER.INP gồm số nguyên dương N. 
Kết quả: Ghi kết quả ra file NUMBER.OUT.
Ví dụ:
NUMBER.INP
NUMBER.OUT
6
1
NUMBER.INP
NUMBER.OUT
13
7
Ràng buộc:
+ 50% số Test có N £ 106.
+ 50% số Test có 106 < N < 1015.
Bài 2 (7.0 điểm): Những đồng xu.
	Bạn được chọn trong tập vô hạn các đồng xu mệnh giá 1 Xu và 2 Xu sau đó xếp chúng thành một hàng thỏa mãn các điều kiện sau:
+ Các đồng xu có tổng mệnh giá là N Xu.
+ Đồng xu đầu tiên của hàng phải để xấp.
+ Các đồng xu sau đó có thể để xấp hoặc ngửa.
Hai cách xếp gọi là khác nhau nếu chúng khác nhau về số lượng đồng xu được sử dụng hoặc tồn tại ít nhất một vị trí i mà đồng xu thứ i ở cách này khác đồng xu thứ i ở cách kia về mệnh giá hoặc tính chất xấp ngửa.
Ví dụ với N = 2 ta có 3 cách xếp:
+ Đồng xu loại 2 Xu nằm xấp.
+ Đồng xu loại 1 Xu nằm xấp đứng trước đồng xu loại 1 xu nằm ngửa.
+ Đồng xu loại 1 Xu nằm xấp đứng trước đồng xu loại 1 xu nằm xấp.
Yêu cầu : Tính số cách xếp các đồng xu.
Do kết quả có thể rất lớn nên bạn chỉ cần đưa ra theo modulo 1,000,000,007.
Dữ liệu vào: Nhập dữ liệu trong file văn bản COINS.INP.
+ Dòng 1: Ghi số nguyên T là số bộ test (1 ≤ T ≤ 10000).
+ T dòng tiếp: Mỗi dòng ghi một số nguyên N (1 ≤ N ≤ 1000,000,000).
Dữ liệu ra: Ghi kết quả vào file văn bản COINS.OUT.
+ Gồm T dòng Ứng với mỗi giá trị N ghi ra một số nguyên tương ứng trên một dòng là kết quả tìm được.
Input
Output
3
1
2
3
1
3
8
Ràng buộc:
+ 30% số Test có N ≤ 20,T ≤ 100.
+ 30% số Test có N ≤ 106,T ≤ 1000.
+ 40% số Test có 106 ≤ N ≤ 109, T ≤ 10000.
Bài 3 (7.0 điểm): Cây cầu dừa.
	John đang sinh sống trên một quần đảo gồm N đảo, John sống ở đảo S. Các đảo khá gần nhau nên chẳng cần thuyền bè gì, John chỉ cần đốn một cây dừa nào đó và bắc ngang là có thể đi được từ đảo này sang đảo khác. Nếu chưa bắc được cầu thì John di chuyển qua các đảo bằng cách bơi bướm hay bơi ngửa đồng thời cũng là để tập thể dục luôn, nhưng Bạn John thì không biết bơi. Hiện tại John mới bắc được M cây cầu dừa. Bạn của John muốn sang thăm anh ấy với mục tiêu là nhanh nhất, bạn của John sống ở đảo F. Thời gian đi qua mỗi cây cầu mất T thời gian như nhau. 
Yêu cầu: Tìm số lượng đường đi nhanh nhất từ đảo S đến đảo F mà John đang ở.
Dữ liệu vào: Tệp văn bản FRIEND.INP.
+ Dòng thứ nhất: Chứa 5 số nguyên N, M, S, F và T.
+ M dòng tiếp theo: Mỗi dòng gồm hai số nguyên a, b. Trong đó a và b là số hiệu hai đảo được nối bởi duy nhất một cây cầu dừa.
Dữ liệu ra: Ghi vào tệp văn bản FRIEND.OUT.
	Hai số nguyên X,Y trong đó X là tổng thời gian nhanh nhất và Y là số đường đi nhanh nhất từ S đến F. Nếu không có đường đi đến F thì ghi duy nhất số 0.
Ràng buộc:
+ 1 ≤ S,F ≤ N ≤ 10000.
+ 1 ≤ M ≤ 1000000.
+ T ≤ 109.
Ví dụ:
FRIEND.INP
4 4 1 4 5
1 2 
2 4 
1 3 
3 4 
FRIEND.OUT
10 2
--------------------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:..............................................................................................