CodeForces 165C Another Problem on Strings

Another Problem on Strings

A string is binary, if it consists only of characters "0" and "1".

String v is a substring of string w if it has a non-zero length and can be read starting from some position in string w. For example, string "010" has six substrings: "0", "1", "0", "01", "10", "010". Two substrings are considered different if their positions of occurrence are different. So, if some string occurs multiple times, we should consider it the number of times it occurs.

You are given a binary string s. Your task is to find the number of its substrings, containing exactly k characters "1".

Input

The first line contains the single integer k (0 ≤ k ≤ 106). The second line contains a non-empty binary string s. The length of s does not exceed 106 characters.

Output

Print the single number — the number of substrings of the given string, containing exactly k characters "1".

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Example

Input

1
1010
      

Output

6
      

Input

2
01010
      

Output

4
      

Input

100
01010
      

Output

Note

In the first sample the sought substrings are: "1", "1", "10", "01", "10", "010".

In the second sample the sought substrings are: "101", "0101", "101""01010".

/*
3   00000100101000100    31+1+1 
思路整體明确了嗯就是說 把一之前的0球出來1後面的0也求出來
這樣子一共就有本身沒有前後0+前後有零的個數再加上前後0相乘的個數
累加就行 
其中出現wa的就是當K=0的時候沒有考慮到這邊wa了好幾發
嘻嘻~~~~開心，昨天想說自己應該寫不出來于是嘗試都沒有嘗試~~下次要勇于嘗試 
*/
           

代碼：

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char str[1111111];
int main()
{
	int k;
	scanf("%d %s",&k,str);
	long long sum=0;
	int cnt=0,first=0,last=0,temp,flag=0;
	int len=strlen(str);
	if(k==0)
	{
		for(int i=0;i<len;i++)
		{
			if(str[i]=='0')
			{
				cnt++;
				flag=0;
			}else 
			{
				if(flag)continue;
				sum=sum+cnt*(cnt+1)/2;
				cnt=0;
				flag=1;
			}
		}
		sum+=(str[len-1]-'0'==0)?cnt*(cnt+1)/2:0;
		printf("%lld\n",sum);
		return 0;
	}

	for(int i=0;i<len;i++)
	{
		if(str[i]=='1')cnt++;
		if(cnt==1&&!flag)
		{
			temp=i;
			flag=1;
		}
		if(cnt==k)
		{	
			int j=i;
			i=temp; 
			temp--;
			while(temp>=0&&str[temp]=='0' )
			{
				first++;
				temp--;
			}
			j++;
			while(j<len&&str[j]=='0')
			{
				last++;
				j++;
			}
			sum=sum+1+first+last+first*last;
			cnt=0,first=last=0;
			flag=0; 
		}
	} 	
	printf("%lld\n",sum);
	return 0;
}