Fişierul intrare/ieşire:mergeheap.in, mergeheap.outSursăarhiva educationala
AutorFilipescu Radu, Mititelu TeodorAdăugată deRadu_FilipescuFilipescu Radu Radu_Filipescu
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Heapuri cu reuniune

Fie N mulţimi de elemente. Asupra acestor mulţimi se vor efectua 3 tipuri de operaţii.

  • operaţia de tipul 1: în mulţimea m se inserează elementul x.
  • operaţia de tipul 2: se afişează elementul maxim din mulţimea m, apoi se elimină din aceasta.
  • operaţia de tipul 3: se reunesc mulţimile a şi b ( mulţimea a preia elementele mulţimii b, care rămâne vidă )

Date de intrare

Fişierul de intrare mergeheap.in va conţine pe prima linie valorile lui N şi Q, care reprezintă numărul de mulţimi pe care se vor face operaţiile, respectiv numărul de operaţii. Pe următoarele Q linii se va afla un număr care reprezintă tipul operaţiei, urmat apoi de o valoare, dacă tipul operaţiei este 2, respectiv de două valori pentru operaţiile 1 şi 3.

Date de ieşire

Fişierul de ieşire mergeheap.out va contine, pe câte o linie, răspunsul pentru fiecare operaţie de tipul 2 din fişierul de intrare, în ordinea data.

Restricţii

  • 1 ≤ N ≤ 100
  • 1 ≤ Q ≤ 300000
  • Elementele mulţimilor sunt numere naturale, mai mici decât 2 000 000 000.
  • Se garantează că nu se va cere operaţia 2 pentru o mulţime vidă.

Exemplu

mergeheap.inmergeheap.out
5 10
1 2 5
1 1 3
1 3 7
1 3 4
1 2 2
2 2
3 2 1
2 2
3 3 2
2 3
5
3
7

Explicaţie

Primele 5 operaţii introduc elemente în mulţimi. La a 6-a operaţie trebuie afişat maximul din a doua mulţime, cea care conţine elementele 2 şi 5. Deci vom afişa 5 şi îl vom elimina din mulţimea sa. Apoi trebuie reunite a doua mulţime cu prima, a doua conţinând, dupa reuniune, elementele 2 şi 3. Apoi ni se cere să afişăm elementul maxim din această mulţime. Penultima operaţie este de reuniune dintre mulţimile 3 şi 2, urmată apoi de afişarea şi eliminarea maximului din aceasta.

Indicaţii de rezolvare

O soluţie simplă constă în folosirea unor heapuri binare, care sunt uşor de implementat şi vor efectua operaţiile de adăugare şi de eliminare în complexitate logaritmică. Problema acestora este operaţia de reuniune, care se efectuează în O(N*log 2 N), dacă introducem element cu element o mulţime în cealaltă, sau în O(N), folosind heapify pentru construirea unui heap, această soluţie va obţine aproximativ 30 de puncte.

Pentru a efectua mai rapid operaţia de reuniune, se pot folosi structuri de date precum Binomial Heap sau Pairing Heap, care efectuează operaţiile de tipul 3 în O(log 2 N), respectiv în O(1) amortizat. O sursă care implementează Binomial Heap puteţi vedea aici, aceasta va obţine în jur de 70 de puncte, şi una cu Pairing Heap aici., care va obţine punctajul integral.

Complexităţile operaţiilor pentru aceste structuri de date, precum şi câteva alternative ale acestora.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?