Đề thi chọn học sinh giỏi thành phố - Môn: Tin học lập trình - Bảng A

SỞ GIÁO DỤC & ĐÀO TẠO
 ..
ĐỀ CHÍNH THỨC
(Đề thi gồm 02 trang)
KỲ THI CHỌN HỌC SINH GIỎI THÀNH PHỐ
 CẤP THPT NĂM HỌC 2019 - 2020
ĐỀ THI MÔN: TIN HỌC LẬP TRÌNH- BẢNG A
Thời gian: 180 phút (không kể thời gian giao đề)
TỔNG QUAN VỀ ĐỀ THI
File nguồn nộp
File dữ liệu
File kết quả
Thời gian mỗi test
Biểu điểm
Bài 1
BAI1.PAS
BAI1.INP
BAI1.OUT
1 giây
3 điểm
Bài 2
BAI2.PAS
BAI2.INP
BAI2.OUT
1 giây
3.5 điểm
Bài 3
BAI3.PAS
BAI3.INP
BAI3.OUT
2 giây
3.5 điểm
Chú ý:
- Bài thi được làm trên máy vi tính.
- Học sinh đặt tên file chương trình theo đúng quy định của từng bài, không ghi bất kỳ thông tin cá nhân nào vào file bài làm (họ tên, số báo danh, ngày sinh, trường, các ký hiệu khác thường, )
- File input và output ở trong thư mục hiện hành, thí sinh không phải khai báo đường dẫn đến file input và output.
Bài 1: Xâu con
Cho 2 xâu kí tự S1 và S2 gồm các chữ cái tiếng Anh in thường (số lượng ký tự S1<S2<255). Viết chương trình tính số lần xuất hiện của xâu S1 trong xâu S2.
Dữ liệu: Vào từ file văn bản BAI1.INP gồm:
Dòng đầu tiên chứa xâu S1.
Dòng thứ hai chứa xâu S2.
Kết quả: Ghi ra tệp văn bản BAI1.OUT:
Ghi một số nguyên dương duy nhất là số lần xuất hiện của xâu S1 trong xâu S2.
Ví dụ:
BAI1.INP
BAI1.OUT
aba
bababababa
4
Bài 2: Bình chọn qua điện thoại
Trong vòng chung kết cuộc thi Tiếng hát truyền hình, các thí sinh được đánh số báo danh là một số nguyên dương có giá trị không vượt quá 100.000. Khán giả có thể bình chọn cho thí sinh mình yêu thích bằng cách nhắn tin qua điện thoại di động.
Ban tổ chức nhận được tin nhắn hợp lệ của N khán giả (các khán giả được đánh số từ 1 đến N), khán giả thứ i bình chọn cho một thí sinh duy nhất mang số báo danh ai.
Yêu cầu: Bạn hãy liệt kê những thí sinh được khán giả bình chọn nhiều nhất theo thứ tự tăng dần của số báo danh.
Dữ liệu: Vào từ file văn bản BAI2.INP
Dòng đầu tiên chứa số nguyên dương N là số lượng khán giả có tin nhắn bình chọn hợp lệ (1≤N≤106)
N dòng tiếp theo, dòng thứ i chứa một số nguyên dương ai là số báo danh của thí sinh mà khán giả thứ i bình chọn. (1≤ai≤100.000)
Kết quả: Ghi ra file văn bản BAI2.OUT
Danh sách các thí sinh được khán giả bình chọn nhiều nhất theo thứ tự số báo danh tăng dần
Ví dụ:
BAI2.INP
BAI2.OUT
Giải thích
5
3
1
3
2
2
2
3
Thí sinh số báo danh 1 có 1 khán giả bình chọn
Thí sinh số báo danh 2 có 2 khán giả bình chọn
Thí sinh số báo danh 3 có 2 khán giả bình chọn
Chú ý:
60% số test tương ứng với 60% số điểm có N≤1.000.
Bài 3: Đoạn con liên tiếp
Cho một dãy N số nguyên dương a1,a2, ,an.
Yêu cầu: Đếm số đoạn con gồm các phần tử liên tiếp (số phần tử ≥2) có tổng là số chính phương ∈[1;k] (số chính phương là bình phương của một số nguyên dương).
Dữ liệu: Vào từ file văn bản BAI3.INP.
Dòng đầu chứa hai số nguyên dương N,k
Dòng tiếp theo chứa N số nguyên dương a1,a2, ,an. 
Kết quả: Ghi ra file văn bản BAI3.OUT: 
Ghi một số nguyên duy nhất là số lượng đoạn con liên tiếp có tổng là số chính phương.
Ví dụ:
BAI3.INP
BAI3.OUT
Giải thích
4 15
2 2 5 9
2
Có 2 đoạn con có tổng là số chính phương: 2,2;2,2,5 thỏa mãn điệu kiện đề bài.
Đoạn (2,5,9) có tổng bằng 16>k không thỏa mãn điều kiện đề bài.
Chú ý: 
70% số test tương ứng với 70% số điểm có n≤100;1≤ai≤10.000;k≤100.000
20% số test tương ứng với 20% số điểm có n≤10.000;1≤ai≤1.000;k≤10.000
10% số test tương ứng với 10% số điểm có n≤100.000;1≤ai≤100;k≤100
---Hết---
(Cán bộ coi thi không giải thích gì thêm)
Họ và tên thí sinh:	Số báo danh:	
Giám thị 1:	Giám thị 2: