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

sys.setrecursionlimit(1000000)


def recur1(a, b, c, ls: [], ans: []):
    s = ls[0]
    if s == "AB":
        if a == 0 and b == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if len(ls) == 1:
                return True, ans
            return recur1(a + 1, b - 1, c, ls[1:], ans)
        else:
            ans.append("B")
            if len(ls) == 1:
                return True, ans
            return recur1(a - 1, b + 1, c, ls[1:], ans)
    elif s == "AC":
        if a == 0 and c == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if len(ls) == 1:
                return True, ans
            return recur1(a + 1, b, c - 1, ls[1:], ans)
        else:
            ans.append("C")
            if len(ls) == 1:
                return True, ans
            return recur1(a - 1, b, c + 1, ls[1:], ans)
    else:
        if b == 0 and c == 0:
            return False, []
        elif b == 0:
            ans.append("B")
            if len(ls) == 1:
                return True, ans
            return recur1(a, b + 1, c - 1, ls[1:], ans)
        else:
            ans.append("C")
            if len(ls) == 1:
                return True, ans
            return recur1(a, b - 1, c + 1, ls[1:], ans)


def recur2(a, b, c, ls: [], ans: []):
    s = ls[0]
    ln = len(ls)
    if s == "AB":
        if a == 0 and b == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if ln == 1:
                return True, ans
            return recur2(1, b - 1, c, ls[1:], ans)
        elif b == 0:
            ans.append("B")
            if ln == 1:
                return True, ans
            return recur2(a - 1, 1, c, ls[1:], ans)
        else:
            if ln == 1:
                ans.append("A")
                return True, ans
            nex = ls[1]
            if nex == "BC":
                ans.append("B")
                ans.append("C")
                if ln == 2:
                    return True, ans
                return recur2(0, 1, 1, ls[2:], ans)
            elif nex == "AC":
                ans.append("A")
                ans.append("C")
                if ln == 2:
                    return True, ans
                return recur2(1, 0, 1, ls[2:], ans)
            else:
                ans.append("A")
                ans.append("B")
                if ln == 2:
                    return True, ans
                return recur2(1, 1, 0, ls[2:], ans)
    elif s == "AC":
        if a == 0 and c == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if ln == 1:
                return True, ans
            return recur2(a + 1, b, c - 1, ls[1:], ans)
        elif c == 0:
            ans.append("C")
            if ln == 1:
                return True, ans
            return recur2(a - 1, b, c + 1, ls[1:], ans)
        else:
            if ln == 1:
                ans.append("A")
                return True, ans
            nex = ls[1]
            if nex == "AB":
                ans.append("A")
                ans.append("B")
                if ln == 2:
                    return True, ans
                return recur2(1, 1, 0, ls[2:], ans)
            elif nex == "BC":
                ans.append("C")
                ans.append("B")
                if ln == 2:
                    return True, ans
                return recur2(0, 1, 1, ls[2:], ans)
            else:
                ans.append("A")
                ans.append("C")
                if ln == 2:
                    return True, ans
                return recur2(1, 0, 1, ls[2:], ans)
    else:
        if c == 0 and b == 0:
            return False, []
        elif c == 0:
            ans.append("C")
            if ln == 1:
                return True, ans
            return recur2(a, b - 1, c + 1, ls[1:], ans)
        elif b == 0:
            ans.append("B")
            if ln == 1:
                return True, ans
            return recur2(a, b + 1, c - 1, ls[1:], ans)
        else:
            if ln == 1:
                ans.append("C")
                return True, ans
            nex = ls[1]
            if nex == "AB":
                ans.append("B")
                ans.append("A")
                if ln == 2:
                    return True, ans
                return recur2(1, 1, 0, ls[2:], ans)
            if nex == "AC":
                ans.append("C")
                ans.append("A")
                if ln == 2:
                    return True, ans
                return recur2(1, 0, 1, ls[2:], ans)
            else:
                ans.append("B")
                ans.append("C")
                return recur2(0, 1, 1, ls[2:], ans)


