Enunțul problemei sstabil, de clasa a 9-a, dată în 2012 la ONI, se găsește pe InfoArena și PbInfo.
Rezumat
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 \le 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
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++
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!