== include(page="template/taskheader" task_id="enemies") ==
Poveste şi cerinţă...
**Atenctie! Aceasta problema este interactiva .**
h2. Date de intrare
Una dintre cele mai neîntelese relaţii dintre oameni este cea de duşmănie. La prima vedere pare a nu fi nicio regulă sau structură legată de aceste relatii, doar legende si povesti. De exemplu, faimoasa expresie “Duşmanul duşmanului meu este prietenul meu“ pare a fi doar o legendă si nimic mai mult.
Fişierul de intrare $enemies.in$ ...
O echipă de cercetători din Dorohoi crede că a reusit să inventeze un dispozitiv cu ajutorul căruia să poată studia aceste relatii de dusmanie. Ei au la dispozitie N -cobai- voluntari numerotati de la 0 la N − 1. Acestia au M relatii de dusmanie x[~i~] - Y[~i~] (x[~i~] ≠ Y[~i~] , 0 ≤ i ≤ M-1) cu semnificatia ca pesoana X[~i~] (0 ≤ X[~i~] ≤ N-1) se afla intr-o relatie de dusmanie cu perosna Y[~i~] (0 ≤ Y[~i~] ≤ N-1).
h2. Date de ieşire
Dispozitivul este format dintr-o camera in car pot intra o parte din acesti N oameni. Apoi aceasta poate fi activat si dupa numeroase calcule, extrapolari si integrari va afisa pe un ecran numarul de relatii de dusmanie intre oamenii din camera si cei aflati in exterior.
În fişierul de ieşire $enemies.out$ ...
Cercetatorii trebuie sa deducă toate relatiile de duşmănie fară sa utilizeze dispozitivul de prea multe ori altfel riscă ca unul din voluntari să iî considere duşmani si din aceasta cauză să nu mai poata sa deducă ralatiile. Voi trebuie să le spuneţi cum să utilizeze dispozitivul de fiecare data şi la final să deduceti relatiile de duşmanie ale celor N voluntari.
h2. Restricţii
* $... ≤ ... ≤ ...$
h2. Interactiune
Puteti apela urmatoarea functie in scopul gasirii acestor relatii:
int split_people(std::string split);
**Atentie! Aceasta functie nu trebuie implementata de catre voi.** Graderul va implementa aceasta functie. Argumentul split trebuie sa fie format din exact N caractere care sunt fie '0', fie '1'. Functia va intoarce cate relatii de dusmanie sunt intre oamenii din camera si cei din exteriorul acesteia oamenii fiind repartizati in functie de caracterul corespunzator. Daca split[~i~]='0' atunci al i-lea om va ramane in afara camerei, iar daca este '1' al i-lea om va intra in camera.
Puteti apela aceasta functie de maxim 20 000 ori, iar scorul vostru va fi calculat in functie de acest numar (vezi sectiunea **Punctare**)
h2. Punctare
|_. Subtask |_. Punctaj |_. Constrangeti |
| 1 | 16 puncte | 1 ≤ N ≤ 100
0 ≤ M ≤ 800|
| 2 | 8 puncte | 3 ≤ N ≤ 100
Cei N oameni pot fi partitionati in 2 multimi A si B astfel incat orice om
din multimea A este in relatie de dusmanie cu orice om din multimea B|
| 3 | 40 de puncte | 1 ≤ N ≤ 800
Graful obtinut din relatiile de dusmanie reprezinta un lant |
| 4 | 20 de punte | 1 ≤ N ≤ 800
Graful obtinut din relatiile de dusmanie reprezinta un arbore. |
| 5 | 16 puncte | 1 ≤ N ≤ 800
0 ≤ M ≤ 800 |
h2. Exemplu
table(example). |_. enemies.in |_. enemies.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
Sa presupunem ca N=4, M=3 si relatiile de dusmanie sunt 0-1, 0-2 si 1-3. O succesiune de apeluri ale functiei split_people care determina aceste relatii este urmatoarea :
table(example). |_. Apel |_. Valoare intoarsa |
| split_people(@[0]@) | 2 |
| split_people(@[0,1]@) | 2 |
| split_people(@[0,2]@) | 1 |
| split_people(@[0,3]@) | 3 |
| split_people(@[0,1,2]@) | 1 |
| split_people(@[0,1,3]@) | 1 |
| split_people(@[0,2,3]@) | 2 |
h3. Explicaţie
...
Pentru primul apel al functiei split_people 0 are exact 2 relatii de dusmanie, deci functia va intoarce 2.
Pentru cel de-al 4-lea apel al functiei split_people toate cele 3 relatii de dusmanie sunt intre un om din camera si unul din afara acesteia.
Pentru cel de-al 6-lea apel al functiei split_people numai relaţia de duşmanie 0 - 2 va fi contorizata de dispozitiv.
In final, funcţia find_enemies trebuie sa intoarca [(3,1),(0,2),(0,1)].
== include(page="template/taskfooter" task_id="enemies") ==
