Fişierul intrare/ieşire:bitconnect.in, bitconnect.outSursăJunior Challenge 2018
AutorRapeanu GeorgeAdăugată deJuniorChallenge2018Junior Challenge JuniorChallenge2018
Timp execuţie pe test1.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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 î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.

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

Date de intrare

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

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 (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 262
  • 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

bitconnect.inbitconnect.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

După primele 2 operaţii de insert reţeaua va arăta ca în prima imagine. Între 1 si 2 nu este o legătură frăţească, deci răspunsul este -1.
După încă 2 operaţii de insert reţeaua va arăta ca în a doua imagine.
După încă o operaţie de insert reţeaua va arăta ca în a treia imagine.
După încă o operaţie de insert reţeaua va arăta ca în a patra imagine.
După 2 operaţii de erase reţeaua va arăta ca în a cincea imagine.
După o operaţie de insert reţeaua va arăta ca în a şasea imagine.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?