Problem:


Score : 500 points

Problem Statement

Takahashi has decided to work on K days of his choice from the N days starting with tomorrow.

You are given an integer C and a string S. Takahashi will choose his workdays as follows:

After working for a day, he will refrain from working on the subsequent C days.

If the i-th character of S is x, he will not work on Day i, where Day 1 is tomorrow, Day 2 is the day after tomorrow, and so on.

Find all days on which Takahashi is bound to work.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq N

0 \leq C \leq N

The length of S is N.

Each character of S is o or x.

Takahashi can choose his workdays so that the conditions in Problem Statement are satisfied.

Input

Input is given from Standard Input in the following format:

N K C
S

Output

Print all days on which Takahashi is bound to work in ascending order, one per line.

Sample Input 1

11 3 2
ooxxxoxxxoo

Sample Output 1

6

Takahashi is going to work on 3 days out of the 11 days. After working for a day, he will refrain from working on the subsequent 2 days.

There are four possible choices for his workdays: Day 1,6,10, Day 1,6,11, Day 2,6,10, and Day 2,6,11.

Thus, he is bound to work on Day 6.

Sample Input 2

5 2 3
ooxoo

Sample Output 2

1
5

There is only one possible choice for his workdays: Day 1,5.

Sample Input 3

5 1 0
ooooo

Sample Output 3

There may be no days on which he is bound to work.

Sample Input 4

16 4 3
ooxxoxoxxxoxoxxo

Sample Output 4

11
16



Sample input:
11 3 2
ooxxxoxxxoo


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

n, k, c = map(int, input().split())
s = input()
m = {}
cnt = 0

# days = set(range(1, n))
days = set()

for i in range(n):
    if s[i] == 'o':
        days.add(i+1)

# print(days)

def solve(idx, work_days):
    global cnt

    if len(work_days) > k:
        return

    if idx == n:
        # return work_days
        if len(work_days) == k:
            cnt += 1
            for day in work_days:
                if day in m:
                    m[day] += 1
                else:
                    m[day] = 1
        return

    # Cannot work
    if s[idx] == 'x':
        return solve(idx+1, work_days)

    if len(work_days) > 0:
        prevIdx = work_days[-1] - 1
        # TODO: check prev condition
        if idx - prevIdx <= c:
            # cannot work
            # days.remove(idx+1)
            solve(idx + 1, work_days)
        else:
            # work
            solve(idx + 1, work_days + [idx + 1])

            # not work
            # days.remove(idx+1)
            solve(idx + 1, work_days)
    else:
        # work
        solve(idx+1, work_days + [idx+1])

        # not work
        # days.remove(idx + 1)
        solve(idx + 1, work_days)

solve(0, [])

# print(cnt, m)
# print('days:', days)
ans = []

for key, val in m.items():
    if val == cnt:
        ans.append(key)

for day in ans:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,k,c = map(int,input().split())
s = list(input())
s = [i+1 for i in range(len(s)) if s[i]=="o"]
set_s = set()
flg = 0
for s_list in list(combinations(s,k)):
  d = [1 for i in range(1,k) if s_list[i]-s_list[i-1] < c+1]
  if sum(d) == 0:
    if flg == 0:
      for i in s_list:
        set_s.add(i)
      flg = 1
    else:
      set_s = set_s&set(s_list)
