Revizia anterioară Revizia următoare
| 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
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
Date de intrare
Fişierul de intrare bitconnect.in ...
Date de ieşire
În fişierul de ieşire bitconnect.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| bitconnect.in | bitconnect.out |
|---|---|
| 25 1 1 1 2 3 1 2 1 3 1 4 3 1 2 3 1 3 3 1 4 3 2 4 1 5 3 1 4 3 2 4 3 3 4 1 7 3 1 4 3 1 5 3 2 7 2 3 2 5 3 1 4 3 2 7 1 5 3 1 7 3 5 2 3 7 4 | bit -1 2 1 -1 -1 2 3 2 2 1 1 2 1 1 2 1 |
Explicaţie
...
