atac

Atac

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

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

Poveste ...

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:

h2. Cerinta

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

...

A treia pereche de orase se determina utilizand in formula perechea a doua si numarul minim de bombe ce trebuie utilizate pentru a o ataca, a patra din a treia si asa mai departe. Asadar este suficienta cunoasterea primei perechi de orase si a numerelor $A, B, C, D$ pentru a determina toate cele $M$ perechi. De asemenea, din aceeasi cauza - transmiterea greoaie a datelor - OTPB vrea sa afle rezultatele doar pentru ultimele $P$ perechi de orase, considerate suficiente pentru a verifica corectitudinea programului dumneavoastra. Scrieti un program pentru organizatia lui Petrica care calculeaza numarul minim de bombe pentru atacul ultimelor $P$ perechi de orase din cele $M$ daca vreti sa mai ramaneti in viata !

h2. Restrictii

h2. Date de Intrare

...

Pe prima linie a fisierului $atac.in$ se afla trei numere reprezentand numarul de orase, numarul de perechi de orase pentru care organizatia vrea sa afle numarul minim de bombe in cazul unui atac asupra lor si numarul $P$ de perechi pentru care programul vostru trebuie sa afiseze raspunsul. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $U$, $V$ cu semnificatia: exista o strada de la orasul $U$ la orasul $i$ ({$i$} este indicele liniei care va lua valori de la $2$ la $N$) pentru care OTPB trebuie sa utilizeze $V$ bombe pentru a o scoate din uz. Pe urmatoarea linie se afla $6$ numere $X, Y, A, B, C, D$ cu semnificatia din enunt.

h2. Date de intrare

h2. Date de Iesire

...

Fisierul atac.out va avea $P$ linii reprezentand numarul minim de bombe ce trebuie utilizat pentru a ataca ultimele $P$ perechi de orase.

h2. Date de iesire

h2. Restrictii si precizari

...

* $1 ≤ N ≤ 32.000$
* $0 < P < M &le; 500.000$
* $P &le; 10.000$
* $0 &le; A, B, C, D &le; 10.000$
* numarul de bombe pentru a scoate din uz o strada este un numar natural mai mic decat $100.000$
* OTPB nu va scoate din uz nici o strada; se doreste sondarea terenului si nimic mai mult, momentan; deci pentru fiecare pereche de orase din cele $M$ se considera ca reteaua de strazi este intacta (nici o strada nu este bombardata).
* Se vor acorda puncte pe un test doar daca toate cele $P$ numere din fisierul de iesire sunt corect aflate.
* Este clar ca pentru a afla corect cele $P$ numere trebuie sa calculati numarul minim de bombe pentru toate cele $M$ perechi de orase.
* Nu va bazati pe faptul ca perechile de orase se vor repeta iar setul de perechi distincte este mic! OTPB vrea sa studieze cat mai multe perechi de orase asa ca numerele $A, B, C, D$ vor fi inteligent alese pentru a genera cat mai multe perechi distincte intre cele $M$.
* Daca $X$ coincide cu $Y$ atunci raspunsul este $0$
* Pentru $40%$ din teste $N$ va fi mai mic sau egal $1000$

h2. Exemplu

| atac.in | atac.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. atac.in |_. atac.out |
| 7 3 2
1 1
2 2
2 2
1 3
5 3
5 2
6 7 1 1 1 1
| 1
1 |
 
==Include(page="template/taskfooter" task_id="atac")==
 

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

98