Fişierul intrare/ieşire:escape.in, escape.outSursă[email protected] 2017
AutorAlexandru IonitaAdăugată devaliro21FII Valentin Rosca valiro21
Timp execuţie pe test1.2 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 din graful din figura, costul acestui drum pentru K = 3 este: 3*40+1*41+2*42=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 se numeste 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

In fişierul de intrare escape.in, pe prime linie se vor gasi 3 numere naturale: N, M si K, in aceasta ordine.
Pe urmatoare linie se vor gasi M numere distincte, reprezentand indicii nodurilor albe din graf.
Urmeaza o matrice A cu N linii si K coloane unde Ai,j reprezinta un arc care pleaca din nodul i si ajunge in nodul Ai,j si are costul j.

Date de ieşire

În fişierul de ieşire escape.out afisati, in ordine lexicografica, cate una pe fiecare linie, toate multimile perfecte de cardinal maxim (elementele din cadrul multimilor vor fi sortate in ordine crescatoare)

Restricţii

30 pct:

  • 1 ≤ K ≤ 10
  • 1 ≤ M ≤ N ≤ 15
  • 1 ≤ Ai,j ≤ N

60 pct:

  • 1 ≤ K ≤ 30
  • 1 ≤ M ≤ N ≤ 50
  • 1 ≤ Ai,j ≤ N

100 pct:

  • 1 ≤ K ≤ 50
  • 1 ≤ M ≤ N ≤ 500
  • 1 ≤ Ai,j ≤ N

Exemplu

escape.inescape.out
3 1 2
3
2 3
1 3
3 3
1 2
3

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?