Problem:
 Score : 1000 points    Problem Statement There are 3^N people dancing in circle.
We denote with 0,1,\dots, 3^{N}-1 the positions in the circle, starting from an arbitrary position and going around clockwise. Initially each position in the circle is occupied by one person.  The people are going to dance on two kinds of songs: salsa and rumba.   When a salsa is played, the person in position i goes to position j , where j is the number obtained replacing all digits 1 with 2 and all digits 2 with 1 when reading i in base 3 (e.g., the person in position 46 goes to position 65 ).  When a rumba is played, the person in position i moves to position i+1 (with the identification 3^N = 0 ).   You are given a string T=T_1T_2\cdots T_{|T|} such that T_i= S if the i -th song is a salsa and T_i= R if it is a rumba.
After all the songs have been played, the person that initially was in position i is in position P_i .
Compute the array P_0,P_1,\dots, P_{3^N-1} .      Constraints  1 \le N \le 12  1 \le |T| \le 200,000  T contains only the characters S and R .         Input Input is given from Standard Input in the following format:  N  T       Output You should print on Standard Output:  P_0  P_1  \cdots  P_{3^N-1}         Sample Input 1 1
SRS      Sample Output 1 2 0 1  Before any song is played, the positions are: 0 , 1 , 2 .  When we say "person i ", we mean "the person that was initially in position i ".   After the first salsa, the positions are: 0 , 2 , 1 .  After the rumba, the positions are: 1 , 0 , 2 (so, person 0 is in position 1 , person 1 is in position 0 and person 2 is in position 2 ).  After the second salsa, the positions are 2 , 0 , 1 (so, person 0 is in position 2 , person 1 is in position 0 and person 2 is in position 1 ).        Sample Input 2 2
RRSRSSSSR      Sample Output 2 3 8 1 0 5 7 6 2 4       Sample Input 3 3
SRSRRSRRRSRRRR      Sample Output 3 23 9 22 8 3 7 20 24 19 5 18 4 17 12 16 2 6 1 14 0 13 26 21 25 11 15 10

Solution (Python):
N=int(input())
T=input()
t=[]
tmp=0
sign="R"
for i in range(len(T)):
    if sign=="R":
        if T[i]=="R":
            tmp+=1
        else:
            if t and t[-1]!="S":
                t[-1]+=tmp
                sign="S"
                tmp=1
            else:
                t.append(tmp)
                tmp=1
                sign="S"
    else:
        if T[i]=="S":
            tmp+=1
        else:
            if tmp%2==1:
                t.append("S")
            tmp=1
            sign="R"

if sign=="R":
    if t and t[-1]!="S":
        t[-1]+=tmp
        sign="S"
        tmp=1
    else:
        t.append(tmp)
        tmp=1
        sign="S"
else:
    if tmp%2==1:
        t.append("S")
    tmp=1
    sign="R"

def dance(n,music):
    if n==0:
        return [0]
    res=[-1]*3**n
    for i in range(3):
        nmusic=[]
        val=i
        for j in range(len(music)):
            if music[j]!="S":
                tmp=music[j]//3
                if val+(music[j]%3)>=3:
                    tmp+=1
                if nmusic and nmusic[-1]!="S":
                    nmusic[-1]+=tmp
                elif tmp:
                    nmusic.append(tmp)
                val+=music[j]
                val%=3
            else:
                if nmusic and nmusic[-1]=="S":
                    nmusic.pop()
                else:
                    nmusic.append("S")
                val=(-val)%3
        rres=dance(n-1,nmusic)
        for j in range(3**(n-1)):
            res[3*j+i]=3*rres[j]+val
    return res


res=dance(N,t)
print(*res)

Solution (Python):
n = int(input())
t = input()
op = [[int(c == 'R') for c in t]]
ans = [0]

for d in range(n):
    k = 3 ** d
    nop = []
    nans = []
    for g in range(3):  
        for i in range(k):  
            opg = op[i]
            opn = []
            h = g
            for o in opg:
                if o == 0:
                    if len(opn) > 0 and opn[-1] == 0:
                        opn.pop()
                    else:
                        opn.append(0)
                    if h == 1:
                        h = 2
                    elif h == 2:
                        h = 1
                else:
                    if h == 2:
                        h = 0
                        opn.append(1)
                    else:
                        h += 1
            nop.append(opn)
            nans.append(h * k + ans[i])

    op = nop
    ans = nans

