Fişierul intrare/ieşire:studenti.in, studenti.outSursăAlgoritmiada 2010, Runda 1
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Studenti

Un grup de N studenti a venit la facultate sa dea un examen si exista 3 sali disponibile in care poti fi repartizati. Fiecare student are o anumita inaltime si greutate. Astfel, fiecare student i are inaltimea Hi si greutatea Gi. Se pune problema unei repartitii cat mai echilibrate in sali a studentilor. In fiecare sala trebuie repartizat cel putin un student si, in mod evident fiecare student trebuie repartizat exact intr-o singura sala. Fie S1, S2 si S3 cele trei sali in care sunt repartizati studenti. O repartitie este cu atat mai echilibrata cu cat valoarea [Gmax(S1)+Gmax(S2)+Gmax(S3)]*[Hmax(S1)+Hmax(S2)+Hmax(S3)] este mai mica (sa numim aceasta valoare echilibrul unei repartitii). Gmax(Si) reprezinta greutatea maxima a unui student din sala Si iar Hmax(Si) inaltimea maxima. Determinati echilibrul minim posibil al unei repartitii.

Date de intrare

Fişierul de intrare studenti.in contine pe prima linie numarul N avand semnificatia din enunt. Urmeaza apoi N linii, pe linia i+1 aflandu-se valorile Hi si Gi, separate printr-un spatiu.

Date de ieşire

În fişierul de ieşire studenti.out se va afisa pe prima linie echilibrul minim posibil al unei repartitii.

Restricţii

  • 3 ≤ N ≤ 300
  • Toate inaltimile studentilor sunt diferite intre ele
  • Toate greutatile studentilor sunt diferite intre ele
  • 1 ≤ Hi, Gi ≤ 2000

Exemplu

studenti.instudenti.out
3
1 1
2 2
3 3
36

Explicaţie

Avem o singura posibilitate, de a plasa cate un student in fiecare sala, si echilibrul obtinut astfel este (2+3+1)*(2+3+1) = 36.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content