Недавно прочитал, что узнавать, кто выигрывает в ним, в котором разрешено брать камни из не более, чем k кучек (при этом нужно взять хотя бы один камень хотя бы из одной кучки), довольно легко. Оказывается, достаточно просто выписать все двоичные записи величин кучек и просуммировать биты каждого столбика по модулю (k+1). Если в результате везде нули — первый игрок проиграл. К сожалению, моих знаний языка и математики не хватило, чтобы понять доказательство. Был бы благодарен, если бы кто-нибудь растолковал.
Я нашел задачу, где, собственно, просто надо вывести, кто выигрывает и восстановить выигрышный первый ход: ipc.susu.ac.ru
Но, к сожалению, с восстановлением ответа у меня возникли проблемы. Я попробовал перебирать маску битовых столбцов, в которых мы будем увеличивать число поставленных бит. В остальных, соответственно, уменьшать. Далее я жадно беру k кучек и пробую их изменять. Получаю WA, что, конечно, неудивительно, но ничего лучшего я пока не придумал. Возможно, у этой задачи есть какое-нибудь стандартное решение?
недавно об этом писал paladin8, если еще не читал, прочти)
если кратко, то пусть (k+1)-xor не равен нулю. Возьмем самый старший разряд, в котором он не равен нулю, а равен некоторому l. Тогда возьмем l кучек, у которых в этой позиции стоит единица (такие, очевидно, найдутся), и заменим эти единицы на нули. Теперь мы можем менять все более младшие разряды: как ставить 0 вместо 1, так и 1 вместо 0, ибо в разряде, старшем чем текущий, мы поменяли единицу на ноль. Идем далее по разрядам вправо. Если в сумме в этом разряде стоит число l, то попробуем поменять в наших текущих выбранных числах текущие разряды так, чтобы (k+1)-xor итога по этому разряду стал нулем. Если мы этого сделать не можем, добавим к нашим текущим числам еще несколько из набора так, чтобы (k+1)-xor текущего разряда стал нулем. Утверждается, что для этого нужно добавить не более (k-l) чисел. Действительно, для текущих l чисел мы можем сделать (k+1)-xor текущего разряда любым от 0 до l. Если при этом (k+1)-xor в этом разряде всей суммы не может стать нулем, то в оставшихся числах содержится не более (k-l) единичек в текущем разряде. Добавим тогда все такие числа в наши текущие и заменим все единички в этом разряде на нули.
Поскольку на каждом шаге у нас текущих чисел не более k, то в итоге мы можем выбрать не больше чем k кучек, из которых можно поубирать камней (текущие числа у нас в итоге процесса уменьшились), чтобы после этого (k+1)-xor стал нулем. Вот так можно найти выигрышный первый ход. Немного тафтологично, но вроде понятно, вопросы приветствуются :)
О, круто. Да, понятно, спасибо. А вы встречали какие-нибудь задачи на эту тему?
не так давно была на КФ, но сам не писал ни разу) собственно, paladin8 был вдохновлен именно этой задачей на написание своего поста
В статье е-макса недавно была поправка про восстановление ответа.