printАнтагонистические игры

printИгра в зачёркивание

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Бумажная полоска разделена на `N` клеток. Двое играющих по очереди выбирают и зачёркивают ровно `K` пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.
Ввод
В первой строке содержатся числа `N` и `K` `(1\ ≤\ K\ ≤\ N\ ≤\ 40)`, во второй строке `N` символов: латинская заглавная O – пустая клетка, латинская заглавная X – зачёркнутая клетка.
Вывод
Вывести одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя.

Пример ввода 1

4 2       
OOOO      

Пример вывода 1

1

Пример ввода 2

5 2       
OOOOO     

Пример вывода 2

2

Пример ввода 3

7 2
OXXOXXO

Пример вывода 3

0
Источник: Сипин, Меньшиков
loading