def recur3(a, b, c, ls: [], ans: []):
    s = ls[0]
    ln = len(ls)
    if s == "AB":
        if a == 0 and b == 0:
            return False, []
        else:
            if a >= b:
                ans.append("B")
                if ln == 1:
                    return True, ans
                return recur3(a - 1, b + 1, c, ls[1:], ans)
            else:
                ans.append("A")
                if ln == 1:
                    return True, ans
                return recur3(a + 1, b - 1, c, ls[1:], ans)
    elif s == "BC":
        if b == 0 and c == 0:
            return False, []
        else:
            if b >= c:
                ans.append("C")
                if ln == 1:
                    return True, ans
                return recur3(a, b - 1, c+1, ls[1:], ans)
            else:
                ans.append("B")
                if ln == 1:
                    return True, ans
                return recur3(a, b + 1, c-1, ls[1:], ans)
    else:
        if a == 0 and c == 0:
            return False, []
        else:
            if a >= c:
                ans.append("C")
                if ln == 1:
                    return True, ans
                return recur3(a - 1, b, c+1, ls[1:], ans)
            else:
                ans.append("A")
                if ln == 1:
                    return True, ans
                return recur3(a + 1, b, c-1, ls[1:], ans)


def main():
    n, a, b, c = map(int, input().split())
    s_ls = []
    for i in range(n):
        s_ls.append(input())

    if a + b + c == 0:
        print("No")
        return

    res = True
    ans = []
    if a + b + c == 1:
        res, ans = recur1(a, b, c, s_ls, ans)
    elif a + b + c == 2:
        res, ans = recur2(a, b, c, s_ls, ans)
    else:
        res, ans = recur3(a, b, c, s_ls, ans)

    if res:
        print("Yes")
        for x in ans:
            print(x)
    else:
        print("No")


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)


def recur1(a, b, c, ls: [], ans: []):
    s = ls[0]
    if s == "AB":
        if a == 0 and b == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if len(ls) == 1:
                return True, ans
            return recur1(a + 1, b - 1, c, ls[1:], ans)
        else:
            ans.append("B")
            if len(ls) == 1:
                return True, ans
            return recur1(a - 1, b + 1, c, ls[1:], ans)
    elif s == "AC":
        if a == 0 and c == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if len(ls) == 1:
                return True, ans
            return recur1(a + 1, b, c - 1, ls[1:], ans)
        else:
            ans.append("C")
            if len(ls) == 1:
                return True, ans
            return recur1(a - 1, b, c + 1, ls[1:], ans)
    else:
        if b == 0 and c == 0:
            return False, []
        elif b == 0:
            ans.append("B")
            if len(ls) == 1:
                return True, ans
            return recur1(a, b + 1, c - 1, ls[1:], ans)
        else:
            ans.append("C")
            if len(ls) == 1:
                return True, ans
            return recur1(a, b - 1, c + 1, ls[1:], ans)


def recur2(a, b, c, ls: [], ans: []):
    s = ls[0]
    ln = len(ls)
    if s == "AB":
        if a == 0 and b == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if ln == 1:
                return True, ans
            return recur2(a + 1, b - 1, c, ls[1:], ans)
        elif b == 0:
            ans.append("B")
            if ln == 1:
                return True, ans
            return recur2(a - 1, b + 1, c, ls[1:], ans)
        else:
            if ln == 1:
                ans.append("A")
                return True, ans
            nex = ls[1]
            if nex == "BC":
                ans.append("B")
                return recur2(a - 1, b + 1, c, ls[1:], ans)
            else:
                ans.append("A")
                return recur2(a + 1, b - 1, c, ls[1:], ans)
    elif s == "AC":
        if a == 0 and c == 0:
            return False, []
        elif a == 0:
            ans.append("A")
            if ln == 1:
                return True, ans
            return recur2(a + 1, b, c - 1, ls[1:], ans)
        elif c == 0:
            ans.append("C")
            if ln == 1:
                return True, ans
            return recur2(a - 1, b, c + 1, ls[1:], ans)
        else:
            if ln == 1:
                ans.append("A")
                return True, ans
            nex = ls[1]
            if nex == "AB":
                ans.append("A")
                return recur2(a + 1, b, c - 1, ls[1:], ans)
            else:
                ans.append("C")
                return recur2(a - 1, b, c + 1, ls[1:], ans)
    else:
        if c == 0 and b == 0:
            return False, []
        elif c == 0:
            ans.append("C")
            if ln == 1:
                return True, ans
            return recur2(a, b - 1, c + 1, ls[1:], ans)
        elif b == 0:
            ans.append("B")
            if ln == 1:
                return True, ans
            return recur2(a, b + 1, c - 1, ls[1:], ans)
        else:
            if ln == 1:
                ans.append("C")
                return True, ans
            nex = ls[1]
            if nex == "AB":
                ans.append("B")
                return recur2(a, b + 1, c - 1, ls[1:], ans)
            else:
                ans.append("C")
                return recur2(a, b - 1, c + 1, ls[1:], ans)


