Motto: Nu poate fi vorba de degradarea biologică a prostiei. Prostia nu are vârstă.

C. Servicii de permutare

          Aveţi  N pietre, marcate cu numere de la 1 la N, aşezate în linie - dar nu în această ordine - pe marginea unei ape. Dispuneţi de un contract cu compania Wally's Rock Permuting, Inc. (WRP) care stabileşte următoarele: pentru un preţ fixat de  5 euro, WRP acceptă o listă de perechi disjunte de pietre şi permută pietrele din fiecare pereche din listă.

De exemplu, dacă WRP primeşte lista (3,5), (4,7), (1,8), iar pietrele sunt aşezate în ordinea

10   6   8   5   2   3   1   4   7   9

ea le va aranja în ordinea  

10   6   1   3   2   5   8    7   4   9

(au fost interschimbate pietrele 3 cu 5, 4 cu 7 şi 1 cu 8).

WRP primeşte 5 euro ca să facă aceste trei transpoziţii. Dacă dorim să mai facem o permutare, aceasta înseamnă altă listă, pentru care plătim tot 5 euro.

Atenţie la condiţia ca perechile din listă să fie disjuncte; nu pot exista simultan în listă (3,5) şi (5,4).

          Fiind date un întreg N, o aranjare iniţială şi una finală, dorim ca WRP să facă aranjamentul dorit astfel ca suma plătită să fie minimă. Care este această sumă minimă ?

 

Sursă: IBM Ponder This

Vezi comentarii
Logheaza-te in site pentru a trimite solutii si comentarii
aatanasiu

Versiunea originala:

We have N rocks, labelled 1 through N, lined up on the river bank but not in the correct order. We have a contract with Wally's Rock Permuting, Inc. (WRP): For the fixed price of 5 euros, WRP will accept a list of disjoint pairs of rocks, and transpose the rocks in each pair. For example, if he receives the list (3,5), (4,7), (1,8), and the rocks initially look like

10   6   8   5   2   3   1   4   7   9

after Wally leaves, they will look like

10   6   1   3   2   5   8    7   4   9

Blocks 3 and 5 have been interchanged, as have blocks 4 and 7, as have blocks 1 and 8.

WRP charged us 5 euros to do these three transpositions; he would also have charged 5 euros if we had requested only one transposition. But the pairs have to be disjoint: we cannot request (3,5), (5,4).

For a given N and a given initial order, suppose we plan our calls to WRP as efficiently as possible. For a fixed N, what is the most we should ever have to pay?