Привет. Задача про игра. Есть N x M прямоугольник. Первый игрок

выберает любая координата (x, y), и вырезает эту строку и столбцу в прямоуголник.

Второй игрок выберает оставшийся любой из прямугольник и повторяет действие, то есть выберает любая координата (x,y) в этом прямуголника и вырезает x-строку, и y-столбцу.

и так далее.

Тот кто не может выбрать прямугольник, то есть для него не останется прямугольник — тот проиграет.

EDIT: надо определить кто выигривает, если оба игрог оптимально играет.


Незнаете как это моделировать независимо для каждой полученный прямоугольника?

Например, если N = 4, M = 4 — то второй игрок всегда выигривает не зависимо как первый игрок первый шаг делает.

Был какие то формулы про XOR операций.

Например, N = 4 , M = 4 и Первый Игрок x = 2, y = 2 выберается, , получаем 4 прямугольника: 1x1 2x1 1x2 2x2 — можно как то для каждого маленького прямугольника вычислят результат независимо и их объеденить?

https://e-maxx.ru/algo/sprague_grundy

Помогло, только решение стало O((N*M)^2), не могу оптимизироваться int nims[1+N][1+M] = { 0 } for A = 1..N for B = 1..M mex = [] for iA = 1..(A+1)/2 for iB = 1..(B+1)/2 xor_sum = nims[ iA-1][iB-1] xor nims[ iA-1][B - iB] xor nims[A-iA][iB - 1] xor nims[A-iA][B - iB]; mex [xor_sum ] = true; nim_A_B = 0; while mex[ nim_A_B] == True: ++nim_A_B nims[A][B] = nim_A_B; if nims[N][M] == 0: lost else win

А ограничения какие?