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: Runtime Error

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

work_days_list = []
whole_days_list = []
for i in range(N):
    new_work_days_list = []
    if S[i] == 'o':
        new_work_days_list.append([i])
    else:
        continue
    for work_days in work_days_list:
        new_work_days_list.append(work_days)
        if i - work_days[-1] > C:
            new_work_days = work_days + [i]
            if len(new_work_days) == K:
                whole_days_list.append(set(new_work_days))
            else:
                new_work_days_list.append(new_work_days)
    work_days_list = new_work_days_list

tmp_days = whole_days_list.pop()
while len(whole_days_list) > 0:
    tmp_days &= whole_days_list.pop()

for day in tmp_days:
    print(day+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k,c = map(int,input().split())
s = input()
dp1 = [0] * (n+1)
dp2 = [0] * (n+1)
# dp[i] = (選択したなかで一番左側のindex,選択した個数)
now = 10 ** 7;count = 0
for i in range(n-1,-1,-1):
  if s[i] == "o" and i + c < now:
    count += 1; now = i
    dp1[i] = (i,count)
  elif i == n-1:dp1[i] = (inf,0)
  else:
    dp1[i] = dp1[i+1]

now = - 10 ** 7;count = 0
for i in range(n):
  if s[i] == "o" and now + c < i:
    count += 1; now = i
    dp2[i] = (i,count)
  elif i == 0:dp2[i] = (-inf,0)
  else:
    dp2[i] = dp2[i-1]

# dp1:右から　　dp2:左から
if dp1[1][1] < k:print(1)
for i in range(1,n-1):
  index0,count0 = dp1[i+1]
  if index0 - c >= 0:
    count0 += dp2[min(index0-c,i-1)][1]
  if count0 < k:
    print(i+1)
if dp2[n-2][1] < k:print(n)
# print(dp2)

Submission status: Runtime Error

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

for i in used:
  nokori = copy.deepcopy(wd)
  nokori.remove(wd[i])
  count = 1
  cur = nokori[0]
  flg = True
  if count == k:
    flg = False
  else:
    for e in nokori:
      if e > cur + c:
        count += 1
        cur = e
        if count == k:
          flg = False
          break
  if flg:
    print(str(wd[i]+1))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    N, K, C = map(int, readline().split())
    S = list(map(int, readline().split()))
    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: Runtime Error

Solution code:
#!/usr/bin/env python3

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

    left = getleft(s, n, c)
    right = list(reversed(getleft(s[::-1], n, c)))

    for i in range(n):
        if i == 0:
            canrest = (right[i + 1][0] >= k)
        elif i == n - 1:
            canrest = (left[i - 1][0] >= k)
        else:
            if left[i - 1][0] + right[i + 1][0] >= k + 1:
                canrest = True
            elif (left[i - 1][0] + right[i + 1][0] >= k) and (left[i - 1][1] + right[i + 1][1] >= c - 1):
                canrest = True
            else:
                canrest = False
        if not canrest:
            print(i + 1)

def getleft(s, n, c):
    left = [None for i in range(n)]
    x = 0
    d = 10 ** 9
    for i in range(n):
        if s[i] == "o":
            if d >= c:
                x += 1
                d = 0
            else:
                d += 1
        else:
            d += 1
        left[i] = (x, d)
    return left

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

Af = [0]*N
Rf = [0]*N
d = 0
f = 0
for i, s in enumerate(S):
    f-=1
    if s=='o' and f<0:
        d+=1
        f=C
    Af[i]=d
    Rf[i]=C-f

Ab = [0]*N
Rb = [0]*N
d = 0
f = 0
for i, s in enumerate(S[::-1]):
    f-=1
    if s=='o' and f<0:
        d+=1
        f=C
    Ab[N-i-1]=d
    Rb[N-i-1]=C-f

if Ab[1]<K:
    print(1)

for i in range(1, N-1):
    if Af[i-1]+Ab[i+1]>K: continue
    if Af[i-1]+Ab[i+1]==K and Rf[i-1]+Rb[i+1]+1>=C: continue
    print(i+1)

if Af[-2]<K:
    print(N)

Submission status: Runtime Error

Solution code:
#差がC以下はダメ（Cもダメ）
N,K,C=map(int,input().split())
S=input()
X=[]
for i in range(N):
    if S[i]=="o":
        X.append(i+1)
M=len(X)
#例外処理（M=1のとき）
#ACしたので試験的にコメントアウト
'''
if M==1:
    #このときK==1
    print(X[0])
    exit()
'''
#X[i]日に働くとき、その直前or直後で働ける最も近い日のindex
L=[-1 for i in range(M)]
R=[-1 for i in range(M)]
j=1
for i in range(M-1):
    while(j<M):
        if X[j]-X[i]>=C+1:
            R[i]=j
            break
        else:
            j+=1
j=M-2
for i in range(M-1,0,-1):
    while(j>=0):
        if X[i]-X[j]>=C+1:
            L[i]=j
            break
        else:
            j-=1
LD=[-1 for i in range(M)]
RD=[-1 for i in range(M)]
def Ldfs(i):
    if LD[i]!=-1:
        return LD[i]
    if L[i]==-1:
        LD[i]=1
        return 1
    else:
        LD[i]=Ldfs(L[i])+1
        return Ldfs(L[i])+1
def Rdfs(i):
    if RD[i]!=-1:
        return RD[i]
    if R[i]==-1:
        RD[i]=1
        return 1
    else:
        RD[i]=Rdfs(R[i])+1
        return Rdfs(R[i])+1
for i in range(M):
    Ldfs(i)
    Rdfs(M-1-i)
Y=[0 for i in range(M)]
Y[0]=RD[1]
Y[-1]=LD[-2]
for i in range(1,M-1):
    Y[i]=LD[i-1]+RD[i+1]
for i in range(M):
    if Y[i]<K:
        print(X[i])

Submission status: Runtime Error

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]
for i, e in enumerate(wd):
  if e > cur + c:
    used.append(i)
    cur = e
    if len(used) == k:
      break

