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