#include <iostream>
using namespace std;

int k(string& s)
{
    int ks = 0;
    int pos = s.find('G');
    for(int p = pos; p >= 0 && s[p] != 'D'; --p)
        if (s[p] == 'K') { s[p] = ' '; ++ks; }
    for(int p = pos; p < s.size() && s[p] != 'D'; ++p)
        if (s[p] == 'K') { s[p] = ' '; ++ks; }
    return ks;
}


bool l(const string& s, int keys);
bool r(const string& s, int keys);

bool l(const string& s, int keys)
{
    int pos = s.find('G');
    if (pos == 0 || pos == s.size()-1) return true;
    string t = s;
    keys += k(t);
    int p = pos-1;
    for(; p >= 0; --p)
    {
        if (t[p] == 'D')
        {
            if (keys > 0)
            {
                t[p] = ' ';
                keys--;
                t[p] = 'G';
                t[pos] = ' ';
                return l(t,keys)||r(t,keys);
            }
            return false;
        }
    }
    return true;
}

bool r(const string& s, int keys)
{
    int pos = s.find('G');
    if (pos == 0 || pos == s.size()-1) return true;
    string t = s;
    keys += k(t);
    int p = pos+1;
    for(; p < t.size(); ++p)
    {
        if (t[p] == 'D')
        {
            if (keys > 0)
            {
                t[p] = ' ';
                keys--;
                t[p] = 'G';
                t[pos] = ' ';
                return l(t,keys)||r(t,keys);
            }
            return false;
        }
    }
    return true;
}

int main(int argc, char * argv[])
{
    
    string s = "DKDDGKKDDKDD";
    cout << (l(s,0)||r(s,0)) << endl;
    s = "DDKGDDKKKKKKD";
    cout << (l(s,0)||r(s,0)) << endl;
    s = "DDDDKKKDDKGDKKDDD";
    cout << (l(s,0)||r(s,0)) << endl;
    
}