Задачі
Гра в закреслювання
Гра в закреслювання
Полоска паперу розділена на 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