{"code":"1819substr","name":"Xâu con (HSG12'18-19)","description":"Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự $0$ hoặc $1$.\r\n\r\nXâ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$. \r\n\r\n**Ví dụ**: xâu $010$ có các xâu con là: $0, 1, 0, 01, 10, 010$.\r\n\r\n**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$.\r\n\r\n#### Input\r\n- Dòng $1$: chứa một số nguyên $k (0 \\leq k \\leq 10^6)$.\r\n- Dòng $2$: chứa một xâu nhị phân có độ dài $\\leq 10^6$.\r\n\r\n#### Output\r\n\r\n- Ghi ra một số nguyên duy nhất là kết quả tìm được.\r\n\r\n#### Scoring\r\n- $len(s)$ là độ dài xâu nhị phân.\r\n- Subtask $1$ ($40\\%$ số điểm): $1 \\leq k \\leq len(s) \\leq 500$.\r\n- Subtask $2$ ($30\\%$ số điểm): $1000 \\leq k \\leq len(s) \\leq 10000$.\r\n- Subtask $3$ ($30\\%$ số điểm): $10^5 \\leq k \\leq len(s) \\leq 10^6$.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2\r\n        01010 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        ```\r\n    ??? warning \"Note\"\r\n        - có 4 xâu con chứa 2 ký tự 1 là: $101, 0101, 1010, 01010$.","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}