Codeforces 729 D Sea Battle(思考問題、良い問題)
3495 ワード
D. Sea Battle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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
output
input
output
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.
标题:n個の格子があり、ここにはa個の船が含まれており、各船はb個の格子を占めているが、船の位置は分からない.Gはこれまでこれらの位置をk回撃ったことがあり、格子を1つ撃つたびに、k回も船に当たらなかった.nの長さの文字列を与え,0は未知の位置を表し,1はGによって射撃された船のない格子を表す.Gが少なくとも1隻の船を射撃することを保証するには、少なくとも何回か射撃し、これらの位置番号を出力する必要があります.この問題は純粋な思考問題で、試合中に久しぶりに思いつかなかった...問題解:まず船が存在する可能性のある位置量numを算出し、各船の最後の位置番号を記録する.そして私たちはこれらの船を射撃して、存在船の位置をa-1にすればいいです.(1隻の船に射撃できることを保証)位置出力前num+1-a個でいいです.
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
标题:n個の格子があり、ここにはa個の船が含まれており、各船はb個の格子を占めているが、船の位置は分からない.Gはこれまでこれらの位置をk回撃ったことがあり、格子を1つ撃つたびに、k回も船に当たらなかった.nの長さの文字列を与え,0は未知の位置を表し,1はGによって射撃された船のない格子を表す.Gが少なくとも1隻の船を射撃することを保証するには、少なくとも何回か射撃し、これらの位置番号を出力する必要があります.この問題は純粋な思考問題で、試合中に久しぶりに思いつかなかった...問題解:まず船が存在する可能性のある位置量numを算出し、各船の最後の位置番号を記録する.そして私たちはこれらの船を射撃して、存在船の位置をa-1にすればいいです.(1隻の船に射撃できることを保証)位置出力前num+1-a個でいいです.
#include
#include
#include
#include
#include
using namespace std;
#define rep(i,a,n) for (int i=a;i=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector VI;
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
const int MAXN=2E5+100;
VI ans;
char s[MAXN];
int main()
{
int n,a,b,k;
ans.clear();
scanf("%d%d%d%d",&n,&a,&b,&k);
scanf("%s",s+1);
int num=0;
rep(i,1,n+1)
{
int v=s[i]-'0';
if(!v)
{
num++;
if(num>=b) ans.pb(i),num-=b;
}
else num=0;
}
printf("%d
",ans.size()-a+1);
rep(i,0,ans.size()-a+1)
printf("%d ",ans[i]);
return 0;
}