naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2017 - Qualification Round

f:id:n4_t:20170409112739p:plain

とりあえずA〜CまではACで65点、1339位で通過。

4/8(土) 8:00am JST〜4/9(日) 11:00am

7:30から営業してるスタバでコーヒーを飲みながら、8時前から待機。
(通過条件も読まずに)とりあえずA問題を開く。
今回はC++で。問題(サンプルケース)ジェネレータはPythonで。

A-smallを通してからあれこれ読む。25点取れば通過

  • A,B,Dのsmall, Cのsmall-1を通す
  • A,BのsmallとCのsmall-1,small-2を通す

25点を確実に(かつお手軽に)押さえるべく、naiveな解法で
A-small (5), B-small (5), C-small-1 (5) と取って15点
Dは難しいのでC-small-2を先にやって25点
ここまではQR終了を待たずに得点が確定するので、この時点でQR通過確定;
スタバを後にして帰宅

帰宅&ブランチ後、C-large, B-large, A-large と取って65点
Dどうするよ;→歯が立たない

とりあえずA〜CまではACで65点、1339位で通過。

A. Oversized Pancake Flipper (5 + 10)

Dashboard - Qualification Round 2017 - Google Code Jam
1000個でも同時に返せる直列パンケーキ返しって、パンケーキが1つ10cmだったとしても100mの化物になるよね

(small, 5pt) 1:06:20

終了状態から逆算。
可能な全ての手をBFSで調べて、ある盤面に何手で到達可能か記録。
全体の長さがN、返しの長さがKとすると
盤面数が2^N, 返せる位置は(N-K+1)箇所あるから
O((N-K+1)*2^N) とか。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int, int> ii;


int solve_s(string& S, int k) {
    int LS = S.size();

    vector<int> _d(1 << LS, -1);

    queue<ii> q;
    q.push(ii(0, 0));
    int mask = (1 << k) - 1;
    while (!q.empty()) {
        ii p = q.front(); q.pop();
        int pat = p.first, turn = p.second;
        if (_d[pat] >= 0) continue;
        _d[pat] = turn;

        for (int j=k,m=mask; j<LS+1; ++j,m<<=1) {
            int next = pat ^ m;
            if (_d[next] >= 0) continue;
            q.push(ii(next, turn+1));
        }
    }

    int p = 0;
    for(int i=0,m=1; i<LS; ++i,m<<=1) {
        if (S[i] == '-') p |= m;
    }

    return _d[p];
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    string S; cin >> S;
    int LS = S.size();
    int K; cin >> K;

    int ans = solve_s(S, K);

 answer:
    cout << "Case #" << (1+_t) << ": ";
    if (ans >= 0) {
      cout << ans;
    } else {
      cout << "IMPOSSIBLE";
    }
    cout << endl;
  }
}
(large, 10pt) 5:29:59

全ての手は(ビットマスクの)xorなんだよね。ってことは順番関係ないじゃん。左から順にひっくり返すべきなら返して行って、一番右までhappy-sideになるか見ればいい。O(N*K) か。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int, int> ii;


int solve_l(string& S, int k) {
    int LS = S.size();

    vector<bool> t(LS);
    rep(i, LS) t[i] = (S[i] == '-');

    int c = 0;
    for (int i=0; i<=LS-k; ++i) {
        if (t[i]) {
            for (int j=0; j<k; ++j) {
                t[i+j] = !t[i+j];
            }
            ++c;
        }
    }
    for (int i=LS-k+1; i<LS; ++i) {
        if (t[i]) return -1;
    }
    return c;
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    string S; cin >> S;
    int LS = S.size();
    int K; cin >> K;

    int ans = solve_l(S, K);

 answer:
    cout << "Case #" << (1+_t) << ": ";
    if (ans >= 0) {
      cout << ans;
    } else {
      cout << "IMPOSSIBLE";
    }
    cout << endl;
  }
}

B. Tidy Numbers (5 + 15)

Dashboard - Qualification Round 2017 - Google Code Jam
1〜Nの範囲で、10進表記が昇順になってる最大の数を求める。
数え上げだと面倒くさいなあ(Project Eulerっぽい)と思ったけどそうじゃなかった

(small, 5pt) 1:20:40

