首页 > > 程序设计 > C/C++ >

Codeforces #380 div2 D(729D) Sea Battle

2018-06-17 23:35:16来源：未知阅读 ()

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 bconsecutive 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.

Input

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.

Output

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.

Examples

input

5 1 2 1
00100

output

2
4 2

input

13 3 2 3
1000000010001

output

2
7 11

Note

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.

题目大意：有a个长为b的船，藏在连续的0里，求至少在0里射击枪，一定能击中至少一艘船，并输出射击的位置

思路：一开始把题想复杂了，以为要对b=1的情况进行特判，其实用一种就行。

　　建立结构体z，表示每一段连续的0的左端点l，右端点r，其中0的个数len，以及能放的船数num=len/b，将所有的num+起来为sum，与a比较，由于只要确保能击中就行，因此只需要攻击sum-a+1次，就一定能攻击到；对每一个z，从他的l+b-1处开始攻击（这个位置的前面不能藏一艘船），每次+b攻击，直到攻击够sum-a+1次为止。

代码：

  1 #include <cstdio>
  2 #include <ctime>
  3 #include <cstdlib>
  4 #include <iostream>
  5 #include <cstring>
  6 #include <cmath>
  7 #include <queue>
  8 #include <algorithm>
  9 #define N 200005
 10 #define inf 1e18+5
 11 typedef long long ll;
 12 #define rep(i,n) for(i=0;i<n;i++)
 13 using namespace std;
 14 int i,j,k,m,n,t,cc,a,b,ans;
 15 int s[N],h[N];
 16 struct z{
 17     int l;
 18     int r;
 19     int len;
 20     int num;
 21 }z[N];
 22 int  main()
 23 {
 24     while(scanf("%d%d%d%d",&n,&a,&b,&k)!=EOF){
 25         ans=0;
 26         k=n-k;
 27         j=0;
 28         m=0;
 29         cc=0;
 30         s[0]=-1;
 31         getchar();
 32         for(i=1;i<=n;i++){
 33             scanf("%c",&s[i]);
 34             if(s[i]=='0'&&s[i-1]!='0'){
 35                 z[j].l=i;
 36             }
 37             if(s[i]=='1'&&s[i-1]=='0'){
 38                 z[j].r=i-1;
 39                 z[j].len=z[j].r-z[j].l+1;
 40                 z[j].num=z[j].len/b;
 41                 cc+=z[j].len/b;
 42                 j++;
 43             }
 44             if(i==n&&s[i]=='0'){
 45                 z[j].r=i;
 46                 z[j].len=z[j].r-z[j].l+1;
 47                 z[j].num=z[j].len/b;
 48                 cc+=z[j].len/b;
 49                 j++;
 50             }
 51         }
 52     /*    if(b==1){
 53             if(k==cc){
 54                 for(i=0;i<j;i++){
 55                     for(int i1=z[i].l;i1<=z[i].r;i1++){
 56                         h[m]=i1;
 57                         m++;
 58                     }
 59                 }
 60                 ans=m;
 61             }
 62             else{
 63                 ans=k-a+1;
 64                 for(i=0;i<j;i++){
 65                     for(int i1=z[i].l;i1<=z[i].r;i1++){
 66                         h[m]=i1;
 67                         m++;
 68                         if(m==ans) break;
 69                     }
 70                     if(m==ans) break;
 71                 }
 72             }
 73         }
 74         else */ {
 75             /*if(a==cc){
 76                 for(i=0;i<j;i++){
 77                     if(z[i].num){
 78                         for(int i1=z[i].l+b-1;i1<=z[i].r+b-1;i1+=b){
 79                             h[m]=i1;
 80                             m++;            
 81                         }    
 82                     }
 83                 }
 84                 ans=m;
 85             }
 86             else */{
 87                 ans=cc-a+1;
 88                 for(i=0;i<j;i++){
 89                     if(z[i].num){
 90                         for(int i1=z[i].l+b-1;i1<=z[i].r;i1+=b){
 91                             h[m]=i1;
 92                             m++;    
 93                             if(m==ans) break;        
 94                         }    
 95                     }
 96                     if(m==ans) break;    
 97                 }
 98             }
 99         }
100     //    for(i=0;i<j;i++) printf("%d %d \n",z[i].l,z[i].r);
101         
102         printf("%d\n",ans);
103         for(i=0;i<m;i++){
104             if(i!=m-1) printf("%d ",h[i]);
105             else printf("%d\n",h[i]);
106         }
107     }
108     
109  
110     return 0;
111 }