| Fişierul intrare/ieşire: | studenti.in, studenti.out | Sursă | Algoritmiada 2010, Runda 1 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | studenti.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.
