Codeforces Round #445

ACM ICPC

每个队伍必须是3个人

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
int cmp(const void * x, const void * y) {
    //x < y
    return (*((double *)(x))) > (*((double *)(y))) ? 1 : -1;
}
int a[6];
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    for (int i = 0; i < 6; i++) scanf("%d", &a[i]);
    int sum = 0;
    for (int i = 0; i < 6; i++) sum += a[i];
    bool f = false;
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            for (int k = 0; k < 6; k++) {
                if (i != j && j != k && i != k && (a[i] + a[j] + a[k]) * 2 == sum)f = true;
            }
        }
    }
    if (f) printf("Yes
");
    else printf("No
");
    return 0;
}

View Code

Vlad and Cafes

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
int cmp(const void * x, const void * y) {
    //x < y
    return (*((double *)(x))) > (*((double *)(y))) ? 1 : -1;
}
int a[200005];
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int n, x, ans;
    scanf("%d", &n);
    memset(a, -1, sizeof(a));
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        a[x] = i;
        ans = x;
    }
    for (int i = 0; i < 200005; i++) {
        if (a[i] != -1 && a[i] < a[ans]) ans = i;
    }
    printf("%d
", ans);
    return 0;
}

View Code

Petya and Catacombs

记录之前每个房间的最近访问时间，对每一个数字如果能用之前的房间来凑就先凑，凑不了就增加一个新房间。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
int cmp(const void * x, const void * y) {
    //x < y
    return (*((double *)(x))) > (*((double *)(y))) ? 1 : -1;
}
int a[200005];
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int ans = 1;
    a[0] = 1;
    int n, x;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        if (a[x] > 0) {
            a[x]--;
            a[i]++;
        } else {
            ans++;
            a[i]++;
        }
    }
    printf("%d
", ans);
    return 0;
}

View Code

Restoration of string

If some string is the most frequent then all its substrings are the most frequent too.
If string ab or similar is the most frequent then letter a is always followed by letter b and b always follow a.
Let's consider directed graph on letters where edge a → b exists only if ab is the most frequent. If there is cycle in such graph then good string doesn't exist.
So such graph can be represented as several non-intersecting paths. All strings which correspond to paths must occur in non-empty good string. So if we print them in lexicographical order then we will get the answer.

有3个判定条件：每个点入度不超过1；每个点出度不超过1；不能存在环。

按字典序输出所有路径

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using std::vector;
using std::sort;
int cmp(const void * x, const void * y) {
    //x < y
    return (*((double *)(x))) > (*((double *)(y))) ? 1 : -1;
}
bool v[300], g[300];
int next[300], pre[300];
char str[100005];
bool dfs(int x) {
    if (g[x]) return false;
    g[x] = true;
    if (next[x] == 0) return true;
    return dfs(next[x]);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int n, len;
    while (scanf("%d", &n) != EOF) {
        memset(next, 0, sizeof(next));
        memset(pre, 0, sizeof(pre));
        memset(v, false, sizeof(v));
        bool flag = true;
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            len = strlen(str);
            for (int j = 0; j < len - 1; j++) {
                v[str[j]] = true;
                if (next[str[j]] == 0) next[str[j]] = str[j + 1];
                else if (next[str[j]] != str[j + 1]) flag = false;
                if (pre[str[j + 1]] == 0) pre[str[j + 1]] = str[j];
                else if (pre[str[j + 1]] != str[j]) flag = false;
            }
            v[str[len - 1]] = true;
        }
        for (int i = 'a'; i <= 'z'; i++) {
            memset(g, false, sizeof(g));
            if (!dfs(i)) flag = false;
        }
        if (!flag) printf("NO
");
        else {
            len = 0;
            for (int i = 'a'; i <= 'z'; i++) {
                if (v[i]) {
                    bool root = true;
                    for (int j = 'a'; j <= 'z'; j++) if (next[j] == i) root = false;
                    if (!root) continue;
                    int ptr = i;
                    while (ptr != 0) {
                        str[len++] = ptr;
                        v[ptr] = false;
                        ptr = next[ptr];
                    }
                }
            }
            str[len] = '';
            printf("%s
", str);
        }
    }
    return 0;
}

View Code

Maximum Element

You asked to find the number of permutations p of length n such that exists index i, such that pi ≠ n, pi is greater than any pj for j in [1, i - 1] and greater then any pj for j in [i + 1, i + k]. We will call such permutations good.

Define D(n) as number of good permutations that have pn = n. Notice that if k ≥ n, then D(n) = 0. Let w be a permutations such that wn = n. If index of element n - 1 is lesser than n - k, then w is good. Otherwise if n - 1 index is j, j ≥ n - k, then because there are less then k elements between n - 1 and n, w could be good only if i from the definition would be lesser than j. In that case permutation w1, ..., wj would form a good permutation of length j of some numbers with wj being the maximum.