Codeforces Round #269 (Div. 2) solution

A.MUH and Sticks

题意：给你6根棍子，问你能否拼出熊或者象。要拼出熊首先要有4个长度一样的棍子当腿，另外2个长度不同的棍子当身体和脑袋。拼大象也需要4个长度一样的棍子当腿，但需要另外2个长度相同的棍子当身体和脑袋。

解法：详见代码。

代码：

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;

int m[11];

int main() {
    int a;
    for(int i = 0; i < 6; i++) { scanf("%d", &a); m[a]++; }
    int f = 0;
    for(int i = 1; i <= 9; i++) { if(m[i] >= 4) m[i] -= 4, f = 1; }
    if(!f) { printf("Alien
"); return 0; }
    for(int i = 1; i <= 9; i++) { if(m[i] >= 2) f = 0; }
    if(!f) printf("Elephant
");
    else printf("Bear
");

    return 0;
}

B.MUH and Important Things

题意：给你一些任务，每个任务有一个难度。问你这些任务按照难度排序能否排出至少3个不同的序列。

解法：显然若有3个或以上任务难度相同我们就可以构造出答案，若没有3个任务难度相同有两组2个难度相同的任务也可构造出答案，否则无解。

代码：

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;

pair<int, int> a[2010];
int o[3][2010], n;

void ot() {
    printf("YES
");
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < n; j++) printf("%d%c", o[i][j], j == n - 1 ? '
':' ');
    }
}

int main() {
    int k = 1;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i].first);
        a[i].second = i + 1;
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++)  o[0][i] = o[1][i] = o[2][i] = a[i].second;
    for(int i = 0; i < n - 1; i++) {
        if(i + 2 < n && a[i].first == a[i + 1].first && a[i + 2].first == a[i + 1].first) {
            o[1][i] = a[i + 1].second, o[1][i + 1] = a[i].second;
            o[2][i] = a[i + 2].second, o[2][i + 2] = a[i].second;
            ot();
            return 0;
        } else if(a[i].first == a[i + 1].first){
            o[k][i] = a[i + 1].second, o[k][i + 1] = a[i].second;
            k++;
            if(k == 3) {
                ot();
                return 0;
            }
        }
    }
    printf("NO
");

    return 0;
}

C.MUH and House of Cards

 题意：用牌来搭房子，上面一层的房间数要小于下面一层。现在给你牌的数量，问你房子可能的层数有多少种，详见图。

解法：我们观察可以发现每层需要的牌数为2 + 3 * k，k为房子数-1。那么我们可以枚举层数，然后判断能否满足题目要求，即下面一层的k至少要是上面一层的k+1，详见代码。

代码：

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;

pair<int, int> a[2010];
int o[3][2010], n;

int main() {
    long long n, k = 1, l = 0;
    scanf("%I64d", &n);
    int ans = 0;
    for(;;k++) {
        long long m = n;
        m -= 2 * k;
        if(m % 3 != 0) { l += k; continue; }
        m /= 3;
        if(m >= l) ans++;
        else break;
        l += k;
    }
    printf("%d
", ans);

    return 0;
}