Editing 0870 - Depou


= Cerința =
Se consideră un depou de cale ferată precum cel din imagine:

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

* <code>A -> B</code>,
* <code>A -> C</code>
* <code>B -> C</code>.

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

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

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>

= 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 ==
<syntaxhighlight lang="python3">
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()

</syntaxhighlight>