Игры на строке

Здравствуйте, недавно писал отбор в сириус(вполне успешно +- 750 из 1000), но мне захотелось узнать как решать эту задачу. Можете подсказать алгоритм решения? Я думаю что тут дп. ( Задача J)

Задача:
Что еще мы вам не рассказали про строки из нулей и единиц?
Оказывается, со строкой из нулей и единиц можно играть. Петя и Вася берут случайную строку
длины n и играют в игру по следующим правилам. Петя ходит первым и может зачеркнуть единицу
на крайнем левом или крайнем правом месте строки (если по краям строки стоят нули, то Петя сразу
проиграл). Вася ходит вторым, и в оставшейся строке он может зачеркнуть на первом или последнем
месте строки ноль, если он там есть, иначе он проиграл. Далее мальчики продолжают ходить по
очереди по этим правилам, пока кто-нибудь не проиграет, так как не сможет сделать очередной ход.
Другой игрок при этом наберет одно очко + столько очков, сколько составит длина оставшейся
строки. Если проигравшему игроку достаётся пустая строка, то игрок, сделавший последний ход,
выигрывает со счётом 1. Каждый из игроков хочет выиграть и набрать при этом как можно больше
очков.
Предположим, например, что они играют со следующей строкой: 10100011. В свой первый ход
Петя может удалить крайнюю левую или крайнюю правую единицу. Предположим, он выбирает
крайнюю левую. Тогда строка станет 0100011. Тогда Васе не останется ничего другого, как убрать
новый крайний левый ноль, так как крайний правый символ единица, и останется строка 100011.
Петя снова может выбирать, и на этот раз он выбирает крайнюю правую единицу, оставляя 10001
Васе. На данный момент у Васи нет подходящего хода, поэтому победил Петя. Поскольку длина
оставшейся строки 5, Петя побеждает со счётом 1 + 5 = 6 очков. Но если бы Петя первым ходом
вычеркнул последнюю единицу, то ходов у Васи больше не было, и Петя бы выиграл со счётом
1 + 7 = 8.
Требуется написать программу, которая по строке из нулей и единиц определит, кто выиграет
при оптимальной игре обоих, и сколько очков он при этом наберёт.

Тесты:
01 - 0 1
100 - 0 2
101000011 - 1 8

Вложения

selection-main-contest.pdf (201.2 Кб, 46 просмотров)

0

Последний тест вы переписали с ошибкой, добавив лишний ноль.
Вы можете меня осудить за такой выбор, но я считаю, что тут хватит простого перебора рекурсией.
Объясню: в задании длина входной строки ограничена 10 символами. На каждом шаге может быть до 2-х вариантов, причём если у одного игрока 2 варианта, то у следующего будет 1. Стек при такой глубине не закончится, 32 варианта перебрать за 1 секунду тоже вполне реально.
Алгоритм простой, каждый пытается получить побольше и отдать поменьше, то есть return max(-rec(left-1, right), -rec(left, right+1)), только ещё учесть ситуации, когда извлечь левый и/или правый символы нельзя. Победитель определяется по знаку результата, очки - по модулю.

1

Не знаю что на меня нашло, но я мог бы решить её еще на самом этапе если бы заметил что ограничения были до 10 символов, а так я думал что ограничения до 1000 поэтому и хотел решать дп :c

0