#include #include #include #include #include #include #include using namespace std; const int WIN = 1; // ход выигрышный const int FAIL = 2; // ход проигрышный const int NAN = 0; // нельзя сделать ход int n,len; string str; long long curState; long long mask; long long one = 1; map > adj; vector mas; vector win; void input() { cin>>n>>len; cin>>str; int pos = 0; for (int i = str.size()-1;i>=0;i--) { if (str[i] == 'X') curState |= one<=0;i++) mask |= one << (hPos - i); } void GenAdj(long long state) { if (adj.find(state) != adj.end()) return; mas.push_back(state); long long curMask = mask; for (int i = 0; i <= n - len; i++) { if ((state & curMask) == 0) { long long next = state | curMask; adj[state].push_back(next); GenAdj(next); } curMask >>= 1; } } void FindAnswer() { sort(mas.begin(), mas.end()); mas.resize(unique(mas.begin(),mas.end()) - mas.begin()); win = vector(mas.size(),0); for (int i = mas.size()-1; i >= 0; i--) { if (adj.find(mas[i]) == adj.end()) win[i] = FAIL; else if (adj[mas[i]].size() == 1) win[i] = WIN; else { vector &v = adj[mas[i]]; bool isCurWin = false; for (int j = 0; j< v.size();j++) { int pos = lower_bound(mas.begin(), mas.end(), v[j]) - mas.begin(); if (win[pos] == FAIL) { isCurWin = true; break; } } win[i] = isCurWin ? WIN : FAIL; } } } void solve() { GenMask(); GenAdj(curState); FindAnswer(); } void output() { if (adj.empty()) cout<