Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | enemies.in, enemies.out | Sursă | Lot Seniori Dorohoi 2019 - Baraj 1 |
| Autor | Andrei Constantinescu, Costin Oncescu | Adăugată de |  brebenel mihnea stefan •tryharderul |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Enemies
Atenctie ! Aceasta problema este interactiva .
Una dintre cele mai neîntelese relatii dintre oameni este cea de dusmănie. La prima vedere pare a nu fi nicio regulă sau structură legată de aceste relatii, doar legende si povesti. De exemplu, faimoasa expresie “Dusmanul dusmanului meu este prietenul meu“ pare a fi doar o legendă si nimic mai mult.
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 xi - Yi (xi ≠ Yi , 0 ≤ i ≤ M-1) cu semnificatia ca pesoana Xi (0 ≤ Xi ≤ N-1) se afla intr-o relatie de dusmanie cu perosna Yi (0 ≤ Yi ≤ N-1).
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.
Cercetatorii trebuie sa deduca toate relatiile de dusmanie fara sa utilezeze dispozitivul de prea multe ori altfel risca ca unul din voluntari sa ii considere dusmani si din aceasta cauza sa nu mai poata sa deduca ralatiile. Voi trebuie sa le spuneti cum sa utilizeze dispozitivul de fiecare data si la final sa deduceti relatiile de dusmanie ale celor N voluntari.
Date de intrare
Fişierul de intrare enemies.in ...
Date de ieşire
În fişierul de ieşire enemies.out ...
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 spliti='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)
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 |
Exemplu
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 :
| 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 |
Explicaţie
...
