Cerința

Se consideră un depou de cale ferată precum cel din imagine:

Pe linia A se află n vagoane, numerotate cu valori distincte de la 1 la n, într-o ordine oarecare. Vagoanele trebuie mutate pe linia C, în ordinea 1 2 .. n. Pentru aceasta se poate muta câte un vagon de pe o linie pe alta, în ordinea indicată de săgeți:

A -> B,
A -> C
B -> C.

Să se determine o succesiune de operații care să mute toate vagoanele de pe linia A pe linia C în ordinea dorită.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale distincte cuprinse între 1 și n, reprezentând ordinea vagoanelor de pe linia A.

Date de ieșire

Programul va afișa pe ecran numărul C de operații efectuate, apoi cele C operații. Fiecare operație va fi afișată pe câte o linie a ecranului, și va consta din două caractere de forma X Y, semnificând faptul că se mută un vagon de pe linia X pe linia Y. Dacă nu este posibilă mutarea vagoanelor de pe linia A pe linia C, numărul de operații afișat va fi 0.

Restricții și precizări

1 ≤ n ≤ 1000

Exemplu

Intrare

4
2 1 3 4

Ieșire

6
A B
A B
A C
A C
B C
B C

Explicație

Ordinea inițială a vagoanelor este următoarea:

După mutarea vagoanele vor fi în ordinea:

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 Depou:

#include <iostream>
using namespace std;

struct mutare{char X,Y;};

int nA , A[1005] , nB , B[1005] , nC , C[1005] , nrm;
mutare mutari[2005];

int main()
{
    int n;
    cin >> n;
    nA = n;
    for(int i = 1 ; i <= nA ; i ++)
            cin >> A[i];
    for(int i = 1 ; i <= n ; i ++)
        if(B[nB] == i)
        {
            C[++nC] = i, nB --;
            nrm ++;
            mutari[nrm].X = 'B', mutari[nrm].Y = 'C';
            //cout << mutari[nrm].X << " " << mutari[nrm].Y << " " << i << endl;
        }
        else
        {
            bool gasit = false;
            while(nA > 0 && !gasit)
                if(A[nA] == i)
                {
                    C[++nC] = i, nA --;
                    nrm ++;
                    mutari[nrm].X = 'A', mutari[nrm].Y = 'C';
                    //cout << mutari[nrm].X << " " << mutari[nrm].Y << " " << i << endl;
                    gasit = true;
                }
                else                    
                {
                    B[++nB] = A[nA], nA --;
                    nrm ++;
                    mutari[nrm].X = 'A', mutari[nrm].Y = 'B';
                    //cout << mutari[nrm].X << " " << mutari[nrm].Y << " " << A[nA+1] << endl;
                }
            if(!gasit)
            {
                cout << 0;
                return 0;
            }
        }
    cout << nrm << "\n";
    for(int i = 1 ; i <= nrm ; i ++)
        cout << mutari[i].X << " " << mutari[i].Y << "\n";
    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 #870 Depou

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #870 Depou 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 #870 Depou