Fişierul intrare/ieşire:	aparare.in, aparare.out	Sursă	Tabăra ICHB 2012, Ziua 2, Grupa 2
Autor	Rodica Pintea	Adăugată de	Dan-Constantin Spatarel •spatarel
Timp execuţie pe test	0.625 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Aparare

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.

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

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

Date de intrare

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.

Date de ieşire

Î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.

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.

Exemplu

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.

Cum se trimit solutii?