Đề thi học sinh giỏi cấp tỉnh môn Tin học Lớp 12 - Năm học 2020-2021 - Sở GD & ĐT Quảng Nam (Có đáp án và thang điểm)

SỞ GIÁO DỤC VÀ ĐÀO TẠO
QUẢNG NAM
ĐỀ CHÍNH THỨC
(Đề thi có 03 trang)
KỲ THI HỌC SINH GIỎI LỚP 12 THPT CẤP TỈNH NĂM HỌC 2020 - 2021
Môn thi : Tin học
Thời gian : 150 phút (không kể thời gian giao đề)
Ngày thi : 12/03/2021
TỔNG QUAN ĐỀ THI TỔNG QUAN ĐỀ BÀI
Bài
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Thời gian
1
Tổng chữ số
SUMN.*
SUMN.INP
SUMN.OUT
1 s
2
Số lượng bội
MULT.*
MULT.INP
MULT.OUT
1 s
3
Tổng bằng 0
ZERO.*
ZERO.INP
ZERO.OUT
1 s
4
Xâu con
SUBSTR.*
SUBSTR.INP
SUBSTR.OUT
1 s
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng 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. Tổng chữ số (5 điểm) 
Cho một số tự nhiên N (N<1064).
Yêu cầu: Hãy viết chương trình tính tổng các chữ số của số tự nhiên đã cho.
Ví dụ: N=1234. Tổng các chữ số của nó là 10.
Dữ liệu vào: Từ tệp văn bản SUMN.INP gồm một số N.
Kết quả: Ghi ra tệp văn bản SUMN.OUT gồm một số duy nhất tìm được.
Ví dụ:
SUMN.INP
SUMN.OUT
1234
10
Ràng buộc:
Có 60% test ứng 60% số điểm của bài với N ≤ 106;
Có 20% test ứng 20% số điểm của bài với N ≤ 1018;
Có 20% test khác ứng với 20% số điểm còn lại của bài với N < 1064.
Bài 2. Số lượng bội (5 điểm)
Cho hai số nguyên dương N và X (N, X ≤ 1018). 
Yêu cầu: Hãy viết chương trình tìm số lượng bội của N sao cho bội của N không vượt quá giá trị của X.
Ví dụ: N=2, X=7. Số lượng bội của N là 3 (vì có 2, 4 và 6 là bội của N).
Dữ liệu vào: Từ tệp văn bản MULT.INP có cấu trúc:
Dòng đầu ghi số nguyên dương K(K ≤ 100) là số lượng bộ dữ liệu;
Tiếp theo là K dòng, mỗi dòng tương ứng với bộ dữ liệu chứa hai số N và X.
Kết quả : Ghi ra tệp văn bản MULT.OUT gồm K dòng, mỗi dòng tương ứng với bộ dữ liệu vào là số lượng bội của N tìm được.
Ví dụ:
MULT.INP
MULT.OUT
1
2 7
3
MULT.INP
MULT.OUT
2
2 7
5 10
3
2
Ràng buộc: 
Có 60% test ứng 60% số điểm của bài với N, X ≤ 105 và K=1;
Có 20% test ứng 20% số điểm của bài với N, X ≤ 105;
Có 20% test khác ứng với 20% số điểm còn lại của bài với N, X ≤ 1018.
Bài 3. Tổng bằng 0 (5 điểm)
Cho dãy số nguyên gồm N phần tử a1, a2, , aN. Gọi Q là số lượng phần tử của dãy con liên tiếp dài nhất có tổng bằng 0.
Yêu cầu: Hãy viết chương trình tìm Q.
Ví dụ: N=5 với dãy: 2, 1, -2, 3, -2 thì dãy con dài nhất có tổng bằng 0 là: 1,-2, 3, -2 và Q=4.
Dữ liệu vào: Từ tệp văn bản ZERO.INP có cấu trúc:
Dòng đầu tiên chứa số tự nhiên N(1 ≤ N ≤ 106);
Dòng tiếp theo chứa dãy số nguyên gồm N phần tử a1, a2, , aN. (|ai| ≤ 109), các số cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản ZERO.OUT gồm một số Q duy nhất.
Ví dụ:
ZERO.INP
ZERO.OUT
5
2 1 -2 3 -2
4
Ràng buộc
Có 80% test ứng 80% số điểm của bài với N ≤ 3*103;
Có 20% khác ứng với 20% số điểm còn lại của bài với N ≤ 106.
Bài 4. Xâu con (5 điểm)	
Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự “0” hoặc “1”. Xâu v gọi là xâu con của w nếu xâu v có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu w. Ví dụ: xâu “010” có các xâu con là “0”, “1”, “0”, “01”, “10”, “010”.
Yêu cầu: Cho trước một giá trị K, hãy đếm xem có bao nhiêu xâu con chứa đúng K ký tự “1”.
Dữ liệu vào: Từ tệp văn bản SUBSTR.INP có cấu trúc:
Dòng 1 chứa một số nguyên K (0 ≤ K ≤ 106);
Dòng 2 chứa một xâu nhị phân có độ dài không quá 106.
Kết quả : Ghi ra tệp văn bản SUBSTR.OUT gồm một số nguyên duy nhất là kết quả tìm được.
Ví dụ:
SUBSTR.INP
SUBSTR.OUT
Giải thích
2
01010
4
Có 4 xâu chứa 2 ký tự “1” là: “101”, “0101”, “1010”, “01010”.
SUBSTR.INP
SUBSTR.OUT
2
1111
3
Ràng buộc: 
Có 60% test ứng 60% số điểm của bài với K ≤ 100 và độ dài của xâu không quá 100;
Có 20% test ứng 20% số điểm của bài với K ≤ 254 và độ dài của xâu không quá 254;
Có 20% test khác ứng với 20% số điểm còn lại của bài với K ≤ 106 và độ dài của xâu không quá 106.
 ---------------Hết---------------
(Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm)
Họ và tên thí sinh: .............................................................. Số báo danh: ...............................
ĐÁP ÁN
SỞ GIÁO DỤC VÀ ĐÀO TẠO
QUẢNG NAM
(ĐA. gồm có 01 trang)
KỲ THI HỌC SINH GIỎI LỚP 12 THPT CẤP TỈNH NĂM HỌC 2020 - 2021
Môn thi : Tin học
ĐÁP ÁN VÀ HƯỚNG DẪN CHẤM
Chấm bài bằng chương trình chấm Themis mới nhất (có kèm theo) cài đặt trên hệ điều hành Windows 10 (64bit) trở lên, các tests đã cài đặt sẵn cấu hình chấm bài.
Bài 1: (5 điểm) Có 20 tests, mỗi TEST đúng được 0.25 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
TEST
SUMN.INP
SUMN.OUT
1
1111
4
...
...
...
20
Bài 2: (5 điểm) Có 25 tests, mỗi TEST đúng được 0.2 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
TEST
MULT.INP
MULT.OUT
1
1
2 7
3
...
...
...
25
Bài 3: (5 điểm) Có 30 tests, 29 TEST đúng được 0.167 điểm và TEST 30 đúng được 0.157. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
TEST
ZERO.INP
ZERO.OUT
1
5
2 1 -2 3 -2
4
...
...
...
30
Bài 4: (5 điểm) Có 25 tests, mỗi TEST đúng được 0.2 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
TEST
SUBSTR.INP
SUBSTR.OUT
1
100
01010
0
...
...
...
25
	------------------------------------HẾT----------------------------------