Вопрос
Нам дана целочисленная последовательность S размера N , и два игрока оптимально играют в игру с этой последовательностью, правила игры следующим образом:
- Игроки чередуют ходы.
- В каждом ходу текущий игрок должен выбрать один или несколько элементов текущей последовательности S так, чтобы значения всех выбранных элементов были идентичные, и удалите эти элементы из S.
- Когда игрок не может ничего выбрать (последовательность S уже пуста), этот игрок проигрывает игру.
Мы должны найти количество выигрышных ходов для первого игрока в первом ходу. Если для этой конкретной последовательности нет выигрышных ходов и первый игрок всегда проиграет, мы должны просто вывести ноль.
Например, если последовательность равна 1 2 2 2 тогда количество выигрышных ходов для первого игрока в первом ходу будет равно 3, поскольку удаление любых двух из трех «двойок» обеспечит победу первому игроку.
My Observation
Я думаю, что сначала мы должны сохранить количество уникальных элементов, а затем частоту каждого элемента, затем нам нужно упростить последовательность до определенной ориентации, в которой будет обеспечена победа для первого игрока, затем мы должны просто рассчитать количество движется для достижения этой ориентации с помощью комбинаторики. Я заметил, что если все элементы имеют одинаковые частоты, то первый игрок выиграет за один ход, если число уникальных элементов является нечетным числом и будет проигрывать каждый раз, когда количество уникальных элементов является четным числом. Но я не могу обобщить случай в случае неравных частот.
Вся помощь приветствуется.