Problem:


Score : 600 points

Problem Statement

There is a game that involves three variables, denoted A, B, and C.

As the game progresses, there will be N events where you are asked to make a choice.
Each of these choices is represented by a string s_i. If s_i is AB, you must add 1 to A or B then subtract 1 from the other; if s_i is AC, you must add 1 to A or C then subtract 1 from the other; if s_i is BC, you must add 1 to B or C then subtract 1 from the other.

After each choice, none of A, B, and C should be negative.

Determine whether it is possible to make N choices under this condition. If it is possible, also give one such way to make the choices.

Constraints

1 \leq N \leq 10^5

0 \leq A,B,C \leq 10^9

N, A, B, C are integers.

s_i is AB, AC, or BC.

Input

Input is given from Standard Input in the following format:

N A B C
s_1
s_2
:
s_N

Output

If it is possible to make N choices under the condition, print Yes; otherwise, print No.

Also, in the former case, show one such way to make the choices in the subsequent N lines. The (i+1)-th line should contain the name of the variable (A, B, or C) to which you add 1 in the i-th choice.

Sample Input 1

2 1 3 0
AB
AC

Sample Output 1

Yes
A
C

You can successfully make two choices, as follows:

In the first choice, add 1 to A and subtract 1 from B. A becomes 2, and B becomes 2.

In the second choice, add 1 to C and subtract 1 from A. C becomes 1, and A becomes 1.

Sample Input 2

3 1 0 0
AB
BC
AB

Sample Output 2

No

Sample Input 3

1 0 9 0
AC

Sample Output 3

No

Sample Input 4

8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB

Sample Output 4

Yes
C
B
B
C
C
B
A
A



Sample input:
2 1 3 0
AB
AC