for i in used:
  nokori = copy.deepcopy(wd)
  nokori.remove(wd[i])
  count = 1
  cur = nokori[0]
  flg = True
  used = [nokori[0]]
  for e in nokori:
      if e > cur + c:
        count += 1
        cur = e
        if count == k:
          flg = False
          break
  if flg:
    print(str(wd[i]+1))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

    left = getleft(s, n, c)
    right = list(reversed(getleft(s[::-1], n, c)))

    for i in range(n):
        if i == 0:
            canrest = (right[i + 1][0] >= k)
        elif i == n - 1:
            canrest = (left[i - 1][0] >= k)
        else:
            if left[i - 1][0] + right[i + 1][0] >= k + 1:
                canrest = True
            elif (left[i - 1][0] + right[i + 1][0] >= k) and (left[i - 1][1] + right[i + 1][1] >= c - 1):
                canrest = True
            else:
                canrest = False
        if not canrest:
            print(i + 1)

def getleft(s, n, c):
    left = [None] * n  # x, d
    x = 0
    d = 10 ** 9
    for i in range(n):
        if s[i] == "o":
            if d >= c:
                x += 1
                d = 0
            else:
                d += 1
        else:
            d += 1
        left[i] = (x, d)
    return left

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n, k, c = [int(s) for s in input().strip().split()]
    s = input().strip()

    prefix, suffix = [0] * n, [0] * n
    for i in range(n):
        if s[i] == "o":
            prefix[i] = 1 + (prefix[i - c - 1] if i - c - 1 >= 0 else 0)
        else:
            prefix[i] = prefix[i - 1]
    for i in range(n - 1, -1, -1):
        if s[i] == "o":
            suffix[i] = 1 + (suffix[i + c + 1] if i + c + 1 < n else 0)
        else:
            suffix[i] = suffix[i + 1]
    
    cont = 0
    for i in range(-c + 1, n):
        ok = (prefix[i - 1] if i - 1 >= 0 else 0) + (suffix[i + c] if i + c < n else 0) >= k
        if ok:
            cont = 0
        else:
            cont += 1
            if cont >= c:
                print(i + 1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def solve(idx, work_days):
    global cnt

    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
            solve(idx + 1, work_days)
        else:
            # work
            solve(idx + 1, work_days + [idx + 1])

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

        # not work
        solve(idx + 1, work_days)

solve(0, [])

# print(cnt, m)
ans = []

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

for day in ans:
    print(day)

Submission status: Runtime Error

Solution code:
N,K,C = map(int,input().split())
S = list(input())
L = [(0,-C) for i in range(N+1)]
R = [(0,N+C+1) for i in range(N+1)]
for i in range(N):
	l = L[i]
	s = S[i]
	if s == "o" and l[1] + C < i+1:
		L[i+1] = (l[0]+1, i+1)
	else:
		L[i+1] = L[i]

	r = R[N-i]
	s = S[N-1-i]
	if s == "o" and N-i + C < r[1]:
		R[N-i-1] = (r[0]+1, N-i)
	else:
		R[N-i-1] = R[N-i]

R = [(0,0)] + R

for n in range(N):
	d = n+1
	if d == 1:
		if R[2][0] < K:
			print(d)
		continue
	if d == N:
		if L[N-1][0] < K:
			print(d)
		continue
	l = L[d-1]
	r = R[d+1]
	if l[0] + R[max(d+1, l[1]+C)][0] < K and r[0] + L[min(d-1, r[1]-C)][0]:
		print(d)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# coding: utf-8
"""
about module
"""


def main():
    n, k = map(int, input().split())
    if n > k:
        n = n % k

    while n * 2 > k:
        n = abs(n - k)
    return n


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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


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 == K:
            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, 0)
    if ans[0] is not None:
        for i in range(N):
            if (ans[0] & (1 << i)) != 0:
                print(i + 1)


main()

Submission status: Runtime Error

Solution code:
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 == K:
            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)

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


main()

Submission status: Runtime Error

Solution code:
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)