def recur3(a, b, c, ls: [], ans: []):
    s = ls[0]
    ln = len(ls)
    if s == "AB":
        if a == 0 and b == 0:
            return False, []
        else:
            if a >= b:
                ans.append("B")
                if ln == 1:
                    return True, ans
                return recur3(a - 1, b + 1, c, ls[1:], ans)
            else:
                ans.append("A")
                if ln == 1:
                    return True, ans
                return recur3(a + 1, b - 1, c, ls[1:], ans)
    elif s == "BC":
        if b == 0 and c == 0:
            return False, []
        else:
            if b >= c:
                ans.append("C")
                if ln == 1:
                    return True, ans
                return recur3(a, b - 1, c+1, ls[1:], ans)
            else:
                ans.append("B")
                if ln == 1:
                    return True, ans
                return recur3(a, b + 1, c-1, ls[1:], ans)
    else:
        if a == 0 and c == 0:
            return False, []
        else:
            if a >= c:
                ans.append("C")
                if ln == 1:
                    return True, ans
                return recur3(a - 1, b, c+1, ls[1:], ans)
            else:
                ans.append("A")
                if ln == 1:
                    return True, ans
                return recur3(a + 1, b, c-1, ls[1:], ans)


def main():
    n, a, b, c = map(int, input().split())
    s_ls = []
    for i in range(n):
        s_ls.append(input())

    if a + b + c == 0:
        print("No")
        return
    
    res = True
    ans = []
    if a + b + c == 1:
        res, ans = recur1(a, b, c, s_ls, ans)
    elif a + b + c == 2:
        res, ans = recur2(a, b, c, s_ls, ans)
    else:
        res, ans = recur3(a, b, c, s_ls, ans)

    if res:
        print("Yes")
        for x in ans:
            print(x)
    else:
        print("No")


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)


