Tema 2: Micul – Marele strateg

1. Înțelegerea conceptului de graf și a modurilor de parcurgere aferente
2. Aplicarea algoritmilor studiați pe topologiile de tip graf in exemple practice

1. Deadline hard, 19 Mai ora 23:59 (termen limită - nu se obţin puncte pe soluţiile trimise mai târziu)
2. Trimiterea temelor se face pe platforma vmchecker (folosiți credențialele de pe http://acs.curs.pub.ro).
3. Checker-ul offline îl puteţi descărca de la această adresă
4. Puteţi cere ajutor oricând la această adresă email

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 !

Fisierul date.in

1. Numarul de statii
2. Corespunzator fiecarei statii, fiecare atribut este afisat pe cate un rand
   • Nume_statie
   • Nr_clienti
3. Fiecare client este reprezentat de:
   • Nume_client
   • Timp_fata_de_statia_de_metrou
   • Suma_de_platit
4. Numar_strazi_intre_clienti
5. Pe urmatoarele Numar_strazi_intre_clienti linii avem
   • Client1 Client2 timp
   • Exemplu: Client17 Client20 3
6. Numar_rute
7. Pe urmatoarele Numar_rute linii avem
   • Statie1 Statie2 distanta
   • Exemplu: Statie5 Statie3 2
8. Numar_operatii_strategie
9. Pe urmatoarele Numar_operatii_strategie linii avem operatiile si descrierea lor

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

• Testele 1-5: 45% nota
• Testele 6-10: 40% nota
• Testele 10-13: 15% nota

• 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.

Structurile urmatoare sunt optionale si nu trebuie implementate la fel

Executabilul obținut în urma compilării va avea numele curier, iar regula de rulare va fi:

• 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”

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.

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.

• 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 vmchecker unde vă puteți loga folosind credențialele de pe acs.curs.
• Arhiva trimisă conține (direct în rădăcină):
  1. Fişierul sau fişierele (.c) cu codul programului;
  2. Makefile-ul (cu regulile make build și make clean). Executabilul generat trebuie să se numească curier;
  3. fișierul README în care va fi descrisă soluția problemei.

• 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)