Tema 3: Instalatia de craciun!

1. Deadline hard, 20 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 numele de utilizator şi parola de pe http://acs.curs.pub.ro).
3. Checker-ul offline poate fi descărcat de la această adresă
4. Puteţi cere ajutor oricând la această adresă email

1. 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;

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.

Asadar, decide sa nu mai stea pe ganduri si sa se apuce de lucru cat mai repede . El isi comanda de pe un website chinezesc foarte multe leduri de diverse culori la un pret foarte mic dar dupa ce primeste comanda, acesta constata ca ledurile sunt amestecate si trebuie organizate pe culori. El ia fiecare led pe rand si il testeaza pentru a le putea eticheta bine. 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. 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.

1. Determinati diferenta maxima de intenistate intre doua leduri invecinate si precizati cate perechi de leduri au aceasta diferenta.
2. BONUS : Determinati numarul minim de leduri ce trebuiesc scoase pentru a obtine o instalatie cu intensitatiile ledurilor in ordine descrescatoare .
3. 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.
4. 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!!!

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

• 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 vmchecker unde vă puteți loga folosind credențialele de pe acs.curs.

• 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ă):
  1. fisierele sursa (.c sau .cpp)
  2. Makefile-ul (cu regulile make build și make clean). Executabilul generat trebuie să se numească leduri;
  3. 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.