==Include(page="template/taskheader" task_id="atac")==

In tara Arboreea lucrurile au iesit de sub control. OTPB (Organizatia Terorista Petrica Bomba) a hotarat sa atace doua orase din aceasta tara deoarece liderul organizatiei, Petrica, a pierdut alegerile prezidentiale din anul 2004. Tara are $N$ orase, numerotate de la $1$ la $N$, iar reteaua oraselor si strazile dintre aceastea formeaza un arbore (graf neorientat conex ce nu contine cicluri). OTPB stie pentru fiecare strada cate bombe trebuie sa utilizeze pentru a o scoate din uz. Acum se pune problema determinarii numarului cel mai mic de bombe pe care trebuie sa-l utilizeze OTPB pentru ca intre cele doua orase alese (considerate de importanta majora in Arboreea) sa nu mai existe drum intre ele dupa bombardament. Cum importanta oraselor se schimba pe parcusul evolutiei tarii, OTPB vrea sa stie numarul minim de bombe pentru atacul asupra mai multor perechi de orase, mai exact $M$. Totusi se doreste comunicarea usoara a acestor $M$ perechi intre organizatiile teroriste din tara. Astfel, nu se poate transmite intreaga lista a celor $M$ perechi de orase asupra carora se doreste efectuarea unui atac deoarece reteaua de legatura dintre organizatii este cam inceata la capitolul trasmiterea datelor. Totusi s-a gasit o solutie: stiind prima pereche de orase $X$ si $Y$ asupra carora se va efectua un atac si numarul minim de bombe $Z$ ce trebuie utilizate in cazul atacului in orasele $X$ si $Y$, urmatoarea pereche de orase, a doua, se determina utilizand relatiile:

In tara Arboreea lucrurile au iesit de sub control. OTPB (Organizatia Terorista Petrica Bomba) a hotarat sa atace doua orase din aceasta tara deoarece liderul organizatiei, Petrica, a pierdut alegerile prezidentiale din anul 2004. Tara are $N$ orase, numerotate de la $1$ la $N$, iar reteaua oraselor si strazile dintre aceastea formeaza un arbore (graf neorientat conex ce nu contine cicluri). OTPB stie pentru fiecare strada cate bombe trebuie sa utilizeze pentru a o scoate din uz. Acum se pune problema determinarii numarului cel mai mic de bombe pe care trebuie sa-l utilizeze OTPB pentru ca intre cele doua orase alese (considerate de importanta majora in Arboreea) sa nu mai existe drum dupa bombardament. Cum importanta oraselor se schimba pe parcusul evolutiei tarii, OTPB vrea sa stie numarul minim de bombe pentru atacul asupra mai multor perechi de orase, mai exact $M$. Totusi se doreste comunicarea usoara a acestor $M$ perechi intre organizatiile teroriste din tara. Astfel, nu se poate transmite intreaga lista a celor $M$ perechi de orase asupra carora se doreste efectuarea unui atac deoarece reteaua de legatura dintre organizatii este cam inceata la capitolul trasmiterea datelor. Totusi s-a gasit o solutie: stiind prima pereche de orase $X$ si $Y$ asupra carora se va efectua un atac si numarul minim de bombe $Z$ ce trebuie utilizate in cazul atacului in orasele $X$ si $Y$, urmatoarea pereche de orase, a doua, se determina utilizand relatiile:

$X' = (X*A + Y*B) mod N + 1$
$Y' = (Y*C + Z*D) mod N + 1$

| 1
1 |

==Include(page="template/taskfooter" task_id="atac")==
 
 

==Include(page="template/taskfooter" task_id="atac")==