Diferente pentru problema/ciob intre reviziile #15 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
* 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}$, sau invers( prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$)
* 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
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 de maxim de trasee posibile$
* $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