4115. Sortowanie przez scalanie
Problem code: PMERG
Proszę rozwiązać problem sortowania algorytmem sortowania przez scalanie. W pierwszej kolejności proszę utworzyć pary składające się z elementu z pierwszej i drugiej połowy. Dalej czwórki scalone z pary z pierwszej i drugiej połowy i tak dalej, aż do jednej pary.
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ę wypisać w nawiasach wartości po kolejnych scaleniach. Czyli najpierw pary, potem czwórki itd... na końcu posortowany ciąg.
Example
Input:
4
13 67/70 10/3 30/13 40/61 -93/97 80/77 7/73 91/1 80/81 -5/3 49/60 61/90 -13/16
7 76/43 1/1 73/94 -45/38 35/37 12/5 79/20
10 13/47 23/2 65/57 1/4 71/48 31/43 13/35 79/56 -83/89 -49/46
7 -94/57 43/20 11/51 71/11 -5/6 -15/14 15/73
Output:
(7/73 67/70) (10/3 91/1) (80/81 30/13) (-5/3 40/61) (-93/97 49/60) (61/90 80/77) (-13/16) (-5/3 7/73 40/61 67/70) (-93/97 49/60 10/3 91/1) (61/90 80/81 80/77 30/13) (-13/16) (-5/3 7/73 40/61 61/90 67/70 80/81 80/77 30/13) (-93/97 -13/16 49/60 10/3 91/1) (-5/3 -93/97 -13/16 7/73 40/61 61/90 49/60 67/70 80/81 80/77 30/13 10/3 91/1) (-45/38 76/43) (35/37 1/1) (73/94 12/5) (79/20)
(-45/38 73/94 76/43 12/5) (35/37 1/1 79/20)
(-45/38 73/94 35/37 1/1 76/43 12/5 79/20)
(13/47 31/43) (13/35 23/2) (65/57 79/56) (-83/89 1/4) (-49/46 71/48) (13/47 31/43 65/57 79/56) (-83/89 1/4 13/35 23/2) (-49/46 71/48) (-83/89 1/4 13/47 13/35 31/43 65/57 79/56 23/2) (-49/46 71/48) (-49/46 -83/89 1/4 13/47 13/35 31/43 65/57 79/56 71/48 23/2) (-94/57 71/11) (-5/6 43/20) (-15/14 11/51) (15/73)
(-94/57 -15/14 11/51 71/11) (-5/6 15/73 43/20)
(-94/57 -15/14 -5/6 15/73 11/51 43/20 71/11)
1
Obszarski Paweł
Date:
2009-03-25
Time limit: 1s
Source limit:50000B
Languages: C C99 strict
2