Pancakes P59791


Statement
 

pdf   zip

html

Tenim una pila de pancakes de radis diferents. Els volem ordenar utilitzant una espàtula, de manera que només podem agafar uns quants consecutius dels primers desde adalt i donar-los la volta. El nostre objectiu és minimitzar el nombre de vegades que hem d’utilitzar l’espàtula per acabar amb una pila ordenada de pancakes, de petit a gran.

Escriviu un programa que, donada una configuració inicial dels pancakes, calculi el mínim nombre possible de moviments per ordenar-los.

Entrada

La primera linia conté un natural n que indica el nombre de pancakes. La segona linia conté una permutació dels naturals de l’1 al n que indica el seu ordre inicial.

Sortida

La sortida és el nombre mínim de moviments per ordenar la pila de pancakes.

Public test cases
  • Input

    3
    3 1 2
    

    Output

    2
    
  • Input

    4
    3 2 1 4
    

    Output

    1
    
  • Input

    30
    29 8 24 19 17 7 5 15 28 1 18 3 9 6 26 22 12 14 10 13 30 2 4 16 27 11 20 23 25 21
    

    Output

    31
    
  • Information
    Author
    Izan Beltran
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python