====== Tema 2: Micul – Marele strateg======

=====  Obiective =====
  - Înțelegerea conceptului de graf și a modurilor de parcurgere aferente
  - Aplicarea algoritmilor studiați pe topologiile de tip graf in exemple practice
===== Informații =====
  - Deadline hard, **19 Mai ora 23:59** (termen limită - **nu se obţin puncte** pe soluţiile trimise mai târziu)
  - Trimiterea temelor se face pe platforma [[https://vmchecker.cs.pub.ro/ui/#|vmchecker]] (folosiți credențialele de pe http://acs.curs.pub.ro).
  - Checker-ul offline îl puteţi descărca de la această [[https://drive.google.com/drive/folders/14T8GgG-Cf1NYut-zYaVplEQ8bT5qAypZ?usp=sharing|adresă]] 
  - Puteţi cere ajutor oricând la această adresă [[sda.ab.teme@gmail.com|email]]

===== Descriere =====
Micul curier trebuie sa isi indeplineasca cerintele de la munca cat mai bine. El este responsabil
cu livrarea coletelor catre anumiti clienti din Bucuresti. Ca multi participanti in trafic, el alege
sa foloseasca metroul ca mijloc de transport principal. Din statiile in care ajunge este necesar sa se
deplaseze in continuare pe jos pana la adresa aferenta fiecarui client.

Avand in vedere faptul ca timpul lui de livrare este unul limitat si el nu este cel mai bun strateg, curierul
s-a gandit sa va ceara ajutorul. Cum ar fi daca ne-am transforma in micile lui ajutoare si ne-am pune in
functiune abilitatile de a scrie cod cu scopul de a-i organiza munca ? Credeti ca am reusi sa il
transformam intr-un “Mare strateg” ? Ramane de vazut !

{{ :teme2019:tema-2:jhnj.jpg |}}
===== Date de intrare =====
** Fisierul date.in **
  - Numarul de statii
  - Corespunzator fiecarei statii, fiecare atribut este afisat pe cate un rand
       * Nume_statie
       * Nr_clienti
  - Fiecare client este reprezentat de:
         * Nume_client
         * Timp_fata_de_statia_de_metrou
         * Suma_de_platit
  - Numar_strazi_intre_clienti
  - Pe urmatoarele Numar_strazi_intre_clienti linii avem
           * Client1 Client2 timp
           * **Exemplu: Client17 Client20 3**
  - Numar_rute
  - Pe urmatoarele Numar_rute linii avem
           * Statie1 Statie2 distanta
           * **Exemplu: Statie5 Statie3 2**
  - Numar_operatii_strategie
  - Pe urmatoarele Numar_operatii_strategie linii avem operatiile si descrierea lor
=====  Backtracking =====

Pentru testele cu **Backtraking** se vor citi un numar_de_strazi si matricea corespunzatoare pentru a ajunge inapoi la sediul jobului sau. 

=====  Punctaje si Detalii Tehnice =====
=== Punctaje: ===
 * Testele 1-5: 45% nota
 * Testele 6-10: 40% nota
 * Testele 10-13: 15% nota

=== Detalii Tehnice ===
  * **Distanta** – distanta dintre statiile de metrou
  * **Timp_fata_de_statia_de_metrou** – este timpul de la statia de metrou corespunzatoare clientului si
pana la locatia acestuia
  * Intre clientii care sunt localizati in zone apropiate ca distanta din Bucuresti se afla strazi.
  * Fiecarei statii de metrou i se asociaza adresele aferente clientilor (un graf) la care curierul
poate ajunge. Dupa livrarea comenzilor, curierul se intoarce la statia de metrou din care a
plecat
  * Micul strateg afla pe parcursul calatoriei pe care o face ca pe langa clientii disponibili, cei
carora le livreaza, are parte si de clienti indisponibili. Dupa ce va termina de expediat
coletele la clientii disponibili, el se va intoarce la statia de metrou.

=====  Anexa =====

**Structurile urmatoare sunt optionale si nu trebuie implementate la fel**

{{ :teme2019:tema-2:anexa3.png |}}

Executabilul obținut în urma compilării va avea numele curier, iar regula de rulare va fi:
<note tip>./curier date.txt rezultate.out</note>

=====  Cerinte =====
  * **conexiune x y** - Se verifica daca exista strada intre doi clienti { da - afiseaza OK; nu - afiseaza NO}
  * **legatura x** - Afiseaza statiile de metrou cu care exista legatura directa(curierul merge doar o
statie in acest caz).
              * **Exemplu: Statie1 Statie2 Statie3**
                       * Se afiseaza un rand liber in cazul in care nu exista nicio statie de metrou legata
  * **blocaj_tunel x y** – Se blocheaza un drum intre 2 statii de metrou – nu se afiseaza nimic, se
marcheaza cu infinit in cazul in care statia exista 
  * **blocaj_strada x y** - Se aglomereaza o strada(timpul devine infinit) – nu se afiseaza nimic, se
marcheaza cu infinit in cazul in care strada exista
  * **adauga_ruta x y valoare_distanta** – Se construieste un drum intre 2 statii de metrou.
  * **sterge_ruta x y** – Inchide un drum intre doua statii de metrou – inundatie, oprire pentru
reparatii.
  * **adauga_strada x y valoare_distanta** – Se construieste un drum intre 2 clienti.
  * **sterge_strada x y** – Inchide un drum intre doi clienti – oprire pentru reparatii
  * **drum_strada x y** – Calculeaza cel mai scurt timp de la x la y(x si y sunt clienti). Se afiseaza clientii in ordinea in care le-a fost livrata comanda, incepand cu primul si pana la ultimul.
Afisarea se face sub forma unui vector de string-uri ce contine numele clientilor la care curierul a livrat.
  * **drum_metrou x y** – Calculeaza cel mai scurt drum de la x la y(x si y sunt statiile de metrou). Se afiseaza numele statiilor inecepand cu prima statie si pana la ultima. Afisarea se face sub foma unui
vector de string-uri ce contine numele clientilor la care curierul a livrat.
  * **timp_statie x** – Calculeaza timpul minim necesar livrarii comenzii la Statia x. Curierul opteaza pentru parcurgerea drumului cel mai scurt catre primul client si mai apoi se parcurge
drumul cel mai scurt de la clientul respectiv la toti clientii. De la ultimul client micul strateg alege
direct strada care face legatura cu metroul
  * **comanda_statie valoare_suma** – Afiseaza statiile in urma carora curierul obtine o suma mai
mare sau egala cu numarul “Valoare_suma” 

=== Backtracking ===

Dupa ce micul strateg reuseste sa devina un „Mare strateg”, voi fiind responsabili in totalitate pentru
reusita lui, curierul trebuie sa isi incheie activitatea prin depunerea sumei colectate din coletele achitate
de catre clienti. El poate depune aceasta suma la orice sediu al firmei, insa nu mai poate folosi ca mijloc
de transport metroul. De specificat faptul ca fiecare statie de metrou are asociata un sediu.

Luand in considerare faptul ca drumul arata ca un labirint, fiind intregit doar din strazi la stanga sau la
dreapta (numarul strazi merge la stanga = numarul de strazi merge la dreapta), sa il ajutam in continuare
pe Marele strateg isi indeplineasca toate cerintele:

**Sa se determine cel mai scurt timp in care curierul poate sa ajunga la sediu.**
  * Problema poate fi vazuta ca o matrice care are asociat timpul pe fiecare strada. Timpul, cel mai
mare adversar al marelui nostru strateg sufera modificari la fiecare noua deplasare. 
  * De asemenea, regula de parcurgere a drumului presupune deplasarea dintr-un colt in altul al
diagonalei principale din matrice. 

**Se poate face si o metoda mai inteligenta decat implementarea cu Backtracking. De asemenea, in exemplul din poza este ales un exemplu Greedy. Mare atentie cum implementati alegerea drumului.**

===== Date de iesire =====
** Fisierul rezultate.out **

Fişierul de ieşire va conţine rezultatele operaţiilor ce generează un răspuns. Rezultatele sunt scrise în
ordinea în care sunt scrise operaţiile primite la intrare, fiecare rezultat este urmat de un final de linie.

In cazul testelor cu Backtraking, pe ultima linie a fisierului este timpul minim pana la sediu. 

===== 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ă (19 Mai, 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.
* Arhiva trimisă conține (direct în rădăcină):
      - Fişierul sau fişierele (.c) cu codul programului;
      - Makefile-ul (cu regulile **make build** și **make clean**). Executabilul generat trebuie să se numească **curier**;
      - fișierul README în care va fi descrisă soluția problemei.

==== Restricții ====
  * Implementarea se va face folosind limbajul C;
  * Implementarea se va face folosind **GRAFURI**. Se recomanda folosirea pointerilor și eliberarea memoriei.;
  * 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).Operațiile pe structurile de date de tip grafuri se fac folosind funcții clare cu scop precis Orice alte manipulări de date se fac, pe cat posibil, prin funcții specializate.
;
  * Memoria trebuie eliberată. Dacă nu se respectă această cerință depunctarea este de pana la 10/100 pct (restricție aplicabila de la 60 de puncte in sus).
  * 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);
  * 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;
  * Se va depuncta cu pana 15% din punctajul obtinut implementarea care nu foloseste tipuri de date specifice pentru entitatile din cerinta (ex: Client, Statie)





<note important>Temele care vor fi copiate vor primi -5 pct şi studenţii implicaţi - mustrări şi vor figura pe blacklist-ul cursului de SDA.</note>