Đề thi chọn học sinh giỏi lớp 12 cấp tỉnh môn Tin học - Năm học 2019-2020 - 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 LỚP 12 CẤP TỈNH NĂM HỌC 2019 – 2020
MÔN: TIN HỌC
Ngày thi: 06/12/2019
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 04 câu, trong 03 trang
Họ và tên thí sinh :........................................................Số báo danh:................................
Họ và tên, chữ ký:	Giám thị số 1:...................................................................................
	Giám thị số 2:.......................................................................................
Tổng quan đề thi
Bài
Tên bài
File
chương trình
File
dữ liệu vào
File kết quả
Thời gian/ Bộ nhớ
1
Học nhóm
NUMBER.*
NUMBER.INP
NUMBER.OUT
1 giây/ test, 1024Mb
2
Mật khẩu
PASSWORD.*
PASSWORD.INP
PASSWORD.OUT
1 giây/ test, 1024Mb
3
May mắn
LUCKY.*
LUCKY.INP
LUCKY.OUT
1 giây/ test, 1024Mb
4
Lễ hội
FESTIVAL.*
FESTIVAL.INP
FESTIVAL.OUT
1 giây/ test, 1024Mb
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++
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.
	Ninh và Bình là hai học sinh thuộc Đội tuyển Học sinh giỏi môn Tin học của trường THPT A. Mỗi bạn có một sở thích và khả năng khác nhau. Ninh thích các bài toán về số đảo ngược còn Bình lại thích các bài toán về số nguyên tố. Thầy giáo phụ trách đội tuyển muốn tăng khả năng tự học và giúp đỡ nhau trong học tập giữa các học sinh. Thầy giáo giao cho các bạn làm một bài tập có liên quan đến số đảo ngược và số nguyên tố với nội dung như sau:
	Cho hai số nguyên dương P và Q (1 ≤ P ≤ Q ≤ 104). Đếm xem có tất cả bao nhiêu số nguyên dương X (P ≤ X ≤ Q) đồng thời thỏa mãn X và số đảo ngược của số X là số nguyên tố.
	Biết số đảo ngược của số X được tạo ra bằng cách viết các chữ số của số X theo thứ tự ngược lại. Ví dụ số 9631 có số đảo ngược là 1369.
