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:
N, K, C = map(int, input().split())
s=input()
l=[]
for i in range(N):
    if s[i]=="o":
        l.append(i)
l2=sorted(l,reverse=True)

s1=set()
s2=set()
j=1
while j==1:
    s1.add(l[0]+1)
    l=[i for i in l if i>l[0]+C]
    if len(s1)==K or l==[]:
        break
while j==1:
    s2.add(l2[0]+1)
    l2=[i for i in l2 if i<l2[0]-C]
    if len(s2)==K or l2==[]:
        break

aa=list(s1&s2)
aa.sort()
for i in range(len(aa)):
  print(aa[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def abc161e(n, k, c, s):
    num_cluster_f = 0
    start = []
    cursor = 0
    while cursor < n:
        if s[cursor] == "x":
            cursor += 1
            continue
        else:
            num_cluster_f += 1
            start.append(cursor)
            cursor += c+1

    if k < num_cluster_f:
        return []

    num_cluster_b = 0
    end = []
    cursor = n-1

    while 0 <= cursor:
        if s[cursor] == "x":
            cursor -= 1
            continue
        else:
            num_cluster_b += 1
            end.insert(0, cursor)
            cursor -= c+1

    if k < num_cluster_b:
        return []

    ans = []
    if num_cluster_b < num_cluster_f:
        num_cluster_f = num_cluster_b
    for s, e in zip(start, end):
        if s == e:
            ans.append(s+1)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n, k, c = map(int, input().split(" "))
    s = input()
    
    ans = abc161e(n, k, c, s)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
from sys import stdin
import sys
sys.setrecursionlimit(10**8)
 
def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]
 
 
def ox(s, i):
	return s[i]=="o"
 
 
def main():
	n,k,c=nextIntList()
	s=nextLine()
	
	height=(c+1)*(k-1)+1
# 	print("height",height)
# 	print(n,k,c)
# 	print(s)
	
	record={}
	for i0 in range(height):
		for i1 in range(i0, n-height+i0+1):
			r=[]
			if i0==0:
				if ox(s,i1):
					r.append([i1])
			else:
				if i0%(c+1)==0: #o
					if ox(s, i1) and (i0-1, i1-1) in record:
						r=list(record[i0-1,i1-1])
						for i,ri in enumerate(r):
							if len(ri)<k:
								ri=list(ri)
								ri.append(i1)
								r[i]=ri
				elif i0%(c+1)==c: #last x
					r2=[]
					if (i0-1, i1-1) in record:
						r2.append(record[i0-1, i1-1])
					if (i0, i1-1) in record:
						r2.append(record[i0, i1-1])
					
					if len(r2)==1:
						r=r2[0]
					elif len(r2)==2:
						rSet=set()
						for r01 in r2:
							for ri in r01:
								rSet.add(tuple(ri))
						r=[list(ri) for ri in rSet]
				else:
					if (i0-1, i1-1) in record:
						r=record[i0-1,i1-1]
			
			if len(r)>0:
				record[i0,i1]=r
 
	s=None
	i0=height-1
	for i1 in range(height-1, n):
		if (i0,i1) in record:
			for r in record[i0,i1]:
				if len(r)==k:
					if s is None:
						s=set(r)
					s=s&set(r)
					if len(s)==0:
						sys.exit(0)
	
	for i in sorted(s):
		print(i+1)
	
	
if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N,K,C=(int(x) for x in input().split())
S=list(input())
Ss=[x for x in range(N) if S[x]=='o']
X = list(combinations(Ss,K))
X1 = [x for x in X if all((x[p+1]-x[p])>C for p in range(K-1))]
X2 = [p+1 for p in Ss if all(p in a for a in X1)]
for i in X2:
  print(i)

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
owari = max(dp[i] - k, 0)
while i < N:
    if dp[i] < k:
        # print(i, cnt, ans, k, ans + C + 1)
        if cnt == 1:
            print(ans + 1)
        i = ans + C + 1
        ans = 0
        cnt = 0
        k -= 1
        if k == owari:
            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:
from itertools import combinations
n, k, c = map(int, input().split())
s = list(input())

l = []
for i in range(n):
    if s[i] == "o":
        l.append(i+1)

l2 = list(combinations(l, k))

work =[]
for i in range(len(l2)):
    for j in range(k-1):
        if l2[i][j+1] - l2[i][j] <= c:
            break
    else:
        work.append(l2[i])

for i in work[0]:
    for j in range(len(work)):
        if i not in work[j]:
            break
    else:
        print(i)

Submission status: Time Limit Exceeded

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


def solve(s2):
    work = 0
    i = 0
    while i < n:
        if s2[i] != 'x':
            work += 1
            i += c + 1
            if work == k:
                return True
        else:
            i += 1
    return False


days = []
for i in range(n):
    if s[i] != 'x':
        s2 = s[:i] + 'x' + s[i+1:]
        if not solve(s2):
            days.append(i+1)

for day in days:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
n, k, c = map(int, input().split())
s = input()
accu = []
tmp = 0
r = 0
for cc in s:
    r -= 1
    if cc=='x' or r>0:
        accu.append(tmp)
        continue
    tmp += 1
    accu.append(tmp)
    r = c+1


for i, cc in enumerate(s):
    if cc=='x':
        continue
    if i>0 and accu[i]==accu[i-1]:
        continue
    if i==0:
        tmp = 0
    else:
        tmp = accu[i-1]
    r = 0
    for j in range(i+1, n):
        r -= 1
        if s[j]=='x' or r>0:
            continue
        tmp += 1
        if tmp >= k:
            break
        r = c+1
    else:
        if tmp<k:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n, k, c = tuple([int(i) for i in input().split()])
    s = input()
    total_working = sum(1 for char in s if char == 'o')

    mandatory = set([i + 1 for i in range(len(s)) if s[i] == 'o'])
    for i in range(len(s)):
        if s[i] != 'o':
            continue
        # is it possible to traverse without visiting this node?
        j = 0
        todo = k
        while j < len(s) and todo > 0:
            if j != i and s[j] == 'o':
                todo -= 1
                j += c
            j += 1
        if todo == 0:
            mandatory.remove(i + 1)

    mandatory = sorted(list(mandatory))
    for n in mandatory:
        print(n)

Submission status: Time Limit Exceeded

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


base_day = []
bef = 0
work = 0
while True:
    if bef >= n:
        break
    if s[bef] =="o":
        base_day.append(bef)
        bef += c+1
        work += 1
        if work == k:
            break
    else:
        bef += 1


if n == k and c == 0:
    for i in range(1,n+1):
        print(i)
else:
    for day in base_day:
        work = 0
        bef = 1
        while True:
            if bef >= n:
                break
            if s[bef] == "o" and bef != day:
                bef += c + 1
                work += 1
                if work == k:
                    break
            else:
                bef += 1

        if work < k:
            print(day+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def GetBase():
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S):
        if s == 'x':
            continue
        elif last + C >= i:
            continue

        ret.append(i)
        last = i
    return ret


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    depend_dict = GetDepend(base_ans)
    for b in base_ans:
        if depend_dict[b] is True:
            continue
        S[b] = 'x'
        if len(GetBase()) < K:
            depend_dict[b] = True
        S[b] = 'o'

    return [a + 1 for a in base_ans if depend_dict[a] is True]


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left

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

last = deque()
pre = -C - 1
for i, s in enumerate(reversed(S)):
  if i > pre + C and s == 'o':
    last.appendleft(N - 1 - i)
    pre = i
    if len(last) == K:
      break
lastset = set(last)

count = 0
pre = -C - 1
for i, s in enumerate(S):
  if i > pre + C and s == 'o':
    if i in lastset and count <= bisect_left(last, i) + 1:
      print(i + 1)
    pre = i
    count += 1
    if count == K:
      break

Submission status: Time Limit Exceeded

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

ans = []
for i in range(n):
  
  save = s[i]
  s[i] = 'x'
  count = 0
  j = 0
  while j < n:  
    if s[j] == 'o':
      count += 1
      j += c+1
    else:
      j += 1  
      
  if count < k:
    ans.append(i+1) 
    
  s[i] = save
  
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

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

days=[]
i=0
while i<N:
    if S[i]=='o':
        days.append(i)
        i+=C
    if len(days)>=K:
        break
    i+=1

days=days[::-1]
while len(days)!=0:
    p=days.pop()
    S[p]='x'
    days2=[]
    j=0
    while j<N:
        if S[j]=='o':
            days2.append(j)
            j+=C
        if len(days2)>=K:
            break
        j+=1
    if len(days2)>=K:
        days=set(days)&set(days2)
    else:
        print(p+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
from itertools import combinations

def main():
    N, K, C = input_nums()
    S = input()
    index = [i for i in range(len(S)) if S[i] == 'o']
    index = list(combinations(index, K))
    index_2 = []
    for idx in index:
        flag = True
        for i in range(len(idx)-1):
            if idx[i+1] - idx[i] <= C:
                flag = False
                break
        if flag:
            index_2.append(idx)
    # print(index_2)
    s = set(index_2[0])
    for idx in index_2:
        s &= set(idx)
    for i in s:
        print(i+1)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
import itertools

N, K, C = map(int, input().split(' '))
S = input()
candidates = [n for n in range(1, N+1)]

del_num = 0
for i, el in enumerate(S):
    if el == 'x':
        del candidates[i - del_num]
        del_num += 1

ans = set(candidates)

for date in itertools.combinations(candidates, K):
    add_flag = True
    for i in range(1, len(date)):
        if date[i] - date[i-1] <= C:
            add_flag = False
            break
    if add_flag:
#         print(date)
        ans = ans & set(list(date))

ans = list(ans)
if ans == []:
    exit(0)
else:
    ans.sort()
    for el in ans:
        print(el)

Submission status: Time Limit Exceeded

Solution code:
import itertools

from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


def ox(s, i):
	return s[i]=="o"


def main():
	n,k,c=nextIntList()
	s=nextLine()
	
	height=(c+1)*(k-1)+1
# 	print("height",height)
# 	print(n,k,c)
# 	print(s)
	
	record={}
	for i0 in range(height):
		for i1 in range(n-height+i0+1):
			r=[]
			if i0==0:
				if ox(s,i1):
					r.append([i1])
			else:
				if i0%(c+1)==0: #o
					if ox(s, i1) and (i0-1, i1-1) in record:
						r=list(record[i0-1,i1-1])
						for i,ri in enumerate(r):
							if len(ri)<k:
								ri=list(ri)
								ri.append(i1)
								r[i]=ri
				elif i0%(c+1)==c: #last x
					r2=[]
					if (i0-1, i1-1) in record:
						r2.append(record[i0-1, i1-1])
					if (i0, i1-1) in record:
						r2.append(record[i0, i1-1])
					
					if len(r2)==1:
						r=r2[0]
					elif len(r2)==2:
						rSet=set()
						for r01 in r2:
							for ri in r01:
								rSet.add(tuple(ri))
						r=[list(ri) for ri in rSet]
				else:
					if (i0-1, i1-1) in record:
						r=record[i0-1,i1-1]
			
			if len(r)>0:
				record[i0,i1]=r

	s=None
	i0=height-1
	for i1 in range(height-1, n):
		if (i0,i1) in record:
			for r in record[i0,i1]:
				if len(r)==k:
					if s is None:
						s=set(r)
					s=s&set(r)
					if len(s)==0:
						sys.exit(0)
	
	for i in sorted(s):
		print(i+1)
	
	
if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k,c=map(int,input().split())
S=input()

d=deque()
ans=[]
for i in range(n):
  if S[i]=='o':
    if len([i])==k:
      ans.append([i])
    else:
      d.append([i])
while len(d)>0:
  tmp=d.pop()
  now=tmp[-1]
  for i in range(now+c+1,n):
    if S[i]=='o':
      ls=tmp+[i]
      if len(ls)==k:
        ans.append(ls)
      else:
        d.append(ls)    
if len(ans)==0: exit()
  
cnt,out=[0]*n,[]
for a in ans:
  for tmp in a:
    cnt[tmp]+=1
    if cnt[tmp]==len(ans):
      out.append(tmp+1)
print(*out,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def muri(k, c, s):
  if k > s.count("o"):
    return True
  for j in range(len(s)):
    if s[j] == "o":
      return muri(k-1, c, s[j+c+1:])
  return False

n, k, c = map(int, input().split())
s = input()
s += "x"*c

for i in range(len(s)):
  if s[i] == "o":
    if muri(k, c, s[:i]+"x"+s[i+1:]):
      print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

input_str = input()
N, K, C = list(map(lambda x: int(x), input_str.split(' ')))

S = list(input())
tmp = [day for day, char in enumerate(S) if char == 'o']
FD_list = np.array(tmp)

stack = [[day] for day in tmp]
result = []
while stack:
  head = stack.pop()
  if len(head) > K -1:
    result.append(head)

  head_tail = head[-1]

  adder = FD_list[FD_list > (head_tail + C)]

  for tmp in adder:
    stack.append(head + [tmp])

if result:
  final_result = set(result[0])
  for tmp in result:
    final_result = final_result.intersection(set(tmp))
  [print(tmp+1) for tmp in final_result]
else:
  pass

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

input_str = input()
N, K, C = list(map(lambda x: int(x), input_str.split(' ')))

S = list(input())
tmp = [day for day, char in enumerate(S) if char == 'o']
FD_list = np.array(tmp)

stack = [[day] for day in tmp]
result = []
while stack:
  head = stack.pop()
  if len(head) > K -1:
    result.append(head)

  head_tail = head[-1]

  adder = FD_list[FD_list > (head_tail + C)]

  for tmp in adder:
    stack.append(head + [tmp])

if result:
  final_result = set(result[0])
  for tmp in result:
    final_result = final_result.intersection(set(tmp))
  [print(tmp+1) for tmp in final_result]
else:
  print('END')
  pass

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left

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

last = deque()
pre = -C - 1
for i, s in enumerate(S[::-1]):
  if i > pre + C and s == 'o':
    last.appendleft(N - 1 - i)
    pre = i
    if len(last) == K:
      break
lastset = set(last)

count = 0
pre = -C - 1
for i, s in enumerate(S):
  if i > pre + C and s == 'o':
    if i in lastset and count <= bisect_left(last, i) + 1:
      print(i + 1)
    pre = i
    count += 1
    if count == K:
      break

Submission status: Time Limit Exceeded

Solution code:
def calc(N, K, C, S):
    ans = []
    memo = [[]]
    for i in range(N):
        new_memo = list(memo)
        for m in memo:
            if S[i] == 'o' and i - (m[0] if m else -N * 2) > C:
                x = [i] + m
                if len(x) == K:
                    ans += [x]
                else:
                    new_memo += [x]
        memo = new_memo
    result = []
    for j in ans[0]:
        b = True
        for k in ans[1:]:
            b = j in k
            if not b:
                break
        if b:
            result += [str(j + 1)]
    result.reverse()
    return '\n'.join(result)



(N, K, C) = tuple([int(s) for s in input().split()])
S = input()
print(calc(N, K, C, S))

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import numpy as np

n,k,c = mi()
s = input()


def isClear(s):
    cnt = n-1
    wa = 0
    while 1:
        if s[cnt] == 'o':
            wa+=1
            cnt-=c+1
        else:
            cnt-=1        
        if wa == k: return 1
        if cnt<=-1: return 0

ans = []
for i in range(n):
    if s[i] == 'x':
        continue
    else:
        ss = s[:i] + 'x' + s[i+1:]
        if isClear(ss) == 0:
            ans.append(i+1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N, K, C = map(int, input().split())
m = {"x":0, "o":1}
S = list(map(lambda x:m[x], input()))

must = []
k = -1
while 1:
  try:
    if k >= 0:
      S[k] = 1
    k = S.index(1, k+1)
    S[k] = 0
  except:
    break
  j = -C-1
  for i in range(K):
    try:
      j = S.index(1, j+C+1)
    except:
      must.append(k)
      break

for m in must:
  print(m+1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
N,K,C = map(int,input().split())
S = input()

A = []
for i in range(N):
  if S[i] == 'o':
    A.append(i + 1)
V = 0
for v in itertools.permutations(A, K):
  k = np.diff(v, n= 1)
  if all(k > C) == True:
    if V == 0:
      V = set(v)
    else:
      V = V  & set(v)
V = list(V)
V.sort()
print(*V)

Submission status: Time Limit Exceeded

Solution code:
N, K, C = list(map(int, input().split()))
S = input()
cal = ['' for i in range(N)]
Q = []
for i in range(N):
    if S[i] == 'x':
        cal[i] = 'x'
    else:
        Q.append(i)

ans = []
for q in Q:
    # q+1日目を休んだ場合に成立するかを調べて背理法を使う
    temp = cal[:]
    temp[q] = 'x'
    total = 0
    i = 0
    # 貪欲に出社
    while total < K and i < N:
        if temp[i] == 'x':
            i += 1
        else:
            total += 1
            i += C + 1
    # 出社日数が足りないなら、q+1日目は必ず出社
    if total < K:
        ans.append(q+1)
        for j in range(max(0, q-C), min(N, q+C)):
            cal[j] = 'x'
        cal[q] = 'o'
if len(ans) > 0:
    print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k,c=map(int,input().split())
S=input()

d=deque()
ans=[]
for i in range(n):
  if S[i]=='o':
    if len([i])==k:
      ans.append([i])
    else:
      d.append([i])
while len(d)>0:
  tmp=d.pop()
  now=tmp[-1]
  for i in range(now+c+1,n):
    if S[i]=='o':
      if len(tmp+[i])==k:
        ans.append(tmp+[i])
      else:
        d.append(tmp+[i])
        
if len(ans)==0: exit()
  
cnt=[0]*n
for a in ans:
  for tmp in a:
    cnt[tmp]+=1
    
out=[]
for i,c in enumerate(cnt):
  if c==len(ans):
    out.append(i+1)
print(*out,sep='\n')

Submission status: Time Limit Exceeded

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

wd = [i for i, e in enumerate(ss) if e == 'o']
wd_flg = [True for _ in wd]

used = [0]
cur = wd[0]
if k != 1:
  for i, e in enumerate(wd):
    if e > cur + c:
      used.append(i)
      cur = e
      if len(used) == k:
        break
        
used_rev = [len(wd)-1]
cur = wd[-1]
if k != 1: 
  for i, e in enumerate(wd[::-1]):
    if e < cur - c:
      used_rev.append(len(wd) - 1 - i)
      cur = e
      if len(used_rev) == k:
        break

for i in used:
  if i not in used_rev:
    continue
  if len(used[:used.index(i)]) + len(used_rev[:used_rev.index(i)]) >= k:
    continue
  else:
    print(wd[i]+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [0] * (n + 1)
for i in reversed(range(n)):
    j = min(i + c + 1, n)
    if s[i] == 'o':
        dp[i] = max(dp[j] + 1, dp[i + 1])
    else:
        dp[i] = max(dp[j], dp[i + 1])

# print(dp)


def check(idx):
    if s[idx] == 'x':
        return False

    s[idx] = 'x'
    dp_ = [0] * (idx + 2)
    dp_[idx + 1] = dp[idx + 1]
    for i in reversed(range(idx + 1)):
        j = min(i + c + 1, idx + 1)
        if s[i] == 'o':
            dp[i] = max(dp[j] + 1, dp[i + 1])
        else:
            dp[i] = max(dp[j], dp[i + 1])
        if dp[i] >= k:
            s[idx] = 'o'
            return False

    s[idx] = 'o'
    return True


for i in range(n):
    if check(i):
        print(i + 1)

Submission status: Time Limit Exceeded

Solution code:
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % mod) % mod
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N,K,C = isRaw()
    S = sRaw()
    ans = []
    for n in range(N):
        ava = 0
        idx = 0
        while idx < N:
            if S[idx]=="x" or idx == n:
                idx+=1
                continue
            ava+=1
            if ava==K:
                break
            idx+=C+1
        if ava < K :
            ans.append(str(n+1))
            
    return "\n".join(ans)

if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
N, K, C = [int(i) for i in input().split()]
S = input()
ok_days = []
for ind, s in enumerate(S):
    if(s=='o'):
        ok_days.append(ind+1)

def search(li, ext):
    last = 0
    cnt = 0
    for i in li:
        if(i==ext):
            continue
        if(i>last):
            cnt += 1
            last = i+C
        if(cnt>=K):
            return True
    return False

for cand in ok_days:
    if(not search(ok_days, cand)):
        print(cand)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

wd = [i for i, e in enumerate(ss) if e == 'o']
wd_flg = [True for _ in wd]

used = [0]
cur = wd[0]
if k != 1:
  for i, e in enumerate(wd):
    if e > cur + c:
      used.append(i)
      cur = e
      if len(used) == k:
        break
        
used_rev = [len(wd)-1]
cur = wd[-1]
if k != 1: 
  for i, e in enumerate(wd[::-1]):
    if e < cur - c:
      used_rev.append(len(wd) - 1 - i)
      cur = e
      if len(used_rev) == k:
        break

a = sorted(set(used) & set(used_rev))

for i in a:
  if len(used[:used.index(i)]) + len(used_rev[:used_rev.index(i)]) >= k:
    continue
  else:
    print(wd[i]+1)

Submission status: Time Limit Exceeded

Solution code:
def judge(S):
    count = 0
    pos = 0
    while(True):
        if count == K:
            return True
        if pos >= len(S):
            return False
        if S[pos] == "o":
            count += 1
            pos += C + 1
        else:
            pos += 1
            
N, K, C = [int(i) for i in input().split()]
S = input()
if not judge(S):
    print("")
else:
    for i in range(N):
        if S[i] == "o":
            tmp = S[:i] + "x" + S[i+1:]
            if judge(tmp) == False:
                print(i + 1)

Submission status: Time Limit Exceeded

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

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

def check(plan):
    cnt=0
    ii=0
    while ii<N:
        if plan[ii]=='o':
            cnt+=1
            ii+=C
        if cnt>=K:
            break
        ii+=1
    if cnt>=K:
        return True
    else:
        return False

p=S
for i in days:
    p[i]='x'
    if not check(p):
        print(i+1)
    p[i]='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:
    if s[j] =='o':
        continue
    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:
            if i == 'a':
                tmp[num] = 'o'
            wait -= 1
            continue
        if i == 'o' or i == 'a':
            wait = c
            last_day -= 1
    if last_day > 0:
        ans.append(j+1)
    else:
        s = copy.deepcopy(tmp)
        
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left

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

first = deque()
pre = -C - 1
for i, s in enumerate(S):
  if i > pre + C and s == 'o':
    first.append(i)
    pre = i
    if len(first) == K:
      break
firstset = set(first)

last = deque()
pre = -C - 1
for i, s in enumerate(S[::-1]):
  if i > pre + C and s == 'o':
    last.appendleft(N - 1 - i)
    pre = i
    if len(last) == K:
      break
lastset = set(last)

for i, s in enumerate(S):
  if s == 'o':
    if i not in firstset or i not in lastset:
      continue
    if bisect_left(first, i) <= bisect_left(last, i):
      print(i + 1)

Submission status: Time Limit Exceeded

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

a = []
b = []

d = 0
for i in range(k):
    while s[d] == 'x':
        d += 1
    a.append(d)
    d += c+1

d = -1
for i in range(k):
    while s[d] == 'x':
        d -= 1
    b.insert(0, n+d)
    d -= c+1

for i in range(k):
    if a[i] == b[i]:
        print(a[i]+1)

Submission status: Time Limit Exceeded

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

s=input()

s=list(s)

memo = []

for num, i in enumerate(s):
    if i == 'o':
        memo.append(num)

count = 0

ans = [0]*200000

for i in itertools.combinations(memo, k):
    check = True
    #print(count)
    for j in range(k-1):
        if abs(i[j]-i[j+1]) <= c:
            check =False
            break
    if check:
        count += 1
        for p in i:
            ans[p] += 1

for num, l in enumerate(ans):
    if l == count:
        print(num+1)

Submission status: Time Limit Exceeded

Solution code:
n,k,c=map(int,input().split())
s=list(input())
for i in range(len(s)):
	if s[i]=="x":
		s[i]=False
	else:
		s[i]=True
i=0
work=[]
while len(work)<k:
	if s[i]:
		work.append(i)
		i+=c+1
	else:
		i+=1
#print(work)

for day in work:
	s0=s[:]
	s0[day]=False
	i=0
	cnt=0
	while i<n:
		if s0[i]:
			i+=c+1
			cnt+=1
		else:
			i+=1
	if cnt<k:
		print(day+1)

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
    ii=0
    while ii<N:
        if plan[ii]=='o':
            cnt+=1
            ii+=C
        if cnt>=K:
            break
        ii+=1
    if cnt>=K:
        return True
    else:
        return False

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, K, C = lr()
    S = [i for i, s in enumerate(sr()) if s == 'o']
    ans = []
    for i in S:
        no_work = -1
        cnt = 0
        for j in S:
            if j == i:
                continue
            if j <= no_work:
                continue
            cnt += 1
            no_work = j+C
        if cnt < K:
            ans.append(i+1)
    print(*ans, sep='\n')
resolve()