SPOJ Problem Set (main) 4119. Sortowanie przez kopcowanie Problem code: PHEAP
Proszę napisać program, który przy wykorzystaniu algorytmu sortowania przez kopcowanie, posortuje podane liczy wymierne w kolejności od najmniejszej do największej.
Wejście
W pierwszej linii wejścia znajduje się liczba testów t. Dalej kolejno w każdej z t linii umieszczono jeden test. Pierwsza liczba testu k określa liczbę liczb wymiernych do posortowania, dalej pojawiają się liczby oddzielone spacjami w postaci uproszczonych ułamków niewłaściwych a/b, gdzie a jest liczbą całkowitą a b liczbą naturalną. -100<=a<=100. Liczba b nie przekracza zakresu zmiennej typu int.
Wyjście
Dla każdego z t testów proszę wykonać następujące operacje. Proszę najpierw w liniowym czasie stworzyć kopiec i wypisać jego zawartość. Proszę kolejno zdejmować najmniejsze wartości z kopca i w osobnej linii wyświetlić zmodyfikowany kopiec. Na końcu w oddzielnej linii proszę wyświetlić posortowane wartości.
Example
Input:
4
7 1/1 69/8 51/77 56/1 70/89 -7/92 17/6
6 70/83 -11/26 -34/41 -97/75 -31/36 86/31
5 5/6 19/22 83/40 77/53 38/37
7 73/53 -36/5 -37/33 7/10 -74/77 4/3 92/93
Output:
-7/92 70/89 51/77 56/1 69/8 1/1 17/6
51/77 70/89 1/1 56/1 69/8 17/6
70/89 17/6 1/1 56/1 69/8
1/1 17/6 69/8 56/1
17/6 56/1 69/8
69/8 56/1
56/1
-7/92 51/77 70/89 1/1 17/6 69/8 56/1
-97/75 -31/36 -34/41 -11/26 70/83 86/31
-31/36 -11/26 -34/41 86/31 70/83
-34/41 -11/26 70/83 86/31
-11/26 86/31 70/83
70/83 86/31
86/31
-97/75 -31/36 -34/41 -11/26 70/83 86/31
5/6 19/22 83/40 77/53 38/37
19/22 38/37 83/40 77/53
1
77/53 83/40
83/40
5/6 19/22 38/37 77/53 83/40
-36/5 -74/77 -37/33 7/10 73/53 4/3 92/93
-37/33 -74/77 92/93 7/10 73/53 4/3
-74/77 7/10 92/93 4/3 73/53
7/10 4/3 92/93 73/53
92/93 4/3 73/53
4/3 73/53
73/53
-36/5 -37/33 -74/77 7/10 92/93 4/3 73/53
Added by:
Obszarski Paweł
Date:
2009-03-25
Time limit: 1s
Source limit:50000B
Languages: C C99 strict
2