Diferente pentru problema/santa intre reviziile #2 si #10

Diferente intre titluri:

santa
Santa

Diferente intre continut:

== include(page="template/taskheader" task_id="santa") ==
==Include(page="template/taskheader" task_id="santa")==
Poveste ...
HO HO HO... Max Damage a ajuns in Laponia, mai precis la fabrica de tractorase a lui Mos Craciun. Acum, toata lumea stie ca Mos Craciun are o lista cu copiii care au fost cuminti si ca le aduce in noaptea de ajun cate o jucarie, dar... sa zicem ca Max Damage nu mai e copil. El stie ca jucariile sunt gata si ca spiridusii vor trebui sa le duca de la atelierul lor (aflat in intersectia notata cu {$S$}) la casuta Mosului (aflata in intersectia notata cu {$E$}). Max Damage are o harta a orasului. Pe ea apar $N$ intersectii, numerotate de la $1$ la $N$ , unite de $M$ strazi. Acum Max Damage isi face urmatorul plan si are nevoie de ajutorul nostru. Stie ca maine spiridusii vor transporta jucariile de la atelier la casuta lui Mos Craciun. Problema este ca nu stie exact pe ce drum vor merge spiridusii, insa este cert ca ei nu vor trece de doua ori printr-o intersectie. Tot ce mai ramane de facut este ca Max sa sara in masina si sa verifice toate intersectiile in care s-ar putea gasi transportul de jucarii. Fiind si econom el nu trebuie sa treaca printr-o intersectie de doua ori sau prin intersectiile in care se stie sigur ca transportul de jucarii nu poate ajunge (sa fim seriosi, benzina costa destul de mult). Astfel el va pleca din "sediul" sau (intersectia notata cu {$Q$}) trecand prin toate si numai prin intersectiile unde transportul de jucarii ar putea ajunge. Turul de verificare facut de Max poate sa se sfarseasca in orice intersectie.
h2. Cerinta
...
Daca este posibila realizarea unui astfel de drum Max Damage va cere unul dintre ele.
h2. Restrictii
h2. Date de Intrare
...
Prima linie a fisierului de intrare $santa.in$ contine doua numere intregi $N$ , $M$ reprezentand numarul de intersectii, respectiv de strazi. Urmatoarele M linii contin cate doua numere $X{~i~}$ , $Y{~i~}$ reprezentand faptul ca exista o strada, care poate fi parcursa in ambele directii, intre intersectiile $X{~i~}$ si {$Y{~i~}$}. Pe ultima linie se afla trei numere $S$ , $E$ , $Q$ cu semnificatia de mai sus.
h2. Date de intrare
h2. Date de Iesire
...
In fisierul $santa.out$ veti afisa {@No [email protected]} daca Max nu isi poate realiza planul pentru fisierul de intrare corespunzator, sau numarul $X$ de intersectii (aflat pe prima linie) ce trebuie vizitate pentru a-si realiza planul, iar pe linia urmatoare numerele $A{~1~} A{~2~} ... A{~x~}$ separate prin spatii reprezentand intersectiile, in ordinea in care Max Damage treace pentru verificare.
h2. Date de iesire
h2. Restrictii si precizari
...
* $1 ≤ N ≤ 45.000$
* $1 ≤ M ≤ 130.000$
* oricum am alege un set de $16$ sau mai multe intersectii exista doua intersectii in set $A$ si $B$ astfel incat este imposibil sa gasim un drum care pleaca din $A$ , trece prin $B$ si revine in $A$ trecand printr-o intersectie cel mult odata(drumul poate sa treaca prin orice intersectie nu neaparat prin cele din setul ales).
h2. Exemplu
| santa.in | santa.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. santa.in |_. santa.out |
| 5 5
1 2
1 4
2 3
3 4
4 5
1 4 2
| 4
2 1 4 3 |
 
 
==Include(page="template/taskfooter" task_id="santa")==
 
 
== include(page="template/taskfooter" task_id="santa") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
713