Xâu con
Thời gian
1s
Bộ nhớ
1GB
Đọc vào (Input)
XAUCON.INP
Ghi ra (Output)
XAUCON.OUT
Đề bài
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'.
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
Đọc từ tệp văn bản XAUCON.INP gồm:
- Dòng đầu tiên chứa một số nguyên k.
- Dòng thứ hai chứa một xâu nhị phân.
Dữ liệu ra
Ghi ra tệp văn bản XAUCON.OUT gồm:
- Một số nguyên duy nhất là số lượng xâu con chứa đúng k ký tự '1'.
Ví dụ
Input 1
2 01010
Output 1
4
Ràng buộc & Tóm tắt
Giải thích
Có 4 xâu chứa đúng 2 ký tự '1' là: '101', '0101', '1010', '01010'.
Ràng buộc
- 0 ≤ k ≤ độ dài xâu nhị phân.
- Subtask 1 (20% số điểm): 1 ≤ độ dài xâu nhị phân ≤ 10.
- Subtask 2 (50% số điểm): 1 ≤ độ dài xâu nhị phân ≤ 5 × 102.
- Subtask 3 (30% số điểm): 5 × 102 ≤ độ dài xâu nhị phân ≤ 105.
Thông tin bài tập
Mã bài:
XAUCON
Mức độ:
Bình thường
Điểm số:
40 đ
