Runda 11 - Granie w szkole

14.12.2009

 

Zawody stałe, runda 11.

Limit czasowy: 15s; Limit pamięciowy: 80MB


Jacek i Agatka, jak zwykle, nudzą się na szkolnych lekcjach informatyki, w których po raz dzięsiąty nauczyciel manifestuje wyższość dobrze znanego wszystkim edytora tekstowego nad zwykłym notatnikiem. Postanowili więc zagrać w grę. Ponieważ nazywają siebie informatykami, więc nie potrzebują komputera do grania. Wyciągnęli kartkę i w jednym wierszu zapisali parzystą liczbę liczb całkowitych, nieujemnych. Wymyślili też proste zasady gry: na zmianę mogą skreślić tylko jedną liczbę, która znajduje się jednym z dwóch końców. Wygrywa ten, którego skreślone liczby utworzą większą sumę. Jacek od razu zastanowił się jak wysoki może uzyskać wynik (sumę skreślonych przez niego liczb), w wypadku gdy to on rozpoczyna grę. W tym celu poprosił Ciebie o pomoc.

Zadanie

Dla danych $ n $ liczb wyznacz największą możliwą sumę liczb skreślonych przez Jacka. Musisz oczywiście uwzględnić to, że Agatka będzie grała, tak aby wynik Jacka był jak najmniejszy.

Na przykład dla czterech liczb $ 4 $ $ 10 $ $ 7 $ $ 2 $, największy możliwy wynik to $ 12 $. Aby go osiągnąć Jacek najpierw powinien skreślić liczbę $ 2 $, a potem $ 10 $.

Wejście

W pierwszym wierszu dana jest liczba zestawów testowych (nie większa od dziesięć). Każdy z zestawów podany jest w dwóch wierszach. Pierwszy z nich zawiera dodatnią, parzystą liczbę liczb zapisanych na kartce (nie większą od $ 5000 $). Drugi wiersz zawiera nieujemne liczby całkowite, które zapisane są na kartce (każda z nich jest nie większa od $ 10^{6} $).

Wyjście

Dla każdego zestawu danych wypisz maksymalny możliwy wynik, jaki może uzyskać w grze Jacek, jeśli to on ją rozpoczyna.

Przykład

Dla danych wejściowych

3
2
5 8
4
4 10 9 2
4
4 10 7 2

Prawidłową odpowiedzią jest

8
13
12

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Przemysław Derengowski1078:56:21
2Bartek Dudek10201:41:11
3Anna Piekarska10201:52:16
4Michal Zgliczynski10892:36:32
5Tomasz Wiatrowski10966:09:05
6Maciej Kisiel105961:51:10
7Michał Karpiński106903:14:23
8Kamil Dębowski1010491:21:58
9Szymon Stankiewicz67238:26:58
10Kuba Skudlarski1132:25:22
11Michał Szmidt13326:23:54

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com