Codeforces 581D - Three Logos (枚举)

Sep 28, 2015


## 题意 ##

用三种logo,每种都有长宽,可以旋转,问能不能排成正方形。

## 思路 ##

因为长宽最多才100,满打满算300*100,所以就可以随便乱搞了。

枚举全部的方案,一个一个填上去,一个一个检查。。。

填的时候我排序了一下,把最长的填上去了,以此作为正方形的边长。 其实填的时候用几个数字搞一下就能判断能不能变成正方形了,比赛的时候为了省事全部for了。。。

## 代码 ##

#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#pragma comment(linker, "/STACK:102400000,102400000")
#include <string>
#include <map>
#include <cmath>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(p, num) memset(p, num, sizeof(p))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid+1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define FOR(i, a, b) for (int i=(a); (i) < (b); (i)++)
#define FOOR(i, a, b) for (int i = (a); (i)<=(b); (i)++)
#define TRAVERSAL(u, i) for (int i = head[u]; i != -1; i = edge[i].nxt)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int dir[][2] = { {0, 1}, {1, 0} };
const int seed = 131;
int cases = 0;
typedef pair<int, int> pii;
 
struct POINT
{
    int x, y;
    char cha;
    bool operator < (const POINT &a) const
    {
        return x > a.x;
    }
}p[10];
 
char mp[330][330];
int max_len, ans;
 
void solve(int x, int y, POINT cur)
{
    for (int i = x; i < x+cur.y; i++)
        for (int j = y; j < y+cur.x; j++) mp[i][j] = cur.cha;
}
 
void fill_map(vector<POINT> &cur_point)
{
    sort(cur_point.begin(), cur_point.end());
    max_len = cur_point[0].x;
    for (auto p : cur_point)
    {
        bool placed = false;
        for (int i = 1; i <= 300; i++)
        {
            if (placed) break;
            for (int j = 1; j <= 300 && j <= max_len; j++)
            {
                if (mp[i][j]) continue;
                if (max_len-j+1 < p.x) break;
                solve(i, j, p);
                placed = true;
                break;
            }
        }
    }
}
 
bool check()
{
    for (int i = 1; i <= 305; i++)
    {
        if (mp[i][1] == 0) return true;
        ans = i;
        for (int j = 1; j <= max_len; j++)
            if (mp[i][j] == 0) return false;
    }
}
 
int main()
{
    //ROP;
    int x1, y1, x2, y2, x3, y3;
    for (int i = 0; i < 3; i++)
    {
        cin >> p[i].x >> p[i].y;
        p[i].cha = (i+'A');
    }
    bool flag = false;
    for (int i = 0; i < (1<<3); i++)
    {
        vector<POINT> cur_point;
        for (int j = 0; j < 3; j++)
        {
            int is_rotate = ((i>>j)&1);
            if (is_rotate) cur_point.push_back((POINT){p[j].y, p[j].x, p[j].cha});
            else cur_point.push_back(p[j]);
        }
        fill_map(cur_point);
        if (check())
        {
            if (max_len == ans)
            {
                flag = true;
                break;
            }
        }
        ans = 0;
        MS(mp, 0);
    }
    if (flag)
        printf("%d\n", ans);
    if (flag)
    {
        for (int i = 1; i <= 300; i++)
            if (mp[i][1] == 0) break;
            else printf("%s\n", mp[i]+1);
    }
    else printf("-1\n");
    return 0;
}