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++
#include <fstream>
#define NMAX 1000010
std::ifstream fin("sstabil.in");
std::ofstream fout("sstabil.out");
int n, v[NMAX];
int m, w[NMAX];
int main() {
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i];
v[0] = 9; // Ca să nu ne extindem niciodată după prima cifră.
w[0] = 9; // Ca prima cifră construită să poată fi oricât de mică,
// pentru că ea nu depinde de cifra de dinaintea sa.
for (int i = n; i >= 1; ) {
int sum = 0;
for (int j = i; sum <= 9; j--)
sum += v[j];
int val = v[i];
for (i--; sum - val > 9 || val + w[m] <= 9; i--)
val += v[i];
w[++m] = val;
}
for (int i = m; i >= 1; i--)
fout << w[i];
fout << '\n';
fout.close();
return 0;
}
Dacă ai vreo nedumerire cu privire la problema sstabil, lasă un comentariu și te voi ajuta