Galya is playing one-dimensional Sea Battle on a 1 × n grid. In this game a ships are placed on the grid. Each of the ships consists of b consecutive cells. No cell can be part of two ships, however, the ships can touch each other.
Galya doesn't know the ships location. She can shoot to some cells and after each shot she is told if that cell was a part of some ship (this case is called "hit") or not (this case is called "miss").
Galya has already made k shots, all of them were misses.
Your task is to calculate the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.
It is guaranteed that there is at least one valid ships placement.
The first line contains four positive integers n, a, b, k (1 ≤ n ≤ 2·105, 1 ≤ a, b ≤ n, 0 ≤ k ≤ n - 1) — the length of the grid, the number of ships on the grid, the length of each ship and the number of shots Galya has already made.
The second line contains a string of length n, consisting of zeros and ones. If the i-th character is one, Galya has already made a shot to this cell. Otherwise, she hasn't. It is guaranteed that there are exactly k ones in this string.
In the first line print the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.
In the second line print the cells Galya should shoot at.
Each cell should be printed exactly once. You can print the cells in arbitrary order. The cells are numbered from 1 to n, starting from the left.
If there are multiple answers, you can print any of them.
5 1 2 1
00100
2
4 2
13 3 2 3
1000000010001
2
7 11
There is one ship in the first sample. It can be either to the left or to the right from the shot Galya has already made (the "1" character). So, it is necessary to make two shots: one at the left part, and one at the right part.
题意：
长度为n的字符串，由0和1组成，其中有a个长度为b的船，某人射击了k次全都没有射中船上，射到的点用1表示，问要再射击多少次才能保证至少射中一条船上并输出任意一组射击点。
代码：
1 //很有想法的一道题，挺不好想的虽然用不到什么算法。先找出串中最多有t个长度为b的子串，这t个子串中有a条是船，先除去 2 //a-1条，那么剩下的t-（a-1）个子串中必包含一条船，所以这些子串要全部射击才能保证至少射中一条船。那么这些子串要怎么组合 3 //,要射击那些点呢？haha,前面你找子串的过程中只有正好找到b个0才会记录，所以在你找出的串中只要每b个中选一个当做射击点就行了。 4 #include<bitsstdc++.h> 5 using namespace std; 6 int n,a,b,k; 7 char ch[200005]; 8 int p[200005]; 9 int main() 10 { 11 scanf("%d%d%d%d",&n,&a,&b,&k); 12 scanf("%s",ch); 13 int t=0,tem=0; 14 for(int i=0;i<n;i++) 15 { 16 if(ch[i]=='1') 17 {tem=0;continue;} 18 tem++; 19 if(tem==b) 20 { 21 p[t++]=i; 22 tem=0; 23 } 24 } 25 int ans=t-a+1; 26 printf("%d ",ans); 27 for(int i=0;i<ans;i++) 28 printf("%d ",p[i]+1); 29 printf(" "); 30 return 0; 31 }