1. Înțelegerea conceptului de funcționare și implementarea unor liste simplu/dublu înlănțuite și circulare,stive,cozi si arbori
2. Operarea cu aceste structuri de date
3. Implementarea unei funcționalități practice folosind aceste concepte

1. Deadline soft, 03 aprilie ora 23:59
2. Termen final de trimitere d m ora hh:mm (depunctare de 0.5pt/zi, maxim 3p depunctare).
3. Trimiterea temelor se face pe platforma vmchecker (folosiți credențialele de pe http://acs.curs.pub.ro).

Dr. Doofus își urmărește în continuare planul de a domina lumea. După zeci de eșecuri în care a fost abrupt întrerupt de imprevizibilul ornitorinc agent Perry sau de frații Phineas și Ferb, el simte că a găsit rețeta succesului. A păzit ingredientele „rețetei succesului“ chiar cu mai multa dedicare decât a dat dovadă când încerca să-i saboteze fiicei lui, Vanessa, prima întalnire cu un băiat.

Foarte încrezător, Dr. Doofus vrea să facă o vizită la supermarket cu o listă în care se află ascuns ingredientul final pentru arma sa secretă. Absolut întamplator, Phineas și Ferb au vizitat supermarketul în ora precedentă pentru a-și procura obiectele necesare pentru o nouă invenție și anumitor obiecte li s-a epuizat stocul. Îngrijorat de cei doi baieți și de ornitorincul buclucaș, Dr. Doofus te roagă pe tine să faci aceste cumpărături pentru el și îți oferă posibilitatea să improvizezi atâta timp cât îi aduci ingredientul cheie.

Poți face față provocării?

Următoarea temă are ca principiu realizarea unor cumpărături dintr-un supermarket pe baza unei liste de cumpărături. Lista de cumpărături va fi modificată prin adăugare sau eliminare de produse, iar achizitionarea se va realiza in limita unui buget disponibil (sold).

Fișiere input:

1. „date1.in“

• pe primul rand se va găsi numărul de produse din supermarket
• conține informații despre toate produsele din supermarket,acestea fiind ordonate alfabetic după campul „categorie“
• un produs este descris de: { nume de tip char*; categorie de tip char*; preț de tip int; cantitate de tip int; stoc de tip int;}
• campul stoc este 0 sau 1( 1=dacă acel produs ce va trebui cumpărat este în stocul supermarket-ului, 0 în caz contrar )

2. „date2.in“

• reprezintă lista de cumpărături
• pe primul rand - numărul de produse ce trebuie achiziționate
• pe următoarele linii se găsesc produsele caracterizate de: { nume; categorie; cantitate_ceruta;}

3. „cerințe.in“

• pe prima linie conține 6 numere, 1 sau 0,corespunzătoare fiecărei cerințe.
• Pentru 1 cerința se va realiza,pentru 0 cerința nu se va realiza.(Exemplu: 0 1 1 0 1 1 → se vor realiza doar cerințele 2, 3 și 5 (imposibil, dar e doar un exemplu)).
  • pe a doua linie bugetul disponibil pentru a realiza cerința a 2-a(se va folosi doar in cadrul celei de-a doua cerințe )

Structuri esențiale:

• o listă, „lista1“, cu informațiile din „date1.in“
• o listă, „lista2“, cu informațiile din „date2.in“
• o listă, „lista3“, cu informațiile produselor achiziționate: {nume; categorie; preț; cantitate_cumpărată;}
• o stiva(bonus)
• un arbore (bonus)

Numele structurilor utilizate sunt pur orientative.

Cerințe:

1. Adăugarea produselor din „date2.in“ in „lista2“. Adăugarea trebuie să respecte următoarea regulă: un produs se adaugă numai după un alt produs din aceeași categorie. Dacă nu se gasește un produs din aceeași categorie se va adăuga la finalul listei.

2. Eliminarea din „lista2“ a tuturor produselor ce au în „lista1“ campul stoc nul.(egal cu 0)

3. Realizarea cumpărăturilor cu buget: completarea listei „lista3“ cu datele obiectelor achiziționate în limita bugetului disponibil (se cumpara la rand produsele din lista - pana la epuizarea fondului).

4. Realizarea cumpărăturilor cu buget nelimitat și compensare: Dacă un produs din „lista2“ prezintă un stoc insuficient în „lista1“, va fi cumpărat, în completarea cantității cerute de produs, un alt produs din „lista1“ ce aparține aceleiași categorii.

Condiții pentru cerința 4:

• produsul cu care se completează are cel mai apropiat preț de cel dorit inițial.
• dacă cantitatea produsului „cel mai apropiat“ este suficient,
  • atunci: se cumpără din acesta cat pentru completarea cantității(acest produs are stocul = 0, NU cantitatea)
  • altfel: se cumpără din acesta cantitatea maxima (existenta în supermarket)
• Lista de cumpărături se va parcurge și se vor cumpără în ordine:
  • produsul curent, compensarea pentru produsul curent, produsul următor, compensarea pentru acest produs și asa mai departe.

5. Arbore:

Se va crea un arbore binar ordonat crescător (la parcurgerea RSD) după cantitate.

6. Stiva:

Pentru fiecare produs P din lista1, sa se afle numărul de produse de pe poziții consecutive înainte de P care au prețul mai mare decat prețul lui P (numărul de produse la rand mai scumpe, mergand spre anterior)

• rezultatul se va adăuga într-un vector (poziția 0 pentru primul produs din lista și asa mai departe).

Fișiere Output:

• în fișierul de output „rezultate.out“ se cer integral datele din liste și arbore, datele fiecărui nod fiind scrise pe linii diferite;
• ce va conține fișierul de output depinde de cerințele rezolvate:
  • dacă se rezolva cerința 1 sau cerința 2, se va afișa „lista2“
  • dacă se rezolva cerința 3 sau cerința 4, se va afișa „lista3“
  • dacă se rezolva cerința 5, se va afișa arborele (doar cantitățile RSD)
  • dacă se rezolva cerința 6, se va afișa vectorul cu rezultatele

date1.in

6
cascaval branzeturi 10 5 1
telemea branzeturi 10 7 0
varza legume 9 5 1 
parizer mezeluri 9 10 1
carnati mezeluri 10 6 0
crenvusti mezeluri 5 10 1

date2.in

4
cascaval branzeturi 10
varza legume 5
parizer mezeluri 14 
crenvusti mezeluri 7

cerinte.in

1 1 0 1 0 0
300

rezultate.out

cascaval branzeturi 0
varza legume 0
parizer mezeluri 0 
crenvusti mezeluri 0
 
cascaval branzeturi 5
telemea branzeturi 5
varza legume 5
parizer mezeluri 10
carnati mezeluri 4
crenvusti mezeluri 7

Așadar, executabilul obținut în urma compilării va avea numele editor iar regula de rulare va fi:

• Deadline-ul soft al temei este până pe 3/04, iar după această zi se aplică o depunctare de 20 pcte/zi.
• Arhiva temei va avea numele GrupaSerie_Nume_Prenume_TemaNr.zip și va fi încărcată pe vmchecker unde vă puteți loga folosind credențialele de pe acs.curs

• Implementarea se va face folosind liste
• Nu se acceptă implementări cu tipuri de date statice; lucrăm cu memorie alocată dinamic pentru eficientizare
• Se va depuncta lucrul nemodularizat, folosind funcții
• Memoria trebuie eliberată. Dacă nu se respectă această cerință depunctarea este de pana la 5/100 pcte.
• Ea va conține (direct în rădăcină):
  1. Listă ordonată fișierele sursă
  2. Makefile-ul (cu regulile make build și make clean). Executabilul generat trebuie să se numească editor
  3. fișierul README în care va fi descrisă soluția problemei
• Dacă soluția voastră nu compilează, dar dacă ideea este bună și trimiteți o încercare de implementare, puteți primi până la 20p
• Temele care vor fi copiate vor primi 0 pcte si studentii implicati - mustrari si vor figura pe blacklist-ul cursului de SDA.