AT_abc161_e [ABC161E] Yutori

题目描述

高桥君决定在接下来的 $N$ 天中选择 $K$ 天去工作。

给定整数 $C$ 和字符串 $S$，他需要选择工作日，使得满足以下两个条件：

• 如果某一天工作了，那么接下来的 $C$ 天都不能工作。
• 当 $S$ 的第 $i$ 个字符为 x 时，从今天起第 $i$ 天不能工作。

请你求出所有高桥君必定要去工作的日期。

输入格式

输入从标准输入按以下格式给出。

$N$ $K$ $C$ $S$

输出格式

请按升序输出所有高桥君必定要去工作的日期，每行一个。

输入输出样例 #1

输入 #1

11 3 2
ooxxxoxxxoo

输出 #1

6

输入输出样例 #2

输入 #2

5 2 3
ooxoo

输出 #2

1
5

输入输出样例 #3

输入 #3

5 1 0
ooooo

输出 #3

输入输出样例 #4

输入 #4

16 4 3
ooxxoxoxxxoxoxxo

输出 #4

11
16

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq N$
• $0 \leq C \leq N$
• $S$ 的长度为 $N$
• $S$ 的每个字符都是 o 或 x
• 一定存在满足题目条件的工作日选择方案

样例解释 1

高桥君打算在 $11$ 天中选择 $3$ 天去工作。如果某一天工作了，之后的 $2$ 天都不能工作。作为工作日的可能组合有“第 $1,6,10$ 天”，“第 $1,6,11$ 天”，“第 $2,6,10$ 天”，“第 $2,6,11$ 天”共 $4$ 种。因此，第 $6$ 天一定要去工作。

样例解释 2

作为工作日的可能组合只有“第 $1,5$ 天”。

样例解释 3

也有可能不存在必定要去工作的日子。

由 ChatGPT 4.1 翻译