English · Original
Chinese · Translation
Formal · Original
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.
## 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.
[samples]
## 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.
Galya 正在玩一个一维的海战游戏，游戏在一个 $1 × n$ 的网格上进行。游戏中，网格上放置了 $a$ 艘船，每艘船由 $b$ 个连续的格子组成。每个格子只能属于一艘船，但船之间可以相互接触。
Galya 不知道船的具体位置。她可以向某些格子射击，每次射击后，她会被告知该格子是否属于某艘船（称为“命中”），或者不属于任何船（称为“未命中”）。
Galya 已经进行了 $k$ 次射击，且所有射击都是未命中。
你的任务是计算最少需要选择多少个格子，使得 Galya 如果对这些格子全部射击，她至少能命中一艘船。
题目保证至少存在一种合法的船放置方案。
第一行包含四个正整数 $n$, $a$, $b$, $k$（$1 ≤ n ≤ 2·10^5$, $1 ≤ a, b ≤ n$, $0 ≤ k ≤ n - 1$）——网格长度、船的数量、每艘船的长度以及 Galya 已经进行的射击次数。
第二行是一个长度为 $n$ 的由 0 和 1 组成的字符串。如果第 $i$ 个字符是 1，则 Galya 已经向该格子射击过；否则，她尚未射击。保证该字符串中恰好有 $k$ 个 1。
第一行输出一个最小的格子数量，使得 Galya 如果对这些格子全部射击，她至少能命中一艘船。
第二行输出 Galya 应当射击的格子编号。
每个格子只能输出一次，顺序可以任意。格子编号从 1 到 $n$，从左到右排列。
如果存在多个答案，输出任意一个即可。
在第一个样例中，有一艘船。它可能位于 Galya 已经射击过的格子（即 "_1_"）的左侧或右侧。因此，必须进行两次射击：一次在左侧部分，一次在右侧部分。
## Input
第一行包含四个正整数 $n$, $a$, $b$, $k$（$1 ≤ n ≤ 2·10^5$, $1 ≤ a, b ≤ n$, $0 ≤ k ≤ n - 1$）——网格长度、船的数量、每艘船的长度以及 Galya 已经进行的射击次数。第二行是一个长度为 $n$ 的由 0 和 1 组成的字符串。如果第 $i$ 个字符是 1，则 Galya 已经向该格子射击过；否则，她尚未射击。保证该字符串中恰好有 $k$ 个 1。
## Output
第一行输出一个最小的格子数量，使得 Galya 如果对这些格子全部射击，她至少能命中一艘船。第二行输出 Galya 应当射击的格子编号。每个格子只能输出一次，顺序可以任意。格子编号从 1 到 $n$，从左到右排列。如果存在多个答案，输出任意一个即可。
[samples]
## Note
在第一个样例中，有一艘船。它可能位于 Galya 已经射击过的格子（即 "_1_"）的左侧或右侧。因此，必须进行两次射击：一次在左侧部分，一次在右侧部分。
**Definitions**
Let $ n, a, b, k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 2 \cdot 10^5 $, $ 1 \leq a, b \leq n $, $ 0 \leq k \leq n - 1 $.
Let $ S \subseteq \{1, 2, \dots, n\} $ be the set of cells already shot (misses), with $ |S| = k $.
Let $ \mathcal{P} $ be the set of all valid placements of $ a $ ships, each of length $ b $, on the $ 1 \times n $ grid such that:
- Ships are disjoint (no overlapping cells),
- Ships may touch,
- No ship overlaps with any cell in $ S $.
**Constraints**
1. $ |S| = k $, and $ S $ is given as a binary string of length $ n $ with exactly $ k $ ones.
2. $ \mathcal{P} \neq \emptyset $ (at least one valid placement exists).
**Objective**
Find the minimum number of cells $ T \subseteq \{1, 2, \dots, n\} \setminus S $ such that:
$$
\forall P \in \mathcal{P},\quad T \cap P \neq \emptyset
$$
That is, $ T $ intersects every possible ship placement $ P \in \mathcal{P} $.
Output $ |T| $ and any such minimal $ T $.
API Response (JSON)
{
"problem": {
"name": "D. Sea Battle",
"description": {
"content": "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, how",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF729D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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, how...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Galya 正在玩一个一维的海战游戏，游戏在一个 $1 × n$ 的网格上进行。游戏中，网格上放置了 $a$ 艘船，每艘船由 $b$ 个连续的格子组成。每个格子只能属于一艘船，但船之间可以相互接触。\n\nGalya 不知道船的具体位置。她可以向某些格子射击，每次射击后，她会被告知该格子是否属于某艘船（称为“命中”），或者不属于任何船（称为“未命中”）。\n\nGalya 已经进行了 $k$ 次射击，且所...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, a, b, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 2 \\cdot 10^5 $, $ 1 \\leq a, b \\leq n $, $ 0 \\leq k \\leq n - 1 $. \nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the set of cells...",
"is_translate": false,
"language": "Formal"
}
]
}