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

<syntaxhighlight lang="python"> A, B, C = map(int, input().split()) 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)

</syntaxhighlight>