| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 35 | 17 | 13 | 41.935% |
Hektor ze Zbyszkiem codziennie rano wybierają się po ciastka. Ciastkarz przygotowuje każdorazowo N ciastek, z których każde opisuje jedna liczba naturalna reprezentująca jego jakość. Chłopcy na zmianę wybierają po jednym ciastku, zawsze wybierając najlepsze z dostępnych jeszcze ciastek.
W tym tygodniu na Zbyszka przypada kolej dokonywania pierwszego wyboru, co jest zdaniem Hektora bardzo niesprawiedliwe. Hektor chciałby, żeby przewaga Zbyszka (suma jakości ciastek wybranych przez Zbyszka pomniejszona o sumę jakości ciastek Hektora) była możliwie mała. Aby osiągnąć ten cel postanowił uciec się do drobnej manipulacji.
Hektor zadzwonił wcześnie rano do kończącego pracę ciastkarza i zapytał o ciastka przygotowane na dzisiaj. Ciastkarz bardzo lubi Hektora i może na jego prośbę uzupełnić ten zbiór o jeszcze jedno jedno ciastko wybranej przez Hektora jakości.
Znając jakości przygotowanych ciastek i mogąc uzupełnić ten zbiór o maksymalnie jedno ciastko dowolnej ( naturalnej ) jakości oblicz minimalną osiągalną przewagę Zbyszka nad Hektorem.
W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z<= 10 ). Następniepodawane są kolejne zestawy testowe.
Każdy zestaw zaczyna się od liczby naturalnej N ( 1 <= N <= 1000000 ) oznaczającej liczbę ciastek przygotowanych przez ciastkarza.
W drugiej linii zestawu znajduje się N liczb naturalnych Ai reprezentujących jakości kolejnych ciastek ( 1 <= Ai <= 1000 ).
Dla każdego przypadku testowego wypisz w osobnej linii minimalną różnicę pomiędzy jakością ciastek Zbyszka a jakością ciastek Hektora.
4 2 1 1 2 1 2 3 1 1 1 5 16 15 7 8 3
0 1 0 2
Contest > Spot > SpringSpot 2010 1-3번