Rezolvare PBinfo #870

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: