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

!{width: 300px; float: right; margin: 10px}problema/cangrena?main.png!
 

Oraşul TownsVille este un oraş foarte aglomerat. Acesta este format din *N* intersecţii numerotate de la *1* la *N*, conectate prin *M* străzi. Primarul oraşului cunoaşte pentru câteva din cele *N* intersecţii un coeficient pozitiv *A[i]* reprezentând aglomeraţia din intersecţia *i*. Pentru intersecţiile în care acest coeficient este necunoscut, primarul este obligat să fixeze personal acest coeficient (de asemenea pozitiv).
Iniţial, primarului nu prea îi păsa ce coeficienţi selectează. Dacă pentru o intersecţie coeficientul era prea mic, lumea ar fi fost mulţumită, dacă nu, ar fi impus taxe, deci el ar fi fost mulţumit. Din păcate, Gaşca Cangrenă este pusă pe tot felul de mârlănii: de la aruncat hârtie în coşul cu plastic, până la furat îngheţata copiilor mici, orice e posibil. Astăzi, în schimb, aceştia s-au decis să fure cauciucurile maşinilor din interiorul intersecţiilor. Astfel, primarul şi-a impus următoarea regulă: pentru oricare două intersecţii conectate printr-o stradă, diferenţa coeficientului de aglomeraţie între cele două intersecţii trebuie să nu fie prea mare. Dacă această diferenţă ar fi mult prea mare, Gaşca Cangrenă ar ataca cu siguranţă intersecţia mai aglomerată. Altfel, aceştia ar fi confuzi pe care să o atace (întrucât nu ştiu să numere câte maşini sunt într-o intersecţie), fapt care le-ar câştiga timp fetiţelor Powerpuff să vină să salveze situaţia.

2 3
4 2
| 10 15 20 12

| Poza1

| !problema/cangrena?explicatie1.png!

|
| 8 8
-1 33 -1 -1 -1 -1 -1 31

5 7
6 7
| 33 33 32 32 34 34 35 31

| Poza2

| !problema/cangrena?explicatie2.png!

|