Unelte utilizator

Unelte site


teme-2020:tema-1

Aceasta e o versiune anterioară a paginii.


Tema 1: ATP Cup

Obiective

  1. Înțelegerea conceptului de funcționare și implementarea structurilor de date (liste, stive, cozi și arbori binari de căutare)
  2. Operarea cu structurile de date
  3. Implementarea funcționalităților practice care să folosească conceptele menționate anterior

Informații

  1. Deadline hard, 14 aprilie ora 23:59 (termen limită - nu se obţin puncte pe soluţiile trimise mai târziu)
  2. Încărcarea 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 adresa
  4. Puteţi cere ajutor oricând la email

Descriere

În cadrul Turneului Internațional de Tenis ATP Cup, fiecare stat participant are un lot de jucători. Acest lot urmează să-și reprezinte țara într-o succesiune de meciuri jucate contra membrilor celorlalte loturi. Se dorește realizarea unei soluții software care să automatizeze desfășurarea turneului.

Input

Prima linie a fișierului date.in va conține un număr natural, reprezentând numărul țărilor participante. În continuare, pentru fiecare țară participantă se vor găsi următoarele date:

  • Un număr natural, reprezentând numărul de jucători al lotului, pe o linie;
  • Numele țării, pe următoarea linie;
  • Numele, prenumele și scorul personal al unui jucător, pe câte o linie pentru fiecare jucător în parte;

Cerințe

  • Fișierul cerinte.in va conține pe prima linie 5 cifre (0 sau 1) separate printr-un spațiu. Fiecare cifră corespunde fiecărei cerințe, iar valoarea ei hotărăște dacă fișierul date.out va conține ieșirea cerinței respective.
  • Exemplu: “1 1 1 0 0”. Se vor rezolva doar cerințele 1, 2 și 3, deoarece cifrele corespunzătoare lor sunt “1”, cifrele corespunzătoare cerințelor 4 și 5 sunt “0”.
  • În cazul în care a 5-a cifră este “1”, adică cerința 5 trebuie rezolvată, pe următoarele două linii ale fișierului se vor găsi numele, prenumele și scorul personal după terminarea turneului a doi jucători. Acestea reprezintă datele de intrare pentru cerința 5 (detalii mai jos).
  • Exemplu:

1 1 1 1 1

  Haas Tommy 56
  Federer Roger 87

- Se vor rezolva toate cerințele, iar datele de intrare pentru cerința 5 sunt “Haas Tommy 56” și “Federer Roger 87”.

  • 1. Se va crea o listă dublu înlănțuită, circulară, cu santinelă, pentru stocarea țărilor participante. Țările se vor adăuga întotdeauna la finalul listei. (Nu la începutul acesteia). Cine nu respectă structura respectivă va primi 0p
  • 2. Din lista anterior creată se vor elimina țări, până când numărul lor devine cea mai mare putere a lui 2 posibilă (exemplu: Dacă există 63 de țări, se vor elimina până când numărul lor ajunge la 32 = 2 la puterea a 5-a). Eliminarea țărilor se face după următorul criteriu:
Se elimină țări al cărei scor inițial este minim. Scorul inițial este reprezentat de media aritmetică a scorurilor personale ale jucătorilor din lotul țării respective. După eliminarea unei țări, procedeul se reia pornind de la santinela listei circulare. În cazul în care, pentru ultima eliminare din listă, există mai multe țări cu același scor inițial minim, este eliminată prima țară cu scorul inițial minim găsită în parcurgerea listei pornind de la santinelă.
  • Scorul inițial al unei țări, reprezentat de media aritmetică a scorurilor personale ale jucătorilor din lotul țării respective este relevant DOAR în cadrul acestei cerințe. Acesta NU se adaugă la scorul global al țării respective. Practic, acest scor NU se va mai folosi în rezolvarea ulterioară a cerințelor.
  • A nu se confunda cu scorul local sau scorul global al unei țări (aflăm în cadrul următoarei cerințe despre aceste scoruri) pe parcursul turneului!!! Toate țările vor începe cu un scor global egal cu 0.
  • 3. Se vor implementa următoarele structuri de date și se vor realiza următoarele procedee asupra lor pentru buna desfășurare a turneului:
    • Se va crea o stivă în care se vor adaugă toate țările rămase în turneu, pornind de la santinelă.
    • Se vor scoate din stivă succesiv câte 2 țări, între care urmează să fie jucate meciurile. Procedeul se repetă până când stiva este goală.
      <note important>Scorul local reprezintă scorul acumulat de fiecare țară pe parcursul meciurilor dintre jucători (până când coada meciurilor se golește).</note>
  • Pentru fiecare pereche de țări extrasă din stiva se va crea o coadă în care se vor pune meciurile dintre jucători.
  • Fiecare jucător din lotul primei țări va juca cu fiecare jucător din lotul celei de-a doua țări, în următoarea ordine: primul jucător din lotul primei țări se confruntă, pe rând, cu toți jucătorii din cel de-al doilea lot, al doilea jucător din lotul primei țări cu toți jucătorii din cel de-al doilea, etc.
  • Jucătorul cu scorul personal mai mare câștigă. Acestuia i se adaugă 5 puncte la scorul personal, iar țara pentru care joacă primește 3 puncte la scorul local.
  • În cazul în care cei doi jucători au scoruri personale egale, se consideră egalitate. Fiecărui jucător i se adaugă câte 2 puncte la scorul personal, iar fiecare țară primește câte 1 punct la scorul local.
