Problema Sstabil – ONI 2012, Clasa a 9-a

• Dificultate:
• Autor: Piț-Rada Vasile
• Online: InfoArena, 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';
    return 0;
}

Dacă ai vreo nedumerire cu privire la problema Sstabil, lasă un comentariu și te voi ajuta