|
Алиса и Боб играют в очередную игру на массиве a длины n.
Алиса начинает с пустого массива c. Оба игрока ходят по очереди, причем Алиса начинает первой.
В свой ход Алиса выбирает один элемент из a, добавляет его в c, а затем удаляет из a.
В свой ход Боб выбирает один элемент из a, а затем удаляет его из a.
Игра заканчивается, когда массив a становится пустым.
Счет игры определяется как MEX† элементов c.
Алиса хочет максимизировать счет игры, а Боб — минимизировать его.
Найдите итоговый счет игры, если оба игрока играют оптимально.
† MEX (minimum excludant) массива целых чисел определяется как наименьшее целое неотрицательное число,
которое не встречается в массиве. Например:
- MEX массива [2,2,1] равен 0, потому что 0 не принадлежит массиву.
- MEX массива [3,1,0,1] равен 2, потому что 0 и 1 принадлежат массиву, а 2 — нет.
- MEX массива [0,3,1,2] равен 4, потому что 0, 1, 2 и 3 принадлежат массиву, а 4 — нет.
|