Observație: Scorul global reprezintă scorul acumulat de fiecare țară pe parcursul întregului turneu, după toate etapele acestuia. Fiecare țară va începe turneul cu scorul global 0.
  • Coada meciurilor dintre două țări s-a golit. Confruntarea dintre cele două s-a terminat. Urmează verificarea scorurilor locale ale celor două țări. Celor doua țări li se adaugă scorul local, acumulat pe parcursul meciurilor dintre jucători, la scorul global, dar câștigătoare este doar țara cu scorul local mai mare.
  • În cazul egalității dintre scorurile locale ale celor două țări, este considerată câștigătoare țara în lotul căreia se află jucătorul cu cel mai mare scor personal (dintre scorurile personale ale jucătorilor celor două țări).
  • Se va crea o stivă WINNER, în care se vor adăuga țările câștigătoare în urma meciurilor.
  • Când stiva inițială devine goală, putem considera încheiată această etapă a turneului. Se vor scoate țările din stiva WINNER și se vor adăuga pe rând în stiva inițială. Se vor repeta procedeele anterioare pentru fiecare etapă a turneului, cu alte cuvinte până când în stiva WINNER va rămâne, în final, o singură țară câștigătoare.
  • 4. Se va crea un BST – arbore binar de căutare, în care se vor afla jucătorii ultimelor 4 țări rămase în turneu, în funcție de scorul personal obținut o dată cu terminarea ultimei etape a turneului.
  • În cazul în care unul dintre jucători are același scor personal cu unul deja existent în arbore, va fi adăugat jucătorul al cărui nume este mai mic din punct de vedere lexicografic.
  • 5. În fișierul cerinte.in, așa cum a fost prezentat anterior, se vor găsi numele și prenumele a 2 jucători. Se cere numărarea jucătorilor care se află între aceștia în BST (cei 2 jucători nu se includ). Mai explicit, se cere numărul jucătorilor care au scorul personal inclus între cele două scoruri personale.
Observație: Dacă un jucător din cei doi primiți ca input nu se găsește în BST, se va afișa un mesaj corespunzător. De asemenea, se garantează faptul că cel puțin un jucător se găsește în BST.

Punctaje și Detalii Tehnice

Punctaje:

Tema are un total de 150 puncte. Verificarea temei se face prin 15 teste. Fiecărei cerințe îi corespund 3 teste. Punctajele cerințelor sunt împărțite, în funcție de complexitate, în modul următor:

  • Cerința 1 – 30 puncte (10 puncte / test)
  • Cerința 2 – 15 puncte (5 puncte / test)
  • Cerința 3 – 45 puncte (15 puncte / test)
  • Cerința 4 – 30 puncte (10 puncte / test)
  • Cerința 5 – 15 puncte (5 puncte / test)

Total: 135 puncte Restul de 15 puncte corespund fișierului README în care va fi descrisă soluția, Coding Style-ului și comentariilor din cod, după cum urmează:

  • Fișier README – 10 puncte
  • Coding Style + Comentarii – 5 puncte

Detalii Tehnice

  • Rezultatele obținute în urma executări cerințelor din fișierul cerinte.in vor fi scrise în fișierul rezultate.out
  • Pentru cerințele 1 și 2 este suficientă scrierea în fișierul de rezultate a numelor echipelor și a punctajelor acestora, în ordinea din lista creată, pe câte o linie separată.
  • Pentru cerința 3 se va scrie în fișier la fiecare rundă conținutul cozii de meciuri alături de conținutul stivei de învingători.
  • Pentru cerința 4 se dorește afișarea BST-ului în ordinea descrescătoare a scorului personal. Adică afișarea clasamentului în ordine descrescătoare.
  • Pentru cerința 5 se dorește afișarea numărului jucătorilor care au scorul inclus între cele două scoruri personale.
  • Structurile de date necesare trebuie deduse astfel încât sa respecte normele de bună implementare Ex: un jucător are nume, prenume, scor - prin urmare se va folosi un tip de date care să caracterizeze această entitate:(Același lucru trebuie făcut și pentru alte tipuri de date necesare realizării aplicației.)
