Intercanvis P58715


Statement
 

pdf   zip

thehtml

Donada una permutació dels nombres entre 1 i n, l’heu d’ordenar de petit a gran. L’única operació que podeu fer és intercanviar dos nombres entre si. Quants intercanvis necessiteu?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguit d’una permutació de { 1, …, n }. Podeu suposar 1 ≤ n ≤ 105.

Sortida

Per a cada cas, escriviu una línia amb el mínim nombre d’intercanvis necessaris.

Public test cases
  • Input

    2  1 2
    2  2 1
    6  1 2 3 4 5 6
    6  6 5 4 3 2 1
    5  2 4 5 1 3
    1  1
    

    Output

    0
    1
    0
    3
    3
    0
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++