print(*ans)

Solution (Python):





















n = int(input())
t = input()
op = [[int(c == 'R') for c in t]]
ans = [0]

for d in range(n):
    k = 3 ** d
    nop = []
    nans = [0] * (k * 3)
    for g in range(3):  
        for i in range(k):  
            opg = op[i]
            opn = []
            h = g
            for o in opg:
                if o == 0:
                    if len(opn) > 0 and opn[-1] == 0:
                        opn.pop()
                    else:
                        opn.append(0)
                    if h == 1:
                        h = 2
                    elif h == 2:
                        h = 1
                else:
                    if h == 2:
                        h = 0
                        opn.append(1)
                    else:
                        h += 1
            nop.append(opn)
            nans[g * k + i] = h * k + ans[i]

    op = nop
    ans = nans

print(*ans)

Solution (Python):
def rev(a):
    L = []
    for i in range(N):
        L.append(a % 3)
        a //= 3
    return int("".join(map(str, L)), 3)
    
def salsa():
    lazy[0] *= -1

def rumba():
    i = 0
    for k in range(N):
        if lazy[i] < 0:
            lazy[3*i+1] *= -1
            lazy[3*i+2] *= -1
            lazy[3*i+3] *= -1
            lazy[i] = 1
            value[3*i+1] ^= 3
            value[3*i+2] ^= 3
            value[3*i+3] ^= 3
        value[3*i+1] += 1
        value[3*i+2] += 1
        value[3*i+3] += 1
        value[3*i+1] %= 3
        value[3*i+2] %= 3
        value[3*i+3] %= 3
        i = 3 * i + (1 if value[3*i+1] == 0 else 2 if value[3*i+2] == 0 else 3)

