Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-03-04 15:24:12.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:escape.in, escape.outSursăProSoft@NT 2017
AutorAlexandru IonitaAdăugată devaliro21Valentin Rosca valiro21
Timp execuţie pe test0.6 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Escape

Poveste şi cerinţă...

Se da un graf orientat cu N noduri. Din fiecare nod pleaca exact K arce de costuri 1,2...K (Cate un arc de fiecare cost). Pot exista arce multiple intre 2 noduri, si arce de la un nod la acelasi nod. Un drum este o succestiune de arce...care poate trece prin acelasi nod si prin aceeasi muchie de mai multe ori. Costul unui drum de lungime L este calculat astfel: Costul primului arc inmultit cu (K+1)0, adunat cu costul celui de-al doilea arc inmultit cu (K+1)1,... adunat cu costul celui de-al L-lea arc inmultit cu (K+1)L-1.
Spre exemplu, pentru drumul de la 1 la 4 in
graful de mai jos, costul acestui drum
pentru K = 3 este :
3*4 0 + 1*4 1 + 2*4 2 = 39
Nodurile sunt colorate in 2 culori: alb si
negru. Exista M noduri albe, iar restul sunt
negre.
Doua noduri sunt simetrice daca pentru un orice cost S posibil, drumurile de cost
exact S care pleaca din cele doua noduri ajung in noduri de aceeasi culoare. (Daca
nodurile A si B sunt simetrice, atunci nu exista un drum de cost S care pleaca din
nodul A si un drum de acelasi cost din nodul B care sa ajunga in doua noduri de
culoari diferite)
O multime de noduri s.n. perfecta, daca oricum am alege doua noduri din aceasta
multime, ele sunt simetrice.
O multime se numeste perfecta de cardinal maxim daca oricum am adauga un alt nod
la multimea respectiva, aceasta nu mai indeplineste conditia de a fi perfecta.
Scopul vostru este sa afisati toate multimile perfecte de cardinal maxim. Afisati
multimile in ordine lexicografica, cate una pe rand. (in cadrul unei multimi, elementele
trebuie sortate in ordine crescatoare).

Date de intrare

Fişierul de intrare escape.in ...

Date de ieşire

În fişierul de ieşire escape.out ...

Restricţii

  • ... ≤ ... ≤ ...

Exemplu

escape.inescape.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?