def recur(current_a, current_b, current_c, ls: [], ans: []):
    s = ls[0]
    if s == "AB":
        if current_a == 0 and current_b == 0:
            return False, []
        elif current_a == 0:
            ans.append("A")
            if len(ls) == 1:
                return True, ans
            ans_1 = ans[:]
            return recur(current_a + 1, current_b - 1, current_c, ls[1:], ans_1)
        elif current_b == 0:
            ans.append("B")
            if len(ls) == 1:
                return True, ans
            ans_1 = ans[:]
            return recur(current_a - 1, current_b + 1, current_c, ls[1:], ans_1)
        else:
            if len(ls) == 1:
                ans.append("A")
                return True, ans

            ans_1 = ans[:]
            ans_1.append("A")
            res, ans_1 = recur(current_a + 1, current_b - 1, current_c, ls[1:], ans_1)
            if res:
                return True, ans_1

            ans.append("B")
            return recur(current_a - 1, current_b + 1, current_c, ls[1:], ans)
    elif s == "AC":
        if current_a == 0 and current_c == 0:
            return False, []
        elif current_a == 0:
            ans.append("A")
            if len(ls) == 1:
                return True, ans
            return recur(current_a + 1, current_b, current_c - 1, ls[1:], ans)
        elif current_c == 0:
            ans.append("C")
            if len(ls) == 1:
                return True, ans
            return recur(current_a - 1, current_b, current_c + 1, ls[1:], ans)
        else:
            if len(ls) == 1:
                ans.append("A")
                return True, ans

            ans_1 = ans[:]
            ans_1.append("A")
            res, ans_1 =recur(current_a + 1, current_b, current_c - 1, ls[1:], ans_1)
            if res:
                return True, ans_1

            ans.append("C")
            return recur(current_a - 1, current_b, current_c + 1, ls[1:], ans)
    elif s == "BC":
        if current_b == 0 and current_c == 0:
            return False, []
        elif current_b == 0:
            ans.append("B")
            if len(ls) == 1:
                return True, ans
            return recur(current_a, current_b + 1, current_c - 1, ls[1:], ans)
        elif current_c == 0:
            ans.append("C")
            if len(ls) == 1:
                return True, ans
            return recur(current_a, current_b - 1, current_c + 1, ls[1:], ans)
        else:
            if len(ls) == 1:
                ans.append("B")
                return True, ans

            ans_1 = ans[:]
            ans_1.append("B")
            res, ans_1 = recur(current_a, current_b + 1, current_c - 1, ls[1:], ans_1)
            if res:
                return True, ans_1

            ans.append("C")
            return recur(current_a, current_b - 1, current_c + 1, ls[1:], ans)


def main():
    n, a, b, c = map(int, input().split())
    s_ls = []
    for i in range(n):
        s_ls.append(input())

    ans = []
    res, ans = recur(a, b, c, s_ls, ans)
    if res:
        print("Yes")
        for x in ans:
            print(x)
    else:
        print("No")


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
def inpl(): return list(map(int, sys.stdin.readline().split()))
n = inpl()
s = []
for i in range(n[0]):
    word = input()
    s.append(word)
A = n[1]
B = n[2]
C = n[3]
def dfs(a,b,c,tmp,step):
    if a < 0 or b < 0 or c < 0:
        return []
    if step == n[0]:
        return tmp
    for j in range(step, len(s)):
        if s[j] == "AB":
            tmp_tmp = dfs(a + 1, b-1, c, tmp + ["A"], step + 1)
            if tmp_tmp:
                return tmp_tmp
            else:
                return dfs(a-1, b+1, c, tmp + ["B"], step + 1)
        elif s[j] == "AC":
            tmp_tmp = dfs(a+1, b, c-1, tmp +["A"], step + 1)
            if tmp_tmp:
                return tmp_tmp
            else:
                return dfs(a-1, b, c + 1, tmp + ["C"], step + 1)
        else:
            tmp_tmp = dfs(a, b + 1, c-1, tmp + ["B"], step + 1)
            if tmp_tmp:
                return tmp_tmp
            else:
                return dfs(a, b - 1, c + 1, tmp + ["C"], step+ 1)
ans = dfs(A,B,C,[],0)
if ans:
    print("Yes")
    for i in range(len(ans)):
        print(ans[i])
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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')
        for s in str(his):
            if s == '1':
                print('A')
            elif s == '2':
                print('B')
            else:
                print('C')
        exit()

    q = sl[cnt]
    if q == 'AB':
        dfs(cnt+1, a+1, b-1, c, his*10+1)
        dfs(cnt+1, a-1, b+1, c, his*10+2)
    elif q == 'AC':
        dfs(cnt+1, a+1, b, c-1, his*10+1)
        dfs(cnt+1, a-1, b, c+1, his*10+3)
    else:
        dfs(cnt+1, a, b-1, c+1, his*10+3)
        dfs(cnt+1, a, b+1, c-1, his*10+2)


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

Submission status: Time Limit Exceeded

Solution code:
import sys

s=[]
ans=[]
 
