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 ieșire

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

#include <bits/stdc++.h>

using namespace std;

int a, b, c, ic = -1, sc = 0, i, v[1000000], difa, difb, lg, f[1000000];
bool gasit;

struct elem
{
    int va, vb, dad, op;
};
elem C[1000000], now;

int main()
{
    cin >> a >> b >> c;
    ic++;
    while (ic <= sc)
    {
        now = C[ic];
        ic++;
        if (!f[1000 * a + now.vb])
        {
            sc++;
            C[sc].va = a;
            C[sc].vb = now.vb;
            C[sc].dad = ic - 1;
            C[sc].op = 1;
            f[1000 * a + now.vb] = 1;
        }
        if (C[sc].va == c || C[sc].vb == c)
            break;
        if (!f[1000 * now.va + b])
        {
            sc++;
            C[sc].va = now.va;
            C[sc].vb = b;
            C[sc].dad = ic - 1;
            C[sc].op = 2;
            f[1000 * now.va + b] = 1;
        }
        if (C[sc].va == c || C[sc].vb == c)
            break;
        if (!f[now.vb])
        {
            sc++;
            C[sc].va = 0;
            C[sc].vb = now.vb;
            C[sc].dad = ic - 1;
            C[sc].op = 3;
            sc++;
            f[now.vb] = 1;
        }
        if (!f[1000 * now.va])
        {
            sc++;
            C[sc].va = now.va;
            C[sc].vb = 0;
            C[sc].dad = ic - 1;
            C[sc].op = 4;
            f[1000 * now.va] = 1;
        }
        if (C[sc].va == c || C[sc].vb == c)
            break;
        if (now.va > b - now.vb)
        {
            difa = now.va - b + now.vb;
            difb = b;
        }
        else
        {
            difa = 0;
            difb = now.vb + now.va;
        }
        if (!f[1000 * difa + difb])
        {
            sc++;
            C[sc].va = difa;
            C[sc].vb = difb;
            C[sc].dad = ic - 1;
            C[sc].op = 5;
            f[1000 * difa + difb] = 1;
        }
        if (C[sc].va == c || C[sc].vb == c)
            break;
        if (now.vb > a - now.va)
        {
            difb = now.vb - a + now.va;
            difa = a;
        }
        else
        {
            difb = 0;
            difa = now.va + now.vb;
        }
        if (!f[1000 * difa + difb])
        {
            sc++;
            C[sc].va = difa;
            C[sc].vb = difb;
            C[sc].dad = ic - 1;
            C[sc].op = 6;
            f[1000 * difa + difb] = 1;
        }
        if (C[sc].va == c || C[sc].vb == c)
            break;
    }
    i = sc;
    while (i)
    {
        lg++;
        v[lg] = C[i].op;
        i = C[i].dad;
    }
    cout << lg << '\n';
    for (i = lg; i >= 1; i--)
    {
        switch (v[i])
        {
        case 1:
            cout << "R A\n";
            break;
        case 2:
            cout << "R B\n";
            break;
        case 3:
            cout << "A C\n";
            break;
        case 4:
            cout << "B C\n";
            break;
        case 5:
            cout << "A B\n";
            break;
        case 6:
            cout << "B A\n";
            break;
        }
    }
    return 0;
}