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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Vase:

#include <iostream>
using namespace std;

int A,B,C,v[1000001], q[1000001], op[1000001];

void operatii(int poz , int cnt)
{
    if ( poz == 0 )
        cout << cnt << endl;
    else
    {
        operatii(v[poz] , cnt + 1);
        switch(op[poz])
        {
            case 1:
                cout << "A C
"; break;
            case 2:
                cout << "B C
"; break;
            case 3:
                cout << "R A
"; break;
            case 4:
                cout << "R B
"; break;
            case 5:
                cout << "A B
"; break;
            case 6:
                cout << "B A
"; break;
        }
    }
}

int main(){
    cin >> A >> B >> C;
    for(int i =1 ; i <= 1000000 ; i ++)
        v[i] = -1;
    int st = 1, dr = 1;
    q[dr] = 0;
    v[0] = 0;
    int pdr = -1;
    while(st <= dr && pdr == -1)
    {
        int k = q[st];
        int x = k / 1000, y = k % 1000;
        int xx , yy , kk;
        
        xx = 0 , yy = y ;
        kk = xx * 1000 + yy;
        if(v[kk] == -1)
        {
            q[++dr] = kk;
            v[kk] = k;
            op[kk] = 1; // golirea lui A
            if(xx == C || yy == C)
                pdr = dr;
        }
        xx = x , yy = 0 ;
        kk = xx * 1000 + yy;
        if(v[kk] == -1)
        {
            q[++dr] = kk;
            v[kk] = k;
            op[kk] = 2; // golirea lui B
            if(xx == C || yy == C)
                pdr = dr;
        }
        xx = A , yy = y ;
        kk = xx * 1000 + yy;
        if(v[kk] == -1)
        {
            q[++dr] = kk;
            v[kk] = k;
            op[kk] = 3; // umplerea lui A
            if(xx == C || yy == C)
                pdr = dr;
        }
        xx = x , yy = B ;
        kk = xx * 1000 + yy;
        if(v[kk] == -1)
        {
            q[++dr] = kk;
            v[kk] = k;
            op[kk] = 4; // umplerea lui B
            if(xx == C || yy == C)
                pdr = dr;
        }
        // A -> B
        if(y + x <= B)
            yy = y + x, xx = 0;
        else
            yy = B, xx = y + x - B;
        kk = xx * 1000 + yy;
        if(v[kk] == -1)
        {
            q[++dr] = kk;
            v[kk] = k;
            op[kk] = 5; // A -> B
            if(xx == C || yy == C)
                pdr = dr;
        }
        // B -> A
        if(x + y <= A)
            xx = x + y , yy = 0;
        else
            xx = A , yy = x + y - A;
        kk = xx * 1000 + yy;
        if(v[kk] == -1)
        {
            q[++dr] = kk;
            v[kk] = k;
            op[kk] = 6; // B -> A
            if(xx == C || yy == C)
                pdr = dr;
        }
        st ++;
    }
    
    if(pdr == -1)
        cerr << "Nu se poate";
    else
    {
        operatii(q[pdr] , 0);
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #873 Vase

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #873 Vase de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #873 Vase