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

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