Structuri de Date și Algoritmi (seria 1AB)

Această pagină poate fi doar citită. Poți vedea sursa, dar nu poți modifica pagina. Consultă administratorul dacă ești de părere că ceva este în neregulă.
====== Tema 1: Supermarket ======

=====  Obiective =====
  - Înțelegerea conceptului de funcționare și implementarea unor liste simplu/dublu înlănțuite și circulare,stive,cozi si arbori
  - Operarea cu aceste structuri de date 
  - Implementarea unei funcționalități practice folosind aceste concepte
===== Informații =====
  - Deadline hard, **03 aprilie ora 11:59** (termen limită - **nu se obţin puncte** pe soluţiile trimise mai târziu)
  - Trimiterea temelor se face pe platforma vmchecker (folosiți credențialele de pe http://acs.curs.pub.ro).
  - Checker-ul offline il puteti descarca de la acesta [[https://drive.google.com/open?id=1Y7SGDeb3cGQslINQns1FfkrNPtUoKDeT|adresa]] 
  - Puteţi cere ajutor oricând la această adresă [[sda-ab-tema1@googlegroups.com|email]]

===== Modificări temă=====
  - 20/03/2018 22:35
     * corecturi checker - nume de categorii din seturile de date (afectează t11)
     * corecturi checker - date de ieşire pentru cerinţa 3 (afectează t6, t7)
     * menţiuni suplimentare pentru cerinţele 3, 4
  - 31/03/2018 02:00
     * explicaţie checker - t13 - nu se elimină altfel noduri din "lista2" (produse dorite) decât prin condiţia de la C2; la rezolvarea C4, dacă un produs dorit nu există în "lista1" (supermarket), atunci nu putem şti preţul lui, deci nu există conceptul de "cel mai apropiat preţ";
  - 02/04/2018 21:30
     * prelungire termen limită cu 12 ore (de la 2 aprilie, ora 23:59, la **3 aprilie, ora 11:59**)


===== Descriere =====
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?
===== Introducere =====
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).
===== Cerințe =====
**Fișiere input:**

1. "date1.in"
       * pe primul rand se va găsi numărul de produse din supermarket
       * pe următoarele rânduri sunt informații despre toate produsele din supermarket, acestea fiind ordonate alfabetic după câmpul "categorie"
       * un produs este descris de următoarea structură:\\

<code>
//produs listă supermarket - datele apar pe un rând, în această ordine
    char* nume;
    char* categorie;
    int pret;
    int cantitate;
    int stoc;
</code>
       * 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:\\

<code>
//produs cumparat
    char* nume;
    char* categorie;
    int cantitate; //ceruta
</code>

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 0 -> 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 3-a (se va folosi doar in cadrul celei de-a treia cerințe)

**Structuri esențiale:** 
  * o listă, "lista1", cu informațiile din "date1.in" (sau lista_produse_supermarket)
  * o listă, "lista2", cu informațiile din "date2.in" (sau lista_cumparaturi)
  * o listă, "lista3", cu informațiile produselor achiziționate (sau lista_produse_cumparate), cu structura produselor:\\

<code>
//produs listă cumpărături - datele apar pe un rând, în această ordine
    char* nume;
    char* categorie;
    int cantitate; //cumparata
</code>
  * o stiva
  * un arbore

 //Numele structurilor utilizate sunt pur orientative.// 

**Cerințe:**

**1.** Adăugarea produselor din "date2.in" in "lista2" (de cumpărături). Datele produselor se citesc şi produsele se adăuga, în ordine, la finalul listei.

**2.** Eliminarea din "lista2" (de cumpărături) a tuturor produselor ce au în "lista1" (supermarket) campul stoc nul (egal cu 0).

**3.** Realizarea cumpărăturilor cu buget: completarea listei "lista3" (produse cumpărate) cu datele obiectelor achiziționate în limita bugetului disponibil (se cumpără, la rând, produsele din listă, în limitele date de buget si de cantităţile cerute/disponibile pentru fiecare produs).
<note>Rezolvarea cerinţei 3 nu produce modificări în "lista2" (de cumpărături). Pentru claritate, nu produce modificări nici în "lista1".</note>

**4.** Realizarea cumpărăturilor cu buget nelimitat și compensare (suprascrie "lista3", adică nu ţine cont de rezultatul cerinţei 3):\\ 
 
  Dacă un produs din "lista2" (de cumpărături) prezintă o cantitate insuficientă în "lista1" (supermarket), va fi cumpărat până la epuizare, iar completarea cantității cerute de produs se va face cu alt produs din "lista1" (supermarket) 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 (se compară numai produse din aceeaşi categorie);  
  * dacă produsul "cel mai apropiat" există în cantitate suficientă în supermarket,
          * atunci: se cumpără din acesta cât pentru completarea cantității
          * altfel: se cumpără din acesta cantitatea maximă (existentă în supermarket) 
  * Lista de cumpărături se va parcurge și se vor cumpăra în ordine:
	  *produsul curent, compensarea pentru produsul curent, produsul următor, compensarea pentru produsul respectiv și asa mai departe.\\

<note>Rezolvarea cerinţei 4 produce modificări în "lista2" (de cumpărături). La cumpărarea unui produs dorit (sau compensarea cu alt produs), se scade cantitatea cerută din produsul dorit cu cantitatea cumpărată.</note>

**5.** Arbore:

Folosind datele din "lista3" (produse cumpărate), se va crea un arbore binar ordonat crescător (la parcurgerea **RSD**) după cantitate.

**6.** Stiva:

Pentru fiecare produs P din "lista1" (supermarket), 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 decat produsul curent, mergand spre anterior);
      * rezultatul se va adăuga într-un vector (poziția 0 pentru primul produs, poziţia 1 pentru următorul din listă și asa mai departe).

**Fișiere Output:**
  * Toate cerinţele marcate (în "cerinţe.in") vor fi rezolvate, în ordine, apoi se va trece la afişarea rezultatelor;
  * în fișierul de output ("rezultate.out") se vor scrie integral datele produselor din liste, datele unui produs vor fi separate prin spaţiu, după fiecare produs urmează un final de linie;
  * după fiecare afişare a unei structuri (listă, arbore, vector) urmează un final de linie;
  * rezultatele cerinţelor se vor afişa în ordinea următoare: 
        * dacă se rezolvă cerința 1 sau cerința 2, se va afișa "lista2" (o singură dată);
        * dacă se rezolvă cerința 3 sau cerința 4, se va afișa "lista3" (o singură dată);
        * dacă se rezolvă cerința 5, se va afișa arborele (doar fiecare cantitate, urmată de un spaţiu, prin parcurgerea RSD);
        * dacă se rezolvă cerința 6, se va afișa vectorul cu rezultatele (doar fiecare valoare din vector, urmată de un spaţiu).


===== Exemplu =====

<file date1.in 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
</file>
  
<file date2.in date2.in>
4
cascaval branzeturi 10
varza legume 5
parizer mezeluri 14 
crenvusti mezeluri 7
</file>
  
<file cerinte.in cerinte.in>
1 1 0 1 0 0
300
</file>

<file rezultate.out 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
</file>

<note warning>NU se lasă rând liber pentru Ci == 0.</note>

Așadar, executabilul obținut în urma compilării va avea numele market iar regula de rulare va fi:
<note tip>**./market date1.in date2.in cerinte.in rezultate.out**</note>

===== Reguli de trimitere =====

*puteţi încărca mai multe soluţii, se va lua în considerare soluţia cu cel mai mare punctaj trimisă până la termenul limită (2 aprilie, ora 23:59);
*Arhiva temei va avea numele GrupaSerie_Nume_Prenume_TemaNr.zip și va fi încărcată pe [[https://vmchecker.cs.pub.ro/ui/|vmchecker]] unde vă puteți loga folosind credențialele de pe acs.curs.

==== Restricții ====
  * Implementarea se va face folosind liste;
  * Nu se acceptă implementări cu tipuri de date cu memorie alocată static (se acceptă numai variabile locale de tip buffer pentru stocare temporară înainte de alocare);
  * Se va depuncta lucrul nemodularizat (fără funcții);
  * Memoria trebuie eliberată. Dacă nu se respectă această cerință depunctarea este de pana la 5/100 pct (pentru mai mult de O(1) memorie alocată fără eliberare).
  * Menţineţi cel puţin un nivel minimal de aspect al codului şi evitaţi inconsistenţa (indentare haotică, numeroase combinaţii de caractere de tip "leading/trailing whitespace", numirea variabilelor şi a funcţiilor în ordinea literelor din alfabet);
  * Arhiva trimisă conține (direct în rădăcină):
      - Makefile-ul (cu regulile **make build** și **make clean**). Executabilul generat trebuie să se numească market;
      - fișierul README în care va fi descrisă soluția problemei;
  * Dacă soluția voastră nu compilează, dar ideea este bună și trimiteți o încercare de implementare, puteți primi până la 20/100 pct;
  * Temele care vor fi copiate vor primi 0 pct şi studenţii implicaţi - mustrări şi vor figura pe blacklist-ul cursului de SDA.
Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Unelte pagină