def dfs(a,b,c,i,root):
    if i==n:
        global ans
        ans=root.copy()
        return True
    l=False
    r=False
    if s[i]=='AB':
        if a>0:
            root.append('B')
            l=dfs(a-1,b+1,c,i+1,root)
            root.pop()
        if b>0:
            root.append('A')
            r=dfs(a+1,b-1,c,i+1,root)
            root.pop()
    elif s[i]=='AC':
        if a>0:
            root.append('C')
            l=dfs(a-1,b,c+1,i+1,root)
            root.pop()
        if c>0:
            root.append('A')
            r=dfs(a+1,b,c-1,i+1,root)
            root.pop()
    else:
        if b>0:
            root.append('C')
            l=dfs(a,b-1,c+1,i+1,root)
            root.pop()
        if c>0:
            root.append('B')
            r=dfs(a,b+1,c-1,i+1,root)
            root.pop()
    return l or r
 
sys.setrecursionlimit(10**6)
n,a,b,c=map(int,input().split())
s=['']*n
for i in range(n):
    s[i]=input()
flag=dfs(a,b,c,0,[])
 
if flag:
    print("Yes")
    for t in ans:
        print(t)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n,a,b,c = map(int, input().split())
ref = [[a,b,c,[]]]
for i in range(n):
    nxt = []
    roun = []
    s = input()
    for l in ref:
        if s == "AB":
            if l[1]>0:
                path = [i for i in l[3]]
                path.append("A")
                if [l[0]+1,l[1]-1,l[2]] not in roun:
                    nxt.append([l[0]+1,l[1]-1,l[2],path])
                    roun.append([l[0]+1,l[1]-1,l[2]])
            if l[0]>0:
                path = [i for i in l[3]]
                path.append("B")
                if [l[0]-1,l[1]+1,l[2]] not in roun:
                    nxt.append([l[0]-1,l[1]+1,l[2],path])
                    roun.append([l[0]-1,l[1]+1,l[2]])
        elif s == "AC":
            if l[2]>0:
                path = [i for i in l[3]]
                path.append("A")
                if [l[0]+1,l[1],l[2]-1] not in roun:
                    nxt.append([l[0]+1,l[1],l[2]-1,path])
                    roun.append([l[0]+1,l[1],l[2]-1])
            if l[0]>0:
                path = [i for i in l[3]]
                path.append("C")
                if [l[0]-1,l[1],l[2]+1] not in roun:
                    nxt.append([l[0]-1,l[1],l[2]+1,path])
                    roun.append([l[0]-1,l[1],l[2]+1])
        elif s == "BC":
            if l[2]>0:
                path = [i for i in l[3]]
                path.append("B")
                if [l[0],l[1]+1,l[2]-1] not in roun:
                    nxt.append([l[0],l[1]+1,l[2]-1,path])
                    roun.append([l[0],l[1]+1,l[2]-1])
            if l[1]>0:
                path = [i for i in l[3]]
                path.append("C")
                if [l[0],l[1]-1,l[2]+1] not in roun:
                    nxt.append([l[0],l[1]-1,l[2]+1,path])
                    roun.append([l[0],l[1]-1,l[2]+1])
        else: pass
    
    ref = nxt

if ref!=[]:
    print("Yes")
    for i in ref[0][3]:
        print(i)
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10**6)

N, *number = map(int, input().split())
s_list = [input() for i in range(N)]


def solve(i, n_list, s):
    if i == N:
        print("Yes")
        for a in s:
            print(a)
        exit()
    if s_list[i] == "AB":
        if n_list[0] - 1 >= 0:
            solve(i + 1, n_list + np.array([-1, 1, 0]), s + ["B"])
        if n_list[1] - 1 >= 0:
            solve(i + 1, n_list + np.array([1, -1, 0]), s + ["A"])
    elif s_list[i] == "AC":
        if n_list[0] - 1 >= 0:
            solve(i + 1, n_list + np.array([-1, 0, 1]), s + ["C"])
        if n_list[2] - 1 >= 0:
            solve(i + 1, n_list + np.array([1, 0, -1]), s + ["A"])
    else:
        if n_list[1] - 1 >= 0:
            solve(i + 1, n_list + np.array([0, -1, 1]), s + ["C"])
        if n_list[2] - 1 >= 0:
            solve(i + 1, n_list + np.array([0, 1, -1]), s + ["B"])


