0873 - Vase

Cerința

Se dau dau două vase cu capacitatea A, respectiv B litri, iniţial goale. Se cere să se măsoare cu ajutorul lor C litri de apă, având la dispoziţie următoarele operaţii:

• umplerea completă a unui vas (de la robinet). Operaţia se notează R X, unde X poate fi A sau B.
• golirea completă a unui vas (în chiuvetă). Operaţia se notează X C , unde X poate fi A sau B.
• mutarea dintr-un vas în celălalt. Mutarea din vasul X în vasul Y se încheie când se goleşte vasul X sau când se umple vasul Y. Operaţia se notează X Y, unde X şi Y sunt diferite şi pot fi A sau B.

Să se determine o secvenţă de operaţii în urma cărora unul dintre vase să conţină C litri de apă.

Date de intrare

Programul citește de la tastatură numerele A B C.

Date de iesire

Programul va afișa pe ecran numărul minim de operaţii n, apoi cele n operaţii, fiecare pe o linie. Operaţiile pot fi: R A, R B, A C, B C, A B, B A, cu semnificaţia de mai sus.

Restricții și precizări

• 1 ≤ A , B , C ≤ 1000
• se garantează că pentru toate datele de test există soluţie

Exemplu:

Intrare

5 8 2

Ieșire

4

R A

A B

R A

A B

Explicaţie

Vasul A are capacitatea de 5 litri, iar vasul B are capacitatea de 8 litri. Se cere să se măsoare 2 litri de apă.

Cele 4 operaţii sunt:

R A – se umple vasul A. A conţine 5 litri, B conţine 0 litri

A B – se mută apă din vasul A în B. Se va muta toată apa din A. A conţine 0 litri, B conţine 5 litri

R A – se umple vasul A. A conţine 5 litri, B conţine 5 litri

A B – se mută apă din vasul A în B. Se vor muta 3 litri de apă din A. A conţine 2 litri, B conţine 8 litri

vasul A conţine 2 litri

Rezolvare

def validate_input(A, B, C):
    return 1 <= A <= 1000 and 1 <= B <= 1000 and 1 <= C <= 1000

# Obțineți valorile de intrare
A, B, C = map(int, input().split())

# Validați valorile de intrare
if not validate_input(A, B, C):
    print("Valorile introduse nu sunt valide. Asigurați-vă că 1 ≤ A, B, C ≤ 1000.")

v = [-1] * 1000001
q = [0] * 1000001
op = [0] * 1000001

def operatii(poz, cnt):
    if poz == 0:
        print(cnt)
    else:
        operatii(v[poz], cnt + 1)
        case = op[poz]
        if case == 1:
            print("A C")
        elif case == 2:
            print("B C")
        elif case == 3:
            print("R A")
        elif case == 4:
            print("R B")
        elif case == 5:
            print("A B")
        elif case == 6:
            print("B A")

st, dr = 1, 1
q[dr] = 0
v[0] = 0
pdr = -1

while st <= dr and pdr == -1:
    k = q[st]
    x, y = k // 1000, k % 1000

    # Golirea lui A
    xx, yy, kk = 0, y, 0
    if v[kk] == -1:
        dr += 1
        q[dr] = kk
        v[kk] = k
        op[kk] = 1
        if xx == C or yy == C:
            pdr = dr

    # Golirea lui B
    xx, yy, kk = x, 0, x * 1000
    if v[kk] == -1:
        dr += 1
        q[dr] = kk
        v[kk] = k
        op[kk] = 2
        if xx == C or yy == C:
            pdr = dr

    # Umplerea lui A
    xx, yy, kk = A, y, A * 1000 + y
    if v[kk] == -1:
        dr += 1
        q[dr] = kk
        v[kk] = k
        op[kk] = 3
        if xx == C or yy == C:
            pdr = dr

    # Umplerea lui B
    xx, yy, kk = x, B, x * 1000 + B
    if v[kk] == -1:
        dr += 1
        q[dr] = kk
        v[kk] = k
        op[kk] = 4
        if xx == C or yy == C:
            pdr = dr

    # A -> B
    if y + x <= B:
        yy, xx, kk = y + x, 0, 0
    else:
        yy, xx, kk = B, y + x - B, B * 1000 + (y + x - B)
    if v[kk] == -1:
        dr += 1
        q[dr] = kk
        v[kk] = k
        op[kk] = 5
        if xx == C or yy == C:
            pdr = dr

    # B -> A
    if x + y <= A:
        xx, yy, kk = x + y, 0, (x + y)
    else:
        xx, yy, kk = A, x + y - A, A * 1000 + (x + y - A)
    if v[kk] == -1:
        dr += 1
        q[dr] = kk
        v[kk] = k
        op[kk] = 6
        if xx == C or yy == C:
            pdr = dr

    st += 1

if pdr == -1:
    print("Nu se poate")
else:
    operatii(q[pdr], 0)