Đề thi HSG môn Tin học 12 năm học 2021 - Sở GD&ĐT Quảng Nam (có đáp án)

ZixDoc gửi tặng quý thầy cô và các em học sinh Đề thi HSG môn Tin học 12 năm học 2021 - Sở GD&ĐT Quảng Nam kèm hướng dẫn giải chi tiết dưới định dạng word hoàn toàn miễn phí. Tài liệu có 5 trang, bao gồm 4 câu tự luận. Thời gian làm bài: 150 phút (không kể thời gian giao đề).

Trích dẫn Đề thi HSG môn Tin học 12 năm học 2021 - Sở GD&ĐT Quảng Nam (có đáp án):
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ụ:
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.

Tải về để xem bản đầy đủ và chính xác nhất!