Fişierul intrare/ieşire:path.in, path.outSursăBursele Agora 2004
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Path

Se considera un graf orientat aciclic ce contine N noduri si M arce. Nodurile sunt identificate prin litere distincte ale alfabetului englezesc (sunt permise atat litere mari, cat si litere mici). Un drum este format dintr-o succesiune de arce, iar aceste drumuri sunt ordonate in ordine lexicografica (fiecarui drum ii corespunde un sir de caractere obtinut prin concatenarea literelor corespunzatoare nodurilor, in ordinea in care apar nodurile in drum; se considera ca toate literele mici sunt, din punct de vedere lexicografic, inaintea tuturor literelor mari).
Dintre toate drumurile din graf, sunt luate in considerare doar cele mai lungi (lungimea unui drum este data de numarul de arce care il formeaza). Se cere ca dintre acestea din urma sa se determine cel de-al k-lea in ordine lexicografica.

Date de Intrare

Prima linie a fisierului de intrare path.in contine trei numere intregi N, M si k separate intre ele printr-un singur spatiu.
Fiecare dintre urmatoarele M linii contine doua caractere ale alfabetului englezesc c1 si c2, separate intre ele printr-un singur spatiu, cu semnificatia ca exista un arc care pleaca din nodul identificat prin c1 si ajunge in nodul identificat prin c2.

Date de Iesire

Fisierul de iesire path.out va contine pe o singura linie un sir de caractere care reprezinta drumul determinat. Caracterele acestui sir nu vor fi separate intre ele prin spatii.

Restrictii si precizari

  • Numarul de drumuri de lungime maxima este mai mare sau egal decat k.
  • 2 ≤ N ≤ 52
  • 1 ≤ M ≤ N(N-1) / 2
  • Intre doua noduri poate exista cel mult o muchie.
  • 1 ≤ K ≤ 2.000.000.000

Exemplu

path.inpath.out
3 3 1
a b
b c
a c
abc
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content