B. Treasure Hunt | Codeforces Round #482 (Div. 2)

const string ALPHA = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
string NAME[3] = { "Kuro", "Shiro", "Katie" };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    ll N; // 0<=N<=10^9
    cin >> N;
    vector<string> S(3);
    vll ma(3);
    rep(a, 3) {
        cin >> S[a];
        // 1文字のsubribbonだけ考えればいい。
        // すべての1文字のsubribbonを試す
        for (char b : ALPHA) {
            ll x = 0;
            each(c, S[a]) {
                if (b == c)x++;
            }

            // 全部の文字をbにしてもターンが余る場合
            if (N > sz(S[a]) - x) {
                // 余分にpターンある
                ll p = N - sz(S[a]) + x;
                // N = p = 1かつS=bbb...bbbの場合
                // 1つだけ異なる文字になる
                // pが偶数のときは、ある箇所を別の文字にして戻すのをp/2回繰り返せばいい。
                // 上記以外でpが奇数の場合は
                // 全部をbにする直前の操作で
                // 別の文字u=>別の文字v=>b
                // と操作することで残りのターン数が偶数になるので可
                if(p==1 && x == sz(S[a])) smax(ma[a], sz(S[a]) - p);
                else smax(ma[a], (ll)sz(S[a]));
            } else {
                // 他の文字をひたすらbに変えていくだけ
                smax(ma[a], N + x);
            }
        }
    }

    ll m = -1, cnt = 0, cat=-1;
    rep(a, 3) {
        if (m < ma[a]) {
            cat = a;
            m = ma[a];
        }
    }
    rep(a, 3)if (m == ma[a])cnt++;
    if (cnt > 1)cout << "Draw" << endl;
    else cout << NAME[cat] << endl;
}