Codeforces Round #322 (Div. 2) D. Three Logos

問題

codeforces.com

解法

よく考えると, 長方形を並べるパターンは, サンプル 1 のように長方形を縦に並べるパターンか, サンプル 2 のようにひとつの長方形が上に来て残りの長方形がエリアを分け合う感じのいずれかしかないことがわかります。

うまいこと場合わけしてがんばります。

int x[3], y[3];

void no() {
    cout << -1 << endl;
    exit(0);
}

int getRoot(int x) {
    for (int i = 0; i*i <= x; i++) if (i*i == x) return i;
    return -1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 3; i++) cin >> x[i] >> y[i];
    int area = 0;
    for (int i = 0; i < 3; i++) area += x[i]*y[i];
    int n = getRoot(area);
    if (n == -1) no();
    int index = -1;
    for (int i = 0; i < n; i++) {
        if (x[i] == n || y[i] == n) {
            index = i;
            break;
        }
    }
    if (index == -1) no();
    int ok = 0;
    for (int i = 0; i < 3; i++) {
        if (i == index) continue;
        if (x[i] == n || y[i] == n) ok = ok*2+1;
    }
    if (ok == 3) {
        cout << n << endl;
        for (int i = 0; i < 3; i++) {
            int mini = min(x[i], y[i]);
            for (int j = 0; j < mini; j++) {
                for (int k = 0; k < n; k++) {
                    cout << (char)('A'+i);
                }
                cout << endl;
            }
        }
        return 0;
    } else {
        int rest = n-min(x[index], y[index]);
        vector<pii> edge;
        for (int i = 0; i < 3; i++) {
            if (i == index) continue;
            if (x[i] == rest) edge.emplace_back(i, y[i]);
            else if (y[i] == rest) edge.emplace_back(i, x[i]);
            else no();
        }
        if (edge.size() < 2 || edge[0].second+edge[1].second != n) no();
        cout << n << endl;
        for (int i = 0; i < min(x[index], y[index]); i++) {
            for (int j = 0; j < n; j++) {
                cout << (char)('A'+index) ;
            }
            cout << endl;
        }
        for (int i = 0; i < rest; i++) {
            for (int j = 0; j < edge[0].second; j++) {
                cout << (char)('A'+edge[0].first);
            }
            for (int j = 0; j < edge[1].second; j++) {
                cout << (char)('A'+edge[1].first);
            }
            cout << endl;
        }
    }
    return 0;
}