Решение задачи Игра с таблицей с Codeforces
С пояснением   Просмотров: 159
На каждом ходу, игрок должен захватить одну клетку. Клетку можно захватить, если она еще не захвачена, и она не находится в одной строке или столбце с другой захваченной клеткой. Игра кончается, когда игрок не может сделать ход, в таком случае, он проигрывает.
Если Ashish и Vivek ходят по очереди и Ashish ходит первым, найдите победителя игры если они оба играют оптимально.
Оптимальная игра между двумя игроками означает, что оба игрока выбирают лучшую возможную стратегию, чтобы получить наиболее благоприятный для себя результат игры.
Пояснение к задаче
Ключевая идея:
Вивек и Ашиш никогда не могут претендовать на ячейки в строках и столбцах, в которых уже есть хотя бы одна заявленная ячейка. Таким образом, нам нужно взглянуть на минимальное соотношение количества строк и столбцов, для которых изначально не было заявлено ни одной ячейки.
Решение:
Пусть a будет количеством строк, в которых изначально не было заявлено ни одной ячейки, и аналогичным образом b будет количеством столбцов, в которых изначально не было заявлено ни одной ячейки. Каждый раз, когда игрок делает ход, a и b уменьшаются на 1, так как они требуют ячейки только в строках и столбцах без заявленных ячеек.
Если один из a или b становится 0, игрок, чей ход следующий, проигрывает игру. Поскольку и a, и b уменьшаются на 1 после каждого хода, min (a, b) становится 0 вначале. Итак, если min (a, b) нечетно, Ашиш выигрывает игру, в противном случае выигрывает Вивек.