== include(page="template/taskheader" task_id="bitconnect") ==
Hei hei hei Eddie Valoare a tot căutat o metodă de îmbogăţire rapidă pentru a-şi cumpăra sticle de Tedi pe care să le bea împreună cu fraţii săi, şi în sfârşit i-a venit o idee garantată succesului: acesta îşi va crea propria criptomonedă(numită $Junior Coin$,sau prescurtat $JC$). Totul a mers bine până când Eddie a trebuit să implementeze crypto currency-ul. Prima provocare a acestuia a fost efectuarea tranzacţiilor.
Eddie Valoare a tot cautat o metoda de imbogatire rapida pentru a-si cumpara sticle de teddy pe care sa le bea impreuna cu fratii sai, si in sfarsit i-a venit o idee garantata succesului: acesta isi va creea propria crypto-moneda.
Totul a mers bine pana cand Eddie a trebuit sa implementeze crypto currency-ul. Prima provocare a acestuia a fost efectuarea tranzactiilor.
Modul de efectuare a tranzactiilor opereaza dupa un model smenar, care poate fi descris in felul urmator:
-fiecare boss are asociat un numar
-intre 2 bossi este o favoare frateasca daca and-ul intre numerele lor este nenul(daca bossi sunt x si y,atunci x & y != 0)
-pentru a efectua o tranzactie de la x la y,se doreste ca aceasta sa foloseasca cat mai putine favoruri fratesti,pentru ca favoriile nu sunt ceva usor de obtinut
Eddie ar dori sa stie care este numarul minim de favoruri prin care trec mai multe tranzactii. Totusi, Eddie nu e multumit: el stie ca moneda lui va avea un succes aproape instant, asadar in final moneda trebuie sa respecte 3 tipuri de operatii:
1.add(x) - bossul x se decide sa se alature familiei. Intre el si bosii vechi se formeaza favoruri fratesti. Se garanteaza ca x nu face parte din familie.
2.erase(x) - bossul x a castigat destula valoare si decide sa nu mai investeasca in moneda. Asadar el trebuie eliminat si toate favorurile pe care le avea trebuie sterse.
3.transaction(x,y) - Eddie vrea sa afle numarul minim de favoruri folosite pentru a fi efectuata o tranzactie de la x la y,se garanteaza ca x si y fac parte din familie.
Deoarece Eddie stie ca ceea ce cere este prea greu,el va da 2 variante de a raspunde la queryuri:
bit mode- trebuie sa spuneti numarul minim de favoruri,aceasta varianta va primi 100% din punctaj/test
connect mode-trebuie sa spuneti doar daca exista un mod de a efectua tranzactia de la x la y.aceasta varianta va primi 25% din punctaj/test
Modul de efectuare a tranzacţiilor operează după un model şmenar, care poate fi descris în felul următor:
* fiecare boss are asociat un număr
* între 2 bossi este o favoare frăţească dacă and-ul între numerele lor este nenul (între $x$ şi $y$ există o favoare frăţească, dacă şi numai dacă $x & y != 0$)
* pentru a efectua o tranzacţie de la $x$ la $y$, se doreşte ca aceasta să folosească cât mai puţine favoruri frăţeşti; pentru că favorurile nu sunt ceva uşor de obţinut Eddie ar dori să ştie care este numărul minim de favoruri prin care trec mai multe tranzacţii. Totuşi, Eddie nu e mulţumit: el ştie că moneda lui va avea un succes aproape instant, aşadar în final moneda trebuie să respecte 3 tipuri de operaţii:
** $add(x)$ - bossul $x$ se decide să se alăture monedei. Între el şi bossii vechi se formează favoruri frăţeşti. Se garantează că $x$ nu face parte din monedă.
** $erase(x)$ - bossul $x$ a câştigat destulă valoare şi decide să nu mai investească în monedă. Aşadar el trebuie eliminat şi toate favorurile pe care le avea trebuie şterse.
** $transaction(x,y)$ - Eddie vrea să afle numărul minim de favoruri folosite pentru a fi efectuată o tranzacţie de la $x$ la $y$ sau $-1$ dacă nu se poate efectua o tranzacţie; se garantează că $x$ şi $y$ fac parte din monedă.
Deoarece Eddie ştie că ceea ce cere este prea greu, el vă dă 2 variante de a răspunde la queryuri:
* $bit-mode$ - trebuie să spuneţi numărul minim de favoruri; această variantă va primi $100%$ din punctaj/test
* $connect-mode$ - trebuie să spuneţi doar dacă există un mod de a efectua tranzacţia de la $x$ la $y$; această variantă va primi $25%$ din punctaj/test
h2. Date de intrare
Pe prima linie Q,care reprezinta numarul de operatii.
Pe fiecare din urmatoarele Q linii va aparea t,care reprezinta tipul operatiei(1=insert,2=erase,3=transaction),x si y(daca t = 3)
În fişierul de intrare $bitconnect.in$ se va găsi pe prima linie un număr natural N, care reprezintă numarul de operaţii.
Pe următoarele $N$ linii vor apărea operaţiile descrise mai sus în următoarea formă:
* $1 x$ - bossul $x$ se alătură reţelei; se garantează că acesta nu era deja în reţea;
* $2 x$ - bossul $x$ iese din reţea; se garantează că acesta era deja în reţea;
* $3 x y$ - se cere răspunsul la întrebarea legată de bossii $x$ şi $y$;
h2. Date de ieşire
Raspunsuriile operatiilor de tip 3 fiecare pe cate o linie separata
În fişierul de ieşire $bitconnect.out$ se va găsi pe prima linie cuvântul $"bit"$ (fără ghilimele) în caz că doriţi să răspundeţi în $bit-mode$, altfel se va găsi cuvântul $"connect"$ (tot fără ghilimele).
Pe următoarele linii vor apărea răspunsurile operaţiilor de tip 3 astfel:
* dacă modul ales a fost $bit-mode$, pe fiecare linie se va găsi numărul minim de favoruri folosite pentru a face o tranzacţie între bossii $x$ şi $y$; în caz că nu se poate efectua o tranzacţie între bossii $x$ şi $y$, se va afişa $-1$;
* dacă modul ales a fost $connect-mode$, pe fiecare linie se va găsi $1$ dacă se poate efectua o tranzacţie directă sau indirectă între bossii $x$ şi $y$, altfel se va afişa $0$;
h2. Restricţii
h2. Restricţii si precizari
* $... ≤ ... ≤ ...$
* $Subtask 1 (testul 1) - 4 puncte: răspunsul va fi 0, 1, sau -1, N ≤ 200$
* $Subtask 2 (testele 2-5) - 16 puncte: N ≤ 500$
* $Subtask 3 (testele 6-13)- 32 puncte: N ≤ 7000$
* $Subtask 4 (testele 14-25)- 48 puncte: N ≤ 106000$
* $La o tranzactie intre x si x se considera ca se folosesc 0 favoruri$
* $Pentru cei neiniţiaţi in arta cryptomonedelor:$
** $"TO THE MOON!" = OK pentru modul bit$
** $"to the moon!-ish" = OK pentru modul connect$
** $"Fisierul de iesire este o teapa" = Format incorect al fişierului de ieşire$
** $"HODL" = Incorect$
* $Valorile numerelor sunt numere naturale mai mici decât 2^62^$
* $Nu întrebaţi ce înseamnă termenii de mai sus de la evaluator, că e posibil să ne supărăm, să luăm punctele şi să nu le mai dăm.$
h2. Exemplu
table(example). |_. bitconnect.in |_. bitconnect.out |
| 25
| 26
1 1
1 2
3 1 2
