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
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 familiei monedei. Intre el şi bossii vechi se formează favoruri frăţeşti. Se garantează ca x nu face parte din familie.
- 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 familie.
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
Pe prima linie Q, care reprezintă numărul de operaţii.
Pe fiecare din următoarele Q linii va apărea t,care reprezinta tipul operaţiei( 1=insert,2=erase,3=transaction ), x şi y(dacă t = 3)
Date de ieşire
Pe prima linie va apărea modul în care vreţi sa răspundeţi( bit/connect ).
Pe următoarele linii vor apărea răspunsurile operaţiilor de tip 3 fiecare pe câte o linie separata
Restricţii si precizari
- Subtask 1 - 4 puncte: raspunsul va fi 0, 1, sau -1
- Subtask 2 - 12 puncte: N ≤ 2500
- Subtask 3 - 16 puncte: N ≤ 5000
- Subtask 4 - 20 puncte: N ≤ 60000
- Subtask 5 - 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 la fisierul de iesire
- "HODL" = Incorect
- Valorile numerelor sunt numere naturale mai mici decat 262
Exemplu
| bitconnect.in | bitconnect.out |
|---|---|
| 26 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 3 7 7 | bit -1 2 1 -1 -1 2 3 2 2 1 1 2 1 1 2 1 0 |
Explicaţie
...
