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

AL_13_04 - Nadmiar trudu

Nadmiar trudu

Za siedmioma bitami, za siedmioma bajtami i jednym terabajtem, w malowniczo położonej krainie, wzdłuż drogi co jeden kilometr rozstawione są w porządku rosnącym punkty widokowe. Chcąc odwiedzić każdy z tych punktów i przebyć jak najkrótszą drogę można rozpocząć od pierwszego, a skończyć na ostatnim. Ale jak zrobić to najgorzej, czyli tak, aby pokonana droga była jak najdłuższa?
Dla zadanej liczby punktów widokowych musisz ustalić jak długa będzie taka droga i zaplanować ją w taki sposób, aby porządek odwiedzanych punktów był leksykograficznie najmniejszy.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (d ≤ 100) - liczba przypadków testowych.
W kolejnych d wierszach dla każdego przypadku testowego podana jest liczba punktów widokowych n (2 ≤ n ≤ 106).
Dla danych wejściowych zachodzi warunek: d · max(n) ≤ 106).

Wyjście
Dla każdego przypadku testowego w pierwszym wierszu należy podać długość najdłuższej drogi, w wierszu drugim leksykograficznie najmniejszą permutację ciągu liczbowego 1, 2, ..., n składającego się na kolejność odwiedzanych punktów widokowych tak, aby pokonana droga spełniała warunek najdłuższej.

 

Przykład

Wejście
1
5

Wyjście
11
2 4 1 5 3

Wyjaśnienie do przykładu
Rozpoczynamy w punkcie widokowym nr 2, dalej odwiedzamy kolejno punkty widokowe: 4, 1, 5 i kończymy w punkcie widokowym nr 3. Tak zaplanowana trasa jest jedną z najdłuższych i wynosi 2 + 3 + 4 + 2 = 11, a wypisany ciąg jest leksykograficznie najmniejszy.


Dodane przez:Mariusz Śliwiński
Data dodania:2013-11-16
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2013-12-22 15:40:50 Filip £ubniewski
czy mógłby ktoś podać odpowiedź dla np. n=10?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.