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:
N = input()
S = raw_input()


def calc_func(_l, _r):
    nl = S.find('#', _l, _r)
    nr = S.rfind('.', _l, _r)
    if nl < 0 or nr < 0 or nr < nl:
        return 0
    elif S.find('#', nl, nr) < 0 or S.find('.', nl, nr) < 0:
        return 1
    else:
        return 2 + calc_func(nl + 1, nr - 1)


print(calc_func(0, N))

Submission status: Runtime Error

Solution code:
import sys
import numpy
from collections import Counter

def calc(N,S):
    i =0
    for x in S:
        if x == '#':
            F = S[i:]
        i+=0
    print(min(Counter(F).values()))

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

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)

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

 
print(count)

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
for idx, char in enumerate(S):
    if char == '#':
        S[idx + 1] = '.'
        count += 1

# result = ''.join(S)
# print(result)
print(count)

Submission status: Runtime Error

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

 
print(count)

Submission status: Runtime Error

Solution code:
N = input()
S = input()
 
count = 0
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
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] == "."): 
        count += 1

print(count)

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)
for idx, char in enumerate(S):
    if char == '#':
        S[idx + 1] = '.'

result = ''.join(S)
print(result)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys, collections, bisect, math, itertools
from fractions import gcd 
#input = sys.stdin.readline #文字列入力のときは注意

m = int(input())
#s = input()
#a = [int(i) for i in input().split()]
a = [int(input()) for j in range(m+1)] # 縦「n」行

beki = 0
while a[-1] == 0:
    a.pop()
    beki+=1
if m != len(a)-1:
    m = len(a)
    a.append(0)


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
allprimes = get_sieve_of_eratosthenes(10010)

primes=[]
def get_sieve_of_eratosthenes2():
    prime = []
    data = [i + 1 for i in range(1, 35000)]
    c=abs(a[m])
    while True:
        p = data[0]
        if 35000 <= p*p:
            return prime + data
        if c%p==0: primes.append(p)
        prime.append(p)
        data = [e for e in data if e % p != 0]

primes2=[]
def get_sieve_of_eratosthenes3():
    prime = []
    data = [i + 1 for i in range(1, 35000)]
    c=abs(a[0])
    while True:
        p = data[0]
        if 35000 <= p*p:
            return prime + data
        if c%p==0: primes2.append(p)
        prime.append(p)
        data = [e for e in data if e % p != 0]


get_sieve_of_eratosthenes2()
#print(primes)
if len(primes) == 0 and abs(a[m]) != 1:
    primes.append(abs(a[m]))
if len(primes2) == 0 and abs(a[0]) != 1:
    primes2.append(abs(a[0]))
n=m
if a[m]==0:
    primes = allprimes


primes = primes + primes2
#print(a)
#print(primes)
for p in primes:
    if p > 10**4+5:
        if sum([i%p for i in a]) == 0:
            print(p)
        continue
    coeff = list(reversed(a))
    while len(coeff) > p:
#        print(coeff,p)
        t=coeff.pop()
        coeff[-p+1]+=t
            
#    print(coeff)
    if sum([i%p for i in coeff]) == 0:
        print(p)

Submission status: Runtime Error

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

print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = input()
S = input()
 
count = 0

for i in range(N):
    if(S[i] == "#" and S[i+1] == "."): 
        S[i] = "."
        count += 1
print(count)

Submission status: Runtime Error

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

print(count)

Submission status: Runtime Error

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


def calc_func(_l, _r):
    nl = S.find('#', _l, _r)
    nr = S.rfind('.', _l, _r)
    if nl < 0 or nr < 0 or nr < nl:
        return 0
    else:
        return min(1 + calc_func(nl + 1, _r), 1 + calc_func(_l, nr - 1))


print(calc_func(0, N))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())

Nums = []
now = "#"#今見てる数(１を見て判定していくために最初を１として判定を始める)
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        if now == ".":
            now = "#"
        else:
            now = "."
        cnt = 1
if cnt != 0:Nums.append(cnt)
ans = 0
i = 0
flag = False
Nums = Nums +[0] * (n-len(Nums))
if len(Nums) == 1:
    print(0)
    exit()
while i < len(Nums):
    if Nums[i] != 0 and flag == False:
        i += 1
        ans = 0
        flag = True
    ans += Nums[i]
    i += 2

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())

Nums = []
now = "#"#今見てる数(１を見て判定していくために最初を１として判定を始める)
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        if now == ".":
            now = "#"
        else:
            now = "."
        cnt = 1
if cnt != 0:Nums.append(cnt)
ans = 0
i = 0
flag = False
Nums = Nums +[0] * (n-len(Nums))
if len(Nums) == 1:
    print(0)
    exit()