Sample output:
Yes
A
C

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,A,B,C=map(int, input().split())
    S=[input().rstrip() for _ in range(N)]

    MX=3
    dp=[[[[None]*(MX+1) for _ in range(MX+1)] for __ in range(MX+1)] for ___ in range(N+4)]
    dp[0][min(MX,A)][min(MX,B)][min(MX,C)]=1
    for i,s in enumerate(S):
        ni=i+1
        for a in range(MX+1):
            for b in range(MX+1):
                for c in range(MX+1):
                    for j in range(2):
                        na,nb,nc=a,b,c
                        sel=None
                        if s=='AB':
                            if j==0:
                                if b==0: continue
                                na,nb=min(MX,na+1),nb-1
                                sel='A'
                            else:
                                if a==0: continue
                                na,nb=na-1,min(MX,nb+1)
                                sel='B'
                        elif s=='AC':
                            if j==0:
                                if c==0: continue
                                na,nc=min(MX,na+1),nc-1
                                sel='A'
                            else:
                                if a==0: continue
                                na,nc=na-1,min(MX,nc+1)
                                sel='C'
                        elif s=='BC':
                            if j==0:
                                if c==0: continue
                                nb,nc=min(MX,nb+1),nc-1
                                sel='B'
                            else:
                                if b==0: continue
                                nb,nc=nb-1,min(MX,nc+1)
                                sel='C'
                        if dp[i][a][b][c]: dp[ni][na][nb][nc]=(a,b,c,sel)

    flag=False
    ga,gb,gc=0,0,0
    for a in range(MX+1):
        for b in range(MX+1):
            for c in range(MX+1):
                if dp[N][a][b][c]:
                    flag=True
                    ga,gb,gc=a,b,c
    if flag==False:
        print('No')
        return
    print('Yes')
    ans=[]
    for i in range(N,0,-1):
        ga,gb,gc,sel=dp[i][ga][gb][gc]
        ans.append(sel)
    for a in reversed(ans):
        print(a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter,deque
input = sys.stdin.readline
N,A,B,C= map(int,input().split())
S = [input().strip() for i in range(N)]

op = []
dq = deque([[A,B,C,0,op]])
while dq:
    A,B,C,i,op = dq.pop()
    if min(A,B,C) < 0:
        continue
    if i == N:
        break
    s = S[i]
    if s == 'AB':
        if A != 0:
            dq.append([A-1,B+1,C,i+1,op+['B']])
        if B != 0:
            dq.append([A+1,B-1,C,i+1,op+['A']])
    if s == 'AC':
        if A != 0:
            dq.append([A-1,B,C+1,i+1,op+['C']])
        if C != 0:
            dq.append([A+1,B,C-1,i+1,op+['A']])
    if s == 'BC':
        if B != 0:
            dq.append([A,B-1,C+1,i+1,op+['C']])
        if C != 0:
            dq.append([A,B+1,C-1,i+1,op+['B']])


if i == N:
    print('Yes')
    for p in op:
        print(p)
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

q = queue.Queue()
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7
S = []
N, A, B, C = map(int,input().split())
ABC = 'ABC'
q = queue.Queue()
cnt = [A,B,C]
h = ''
q.put((cnt,0,h))
for n in range(N):
    s = input()
    s = s.replace('A','0').replace('B','1').replace('C','2')
    s = list(s)
    S.append(s)


i = 0
#print (S)
while(not q.empty()):
    cnt,d,h = q.get()
    
    #print (cnt,d,h)
    if (d > i):
        i+=1
        if (i==len(S)):
            print ('Yes')
            for k in h:
                print (k)
            exit()
    l,r = S[i]
    l  = int(l)
    r  = int(r)
    if (cnt[l] > 0):
        cnt_ = cnt[:]
        cnt_[l]-=1
        cnt_[r]+=1
        q.put((cnt_,d+1,h+ABC[r]))
        # cnt[l]+=1
        # cnt[r]-=1
    if (cnt[r] > 0):
        cnt_ = cnt[:]
        cnt_[r]-=1
        cnt_[l]+=1
        q.put((cnt_,d+1,h+ABC[l]))
        # cnt[r]+=1
        # cnt[l]-=1
print ('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, a, b, c = map(int, input().split())
choice = {(a, b, c, 0, 0, 0)}
order = defaultdict(tuple)

if min(n, a, b, c) == n:
    print("Yes")
    for i in range(n):
        print(input()[0])
    exit(0)

for i in range(n):
    s = input().rstrip()
    new_choice = set()
    new_order = defaultdict(tuple)
    for ch in choice:
        aa, bb, cc, na, nb, nc = ch
        if s == 'AB':
            if a >= n:
                new_choice.add((aa - 1, bb + 1, cc, na, nb + 1, nc))
                new_order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ('B',)
            elif b >= n:
                new_choice.add((aa + 1, bb - 1, cc, na + 1, nb, nc))
                new_order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ('A',)
            else:
                if bb > 0:
                    new_choice.add((aa + 1, bb - 1, cc, na + 1, nb, nc))
                    new_order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ('A',)
                if aa > 0:
                    new_choice.add((aa - 1, bb + 1, cc, na, nb + 1, nc))
                    new_order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ('B',)
        elif s == 'AC':
            if a >= n:
                new_choice.add((aa - 1, bb, cc + 1, na, nb, nc + 1))
                new_order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ('C',)
            elif c >= n:
                new_choice.add((aa + 1, bb, cc - 1, na + 1, nb, nc))
                new_order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ('A',)
            else:
                if cc > 0:
                    new_choice.add((aa + 1, bb, cc - 1, na + 1, nb, nc))
                    new_order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ('A',)
                if aa > 0:
                    new_choice.add((aa - 1, bb, cc + 1, na, nb, nc + 1))
                    new_order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ('C',)
        elif s == 'BC':
            if b >= n:
                new_choice.add((aa, bb - 1, cc + 1, na, nb, nc + 1))
                new_order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ('C',)
            elif c >= n:
                new_choice.add((aa, bb + 1, cc - 1, na, nb + 1, nc))
                new_order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ('B',)
            else:
                if cc > 0:
                    new_choice.add((aa, bb + 1, cc - 1, na, nb + 1, nc))
                    new_order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ('B',)
                if bb > 0:
                    new_choice.add((aa, bb - 1, cc + 1, na, nb, nc + 1))
                    new_order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ('C',)
        else:
            print("Error")
            exit(0)
    choice = new_choice
    order = new_order
    if not choice:
        print("No")
        exit(0)
ch = list(choice)[0]
print("Yes")
for x in order[(ch[3], ch[4], ch[5])]:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,A,B,C=map(int, input().split())
    S=[input().rstrip() for _ in range(N)]

    dp=[[[[None]*5 for _ in range(5)] for __ in range(5)] for ___ in range(N+4)]
    dp[0][min(4,A)][min(4,B)][min(4,C)]=1
    for i,s in enumerate(S):
        ni=i+1
        for a in range(5):
            for b in range(5):
                for c in range(5):
                    for j in range(2):
                        na,nb,nc=a,b,c
                        sel=None
                        if s=='AB':
                            if j==0:
                                if b==0: continue
                                na,nb=min(4,na+1),nb-1
                                sel='A'
                            else:
                                if a==0: continue
                                na,nb=na-1,min(4,nb+1)
                                sel='B'
                        elif s=='AC':
                            if j==0:
                                if c==0: continue
                                na,nc=min(4,na+1),nc-1
                                sel='A'
                            else:
                                if a==0: continue
                                na,nc=na-1,min(4,nc+1)
                                sel='C'
                        elif s=='BC':
                            if j==0:
                                if c==0: continue
                                nb,nc=min(4,nb+1),nc-1
                                sel='B'
                            else:
                                if b==0: continue
                                nb,nc=nb-1,min(4,nc+1)
                                sel='C'
                        if dp[i][a][b][c]: dp[ni][na][nb][nc]=(a,b,c,sel)

    flag=False
    ga,gb,gc=0,0,0
    for a in range(5):
        for b in range(5):
            for c in range(5):
                if dp[N][a][b][c]:
                    flag=True
                    ga,gb,gc=a,b,c
    if flag==False:
        print('No')
        return
    print('Yes')
    ans=[]
    for i in range(N,0,-1):
        ga,gb,gc,sel=dp[i][ga][gb][gc]
        ans.append(sel)
    for a in reversed(ans):
        print(a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

    N, A, B, C = map(int, input().split())

    cur = collections.defaultdict(int)
    cur[(A, B, C)] = ""
    for _ in range(N):
        s = input()
        temp = collections.defaultdict(int)
        for a, b, c in cur:
            if s == "AB":
                if b-1>=0:
                    temp[(a+1, b-1, c)] = cur[(a, b, c)] + 'A'
                if a-1>=0:
                    temp[(a-1, b+1, c)] = cur[(a, b, c)] + 'B'
            elif s == "AC":
                if c-1>=0:
                    temp[(a+1, b, c-1)] = cur[(a, b, c)] + 'A'
                if a-1>=0:
                    temp[(a-1, b, c+1)] = cur[(a, b, c)] + 'C'
            else:
                if b-1>=0:
                    temp[(a, b-1, c+1)] = cur[(a, b, c)] + 'C'
                if c-1>=0:
                    temp[(a, b+1, c-1)] = cur[(a, b, c)] + 'B'
        cur = temp

    if len(cur) > 0:
        print("Yes")
        for v in cur:
            for c in cur[v]:
                print(c)
            break
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C = map(int,input().split())

if A > N:
  A = N
if B > N:
  B = N
if C > N:
  C = N
  
# A + B + C : constant

Now = {(A,B,C) : ""}

Q = {"AB" : (1,-1,0), "AC" : (1,0,-1), "BC" : (0,1,-1)}

for i in range(N):
  q = input()
  Temp = {}
  for p, s in Now.items():
    p1 = (p[0] + Q[q][0], p[1] + Q[q][1], p[2] + Q[q][2])
    if p1[0] >= 0 and p1[1] >= 0 and p1[2] >= 0:
      Temp[p1] = s + q[0]
    p2 = (p[0] - Q[q][0], p[1] - Q[q][1], p[2] - Q[q][2])
    if p2[0] >= 0 and p2[1] >= 0 and p2[2] >= 0:
      Temp[p2] = s + q[1]
  Now = Temp.copy()

if len(Now) == 0:
  print('No')
else:
  print('Yes')
  ans = list(Now.values())[0]
  for i in range(N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C = map(int, input().split(" "))
commands = []
data = {
    'A': A,
    'B': B,
    'C': C
}
ans = [] 

if A >=1 and B >= 1 and C >= 1 :
    print("Yes")
    for _ in range(N) :
        command = input()
        if data[command[0]] > data[command[1]] :
            data[command[0]] -= 1
            data[command[1]] += 1
            print(command[1])
        else :
            data[command[0]] += 1
            data[command[1]] -= 1
            print(command[0]) 
else :
    safe = []
    commands = []
    for _ in range(N) :
        commands.append(input())

    fail = False
    i = 0 
    ans = []
    
    while i < N : 
        if data[commands[i][0]] == 0 and data[commands[i][1]] == 0 :
            if safe == [] :
                fail = True
                break
            else : 
                data, i, ans = safe.pop()
        elif data[commands[i][0]] == 1 and data[commands[i][1]] == 1 :
            _data = { 'A' :data['A'], 'B' :data['B'], 'C' :data['C'] }
            _i = i
            _ans = list(ans)
        
            _data[commands[i][1]] += 1
            _data[commands[i][0]] -= 1
            _ans.append( commands[i][1] )
            safe.append( [_data, _i, _ans] )  

            data[commands[i][0]] += 1
            data[commands[i][1]] -= 1
            ans.append( commands[i][0] )
        else :
            if data[commands[i][0]] > data[commands[i][1]] :
                x = commands[i][0] 
                y = commands[i][1] 
            else :
                x = commands[i][1] 
                y = commands[i][0]

            data[x] -= 1 
            data[y] += 1
            ans.append(y)

        i += 1

    if fail :
        print("No")
    else :
        print("Yes")
        for c in ans :
            print(c)

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c = map(int,input().split())
now = [[a,b,c,[]]]
for _ in range(n):
  q = input()
  tmp = []
  if q == 'AB':
    for x in now:
      a,b,c,his = x
      if a > 0:
        tmp.append([a-1,b+1,c,his+['B']])
      if b > 0:
        tmp.append([a+1,b-1,c,his+['A']])
  elif q == 'AC':
    for x in now:
      a,b,c,his = x
      if a > 0:
        tmp.append([a-1,b,c+1,his+['C']])
      if c > 0:
        tmp.append([a+1,b,c-1,his+['A']])
  else:
    for x in now:
      a,b,c,his = x
      if b > 0:
        tmp.append([a,b-1,c+1,his+['C']])
      if c > 0:
        tmp.append([a,b+1,c-1,his+['B']])
  if not tmp:
    print('No')
    exit()
  now = []
  now2 = []
  for d in range(3):
    m = max(tmp,key=lambda x:x[d])
    if m[:3] not in now2:
      now.append(m)
      now2.append(m[:3])
    m = min(tmp,key=lambda x:x[d])
    if m[:3] not in now2:
      now.append(m)
      now2.append(m[:3])
print('Yes')
ans = now[0][3]
for s in ans:
  print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, a, b, c = list(map(int, input().split()))
sys.setrecursionlimit(10 ** 6)
sl = [0] * n
for i in range(n):
    sl[i] = input()


def dfs(cnt, a, b, c, his):
    if a < 0 or b < 0 or c < 0:
        return

    if cnt == n:
        print('Yes')
        print(*list(his), sep="\n")
        exit()

    q = sl[cnt]
    if q == 'AB':
        dfs(cnt+1, a+1, b-1, c, his+'A')
        dfs(cnt+1, a-1, b+1, c, his+'B')
    elif q == 'AC':
        dfs(cnt+1, a+1, b, c-1, his+'A')
        dfs(cnt+1, a-1, b, c+1, his+'C')
    else:
        dfs(cnt+1, a, b-1, c+1, his+'C')
        dfs(cnt+1, a, b+1, c-1, his+'B')


dfs(0, a, b, c, '')
print('No')

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C = map(int,input().split())

if A > N:
  A = N
if B > N:
  B = N
if C > N:
  C = N
  
# A + B + C : constant

Now = {(A,B,C) : ""}

for i in range(N):
  q = input()
  Temp = {}
  if q == 'AB':
    a = [1,-1,0]
    b = [-1,1,0]
    sa = 'A'
    sb = 'B'
  elif q == 'AC':
    a = [1,0,-1]
    b = [-1,0,1]
    sa = 'A'
    sb = 'C'
  else:
    a = [0,1,-1]
    b = [0,-1,1]
    sa = 'B'
    sb = 'C'
  for p, s in Now.items():
    p1 = (p[0] + a[0], p[1] + a[1], p[2]+a[2])
    if p1[0] >= 0 and p1[1] >= 0 and p1[2] >= 0:
      Temp[p1] = s + sa
    p2 = (p[0] + b[0], p[1] + b[1], p[2]+b[2])
    if p2[0] >= 0 and p2[1] >= 0 and p2[2] >= 0:
      Temp[p2] = s + sb
  Now = Temp.copy()

if len(Now) == 0:
  print('No')
else:
  print('Yes')
  ans = list(Now.values())[0]
  for i in range(N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, a, b, c = map(int, input().split())
choice = {(a, b, c, 0, 0, 0)}
ss = [None] * n
order = defaultdict(tuple)

for i in range(n):
    s = input().rstrip()
    ss[i] = s
    new_choice = set()
    new_order = defaultdict(tuple)
    for ch in choice:
        aa, bb, cc, na, nb, nc = ch
        if s == 'AB':
            if bb > 0:
                new_choice.add((aa + 1, bb - 1, cc, na + 1, nb, nc))
                new_order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ('A',)
            if aa > 0:
                new_choice.add((aa - 1, bb + 1, cc, na, nb + 1, nc))
                new_order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ('B',)
        elif s == 'AC':
            if cc > 0:
                new_choice.add((aa + 1, bb, cc - 1, na + 1, nb, nc))
                new_order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ('A',)
            if aa > 0:
                new_choice.add((aa - 1, bb, cc + 1, na, nb, nc + 1))
                new_order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ('C',)
        elif s == 'BC':
            if cc > 0:
                new_choice.add((aa, bb + 1, cc - 1, na, nb + 1, nc))
                new_order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ('B',)
            if bb > 0:
                new_choice.add((aa, bb - 1, cc + 1, na, nb, nc + 1))
                new_order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ('C',)
        else:
            print("Error")
            exit(0)
    choice = new_choice
    order = new_order
    if not choice:
        print("No")
        exit(0)
ch = list(choice)[0]
print("Yes")
for x in order[(ch[3], ch[4], ch[5])]:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c = map(int,input().split())
now = [[a,b,c,[]]]
for _ in range(n):
  q = input()
  tmp = []
  if q == 'AB':
    for x in now:
      a,b,c,his = x
      if a > 0:
        tmp.append([a-1,b+1,c,his+['B']])
      if b > 0:
        tmp.append([a+1,b-1,c,his+['A']])
  elif q == 'AC':
    for x in now:
      a,b,c,his = x
      if a > 0:
        tmp.append([a-1,b,c+1,his+['C']])
      if c > 0:
        tmp.append([a+1,b,c-1,his+['A']])
  else:
    for x in now:
      a,b,c,his = x
      if b > 0:
        tmp.append([a,b-1,c+1,his+['C']])
      if c > 0:
        tmp.append([a,b+1,c-1,his+['B']])
  if not tmp:
    print('No')
    exit()
  now = []
  m = max(tmp,key=lambda x:x[0])
  if m not in now:
    now.append(m)
  m = min(tmp,key=lambda x:x[0])
  if m not in now:
    now.append(m)
  m = max(tmp,key=lambda x:x[1])
  if m not in now:
    now.append(m)
  m = min(tmp,key=lambda x:x[1])
  if m not in now:
    now.append(m)
  m = max(tmp,key=lambda x:x[2])
  if m not in now:
    now.append(m)
  m = min(tmp,key=lambda x:x[2])
  if m not in now:
    now.append(m)
print('Yes')
ans = now[0][3]
for s in ans:
  print(s)

Submission status: Time Limit Exceeded

Solution code:
N, A, B, C = map(int,input().split())

if A > N:
  A = N
if B > N:
  B = N
if C > N:
  C = N
  
# A + B + C : constant

Now = {(A,B,C) : ""}

for i in range(N):
  q = input()
  Temp = {}
  if q == 'AB':
    a = [1,-1,0]
    b = [-1,1,0]
    sa = 'A'
    sb = 'B'
  elif q == 'AC':
    a = [1,0,-1]
    b = [-1,0,1]
    sa = 'A'
    sb = 'C'
  else:
    a = [0,1,-1]
    b = [0,-1,1]
    sa = 'B'
    sb = 'C'
  for p, s in Now.items():
    p1 = (p[0] + a[0], p[1] + a[1], p[2]+a[2])
    if p1[0] >= 0 and p1[1] >= 0 and p1[2] >= 0:
      Temp[p1] = s + sa
    p2 = (p[0] + b[0], p[1] + b[1], p[2]+b[2])
    if p2[0] >= 0 and p2[1] >= 0 and p2[2] >= 0:
      Temp[p2] = s + sb
  Now = Temp.copy()

if len(Now) == 0:
  print('No')
else:
  print('Yes')
  ans = list(Now.values())[0]
  for i in range(N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, a, b, c = map(int, input().split())
choice = {(a, b, c, 0, 0, 0)}
ss = [None] * n
order = defaultdict(list)

for i in range(n):
    s = input().rstrip()
    ss[i] = s
    new_choice = set()
    for ch in choice:
        aa, bb, cc, na, nb, nc = ch
        if s == 'AB':
            if bb > 0:
                new_choice.add((aa + 1, bb - 1, cc, na + 1, nb, nc))
                order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ['A']
            if aa > 0:
                new_choice.add((aa - 1, bb + 1, cc, na, nb + 1, nc))
                order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ['B']
        elif s == 'AC':
            if cc > 0:
                new_choice.add((aa + 1, bb, cc - 1, na + 1, nb, nc))
                order[(na + 1, nb, nc)] = order[(na, nb, nc)] + ['A']
            if aa > 0:
                new_choice.add((aa - 1, bb, cc + 1, na, nb, nc + 1))
                order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ['C']
        elif s == 'BC':
            if cc > 0:
                new_choice.add((aa, bb + 1, cc - 1, na, nb + 1, nc))
                order[(na, nb + 1, nc)] = order[(na, nb, nc)] + ['B']
            if bb > 0:
                new_choice.add((aa, bb - 1, cc + 1, na, nb, nc + 1))
                order[(na, nb, nc + 1)] = order[(na, nb, nc)] + ['C']
        else:
            print("Error")
            exit(0)
    choice = new_choice
    if not choice:
        print("No")
        exit(0)
ch = list(choice)[0]
print("Yes")
for x in order[(ch[3], ch[4], ch[5])]:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,a,b,c = get_nums_l()
d = {
    "A": a,
    "B": b,
    "C": c
}
S = []
for _ in range(n):
    S.append(input())

def dfs(i, x, history):

    if d[S[i][1-x]] == 0:
        return False

    d[S[i][x]] += 1
    d[S[i][1-x]] -= 1

    history.append(S[i][x])

    if i == n-1:
        return True

    ok = dfs(i+1, 0, history)
    if ok:
        return ok

    ok = dfs(i+1, 1, history)

    if ok:
        return ok

    # バックトラック
    history.pop()
    d[S[i][x]] -= 1
    d[S[i][1-x]] += 1

    return False

history = deque()
ok = dfs(0, 0, history) or dfs(0, 1, history)

print("Yes" if ok else "No")
if ok:
    for s in history:
        print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

N, A, B, C = map(int,input().split())
Q = []
for _ in range(N):
    Q.append(input())

def check(i, A, B, C):
    if A < 0 or B < 0 or C < 0:
        return False
    if Q[i] == 'AB':
        return not (A == 0 and B == 0)
    if Q[i] == 'AC':
        return not (A == 0 and C == 0)
    return not (B == 0 and C == 0)

def solve(L, A, B, C):
    if len(L) == N:
        return L
    i = len(L)
    if i == N-1:
        if Q[i] == 'AB':
            if A == 0 and B == 0:
                return 'No'
            if A == 0:
                return solve(L + ['A'], A+1, B-1, C)
            return solve(L + ['B'], A-1, B+1, C)
        if Q[i] == 'AC':
            if A == 0 and C == 0:
                return 'No'
            if A == 0:
                return solve(L + ['A'], A+1, B, C-1)
            return solve(L + ['C'], A-1, B, C+1)
        if Q[i] == 'BC':
            if B == 0 and C == 0:
                return 'No'
            if B == 0:
                return solve(L + ['B'], A, B+1, C-1)
            return solve(L + ['C'], A, B-1, C+1)
    if not check(i, A, B, C):
        return 'No'
    if Q[i] == 'AB':
        if check(i+1, A+1, B-1, C):
            return solve(L + ['A'], A+1, B-1, C)
        if check(i+1, A-1, B+1, C):
            return solve(L + ['B'], A-1, B+1, C)
        return 'No'
    if Q[i] == 'AC':
        if check(i+1, A+1, B, C-1):
            return solve(L + ['A'], A+1, B, C-1)
        if check(i+1, A-1, B, C+1):
            return solve(L + ['C'], A-1, B, C+1)
        return 'No'
    if Q[i] == 'BC':
        if check(i+1, A, B+1, C-1):
            return solve(L + ['B'], A, B+1, C-1)
        if check(i+1, A, B-1, C+1):
            return solve(L + ['C'], A, B-1, C+1)
        return 'No'

ans = solve([], A, B, C)

if ans == 'No':
    print('No')
else:
    print('Yes')
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, A: int, B: int, C: int, S: "List[str]"):
    L = 'ABC'
    def rec(i, a, b, c, ll):
        if i == N:
            return ll
        s = S[i]
        vals = [a, b, c]
        if s == 'AB':
            u, v = 0, 1
        if s == 'BC':
            u, v = 1, 2
        if s == 'AC':
            u, v = 0, 2

        if vals[u] == 0 and vals[v] == 0:
            return False
        elif vals[u] == 0:
            vals[u] += 1
            vals[v] -= 1
            return rec(i + 1, vals[0], vals[1], vals[2], ll + L[u])
        elif vals[v] == 0:
            vals[u] -= 1
            vals[v] += 1
            return rec(i + 1, vals[0], vals[1], vals[2], ll + L[v])
        else:
            if vals[u] > vals[v]:
                u, v = v, u
            vals[u] += 1
            vals[v] -= 1
            tmp = rec(i + 1, vals[0], vals[1], vals[2], ll + L[u])
            if tmp:
                return tmp
            else:
                vals[u] -= 2
                vals[v] += 2
                return rec(i + 1, vals[0], vals[1], vals[2], ll + L[v])

    ret = rec(0, A, B, C, '')
    if ret:
        print('Yes')
        for c in ret:
            print(c)
        '''
        vals = [A, B, C]
        for i in range(N):
            x = S[i]
            c = ret[i]
            for d in x:
                k = L.find(d)
                if d == c:
                    vals[k] += 1
                else:
                    vals[k] -= 1
            print(x, c)
            print(vals)
        '''
    else:
        print('No')

    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))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, A, B, C, s)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)

N,A,B,C=[int(i) for i in input().split(" ")]
cmds=[]
for i in range(N):
    cmds.append(input())

@lru_cache(maxsize=None)
def game(i,A,B,C):
    if i==N:
        if A>=0 and B>=0 and C>=0:
            return True,[]
        else:
            return False,[]
    cmd=cmds[i]
    if cmd=="AB":

        if A==0 and B==0:
            return False,[]
        g1= game(i+1,A-1,B+1,C)
        if g1[0]:
            return g1[0],g1[1]+["B"]
        g2=game(i+1,A+1,B-1,C)
        if g2[0]:
            return g2[0],g2[1]+["A"]
        else:
            return False,[]

    elif cmd=="AC":
            if A==0 and C==0:
                return False,[]
            g1= game(i+1,A-1,B,C+1)
            if g1[0]:
                return g1[0],g1[1]+["C"]
            g2=game(i+1,A+1,B,C-1)
            if g2[0]:
                return g2[0],g2[1]+["A"]
            else:
                return False,[]
    else:
            if C==0 and B==0:
                return False,[]
            g1= game(i+1,A,B+1,C-1)
            if g1[0]:
                return g1[0],g1[1]+["B"]
            g2=game(i+1,A,B-1,C+1)
            if g2[0]:
                return g2[0],g2[1]+["C"]
            else:
                return False,[]



suc,his=game(0,A,B,C)
if suc:
    print("Yes")
    for h in his[::-1]:
        print(h)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N,A,B,C = list(map(int,input().split()))
import sys
input = sys.stdin.readline
S = tuple(input().strip() for i in range(N))
tup = [A,B,C]

def idx(ch):
  return "ABC".index(ch)

def search(ABC,path):
  res = ""
  for i,(l1,l2) in enumerate(path):
    if ABC[idx(l1)] > ABC[idx(l2)]:
      ABC[idx(l1)] -= 1
      ABC[idx(l2)] += 1
      res += l2
    elif ABC[idx(l1)] < ABC[idx(l2)]:
      ABC[idx(l1)] += 1
      ABC[idx(l2)] -= 1
      res += l1
    elif ABC[idx(l1)] + ABC[idx(l2)]== 0:
      return False,""
    elif ABC[idx(l1)] + ABC[idx(l2)] >= 4:
      ABC[idx(l1)] += 1
      res += l1
      ABC[idx(l2)] -= 1
    else:
      # 両方のpathを探索する
      ABC_j = [i for i in ABC]
      ABC_j[idx(l1)] += 1
      ABC_j[idx(l2)] -= 1
      
      ABC_k = [i for i in ABC]
      ABC_k[idx(l1)] -= 1
      ABC_k[idx(l2)] += 1
      
      jT,jpath = search(ABC_j,path[i:])
      if jT:
        return jT,res + jpath
      
      kT,kpath = search(ABC_k,path[i:])
      if kT:
        return kT,res + kpath
      return False, ""
  else:
    return True,res
res, p = search(tup,S)
if res:
  print("Yes")
  for c in p:
    print(c)
else:
  print("No")