[SOLUTION] USACO 2021 JAN Bronze

· · 个人记录

Uddered but not Herd

Statement:

{% tabs, Uddered but not Herd, 1%} <!-- tab En --> A little known fact about cows is that they have their own version of the alphabet, the "cowphabet". It consists of the 26 letters 'a' through 'z', but when a cow speaks the cowphabet, she lists these letters in a specific ordering that might be different from the order 'abcdefghijklmnopqrstuvwxyz' we are used to hearing. To pass the time, Bessie the cow has been humming the cowphabet over and over again, and Farmer John is curious how many times she's hummed it.

Given a lowercase string of letters that Farmer John has heard Bessie say, compute the minimum number of times Bessie must have hummed the entire cowphabet in order for Farmer John to have heard the given string. Farmer John isn't always paying attention to what Bessie hums, and so he might have missed some of the letters that Bessie has hummed. The string you are told consists of just the letters that he remembers hearing.

INPUT FORMAT (input arrives from the terminal / stdin): The first line of input contains the 26 lowercase letters 'a' through 'z' in the order they appear in the cowphabet. The next line contains the string of lowercase letters that Farmer John heard Bessie say. This string has length at least 1 and at most 1000. OUTPUT FORMAT (print output to the terminal / stdout): Print the minimum number of times Bessie must have hummed the entire cowphabet. SAMPLE INPUT: abcdefghijklmnopqrstuvwxyz mood SAMPLE OUTPUT: 3 In this example, the cowphabet is ordered the same as the normal alphabet.

Bessie must have hummed the cowphabet at least three times. It is possible for Bessie to have only hummed the cowphabet three times, and for Farmer John to have heard the letters in uppercase as denoted below.

abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz SCORING: In test cases 2-5, the cowphabet is the same as the normal alphabet. Test cases 6-10 satisfy no additional constraints. <!-- endtab --> <!-- tab Zh --> 一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。牛文由 26 个字母 'a' 到 'z' 组成，但是当奶牛说牛文时，可能与我们所熟悉的 'abcdefghijklmnopqrstuvwxyz' 不同，她会按某种特定的顺序排列字母。 为了打发时间，奶牛 Bessie 在反复哼唱牛文字母歌，而 Farmer John 好奇她唱了多少遍。

给定一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母，计算 Bessie 至少唱了几遍完整的牛文字母歌，使得 Farmer John 能够听到给定的字符串。Farmer John 并不始终注意 Bessie 所唱的内容，所以他可能会漏听 Bessie 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。

输入格式（从终端/标准输入读入）： 输入的第一行包含 26 个小写字母 'a' 到 'z' 的牛文字母表顺序。下一行包含一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母。字符串的长度不小于 1 且不大于 1000。 输出格式（输出至终端/标准输出）： 输出 Bessie 所唱的完整的牛文字母歌的最小次数。 输入样例： abcdefghijklmnopqrstuvwxyz mood 输出样例： 3 在这个样例中，牛文字母表与日常的字母表的排列一致。

Bessie 至少唱了三遍牛文字母歌。有可能 Bessie 只唱了三遍牛文字母歌，而 Farmer John 听到了以下被标记为大写的字母。

abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz 测试点性质： 测试点 2-5 中，牛文字母表与日常的字母表相同。 测试点 6-10 没有额外限制。 <!-- endtab --> {% endtabs %}

Suppose Bessie says s_{0...n - 1}. First we can decode what Bessie says into ordered numbers. Second we count how many i \ne 0 appears such that s_{i} \le s_{i - 1}. Every time such i appears, it means that another song must begin. So cnt + 1 will be the right answer.

#include <cstdio>
#include <cstring>

char dict[30], input[1005];
int map[30];
int n;

int Decode(char x) {
    return map[x - 'a'];
}

int main() {
    scanf("%s%s", dict, input);
    n = strlen(input);

    for (int i = 0; i < 26; ++i)
        map[dict[i] - 'a'] = i;

    int ans = 1;
    for (int i = 1; i < n; ++i)
        if (Decode(input[i]) <= Decode(input[i - 1]))
            ++ans;
    printf("%d\n", ans);
    return 0;
}

