Diferente pentru problema/asmin intre reviziile #2 si #1

Diferente intre titluri:

asmin
Asmin

Diferente intre continut:

== include(page="template/taskheader" task_id="asmin") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| asmin.in | asmin.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="asmin") ==
==Include(page="template/taskheader" task_id="asmin")==
==Include(page="template/raw")==
 
Asmin
 
 
 
Se considera un arbore (graf conex aciclic) cu N varfuri, fara radacina fixata. Drept radacina, poate fi ales oricare dintre varfuri. Sa presupunem ca a fost ales varful cu numarul T. Intre oricare varf si T exista un drum unic care contine fiecare varf al arborelui cel mult o singura data (un drum intre varfurile i si j este o secventa de varfuri, care incepe cu i, se termina cu j, iar intre oricare doua varfuri consecutive exista o muchie in arbore). Fiecarui varf i(inclusiv T) trebuie sa i se asocieze o valoare V[i], mai mare sau egala cu 0, astfel incat suma valorilor varfurilor de pe drumul dintre i si radacina T, impartita la K, sa dea restul R[i]. Se defineste costul arborelui cu radacina fixata in T, C[T], ca fiind suma valorilor asociate fiecarui nod. Dintre toate posibilitatile de alegere a valorilor V[i] care respecta conditia precizata anterior, se va alege aceea pentru care C[T] este minim.
 
Se constata usor ca alegand alt varf drept radacina, de exemplu, varful S (diferit de T), C[S] nu este neaparat egal cu C[T].
 
h2. Cerinta
 
Dandu-se un arbore cu N varfuri, un numar intreg K si valorile R[i], i=1,2,..,N, corespunzatoare fiecarui varf, determinati acele varfuri T care pot fi alese drept radacina, pentru care costul C[T] este minim (adica C[T]<=C[S], oricare ar fi S diferit de T), precum si costul respectiv.
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare asmin.in se afla 2 valori intregi: N si K. Pe urmatoarele N-1 linii se afla cate doua numere intregi a b, separate printr-un spatiu, avand semnificatia ca exista muchie intre varfurile a si b. Varfurile sunt numerotate de la 1 la N. Pe urmatoarea linie se afla N numere intregi, reprezentand valorile R[i], i=1,2,..,N.
 
h2. Date de Iesire
 
Pe prima linie a fisierului de iesire asmin.out se vor afisa doua valori intregi: C si M. C reprezinta costul minim posibil al arborelui. M reprezinta numarul de varfuri care pot fi alese drept radacina si pentru care se obtine costul C. Pe a doua linie se afla M numere intregi separate prin cate un spatiu, scrise in ordine crescatoare, reprezentand numerele varfurilor ce pot fi alese ca radacina astfel incat sa se obtina costul C.
 
h2. Restrictii si precizari
 
. 2 <= N <= 16.000
 
. 2 <= K <= 1.000
 
. 0 <= R[i] <= K-1
 
h2. Exemplu
 
asmin.in asmin.out Explicatie
5 3 5 2 Valorile asociate varfurilor celor doi arbori sunt urmatoarele:
 
1 2 1 5 V[1]=0 V[2]=1 V[3]=2 V[4]=0 V[5]=2
 
1 3 V[1]=2 V[2]=1 V[3]=2 V[4]=0 V[5]=0
 
2 4
 
2 5
 
0 1 2 1 0
 
 
==Include(page="template/taskfooter" task_id="asmin")==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.