== include(page="template/taskheader" task_id="aparare") ==
Poveste şi cerinţă...
Se consideră $N$ puncte strategice aflate în administrarea Ministerului Apărării (MA). Pentru fiecare pereche de puncte se cunoaşte costul de conectare directă, în caz că se doreşte realizarea conectării directe a punctelor din acea pereche.
# Să se aleagă un număr de perechi de noduri a căror conectare va fi efectiv implementată astfel încât, la finalul lucrării, între oricare dintre cele $N$ noduri să existe comunicare directă sau indirectă prin conexiunile realizate şi, în plus, costul total al lucrărilor să fie minim.
# Comandamentul Trupelor de Uscat (CTU) va prelua $5$ dintre cele $N$ noduri, astfel încât, conform strategiei de conectare stabilită la (1), comunicarea între oricare dintre cele $5$ noduri să se realizeze fie direct, fie folosind numai puncte preluate de CTU. Ştiind că toate costurile de conectare (stabilite la (1)) dintre cele $5$ puncte vor fi plătite de CTU, să se aleagă convenabil cele $5$ noduri astfel încât costul conectărilor (de la (1)) rămase în responsabilitatea MA să fie minim.
h2. Date de intrare
Fişierul de intrare $aparare.in$ ...
Fişierul de intrare $aparare.in$ conţine pe prima linie valoarea lui $N$, numărul de puncte strategice şi pe următoarele $N - 1$ linii, valori reprezentând costurile de conectare dintre puncte. Astfel, pe fiecare linie $i$ din fişier ($i > 1$) se află $i - 1$ valori reprezentând costurile de conectare dintre nodul $i$ şi nodurile $1, 2, ..., i - 1$.
h2. Date de ieşire
În fişierul de ieşire $aparare.out$ ...
În fişierul de ieşire $aparare.out$ va conţine pe prima linie un număr natural reprezentând costul total de conectare de la (1), iar pe linia a doua costul total rămas după preluarea de către CTU a celor $5$ puncte strategice alese convenabil.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $5 ≤ N ≤ 9999$
* Costurile de conectare sunt numere naturale strict pozitive *distincte* de cel mult $9$ cifre fiecare.
* Costul de conectare de la nodul $i$ la nodul $j$ este acelaşi cu costul de conectare de la nodul $j$ la nodul $i$, oricare ar fi $1 ≤ i, j ≤ N$.
* Se acordă $40%$ din punctaj pentru prima valoare corectă şi $100%$ din punctaj pentru ambele valori corecte.
h2. Exemplu
table(example). |_. aparare.in |_. aparare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
5
3 11
7 2 1
6 10 4 14
9 16 8 20 18
| 18
2
|
h3. Explicaţie
...
Se conectează perechile: $3-1$, $3-4$, $3-5$, $3-6$, $2-4$ obţinându-se costul total minim $18$.
Se preiau de către CTU punctele $1$, $3$, $4$, $5$ şi $6$, cu costurile aferente de conectare, MA plătind doar conectarea $2-4$ cu costul $2$.
== include(page="template/taskfooter" task_id="aparare") ==
