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))) ?  : -;

}

int a[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    for (int i = ; i < ; i++) scanf("%d", &a[i]);

    int sum = ;

    for (int i = ; i < ; i++) sum += a[i];

    bool f = false;

    for (int i = ; i < ; i++) {

        for (int j = ; j < ; j++) {

            for (int k = ; k < ; k++) {

                if (i != j && j != k && i != k && (a[i] + a[j] + a[k]) *  == sum)f = true;

            }

        }

    }

    if (f) printf("Yes\n");

    else printf("No\n");

    return ;

}

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))) ?  : -;

}

int a[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    int n, x, ans;

    scanf("%d", &n);

    memset(a, -, sizeof(a));

    for (int i = ; i < n; i++) {

        scanf("%d", &x);

        a[x] = i;

        ans = x;

    }

    for (int i = ; i < ; i++) {

        if (a[i] != - && a[i] < a[ans]) ans = i;

    }

    printf("%d\n", ans);

    return ;

}

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))) ?  : -;

}

int a[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    int ans = ;

    a[] = ;

    int n, x;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) {

        scanf("%d", &x);

        if (a[x] > ) {

            a[x]--;

            a[i]++;

        } else {

            ans++;

            a[i]++;

        }

    }

    printf("%d\n", ans);

    return ;

}

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))) ?  : -;

}

bool v[], g[];

int next[], pre[];

char str[];

bool dfs(int x) {

    if (g[x]) return false;

    g[x] = true;

    if (next[x] == ) 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, , sizeof(next));

        memset(pre, , sizeof(pre));

        memset(v, false, sizeof(v));

        bool flag = true;

        for (int i = ; i < n; i++) {

            scanf("%s", str);

            len = strlen(str);

            for (int j = ; j < len - ; j++) {

                v[str[j]] = true;

                if (next[str[j]] == ) next[str[j]] = str[j + ];

                else if (next[str[j]] != str[j + ]) flag = false;

                if (pre[str[j + ]] == ) pre[str[j + ]] = str[j];

                else if (pre[str[j + ]] != str[j]) flag = false;

            }

            v[str[len - ]] = true;

        }

        for (int i = 'a'; i <= 'z'; i++) {

            memset(g, false, sizeof(g));

            if (!dfs(i)) flag = false;

        }

        if (!flag) printf("NO\n");

        else {

            len = ;

            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 != ) {

                        str[len++] = ptr;

                        v[ptr] = false;

                        ptr = next[ptr];

                    }

                }

            }

            str[len] = '\0';

            printf("%s\n", str);

        }

    }

    return ;

}

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.