Enunțul problemei sstabil, de clasa a 9-a, dată în 2012 la ONI, se găsește pe InfoArena, .campion și PbInfo.
Rezumat sstabil
Un număr se consideră sstabil dacă suma oricăror două cifre vecine ale sale este strict mai mare decât 9. Asupra unui număr care nu este sstabil se aplică operații de tipul următor, până devine sstabil: Se aleg două cifre vecine a căror sumă este strict mai mică decât 10, și se înlocuiesc cu suma lor. Dându-se un număr natural n ≤ 1000000, să se determine cel mai mare număr sstabil ce se poate obține din n, aplicând oricâte operații de tipul menționat.
Soluție sstabil
Problema se rezolvă aplicând o strategie de tip greedy. Parcurgem cifrele numărului de la dreapta la stânga, iar la fiecare pas calculăm în sum suma cifrelor celei mai scurte secvențe care se termină în poziția curentă i, și care are suma cifrelor mai mare decât 9. Cum într-un număr sstabil nu poate exista nicio secvență de mai mult de două cifre cu suma mai mică decât 10, trebuie să înlocuim secvența obținută prin două cifre care să aibă suma egală cu sum. Este evident că putem face asta, deoarece suma respectivă ar fi maxim 18 = 9 + 9.
Pentru a afla cifra din dreapta, pornim din i, și adunăm cifre atât timp cât cifrele rămase să formeze cealaltă cifră au suma mai mare decât 9 (cât timp ele încă nu pot forma o singură cifră). În acest fel, asigurăm o sumă cât mai mare pentru a forma cifra din stânga, maximizând numărul final. Totuși există un caz când trebuie să ne extindem mai mult pentru a forma prima cifră: Atunci când suma curentă, adunată la ultima cifră adăugată la numărul final, nu este încă mai mare decât 9. Asta pentru că trebuie să respectăm condiția ca oricare două cifre consecutive să aibă suma mai mare decât 9. După ce am terminat de construit prima cifră, repetăm procedeul pentru numărul rămas, adică cel format din cifrele nefolosite în construirea primei cifre. Nu adăugăm direct a doua cifră la numărul final, pentru că s-ar putea să o mărim mai încolo.
Sursă C++ sstabil
Dacă ai vreo nedumerire cu privire la problema sstabil, lasă un comentariu și te voi ajuta 🙂
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!