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()