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

SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH
NĂM HỌC 2020 - 2021
MÔN: TIN HỌC
Ngày thi: 15/12/2020
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 04 bài, trong 03 trang
Tổng quan đề thi:
Bài
Tên bài
File chương trình
File dữ liệu vào
File dữ liệu ra
Thời gian
Bài 1
Học nhóm
SORT.*
SORT.INP
SORT.OUT
1 giây/test
Bài 2
Số có thứ tự N
NUMBER.*
NUMBER.INP
NUMBER.OUT
1 giây/test
Bài 3
Trò chơi
GAME.*
GAME.INP
GAME.OUT
1 giây/test
Bài 4
Cứu trợ
AID.*
AID.INP
AID.OUT
1 giây/test
- Dấu * được thay bởi PAS hoặc CPP của ngôn ngữ lập trình tương ứng là Pascal hoặc C++.
- Các số nguyên trên cùng một dòng trong bài 1, bài 3 và bài 4 được viết cách nhau ít nhất một khoảng trắng.
Hãy lập trình giải các bài toán sau:
Bài 1 (6,0 điểm): Học nhóm
	Hai bạn Bình và An rất yêu thích Toán học. Bình say mê tìm hiểu về cách sắp xếp dãy số theo chiều tăng hoặc chiều giảm, còn An luôn mong muốn tìm hiểu về các số hoàn hảo. Thầy giáo của Bình và An giao cho hai bạn làm một bài toán như sau: 
	Cho một dãy gồm số nguyên dương, hãy tìm ra các số hoàn hảo trong dãy và sắp xếp chúng thành một dãy không giảm (số nguyên được gọi là số hoàn hảo nếu tổng của tất cả các ước nhỏ hơn đúng bằng Ví dụ: số 6 là một số hoàn hảo vì 6 có 3 ước là 1, 2, 3 và 1 + 2 + 3 = 6).
Yêu cầu: Hãy giúp Bình và An lập trình giải bài toán trên.
Dữ liệu vào: File SORT.INP gồm 2 dòng
	+ Dòng đầu chứa một số nguyên 
	+ Dòng tiếp theo chứa số nguyên 
Dữ liệu ra: File SORT.OUT chứa một dòng là các số hoàn hảo tìm được và sắp xếp chúng thành dãy không giảm. Trường hợp không có số hoàn hảo thì dữ liệu ra ghi số 0.
Ví dụ:
SORT.INP
SORT.OUT
5
6 28 10 6 29
6 6 28
	Giới hạn test: 60% số test có 
	 20% số test có 
	 20% số test có 
Bài 2 (6,0 điểm): Số có thứ tự N
	là một số nguyên lớn được xây dựng theo quy tắc sau: Bắt đầu từ số nguyên 123 sau đó ghép số nguyên này với chính nó khi đã chuyển tất cả các số có giá trị bằng 1 thành số 3 và tất cả các số có giá trị bằng 3 thành số 1. Việc làm này được lặp lại cho đến khi số lượng chữ số của số không nhỏ hơn chữ số 
	Ví dụ: Với thì số là 123
	Với thì số là 123321
	Với thì số là 123321321123
	Với thì số là 123321321123321123123321
Yêu cầu: Tìm chữ số thứ của số 
Dữ liệu vào: File NUMBER.INP chứa duy nhất một số nguyên 
Dữ liệu ra: File NUMBER.OUT là giá trị chữ số thứ của số 
Ví dụ:
NUMBER.INP
NUMBER.OUT
NUMBER.INP
NUMBER.OUT
8
2
21
3
Giới hạn test:	80% số test có 
	20% số test có 
Bài 3 (4,0 điểm): Trò chơi
	Sau một năm học tập chăm chỉ, Huy đã đạt kết quả xuất sắc. Bố mẹ muốn thưởng cho Huy một phần thưởng xứng đáng và cho em quyền lựa chọn, điều đầu tiên Huy nghĩ tới đó là đi chơi tại công viên Khủng Long mới được xây dựng ở thành phố Ninh Bình. Ở đó có rất nhiều trò chơi thú vị và có một trò chơi mà Huy rất yêu thích. Biết rằng, Huy được bố mẹ cho một số tiền là và giả sử trong công viên có trò chơi, trò chơi thứ sẽ phải trả số tiền là , trò chơi mà Huy yêu thích có thứ tự là 