Yêu cầu: Đọc vào 2 số P, Q và in ra số lượng các số X thỏa mãn.
Dữ liệu vào: File NUMBER.INP gồm 1 dòng ghi 2 số nguyên dương P, Q được ghi cách nhau bởi một dấu cách.
Dữ liệu ra: File NUMBER.OUT chỉ 1 dòng ghi số lượng số X thỏa mãn yêu cầu.
Ví dụ:
NUMBER.INP
NUMBER.OUT
GIẢI THÍCH
10 19
3
Trong đoạn [10,19] có 3 số 11, 13, 17 là các số nguyên tố và các số đảo ngược lần lượt là 11, 31, 71 cũng là số nguyên tố.
Bài 2 (6,0 điểm): Mật khẩu.
Hiện nay, có rất nhiều cuộc tấn công vào các máy tính cá nhân với mục đích lấy trộm các file dữ liệu thông qua mạng Internet. Trung tâm bảo mật BKAV khuyến cáo mọi người nên đặt mật khẩu an toàn cho các file dữ liệu của mình. Mật khẩu được coi là an toàn phải có từ 6 kí tự trở lên và có đủ 3 loại: Chữ cái Latinh in hoa [‘A’.. ‘Z’], chữ cái Latinh in thường [‘a’.. ‘z’] và chữ số [‘0’.. ‘9’]. Ví dụ: Xâu ‘Tinhoc2019’ được coi là mật khẩu an toàn, còn xâu ‘hsgtin2019’ không phải là mật khẩu an toàn. 
Yêu cầu: Cho một xâu S chỉ gồm các kí tự là chữ cái và chữ số. Đếm xem có bao nhiêu xâu con gồm các kí tự liên tiếp trong xâu S để xâu con đó là một mật khẩu an toàn. Biết rằng các xâu con giống nhau hoàn toàn được coi là 1 cách.
Dữ liệu vào: File PASSWORD.INP 
Gồm một dòng chứa xâu S có độ dài n kí tự (6 ≤ n ≤ 255).
Dữ liệu ra: File PASSWORD.OUT ghi một số là số lượng mật khẩu an toàn tìm được. 
Ví dụ:
PASSWORD.INP
PASSWORD.OUT
GIẢI THÍCH
Tinhoc2019
4
Có 4 xâu con ‘Tinhoc2’, ‘Tinhoc20’, ‘Tinhoc201’ và ‘Tinhoc2019’ thỏa mãn yêu cầu là mật khẩu an toàn.
Ti1Ti1Ti1
9
Có 10 xâu con thỏa mãn là mật khẩu an toàn: ‘Ti1Ti1’, ‘Ti1Ti1T’, ‘Ti1Ti1Ti’, ‘Ti1Ti1Ti1’, ‘i1Ti1T’, ‘i1Ti1Ti’, ‘i1Ti1Ti1’, ‘1Ti1Ti’, ‘1Ti1Ti1’, ‘Ti1Ti1’.
Có 2 xâu con trùng nhau là ‘Ti1Ti1’ nên số lượng chính xác là 9.
Bài 3 (4,0 điểm): May mắn.
Sau Kì thi chọn Học sinh giỏi cấp tỉnh, trường của Minh tổ chức cho các bạn trong đội tuyển học sinh giỏi đi thăm quan vịnh Hạ Long. Tại đây đang có chương trình bốc thăm trúng thưởng. Rất may mắn Minh nhận được giải đặc biệt. Cách thức nhận quà như sau: Có n phần quà, được đánh số từ 1 đến n, gói quà thứ i (1 ≤ i ≤ n) có trọng lượng là Wi (Wi ≤ 100) và giá trị là Vi (Vi ≤ 100). Các gói quà được đặt trên một chiếc thuyền Rồng neo đậu xa bờ. Muốn lấy được quà Minh cần phải dùng thuyền nhỏ để chèo ra lấy. Có thể lấy bao nhiêu gói quà tùy ý trong n gói quà trên, nhưng để đảm bảo an toàn Minh chỉ có thể lấy các phần quà có tổng trọng lượng nhỏ hơn hoặc bằng m cho trước. Gọi T là tổng giá trị của các gói quà mang về.
Yêu cầu: Giúp bạn Minh tìm T lớn nhất.
Dữ liệu vào: File LUCKY.INP gồm 3 dòng. 
+ Dòng đầu ghi hai số tự nhiên n và m (1 ≤ m, n ≤ 100). 
+ Dòng thứ 2 là trọng lượng của n gói hàng.
+ Dòng thứ 3 là giá trị của n gói hàng.
(Trong đó: Số có thứ tự thứ i trong hàng là trọng lượng và giá trị của gói quà thứ i. Mỗi số trong các hàng cách nhau một dấu cách).
Dữ liệu ra: File LUCKY.OUT ghi một số là số T tìm được.
Ví dụ: 
LUCKY.INP
LUCKY.OUT
GIẢI THÍCH
5 15
2 3 5 7 8
12 2 5 6 7
24
Có thể chọn các gói thứ 1, 3, 5 có tổng trọng lượng 2+5+8=15 và có tổng giá trị T = 12+5+7= 24 là T lớn nhất có thể mang về.
Bài 4 (4,0 điểm): Lễ hội.
Tại Festival Huế có tổ chức biểu diễn áo dài trên sông Hương. Sân khấu trên sông được thiết kế đặc biệt bằng cách dùng các sợi dây thừng kết nối n chiếc phà với nhau. Các phà được đánh số hiệu từ 1 đến n, trong đó phà trung tâm có số hiệu là 1. Mỗi sợi dây chỉ kết nối được 2 phà bất kì. Mục đích để tạo ra một sân khấu lớn sao cho từ phà trung tâm có thể đi đến tất cả các phà còn lại. Sau khi kết nối xong, một sự cố đã xảy ra khiến cho một số dây thừng nối giữa các phà bị đứt làm cho một số phà bị tách ra khỏi khối kết nối với phà trung tâm. Để tổ chức được buổi biểu diễn thì số lượng phà còn đang nằm trong khối kết nối với phà trung tâm phải lớn hơn hoặc bằng số k. Nếu không đủ thì Ban tổ chức muốn tính xem cần ít nhất bao nhiêu sợi dây thừng để nối tất cả các phà còn lại với khối có phà trung tâm.
Yêu cầu: Giúp Ban tổ chức đếm số phà trong khối có phà trung tâm là bao nhiêu và số sợi dây thừng cần thêm.
Dữ liệu vào: File FESTIVAL.INP	
 + Dòng đầu là 3 số n, m, k trong đó n là số lượng phà ban đầu, m là số lượng kết nối còn lại giữa các phà và k là số phà tối thiểu (không tính phà trung tâm) để tổ chức được cuộc biểu diễn (1 ≤ k ≤ n - 1 ≤ 103, 1 ≤ m ≤ n2).
 + m dòng tiếp theo mỗi dòng ghi 2 số là số hiệu của 2 phà còn được kết nối với nhau (các số cách nhau bởi 1 dấu cách).
Dữ liệu ra: File FESTIVAL.OUT gồm 2 dòng: 
 + Dòng 1: Ghi số lượng phà còn nằm trong khối kết nối với phà trung tâm (không tính phà trung tâm).
+ Dòng 2: Ghi số 0 nếu số phà trong khối có phà trung tâm đủ để tổ chức buổi biểu diễn. Trong trường hợp không đủ thì ghi số lượng dây thừng ít nhất để kết nối tất cả các phà thành 1 khối.
Ví dụ :
2
4
6
1
7
8
3
5
FESTIVAL.INP
FESTIVAL.OUT
GIẢI THÍCH
8 7 7
1 2
1 3
2 3
2 4
3 5
4 6
7 8
5
1
Hiện tại có 5 phà đang trong khối kết nối với phà trung tâm (chưa đủ 7 phà) nên cần thêm 1 đoạn dây thừng để nối với phà 7 hoặc 8 để tất cả thành một khối.
8 7 4
1 2
1 3
2 3
2 4
3 5
4 6
7 8
5
0
Vì số phà kết nối với phà trung tâm là 5 mà số phà cần để biểu diễn là 4 nên không cần thêm dây thừng để nối nữa.
-----Hết-----