Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PA05_BIB - Biblioteka

Podczas wakacji Bajtazar stał się miłośnikiem dobrej literatury. Czytał bardzo dużo książek, które wypożyczał z biblioteki. Pewnego dnia odwiedził go kolega Wyjątek i zainteresował się jedną z wypożyczonych książek. Po długich namowach Bajtazar, niepomny swoich poprzednich problemów z Wyjątkiem, zgodził się wreszcie mu ją pożyczyć.

Wakacje szybko minęły. Rozpoczął się nowy rok szkolny (choć i tak w Bajtocji rozpoczyna się wyjątkowo późno - 10 Terabajta) i nadszedł czas zwrotu książek do biblioteki. Bajtazar przypomniał sobie, że jedną z nich pożyczył Wyjątkowi. Kiedy poprosił go o jej zwrot, ten przyznał się, że podczas pobytu w Kurorcie zgubił ją bawiąc się na Lollobrygidzie. Bardzo to zmartwiło biednego Bajtazara, bo wiedział, że będzie miał w związku z tym wiele nieprzyjemności.

Kiedy opowiedział o wszystkim paniom w Bibliotece, te zdecydowały, że za swoje lekkomyślne zachowanie będzie musiał ponieść karę i kazały mu przyjść w 0110 (odpowiednik naszej soboty), aby pomóc im w sortowaniu kart bibliotecznych. Jako, że kilku kolegów Bajtazara już odbyło taką karę, to karty znajdują się w wielu posortowanych plikach o różnych rozmiarach, a zadaniem Bajtazara jest połączyć je w jeden plik.

Ponieważ Bajtazar wcześniej zaplanował już sobie ten dzień, a jednocześnie nie chce znów zawieść pań bibliotekarek, musisz mu pomóc napisać program, który pozwoli mu ustalić, jak wiele czasu zajmie sortowanie kart oraz wyznaczyć stosowną kolejność łączenia plików, tak aby mógł to zrobić jak najszybciej.

Bajtazar może naraz scalić tylko dwa pliki kart. Dla uproszczenia przyjmujemy, że czas scalania dwóch plików jest równy sumie ich długości.

Zadanie

Napisz program, który:

  • wczyta:
    • liczbę plików kart bibliotecznych, które należy scalić w jeden uporządkowany plik,
    • długości plików,
  • obliczy:
    • minimalny łączny czas uporządkowania kart w bibliotece,
    • kolejność łączenia plików kart dającą ten czas,
  • wypisze wynik.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t (t < 20). Każdy test składa się z dokładnie dwóch wierszy. Pierwszy wiersz zawiera liczbę n (1 < n ≤ 105) plików do scalenia. W drugim wierszu znajduje się n liczb s1s2, ..., sn, poodzielanych pojedynczymi odstępami, gdzie si oznacza długość pliku o numerze i (1 ≤ si ≤ 104).

Wyjście

Dla każdego testu twój program powinien wypisać n wierszy. Wiersz pierwszy powinien zawierać dokładnie jedną liczbę równą minimalnemu czasowi potrzebnemu do scalenia wszystkich plików w jeden. Każdy z następnych wierszy odpowiada łączeniu dwóch plików. Wiersz o numerze i+1 (1 ≤ i ≤ n-1), powinien zawierać dwie liczby całkowite kili (1 ≤ ki < li ≤ n) oddzielone spacją. Liczby te mówią, że w i-tym kroku Bajtazar scala dwa pliki o numerach ki oraz li. Nowo powstały plik otrzymuje numer ki, a jego długość jest równa sumie długości plików ki oraz li.

Jeśli istnieje wiele optymalnych kolejności łączenia plików, Twój program powinien wypisać tylko jedną z nich.

Przykład

Wejście:

1
4
1 2 4 7

Wyjście:

24
1 2
1 3
1 4

Dodane przez:Rafal Nowak
Data dodania:2005-04-29
Limit czasu wykonania programu:10s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Potyczki Algorytmiczne 2005 (marzec)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.