Codeforces Round #386 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #386 (Div. 2)
过题数：4
排名：890/12568

A. Compote

题意

$Nikolay$ 想做一个果盘，要做一个果盘需要的柠檬、苹果、梨的比例为 $1:2:4$，现在他有 $a$ 个柠檬、$b$ 个苹果和 $c$ 个梨，每个水果都不能再分割，问他要做果盘，能用到的最多的柠檬+苹果+梨的个数是多少？

输入

输入有三行，每行包含一个整数，分别为 $a,b,c~(1\leq a,b,c\leq1000)$。

输出

输出答案，如果一个水果都不能用上，就输出 $0$

样例

题解

按比例取最少的那份，将最小的份数乘 $7$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int a, b, c;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &a, &b, &c) != EOF) {
        b /= 2;
        c /= 4;
        int ans = min(a, min(b, c));
        printf("%d\n", ans * 7);
    }
    return 0;
}

B. Decoding

题意

定义字符串的“中位字符”，如果字符串的长度为奇数，那么字符串的中位字符就是正中间的字符，如果字符串的长度为偶数，那么字符串的中位字符就是中间两个字符中，右边的那个字符；
$Polycarp$ 正在对一些字符串进行编码，编码的方式是先选择一个字符串的中位字符，然后删掉这个字符，继续重复以上操作，直到字符串为空。
现在给定一个长度为 $n$ 的编码字符串，输出解码后的字符串。

输入

第一行为一个整数 $n~(1\leq n\leq2000)$，第二行为一个长度为 $n$ 的字符串，字符串只包含小写字符。

输出

输出 $Polycarp$ 编码的那个字符串。

样例

题解

找规律可以发现，如果字符串的长度为奇数，则除了第一个字符在中间位置，其他字符的还原顺序为“左$\rightarrow$右$\rightarrow$左$\rightarrow\cdots$”，如果字符串的长度为偶数，除了第一个字符在中间两个里靠左的那个位置，其他字符的还原顺序为“右$\rightarrow$左$\rightarrow$右$\rightarrow\cdots$”。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 2000 + 100;
int n;
char str[maxn], ans[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        memset(ans, 0, sizeof(ans));
        scanf("%s", str + 1);
        if(n % 2 == 0) {
            int l = n / 2;
            int r = l + 1;
            for(int i = 1; str[i]; ++i) {
                if(i % 2 == 0) {
                    ans[r++] = str[i];
                } else {
                    ans[l--] = str[i];
                }
            }
        } else {
            int r = (n + 1) / 2;
            int l = r - 1;
            for(int i = 1; str[i]; ++i) {
                if(i % 2 == 0) {
                    ans[l--] = str[i];
                } else {
                    ans[r++] = str[i];
                }
            }
        }
        ans[n + 1] = '\0';
        printf("%s\n", ans + 1);
    }
    return 0;
}

C. Tram

题意

一辆电车在 $x=0$ 和 $x=s$ 之间以 $t_1s/m$ 的速度行驶，一旦到达某一个端点，立即掉头回去。
$Igor$ 当前在 $x_1$，他想要去 $x_2$，他步行的速度是 $t_2s/m$，且已知此时电车的位置 $p$ 和电车的行驶方向，他可以在任何时间任何位置上车（不必在整数位置），且他上下车的时间可以忽略不计，问他最快要多久才能到达 $x2$ 点。

输入

第一行包含三个整数 $s,x_1,x_2~(2\leq s\leq1000,0\leq x_1,x_2\leq s,x_1\neq x_2)$，第二行包含两个整数 $t_1,t_2~(1\leq t_1,t_2\leq1000)$，第三行包含两个整数 $p,d~(1\leq p\leq s-1,d\in\{1,-1\})$，$d=1$ 表示电车正在往 $x=s$ 的方向行驶，$d=-1$ 表示电车正在往 $s=0$ 的方向行驶。

输出

输出 $Igor$ 要从 $x_1$ 到达 $x_2$ 的最短时间。

样例

题解

如果 $Igor$ 想通过电车到达 $x_2$，不论 $Igor$ 往哪个方向走，他到达 $x_2$ 的时间都是相等的，所以如果他想要上车，直接在原地等即可。所以可以用他走路到达 $x_2$ 的时间与电车到达 $x_2$ 的时间做比较，取较小的那个。计算电车到达的时间直接按题意一米一米地模拟即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 20;
int s, x1, x2;
int t1, t2, p, d;
int to[maxn];
bool small(int a, int b, int c) {
    return a <= b && b <= c;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &s, &x1, &x2) != EOF) {
        scanf("%d%d%d%d", &t1, &t2, &p, &d);
        int ans = abs(x1 - x2) * t2;
        bool flag = false;
        int t = 0;
        while(true) {
            if(p == x1) {
                flag = true;
            }
            if(p == x2 && flag) {
                break;
            }
            ++t;
            p += d;
            if(p == 0) {
                d = 1;
            } else if(p == s) {
                d = -1;
            }
        }
        printf("%d\n", min(ans, t * t1));
    }
    return 0;
}

D. Green and Black Tea

题意

有 $n$ 个字符，其中有 $a$ 个字符为 'G'，$b$ 个字符为 'B'，要求构造一个字符串，使这个字符串连续相同的字符个数不超过 $k$。

输入

输入包含四个整数 $n,k,a,b~(1\leq k\leq n\leq10^5,0\leq a,b\leq n)$，数据保证 $a+b=n$。

输出

如果无法构造出这个字符串，则输出 "NO"，否则输出满足条件的字符串，如果有多个解，输出任意一个即可。

样例

题解

假设大的那个数字为 $b$，小的那个数字为 $a$（如果 $a>b$，只要交换一下就行了），然后将 $b$ 拆分成 $a+1$ 块，这样可以保证连续的 $b$ 对应的字符数最少，所以可以通过比较 $\lceil\frac{b}{a+1}\rceil$ 与 $k$ 的大小，如果这个值大于 $k$，则直接输出 “NO”，否则就将 $b$ 分成 $a+1$ 块，每连续 $\lceil\frac{b}{a+1}\rceil$ 个 $b$ 对应的字符，就插入一个 $a$ 对应的字符，每经过这样一轮，就更新 $a$ 和 $b$ 的值，将它们减去自己对应的已经确定的字符数量，直到最后。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n, k, a, b;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d%d", &n, &k, &a, &b) != EOF) {
        char ch1 = 'G';
        char ch2 = 'B';
        if(a > b) {
            swap(a, b);
            swap(ch1, ch2);
        }
        if((b + a) / (a + 1) > k) {
            printf("NO\n");
            continue;
        }
        k = (b + a) / (a + 1);
        int cnt = k;
        for(int i = 0; i < n; ++i) {
            if(cnt == 0) {
                b -= k;
                --a;
                k = (b + a) / (a + 1);
                cnt = k;
                putchar(ch1);
                continue;
            }
            --cnt;
            putchar(ch2);
        }
        putchar('\n');
    }
    return 0;
}