Enunțul problemei reteta, de clasa a 10-a, dată în 2009 la OJI, se găsește pe PbInfo, .campion și InfoArena.

Rezumat reteta

Ni se dă o rețetă codificată sub forma unui șir de caractere, într-un mod mai neobișnuit. Rețeta este scrisă pe un singur rând, unde sunt precizate ingredientele folosite, cantitățile necesare, ordinea în care se execută operațiile, precum și timpul pentru care se amestecă fiecare grup de ingrediente. De exemplu:

(((zahar 100 ou 3)5 unt 100 nuca 200)4 (lapte 200 cacao 50 zahar 100) 3)20

Semnificația rețetei: Se amestecă 100 grame de zahăr cu 3 ouă pentru 5 minute. Se adaugă 100 grame de unt și 200 de nucă, și se amestecă toată compoziția pentru 4 minute. Apoi, timp de 3 minute se amestecă 200 grame de lapte, 50 grame de cacao și 100 de zahăr. La final, se amestecă cele două compoziții pentru 20 de minute.

Trebuie să determinăm timpul total de preparare a rețetei și cantitățile necesare din fiecare ingredient. Ingredientele trebuie afișate în ordine alfabetică.

Soluție reteta

Pentru reținerea ingredientelor din rețetă am definit struct-ul Ing, ce conține câmpul cnt (frecvența ingredientului) și str (numele său). Am reținut un vector cu ingredientele, sortat după numele lor. Astfel, am putut folosi căutare binară pentru găsirea unui ingredient în vector și actualizarea frecvenței sale. Când acesta nu se găsește, îl inserăm pe poziția unde se oprește căutarea binară. Pentru calcularea timpului total de preparare a rețetei, pur și simplu se adună toate numerele scrise imediat după parantezele închise (ignorând spațiile).

Mai rămâne de discutat parsarea (citirea) expresiei. Eu am creat o copie a rețetei în variabila aux, pe care am împărțit-o în cuvinte folosind funcția strtok. Apoi, am parcurs originalul șirului de caractere (str), reținând caracterul precedent (pentru a ști când să actualizăm răspunsul la a doua cerință). Dacă dăm de o cifră sau de o literă, actualizăm vectorul de ingrediente sau timpul total de preparare folosind string-ul delimitat de strtok ce începe pe aceeași poziție, iar apoi trecem la următorul spațiu.

Puteam obține o sursă mai eficientă folosind un treap (map-ul din STL), pentru a insera în timp logaritmic noile ingrediente. Dar, fiind o problemă destul de clasică cu șiruri de caractere, am lăsat varianta cu vectori și string-uri din C 😉

Sursă C++ reteta

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