Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | escape.in, escape.out | Sursă | ProSoft@NT 2017 |
Autor | Alexandru Ionita | Adăugată de | |
Timp execuţie pe test | 0.6 sec | Limită de memorie | 131072 kbytes |
Scorul tău | N/A | Dificultate | N/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 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.in | escape.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...