Inverseaza reviziile

Diferente pentru problema/path intre reviziile #2 si #5

Diferente intre #1 si #2

Diferente intre titluri:

path

Path

Diferente intre continut:

== include(page="template/taskheader" task_id="path") ==

==Include(page="template/taskheader" task_id="path")==

Poveste ...

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.

h2. Cerinta

h2. 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 $c[1]$ si $c[2]$, separate intre ele printr-un singur spatiu, cu semnificatia ca exista un arc care pleaca din nodul identificat prin $c[1]$ si ajunge in nodul identificat prin $c[2]$.

h2. Restrictii

h2. 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.

h2. Date de intrare

h2. Restrictii si precizari

...
 
h2. Date de iesire
 
...

* 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$

h2. Exemplu

| path.in | path.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. path.in |_. path.out |
| 3 3 1
a b
b c
a c
| abc |

== include(page="template/taskfooter" task_id="path") ==

==Include(page="template/taskfooter" task_id="path")==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 

1024