Even More Odd Photos

Statement:

{% tabs, Even More Odd Photos, 1%} <!-- tab En --> Farmer John is yet again trying to take a photograph of his N cows (2≤N≤1000). Each cow has an integer "breed ID" number in the range 1…100. Farmer John has a very peculiar idea in mind for his photo: he wants to partition all the cows into disjoint groups (in other words, place each cow in exactly one group) and then line up the groups so the sum of the breed IDs of the cows in the first group is even, the sum of the IDs in the second group is odd, and so on, alternating between even and odd.

What is the maximum possible number of groups Farmer John can form?

INPUT FORMAT (input arrives from the terminal / stdin): The first line of input contains N. The next line contains N space-separated integers giving the breed IDs of the N cows. OUTPUT FORMAT (print output to the terminal / stdout): The maximum possible number of groups in Farmer John's photo. It can be shown that at least one feasible grouping exists. SAMPLE INPUT: 7 1 3 5 7 9 11 13 SAMPLE OUTPUT: 3 In this example, one way to form the maximum number of three groups is as follows. Place 1 and 3 in the first group, 5, 7, and 9 in the second group, and 11 and 13 in the third group.

SAMPLE INPUT: 7 11 2 17 13 1 15 3 SAMPLE OUTPUT: 5 In this example, one way to form the maximum number of five groups is as follows. Place 2 in the first group, 11 in the second group, 13 and 1 in the third group, 15 in the fourth group, and 17 and 3 in the fifth group. <!-- endtab --> <!-- tab Zh --> Farmer John 正再一次尝试给他的 N 头奶牛拍照（2≤N≤1000）。 每头奶牛有一个范围在 1…100 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。

Farmer John 可以分成的最大组数是多少？

输入格式（从终端/标准输入读入）： 输入的第一行包含 N。下一行包含 N 个空格分隔的整数，为 N 头奶牛的品种编号。 输出格式（输出至终端/标准输出）： 输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。 输入样例： 7 1 3 5 7 9 11 13 输出样例： 3 在这个样例中，以下是一种分成最大组数三组的方案。将 1 和 3 分在第一组，5、7 和 9 分在第二组，11 和 13 分在第三组。

输入样例： 7 11 2 17 13 1 15 3 输出样例： 5 在这个样例中，以下是一种分成最大组数五组的方案。将 2 分在第一组，11 分在第二组，13 和 1 分在第三组，15 分在第四组，17 和 3 分在第五组。 <!-- endtab --> {% endtabs %}

It doesn't matter how tall the cow is or the order of them. It matters if a height is odd or even. Just simply count how many odds and evens, list all possible situations.

#include <cstdio>

int n;

int main() {
    scanf("%d", &n);
    int odd = 0, even = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        if (a & 1) ++odd;
        else ++even;
    }
    if (even == odd) {
        printf("%d\n", n);
    } else if (even > odd) {
        printf("%d\n", odd * 2 + 1);
    } else {  // even < odd
        if (odd == 2) {
            printf("1\n");
        } else {
            odd -= even;
            if (odd % 3 == 1) {
                printf("%d\n", even * 2 + odd / 3 * 2 - 1);
            } else if (odd % 3 == 0) {
                printf("%d\n", even * 2 + odd / 3 * 2);
            } else {  // odd % 3 == 2
                printf("%d\n", even * 2 + odd / 3 * 2 + 1);
            }
        }
    }
    return 0;
}

Just Stalling

Statement:

{% tabs, Just Stalling, 1%} <!-- tab En --> Farmer John has N cows (1≤N≤20) of heights a1…aN. His barn has N stalls with max height limits b1…bN (so for example, if b5=17, then a cow of height at most 17 can reside in stall 5). In how many distinct ways can Farmer John arrange his cows so that each cow is in a different stall, and so that the height limit is satisfied for every stall? INPUT FORMAT (input arrives from the terminal / stdin): The first line contains N. The second line contains N space-separated integers a1,a2,…,aN. The third line contains N space-separated integers b1,b2,…,bN. All heights and limits are in the range [1,109]. OUTPUT FORMAT (print output to the terminal / stdout): The number of ways Farmer John can place each cow into a different stall such that the height limit is satisfied for every stall. Note that the large size of the output might require the use of a 64-bit integer, like a "long long" in C++. SAMPLE INPUT: 4 1 2 3 4 2 4 3 4 SAMPLE OUTPUT: 8 In this example, we cannot place the third cow into the first stall since 3=a3>b1=2. Similarly, we cannot place the fourth cow into the first or third stalls. One way to satisfy the height limits is to assign cow 1 to stall 1, cow 2 to stall 2, cow 3 to stall 3, and cow 4 to stall 4.

