В задаче описывается игра на ациклическом графе. Состояниями (вершинами графа) являются пары (n, m), где n и m - расстояния от текущей позиции фигуры до нижнего и правого краев доски соответственно. Из каждого состояния (n, m) существует не более трех переходов: (n - 1, m), (n, m - 1), (n - k, m - k). Граф ациклический, поскольку при каждом переходе сумма n+m строго уменьшается.
Если бы n, m и k в задаче были, скажем, до 1000, то задача решалась бы несложной динамикой на ациклическом графе, стандартной для подобных игр. Пусть d(n, m) = 1, если (n, m) - выигрышная позиция, и d(n, m) = 0, если позиция (n, m) - проигрышная. Тогда d(n, m) вычисляется из следующих соображений: если из позиции существует хотя бы один переход в проигрышное состояние, то эта позиция выигрышная, иначе она проигрышная.
Но ограничения в задаче не позволяют решать ее обычной динамикой. Выход из ситуации - посчитать динамику для маленьких значений n и m и заметить закономерность! Например, построим матрицу значений d(n, m) при k = 2:
01010101010101
10101010101010
01111111111111
10110101010101
01101010101010
10110111111111
01101101010101
10110110101010
01101101............
Будем рассматривать угловые полосы на этой картинке. Начнем с угловой полосы шириной 2 в левом верхнем углу (полоса в данном случае - множество клеток при n <= 2 || m <= 2) .
Получается, что начиная с левого верхнего угла идет полоса ширины 2 (на самом деле k при k > 2), в которой 0 и 1 чередуются. Что неудивительно, потому что в этой полосе нет возможности прыжка на k. Дальше идет полоса из 1, затем - такая же полоса ширины k, как и первая, только инвертированная (1 заменены на 0, 0 на 1), затем - снова полоса из 1, и затем - снова такая же полоса, как и в самом начале! Поскольку каждая следующая угловая полоса зависит только от предыдущей полосы шириной k клеток, получается, что дальше закономерность будет повторяться: последует полоса из плюсов, инвертированная полоса, снова полоса из плюсов и т.д. Фактически получается, что d(n, m) = d(n - (2 k + 2), m - (2 k + 2)) при n, m > 2 k + 2. Отсюда можно получить формулы для вычисления d(n, m) при любых n и m.
Чтобы лучше разобраться в приведенный объяснениях, советую написать программу подсчета динамики и поискать закономерность самостоятельно.
Есть еще один хитрый случай k = 1. Для него получается немного другая закономерность:)
Замечание. Особо подчеркну, что мы не просто нашли закономерность и выдвинули шаманскую гипотезу о том, что она будет повторяться. Мы это доказали. Полосы будут чередоваться дальше, потому что каждая следующая полоса однозначно определяется через предыдущую полосу шириной k клеток.
У меян была идея алгоритмического решения, она заключаласть в следующем:
пусть c = min(a-1,b-1)/k -- кол-во возможных ходов по диагонали. Если min( (a-1) % k , (b-1)%k ) >= c то ответ a+b+c % 2 == 1 , иначе второй игрок может испортить первому ситуацию, ходя в ту сторону, остаток от деления величины которой наименьший (диагонали теперь первому ходить не выгодно), и мы перейдем в следующее состояние, пусть для общности было a%k<b%k. Теперь b %k=(b-a%k)%k; a%k=k-1 c--; a и б уменьшаются равномерно. будем делать динамику по остаткам числа a. их всего будет sqrt(n). возможно будут цикл в ДП надо найти его длину и ввеличину с взять по модулю его длины.
Хотелось бы спросить мнение сообщества по этому методу.
PS Извиняюсь за смутное изложение идеи. Не проснулся еще ))
PS2 Возможны ошибки +-1 и = != :o)