Yêu cầu: Giúp Huy tính xem có bao nhiêu cách khác nhau để chọn các trò chơi sao cho tổng chi phí là mà Huy vẫn được chơi trò chơi mình yêu thích?
Dữ liệu vào: File GAME.INP gồm 2 dòng
	+ Dòng đầu chứa ba số nguyên dương 
	+ Dòng tiếp theo chứa số nguyên không âm 
Dữ liệu ra: File GAME.OUT ghi một số nguyên duy nhất là số cách lựa chọn của Huy. Trong trường hợp không có cách chọn nào thì dữ liệu ra ghi số 0.
Ví dụ:
GAME.INP
GAME.OUT
GIẢI THÍCH
4 5 2
1 2 3 4 
1
Có 2 cách chọn trò chơi là 1, 4 và 2, 3 có tổng số tiền phải trả là 5 nhưng chỉ có một cách chọn 2 trò chơi 2, 3 là chứa trò chơi thứ 2 mà Huy yêu thích.
Giới hạn test:	80% số test có 
	20% số test có 
Bài 4 (4,0 điểm): Cứu trợ
	Sau khi nước rút trong trận lũ lụt lịch sử vừa qua, nhiều điểm dân cư ở miền Trung bị cô lập do đường bị hư hỏng. Điều đó khiến các đoàn cứu trợ không thể tiếp cận bằng đường bộ để chuyển hàng cứu trợ đến với người dân kịp thời. Để giúp người dân vượt qua khó khăn chính quyền các địa phương quyết định sửa chữa một số tuyến đường bị hư hỏng sao cho các đoàn cứu trợ có thể nhanh chóng đưa hàng cứu trợ đến với người dân. Dữ liệu khảo sát cho thấy có điểm dân cư bị cô lập được đánh thứ tự từ 1 đến Tại mỗi điểm dân cư có một số tuyến đường hai chiều bị hư hỏng nối trực tiếp điểm dân cư này đến các điểm dân cư khác. 
Yêu cầu: Hãy lập trình tìm ra phương án sửa chữa các tuyến đường để tổng thời gian khắc phục là ít nhất mà các đoàn cứu trợ đến được tất cả các điểm dân cư bằng đường bộ. Biết rằng trong số các tuyến đường khảo sát có tuyến đường thứ là tuyến đường huyết mạch bắt buộc phải sửa chữa.
Dữ liệu vào: File AID.INP gồm
	+ Dòng đầu chứa 3 số trong đó là số lượng điểm dân cư bị cô lập, là số tuyến đường đã khảo sát để sửa chữa và là số thứ tự của tuyến đường huyết mạch bắt buộc phải sửa chữa 
	+ dòng tiếp theo mỗi dòng thứ chứa 3 số trong đó là số thứ tự của điểm đầu và điểm cuối, là thời gian để sửa chữa của tuyến đường thứ 
Dữ liệu ra: File AID.OUT ghi một số nguyên là tổng thời gian sửa chữa ít nhất.
Ví dụ:
AID.INP
AID.OUT
GIẢI THÍCH
5 10 2
5 3 2
4 5 9
4 2 4
4 3 4
2 3 1
1 4 2
1 5 4
1 2 7
2 5 8
1 3 3
14
Các tuyến đường được sửa chữa là 
6. 1 4 2
5. 2 3 1
1. 5 3 2
2. 4 5 9 (Đây là tuyến đường huyết mạch)
Giới hạn test:	80% số test có 
	20% số test có 
------------HẾT------------
Họ và tên thí sinh :........................................................Số báo danh:....................................
Họ và tên, chữ ký:	Giám thị coi thi thứ nhất :.....................................................................
	Giám thị coi thi thứ hai:............................................................................