while i < len(Nums):
    if Nums[i] != 0 and flag == False:
        i += 1
        ans = 0
        flag = True
    ans += Nums[i]
    i += 2

print(s,Nums,ans)

Submission status: Runtime Error

Solution code:
# read = input
n = int(read())
s = read()
SW = [0 for i in range(n)]
SB = [0 for i in range(n)]
for i,c in enumerate(s):
    if i == 0:
        SW[i] = 1 if c == '.' else 0
        SB[i] = 1 if c == '#' else 0
    else :
        SW[i] = SW[i-1] + 1 if c == '.' else SW[i-1]
        SB[i] = SB[i-1] + 1 if c == '#' else SB[i-1]
cost = n
for i in range(n):
    pass
#     print(i, SW[i], SB[i])
for i in range(n + 1):
    startW = 0
    endW = i # left W is [0,i)
    startB = i 
    endB = n # right B is [i, n)
#     print(i)
    if i == 0: # all B 
        cost = min(cost, n - SW[n-1])
    elif i == n: # all W
        cost = min(cost, n - SB[n-1])
    else:
        cost = min(cost, 
                   i - SB[i-1] + (n-i) - (SB[n-1] - SB[i-1])
                  )
print(cost)

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):
    print(black)    
else:    
    for i in range(int(N)):
        if(S[i] == "#" and S[i+1] == "."): 
            count += 1    
print(count)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

d2 = [1]
tmp = 1
for i in range(n):
    tmp = tmp * 2 % MOD
    d2.append(tmp)

s = sum(aaa)
dp = [defaultdict(lambda: 0) for _ in [0] * (s + 1)]
dp[0][0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dd = dp[i]
        if not dd:
            continue
        for k, p in dd.items():
            dp[i + a][k + 1] += p
    tmp_sum += a

ans = pow(3, n, MOD)
sub = 0
h = (s + 1) // 2
for dd in dp[h:]:
    for k, p in dd.items():
        sub += d2[n - k] * p * 3
    sub %= MOD
if s % 2 == 0:
    dd = dp[h]
    for k, p in dd.items():
        sub -= p * 3

ans = (ans - sub) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()

c = s.count('.')
if n == s:
  print(n)
elif n>s: 
  print(s)
elif n<s:
  print(n)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()

def trim(n, s):
    i = 0
    while i < n and s[i] == '.':
        i += 1
    start = i

    i = n
    while i > 0 and s[i - 1] == '#':
        i -= 1
    end = i

    return s[start:end]


def f(n, s):
    bs = 0
    ws = 0

    for c in s:
        if c == '#':
            bs += 1
        else:
            ws += 1
    return min(ws, bs)


def g(n, s):
    bs = 0
    ws = 0
    i = 0
    while i < n:
        if s[i] == '#':
            bs += 1
        else:
            break
        i += 1

    i = len(s)
    while i > 0:
        if s[i - 1] == '.':
            ws += 1
        else:
            break
        i -= 1

    return bs + ws

s = trim(n, s)
print(min(f(n, s), g(n, s)))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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


indices_black = list()
for i, c in enumerate(S):
    if c == '#':
        indices_black.append(i)

count_white = dict()
count = 0
for i, c in enumerate(S[::-1]):
    if c == '.':
        count += 1
    count_white[N - i - 1] = count


def get_answer(S):
    # most left
    if len(indices_black) == 0:
        return 0

    idx = indices_black.pop(0)
    if count_white[idx] == 0:
        return 0
    # count white: turn all white -> black
    ans_w = count_white[idx]

    # turn most left black -> white
    S[idx] = '.'
    ans_b = get_answer(S) + 1
    return min(ans_w, ans_b)


print(get_answer(S))

Submission status: Runtime Error

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

ans = 0
T1 = S.copy()
f = False
for i in range(N):
    s = T1[i]
    if s == ".":
        continue
    else:
        if i < N - 1 and T1[i+1] == ".":
            if not f and i + 1 < N - 1 and T1[i+2] == ".":
                ans += 1
            else:
                f = True
                T1[i+1] = "#"
                ans += 1
        else:
            f = True
ans2 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        continue
    else:
        ans2 += 1

ans3 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        ans3 += 1
    else:
        continue

while S[-1] != ".":
    S.pop()
N = len(S)
ans4 = 0
for i in range(N):
    s = S[i]
    if s == ".":
        continue
    else:
        ans4 += 1

# print(ans, ans2, ans3)
print(min(ans2, ans, ans3, ans4))

Submission status: Runtime Error

Solution code:
b_tot, w_tot = 0, 0
for s in S:
    if s == '.':
        w_tot += 1
    else:
        b_tot += 1
b_left, w_left = 0, 0
tmp = 3 * 10**5
for s in S:
    if s == '.':
        w_left += 1
    else:
        b_left += 1
    tmp = min(tmp, b_left + w_tot - w_left)
print(tmp)

Submission status: Runtime Error

Solution code:
mport re


def main():
    n = int(input())
    s = input()

    count = 0

    for _ in range(n):

        relst = re.findall(r"#\.", s)

        if not len(relst):
            break

        count += len(relst)

        s = s.replace("#.", "..")

    print(count)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy


    
if __name__ == '__main__':
    tmp = input()
    H,W,K = tmp.split()
    main5(int(H)+1,int(W)+1,int(K))

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())

