0870 - Depou

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:

Rezolvare

def main():
    a = [0] * 1001
    d = [[0] * 3 for _ in range(2001)]
    b = [0] * 1001

    n = int(input())
    a[1:n + 1] = map(int, input().split())

    vf = 0
    vagon = 1
    op = 0
    ok = 1
    i = n

    while vagon <= n and ok == 1:
        if vagon == a[i]:
            op += 1
            vagon += 1
            i -= 1
            d[op][0] = 1
            d[op][1] = 3
        elif vf > 0 and b[vf] == vagon:
            op += 1
            vagon += 1
            vf -= 1
            d[op][0] = 2
            d[op][1] = 3
        elif i >= 1:
            op += 1
            d[op][0] = 1
            d[op][1] = 2
            vf += 1
            b[vf] = a[i]
            i -= 1
        elif vagon >= 1 and i == 0 and vf > 0:
            ok = 0

    if ok == 0:
        print(0)
    else:
        print(op)
        for i in range(1, op + 1):
            if d[i][0] == 1:
                print("A", end=" ")
            else:
                print("B", end=" ")
            if d[i][1] == 2:
                print("B")
            else:
                print("C")

if __name__ == "__main__":
    main()