Problem:


Score : 300 points

Problem Statement

There are N stones arranged in a row. Every stone is painted white or black.
A string S represents the color of the stones. The i-th stone from the left is white if the i-th character of S is ., and the stone is black if the character is #.

Takahashi wants to change the colors of some stones to black or white so that there will be no white stone immediately to the right of a black stone.
Find the minimum number of stones that needs to be recolored.

Constraints

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

S is a string of length N consisting of . and #.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the minimum number of stones that needs to be recolored.

Sample Input 1

3
#.#

Sample Output 1

1

It is enough to change the color of the first stone to white.

Sample Input 2

5
#.##.

Sample Output 2

2

Sample Input 3

9
.........

Sample Output 3

0



Sample input:
3
#.#


Sample output:
1

Submission status: Runtime Error

Solution code:
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

N = int( input())
A = [ int( input()) for _ in range(N+1)]
Primes = eratosththenes(N)
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1): # f が恒等的に 0 であるかどうかのチェック
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1): # フェルマーの小定理
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 0
        if sum(poly) == 0 and A[N]%p == 0: # a_0 が 0 かつ、g が恒等的に 0 であることをチェックしている
            check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
i = 0
while i < N:
    if S[i] == "#":
        break
    i += 1
t_b = 0
k = N-1
while(S[k] == "#"):
    k -= 1
    t_b += 1
if i == N:
    print(0)
else:
    count = 0
    for j in range(i,N):
        if S[j] == ".":
            count += 1
    if N - (count + i) - t_b <= count:
            print(N - count - i - t_b)
    else:
            print(count)

Submission status: Runtime Error

Solution code:
# スペース区切りの整数の入力
a, b = map(int, input().split())
# 文字列の入力
s = [2*a-1, 2*b-1, a+b]
# 出力
print("{}".format(max(s)))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

N = input()
S = input()

# 黒の右を黒に変える　or 黒を白にする
# 黒より右を全て黒にするか、黒を白にするか


firstblack = S.find('#') # ない場合は-1を返す
if int(firstblack) == int(-1):
    print(0)
    sys.exit()
if int(firstblack) == int(N):
    print(1)
    sys.exit()

check1 = S[(firstblack+1):]
edgeblack = check1.rfind('.') + 1
if int(edgeblack) == int(0):
    print(0)
    sys.exit()

if int(edgeblack) ==int(len(check1)-1)
    check2 = check1 
    blacknum = check2.count('#') # 黒の個数を返す
    whitenum = check2.count('.') # 白の個数を返す
    if whitenum <= blacknum:
        print(whitenum)
    else:
        print(blacknum + 1)
else:
    check2 = check1[:edgeblack]
    blacknum = check2.count('#') # 黒の個数を返す
    whitenum = check2.count('.') # 白の個数を返す

    if whitenum <= blacknum:
        print(whitenum)
    else:
        print(blacknum + 1)

Submission status: Runtime Error

Solution code:

def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(0, sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + dp[i - 1][length] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0

def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    for i in range(1, N):
        for length in range(0, sum_A + 1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= A[i]:
                dp[i][length] = dp[i - 1][length - A[i]] + dp[i - 1][length] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            dp[i][length] %= mod
            if length >= A[i]:
                dp2[i][length] = dp2[i - 1][length - A[i]] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
cumsum_b = [0] * (N+1)
cumsum_w = [0] * (N+1)

for i in range(N):#累積和
  if S[i] == "#":
    cumsum_b[i+1] += cumsum_b[i] + 1
  else:
    cumsum_w[i+1] += cumsum_w[i] + 1

ans = N
for left in range(1,N+1):#白の範囲を全探索
  tmp = 0
  tmp += cumsum_b[left] - cumsum_b[1]
  tmp += cumsum_w[-1] - cumsum_w[left]
  ans = min(ans,tmp)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())
i = 0

while True:
  if S[i] == ".":
    S.pop(i)
    i += 1
  else:
    break
print(S.count("."))

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())

