Enunțul problemei betisoare, de clasa a 6-a, dată în 2014 la ONI, se găsește pe .campion.

Rezumat betisoare

Trebuie să evaluăm n expresii ce conțin numere formate din bețișoare. Aceste expresii pot conține operatorii + și *, înmulțirea având prioritate mai mare decât adunarea. Numărul x va fi reprezentat drept o succesiune de x bețișoare (caracterul pentru bețișor fiind I).

Soluție betisoare

Având în vedere că fiecare expresie poate avea până la 1.000.000 de caractere, trebuie să procedăm cât mai eficient, și deci să le evaluăm chiar în timpul citirii. Așadar, vom folosi trei variabile, în care reținem suma, termenul curent și factorul curent.

Citim pe rând fiecare caracter. Dacă acesta este 'I', atunci factorul curent se incrementează. Dacă este '*', atunci înmulțim termenul curent cu factorul pe care tocmai l-am calculat (un termen poate fi format dintr-un singur factor). Dacă este '+', atunci adunăm la sumă termenul pe care tocmai l-am calculat. Dacă este '\n', înseamnă că s-a terminat expresia, așa că înmulțim ultimul termen cu ultimul factor calculat, și adunăm acest termen la suma finală.

Vom folosi tipul unsigned long long int deoarece putem ajunge la niște numere ce depășesc maximul int-ului. De asemenea, vom ține cont de faptul că elementul neutru la adunare este 0, iar cel de la înmulțire e 1.

Sursă C++ betisoare

Dacă ai vreo nedumerire cu privire la problema betisoare, 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!