//Structura pentru jucator:
typedef struct Player { 
   char *last_name;
   char *first_name;
   int score;
} Player;
 
//Structura pentru tara:
typedef struct Country {
   char *name;
   int nr_players;
   int global_score;
   Player *players;
} Country;

Output

Afișarea se va face în fișierul date.out:

  • Pentru cerințele 1 și 2 se vor afișa numele țărilor aflate în lista circulara, începând de la santinela, după eliminarea efectuata la cerința 2.

(Exemplu: “Romania”)

  • Pentru cerința 3 se vor afișa la fiecare etapă:
    1. Numărul etapei.

(Exemplu: “=== Etapa 4 ===”)

  1. Partidele dintre perechile de doua tari extrase succesiv din stiva inițială. Pe lângă numele celor două țări, vor fi afișate și scorurile globale de până în momentul respectiv pentru acestea.

(Exemplu: “Brazilia 12 —– Franta 22”)

  1. Coada cu meciurile dintre jucătorii țărilor extrase succesiv din stiva inițială. Pentru fiecare meci se vor afișa numele, prenumele și scorul fiecăruia dintre cei doi jucători, separate printr-un spațiu. Între cei doi jucători se va afișa un “vs”.

(Exemplu: “Haas Tommy 36 vs Tecau Horia 35”)

  1. Tarile, împreună cu scorul lor global de la acel moment, aflate în stiva WINNER după fiecare etapă.

(Exemplu: “Spania — 21”)

  • Pentru cerința 4 se vor afișa numele, prenumele și scorul personal al jucătorilor aflați în BST (pe câte o linie fiecare, separate printr-un spațiu) în ordine descrescătoare după scorul personal al acestora (fără a folosi vreun vector intermediar sau algoritm de sortare), adaptați o metoda de parcurgere a arborilor din cele cunoscute.
  • Pentru cerința 5 se va afișa numărul jucătorilor aflați între cei 2 jucători primiți ca input. În cazul în care, unul dintre jucători nu se afla în BST, se va afișa mesajul: “Nume_Jucator Prenume_Jucator nu poate fi identificat!\n”.

(Exemplu: “Hanescu Victor nu poate fi identificat!\n”)

Exemplu

Fisierel folosite de checker arata astfel:

cerinte.in
1 0 0 0 0
Obiectivele se vor realiza în funcție de cum apar în fișierul cu cerinte cerinte.in (Spre exemplu dacă fișierul cerinte.in conține 1 0 0 0 0 înseamnă ca se dorește doar realizarea cerinței 1. Se vor folosi ca valori de intrare datele din fișierul date.in)
date.in
3                 // numarul de echipe din fisier
5                 // numarul de jucatori 
Franta            //numele echipei
Serra Florent 31  //numele prenumele si punctajul jucatorului 1
Monfils Gael 25
Pouille Lucas 27
Llondra Michael 30
Gasquet Richard 21
5
Spania
Ferrer David 27
Nadal Rafael 42
Montanes Albert 33
Navarro Ivan 29
Moya Carlos 38
5
Romania
Hanescu Victor 30
Tecau Horia 35
Cruciat Adrian 23
Copil Marius 22
Daescu Andrei 29
În cazul in care un jucator are 2 prenume - acestea sunt scrise cu cratima - si reprezinta un singur sir de caractere. Formatul folosit pentru fprintf este %-25s în cazul afișării meciurilor din coadă.
rezultate.out
 Franta
 Spania
 Romania

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

./tenis cerinte.in date.in rezultate.out

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ă (14 aprilie, 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ă lanParty;
    3. 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 liste. Nu e permisă implementarea cu vector a stivelor, cozii și a listei cu echipe participante. Se recomandă folosirea pointerilor și eliberarea memoriei.
  • Se va evita pe cât posibil duplicarea nodurilor din lista. Pentru abateri grave de la această cerința se vor scădea până la 5 puncte.
  • 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 arbore, coadă, etc se fac folosind funcții - Ex: adaugaNod, stergeNod, etc. Orice alte manipulări de date se fac, pe cât posibil, prin funcții specializate.
  • Memoria trebuie eliberată. Dacă nu se respectă această cerință depunctarea este de pana la 10/100 pct (restricție aplicabilă de la 60 de puncte în 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 pâna 15% din punctajul obținut implementarea care nu folosește tipuri de date specifice pentru entitățile din cerință (ex: Jucător)
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.
teme-2020/tema-1.1583702762.txt.gz · Ultima modificare: 2020/03/08 23:26 de către eduard.ciurezu