while True:
  if S[i] == ".":
    S.pop(i)
  else:
    break
print(S.count("."))

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(input())
a = S.pop(0)
b = S.pop(N - 1)

c = 0
for i in range(N - 1):
  if a[i] == "#" and b[i] == ".":
    c += 1
print(c)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
""""
import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
N = int(input())
S = input()
def main():
    B_list = []
    W_list = []
    BW_list = []
    for n in range(N):
        if S[n] == "#":
            B_list.append(n)
        else:
            W_list.append(n)
        if n > 0 and S[n] != S[n-1]:
            BW_list.append(n-1)
            
    if len(B_list) ==0 or len(W_list)==0:
        print(0)
        sys.exit()
    num_BL =np.inf
    num_WR =np.inf
    res = np.inf
    for i, n in enumerate(BW_list):
        num_BL = len(B_list[:find_index(BW_list, n)+1])
        num_WR = len(W_list[find_index(BW_list, n)+1:])
        res = min(res, num_BL+num_WR)
    print(res)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
N = int(input())
S = input()
def main():
    B_list = []
    W_list = []
    BW_list = []
    for n in range(N):
        if S[n] == "#":
            B_list.append(n)
        else:
            W_list.append(n)
        if n > 0 and S[n] != S[n-1]:
            BW_list.append(n)
            
    if len(B_list) ==0 or len(W_list)==0:
        print(0)
        sys.exit()
    num_BL =np.inf
    num_WR =np.inf
    for i, n in enumerate(BW_list):
        num_BL = len(B_list[:find_index(BW_list, n)+1])
        num_WR = len(W_list[find_index(BW_list, n)+1:])
        res = min(res, num_BL+num_WR)
    print(res)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

n = int(input().split())
s = input().split()

cnt = 0
for i in range(1, n):
    if s[i-1:i+1] == '#.':
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)]
A.reverse()
g = A[0]
for a in A:
     g = gcd(g,a)
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+2)

for p in prime:
    for n in range(p-1):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()

#連続する文字の個数数えてリストに入れる
saki = 0
ato = 0
f = S[0]
switch = 0
kazu_list = []
for i in range(N):
    if S[i] == f and switch == 0:
        saki += 1
    
    if S[i] != f and switch == 1:
        ato += 1

    if S[i] != f and switch == 0:
        kazu_list.append(saki)
        saki = 0
        switch = 1
        ato = 1
    
    if S[i] == f and switch == 1:
        kazu_list.append(ato)
        ato = 0
        switch = 0
        saki = 1
aaaa = [saki, ato]
kazu_list.append(max(aaaa))

ki_list = []
gu_list = []

for i in range(len(kazu_list)):
    if i % 2 == 0:
        gu_list.append(kazu_list[i])
    if i % 2 == 1:
        ki_list.append(kazu_list[i])
#累積和にする
for i in range(len(ki_list)-1):
    ki_list[i+1] = ki_list[i] + ki_list[i+1]
for i in range(len(gu_list)-1):
    gu_list[i+1] = gu_list[i] + gu_list[i+1]

if S[0] == '.':
    ans_list = []
    ki_list.insert(0, 0)
    for i in range(len(ki_list)-1):
        ki = ki_list[len(ki_list)-2-i]
        gu = gu_list[len(gu_list)-1] - gu_list[len(gu_list)-1-i]
        ans_list.append(ki+gu)

if S[0] == '#':
    ans_list = []
    ki_list.insert(0, 0)
    gu_list.insert(0, 0)
    for i in range(len(ki_list)-1):
        ki = ki_list[len(ki_list)-1] - ki_list[len(ki_list)-1-i]
        gu = gu_list[len(gu_list)-1-i]
        ans_list.append(ki+gu)

print(min(ans_list))

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()

#連続する文字の個数数えてリストに入れる
saki = 0
ato = 0
f = S[0]
switch = 0
kazu_list = []
for i in range(N):
    if S[i] == f and switch == 0:
        saki += 1
    
    if S[i] != f and switch == 1:
        ato += 1

    if S[i] != f and switch == 0:
        kazu_list.append(saki)
        saki = 0
        switch = 1
        ato = 1
    
    if S[i] == f and switch == 1:
        kazu_list.append(ato)
        ato = 0
        switch = 0
        saki = 1
aaaa = [saki, ato]
kazu_list.append(max(aaaa))

ki_list = []
gu_list = []

for i in range(N):
    if i % 2 == 0:
        gu_list.append(kazu_list[i])
    if i % 2 == 1:
        ki_list.append(kazu_list[i])
#累積和にする
for i in range(len(ki_list)-1):
    ki_list[i+1] = ki_list[i] + ki_list[i+1]
for i in range(len(gu_list)-1):
    gu_list[i+1] = gu_list[i] + gu_list[i+1]

if S[0] == '.':
    ans_list = []
    ki_list.insert(0, 0)
    for i in range(len(ki_list)-1):
        ki = ki_list[len(ki_list)-2-i]
        gu = gu_list[len(gu_list)-1] - gu_list[len(gu_list)-1-i]
        ans_list.append(ki+gu)

if S[0] == '#':
    ans_list = []
    ki_list.insert(0, 0)
    gu_list.insert(0, 0)
    for i in range(len(ki_list)-1):
        ki = ki_list[len(ki_list)-1] - ki_list[len(ki_list)-1-i]
        gu = gu_list[len(gu_list)-1-i]
        ans_list.append(ki+gu)

print(min(ans_list))

Submission status: Runtime Error

Solution code:
DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)
dp = [[0] * (suma+1) for i in range(N)]
dp[0][0] = 2
dp[0][a[0]] = 1
allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	for j in range(sum(a[:i+1])+1):
		if(j < k):
			dp[i][j] = dp[i-1][j]*2
		else:
			dp[i][j] = dp[i-1][j]*2+dp[i-1][j-k]
allc = allc - sum(dp[N-1][suma-suma/2:])*3
if(suma%2 == 0):
	dp2 = [[0] * (suma+1) for i in range(N)]
	dp2[0][0] = 1
	dp2[0][a[0]] = 1 
	for i in range(1,N):
		k = a[i]
		for j in range(sum(a[:i+1])+1):
			if(j < k):
				dp2[i][j] = dp2[i-1][j]
			else:
				dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-k]
	allc += dp2[N-1][suma/2]*3
print(allc%DIV)

Submission status: Runtime Error

Solution code:
N = int(input())
S =(list(input()))
newS=[]
for i in S:
    if i == ".":
        newS.append(0)
    else:
        newS.append(1)

points10=[]
before=0
for i,s in enumerate(newS):
    if before -s ==1:
        points10.append(i)
    before = s

ans=[]
for i in points10:
    countW=0
    countB=0
    for j,s in enumerate(newS):
        if j<i:
            if s==1:
                countB=countB+1
        else:
            if s==0:
                countW=countW+1
    #print(countW,countB)
    ans.append(countB+countW-1)
#print(ans)
print(min(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

dp = [[0]*(s+1) for _ in range(N)]
# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

for i in range(1,N):
  for j in range(A[i]):
    dp[i][j] = (dp[i-1][j]*2) %mod
  for j in range(A[i], temp_sum+1):
    dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-A[i]]) %mod
  for j in range(temp_sum+1, temp_sum+1 + A[i]):
    dp[i][j] = (dp[i-1][j-A[i]]) %mod
  temp_sum += A[i]


def part_sum(a,A):
  p=mod
  #初期化
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod



print(answer)

Submission status: Runtime Error

Solution code:
from __future__ import print_function
n = int(input())
s = input()

s = s.rstrip('#')
s = s.lstrip('.')

if len(set(s)) <= 1:
    print(0)
    exit(0)

print(min(s.count('#'), s.count('.')))

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(input())
c = 0
d = 0
e = []
st = a[N-1]
f = [st,1]
for i in range(2,N+1):
    if a[N-i] == st:
        f[1] += 1
    else:
        e.append(f)
        st = a[N-i]
        f = [st,1]
e.append(f)
for i in range(len(e) - 1):
    if e[i][0] == ".":
        c += e[i][1]
if e[len(e)-1][0] ==".":
    d += e[len(e-1)][1]
print(min(c,N-c-d))

Submission status: Runtime Error

Solution code:
n = int(input())
ss = input()
flag = True
ans =  0
i = 0
a = 0
black = ss.count('#')
for s in ss:
    if black >= n - black:
        if flag:
            if s == '#':
                flag = False
        else:
            if s == '.':
                ans += 1
    else:
        if s == '#':
            ans += 1
        if flag:
            if ss[n-i] == '.':
                a = i
                flag = False
        i += 1
print(ans if ss[n-i] == '#' else ans-a)

Submission status: Runtime Error

Solution code:
import math
import re
n = int(raw_input())
s = raw_input()

prev = ''
ar = []
for i in s:
    if prev == '' or prev[0] == i:
        prev += i
    else:
        ar.append(prev)
        prev = i

ar.append(prev)

cnt = 0
if ar[-1].count('#') > 0:
    ar.pop(-1)
if ar[0].count('.') > 0:
    ar.pop(0)
while True:
    if len(ar) < 2:
        break
    last = ar[-1]
    last2 = ar[-2]
    if len(last2) >= len(last):
        cnt += len(last)
        ar.pop(-2)
        ar.pop(-1)
    else:
        break

new_s = ''.join(ar)

a = new_s.count('#')
b = new_s.count('.')

cnt += min(a,b)
print cnt

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 998244353  # type: int

def solve(N: int, a: "List[int]"):
    s = sum(a)
    dp = [[[0] * 2 for _ in range(s + 1)] for _ in range(N + 1)] # dp[idx][sum][]
    dp[0][0][0] = 1
    dp[0][0][1] = 1
    for i in range(N):
        for j in range(s + 1 - a[i]):
            dp[i + 1][j + a[i]][0] += dp[i][j][0]
            dp[i + 1][j + a[i]][1] += dp[i][j][1]
            dp[i + 1][j][0] += dp[i][j][0]
            dp[i + 1][j][1] += dp[i][j][1] * 2

    tmp = 0
    border = (s + 1) // 2
    uniq = 0
    #pprint(dp)
    for j in range(border, s + 1):
        tmp += dp[N][j][1]
        uniq += dp[N][j][0]
    #print(tmp, uniq)
    tmp -= uniq * 2
    tmp *= 3

    ret = (3 ** N) % MOD
    col_2 = (2 ** N) % MOD
    ret -= 3 + (col_2 - 2) * 3 + 3
    #print(ret)
    #for i in range(N):
    #    ret *= 3
    #    ret %= MOD
    #    col_2 *= 2
    #    col_2 %= MOD
    ret -= tmp
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
d = S.count(".")
s = S.count("#")
m = -1
if s == 1 and S[N - 1] == "#":
    l = 0
else:
    if S[0] == ".":
        for i in range(d):
            if S[i] == ".":
                if m != 1:
                    l = 0
                    m = 0
            else:
                m = 1
    if m != 0:
        if s < d:
            if S[0] == ".":
                l = s
            else:
                l = d
        elif d < s:
            if S[0] == ".":
                l = d - 1
            else:
                l = d
        if l < 0:
            l = 0
print(l)

Submission status: Runtime Error

Solution code:
import sys
import numpy
from collections import Counter

def calc(N,S):
    if '#' not in S or '.' not in S:
        return 0
    i =0
    for x in S:
        if x == '#':
            F = S[i:]
            cnt = Counter(F)
            if len(cnt.keys())>1:
                return min(.values())
            else:
                return 0
        i+=1

if __name__ == '__main__':
    N = input()
    S = input()
    print(calc(N,S))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

N = stdin.readline().rstrip()
S = stdin.readline().rstrip()

# print(S)
S = list(S)
count = 0
flag = False
for idx, char in enumerate(S):
    if flag == True:
        flag += 1
        continue
    if char == '#':
        S[idx + 1] = '.'
        count += 1
    flag += 1

print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

aaa = [int(input()) for _ in range(N)]
sum_aaa = sum(aaa)

sum_now = 0
DP = [[0] * (sum_aaa+1) for i in range(N)]
DP2 = [[0] * (sum_aaa+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 1):

		if (j >= a):
			DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-a]
		else:
			DP[i][j] = DP[i-1][j]*2

		while (DP[i][j] > mod):
			DP[i][j] -= mod

	for j in range(min(sum_now + 1, int(sum_aaa /2)+1)):
		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

		while (DP2[i][j] > mod):
			DP2[i][j] -= mod

# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum_aaa %2 == 0):
	num_too_long -= DP2[N-1][int(sum_aaa /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )

Submission status: Runtime Error

Solution code:
N = input()
S = input()
 
count = 0
black = 0
white = 0
for i in range(int(N)):
    if(S[i] == "#"): 
        black += 1
    elif(S[i] == "."): 
        white += 1
 
if(white < black):
    for i in range(int(N)-1):
        if(S[i] == "#" and S[i+1] == "."): 
            S[i+1] = "#"
            count += 1
    for j in range(int(N)-1):
        if(S[j] == "#" and S[j+1] == "."): 
            S[j+1] = "#"
            count += 1
    for k in range(int(N)-1):
        if(S[k] == "#" and S[k+1] == "."): 
            count += 1   
else:    
    for i in range(int(N)-1):
        if(S[i] == "#" and S[i+1] == "."): 
            S[i] = "."
            count += 1
    for j in range(int(N)-1):
        if(S[j] == "#" and S[j+1] == "."): 
            S[j] = "."
            count += 1
    for k in range(int(N)-1):
        if(S[k] == "#" and S[k+1] == "."): 
            count += 1    
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
x = s.count("#")
lst = [s[:i].count("#")+s[i+1:].count(".") for i in range(n) if (s[i]=="#")]
x = min(x,min(lst))
print(x)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
d = S.count(".")
s = S.count("#")
m = 1
if s == 1 and S[N - 1] == "#":
    l = 0
else:
    if S[0] == ".":
        for i in range(d):
            if S[i] != ".":
                m = 1
            else:
                if m != 1:
                    l = 0
                    m = 0
    if m:
        if s < d:
            if S[0] == ".":
                l = s
            else:
                l = d
        elif d < s:
            if S[0] == ".":
                l = d - 1
            else:
                l = d
        if l < 0:
            l = 0
print(l)

Submission status: Runtime Error

Solution code:
N = input()
S = input()
 
count = 0
black = 0
white = 0
for i in range(int(N)):
    if(S[i] == "#"): 
        black += 1
    elif(S[i] == "."): 
        white += 1
 
if(white > black):
    for i in range(int(N)-1):
        if(S[i] == "#" and S[i+1] == "."): 
            S[i+1] = "#"
            count += 1
    for j in range(int(N)-1):
        if(S[j] == "#" and S[j+1] == "."): 
            S[j+1] = "#"
            count += 1
    for k in range(int(N)-1):
        if(S[k] == "#" and S[k+1] == "."): 
            count += 1   
else:    
    for i in range(int(N)):
        if(S[i] == "#" and S[i+1] == "."): 
            S[i] = "."
            count += 1
    for j in range(int(N)):
        if(S[j] == "#" and S[j+1] == "."): 
            S[j] = "."
            count += 1
    for k in range(int(N)):
        if(S[k] == "#" and S[k+1] == "."): 
            count += 1    
print(count)

Submission status: Runtime Error

Solution code:
N = input()
S = input()
 
count = 0
black = 0
white = 0
for i in range(int(N)):
    if(S[i] == "#"): 
        black += 1
    elif(S[i] == "."): 
        white += 1
 
if(white > black):
    for i in range(int(N)-1):
        if(S[i] == "#" and S[i+1] == "."): 
            S[i+1] = "#"
            count += 1
    for j in range(int(N)-1):
        if(S[j] == "#" and S[j+1] == "."): 
            S[j+1] = "#"
            count += 1
    for k in range(int(N)-1):
        if(S[k] == "#" and S[k+1] == "."): 
            count += 1   
else:    
    for i in range(int(N)-1):
        if(S[i] == "#" and S[i+1] == "."): 
            S[i] = "."
            count += 1
    for j in range(int(N)-1):
        if(S[j] == "#" and S[j+1] == "."): 
            S[j] = "."
            count += 1
    for k in range(int(N)-1):
        if(S[k] == "#" and S[k+1] == "."): 
            count += 1    
print(count)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
	while a > 0 and b > 0:
		a, b = b, a % b
	return a + b

def st(a, b):
	if b == 0:
		return 1
	if b % 2 == 0:
		q = st(a, b // 2)
		return q * q
	return a * st(a, b - 1)

n = int(input())
a = []
for i in range(n + 1):
	x = int(input())
	a.append(x)
ans = 0
for x in range(1, 32):
	tmp = 0
	r = st(x, n)
	for i in range(0, n + 1):
		tmp += a[i] * r
		r //= x
	ans = gcd(ans, abs(tmp))
v = []
j = 2
while j * j <= ans:
	if ans % j == 0:
		ans //= j
		v.append(j)
	else:
		j += 1
if ans != 1:
	v.append(ans)
v.sort()
for i in range(len(v)):
	if i == 0 or v[i] != v[i - 1]:
		print(v[i])

Submission status: Runtime Error

Solution code:
import math
import re
n = int(raw_input())
s = raw_input()

prev = ''
ar = []
for i in s:
    if prev == '' or prev[0] == i:
        prev += i
    else:
        ar.append(prev)
        prev = i

ar.append(prev)

cnt = 0
if ar[-1].count('#') > 0:
    ar.pop(-1)
if ar[0].count('.') > 0:
    ar.pop(0)
while True:
    if len(ar) < 2:
        break
    last = ar[-1]
    last2 = ar[-2]
    if len(last2) >= len(last):
        cnt += len(last)
        ar.pop(-1)
        ar.pop(-1)
    else:
        break

new_s = ''.join(ar)

a = new_s.count('#')
b = new_s.count('.')

cnt += min(a,b)
print cnt

Submission status: Runtime Error

Solution code:
N = input()
S = input()
 
count = 0
for i in range(int(N)-1):
    if(S[i] == "#" and S[i+1] == "."): 
        S[i] = "."
        count += 1
for j in range(int(N)-1):
    if(S[j] == "#" and S[j+1] == "."): 
        S[j] = "."
        count += 1
for k in range(int(N)-1):
    if(S[k] == "#" and S[k+1] == "."): 
        count += 1
 
print(count-1)

Submission status: Runtime Error

Solution code:
N = input()
S = input()
 
count = 0
for i in range(int(N)-1):
    if(S[i] == "#" and S[i+1] == "."): 
        S[i] = "."
        count += 1
for j in range(int(N)-1):
    if(S[j] == "#" and S[j+1] == "."): 
        S[j] = "."
        count += 1
for m in range(int(N)-1):
    if(S[m] == "#" and S[m+1] == "."): 
        S[m] = "."
        count += 1
for n in range(int(N)-1):
    if(S[n] == "#" and S[n+1] == "."): 
        S[n] = "."
        count += 1
for k in range(int(N)-1):
    if(S[k] == "#" and S[k+1] == "."): 
        count += 1
 
print(count)