Unelte utilizator

Unelte site


teme2018:tema-3

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
teme2018:tema-3 [2017/10/03 19:43]
nicolae.cociorba
teme2018:tema-3 [2018/05/09 23:48] (curent)
mihai.iacov [Informaţii]
Linia 1: Linia 1:
-====== Tema 3: Greedy, Elemente de Programare Dinamica si Backtracking. ======+====== Tema 3: Instalatia de craciun! ======
  
 +==== Informaţii ====
 +  - Deadline hard, **20 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/|vmchecker]] (folosiți numele de utilizator şi parola de pe http://acs.curs.pub.ro).
 +  - Checker-ul offline poate fi descărcat de la această [[https://drive.google.com/file/d/18y_ser5KDA-2xc5UHY7W9vnYCYPgQekx/view?usp=sharing|adresă]] 
 +  - Puteţi cere ajutor oricând la această adresă [[sda-ab-tema3@googlegroups.com|email]]
  
 +==== Modificări temă====
 +  - 09/05/2018 23:45
 +     * corecturi checker - date intrare - rezistenţele de la unele teste nu îndeplineau condiţiile pentru ca o abordare Greedy să ducă la rezultatul cel mai bun pentru cerinţa 3;
 +
 +
 +
 +==== Descriere ====
 Dezamagit de bradul sau de Craciun, Andrei decide ca anul acesta va avea cel mai frumos brad. El se hotaraste sa isi creeze o propria instalatie de lumini cu care isi va impresiona toti vecinii si prietenii din cartier. Dezamagit de bradul sau de Craciun, Andrei decide ca anul acesta va avea cel mai frumos brad. El se hotaraste sa isi creeze o propria instalatie de lumini cu care isi va impresiona toti vecinii si prietenii din cartier.
  
Linia 8: Linia 20:
 In timpul testelor acesta observa un lucru surprinzator: desi doua leduri au aceeiasi culoare, acestea lumineaza cu intensitati diferite  In timpul testelor acesta observa un lucru surprinzator: desi doua leduri au aceeiasi culoare, acestea lumineaza cu intensitati diferite 
 Elev bun fiind, Andrei stie sa masoare intensitatea luminoasa a ledurilor si stie ca o poate modifica dupa bunul plac adaugand rezistente de diferite valori in instalatia sa. Elev bun fiind, Andrei stie sa masoare intensitatea luminoasa a ledurilor si stie ca o poate modifica dupa bunul plac adaugand rezistente de diferite valori in instalatia sa.
-Deoarece este abia luna Mai?,  Andrei vrea sa faca cat mai multe simulari pe calculator inainte sa se apuce efectiv de lucru deoarece nu vrea sa greseasca nimic in timpul instalarii ledurilor si are nevoie de ajutorul vostru.+Deoarece este abia luna Mai,  Andrei vrea sa faca cat mai multe simulari pe calculator inainte sa se apuce efectiv de lucru deoarece nu vrea sa greseasca nimic in timpul instalarii ledurilor si are nevoie de ajutorul vostru. 
 + 
 +==== Cerinţe ==== 
 + 
 +  -  Determinati diferenta maxima de intenistate intre doua leduri invecinate si precizati cate perechi de leduri au aceasta diferenta. 
 +  - **BONUS : Determinati numarul minim de leduri ce trebuiesc scoase pentru a obtine o instalatie cu intensitatiile ledurilor in ordine descrescatoare .** 
 +  - Cunoscand rezistentele disponibile si intensitatea scazuta de fiecare rezistenta. Precizati numarul minim (folosind o abordare Greedy) de rezistente utilizate pentru a aduce toate ledurile la o intensitate egala cu Y. Daca nu se poate afisati -1. 
 +  - Aflati cate moduri de organizare a ledurilor exista astfel incat sa nu existe doua leduri de aceeiasi culoare unul langa altul iar diferenta dintre intensitatile lor sa nu fie mai mare de K . 
 + 
 +**Precizari:** 
 +  * Intensitatile luminoase ale ledurilor sunt reprezentate de numere intregi. 
 +  * Pentru fiecare led se cunosc : culoarea si intensitatea sa 
 +  * Culori: R , O , G , V , A  
 +  * Pentru fiecare rezistenta disponibila se cunoaste intensitatea pe care aceasta o scade.  
 +  * Ex. (“R1 100” = “R1 scade intensitatea cu 100” )  
 +  * La cerinta 3 dispuneti un numar nelimitat de rezistente din fiecare tip!!! 
 + 
 +==== Date I/O ==== 
 + 
 + 
 +**Cerinte.in** 
 +        * prima linie conține 4 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 -> se vor realiza doar cerințele 2, 3). 
 + 
 +**Exemplu:** 
 +  1 1 1 1 
 +   
 +**Leduri.in** 
 + 
 +In acest fisier se afla pe prima linie numerele : N , Y ,K cu semnificatia precizata mai jos si N linii reprezentand in ordine: eticheta ledului,culoarea si intensitatea luminoasa. 
 +N = numarul de leduri dintr-o configuratie 
 +Y = intensitatea la care trebuie aduse ledurile (cerinta 3) 
 +K = diferenta de intensitate acceptata (cerinta 4) 
 + 
 +**Exemplu:** 
 + 
 +  5 55 40 
 +  Led1 R 90 
 +  Led2 V 100 
 +  Led3 O 75 
 +  Led4 R 80 
 +  Led5 G 55 
 + 
 + 
 + 
 +**Rezistente.in** 
 + 
 +In acest fisier sa gaseste pe prima linie un numar natural M ce reprezinta numarul de rezistente disponibile si M linii reprezentand eticheta rezistentei si valoarea cu care aceasta scade intensitatea unui led. 
 + 
 +**Exemplu:** 
 + 
 +  3 
 +  R1 1 
 +  R2 5 
 +  R3 10 
 + 
 + 
 +**Rezultat.out** 
 + 
 +  25 2 
 +  2 
 +  14 
 +  48 
 +   
 +In acest fisier se vor afla in ordine:  
 +Pe prima linie: diferenta maxima si numarul de perechi care respecta aceasta diferenta 
 +Pe a doua linie: numarul minim de leduri ce trebuiesc eliminate 
 +Pe a treia linie: numarul de rezistente utilizat 
  
-** = to be deleted +<note tip> 
-Cerinte: +Executabilul obținut în urma compilării va avea numele **leduri** iar regula de rulare va fi
-Cerinta 1: Determinati diferenta maxima de intenistate intre doua leduri invecinate si precizati cate perechi de leduri au aceasta diferenta. +**
-**easy , parcurgeri array si facut un maxim +
-Cerinta 2: Determinati numarul minim de leduri ce trebuiesc scoase pentru a obtine o instalatie cu intensitatiile ledurilor in ordine descrescatoare . +
-** longest decreasing subsequence ( P.D) reinventata +
-Cerinta 3: Cunoscand rezistentele disponibile si intensitatea scazuta de fiecare rezistenta. Precizati numarul minim de rezistente utilizate pentru a aduce toate ledurile la o intensitate mai mica sau egala cu Y. +
-**problema platii unei sume (Greedy sau ?P.D? vedem ce teste este dam ) +
-BONUS : Aflati cate moduri de organizare a ledurilor exista astfel incat sa nu existe doua leduri de aceeiasi culoare unul langa altul iar diferenta dintre intensitatile lor sa nu fie mai mare de K . +
-**backtracking problema permutarilor cu cateva conditii in + +
-Precizari+
- Intensitatile luminoase ale ledurilor sunt reprezentate de numere intregi de la 0 la 99. +
- Pentru fiecare led se cunosc : culoarea si intensitatea sa +
- Culori: R , O , G , V , A **mai putem adauga sa iasa frumos testele la BONUS +
- Pentru fiecare rezistenta disponibila se cunoaste intensitatea pe care aceasta o scade.  +
- Ex. (“R1 100” = “R1 scade intensitatea cu 100” )  +
- La cerinta 3 dispuneti un numar nelimitat de rezistente din fiecare tip!!!+
  
 +./leduri Rezistente.in Leduri.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ă (20 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.
  
 +==== Restricții ====
 +  * 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ă):
 +      - fisierele sursa (.c sau .cpp)
 +      - Makefile-ul (cu regulile **make build** și **make clean**). Executabilul generat trebuie să se numească leduri;
 +      - 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.
teme2018/tema-3.1507049026.txt.gz · Ultima modificare: 2017/10/03 19:43 de către nicolae.cociorba