def calcall():
    a = 1
    i = 0
    for k in range(1, N + 1):
        for _ in range(3 ** k):
            i += 1
            if lazy[(i-1)//3] < 0:
                lazy[i] *= -1
                if value[i]: value[i] ^= 3
            value[i] = value[i] * a + value[(i-1) // 3]
        a *= 3
        
N = int(input())
NN = 3 ** (N + 1) // 2
value = [(i-1) % 3 if i else 0 for i in range(NN)]
lazy = [1 for i in range(NN)]

for t in input():
    if t == "R":
        rumba()
    else:
        salsa()

calcall()

ANS = [0] * (3 ** N)
for i in range(3 ** N):
    ANS[rev(i)] = value[i + (NN - 1) // 3]

print(*ANS)

Solution (Python):
n = int(input())
t = input()

new_pos = [0]
new_w = [0]*len(t)

for i in range(1, n+1):
    ith_bit = [0]*(3**i)  
    for k in range(3):
        for l in range(3**(i-1)):
            ith_bit[k*3**(i-1)+l] = k

    pos = new_pos
    w = new_w  

    q = 0
    already = [0]*3**i
    new_w = [0]*len(t)

    for j in range(len(t)):
        mark = w[j]
        for k in range(3):
            cand = mark + k*3**(i-1)
            if ith_bit[cand] and (q - already[cand]) % 2:
                
                ith_bit[cand] = 3 - ith_bit[cand]
            already[cand] = q  
            if ith_bit[cand] == 2:
                new_w[j] = cand

        if t[j] == 'S':
            q += 1
        else:
            for k in range(3):
                ith_bit[mark + k*3**(i-1)] = (ith_bit[mark + k*3**(i-1)]+1) % 3

    new_pos = [0]*(3**i)
    for j in range(3**i):
        if ith_bit[j] and (q - already[j]) % 2:
            
            
            
            ith_bit[j] = 3-ith_bit[j]
        new_pos[j] = pos[j % 3**(i-1)] + ith_bit[j]*3**(i-1)

print(*new_pos)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
P3 = [pow(3, i) for i in range(N+1)]

St = [1 if s == 'R' else 0 for s in readline().strip()]
LS = len(St)
ans = [None]*P3[N]
arr = [None]*P3[N]
ans[0] = 0
arr[0] = St[:]
REV = (0, 2, 1)
for l in range(N):
    p3l = P3[l]
    for i in range(p3l):
        k0, k1, k2 = 0, 1, 2
        r0, r1, r2 = [], [], []
        for s in arr[i]:
            if s:
                k0 += 1
                k1 += 1
                k2 += 1
                if k0 == 3:
                    k0 = 0
                    r0.append(1)
                if k1 == 3:
                    k1 = 0
                    r1.append(1)
                if k2 == 3:
                    k2 = 0
                    r2.append(1)
            else:
                k0 = REV[k0]
                k1 = REV[k1]
                k2 = REV[k2]
                if r0 and r0[-1] == 0:
                    r0.pop()
                else:
                    r0.append(0)
                if r1 and r1[-1] == 0:
                    r1.pop()
                else:
                    r1.append(0)
                if r2 and r2[-1] == 0:
                    r2.pop()
                else:
                    r2.append(0)
        arr[2*p3l+i] = r2[:]
        arr[p3l+i] = r1[:]
        arr[i] = r0[:]
        a = ans[i]
        ans[2*p3l+i] = k2*p3l+a
        ans[p3l+i] = k1*p3l+a
        ans[i] = k0*p3l+a
                
print(*ans)

Solution (Python):
import sys
readline = sys.stdin.readline

def calc(x):
    stack = []
    for _ in range(N):
        stack.append((3-x%3)%3)
        x //= 3
    res = 0
    for i in range(N-1, -1, -1):
        res *= 3
        res += stack[i]
    return res

N = int(readline())
P3 = [pow(3, i) for i in range(N+1)]

St = [1 if s == 'R' else 0 for s in readline().strip()]
LS = len(St)
ans = [None]*P3[N]
arr = [None]*P3[N]
ans[0] = 0
arr[0] = St[:]
REV = (0, 2, 1)
for l in range(N):
    p3l = P3[l]
    for i in range(p3l):
        k0, k1, k2 = 0, 1, 2
        r0, r1, r2 = [], [], []
        for s in arr[i]:
            if s:
                k0 += 1
                k1 += 1
                k2 += 1
                if k0 == 3:
                    k0 = 0
                    r0.append(1)
                if k1 == 3:
                    k1 = 0
                    r1.append(1)
                if k2 == 3:
                    k2 = 0
                    r2.append(1)
            else:
                k0 = REV[k0]
                k1 = REV[k1]
                k2 = REV[k2]
                if r0 and r0[-1] == 0:
                    r0.pop()
                else:
                    r0.append(0)
                if r1 and r1[-1] == 0:
                    r1.pop()
                else:
                    r1.append(0)
                if r2 and r2[-1] == 0:
                    r2.pop()
                else:
                    r2.append(0)
        arr[2*p3l+i] = r2[:]
        arr[p3l+i] = r1[:]
        arr[i] = r0[:]
        a = ans[i]
        ans[2*p3l+i] = k2*p3l+a
        ans[p3l+i] = k1*p3l+a
        ans[i] = k0*p3l+a
                
print(*ans)

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8,i4[::1])', cache=True)
def solve(dep, T):
    if dep == 0:
        return np.array([0], np.int32)
    A = np.empty(3**dep, np.int32)
    for d in range(3):
        TT = np.empty_like(T)
        p = 0
        x = d
        for t in T:
            if t == 0:
                x = 3 - x if x else 0
                if p > 0 and TT[p - 1] == 0:
                    p -= 1
                else:
                    TT[p] = 0
                    p += 1
            else:
                x = x + 1
                if x == 3:
                    x = 0
                    TT[p] = 1
                    p += 1
        TT = TT[:p]
        A[d::3] = 3 * solve(dep - 1, TT) + x
    return A

N = int(readline())
T = np.frombuffer(read().rstrip(), 'S1')

T = ((T == b'R') * 1).astype(np.int32)

ans = solve(N, T)
print(' '.join(ans.astype(str)))

Solution (Python):
n = int(input())
s = input()
m = 3 ** n
ans = [0] * m
c = 3
t = [[0 if q == 'S' else 1 for q in s]]
for i in range(n) : 
    nt = [[]] * c
    for j in range(c) : 
        x = j
        x = x // (3**i)
        pre = j - x*c//3
        nxt = []
        for q in t[pre] : 
            if q == 0 : 
                if x != 0 : x = 3 - x
                if len(nxt) >= 1 and nxt[-1] == 0 : nxt.pop()
                else : nxt.append(0)
            else :
                x += 1
                if x == 3 :
                    x = 0
                    nxt.append(1)
        for k in range(j,m,c):
            ans[k] += x*c//3
        nt[j] = nxt
    t = nt
    c *= 3
print(*ans)