Предсказать победителя игры, переводя 0 в 1 ход за ходом, следуя заданным правилам.
Дана двоичная строка str , состоящая только из 0 и 1 , где 0 представляет незанятую позицию, а 1 представляет занятую позицию. Два игрока A и B должны занимать свободную позицию (преобразовывать 0 в 1) ход за ходом, следуя заданным правилам:
- Игрок может занимать только свободную позицию
- Каждый ход игрок может перемещаться только на соседнюю позицию.
Если игрок не может сделать ход на ходу, он проигрывает. Предскажите победителя игры, если оба игрока играют оптимально, учитывая, что А делает первый ход.
Пример:
Input: str=”1000″
Output: A
Explanation: A makes first move and occupy position at 2nd index of the string(0 based index) then no matter which position B choose there will be only a single unoccupied position left which will be occupied by A in next turn and B can’t make further move hence A wins.Input: str=”1001″
Output: B
Подход:
- Найдите длину двух самых длинных подстрок начальных незанятых позиций (т.е. подстроки из 0 ).
- Если длина наибольшей подстроки четна , то B будет победителем независимо от длины второй наибольшей подстроки. Это связано с тем, что A всегда будет занимать средний слот наибольшей подстроки, следовательно, в этом случае у него будет столько же слотов для хода, сколько осталось для B в данной подстроке. А нужно больше слотов, чем Б , чтобы выиграть игру, в то время как в этом случае у обоих одинаковое количество слотов, следовательно, А проиграет.
- Если длина наибольшей подстроки нечетна , то может быть два случая:
- Если длина второй по величине подстроки меньше, чем количество слотов A в самой большой подстроке (т. е. (n/2) + 1 , где n — размер подстроки), то A будет победителем, поскольку B всегда будет иметь меньшее количество слотов, чем A , независимо от его первоначального решения (выбрать между самой большой или второй по величине подстрокой).
- В противном случае B будет победителем, поскольку B может выбрать вторую по величине подстроку, чтобы сделать начальный ход, и у него будет больше доступных слотов для дальнейших ходов, чем у A.
- Выведите ответ в соответствии с приведенным выше наблюдением.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(1)