На столе лежат в ряд палочки. Можно брать одну палочку или две соседних. Тот кто берёт последнюю проигрывает.
Т.е. если группа палочек разделена промежутком (уже кто-то взял или так было в начальной позиции) - то нельзя взять две палочки по обе стороны промежутка.
И выиграет тот, кто вынудит противника взять последнюю палочку.
Пример:
начальная позиция:
XXXXXX
После хода игрока А
XX__XX
После хода игрока B
XX___X
После хода игрока A
______X
Игрок B берёт последнюю и проигрывает.
Очевидно, что любая позиция может быть либо выигрышной (если существует ход переводящий её в проигрышную), либо проигрышной (если любой ход делает её выигрышной). Пример проигрышной позиции 1 палочка, пример выигрышной - пустой стол.
Стратегия игры очевидно напрямую связана с возможностью определять выигрышность позиции.
Требуется внятный алгоритм определения выигрышности позиции. Мне он неизвестен. Статьи по такой именно игре вроде есть в сети, но они не обязательно описывают алгоритм (или не обязательно в доступных терминах). Буду рад помощи!
Кстати, с интересом заметил что рейтинг всех моих старых постов находится на уровне минус 200-300 баллов. По-моему даже JKeeJ1e30 такого не удостаивался. Польщён, весьма польщён! (Вот соплежуям озорникам некуда технический гений направить!) :D
UPD: вижу что случилось какое-то массовое обнуление "вкладов". Чем дальше, тем любопытственнее.
я обязательно когда-нибудь научусь читать условия задач =/
очевидно, что серии подряд идущих "XXX" никак не влияют друг на друга, поэтому можно рассуждать так:
пусть d[i] - ответ для i подряд идущих X, тогда из i можно походить в i-1, i-2, или разбить на две кучки с количеством подряд идущих X, равным, соответственно, j и k, для которых ответ будет d[j] xor d[k]
ответ для 0 и 1 тривиален, остальные можно вычислить, переберя все возможные переходы и выбрать значением функции минимальное из не использовавшихся результатов
если непонятно почему это так - читаем теорию
если d[n] равно нулю, то это проигрышная ситуация, иначе выигрышная
1 - это проигрышная позиция, значит d[1] = 0?
Единственный переход из этой позиции ведёт в 0... Чему, стало быть, равно d[0]?
d[0] никогда не должно использоваться, иначе это означает, что мы кучку размера i разделили на 0 и i-0, чего быть не может
я обычно инициализирую d[0] = 1, хотя не знаю, насколько это можно назвать корректным
ещё вопросы? :)
Но явно моя тупость превозмогает. Поэтому извини и поясни пожалуйста ещё - как считается d для позиции из нескольких кучек. Например d[2, 2] (я думаю тоже должно быть равно 0)...
d[2] xor d[2] = 0, да, это действительно проигрышная позиция
P. S. весь топик со всеми твоими комментариями похож на троллинг, но я учитываю, что связи между срачем в соседнем треде и этим топиком может и не быть ;)
Это не троллинг. Это демка к вот этому комменту.
эта задача отличается от классической или я что-то упускаю? =)
не, тогда решение неверно, её сперва нужно как-то свести к классической, а потом только решать описанным способом
А... Т.е. думать мне ещё рано? ;-)
Насколько я понимаю тут по-моему вот это "очевидно, что серии подряд идущих XXX никак не влияют друг на друга" не вполне верно.
Я пытался когда был маленький найти какие-то формулы для вычисления выигрышности/проигрышности группы из нескольких кучек (типа В+П=В) - но по-моему нашлись контрпримеры и эта идея потерпела неуспех. Правда возможно надо было рассматривать кучки из 1 палочки как отдельную категорию... Впрочем мои чайницкие рассуждения здесь вряд ли уместны. :-(
думаю, что эта задача решается сведением каждой кучки к одной палочке, а потом подсчёту количества одиноких палочек
Ну да, в смысле на будущее друг друга они не влияют. Я хотел сказать что их влияние на оценку позиции из нескольких кучек мне неочевидно.
В позиции 1+3 например кучку 3 надо сводить не к одинокой палочке а к двум одиноким палочкам.
ыыыыыыыыыыыыыыыыыыыыыыыыы
проверяли?... ибо я проверил и у мну не сошлось с брутом...
Кажется, что да. Если позиция в старой игре выигрышная, просто делаем тот же ход, что и в старой игре, не обращая внимания на отдельную палочку. Если позиция в старой игре проигрышная, у нас есть дополнительная возможность убрать отдельную палочку. В этом случае у противника есть ответ, приводящий к выигрышу: интуитивно кажется, что позиция без отдельной палочки не может быть проигрышной и в игре “проигрывает тот, кто сделал последний ход”, и в игре “проигрывает тот, кто не может ходить”.
Если это правда, то применяем к этой модифицированной игре теорию Гранди в чистом виде.
и это проверил... не сходится ни с брутом, ни с идеей Alex_KPR...
В "модифицированной версии" любая комбинация типа 1+K+K (т.е. одна палочка и ещё две кучки равной величины) является выигрышной - забираем одинокую палочку и дальше ведём симметричную игру. Естественно что первым кто не сможет сделать ход, будет наш противник.
Однако если бы игры были эквивалентны, то это означало бы что в "старой версии" любая комбинация K+K проигрывает. На примере (1+1=В и 2+2=П) видно что это не так.