Diferente pentru problema/ciob intre reviziile #8 si #22

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="ciob") ==
Undeva departe exista o tara a carei retea stradala are structura unui graf conex aciclic, orasele fiind reprezentate de noduri, iar strazile de muchii. Ministrul responsabil cu salubritatea din fiecare oras tocmai a aflat ca Ciob cel mic si rau va veni in inspectie. El va ateriza cu elicopterul intr-un oras si va parcurge un drum simplu (un drum pe parcursul caruia nu va vizita acelasi oras de mai multe ori). Ministrul nostru a reusit sa afle traseele posibile. Pentru un traseu se cunosc orasul in care aterizeaza Ciob si $2$ liste de orase. Prima lista contine orase din care Ciob ar trebui sa poata decola spre casa, iar a doua lista contine orase din care Ciob nu ar trebui sa poate decola. Fiecare oras din tara are un grad de curatenie, iar gradul de multumire al lui Ciob la un moment dat este suma gradelor de curatenie a oraselor prin care a trecut. Orasele din cele $2$ liste au asociat un grad de libertate (daca un oras face parte din $2$ trasee distincte atunci el poate avea, in cele $2$ situatii, grade de libertate diferite). Se considera ca Ciob poate decola dintr-un oras daca gradul sau de multumire in momentul in care il tranziteaza este mai mare sau egal cu gradul de libertate al orasului. De asemenea, marele sef nu poate decola daca gradul sau de multumire este strict mai mic decat gradul de libertate al orasului, in momentul in care il viziteaza.
Undeva, departe, exista o tara a carei retea stradala are structura unui graf conex aciclic, orasele fiind reprezentate de noduri, iar strazile de muchii. Ministrul responsabil cu salubritatea din fiecare oras tocmai a aflat ca Ciob cel Mic si Rau va veni in inspectie. El va ateriza cu elicopterul intr-un oras si va parcurge un drum simplu (un drum pe parcursul caruia nu va vizita acelasi oras de mai multe ori). Ministrul nostru a reusit sa afle traseele posibile. Pentru un traseu se cunosc urmatoarele: orasul in care aterizeaza Ciob si $2$ liste de orase. Prima lista contine orasele din care Ciob ar trebui sa poata decola spre casa, iar a doua lista contine orasele din care Ciob nu ar trebui sa poata decola. Fiecare oras din tara are un grad de curatenie, iar gradul de multumire al lui Ciob la un moment dat este suma gradelor de curatenie a oraselor prin care a trecut. Orasele din cele $2$ liste au asociat un grad de libertate (daca un oras face parte din $2$ trasee distincte atunci el poate avea, in cele $2$ situatii, grade de libertate diferite). Se considera ca Ciob poate decola dintr-un oras daca gradul sau de multumire in momentul in care il tranziteaza este mai mare sau egal cu gradul de libertate al orasului. De asemenea, marele sef nu poate decola daca gradul sau de multumire in momentul in care il viziteaza este strict mai mic decat gradul de libertate al orasului,.
Ministrul va cere sa ii spuneti ce grad de curatenie ar trebui sa aiba fiecare oras pentru a fi respectate toate restrictiile. Gradele de curatenie pot fi si negative (Ministrul manuieste exceptional ranga si tomberonul). Pentru a va ajuta el va mai dezvaluie $2$ proprietati ale traseelor posibile:
Ministrul va cere sa ii spuneti ce grad de curatenie ar trebui sa aiba fiecare oras pentru a fi respectate toate restrictiile. Gradele de curatenie pot fi si negative( ministrul manuieste exceptional ranga si tomberonul). Pentru a va ajuta el va mai dezvaluie $2$ proprietati ale traseelor posibile:
* daca $2$ trasee se intersecteaza, atunci unul este inclus in celalalt
* prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$. Pentru oricare $2$ trasee posibile disjuncte cele mai apropiate $2$ orase, din punct de vedere al numarului strazilor parcurse de la unul la celalalt, sunt unul dintre capetele primului traseu si unul dintre capetele celui de-al doilea traseu: daca $[a, b]$ si $[c, d]$ sunt traseele atunci perechea celor mai apropiate $2$ noduri o notam cu $(x, y)$, cu $x$ apartinand $[a, b]$ si $y$ apartinand $[c, d]$ atunci $(x, y)$ apartine ${ (a,c), (a,d), (b,c), (b,d)}$.
* daca $x$ si $y$ sunt cele mai apropiate $2$ puncte ale traseelor $[a, b]$ si $[c, d]$, atunci $x$ apartine multimii ${a, b}$ si $y$ apartine multimii ${c, d}$( prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$)
h2. Date de intrare
Pe prima linie a fisierului $ciob.in$ se afla numarul $N$, nr de orase. Pe urmatoarele $N - 1$ linii se afla 2 numere, $x y$, cu semnificatia ca exista o sosea intre orasele $x$ si $y$. Pe linia $N + 1$ se alfa numarul M, numarul de trasee. Pe fiecare dintre urmatoarele $3  * M$ linii sunt descrise traseele posibile. Pe linia $N + 3 * i - 1$ se afla nodul de plecare. Pe linia $N + 3 * i$ se afla lista oraselor de pe traseul $i$ din care Ciob poate pleca. Pe linia $N + 3 * i + 2$ se afla lista oraselor de pe traseul $i$ din care Ciob nu poate pleca. Randurile care descriu o lista contin un numar $k$, numarul de orase din acea lista, urmat de k perechi de numere $o g$, $o$ = orasul, iar $g$ = gradul sau de libertate. Orasele speciale sunt date in ordinea parcurgerii.
Pe prima linie a fisierului $ciob.in$ se afla numarul $N$, nr de orase. Pe urmatoarele $N - 1$ linii se afla 2 numere, $x y$, cu semnificatia ca exista o sosea intre orasele $x$ si $y$. Pe linia $N + 1$ se alfa numarul M, numarul de trasee. Pe fiecare dintre urmatoarele $3 * M$ linii sunt descrise traseele posibile. Pe linia $N + 3 * i - 1$ se afla nodul de plecare. Pe linia $N + 3 * i$ se afla lista oraselor de pe traseul $i$ din care Ciob poate pleca. Pe linia $N + 3 * i + 1$ se afla lista oraselor de pe traseul $i$ din care Ciob nu poate pleca. Randurile care descriu o lista contin un numar $k$, numarul de orase din acea lista, urmat de k perechi de numere $o g$, $o$ = orasul, iar $g$ = gradul sau de libertate.
h2. Date de ieşire
În fişierul de ieşire $ciob.out$ se vor afisa $N$ numere reprezentand gradele de curatenie ale oraselor, al i-lea numar fiind gradul de cuiratenie al orasului $i$. Daca exista mai multe solutii se poate afisa oricare atat timp cat numerele sunt in intervalul $[- 2 * 10^9^, 2 * 10^9^]$.
În fişierul de ieşire $ciob.out$ se vor afisa $N$ numere reprezentand gradele de curatenie ale oraselor, al i-lea numar fiind gradul de curatenie al orasului $i$. Daca exista mai multe solutii se poate afisa oricare atat timp cat numerele sunt in intervalul $[- 2 * 10^9^, 2 * 10^9^]$.
h2. Restricţii
* $1 ≤ N ≤ 10000$
* $0 ≤ M ≤ numarul maxim de trasee posibile$
* Nu este neaparat ca Ciob sa poata pleca din orasul in care aterizeaza.
* Se garanteaza ca exista solutie pentru datele de test.
* Se garanteaza ca nu vor exista 2 drumuri identice( ca noduri) in fisierul de intrare.
* Ciob decoleaza dintr-un oras dupa ce il tranziteaza.
h2. Exemplu

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
5934