Pagini recente » Monitorul de evaluare | Diferente pentru problema/dungeon intre reviziile 3 si 4

Diferente pentru problema/dungeon intre reviziile #3 si #4

Nu exista diferente intre titluri.

Diferente intre continut:

Fie G un graf neorientat cu 2 ∗ N noduri și 3 ∗ N − 2 muchii. Fiecare muchie este colorată în alb, negru sau roșu.
Se garantează următoarele:

		§  Există N − 1 muchii albe. Capetele lor sunt noduri din mulțimea 1, 2, . . . , N. Ele formează un  arbore.  
		§  Există N − 1 muchii negre. Capetele lor sunt noduri din mulțimea N + 1, N + 2, ..., 2 ∗ N.  Ele formează un arbore.  
		§  Există N muchii roșii. Fiecare muchie are un capăt în mulțimea 1, 2, . . . , N și celălalt capăt în  mulțimea N + 1, N + 2, ..., 2 ∗ N. Cele 2 * N capete ale muchiilor roșii sunt distincte două câte două. Cu alte cuvinte, fiecare nod  din graf are exact o muchie roșie incidentă.  Numim ciclu hamiltonian special un ciclu care: § vizitează fiecare nod al grafului exact o dată. § nu parcurge consecutiv două muchii de aceeași culoare. § începe din nodul 1, iar prima muchie parcursă este de culoare roșie.

		• Există N − 1 muchii albe. Capetele lor sunt noduri din mulțimea 1, 2, . . . , N. Ele formează un  arbore.  
		• Există N − 1 muchii negre. Capetele lor sunt noduri din mulțimea N + 1, N + 2, ..., 2 ∗ N.  Ele formează un arbore.  
		• Există N muchii roșii. Fiecare muchie are un capăt în mulțimea 1, 2, . . . , N și celălalt capăt în  mulțimea N + 1, N + 2, ..., 2 ∗ N. Cele 2 * N capete ale muchiilor roșii sunt distincte două câte două. Cu alte cuvinte, fiecare nod  din graf are exact o muchie roșie incidentă.  
 
Numim ciclu hamiltonian special un ciclu care: 
    • vizitează fiecare nod al grafului exact o dată. 
    • nu parcurge consecutiv două muchii de aceeași culoare. 
    • începe din nodul 1, iar prima muchie parcursă este de culoare roșie.

h2. Cerinta

Fișierul de ieșire dungeon.out va conține pentru fiecare din cele T teste câte o linie cu 2 ∗ N valori reprezentând succesiunea nodurilor care formează ciclul hamiltonian special al fiecărui graf dat, respectiv valoarea -1 dacă nu există un astfel de ciclu.

h2. Restrictii si precizari

• N ≤ 50000
• T ≤ 5
• Pentru teste in valoare de 20 puncte se garantează că N ≤ 10

4 6
| -1
1 7 6 4 3 5 8 2

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

infoarena informatica de performanta

Diferente pentru problema/dungeon intre reviziile #3 si #4

Nu exista diferente intre titluri.

Diferente intre continut:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.