Revizia anterioară Revizia următoare
Solutii Grigore Moisil 2009
Alibaba
Vom prezenta trei moduri de abordare a rezolvării.
Varianta 1 (propusă de Clara Ionescu)
Să observăm că la fiecare pas trebuie tăiată ultima cifră dintr-o secvenţă descrescătoare de cifre aflate pe poziţii consecutive. Astfel peste această cifră vom putea pune cea aflată pe poziţia imediat următoare şi care are valoare mai mare. Conform acestui algoritm pentru exemplul din enunţ (12312) se vor obţine pe rând numerele: 2312, 312, 32.
Algoritmul de mai sus pierde timp preţios efectuând translatările aferente tăierii unei cifre. În concluzie vom crea un şir martor în care memorăm faptul că o anumită cifră este tăiată sau nu.
Varianta 2 (propusă de Pătcaş Csaba)
Pornim de la observaţia că pentru a maximiza numărul trebuie să aducem pe prima poziţie cea mai mare cifră posibilă. Dacă putem tăia maxim k cifre, rezultă că vom putea muta pe prima poziţie o cifră dintre primele k + 1 cifre. Pornim cu cifrele din intervalul [1, n] şi cu valoarea k. Dacă cifra având valoare maximă din intervalul [1, k + 1] se află pe poziţia l, atunci problema se reduce la intervalul [l + 1, n] şi valoarea k – l. O implementare naivă va avea complexitatea O(k2) în cel mai rău caz, dar în practică algoritmul se comportă mult mai bine. Menţionăm că complexitatea se poate reduce la O(k log k) folosind arbori de intervale.
Varianta 3 (propusă de Marius Stroe)
Soluţia foloseşte metoda greedy. În continuare, vom considera S ca fiind şirul cifrelor. Pentru a forma cel mai mare număr, trebuie ca pe primele poziţii să avem cifre cât mai mari. Din acest motiv, vom căuta prima cea mai mare cifră din şir, după care următoarea cea mai mare cifră din şir ş.a.m.d. Spre exemplu, pentru şirul 1295413746 cifrele găsite sunt, în această ordine, 9, 7 şi 6. Cu aceste cifre vom forma un număr T, aici 976, care este cel mai mare dacă, în cazul acesta, trebuie să eliminăm 7 cifre. Dacă, însă, numărul cifrelor ce trebuie eliminate este mai mic, atunci trebuie să avem un şir T mai lung adăugându-i noi cifre din cele rămase. Când vom insera aceste cifre noi, vrem ca cele găsite până acum să rămână pe poziţii cât mai înaintate. De aceea, pentru fiecare şir rămas cuprins între cifrele găsite, 12, 5413, 4, vom aplica acelaşi procedeu, însă, le vom considera în ordine inversă, 4, 5413, 12, pentru ca cifrele cele mai mari să rămână pe poziţii cât mai semnificative. Vom repeta recursiv procedeul până când şirul T are lungimea n – k.
Subproblema determinării celei mai mari cifre, a următoarei celei mai mari cifre ş.a.m.d. se rezolvă cu ajutorul unei stive în timp liniar. Algoritmul parcurge şirul cifrelor de la cea mai semnificativă la cea mai puţin semnificativă, scoate din stivă toate elementele care sunt mai mici strict decât cifra curentă, iar apoi o inserează pe aceasta în vârful structurii de date.
...
stk_len = 0
pentru i = 1, n execută
cât timp (stk_len > 0) şi (stk[stk_len] < stk[i]) execută
stk_len --;
sfârşit cât timp
stk[stk_len] = S[i]
stk_len ++
sfârşit pentru
...Complexitate finală: O(n)