Nums = []
now = "#"#今見てる数(１を見て判定していくために最初を１として判定を始める)
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        if now == ".":
            now = "#"
        else:
            now = "."
        cnt = 1#新しいのをカウントし始める
if cnt != 0:Nums.append(cnt)
ans = 0
for i in range(1,len(Nums),2):
    ans += Nums[i]
if Nums[0] == len(s):
    ans = 0
elif len(s) == Nums[1] or Nums[1] == len(s) - Nums[2]:
    ans = 0
print(ans)

Submission status: Runtime Error

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

while S[-1] != ".":
    S.pop()
N = len(S)

if N == 0:
    print(0)

ans = 0
T1 = S.copy()
f = False
for i in range(N):
    s = T1[i]
    if s == ".":
        continue
    else:
        if i < N - 1 and T1[i+1] == ".":
            if not f and i + 1 < N - 1 and T1[i+2] == ".":
                ans += 1
            else:
                f = True
                T1[i+1] = "#"
                ans += 1
        else:
            f = True
ans2 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        continue
    else:
        ans2 += 1

ans3 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        ans3 += 1
    else:
        continue
print(min(ans2, ans, ans3))

Submission status: Runtime Error

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

count = 0
for i in range(N):
    if(S[i] == "#" and S[i+1] == "."): 
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())

Nums = []
now = "#"#今見てる数(１を見て判定していくために最初を１として判定を始める)
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        if now == ".":
            now = "#"
        else:
            now = "."
        cnt = 1#新しいのをカウントし始める
if cnt != 0:Nums.append(cnt)
ans = 0
for i in range(1,len(Nums),2):
    ans += 1
if Nums[0] == len(s):
    ans = 0
elif len(s) == Nums[1] or Nums[1] == len(s) - Nums[2]:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
black_flag = False
white = False
counter = 0
for item in s:
    if item == "#":
        black_flag = True
        continue
    if black_flag:
        if item == '.':
            counter += 1
            white = True
        if white and item == '#':
            black_flag = 0
print(counter)

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
i=S.index(".")
if i==0:
    print(0)
else:
    print(S.count("."))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	string s; cin >> s;
	int b = 0;
	int w = 0;
	for( char c : s ){
		if( c == '.' ) ++w;
	}
	int ans = min(INF, b+w);
	for( char c : s ){
		if( c == '.' ) --w;
		if( c == '#' ) ++b;
		cout << b+w << endl;
		ans = min(ans, b+w);
	}
	cout << ans << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
def main():
    n=int(input())
    s=input()
    if '.' not in s or '#' not in s:
        print(0)
        return
    j = s.index('.')
    a = len([i for i in s[j:] if i == '#'])
    j = n - s[:-1].index('.')
    b = len([i for i in s[:j] if i == '#'])
    print(min([a, b]))

main()

Submission status: Runtime Error

Solution code:
n=int(input())
s=list(input())
li=[0]
ans=n
for i in s:
    li+=[li[-1]+1] if i=='#' else [li[-1]]
b=li[-1]
for i in range(n+1):
    temp=li[i]+n-i-b+li[i]
    ans=min(ans,temp)
print(ans)n

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())

Nums = []
now = "#"#今見てる数(１を見て判定していくために最初を１として判定を始める)
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        if now == ".":
            now = "#"
        else:
            now = "."
        cnt = 1#新しいのをカウントし始める
if cnt != 0:Nums.append(cnt)
ans = 0
for i in range(1,len(Nums),2):
    ans += 1
if len(s) == Nums[1]:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
text = input()
pos = text.index(".")
result = 0
for i in range(pos+1, len(text)):
    if text[i] == '#':
        result += 1

print(result)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    b = s.copy()
    ans = 0
    for i in range(n-1):
        if s[i] == "#" and s[i+1] == ".":
            ans += 1
            s[i+1] = "#"
    m = 0
    for i in range(n-1)[::-1]:
        if b[i] == "#" and b[i+1] == ".":
            m += 1
            b[i] = "."
    print(min(m,ans))
    return

#D
def D():
    n = I()
    a = IR(n)

    return

#E
def E():
    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    C()