Problem:


Score : 300 points

Problem Statement

Given is a string S. Let T be the concatenation of K copies of S.
We can repeatedly perform the following operation: choose a character in T and replace it with a different character.
Find the minimum number of operations required to satisfy the following condition: any two adjacent characters in T are different.

Constraints

1 \leq |S| \leq 100

S consists of lowercase English letters.

1 \leq K \leq 10^9

K is an integer.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the minimum number of operations required.

Sample Input 1

issii
2

Sample Output 1

4

T is issiiissii.  For example, we can rewrite it into ispiqisyhi, and now any two adjacent characters are different.

Sample Input 2

qq
81

Sample Output 2

81

Sample Input 3

cooooooooonteeeeeeeeeest
999993333

Sample Output 3

8999939997



Sample input:
issii
2


Sample output:
4

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# agc039/agc039_a
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    S = i2s()
    K = i2n()
    ps = S[0]
    cnt = 0
    s_n = []
    for s in S:
        if ps == s:
            cnt += 1
        else:
            s_n.append(cnt)
            cnt = 1
            ps = s
    s_n.append(cnt)
    if len(s_n) == 1:
        print((s_n[0] * K) // 2)
        return
    sum_n = sum((x//2 for x in s_n[1:-1])) * K
    if S[0] == S[-1]:
        sum_n += (s_n[0] // 2 + s_n[-1] // 2)
        sum_n += ((s_n[0] + s_n[-1]) // 2) * (K-1)
    else:
        sum_n += (s_n[0] // 2 + s_n[-1] // 2) * K
    print(sum_n)
    return

main()

Submission status: Accepted

Solution code:
def main():
    s = input()
    k = int(input())
    s_ = []
    f = False
    for i in range(len(s)):
        if not s_:
            s_.append(s[i])
        elif not s_[-1][0] == s[i]:
            s_.append(s[i])
        else:
            s_[-1] += s[i]
    if s_[0][0] == s_[-1][0]:
        if len(s_) > 1:
            if len(s_[0])%2 == 1 and len(s_[-1])%2==1:
                f = True
            s_[0] = s_[0] + s_[-1]
            s_ = s_[:-1] 
    ans = 0
    if len(s_) == 1 and len(s_[0])%2==1:
        l = len(s_[0])
        if k%2==0:
            ans = l*k//2
        else:
            ans = l*(k-1)//2+l//2
        print(ans)
    else:
        for i in s_:
            ans += len(i)//2
        ans *= k
        if f == True and not len(s_) == 1:
          ans -= 1
        print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
k = int(input())
flg = 1
for i in range(n - 1):
    if s[i] != s[i + 1]:
        flg = 0
if flg:
    print(n * k // 2)
    exit(0)
t = s + s
tmp1 = 0
for i in range(n * 2 - 1):
    if t[i] == t[i + 1]:
        tmp1 += 1
        t[i + 1] = 'X'
tmp2 = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        tmp2 += 1
        s[i + 1] = 'X'
tmp3 = tmp1 - tmp2 * 2
print(tmp3 * (k - 1) + tmp2 * k)

Submission status: Accepted

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

sameword = [1]
for i in range(1, len(s)):
  if s[i] == s[i-1]:
    sameword[-1] += 1
  else:
    sameword.append(1)  
    
if len(sameword) == 1:
  print((sameword[0] * k) // 2) 
elif s[0] != s[-1]:
  change = 0    
  for seq in sameword:
    change += seq // 2
  print(change * k)
else:
  init = sameword[0]
  last = sameword[-1]
  change = 0
  for i in range(1, len(sameword)-1):
    change += sameword[i] // 2
  print(change * k + (init // 2) + (last // 2) + ((init + last) // 2) * (k - 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    K = II()
    N = len(S)

    same_cnt = 0
    for c in S:
        if c == S[0]:
            same_cnt += 1

    if same_cnt == N:
        print((N*K)//2)
        return

    chunks = []
    prev = ''
    chunk_len = 0
    in_chunk = False
    for i, c in enumerate(S):
        dprint(c, in_chunk, prev, c)
        if prev == c:
            if in_chunk:
                chunk_len += 1
            else:
                chunk_len = 2
                chunk_start = i-1
                in_chunk = True
        else:
            if in_chunk:
                in_chunk = False
                chunks.append((chunk_start, chunk_len))
        prev = c

    if in_chunk:
        chunks.append((chunk_start, chunk_len))

    # start end chunk
    if S[0] == S[N-1]:
        start_chunk_head = chunks[0][0]
        end_chunk_tail = chunks[len(chunks)-1][0] + chunks[len(chunks)-1][1] - 1
        start_n, end_n = 1, 1
        start_chunk_i = 0
        cnt_for_end_chunk = 0
        cnt_for_start_chunk = 0
        end_chunk_i = len(chunks) - 1
        if start_chunk_head == 0:
            start_n = chunks[0][1]
            start_chunk_i = 1
            cnt_for_start_chunk = start_n // 2
        if end_chunk_tail == N-1:
            end_n = chunks[len(chunks)-1][1]
            end_chunk_i = len(chunks) - 2
            cnt_for_end_chunk = end_n // 2

        start_end_chunk_n = start_n + end_n

        dprint(chunks, start_n, end_n, start_end_chunk_n)
        dprint(start_chunk_i, end_chunk_i)
        cnt = 0
        for chead, clen in chunks[start_chunk_i:end_chunk_i+1]:
            cnt += clen //2
        dprint(cnt)
        cnt = cnt*K + start_end_chunk_n//2 * (K-1) + cnt_for_end_chunk + cnt_for_start_chunk

        print(cnt)
        return


    else:
        cnt = 0
        for chead, clen in chunks:
            cnt += clen //2
        print(cnt * K)
        return


solve()

Submission status: Accepted

Solution code:
import sys

s = input()
k = int(input())

onaji = 1
before = s[0]
for i in range(len(s)):
    now = s[i]
    if now != before:
        onaji = 0

if onaji == 1:
    print((len(s)*k)//2)
    sys.exit()

s_2 = s + s

num_first = 0
renzoku = 1
before = 0
for i in range(len(s)):
    now = s[i]
    if now == before:
        renzoku += 1
    else:
        num_first += renzoku // 2
        renzoku = 1
    before = now
num_first += renzoku // 2

num_rest = 0
renzoku = 1
before = 0
for i in range(len(s_2)):
    now = s_2[i]
    if now == before:
        renzoku += 1
    else:
        num_rest += renzoku // 2
        renzoku = 1
    before = now
num_rest += renzoku // 2

num_rest -= num_first

print(num_first + (k-1) * num_rest)

Submission status: Accepted

Solution code:
s=input()
k=int(input())
if len(set(s))==1:
  print(len(s)*k//2)
else:
  cnt=1
  s_ans=0
  x=s[0]
  for a in s[1:]:
    if a==x:
      cnt+=1
    else:
      s_ans+=cnt//2
      x=a
      cnt=1
  s_ans+=cnt//2
  if s[0]!=s[-1]:
    print(s_ans*k)
  else:
    ss=s*2
    cnt=1
    ss_ans=0
    x=ss[0]
    for a in ss[1:]:
      if a==x:
        cnt+=1
      else:
        ss_ans+=cnt//2
        x=a
        cnt=1
    ss_ans+=cnt//2
    print(s_ans*k+(ss_ans-s_ans*2)*(k-1))

Submission status: Accepted

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

ck=0
ne=True

if len(set(s))==1:
    print((len(s)*k)//2)
    ne=False
elif s[0]==s[-1]:
    for i in range(len(s)):
       if s[i] != s[0]:
           s=s[i:]+s[:i]
           ck=i
           break

if ne:    
    #print(s)
    ans=0
    
    M=[]
    now=s[0]
    cnt=1
    for c in s[1:]:
        if c==now:
            cnt+=1
        else:
            M.append(cnt)
            #print(M)
            ans+=cnt//2
            cnt=1
            now=c
            
    M.append(cnt)
    ans+=cnt//2
    #print(M)
    
    ans=ans*k
    
    #print(ans)
    
    if ck>0:
       for i in range(1,len(s)):
           if s[-i] != s[-1]:
               ck2=i-1
               break
       ans-=ck2//2
       ans+=(ck2-ck)//2+ck//2
    
    print(ans)

Submission status: Accepted

Solution code:
s = input()
k = int(input())
l = len(s)
s = s * 3
dp = [0,0]
check = []
for i in range(3*l-1):
  if s[i+1] != s[i]:
    dp.append(dp[-1])
  else:
    dp.append(dp[-2]+1)
  if (i+2) % l == 0:
    check.append(dp[-1])
if l == 1:
  ans =  k // 2
elif k % 2 == 0:
  ans = check[1] + (k-2) // 2 * (check[2]-check[0])
else:
  ans = check[0] + (k-1) // 2 * (check[2]-check[0])
print(ans)

Submission status: Accepted

Solution code:
s=input()
k=int(input())
if len(s)==1:
  print(k//2)
else:
  ans=0
  chg=0
  for i in range(1,len(s)):
    if chg==0 and s[i-1]==s[i]:
      ans+=1
      chg=1
    else:
      chg=0
  ans2=1
  chg2=1
  for i in range(1,len(s)):
    if chg2==0 and s[i-1]==s[i]:
      ans2+=1
      chg2=1
    else:
      chg2=0
  if s[0]!=s[-1] or chg==1:
    print(k*ans)
  elif chg2==0:
    print((k-1)*ans2+ans)
  else:
    print(ans*((k+1)//2)+ans2*(k//2))

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    s=input()
    k=int(input())
    ans=0
    n=[len(list(v)) for k,v in groupby(s)]
#    print(x)
    if s[0]!=s[-1]:
        y=[len(list(v))//2 for k,v in groupby(s)]
        print(sum(y)*k)
    else:
        x=[len(list(v))//2 for k,v in groupby(s)]
#        print(x)
        if len(x)!=1:
            ans+=x[0]+x[-1]
#            print(ans)
            ans+=sum(x[1:-1])*k
#            print(ans)
            ans+=(k-1)*((n[0]+n[-1])//2)
            print(ans)
        else:
            print(len(s)*k//2)
        
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


S = input()
K = int(input())

pre = None
if K < 10:
    first_cnt = 0
    for s in S*K:
        if s == pre:
            first_cnt += 1
            pre = None
        else:
            pre = s
    print(first_cnt)
    exit()

pre = S[0]
first_cnt = 0

for s in S[1:]:
    if s == pre:
        first_cnt += 1
        pre = None
    else:
        pre = s

continuous_cnt = 0
for s in S:
    if s == pre:
        continuous_cnt += 1
        pre = None
    else:
        pre = s

continuous_cnt2 = 0
for s in S:
    if s == pre:
        continuous_cnt2 += 1
        pre = None
    else:
        pre = s

if continuous_cnt == continuous_cnt2:
    print(first_cnt+continuous_cnt*(K-1))
elif K % 2 == 1:
    print(first_cnt+(continuous_cnt+continuous_cnt2)*((K-1)//2))
else:
    print(first_cnt+continuous_cnt*((K-1)//2+1)+continuous_cnt2*((K-1)//2))
    # print(first_cnt, ((K-1)//2))

Submission status: Accepted

Solution code:
S = input()
K = int(input())
all_same = False
for i, (s, t) in enumerate(zip(S, S[1:])):
    if s != t:
        break
else:
    all_same = True

if all_same:
    ans = (K * len(S)) // 2
else:
    first, last = 0, 0
    if S[0] == S[-1]:
        for j, t in enumerate(reversed(S)):
            if t != S[0]: break
        first, last = i+1, j
        S = S[i+1:-j]        
    seq = []
    temp = 1
    for s, t in zip(S, S[1:]):
        if s == t: temp += 1
        else:
            if temp != 1: seq.append(temp)
            temp = 1
    if temp != 0:
        seq.append(temp)
    ans = first // 2 + last // 2 + ((first + last)//2) * (K-1)
    for se in seq:
        ans += (se // 2) * K
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

s = input()
k = int(input())
n = len(s)

if n > 1:
    a = [len(list(g)) for _, g in groupby(s)]

    if len(a) == 1:
        print(n * k // 2)
    else:
        answer = sum([i // 2 for i in a]) * k

        if s[0] == s[-1] and a[0] % 2 == 1 and a[-1] % 2 == 1:
            answer += k - 1            

        print(answer)
else:
    print(k // 2)

Submission status: Accepted

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

change = []
tmp = 1
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        tmp += 1
    else:
        change.append(tmp)
        tmp = 1
change.append(tmp)

#print(change)

ret = 0
if len(change) >= 3:

    for i in range(1, len(change) - 1):
        ret += change[i] // 2 * k
    
    if s[0] == s[-1]:
        ret += (change[0] + change[-1]) // 2 * (k - 1) + change[0] // 2 + change[-1] // 2
    else:
        ret += (change[0] // 2 + change[-1] // 2) * k
elif len(change) == 2:
    ret = (change[0] // 2 + change[1] // 2) * k
else:
    ret = change[0] * k // 2

print(ret)

Submission status: Accepted

Solution code:
s = list(str(input()))
k = int(input())

s_pre = s[0]
cnt = 1
s2 = []
for x in s[1:]:
    if s_pre == x:
        cnt += 1
    else:
        s2 += [cnt]
        cnt = 1
        s_pre = x
s2 += [cnt]

def div2(x):
    return x//2

if len(s2) == 1:
    print((s2[0]*k)//2)

elif s[0] == s[-1]:
    print(s2[0]//2 + s2[-1]//2 + (s2[0]+s2[-1])//2*(k-1) + sum(map(div2, s2[1:-1]))*k)

else:
    print(sum(map(div2, s2))*k)

Submission status: Accepted

Solution code:
import math
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
K = I()
N = len(s)

start = s[0]
left = 0
right = 0
f = 0
for i in range(N):
  if f == 0:
    if s[i] == start:
      left = i
    else:
      f = 1
if f == 0:
  ans = N*K//2
  print(ans)
else:
  if s[0] == s[-1]:
    f = 0
    for i in range(N-1,-1,-1):
      if f == 0:
        if s[i] == start:
          right = i
        else:
          f = 1
    left = left +1

    #print(left)
    #print(right)
    #print(((left + (N-right))//2)*(K-1))
    ans = ((left + (N-right))//2)*(K-1) + left//2  + (N-right)//2
  else:
    ans = 0
    left = 0
    right = N
  tmp = 0
  t = ""
  for i in range(left,right):
    if t == s[i]:
      tmp += 1
    else:
      t = s[i]
      tmp = 1
    if tmp%2 == 0:
      ans += K
  print(ans)

Submission status: Accepted

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

Count = []
c = []
pre = ''
for s in S:
  if s != pre:
    if len(c) != 0:
      Count.append(c)
    c = [s,1]
    pre = s
  else:
    c[1] += 1
if len(c) != 0:
  Count.append(c)
#print(Count)
if len(Count) == 1:
  ans = Count[0][1]*K//2
else:
  ans = 0
  for i in range(len(Count)):
    ans += Count[i][1]//2
  ans *= K
  if Count[0][0] == Count[-1][0] and Count[0][1] % 2 == 1 and Count[-1][1] % 2 == 1:
    ans += K-1
print(ans)

Submission status: Accepted

Solution code:
S = list(input())
K = int(input())
R = []
hoge = 1
for i in range(1,len(S)):
    if S[i] == S[i-1]:
        hoge += 1
    else:
        R.append(hoge)
        hoge = 1
R.append(hoge)
ans = 0
if len(R) == 1:
    print((R[0]*K)//2)
    exit()
if S[0] == S[-1]:
    ans += (K-1)*((R[0]+R[-1])//2) + R[0]//2 + R[-1]//2
    R[0],R[-1] = 0,0
for i in R:
    ans += (i//2)*K 
print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    k = int(input())

    prev = s[0]
    prev_idx = 0
    idx = 1

    acm = []
    while idx < len(s):
        if s[idx] != prev:
            acm.append(idx - prev_idx)
            prev_idx = idx
            prev = s[idx]
        idx += 1

    acm.append(idx - prev_idx)

    bl = True
    for i in range(len(s) - 1):
        bl = bl and (s[i] == s[i+1])

    if bl:
        ans = len(s) * k // 2

    elif s[0] == s[-1]:
        ad = acm[0] + acm[-1]
        acm2 = acm[1:-1] + [ad]
        tmp = 0
        for e in acm2:
            tmp += e // 2
        tmp2 = 0
        for e in acm:
            tmp2 += e // 2
        ans = tmp * (k - 1) + tmp2

    else:
        tmp = 0
        for e in acm:
            tmp += e // 2
        ans = tmp * k

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

S = readline().rstrip().decode('utf-8')
K = int(read())

# どうせ2つしか状態数がない。十分大きなKで、周期2の等差数列だろう

def F(S):
    arr = list(S)
    prev = 'A' # 衝突回避
    cnt = 0
    for x in S:
        if x == prev:
            cnt += 1
            prev = 'A'
        else:
            prev = x
    return cnt

arr = [F(S*i) for i in range(10)]

if K < 10:
    answer = arr[K]
else:
    if K&1:
        d = arr[9] - arr[7]
        answer = arr[9] + d * ((K-9)//2)
    else:
        d = arr[8] - arr[6]
        answer = arr[8] + d * ((K-8)//2)
print(answer)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
s=input().rstrip()
k=int(input())
n=len(s)
if s[n-1]==s[0]:
    x=s[0]
    a=0
    while a<n:
        if s[a]==x:
            a+=1
        else:
            break
    b=0
    while b<n:
        if s[n-1-b]==x:
            b+=1
        else:
            break
    if a==n:
        ans=(n*k)//2
        print(ans)
    else:
        ans=0
        p='!'
        l=0
        for i in range(a,n-b):
            if s[i]==p:
                l+=1
            else:
                ans+=l//2
                l=1
            p=s[i]
        ans+=l//2
        ans=ans*k+a//2+b//2+((a+b)//2)*(k-1)
        print(ans)
else:
    ans=0
    p='!'
    l=0
    for i in range(n):
        if s[i]==p:
            l+=1
        else:
            ans+=l//2
            l=1
        p=s[i]
    ans+=l//2
    print(ans*k)

Submission status: Accepted

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


if s.count(s[0]) == len(s):
    print(len(s)*K//2)
elif len(s) >= 3:
    ans1 = 0
    ans2 = 0
    use = [True]*len(s)
    use2 = [True]*len(s)
    for i in range(len(s)-1):
        if use[i+1] and use[i]:
            if s[i+1] == s[i]:
                ans1 += 1
                use[i+1] = False

    if use[-1] and use2[0]:
        if s[-1] == s[0]:
            ans2 += 1
            use2[0] = False

    for i in range(len(s)-1):
        if use2[i+1] and use2[i]:
            if s[i+1] == s[i]:
                ans2 += 1
                use2[i+1] = False

    print(ans1+ans2*(K-1))

else:
    if len(s) == 1:
        print(K//2)
    else:
        if s[0] == s[1]:
            print(K)
        else:
            print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  s = input().strip()
  k = int(input())
  mode = s[0] == s[-1]

  pre = 1
  idx = 1

  while idx < len(s) and s[idx] == s[0]:
    pre += 1
    idx += 1

  s = s[idx:]

  if len(s) == 0:
    print(pre * k // 2)
    return

  post = 1
  idx = -2

  while idx >= -len(s) and s[idx] == s[-1]:
    post += 1
    idx -= 1

  s = s[:idx + 1]

  required = 0
  count = 1

  for i in range(1, len(s)) :
    if s[i - 1] == s[i]:
      count += 1
    else:
      required += count // 2
      count = 1

  required += count // 2
  required *= k
  required += pre // 2
  required += post // 2

  if mode:
    required += ((pre + post) // 2) * (k - 1)
  else:
    required += (pre // 2 + post // 2) * (k - 1)

  print(required)


if __name__ == '__main__':
  main()

Submission status: Accepted

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

same = 1
for i in range(1, len(s)):
    if s[i-1] == s[i]:
        same += 1
    else:
        break

if same == len(s):
    print((len(s) * k )// 2)
    exit()

re_same = 1
for i in range(len(s)-2, -1, -1):
    if s[i+1] == s[i]:
        re_same += 1
    else:
        break


f = 0
count = 0
for i in range(1, len(s)):
    if f == 1:
        f = 0
        continue

    if s[i-1] == s[i]:
        f = 1
        count += 1


if (re_same + same) % 2 == 0 and s[0] == s[len(s)-1]:
    print(count*k + k - 1)
else:
    print(count*k)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Submit as pypy2


from __future__ import print_function, division, unicode_literals

__metaclass__ = type

try:
    input = raw_input
    range = xrange
except NameError:
    pass


import sys


# Test code requires python3
# from hypothesis import given
# from hypothesis import strategies as st
#
#
# def debug(*args, **kwargs):
#     print(*args, *('{}={}'.format(k, v) for k, v in kwargs.items()),
#           sep='; ', file=sys.stderr)


def f(k):
    return k // 2


def rle(S):
    res = []
    last = None
    for i, c in enumerate(S):
        if c == last:
            res[-1] = (last, res[-1][1] + 1)
        else:
            res.append((c, 1))
            last = c
    return res


def solve(S, K):
    N = len(S)
    x = S[0]
    i = 0
    j = N
    while i < N and S[i] == x:
        i += 1
    if i == N:
        return f(N * K)
    while j > 0 and S[j - 1] == x:
        j -= 1
    if j == N or K == 1:
        res = rle(S)
        return K * sum(f(k) for _, k in rle(S))
    res = rle(S)
    return f(i) + f(N - j) + (K - 1) * f(i + N - j)\
        + K * sum(f(k) for _, k in res[1:-1])


def main():
    S = input()
    K = int(input())
    print(solve(S, K))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

N = len(S)
first = S[0]
last = S[-1]
now = 1
ing = 0
a = []
cnt = 1
flag = 0
if N > 1:
    while now < N:
        if S[now] == S[now-1]:
            ing = 1
            cnt += 1
            now += 1
            continue
        else:
            if ing ==1:
                a.append(cnt)
                cnt = 1
                now +=1
                ing = 0
            else:
                now +=1
                cnt = 1
                ing = 0
    if ing ==1:
        a.append(cnt)

    output = 0
    for j in range(len(a)):
        output += a[j]//2

    if first==last:
        if S[0]==S[1]:
            if S[-1]==S[-2]:
                X =a[0]
                Y =a[-1]
            else:
                X = a[0]
                Y = 1
        else:
            if S[-1]==S[-2]:
                X = 1
                Y =a[-1]
            else:
                X = 1
                Y = 1

        if (X==1)and(Y==1):
            output += 1
            flag = 1
        elif X==1:
            if Y%2==1:
                output+=1
                flag = 1
        elif Y==1:
            if X%2==1:
                output+=1
                flag = 1
        else:
            if (X%2==1)and(Y%2==1):
                output += 1
                flag = 1

    output = output * K - flag
    if (len(a)==1)and(a[0]==N):
        output = (K*N)//2
elif N == 1:
    output = K//2

print(output)

Submission status: Accepted

Solution code:
#%%
s = list(input())
k = int(input())

t1 = 0
t2 = 0
if s[0] == s[-1]:
    for i in range(len(s)):
        if s[i] == s[0]:
            t1 += 1
        else:
            break
    s = s[::-1]
    for i in range(len(s)):
        if s[i] == s[0]:
            t2 += 1
        else:
            break
    if len(set(s)) == 1:
        t = len(s)
    s = s[::-1]
    t = t1 + t2

t = t1 + t2
ss = t//2
ans = 0
tmp = 0

for i in range(t1, len(s)-t2):
    #print(i)
    #print(t1, len(s)-t2-1)
    if i == t1:
        tmp = 1
    elif t1 < i < len(s)-t2-1:
        if s[i] == s[i-1]:
            tmp += 1
            #print("tmp", tmp)
        else:
            ans += tmp//2
            tmp = 1
    else:
        if s[i] == s[i-1]:
            tmp += 1
            ans += tmp //2
        else:
            ans += tmp //2
            tmp = 1

if len(set(s)) == 1:
    anser = len(s) * k //2
    print(anser)
else:
    anser = ss*(k-1) + ans * k + t1//2 + t2//2
    print(anser)
    #print(ss, ans)

Submission status: Accepted

Solution code:
l=list(input())
k=int(input())
n=len(l)
if n==1:
    if k%2==0:
        print(k//2)
    else:
        print((k-1)//2)
    exit()
al=[]
su=[]
f=1
for i in range(n-1):
    if l[i]!=l[i+1]:
        al.append(l[i])
        su.append(f)
        f=1
    else:
        f+=1
if l[-2]==l[-1]:
    al.append(l[-1])
    su.append(f)
else:
    al.append(l[-1])
    su.append(1)
    
if len(al)==1:
    j=su[0]*k
    if j%2==0:
        print(j//2)
    else:
        print((j-1)//2)
    exit()

if al[0]!=al[-1]:
    ans=0
    for i in su:
        if i%2==0:
            ans+=i//2
        else:
            ans+=(i-1)//2
    print(k*ans)
else:
    ans=0
    if su[0]%2==0:
        ans+=su[0]//2
    else:
        ans+=(su[0]-1)//2
    tmp=0
    for i in range(len(al)-2):
        if su[i+1]%2==0:
            tmp+=su[i+1]//2
        else:
            tmp+=(su[i+1]-1)//2
    ans+=tmp*k
    j=su[0]+su[-1]
    if j%2==0:
        ans+=(j//2)*(k-1)
    else:
        ans+=((j-1)//2)*(k-1)
    if su[-1]%2==0:
        ans+=su[-1]//2
    else:
        ans+=(su[-1]-1)//2
    print(ans)

Submission status: Accepted

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

ans = 0
def aa(s):
    ansaa=0
    a = 0
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            a += 1
        else:
            if a > 0:
                ansaa += (a+1)//2
                a = 0
    ansaa += (a+1)//2    
    return ansaa
# print(aa(s))
# print(aa(s*2))
# print(aa(s) + (aa(s*2) - aa(s))*(k-1))

l = -1
r = 0
if s[0] == s[-1]:
    ss = s[0]
    while l >= -n and s[l] == ss:
        l -= 1
    while r < n and s[r] == ss:
        r += 1
    # print(l,r)
    if l == -n-1:
        ans = (n*k)//2
    else:
        ans += ((r-l-1)//2)*(k-1)
        # print(aa(s[r:n+l+1])*k)
        ans += aa(s[r:n+l+1])*k
        ans += aa(s[:r])
        ans += aa(s[n+l+1:])
else:
    ans += aa(s)*k

print(ans)

Submission status: Accepted

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

lst = []
ch = ''
cnt = 0
for c in s:
    if c == ch:
        cnt += 1
    else :
        lst.append([ch, cnt])
        ch = c
        cnt = 1
lst.append([ch, cnt])
ans = 0
if len(lst) == 2:
    print((lst[1][1] * k) // 2)
    exit()
for ch, cnt in lst:
    ans += cnt // 2
# print(lst, lst[-1][0], lst[1][0])
if lst[-1][0] == lst[1][0] and (lst[-1][1] + lst[1][1]) % 2 == 0:
    print(ans * k + k -1)
else :
    print(ans * k)

Submission status: Accepted

Solution code:
import sys

S = input()
K = int(input())

if len(S) == 1:
    print(K//2)
    sys.exit()
if len(S) == 2:
    if S[0] == S[1]:
        print(K)
    else:
        print('0')
    sys.exit()

olds = S[0]
l = 1
c = 0
first = 1
for i in range(1,len(S)):

    if olds == S[i]:
        l += 1
    else:
        if first:
            firstL = l
            first = 0
        c += l//2
        l = 1
    olds = S[i]
    
    if i == len(S)-1:
        if first:
            print(len(S)*K//2)
            sys.exit()
        lastL = l
        c += l//2

if S[0] == S[-1] and firstL%2 == 1 and lastL%2 == 1:
    print((c+1)*K-1)
else:
    print(c*K)

Submission status: Accepted

Solution code:
import sys
s=input()
k=int(input())
f=0
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        f=1
        break
if f==0:
    print(len(s)*k//2)
    sys.exit()
if k>=3:
    ss=s+s+s
else:
    ss=s*k
flag=[0]*len(ss)
for i in range(1,len(ss)):
    if ss[i-1]==ss[i] and flag[i-1]==0:
        flag[i]=1
        continue
if k>=3:
    count=sum(flag[0:len(s)])+sum(flag[len(s):2*len(s)])*(k-2)+sum(flag[2*len(s):3*len(s)])
else:
    count=sum(flag)
print(count)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

S = input()
K = INT()

N = len(S)
numlist = []
count = 1
if N == 1:
    print(K // 2)
else:
    for i in range(1, N):
        if S[i] == S[i - 1]:
            count += 1
        else:
            numlist.append(count)
            count = 1
    numlist.append(count)
    if len(numlist) == 1:
        ans = (N * K) // 2
    elif S[0] == S[-1]:
        center = numlist[0] + numlist[-1]
        ans = (center // 2) * (K - 1)
        ans += numlist[0] // 2
        ans += numlist[-1] // 2
        for i in range(1, len(numlist)-1):
            ans += (numlist[i] // 2) * K
    else:
        ans = 0
        for i in range(len(numlist)):
            ans += (numlist[i] // 2) * K
    print(ans)

Submission status: Accepted

Solution code:
import sys, collections, copy

def solve():
    S = list(input())
    S2 = copy.deepcopy(S)
    K = int(input())
    lens = len(S)
    head_change = 0
    for i in range(1, lens):
        if S[i] == S[i - 1]:
            head_change += 1
            S[i] = "Changed"
    
    inner_change = 1
    S2[0] = "Changed"
    for i in range(1, lens):
        if S2[i] == S2[i-1]:
            inner_change += 1
            S2[i] = "Changed"

    if lens == 1: print(K // 2)
    elif S[lens-1] != "Changed" and S[0] == S[lens - 1]:
        if S2[lens-1] != "Changed":
            print(head_change + inner_change * (K - 1))
        else:
            print((head_change + inner_change) * (K // 2) + head_change * (K % 2))
    else:
        print(head_change * K)
    #print(S)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
S = input()
K = int(input())
ns = []
c = S[0]
n = 1
for i in range(1, len(S)):
  if c == S[i]:
    n += 1
  else:
    ns.append(n)
    n = 1
  c = S[i]
ns.append(n)
#print(ns)
if len(ns) == 1:
  r = ns[0]*K//2
  print(r)
  exit()
r = 0
for i in range(1, len(ns)-1):
  r += K*(ns[i]//2)
if S[0] == S[-1]:
  r += (ns[0]//2)+(ns[-1]//2)
  r += (K-1)*((ns[0]+ns[-1])//2)
else:
  r += K*(ns[0]//2)+K*(ns[-1]//2)
print(r)