Nからカウントダウンして、最初に tidy(n) == true な n を返す。
桁数はlog(N)/log(10)なので O(N logN) か。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef long long ll;

#include <cassert>


inline bool tidy(ll n) {
    for (ll x=n,l=10; x>0; ) {
        ll o = x % 10;
        if (o > l) return false;
        x /= 10;
        l = o;
    }
    return true;
}

ll solve_s(ll N) {
    assert(1 <= N && N <= 1000);
    for (ll n=N; n>=1; --n) {
        if (tidy(n)) return n;
    }
    return 1;
}

int main(){
  int _T; cin>>_T;


  rep(_t,_T){
      ll N; cin >> N;

 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << solve_s(N) << endl;
  }
}
(large, 15pt) 5:07:53

10進表記したNを左から見ていって、k桁目の数字が(k-1)桁目の数字以上ならそのまま、そうでなければ(可能なら)-1した数を採用し、そこから先を999... で埋める。18桁で2分岐したら2^18通りの計算?とか思ったけど、後者についてはそれ以上調べる必要がないから高々2*18通り、か。
計算量は桁数に比例するので O(logN) か。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef long long ll;

#include <cassert>


inline ll vec2ll(vector<int>& v) {
    int k = v.size();
    ll n = 0LL;
    rep(i, k) {
        n = n * 10LL + v[i];
    }
    return n;
}


vector<int> s;
int k;

ll sub(vector<int>& abc, int i) {
    if (i == k) {
        assert(abc <= s);
        return vec2ll(abc);
    }

    ll best = -1;

    int si = s[i];
    for (int j=i; j<k; ++j) abc[j] = si;
    if (abc <= s) {
        best = max(best, sub(abc, i+1));
    }

    if (si > 0) {
        abc[i] = si-1;
        for (int j=i+1; j<k; ++j) abc[j] = 9;
        best = max(best, vec2ll(abc));
    }

    return best;
}

ll solve_l(ll N) {
    assert(1 <= N && N <= 1e18);

    s.clear();
    while (N) {
        s.push_back((int)(N % 10LL));
        N /= 10LL;
    }
    reverse(all(s));
    k = s.size();
    int first = s[0];
    assert(1 <= first && first <= 9);

    {
        vector<int> aaa(k, s[0]);
        if (s < aaa) {
            vector<int> nines(k, 9);
            nines[0] = s[0]-1;
            return vec2ll(nines);
        }
    }

    vector<int> abc(k, s[0]);
    return sub(abc, 1);
}

int main(){
  int _T; cin>>_T;


  rep(_t,_T){
      ll N; cin >> N;

 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << solve_l(N) << endl;
  }
}

C. Bathroom Stalls (5 + 10 + 15)

Dashboard - Qualification Round 2017 - Google Code Jam
鴨川等間隔の法則問題。

(small-1, 5pt) 2:17:48

シミュレーションしてみた
各stallについて左スペース、右スペースを保持してるから全く愚直というわけでもないけれど。
K人について、全室(N)の左右をスキャンするから O(NK) か。
(今回の実装ではsetを使っちゃってるから更にlogN倍?)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())


typedef long long ll;
typedef pair<ll, ll> ll_ll;

#include <cassert>


ll_ll solve_s1(ll N, ll K) {
    vector<ll> left(N), right(N);
    rep(i, N) {
        left[i] = i; right[i] = (N-1)-i;
    }
    vector<bool> used(N, false);

    ll choice;

    for (ll k=0; k<K; ++k) {

        ll max_min = -1, max_max = -1;
        set<ll> mins, maxs;

        for (ll i=0; i<N; ++i) {
            if (used[i]) continue;
            ll _min = min(left[i], right[i]);
            if (_min >= max_min) {
                if (_min > max_min) {
                    mins.clear();
                    max_min = _min;
                }
                mins.insert(i);
            }
        }
        assert(mins.size() >= 1);
        if (mins.size() == 1) {
            choice = *mins.begin();
            goto chosen;
        }


        tr(it, mins) {
            ll i = *it;
            if (used[i]) continue;
            ll _max = max(left[i], right[i]);
            if (_max >= max_max) {
                if (_max > max_max) {
                    maxs.clear();
                    max_max = _max;
                }
                maxs.insert(i);
            }
        }
        choice = *maxs.begin();
        goto chosen;

    chosen:
        {
            assert(0 <= choice && choice < N);
            used[choice] = true;
            if (k == K-1) break;

            for (ll p=choice+1; p<N; ++p) {

                ll newd = (p - choice) - 1;
                if (left[p] < newd) break;
                left[p] = newd;
            }
            for (ll p=choice-1; p>=0; --p) {

                ll newd = (choice - p) - 1;
                if (right[p] < newd) break;
                right[p] = newd;
            }
        }

    }
    return ll_ll(left[choice], right[choice]);
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      ll N, K; cin >> N >> K;


      ll_ll ans = solve_s1(N, K);
      ll Ls = ans.first, Rs = ans.second;
 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << max(Ls, Rs) << " " << min(Ls, Rs);
    cout << endl;
  }
}
(small-2, 10pt) 2:40:17

