Fişierul intrare/ieşire:	bitconnect.in, bitconnect.out	Sursă	Junior Challenge 2018
Autor	Rapeanu George	Adăugată de	Junior Challenge •JuniorChallenge2018
Timp execuţie pe test	0.75 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 împreuna cu fraţii săi, şi în sfârşit i-a venit o idee garantată succesului: acesta îşi va creea 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.

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ăţeasca dacă and-ul între numerele lor este nenul(între x şi y există o favoare frăţeasca, dacă şi numai dacă x & y != 0)
• pentru a efectua o tranzacţie de la x la y,se doreşte ca aceasta sa folosească cât mai puţine favoruri frăţeşti; pentru ca favorurile nu sunt ceva uşor de obţinut Eddie ar dori sa ştie care este numărul minim de favoruri prin care trec mai multe tranzacţii. Totuşi, Eddie nu e mulţumit: el ştie ca moneda lui va avea un succes aproape instant, aşadar în final moneda trebuie sa respecte 3 tipuri de operaţii:
  • add(x) - bossul x se decide sa se alăture monedei. Intre el şi bossii vechi se formează favoruri frăţeşti. Se garantează ca x nu face parte din moneda.
  • erase(x) - bossul x a câştigat destulă valoare şi decide sa nu mai investească în moneda. Aşadar el trebuie eliminat şi toate favorurile pe care le avea trebuie şterse.
  • transaction(x,y) - Eddie vrea sa afle numărul minim de favoruri folosite pentru a fi efectuata o tranzacţie de la x la y sau -1 dacă nu se poate efectua o tranzacţie; se garantează ca x şi y fac parte din monede.

Deoarece Eddie ştie că ceea ce cere este prea greu, el va da 2 variante de a raspunde la queryuri:

• bit-mode - trebuie să spuneţi numărul minim de favoruri; aceasta varianta va primi 100% din punctaj/test
• connect-mode - trebuie să spuneţi doar dacă exista un mod de a efectua tranzacţia de la x la y; această variantă va primi 25% din punctaj/test

Date de intrare

În fişierul de intrare bitconnect.in 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 N numere 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;

Date de ieşire

Î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;

Restricţii si precizari

• Subtask 1 - 4 puncte: răspunsul va fi 0, 1, sau -1, N ≤ 200
• Subtask 2 - 16 puncte: N ≤ 500
• Subtask 3 - 32 puncte: N ≤ 7000
• Subtask 4 - 48 puncte: N ≤ 106000
• Mesajele pe teste sunt:
  • "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⁶²
• 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.

Exemplu

Explicaţie

...

Cum se trimit solutii?