SCORING: Test cases 1-5 satisfy N≤8. Test cases 6-12 satisfy no additional constraints. <!-- endtab --> <!-- tab Zh --> Farmer John 有 N 头奶牛（1≤N≤20），高度为 a1…aN。他的牛栏有 N 个牛棚，高度限制分别为 b1…bN（例如，如果 b5=17，那么一头高度不超过 17 的奶牛可以住在牛棚 5 里）。Farmer John 有多少种不同的方式安排他的奶牛，使得每头奶牛均住在不同的牛棚里，并且使得每个牛棚的高度限制均得到满足？ 输入格式（从终端/标准输入读入）： 输入的第一行包含 N。第二行包含 N 个空格分隔的整数 a1,a2,…,aN。第三行包含 N 个空格分隔的整数 b1,b2,…,bN。所有的高度和高度限制均在范围 [1,109] 内。 输出格式（输出至终端/标准输出）： 输出 Farmer John 可以将每头奶牛安排到不同的牛棚里，使得每个牛棚的高度限制均得到满足的方法数。注意输出的数量可能需要使用 64 位整数型，例如 C++ 中的 long long。 输入样例： 4 1 2 3 4 2 4 3 4 输出样例： 8 在这个例子中，我们不能将第三头奶牛安排到第一个牛棚里，因为 3=a3>b1=2。类似地，我们不能将第四头奶牛安排到第一或第三个牛棚里。一种符合高度限制的安排方式为将奶牛 1 安排到牛棚 1，奶牛 2 安排到牛棚 2，奶牛 3 安排到牛棚 3，奶牛 4 安排到牛棚 4。

测试点性质： 测试点 1-5 满足 N≤8。 测试点 6-12 没有额外限制。 <!-- endtab --> {% endtabs %}

For n \le 8, we can enumerate all possible permutations and check if they are legal. This takes O(n!) time.

#include <cstdio>
#include <vector>
#define LL long long
using std::vector;

int n;
int a[30], b[30];
vector<int> ac[30];

LL Dfs(int pos, int sta) {
    if (pos == n + 1)
        return 1;
    LL ret = 0;
    for (int i = 0, sz = (int)ac[pos].size(); i < sz; ++i) {
        if ((sta & (1 << ac[pos][i])) == 0)
            ret += Dfs(pos + 1, sta ^ (1 << ac[pos][i]));
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &b[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (a[j] <= b[i])
                ac[i].push_back(j);
    printf("%lld\n", Dfs(1, 0));
    return 0;
}

For n \le 20, sort b from smallest to largest. Let set s_{i} = \left \{ a_{j} \mid a_{j} \le b_{i} \right \}. Note that s_{1}\subseteq s_{2} \subseteq \dotsm \subseteq s_{n}. When we decide which to choose in position i, all the previous chosen elements belongs to s_{i}, that means there are only \left | s_{i} \right | - i + 1 choises in s_{i}. So the answer is \prod_{1 \le i \le n}^{} (\left | s_{i} \right | - i + 1)

#include <cstdio>
#include <algorithm>
using std::sort;
#define LL long long

int n;
int a[30], b[30];

int Count(int x) {
    int ret = 0;
    for (int i = 1; i <= n; ++i)
        if (a[i] <= x)
            ++ret;
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &b[i]);
    sort(b + 1, b + n + 1);
    LL ans = 1;
    for (int i = 1; i <= n; ++i)
        ans *= Count(b[i]) - i + 1;
    printf("%lld\n", ans);
    return 0;
}