あれ?誰か1人入ったらそのstallを境に風呂場は2分割されて、次からは長い方の(一番長い)風呂場を選んで同じ問題を解けばいいのでは。
プライオリティキューに風呂場の長さを突っ込んで、人が来るたびに分割した長さを再度突っ込んで。
priority_queueにK人突っ込むから O(K logK) かな。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())


typedef long long ll;
typedef pair<ll, ll> ll_ll;

#include <cassert>


ll_ll solve_s2(ll N, ll K) {
    priority_queue<ll> pq;
    pq.push(N);

    for (ll k=0; k<K; ++k) {
        ll L = pq.top(); pq.pop();
        ll m = (L-1)/2, r = (L-1) - m;
        assert(m <= r && r <= m+1);
        pq.push(m); pq.push(r);
        if (k == K-1) return ll_ll(r, m);
    }

    return ll_ll(0, 0);
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      ll N, K; cin >> N >> K;


      ll_ll ans = solve_s2(N, K);
      ll maxl = ans.first, minl = ans.second;
 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << maxl << " " << minl;
    cout << endl;
  }
}
(large, 15pt) 4:24:10

同じ長さの風呂場がいくつあるかが分かれば、更に効率よくなるね。
priority_queueに突っ込む回数はlogK回とか?
O(logK log logK)とか?

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())


typedef long long ll;
typedef pair<ll, ll> ll_ll;

#include <cassert>


ll_ll solve_s3(ll N, ll K) {
    priority_queue<ll_ll> pq;

    pq.push(ll_ll(N, 1));

    ll k = 0;
    while (true) {
        ll L = pq.top().first, M = pq.top().second; pq.pop();
        if (!pq.empty()) {
            ll next_L = pq.top().first;
            if (next_L == L) {
                ll next_M = pq.top().second;
                pq.pop();
                pq.push(ll_ll(L, M+next_M));
                continue;
            }
        }
        ll m = (L-1)/2, r = (L-1) - m;
        assert(m <= r && r <= m+1);
        pq.push(ll_ll(m, M));
        pq.push(ll_ll(r, M));

        if (K <= M) {
            return ll_ll(r, m);
        }
        K -= M;
    }

    return ll_ll(0, 0);
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      ll N, K; cin >> N >> K;


      ll_ll ans = solve_s3(N, K);
      ll maxl = ans.first, minl = ans.second;
 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << maxl << " " << minl;
    cout << endl;
  }
}

D. Fashion Show (10 + 25)

Dashboard - Qualification Round 2017 - Google Code Jam

制約をどう利用していったらいいのか見当もつかず。

(small, 10pt)

上1行目だけ既にmodelが入っている特殊ケース。
n-queensみたいにoを置いていけるのか?いや、その効き筋にx+が置けなくなるからさほど得点にならない?
終了間際に一投してみたやつはWA。どういう状態が最密なのか掴めてないんだろう。
// WA解ソース→Qual. D small (WA解) · GitHub

(large, 25pt)

見当もつかなかった

【終了後】

→ oをxと+の重ね合わせと見ればxと+を独立で最適化できるらしい。つまり、+は同じ斜め線上に、xは縦横線上に、それぞれ2つ以上存在しないことが保証されさえすれば、x-+相互の位置関係などどうでもいい、ということ。そこに気づけたか気づけなかったかが勝敗を分けた。