solve(0, np.array(number), [])
print("No")

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

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

# process
dq = deque()
dq.append((A, B, C, []))

for i, s in enumerate(S):
    l = len(dq)
    for _ in range(l):
        a, b, c, op = list(dq.popleft())
        
        if a < 0 or b < 0 or c < 0:
            continue

        op1 = op
        op2 = copy.copy(op)
        if s == "AB":
            op1.append("A")
            op2.append("B")
            dq.append((a+1, b-1, c, op1))
            dq.append((a-1, b+1, c, op2))
        elif s == "BC":
            op1.append("B")
            op2.append("C")
            dq.append((a, b+1, c-1, op1))
            dq.append((a, b-1, c+1, op2))
        else:
            op1.append("A")
            op2.append("C")
            dq.append((a+1, b, c-1, op1))
            dq.append((a-1, b, c+1, op2))

# output
operation = []
for a, b, c, op in dq:
    if a >= 0 and b >= 0 and c >= 0:
        operation = op
        break

if operation == []:
    print("No")
else:
    print("Yes")
    [print(x) for x in operation]

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,a,b,c=map(int,input().split())
s=[input() for i in range(n)]
dp=[dict() for i in range(n+1)]
dp[0][(a,b,c)]=""
for i in range(n):
    if len(dp[i])==0:
        print("No")
        break
    if s[i][0]=="A" and s[i][1]=="B":
        #print(0)
        for j in dp[i]:
            a,b,c=j
            if a>0:
                dp[i+1][(a-1,b+1,c)]=dp[i][j]+"B"
            if b>0:
                dp[i+1][(a+1,b-1,c)]=dp[i][j]+"A"
    elif s[i][0]=="A" and s[i][1]=="C":
        #print(1)
        for j in dp[i]:
            a,b,c=j
            if a>0:
                dp[i+1][(a-1,b,c+1)]=dp[i][j]+"C"
            if c>0:
                dp[i+1][(a+1,b,c-1)]=dp[i][j]+"A"
    else:
        #print(2)
        for j in dp[i]:
            a,b,c=j
            if b>0:
                dp[i+1][(a,b-1,c+1)]=dp[i][j]+"C"
            if c>0:
                dp[i+1][(a,b+1,c-1)]=dp[i][j]+"B"