print(*sorted(set_s),sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def is_possible(S, K, C):
    work = 0
    d = 0
    while True:
        if S[d] == "o":
            work += 1
            d += C+1
        else:
            d += 1
        if d>=len(S):
            break
        if work >= K:
            break
    if work >= K:
        return True
    else:
        return False
        

N, K, C = map(int, input().split())
S = input()

for i in range(N):
    if i==0:
        before = ""
    else:
        before = S[:i]
    if i==len(S)-1:
        after = ""
    else:
        after = S[i+1:]
    if S[i] == "o":
        s = before + "x" + after
        if not is_possible(s, K, C):
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
N, K, C = map(int, input().split())
S = input()

dp = [0] * N

dp[N - 1] = 1 if S[N - 1] == "o" else 0
pm = dp[N - 1]
for i in range(N - 2, -1, -1):
    if S[i] == "x" or N - i <= C + 1:
        dp[i] = dp[i + 1]
    else:
        dp[i] = dp[i + C + 1] + 1

# print(dp)
k = K
i = 0
cnt = 0
ans = 0
while i < N:
    if dp[i] < k:
        if cnt == 1:
            print(ans + 1)
        i = ans + C + 1
        cnt = 0
        k -= 1
        if k == 0:
            break
    if S[i] == "o" and dp[i] >= k:
        cnt += 1
        if cnt == 1:
            ans = i
    i += 1

if cnt == 1:
    print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
N, K, C = (int(i) for i in input().split())
#B = [int(x) for x in stdin.readline().rstrip().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
S = input()
#workdays = list(range(1, N+1))
workdays = []
for i in range(len(S)-1):
    #print(i)
    if S[i] == "x":
        continue
    else:
        workdays.append(i+1)

#print(workdays)
combs = list(itertools.combinations(workdays, K))

total = 0
worked = [0]*(N+1)

for i in range(len(combs)):
    for j in range(K-1):
        if combs[i][j+1] -combs[i][j] <= C:
            break
    else:
        total +=1
        for j in range(K):
            worked[combs[i][j]] += 1

for i in range(1, N+1):
    if worked[i] == total:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import copy

N, K, C = map(int, input().split())
S = input()

ans = []
for i in range(N):
	if S[i] == 'x':
		continue
	cpy = list(S)
	cpy[i] = 'x'
	cnt = 0
	for j in range(N):
		if cpy[j] == 'x':
			continue
		for k in range(j, min(j + C + 1, N)):
			cpy[k] = 'x'
		cnt += 1
	if cnt < K:
		ans.append(i + 1)

[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K,C = map(int, input().split())
S = input()
MAX = N+1

dates = [x+1 for x in range(N)]

for i,s in enumerate(S):
	if s == 'x':
		dates.remove(i+1)

ans = list(itertools.combinations(dates, K))
# print(ans)

del_list = list()
for tmp in ans:
	for i in range(K-1):
		if (tmp[i+1]-tmp[i]) <= C:
			del_list.append(tmp)
			break

for tmp in del_list: ans.remove(tmp)
# print(ans)

if len(ans) == 0:
	output = []
else:
	output = list(ans[0])
	for i in range(1, len(ans)):
		for out in output:
			if not out in list(ans[i]):
				output.remove(out)

for o in output: print(o)

Submission status: Time Limit Exceeded

Solution code:
import copy

n, k, c = map(int, input().split())
s = list(input())

tmp = copy.deepcopy(s)
wait = 0
last_day = k
count = []

for num, i in enumerate(tmp):
    if last_day == 0:
        break
    if wait>0:
        wait -= 1
        continue
    if i == 'o':
        s[num] = 'a'
        count.append(num)
        wait = c
        last_day -= 1

# print(count)        
ans = []    
for j in count:
    wait = 0
    tmp = copy.deepcopy(s)
    last_day = k
    tmp[j] = 'x'
    for num, i in enumerate(tmp):
        if last_day == 0:
            break
        if wait>0:
            wait -= 1
            continue
        if i == 'o' or i == 'a':
            wait = c
            last_day -= 1
    if last_day > 0:
        ans.append(j+1)
        
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def is_possible(S, K, C):
    work = 0
    d = 0
    while True:
        if S[d] == "o":
            work += 1
            d += C+1
        else:
            d += 1
        if d>=len(S):
            break
    if work >= K:
        return True
    else:
        return False
        

N, K, C = map(int, input().split())
S = input()

count = 0
for i in range(len(S)):
    if i==0:
        before = ""
    else:
        before = S[:i]
    if i==len(S)-1:
        after = ""
    else:
        after = S[i+1:]
    if S[i] == "o":
        s = before + "x" + after
        if not is_possible(s, K, C):
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n, k, c = map(int, input().split())
s = input()

ans = ""
for i in range(n):
    if s[i] == "x":
        continue

    cur = 0
    count = 0

    while cur < n:
        if s[cur] == "o" and cur != i:
            count += 1
            cur += c

        cur += 1

        if count >= k:
            break

    if count < k:
        ans+=(str(i+1)+"\n")

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# dp[日数] = 残り日数まで働ける最大回数
# dp[N-1] = 1 if "o" else 0
# dp[i] = max(dp[i-C] + 1, max(dp[i+1 ~ N]))

N, K, C = map(int, input().split())
S = input()

dp = [0] * N

dp[N - 1] = 1 if S[N - 1] == "o" else 0
pm = dp[N - 1]
for i in range(N - 2, -1, -1):
    if S[i] == "x" or N - i <= C + 1:
        dp[i] = dp[i + 1]
    else:
        dp[i] = dp[i + C + 1] + 1

k = K
i = 0
cnt = 0
ans = 0
while i < N:
    if dp[i] < k:
        if cnt == 1:
            print(ans + 1)
        cnt = 0
        k -= 1
        i = ans + C + 1
        if k == 0:
            break
    if S[i] == "o" and dp[i] >= k:
        cnt += 1
        if cnt == 1:
            ans = i
    i += 1

if cnt == 1:
    print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
N, K, C = (int(i) for i in input().split())
#B = [int(x) for x in stdin.readline().rstrip().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
S = input()
workdays = list(range(1, N+1))

for i in range(len(S)):
    if S[i] == "x":
        workdays.remove(i+1)

combs = list(itertools.combinations(workdays, K))

total = 0
worked = [0]*(N+1)

for i in range(len(combs)):
    for j in range(K-1):
        if combs[i][j+1] -combs[i][j] <= C:
            break
    else:
        total +=1
        for j in range(K):
            worked[combs[i][j]] += 1

for i in range(1, N+1):
    if worked[i] == total:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import itertools

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, K, C = i_l()
S = i_s()

arr = []

for i in range(len(list(S))):
    if S[i] == 'o':
        arr.append(i+1)

p = itertools.combinations(arr, K)

sets = []
for x in p:
    f = True
    for i in range(len(x)-1):
        if x[i+1] - x[i] <= C:
            f = False
            break
    if f:
        sets.append(set(x))

ans = sets[0]
for s in sets:
    ans &= s

for a in sorted(ans):
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K,C=map(int,input().split())
S=list(input())

#まず一つ答えをつくる これはたぶん貪欲でいける
days=[]
T=S.copy()
for i in range(N):
    if T[i]=='o':
        days.append(i)
        if C!=0:
            for j in range(1,C+1):
                if i+j>=N:
                    break
                T[i+j]='x'
    if len(days)>=K:
        break

def check(plan):
    cnt=0
    qlan=plan.copy()
    for i in range(N):
        if qlan[i]=='o':
            cnt+=1
            if C!=0:
                for j in range(1,C+1):
                    if i+j>=N:
                        break
                    qlan[i+j]='x'
        if cnt>=K:
            return True  #これなしでも成立する
            break
    return False  #これなしでは成立しない

for i in days:
    p=S
    p[i]='x'
    if not check(p):
        print(i+1)
    p[i]='o'

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K, C = map(int, input().split())
    S = list(input())

    work = []
    for i, s in enumerate(S):
        if s == 'o':
            # work.append(i+1)
            work.append(i)
    # print(work)
    import itertools

    cand_list = []
    for v in itertools.combinations(work, K):
        cand = check1(v, C)
        if cand == -1:
            pass
        else:
            cand_list.append(cand)
    # print(cand_list)
    cand = cand_list[0]
    for c in cand:
        check(c, cand_list[1:])


def check(c, cand_list):
    for cand in cand_list:
        if c in cand:
            pass
        else:
            return -1
    print(c+1)


def check1(cand, C):
    num = len(cand)
    for i in range(num-1):
        if cand[i+1] - cand[i] < C+1:
            return -1
    return cand


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k, c = map(int, input().split())
s = input()

ans = []
for i in range(n):
    if s[i] == "x":
        continue
        
    cur = 0
    count = 0

    while cur < n:
        if s[cur] == "o" and cur != i:
            count += 1
            cur += c

        cur += 1

        if count >= k:
            break

    if count < k:
        ans.append(i+1)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K, C, = map(int,input().split())
    S = list(input())
    ans = []

    def solve(index, K):
        i = 0
        cnt = 0
        while i < N:
            if S[i] == 'o' and i != index:
                cnt += 1
                i += C + 1
            else:
                i += 1
        return cnt < K

    if not (solve(-1, K+1)):
        pass
    else:
        index = 0
        while index < N:
            if S[index] == 'x':
                index += 1
            elif solve(index, K):
                ans.append(index + 1)
                index += C + 1
            else:
                index += 1

        for i in ans:
            print(i)
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k,c = map(int,input().split())
s = list(input())

ans = []
cnt = 0
kcn = 0
for i,x in enumerate(s[::-1]):
    i = n - i - 1
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        ans.append(i)
cnt = 0
j = len(ans) - 1
kcn = 0
for i,x in enumerate(s):
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        # while 0<=j and ans[j] <= i:
        #     if ans[j] == i:
        #         print(i+1)
        #     j -= 1
        if i in ans:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
N, K, C, = map(int,input().split())
S = list(input())
ans = []

def solve(index, K):
    i = 0
    cnt = 0
    while i < N:
        if S[i] == 'o' and i != index:
            cnt += 1
            i += C + 1
        else:
            i += 1
    return cnt < K

if not (solve(-1, K+1)):
    pass
else:
    index = 0
    while index < N:
        if S[index] == 'x':
            index += 1
        elif solve(index, K):
            ans.append(index + 1)
            index += C + 1
        else:
            index += 1

    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
n,k,c = map(int,input().split())
s = input()

dp = [[] for _ in range(k)]

days = [i for i in range(n) if s[i] == 'o']
dp[0] = [[day] for day in days]


for day in days:
  for i in range(k-1):
    for j in range(len(dp[i])):
      if dp[i][j][-1] +c < day:
        dp[i+1].append(dp[i][j]+[day])

ans = set(dp[k-1][0])
for lst in dp[k-1]:
  ans = ans.intersection(set(lst))
ans = list(ans)
ans.sort()
for a in ans:
  print(a+1)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, k, c = map(int, input().split())
s = input().rstrip()

ss = [i + 1 for i, ch in enumerate(s) if ch == 'o']

ans = set(ss)
for x in itertools.combinations(ss, k):
    f = True
    for i in range(1, k):
        if x[i] - x[i - 1] < c + 1:
            f = False
            break
    if f:
        ans = ans & set(x)
for a in sorted(ans):
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K,C =map(int,input().rstrip().split(" "))
S = input()
kinmu = 0
niti = 0
for i in range(N):
  if S[i] == "o":
    kinmu = 0
    niti = 0
    while kinmu < K and niti < N:
      if S[niti] == "o" and niti != i:
        kinmu += 1
        niti += C
      niti += 1
    if niti >= N and kinmu < K:
      print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N,K,C = map(int, input().split())
S = input()
s = [i for i in range(N) if S[i]=='o']

def max_work(s,K,C):
  M = len(s)
  if M==0 or C==0:
    return M
  max_work_count = 1
  prev_index = 0
  now_index = 1
  while max_work_count<K and now_index<M: # K日確保できたら終わり
    if s[now_index]-s[prev_index]>C:
      max_work_count += 1
      prev_index = now_index
    now_index += 1
  return max_work_count

for i in range(len(s)):
  if max_work(s[:i]+s[i+1:],K,C)<K:
    print(s[i]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)


def main():
    N, K, C = map(int, input().split())
    S = input()

    end = len(S)
    fullbit = (1 << end) - 1

    ans = [None]

    def search(i, bit, cnt):
        if cnt == 0:
            if ans[0] is None:
                ans[0] = fullbit
            ans[0] &= bit
            return
        if i >= end:
            return
        search(i + 1, bit, cnt)
        if S[i] == 'x':
            return
        search(i + C + 1, bit | (1 << i), cnt - 1)

    search(0, 0, K)
    if ans[0] is not None:
        for i in range(N):
            if (ans[0] & (1 << i)) != 0:
                print(i + 1)


main()

Submission status: Time Limit Exceeded

Solution code:
N, K, C, = map(int,input().split())
S = list(input())
ans = []

def solve(index):
    i = 0
    cnt = 0
    while i < N:
        if S[i] == 'o' and i != index:
            cnt += 1
            i += C + 1
        else:
            i += 1
    return cnt < K

index = 0
while index < N:
    if S[index] == 'x':
        index += 1
    elif solve(index):
        ans.append(index + 1)
        index += C + 1
    else:
        index += 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

N,K,C = [int(i) for i in input().split()]
S = input()

count = [0]*len(S)
total = 0
def work(p, wd):
    global total
    if len(wd) == K:
        for a in wd:
            count[a] += 1
        total += 1
        return

    j = p + C + 1
    # print("\t"*(len(wd)), j, p, wd)
    for a in range(j, len(S)):
        if S[a] == "o":
            work(a, wd + [a])

work(-C-1, [])
# print(count, total)
for i,a in enumerate(count, 1):
    if a == total:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
n, k, c = map(int, input().split())
s = input()

ans = []
for i in range(n):
    cur = 0
    count = 0

    while cur < n:
        if s[cur] == "o" and cur != i:
            count += 1
            cur += c

        cur += 1

    if count < k:
        ans.append(i+1)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N, K, C, = map(int,input().split())
S = list(input())
ans = []

def solve(index):
    i = 0
    cnt = 0
    while i < N:
        if S[i] == 'o' and i != index:
            cnt += 1
            i += C + 1
        else:
            i += 1
    return cnt < K

for index in range(N):
    if S[index] == 'x':
        continue
    elif solve(index):
        ans.append(index + 1)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,k,c = map(int,input().split())
s = input()
idx = []
for i in range(n):
    if s[i]=='o':
        idx.append(i+1)
dic = {}
for i in idx:
    dic[i] = 0
cnt = 0
for l in combinations(idx, k):
    l = list(l)
    flg = True
    for j in range(1, len(l)):
        if l[j]-l[j-1]<=c:
            flg = False
    if flg:
        cnt += 1
        for x in l:
            dic[x] = dic[x] + 1

for k,v in dic.items():
    if v==cnt:
        print(k)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K, C = mapint()
S = list(input())
r_S = S[::-1]

pos = [10**18]*N
neg = [10**18]*N
ok = 0
cnt = 0
for i in range(N):
    if S[i]=='o':
        if ok<=i:
            pos[i] = cnt + 1
            cnt += 1
            ok = i + C + 1

    else:
        pass
ok = 0
cnt = 0
for i in range(N):
    if r_S[i]=='o':
        if ok<=i:
            neg[i] = cnt + 1
            cnt += 1
            ok = i + C + 1

    else:
        pass

ans = []
neg = neg[::-1]

for i in range(N):
    if pos[i]+neg[i]-1==K:
        ans.append(i)
for a in ans:
    print(a+1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K, C = mapint()
S = list(input())
r_S = S[::-1]

pos = [0]*N
neg = [0]*N
ok = 0
cnt = 0
for i in range(N):
    if S[i]=='o':
        if ok<=i:
            pos[i] = cnt + 1
            cnt += 1
            ok = i + C + 1
            if cnt==K:
                break

    else:
        pass
ok = 0
cnt = 0
for i in range(N):
    if r_S[i]=='o':
        if ok<=i:
            neg[i] = cnt + 1
            cnt += 1
            ok = i + C + 1
            if cnt==K:
                break

    else:
        pass

ans = []
neg = neg[::-1]

for i in range(N):
    if pos[i]+neg[i]-1==K:
        ans.append(i)
for a in ans:
    print(a+1)

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

n,k,c=sep()
s=input()
c1=[0]*(n+5)
c2=[0]*(n+5)
for i in range(n):
    if s[i]=="x":
        c1[i]=c1[i-1]
    else:
        c1[i]=max(c1[i-1],c1[i-c-1]+1)
for i in range(n-1,-1,-1):
    if s[i]=="x":
        c2[i]=c2[i+1]
    else:
        c2[i]=max(c2[i+1],c2[(i+c+1)%n]+1)
ans=[]
if c2[1]==k-1 and s[0]=="o":
    ans.append(1)

for i in range(1,n-1):
    if s[i]=="x":
        continue
    if c1[i-1] + c2[i+1]==k-1:
        ans.append(i+1)

if n!=1:
    if c1[n-2]==k-1 and s[0]=="o":
        ans.append(n)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
N日間のうちK日選んで働く
働いたらそれからC日間は働かない
Sにxがついていたら働かない

oの付いてる日のみ働く
全ての通りを求めてみよう

N, K, C = 11, 3, 2
S = ooxxxoxxxoo の時
働けるのは[1, 2, 6, 10, 11]日目
ここから3つ以上間が空く条件で3つ選ぶと条件を満たす
全ての通りでi日目に働く必要がある

A = [1, 2, 5, 7, 11, 13, 16]
M = 4
C = 3

for bit in range(1 << len(A)):
    cnt = []
    for i in range(len(A)):
        if bit & (1 << i):
            cnt.append(A[i])
    if len(cnt) == 4:
        for i in range(1, len(cnt)):
            if cnt[i] - cnt[i - 1] <= C:
                break
        else:
            print(cnt)

# python index.py
[1, 5, 11, 16]
[1, 7, 11, 16]
[2, 7, 11, 16]

A = [1, 2, 5, 10, 24]
M = 3
C = 2
[1, 5, 10]
[2, 5, 10]
[1, 5, 24]
[2, 5, 24]
[1, 10, 24]
[2, 10, 24]
[5, 10, 24]
[1, 5, 10, 24] M + 1回以上ジャンプできる場合には答えが[]になる
A[0]から頑張ってもM回しかジャンプできない

間がC + 1以上離れたM個の集合はどのように求める？
必ず働く日の特性は？
動かすと？
場所は固定？
"""
# N, K, C = getNM()
# S = getN()

N, K, C = getNM()
S = input()

# i回目に選べる要素の上限と下限を比べる
place = []
for i in range(N):
    if S[i] == 'o':
        place.append(i)

# 下限 出来るだけ前の仕事を選べるように
fore = [place[0]]
for i in place[1:]:
    if i - fore[-1] > C:
        fore.append(i)

# 上限 出来るだけ後ろの仕事を選ぶように
back = deque([])
back.append(place[-1])
for i in place[::-1]:
    if back[0] - i > C:
        back.appendleft(i)
back = list(back)

if len(fore) != K:
    print()
    exit()

ans = []
for a, b in zip(fore, back):
    if a == b:
        ans.append(a + 1)

for i in ans:
    print(i)


"""
fore = [0] * N
if S[0] == 'o':
    fore[0] = 1

for i in range(1, N):
    fore[i] = fore[i - 1]
    if S[i] == 'o' and i - C - 1 >= 0:
        fore[i] = max(fore[i], fore[i - C - 1] + 1)

back = [float('inf')] * N
ma = max(fore)
if S[N - 1] == 'o':
    back[N - 1] = ma

for i in range(N - 2, -1, -1):
    back[i] = min(ma, back[i + 1])
    if S[i] == 'o' and i + C + 1 < N:
        back[i] = min(back[i], back[i + C + 1] - 1)
print(back)
"""

Submission status: Accepted

Solution code:
N, K, C = map(int, input().split())
S = input()
length = len(S)

INF = float('inf')
Ls = [-INF]
n = 0
for i, c in enumerate(S):
    if c == 'o' and i - Ls[-1] > C:
        Ls.append(i)
        n += 1
        if n >= K: break

Rs = [INF]
n = 0
for i, c in enumerate(reversed(S)):
    if c == 'o' and Rs[-1] - (length-1-i) > C:
        Rs.append(length-1-i)
        n += 1
        if n >= K: break
Rs.reverse()

for l, r in zip(Ls[1:], Rs[:-1]):
    if l == r:
        print(l+1)

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
s = input()
canwork=[0]*(n+1) #canwork[i]:=i日目までに働くことができる最大日数(1-indexed)
canwork2 = [0]*(c+n+3)
for i in range(n):
    if s[i] == "o":
        canwork[i+1]=max(canwork[i],canwork[i-c]+1)
        
    else:
        canwork[i+1] = canwork[i]
        
for i in range(n)[::-1]:
    if s[i] == "o":
        canwork2[i]=max(canwork2[i+1],canwork2[i+c+1]+1)
    else:
        canwork2[i] = canwork2[i+1]

ans = []
for i in range(n):
    if canwork[i]+canwork2[i+1]==k-1:
        ans.append(i+1)
print(*ans)

Submission status: Accepted

Solution code:
n,k,c = map(int, input().split())
s = input()
sr = s[::-1]
lcnt = [0]*n
rcnt = [0]*n

last_i = -10**8
cnt = 0
for i in range(n):
    if s[i] == 'o' and i - last_i > c:
        cnt += 1
        last_i = i
    lcnt[i] = cnt


last_i = -10**8
cnt = 0
for i in range(n):
    if sr[i] == 'o' and i - last_i > c:
        cnt += 1
        last_i = i
    rcnt[i] = cnt
rcnt = rcnt[::-1]


for i in range(n):
    if s[i] == 'x': continue
    if i > 0: l = lcnt[i-1]
    else: l = 0
    if i < n-1: r = rcnt[i+1]
    else: r = 0
    if l+r < k:
        print(i+1)

Submission status: Accepted

Solution code:
n,k,c = map(int,input().split())
s = input()
l = [0]*k
r = [0]*k

start = 0
count = 0
while count <= k-1 and start <= n-1:
    if s[start] == "o":
        l[count] = start
        count += 1
        start += 1+c
    else:
        start += 1
# print(l)

start = n-1
count = k-1
while count >= 0 and start >= 0:
    if s[start] == "o":
        r[count] = start
        count -= 1
        start -= 1+c
    else:
        start -= 1
# print(r)

for i in range(k):
    if l[i] == r[i]:
        print(l[i] + 1)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k,c=map(int,input().split())
s=input()

l_lst=[0]*k
r_lst=[0]*k

l=-float('inf')
cnt=0
for i in range(n):
    if i-l>c and s[i]!="x":
        l_lst[cnt]=i
        cnt+=1
        l=i
        if cnt==k:
            break
# print(l_lst)
l=float('inf')
cnt=0
for i in range(n)[::-1]:
    if l-i>c and s[i]!="x":
        r_lst[-1-cnt]=i
        cnt+=1
        l=i
        if cnt==k:
            break
# print(r_lst)

for i,j in zip(l_lst,r_lst):
    if i==j:
        print(i+1)

Submission status: Accepted

Solution code:
N,K,C=map(int,input().split())
S=input()

mae=[]
rest=0
work=0
for i in range(len(S)):
    if S[i]=='o' and rest==0:
        mae.append(i)
        rest=C
        work+=1
    else:
        rest=max(rest-1,0)
    if work==K:
        break
        
usiro=[]
rest=0
work=0
S=S[::-1]
for i in range(len(S)):
    if S[i]=='o' and rest==0:
        usiro.append(len(S)-i-1)
        rest=C
        work+=1
    else:
        rest=max(rest-1,0)
    if work==K:
        break

usiro=usiro[::-1]

for i in range(K):
    if mae[i]==usiro[i]:
        print(mae[i]+1)

Submission status: Accepted

Solution code:
#from collection import deque
N, K, C = map(int, input().split())
C += 1
S = input()

DP = [-1 for _ in range(N)] #i日目から初めて、働くことのできる最大の回数

day_prv = [-1] #その日からc日目後に働くことのできた日(day_prv[-c])
for day in range(N-1, -1, -1):
  if S[day] == "x": 
    day_prv.append(day_prv[-1])
  else:
    if day + C >= N or day_prv[-C] == -1:
      DP[day] = 1
    else:
      DP[day] = DP[day_prv[-C]] + 1
    day_prv.append(day) 
  #print(day, day_prv, DP)
  
if DP[0] == K:
  val = DP[0]
  day_start = 0
  ct = 0
  while day_start < N:
    day = day_start
    while day < N and DP[day] != val-1:
      if DP[day] == val:
        ct += 1
      day += 1 
      #print(day, ct)
    if ct == 1:
      print(day_start+1)
    day_start = max(day, day_start + C)
    while day_start < N and DP[day_start] == -1:
      day_start += 1  
    #print(day, ct, val, day_start)
    ct = 0
    val -= 1

Submission status: Accepted

Solution code:
INF=float('inf')
n,k,c=map(int,input().split())
s=input()

L=[-1 for _ in range(n)]
cl=c+1
wl=1
for i in range(n):
  if wl>k:
    continue
  if s[i]=='x':
    cl+=1
  else:
    if cl>c:
      L[i]=wl
      wl+=1
      cl=1
    else:
      cl+=1

R=[-1 for _ in range(n)]
cr=c+1
wr=k
for j in range(n-1,-1,-1):
  if wr<1:
    continue
  if s[j]=='x':
    cr+=1
  else:
    if cr>c:
      R[j]=wr
      wr-=1
      cr=1
    else:
      cr+=1

for i in range(n):
  if L[i]==-1:
    continue
  if R[i]==-1:
    continue
  if L[i]==R[i]:
    print(i+1)

Submission status: Accepted

Solution code:
n, k, c = map(int, input().split())
s = input()
l = [0 for i in range(k)]
r = [0 for i in range(k)]
i, j = 0, 0
while i < n and (not l[-1]):
    if s[i] == "o":
        l[j] = i + 1
        i += c + 1
        j += 1
    else:
        i += 1
i, j = 0, k - 1
while i < n and (not r[0]):
    if s[n - i - 1] == "o":
        r[j] = n - i
        i += c + 1
        j -= 1
    else:
        i += 1
for i in range(k):
    if l[i] == r[i]:
        print(l[i])

Submission status: Accepted

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()[::-1]
  
  R=[0]*K
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R[k]=N-n
      k+=1
      n += C
    n+=1
  R=R[::-1]
  
  S=S[::-1]
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if n+1 == R[k]:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()

  R=[0]*K
  n, k=N-1, 0
  while k < K:
    if S[n]=='o':
      R[k]=n+1
      k+=1
      n -= C
    n-=1
  R=R[::-1]
  
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if n+1 == R[k]:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  

  
if __name__=='__main__':
  main()