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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#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 🙂
Îț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!