Xâu con (HSG12'18-19)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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\).

Input

  • Dòng \(1\): chứa một số nguyên \(k (0 \leq k \leq 10^6)\).
  • Dòng \(2\): chứa một xâu nhị phân có độ dài \(\leq 10^6\).

Output

  • Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring

  • \(len(s)\) là độ dài xâu nhị phân.
  • Subtask \(1\) (\(40\%\) số điểm): \(1 \leq k \leq len(s) \leq 500\).
  • Subtask \(2\) (\(30\%\) số điểm): \(1000 \leq k \leq len(s) \leq 10000\).
  • Subtask \(3\) (\(30\%\) số điểm): \(10^5 \leq k \leq len(s) \leq 10^6\).

Example

Test 1

Input 
2
01010
Output 
4
Note
  • có 4 xâu con chứa 2 ký tự 1 là: \(101, 0101, 1010, 01010\).

Bình luận


  • 0
    EAGLE_RULER    10:14 a.m. 26 Tháng 12, 2022

    Mọi người cho e hỏi thuật full bài này làm như nào ạ?


    • 2
      trieunguyen_a1    9:22 p.m. 30 Tháng 7, 2023

      dùng mảng đếm bạn


      • -7
        rip_indra12345    7:04 p.m. 27 Tháng 7, 2023

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

        2 bình luận nữa