0873 - Vase

Cerinta

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.

Rezolvare

def operatii_masurare(A, B, C):

   operatii = []

   def umplere_completa(vas):
       if vas == 'A':
           return 'R A'
       else:
           return 'R B'

   def golire_completa(vas):
       if vas == 'A':
           return 'A C'
       else:
           return 'B C'

   def mutare_din_to_A():
       return 'B A'

   def mutare_din_to_B():
       return 'A B'

   def masoara():
       return 'A C'

   def BFS():
       visited = set()
       queue = '', 0, 0  # Stare (operație, cantitate_A, cantitate_B)

       while queue:
           state = queue.pop(0)
           if state[1] == C or state[2] == C:
               return state[0].split()
           if (state[1], state[2]) in visited:
               continue
           visited.add((state[1], state[2]))

           # Umplere completă
           if state[1] < A:
               queue.append([state[0] + umplere_completa('A'), A, state[2]])
           if state[2] < B:
               queue.append([state[0] + umplere_completa('B'), state[1], B])

           # Golire completă
           if state[1] > 0:
               queue.append([state[0] + golire_completa('A'), 0, state[2]])
           if state[2] > 0:
               queue.append([state[0] + golire_completa('B'), state[1], 0])

           # Mutare între vase
           if state[1] > 0 and state[2] < B:
               queue.append([state[0] + mutare_din_to_A(), state[1] - min(state[1], B - state[2]), state[2] + min(state[1], B - state[2])])
           if state[2] > 0 and state[1] < A:
               queue.append([state[0] + mutare_din_to_B(), state[1] + min(state[2], A - state[1]), state[2] - min(state[2], A - state[1])])

       return None

   rezultat = BFS()
   return len(rezultat), rezultat

if __name__ == "__main__":

   A = int(input("Capacitatea vasului A: "))
   B = int(input("Capacitatea vasului B: "))
   C = int(input("Cantitatea dorită de apă: "))

   numar_operatii, secventa_operatii = operatii_masurare(A, B, C)

   print("Numărul minim de operații necesare:", numar_operatii)
   print("Secvența de operații:")
   for operatie in secventa_operatii:
       print(operatie)