|
Во время своих новогодних каникул дядя Федор решил устроить для Матроскина и Шарика соревнование в арифметике.
Для этого он организовал игру с помощью своей коллекции карточек натуральных чисел. Дядя Фёдор разложил все карточки на столе и задал вопрос:
Сумма каких чисел (четных или нечётных) больше?
Шарик, не долго думая, ответил "нечётных"
Матроскин сразу выбрал другой вариант и ответил "четных"
Дядя Фёдор предложил Шарику и Матроскину сыграть в следующую игру:
- Игроки ходят по очереди, первым ходит Шарик.
- Каждый ход игрок выбирает любую карточку и удаляет её со стола
- Если Матроскин выбрал четное число, то он прибавляет его в свой результат. Если же число было нечетным, то карточка вешается на новогоднюю елку.
- Аналогично, если Шарик выбрал нечетное число, то он прибавляет его в свой результат. Если же число было четным, то карточка отправляется на елку.
Если в массиве не осталось чисел, то игра заканчивается. Побеждает тот игрок, результат которого больше.
Результат игры равен разности результата победителя и проигравшего
Если результаты игроков равны, то объявляется ничья.
Например, если n=4 и a=[5,2,7,3], то игра могла пройти следующим образом (существуют и другие варианты):
- Первым ходом Алиса выбрала число 2 и получила два очка. Ее результат теперь равен 2. Массив a становится равным [5,7,3].
- Вторым ходом Боб выбрал число 5 и получил пять очков. Его результат теперь равен 5. Массив a становится равным [7,3].
- Третьим ходом Алиса выбрала число 7 и не получила очков. Ее результат теперь равен 2. Массив a становится равным [3].
- Последним ходом Боб выбрал число 3 и получил три очка. Его результат теперь равен 8. Массив a становится пустым.
- Так как у Боба на конец игры больше очков, он объявлется победителем.
Вам интересно, кто победит и чему может быть равен максимальный результат игры, если оба игрока будут играть оптимально
Обратите внимание, что в массиве могут быть повторяющиеся числа.
|