W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Asia i Basia poznały niedawno grę w minima, która bardzo im się spodobała. Zasady tej gry są następujące. Na stole leży pewna liczba kart, na których napisane są dodatnie liczby całkowite. Gracze wykonują ruchy na przemian (pierwszy ruch należy do Asi). W swoim ruchu gracz wybiera dowolną liczbę kart (ale co najmniej jedną) i zabiera je ze stołu. Za taki ruch gracz otrzymuje liczbę punktów równą najmniejszej z liczb zapisanych na zabranych przez niego kartach. Gra kończy się, gdy ze stołu zostanie wzięta ostatnia karta. Każdemu graczowi zależy na tym, aby różnica między jego końcowym wynikiem a wynikiem przeciwnika była jak największa.
Asia i Basia szybko spostrzegły, że w tej grze musi istnieć strategia optymalna. Poprosiły Cię więc o napisanie programu, który dla danego zestawu kart wyznaczy, jaki będzie wynik gry, przy założeniu, że obaj gracze grają optymalnie.
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę kart. W drugim wierszu znajduje się dodatnich liczb całkowitych (), pooddzielanych pojedynczymi odstępami, oznaczających liczby zapisane na kartach.
Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą - liczbę punktów, o które Asia wygra z Basią, pod warunkiem, że obie będą grać optymalnie (jeżeli więcej punktów uzyska Basia, to należy wypisać liczbę ujemną).
Dla danych wejściowych:
3 1 3 1
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu: Asia zabiera ze stołu kartę z liczbą 3, za co otrzymuje trzy punkty. Basia bierze obie pozostałe karty, za co otrzymuje jeden punkt. Gra skończy się wynikiem trzy do jednego, a zatem Asia wygra dwoma punktami.
Autor zadania: Jakub Onufry Wojtaszczyk.