GCJ 2015 Qual D. Ominous Omino

2015/04/13 (Mon) gcj 場合分け 探索

問題

https://code.google.com/codejam/contest/6224486/dashboard

$N$ 枚の正方形の板を、辺同士をくっつけて並べてできる図形たちを $N$-omino と呼ぶ。

http://mathworld.wolfram.com/Polyomino.html

入力として $X , R , C$ が与えられる。 $X$-omino を使って、$R \times C$ の長方形の方眼を敷き詰めたい。 このとき、「ある 1 つの種類の $X$-omino を必ず使わなければいけない」という条件がある。 敷き詰めをが不可能にするような $X$-omino は存在するか判定せよ。

方針

Small は十分小さいので全ての場合を手作業で確かめて通した。

Large は $X \geq 7$ のときは真ん中に穴が開いたミノが作れ、それがあると絶対に敷き詰めできないので $X=5,6$ のときだけ考えれば良い。 Small と同じように全列挙するか探索を書こうとしたけどそれなりに面倒で Qual 通過も確定していたのでやめた。

実装

string const GA = "GABRIEL";
string const RI = "RICHARD";
string solve(int X, int R, int C){
    if(R>C) swap(R,C);
    if(X==1){
        if(R*C%X!=0) return RI;
        else return GA;
    }
    if(X==2){
        if(R*C%X!=0) return RI;
        else return GA;
    }
    if(X==3){
        if(R*C%X!=0) return RI;
        else {
            if((R==3 && C==3) || (R==3 && C==4) || (R==2 && C==3)) return GA;
            if((R==1 && C==3)) return RI;
        }
    }
    if(X==4){
        if(R*C%X!=0) return RI;
        else {
            if((R==4 && C==4) || (R==3 && C==4)) return GA;
            else return RI;
        }
    }
    dump(X,R,C);
    return "!!!";
}

int main(){
    int T;
    cin >> T;
    rep(i,T){
        int X,R,C;
        cin >> X >> R >> C;
        string ans = solve(X,R,C);
        cout << "Case #" << i+1 << ": " << ans << endl;
    }
}