どの座標に配置するかは、あらかじめ盤面に存在する '+', 'x' それぞれが専有している座標を集合から抜いた上で、使えるx座標集合(それぞれ1回ずつしか使えない)と、使えるy座標集合(同じく1回ずつしか使えない)を組み合わせる最大マッチング問題。

  • '+'の方は45度回転した座標系、というか (x+y), (x-y) 座標系で、交点 (x, y) が盤面に乗っている(0<=x
  • 'x' の場合は完全二部グラフで、どれをどの順に選んでも変わらないのでgreedyでOK。

とりあえず、smallはWAコードを少し手直ししたやつで通った。要はoを特別扱いしなくていいこと、+をxを避けて配置しなくてもいい(一番上の1行をxxxxxxxxxxと埋め尽くして、一番下の行を .xxxxxxxxxxx. みたいな角だけ空けて埋め尽くす形で十分)。xはgreedyに上から1行に1つずつ配置していくだけ。

図説

agwたんに説明した時にホワイトボードに描いた図
f:id:n4_t:20170410081527j:plain
f:id:n4_t:20170410081535j:plain
f:id:n4_t:20170410081542j:plain
f:id:n4_t:20170410081550j:plain

実装 (small, large)
// small
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#include "cout11.h"
#define NDEBUG
#include <cassert>

typedef pair<int, int> ii;


int render(int N, vector<int>& F, vector<vector<int> >& G) {
    int score = 0;
    vector<pair<char, ii> > Q;

    rep(r, N) rep(c, N) {
        score += __builtin_popcount(G[r][c]);

        if (r == 0 && G[r][c] == F[c]) continue;
        if (G[r][c]) {
            Q.push_back(make_pair(G[r][c], ii(r, c)));
        }
    }

    bool is_valid = true;
#ifdef VALIDITY_CHECK
    {
        rep(r, N) rep(c, N) {
            if (G[r][c] & 2) {

                rep(ri, N) {
                    if (ri == r) continue;
                    if (G[ri][c] & 2) { is_valid = false; goto valid_check_end; }
                }

                rep(ci, N) {
                    if (ci == c) continue;
                    if (G[r][ci] & 2) { is_valid = false; goto valid_check_end; }
                }
            }
            if (G[r][c] & 1) {

                rep(ci, N) {
                    int d = ci - c;
                    if (d == 0) continue;
                    int ri = r + d;
                    if (0 <= ri && ri < N) {
                        if (G[ri][ci] & 1) { is_valid = false; goto valid_check_end; }
                    }
                    ri = r - d;
                    if (0 <= ri && ri < N) {
                        if (G[ri][ci] & 1) { is_valid = false; goto valid_check_end; }
                    }
                }
            }
        }
    valid_check_end:
        ;
    }
#endif

    printf("%d %lu\n", score, Q.size());
    rep(i, Q.size()) {
        printf("%c %d %d\n", ".+xo"[Q[i].first], 1+Q[i].second.first, 1+Q[i].second.second);
    }
    return is_valid;
}

int solve_s(int N, vector<pair<char, ii> >& P) {
    int M = P.size();
    vector<int> F(N, 0);

    int ox_at = -1;
    rep(i, M) {
        char ch = P[i].first;
        int r = P[i].second.first, c = P[i].second.second;
        assert(r == 0);

        if (ch == '+' || ch == 'o') { F[c] |= 1; }
        if (ch == 'x' || ch == 'o') { F[c] |= 2; ox_at = c; }
    }

    vector<vector<int> > G(N, vector<int>(N, 0));
    G[0].assign(all(F));
    int last = N-1;

    vector<bool> used(N, false);;
    if (ox_at >= 0) {
        used[ox_at] = true;
    } else {
        G[0][0] |= 2;
        used[0] = true;
    }
    for (int r=1,c=0; r<N; ++r) {
        if (used[c]) ++c;
        G[r][c] |= 2;
        used[c++] = true;
    }

    rep(c, N) G[0][c] |= 1;
    for(int c=1; c<last; ++c) G[last][c] |= 1;

    return render(N, F, G);
}

int main(){
    int _T; cin>>_T;
    rep(_t,_T){
        cout << "Case #" << (1+_t) << ": ";

        int N; cin >> N;
        assert(1 <= N && N <= 100);

        vector<pair<char, ii> > P;
        int M; cin >> M;
        assert(0 <= M && M <= N*N);

        rep(m, M) {
            char ch; int r, c; cin >> ch >> r >> c;
            assert(ch == '+' || ch == 'x' || ch == 'o');
            --r; --c;
            assert(0 <= r && r < N);
            assert(0 <= c && c < N);

            P.push_back(make_pair(ch, ii(r, c)));
        }
        solve_s(N, P);
    }
}

largeは最大マッチング(最大フロー)問題

// large
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#include <cassert>

typedef pair<int, int> ii;

int N;
int F[100][100], G[100][100];

int render() {
    int score = 0;
    vector<pair<char, ii> > Q;

    assert(1 <= N && N <= 100);
    rep(r, N) rep(c, N) {
        score += __builtin_popcount(G[r][c]);

        if (G[r][c] == F[r][c]) continue;
        if (G[r][c]) {
            Q.push_back(make_pair(G[r][c], ii(r, c)));
        }
    }

    bool is_valid = true;
    {
        rep(r, N) rep(c, N) {
            if (G[r][c] & 2) {
                rep(ri, N) {
                    if (ri == r) continue;
                    if (G[ri][c] & 2) { is_valid = false; goto valid_check_end; }
                }

                rep(ci, N) {
                    if (ci == c) continue;
                    if (G[r][ci] & 2) { is_valid = false; goto valid_check_end; }
                }
            }
            if (G[r][c] & 1) {

                rep(ci, N) {
                    int d = ci - c;
                    if (d == 0) continue;
                    int ri = r + d;
                    if (0 <= ri && ri < N) {
                        if (G[ri][ci] & 1) { is_valid = false; goto valid_check_end; }
                    }
                    ri = r - d;
                    if (0 <= ri && ri < N) {
                        if (G[ri][ci] & 1) { is_valid = false; goto valid_check_end; }
                    }
                }
            }
        }
    valid_check_end:
        ;
    }

    printf("%d %lu\n", score, Q.size());
    rep(i, Q.size()) {
        printf("%c %d %d\n", ".+xo"[Q[i].first], 1+Q[i].second.first, 1+Q[i].second.second);
    }
    return is_valid;
}

#define infty 987654321
vector<pair<int, int> > maximum_match(vector<pair<int, int> >& possible_pairs) {
    int M = possible_pairs.size();
    if (M <= 1) {
        return possible_pairs;
    }

    set<int> _part1, _part2;
    for (int i=0; i<M; ++i) {
        int p1 = possible_pairs[i].first, p2 = possible_pairs[i].second;
        _part1.insert(p1);
        _part2.insert(p2);

    }
    vector<int> part1(all(_part1)), part2(all(_part2));
    int P1 = part1.size(), P2 = part2.size();
    map<int, int> part1_map, part2_map;
    for (int i=0; i<P1; ++i) part1_map[part1[i]] = i;
    for (int i=0; i<P2; ++i) part2_map[part2[i]] = i;

    int w = 1 + P1 + P2 + 1;

    vector<vector<int> > capacity(w, vector<int>(w, 0));
    for (int i=0; i<P1; ++i) {
        capacity[0][1+i] = 1;
    }
    for (int i=0; i<M; ++i) {
        int p1 = part1_map[possible_pairs[i].first];
        int p2 = part2_map[possible_pairs[i].second];
        assert((0 <= p1 && p1 < P1) && (0 <= p2 && p2 < P2));

        capacity[1+p1][1+P1+p2] = 1;
    }
    for (int i=0; i<P2; ++i) {
        capacity[1+P1+i][1+P1+P2] = 1;
    }

    int s = 0, t = w-1;

    vector<vector<int> > resid(w, vector<int>(w, 0));
    for (int j=0; j<w-1; ++j) {
        for (int k=j+1; k<w; ++k) {
            resid[j][k] = capacity[j][k];
            resid[k][j] = 0;
        }
    }

    int total = 0;
    for (total=0; ; ++total) {
        bool another_way = false;
        vector<int> prev(w, infty);
        queue<pair<int, int> > q;
        q.push(pair<int, int>(s, -1));
        while (!q.empty()) {
            pair<int, int> p = q.front();
            int node = p.first, prev_node = p.second;
            q.pop();
            prev[node] = prev_node;
            if (node == t) { another_way = true; break; }
            rep(i, w) {
                if (resid[node][i] == 0) continue;
                if (prev[i] < infty) continue;
                q.push(pair<int, int>(i, node));
            }
        }

        if (!another_way) {

            break;
        }
        for (int node=t; node!=s; node=prev[node]) {
            int prev_node = prev[node];
            resid[prev_node][node]--;
            resid[node][prev_node]++;
        }
    }

    vector<pair<int, int> > pairs;
    rep(i, M) {
        int p1 = part1_map[possible_pairs[i].first];
        int p2 = part2_map[possible_pairs[i].second];
        assert((0 <= p1 && p1 < P1) && (0 <= p2 && p2 < P2));

        int r1 = resid[1+p1][1+P1+p2], r2 = resid[1+P1+p2][1+p1];
        if (r1 == 0 && r2 == 1) pairs.push_back(possible_pairs[i]);
    }
    assert(pairs.size() == total);

    return pairs;
}

int solve_l(vector<pair<char, ii> >& P) {
    int M = P.size();

    memset(F, 0, sizeof(F));
    memset(G, 0, sizeof(G));

    int ox_at = -1;
    rep(i, M) {
        char ch = P[i].first;
        int r = P[i].second.first, c = P[i].second.second;

        if (ch == '+' || ch == 'o') { F[r][c] |= 1; }
        if (ch == 'x' || ch == 'o') { F[r][c] |= 2; }
    }

    int last = N-1;
    vector<bool> used_c(N, false), used_r(N, false);
    set<int> used_sums, used_diffs;
    rep(r, N) {
        rep(c, N) {
            int x = G[r][c] = F[r][c];
            if (x & 2) {
                used_c[c] = used_r[r] = true;
            }
            if (x & 1) {
                used_sums.insert(r+c);
                used_diffs.insert(r-c);
            }
        }
    }

    vector<int> sums, diffs;
    for (int sum=0; sum<=N+N; ++sum) {
        if (!found(used_sums, sum)) sums.push_back(sum);
    }
    for (int diff=-N; diff<=N; ++diff) {
        if (!found(used_diffs, diff)) diffs.push_back(diff);
    }

    vector<int> unused_c;
    rep(c, N) {
        if (!used_c[c]) unused_c.push_back(c);
    }

    for (int r=0,i=0; r<N; ++r) {
        if (!used_r[r]) {
            int c = unused_c[i++];
            G[r][c] |= 2;
        }
    }


    vector<ii> possible_pairs;
    rep(i, sums.size()) {
        int sum = sums[i];
        rep(j, diffs.size()) {
            int diff = diffs[j];
            int r2 = sum + diff, c2 = sum - diff;
            if (r2 & 1 /*|| c2 & 1*/) continue;
            int r = r2/2, c = c2/2;
            if ((0 <= r & r < N) && (0 <= c & c < N)) {
                possible_pairs.push_back(ii(i, j));
            }
        }
    }

    vector<ii> pairs = maximum_match(possible_pairs);


    rep(k, pairs.size()) {
        int i = pairs[k].first, j = pairs[k].second;
        int sum = sums[i], diff = diffs[j];
        int r = (sum + diff)/2, c = (sum - diff)/2;
        G[r][c] |= 1;
    }

    return render();
}

int main(){
    int _T; cin>>_T;
    rep(_t,_T){
        cout << "Case #" << (1+_t) << ": ";

        /* int N; */ cin >> N;
        assert(1 <= N && N <= 100);

        vector<pair<char, ii> > P;
        int M; cin >> M;
        assert(0 <= M && M <= N*N);

        rep(m, M) {
            char ch; int r, c; cin >> ch >> r >> c;
            assert(ch == '+' || ch == 'x' || ch == 'o');
            --r; --c;
            assert(0 <= r && r < N);
            assert(0 <= c && c < N);

            P.push_back(make_pair(ch, ii(r, c)));
        }
        solve_l(P);
    }
}