else:
    if len(dp[n])==0:
        print("No")
    else:
        print("Yes")
        #print(dp)
        z=list(dp[n].items())
        #print(z)
        for i in range(n):
            print(z[0][1][i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N, A, B, C = map(int, input().split())
    S_lsit = []
    for i in range(N):
        S_lsit.append(input())
    x, y, z = 0, 0, 0
    for S in S_lsit:
        if S == "AB":
            x += 1
        elif S == "BC":
            y += 1
        else:
            z += 1
    a_ac, b_ac, c_ac = -1, -1, -1
    for a in range(x+1):
        for b in range(y+1):
            for c in range(z+1):
                if (A -2*a +x +2*c -z) >= 0 \
                    and (B -2*b +y +2*a -x) >= 0 \
                    and (C -2*c +z +2*b -y) >= 0:
                    a_ac, b_ac, c_ac = a, b, c
                    break
                    break
                    break
    #print([a_ac, b_ac, c_ac])
    if a_ac==-1 or b_ac==-1 or c_ac==-1:
        print("No")
    else:
        print("Yes")
        for S in S_lsit:
            if S == "AB":
                if a_ac >= 1 and A >= 1:
                    print("B")
                    A -= 1
                    B += 1
                    a_ac -= 1
                else:
                    print("A")
                    A += 1
                    B -= 1
            elif S == "BC":
                if b_ac >= 1 and B >= 1:
                    print("C")
                    B -= 1
                    C += 1
                    b_ac -= 1
                else:
                    print("B")
                    B += 1
                    C -= 1
            else:
                if c_ac >= 1 and C >= 1:
                    print("A")
                    C -= 1
                    A += 1
                    c_ac -= 1
                else:
                    print("C")
                    C += 1
                    B -= 1
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,a,b,c=map(int,input().split())
s=[input() for i in range(n)]
dp=[dict() for i in range(n+1)]
dp[0][""]=[a,b,c]
for i in range(n):
    if len(dp[i])==0:
        print("No")
        break
    if s[i][0]=="A" and s[i][1]=="B":
        #print(0)
        for j in dp[i]:
            a,b,c=dp[i][j]
            if dp[i][j][0]>0:
                dp[i+1][j+"B"]=[a-1,b+1,c]
            if dp[i][j][1]>0:
                dp[i+1][j+"A"]=[a+1,b-1,c]
    elif s[i][0]=="A" and s[i][1]=="C":
        #print(1)
        for j in dp[i]:
            a,b,c=dp[i][j]
            if dp[i][j][0]>0:
                dp[i+1][j+"C"]=[a-1,b,c+1]
            if dp[i][j][2]>0:
                dp[i+1][j+"A"]=[a+1,b,c-1]
    else:
        #print(2)
        for j in dp[i]:
            a,b,c=dp[i][j]
            if dp[i][j][1]>0:
                dp[i+1][j+"C"]=[a,b-1,c+1]
            if dp[i][j][2]>0:
                dp[i+1][j+"B"]=[a,b+1,c-1]
else:
    if len(dp[n])==0:
        print("No")
    else:
        print("Yes")
        #print(dp)
        z=list(dp[-1])
        #print(z)
        for i in range(n):
            print(z[-1][i])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, A, B, C = lmi()
S = [input().strip() for _ in range(N)]

a = A
b = B
total = A + B + C
ans = []
if total != 2:
    for s in S:
        c = total - a - b
        if s == "AB":
            if a == 0 and b == 0:
                print("No")
                exit()
            if a > b:
                a -= 1
                b += 1
                ans.append('B')
            else:
                a += 1
                b -= 1
                ans.append('A')
        if s == "AC":
            if a == 0 and c == 0:
                print("No")
                exit()
            if a > c:
                a -= 1
                ans.append('C')
            else:
                a += 1
                ans.append('A')
        if s == "BC":
            if b == 0 and c == 0:
                print("No")
                exit()
            if b > c:
                b -= 1
                ans.append('C')
            else:
                b += 1
                ans.append('B')
        # print(a,b,c)

    # print(ans, a, b, c)
    print('\n'.join(['Yes'] + ans))
    exit()

case = {(A, B, C): []}  # 1,1 1,0 0,1 0,0 2,0 0,2

for i, s in enumerate(S):
# while True:
#     s = input().strip()
    new_case = {}
    for (a, b, c), v in case.items():
        if s == "AB":
            if a == 0 and b == 0:
                continue
            elif a == 1 and b == 1:
                new_case[(0, 2, 0)] = list(v) + ['B']
                v.append('A')
                new_case[(2, 0, 0)] = v
                # two case
                pass
            else:
                v.append('A' if b else 'B')
                new_case[(abs(a - 1), abs(b - 1), c)] = v
        if s == "AC":
            if a == 0 and c == 0:
                continue
            if a == c:
                new_case[(2, 0, 0)] = list(v) + ['A']
                v.append('C')
                new_case[(0, 0, 2)] = v

                # two case
                pass
            else:
                v.append('C' if a else 'A')
                new_case[(abs(a - 1), b, abs(c-1))] = v

        if s == "BC":
            if b == 0 and c == 0:
                continue
            elif b == c:
                new_case[(0, 2, 0)] = list(v) + ['B']
                v.append('C')
                new_case[(0, 0, 2)] = v
            else:
                v.append('B' if c else 'C')
                new_case[(a ,abs( b-1), abs(c-1))] = v

    if not new_case:
        print("No")
        exit()
    case = new_case
    # print(case)

print('\n'.join(['Yes'] + list(case.values())[0]))