Problem:


Extraordinary Girl (I)

    She is an extraordinary girl. She works for a library. Since she is young
and cute, she is forced to do a lot of laborious jobs. The most annoying job
for her is to put returned books into shelves, carrying them by a cart. The
cart is large enough to carry many books, but too heavy for her. Since she
is delicate, she wants to walk as short as possible when doing this job.
    The library has 4N shelves (1 

    Since she is so lazy that she doesn’t want to memorize a complicated
route, she only walks main passages in forward direction (see an arrow in
Figure 1). The walk from an intersection to its adjacent intersections takes 1
cost. It means the walk from the middle of shelves to its adjacent intersection,
and vice versa, takes 0.5 cost. You, as only a programmer amoung her friends,
are to help her compute the minimum possible cost she takes to put all books
in the shelves.

Input

The first line of input contains the number of test cases, T . Then T test
cases follow. Each test case consists of two lines. The first line contains the
number N , and the second line contains 4N characters, either Y or N . Y in
n-th position means there are some books with ID n, and N means no book
with ID n.

Output

The output should consists of T lines, each of which contains one integer,
the minimum possible cost, for each test case.

Sample Input

2
2
YNNNNYYY
4
NYNNYYNNNYNYYNNN

Output for the Sample Input

6
9



Sample input:
2
2
YNNNNYYY
4
NYNNYYNNNYNYYNNN


Sample output:
6
9

Submission status: Wrong Answer

Solution code:
def getAB(r,books,N):
     if r==0:
         return(books[2*r],books[2*(N+r)])
     elif r==N:
         return(books[2*r-1],books[2*(N+r)-1])
     elif r==N+1:
         return (0,0)
     else:
         return(books[2*r-1]|books[2*r],books[2*(N+r)-1]|books[2*(N+r)])
def getcostandarray(A,B,array,r,books):
    if array==0:
        if B:
            return(3,2)
        elif A:
            nextB=getAB(r+1,books,N)[1]
            if nextB:
                return (2,1)
            else:
                return(2,0)
        else:
            return (1,0)
    elif array==2:
        if A:
            return(3,0)
        elif B:
            return (2,1)
        else:
            return (1,2)
    else:
        if A==0 and B==0:
            return (1,1)
        elif A==1 and B==0:
            return (2,0)
        elif B==1 and A==0:
            return (2,2)
        else:
            nextA=getAB(r+1,books,N)[0]
            if nextA:
                return (4,0)
            else:
                return (4,2)


Q=int(raw_input())
for i in range(Q):
    N=int(raw_input())
    books=[1 if x=='Y' else 0 for x in raw_input()]
    array=0
    totalcost=-1
    for i in range(N+1):
        (A,B)=getAB(i,books,N)
        (cost,array)=getcostandarray(A,B,array,i,books)
        totalcost=totalcost+cost
    totalcost=totalcost+array
    print totalcost

Submission status: Wrong Answer

Solution code:
def getAB(r,books,N):
     if r==0:
         return(books[2*r],books[2*(N+r)])
     elif r==N:
         return(books[2*r-1],books[2*(N+r)-1])
     elif r==N+1:
         return (1,0)
     else:
         return(books[2*r-1]|books[2*r],books[2*(N+r)-1]|books[2*(N+r)])
def getcostandarray(A,B,array,r,books):
    if array==0:
        if B:
            return(3,2)
        elif A:
            nextB=getAB(r+1,books,N)[1]
            if nextB:
                return (2,1)
            else:
                return(2,0)
        else:
            return (1,0)
    elif array==2:
        if A:
            return(3,0)
        elif B:
            return (2,1)
        else:
            return (1,2)
    else:
        if A==0 and B==0:
            return (1,1)
        elif A==1 and B==0:
            return (2,0)
        elif B==1 and A==0:
            return (2,2)
        else:
            nextA=getAB(r+1,books,N)[0]
            if nextA:
                return (4,0)
            else:
                return (4,2)


Q=int(raw_input())
for i in range(Q):
    N=int(raw_input())
    books=[1 if x=='Y' else 0 for x in raw_input()]
    array=0
    totalcost=-1
    for i in range(N+1):
        (A,B)=getAB(i,books,N)
        (cost,array)=getcostandarray(A,B,array,i,books)
        totalcost=totalcost+cost
        #print (A,B),(cost,array)
    totalcost=totalcost+array
    print totalcost

Submission status: Wrong Answer

Solution code:
def getAB(r,books,N):
     if r==0:
         return(books[2*r],books[2*(N+r)])
     elif r==N:
         return(books[2*r-1],books[2*(N+r)-1])
     elif r==N+1:
         return (1,0)
     else:
         return(books[2*r-1]|books[2*r],books[2*(N+r)-1]|books[2*(N+r)])
def getcostandarray(A,B,array,r,books):
    if array==0:
        if B:
            return(3,2)
        elif A:
            nextB=getAB(r+1,books,N)[1]
            if nextB:
                return (2,1)
            else:
                return(2,0)
        else:
            return (1,0)
    elif array==2:
        if A:
            return(3,0)
        elif B:
            nextB=getAB(r+1,books,N)[1]
            if nextB:
                return (2,2)
            else:
                return(2,1)
        else:
            return (1,2)
    else:
        if A==0 and B==0:
            return (1,1)
        elif A==1 and B==0:
            return (2,0)
        elif B==1 and A==0:
            return (2,2)
        else:
            nextA=getAB(r+1,books,N)[0]
            if nextA:
                return (4,0)
            else:
                return (4,2)


Q=int(raw_input())
for i in range(Q):
    N=int(raw_input())
    books=[1 if x=='Y' else 0 for x in raw_input()]
    array=0
    totalcost=-1
    for i in range(N+1):
        (A,B)=getAB(i,books,N)
        (cost,array)=getcostandarray(A,B,array,i,books)
        totalcost=totalcost+cost
        #print (A,B),(cost,array)
    totalcost=totalcost+array
    print totalcost

Submission status: Wrong Answer

Solution code:
pre = [
    ((0, 1, 2), (1, 0, 1), (2, 1, 0)),
    ((3, 2, 2), (2, 1, 1), (2, 1, 1)),
    ((1, 1, 2), (1, 1, 2), (2, 2, 3)),
    ((3, 2, 2), (2, 2, 2), (2, 2, 3)),
]

queries = int(input())
for _ in range(queries):
    n = int(input())
    books = [c == 'Y' for c in input()]
    books = [(False, False)] + list(map(lambda u, l: (u, l), books[:2 * n], books[2 * n:])) + [(False, False)]
    shelves = [int(u1 or u2) * 2 + int(l1 or l2) for (u1, l1), (u2, l2) in zip(*[iter(books)] * 2)]
    ans = [0, 0, 0]
    for key in shelves:
        ans = [min(ans[j] + c for j, c in enumerate(costs)) + 1 for costs in pre[key]]
    print(ans[0] - 1)

Submission status: Wrong Answer

Solution code:
pre = [
    ((0, 1, 2), (1, 0, 1), (2, 1, 0)),
    ((3, 2, 2), (2, 1, 1), (2, 1, 1)),
    ((1, 1, 2), (1, 1, 2), (2, 2, 3)),
    ((3, 2, 2), (2, 2, 2), (2, 2, 3)),
]

queries = int(input())
for _ in range(queries):
    n = int(input())
    books = [c == 'Y' for c in input()]
    books = [(False, False)] + list(map(lambda u, l: (u, l), books[:2 * n], books[2 * n:])) + [(False, False)]
    shelves = [int(u1 or u2) * 2 + int(l1 or l2) for (u1, l1), (u2, l2) in zip(*[iter(books)] * 2)]
    ans = [0, 0, 0]
    for key in shelves:
        new_ans = [min(ans[j] + c for j, c in enumerate(costs)) + 1 for costs in pre[key]]
        ans = new_ans
    print(ans[0] - 1)

Submission status: Wrong Answer

Solution code:
pre = [
    ((0, 1, 2), (1, 0, 1), (2, 1, 0)),
    ((3, 2, 2), (2, 1, 1), (2, 1, 1)),
    ((1, 1, 2), (1, 1, 2), (2, 2, 3)),
    ((3, 2, 2), (2, 2, 2), (2, 2, 3)),
]

q = int(input())
for _ in range(q):
    n = int(input())
    books = [c == 'Y' for c in input()]
    books = [(False, False)] + list(map(lambda u, l: (u, l), books[:2 * n], books[2 * n:])) + [(False, False)]
    shelves = [int(u1 or u2) * 2 + int(l1 or l2) for (u1, l1), (u2, l2) in zip(*[iter(books)] * 2)]
    ans = [0, 0, 0]
    for key in shelves:
        new_ans = [min(a + c for a, c in zip(ans, costs)) for costs in pre[key]]
        ans = new_ans
    print(ans[0] + n)

Submission status: Accepted

Solution code:
def getAB(r,books,N):
     if r==0:
         return(books[2*r],books[2*(N+r)])
     elif r==N:
         return(books[2*r-1],books[2*(N+r)-1])
     elif r==N+1:
         return (1,0)
     else:
         return(books[2*r-1]|books[2*r],books[2*(N+r)-1]|books[2*(N+r)])
         
#def getcostandarray(A,B,array,r,books):
#    if array==0:
#        if B:
#            return(3,2)
#        elif A:
#            nextB=getAB(r+1,books,N)[1]
#            if nextB:
#                return (2,1)
#            else:
#                return(2,0)
#        else:
#            return (1,0)
#    elif array==2:
#        if A:
#            return(3,0)
#        elif B:
#            nextB=getAB(r+1,books,N)[1]
#            if nextB:
#                return (2,2)
#            else:
#                return(2,1)
#        else:
#            return (1,2)
#    else:
#        if A==0 and B==0:
#            return (1,1)
#        elif A==1 and B==0:
#            return (2,0)
#        elif B==1 and A==0:
#            return (2,2)
#        else:
#            nextA=getAB(r+1,books,N)[0]
#            if nextA:
#                return (4,0)
#            else:
#                return (4,2)


Q=int(raw_input())
for i in range(Q):
    N=int(raw_input())
    books=[1 if x=='Y' else 0 for x in raw_input()]
    array=0
    Alist=[]
    Blist=[]
    firstB=-1
    lastB=-1
    for i in range(N+1):
        (A,B)=getAB(i,books,N)
        Alist.append(A)
        Blist.append(B)
        if B:
            if firstB==-1:
                firstB=i
            lastB=i
    if firstB!=-1:
        if 1 not in Alist[:firstB+1]:
            Alist[firstB]=1
        if 1 not in Alist[lastB:]:
            Alist[lastB]=1
    totalcost=N+sum(Alist)+sum(Blist)
        #(cost,array)=getcostandarray(A,B,array,i,books)
        #totalcost=totalcost+cost
        #print (A,B),(cost,array)
    #totalcost=totalcost+array
    print totalcost

Submission status: Accepted

Solution code:
#while 1:
    #n=map(int,raw_input().split())




l = int(raw_input())


for i in range(l):
    n= int(raw_input())
    line = raw_input()
    arr = [ [0,0,0] for j in range(n+1)]
    u = [0] * (n+1)
    d = [0] * (n+1)
    
    if(line[0]=='Y'): u[0]=1
    if(line[2*n]=='Y'): d[0]=1
    if(line[2*n-1]=='Y'): u[n]=1
    if(line[4*n-1]=='Y'): d[n]=1
    for i in range(1,n):
        if(line[2*i-1]=='Y'): u[i]=1
        if(line[2*i]=='Y'): u[i]=1
        if(line[2*n + 2*i-1]=='Y'): d[i]=1
        if(line[2*n + 2*i]=='Y'): d[i]=1
    #
    #print "u",u
    #print "d",d
    
    if(u[0]==1 and d[0] ==1):
           arr[0][0]=3
           arr[0][1]=2
           arr[0][2]=2
    if(u[0]==1 and d[0] ==0):
           arr[0][0]=1
           arr[0][1]=1
           arr[0][2]=2
    if(u[0]==0 and d[0] ==1):
           arr[0][0]=3
           arr[0][1]=2
           arr[0][2]=2
    if(u[0]==0 and d[0] ==0):
           arr[0][0]=0
           arr[0][1]=1
           arr[0][2]=2
           
    for i in range(1 , n+1):
        if(u[i]==1 and d[i] ==1):
               arr[i][0]=min( \
                   arr[i-1][0]+1+3, \
                   arr[i-1][1]+1+2, \
                   arr[i-1][2]+1+2)
               arr[i][1]=min( \
                   arr[i-1][0]+1+2, \
                   arr[i-1][1]+1+2, \
                   arr[i-1][2]+1+2)
               arr[i][2]=min( \
                   arr[i-1][0]+1+2, \
                   arr[i-1][1]+1+2, \
                   arr[i-1][2]+1+3)
        if(u[i]==1 and d[i] ==0):
               arr[i][0]=min( \
                   arr[i-1][0]+1+1, \
                   arr[i-1][1]+1+1, \
                   arr[i-1][2]+1+2)
               arr[i][1]=min( \
                   arr[i-1][0]+1+1, \
                   arr[i-1][1]+1+1, \
                   arr[i-1][2]+1+2)
               arr[i][2]=min( \
                   arr[i-1][0]+1+2, \
                   arr[i-1][1]+1+2, \
                   arr[i-1][2]+1+3)
        if(u[i]==0 and d[i] ==1):
               arr[i][0]=min( \
                   arr[i-1][0]+1+3, \
                   arr[i-1][1]+1+2, \
                   arr[i-1][2]+1+2)
               arr[i][1]=min( \
                   arr[i-1][0]+1+2, \
                   arr[i-1][1]+1+1, \
                   arr[i-1][2]+1+1)
               arr[i][2]=min( \
                   arr[i-1][0]+1+2, \
                   arr[i-1][1]+1+1, \
                   arr[i-1][2]+1+1)
        if(u[i]==0 and d[i] ==0):
               arr[i][0]=min( \
                   arr[i-1][0]+1, \
                   arr[i-1][1]+1+1, \
                   arr[i-1][2]+1+2)
               arr[i][1]=min( \
                   arr[i-1][0]+1+1, \
                   arr[i-1][1]+1, \
                   arr[i-1][2]+1+1)
               arr[i][2]=min( \
                   arr[i-1][0]+1+2, \
                   arr[i-1][1]+1+1, \
                   arr[i-1][2]+1)
        #
    print arr[n][0]

Submission status: Accepted

Solution code:
pre = [
    ((0, 1, 2), (1, 0, 1), (2, 1, 0)),
    ((3, 2, 2), (2, 1, 1), (2, 1, 1)),
    ((1, 1, 2), (1, 1, 2), (2, 2, 3)),
    ((3, 2, 2), (2, 2, 2), (2, 2, 3)),
]

q = int(input())
for _ in range(q):
    n = int(input())
    books = [c == 'Y' for c in input()]
    books = [(False, False)] + list(map(lambda u, l: (u, l), books[:2 * n], books[2 * n:])) + [(False, False)]
    shelves = [int(u1 or u2) * 2 + int(l1 or l2) for (u1, l1), (u2, l2) in zip(*[iter(books)] * 2)]
    ans = [0, 1, 2]
    for key in shelves:
        new_ans = [min(a + c for a, c in zip(ans, costs)) for costs in pre[key]]
        ans = new_ans
    print(ans[0] + n)

Submission status: Accepted

Solution code:
pre = [
    ((0, 1, 2), (1, 0, 1), (2, 1, 0)),
    ((3, 2, 2), (2, 1, 1), (2, 1, 1)),
    ((1, 1, 2), (1, 1, 2), (2, 2, 3)),
    ((3, 2, 2), (2, 2, 2), (2, 2, 3)),
]

q = int(input())
for _ in range(q):
    n = int(input())
    books = [c == 'Y' for c in input()]
    books = [(0, 0)] + list(zip(books[:2 * n], books[2 * n:])) + [(0, 0)]
    shelves = [(u1 | u2) * 2 + (l1 | l2) for (u1, l1), (u2, l2) in zip(*[iter(books)] * 2)]
    ans = [0, 1, 2]
    for key in shelves:
        new_ans = [min(a + c for a, c in zip(ans, costs)) for costs in pre[key]]
        ans = new_ans
    print(ans[0] + n)

Submission status: Accepted

Solution code:
from operator import add

pre = [
    ((0, 1, 2), (1, 0, 1), (2, 1, 0)),
    ((3, 2, 2), (2, 1, 1), (2, 1, 1)),
    ((1, 1, 2), (1, 1, 2), (2, 2, 3)),
    ((3, 2, 2), (2, 2, 2), (2, 2, 3)),
]

q = int(input())
for _ in range(q):
    n = int(input())
    books = [c == 'Y' for c in input()]
    books = [(0, 0)] + list(zip(books[:2 * n], books[2 * n:])) + [(0, 0)]
    shelves = [(u1 | u2) * 2 + (l1 | l2) for (u1, l1), (u2, l2) in zip(*[iter(books)] * 2)]
    ans = [0, 1, 2]
    for key in shelves:
        new_ans = [min(map(add, ans, costs)) for costs in pre[key]]
        ans = new_ans
    print(ans[0] + n)

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

T = input()

for loop in range(T):
    N = input()
    S = raw_input()
    S1 = 'N' + S[:N * 2] + 'N'
    S2 = 'N' + S[N * 2:] + 'N'
    sx1 = sx2 = 100000
    gx1 = gx2 = -1
    ans = 0
    for i in range(N + 1):
        if S1[i * 2] == 'Y' or S1[i * 2 + 1] == 'Y':
            ans += 1
            sx1 = min(sx1, i)
            gx1 = i
        if S2[i * 2] == 'Y' or S2[i * 2 + 1] == 'Y':
            ans += 1
            sx2 = min(sx2, i)
            gx2 = i
    if sx1 > sx2:
        ans += 1
    if gx1 < gx2:
        ans += 1
    print N + ans

Submission status: Accepted

Solution code:
# AOJ 1002: Extraordinary Girl I
# Python3 2018.7.5 bal4u

import sys
from sys import stdin
input = stdin.readline

INF = 0x7fffffff
cost = ((((0,3),(1,3)),((1,2),(1,2)),((2,2),(2,2))),
	    (((1,2),(1,2)),((0,1),(1,2)),((1,1),(2,2))),
	    (((2,2),(2,2)),((1,1),(2,2)),((0,1),(3,3))))

for cno in range(int(input())):
	n = int(input())
	n2 = n << 1
	shelf = [[0 for j in range(n+2)] for i in range(2)]
	p = input()
	for i in range(n2):
		if p[i] == 'Y': shelf[0][(i+1)>>1] = 1
	for i in range(n2):
		if p[n2+i] == 'Y': shelf[1][(i+1)>>1] = 1

	dp = [[INF for j in range(n+2)] for i in range(3)]
	dp[0][0] = 0
	for i in range(n+1):
		for j in range(9):
			dp[j%3][i+1] = min(dp[j%3][i+1], dp[j//3][i]+cost[j//3][j%3][shelf[0][i]][shelf[1][i]]+1)
	print(dp[0][n+1]-1)