Educational Codeforces Round 38

Codeforces

Contests 链接：Educational Codeforces Round 38
过题数：2
排名：1341/9908

A. Word Correction

题意

给定一个字符串，在字符串中如果出现连续的两个元音字母(‘a', 'e', 'i', 'o', 'u', 'y')，就用第一个元音字母代替这两个元音字母。

输入

输入为一个只包含小写字母的字符串 $s~(1\leq|s|\leq100)$。

输出

输出最终字符串。

样例

题解

按照题意模拟。

过题代码

#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>
using namespace std;
#define LL long long
const int maxn = 200;
int n;
char str[maxn], ch[10] = "aeiouy";
set<char> st;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    for(int i = 0; i < 6; ++i) {
        st.insert(ch[i]);
    }
    while(scanf("%d%s", &n, str) != EOF) {
        bool flag = false;
        for(int i = 0; i < n; ++i) {
            if(st.find(str[i]) != st.end()) {
                if(!flag) {
                    printf("%c", str[i]);
                }
                flag = true;
            } else {
                printf("%c", str[i]);
                flag = false;
            }
        }
        printf("\n");
    }
    return 0;
}

B. Run For Your Prize

题意

一个人站在 $x=1$ 的地方，另一个人站在 $x=10^6$ 的地方，在这之间有 $n$ 个奖品，每个奖品的位置分别为 $a_1,a_2,\cdots,a_n$，且没有任何两个奖品在同一个位置，每个人的移动速度都是 $1/s$，如果某个人的位置正好和某个奖品的位置相同，他可以立即捡起这个奖品，问两人合作将所有奖品捡起的最短时间。

输入

第一行为一个整数 $n~(1\leq n\leq10^5)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(2\leq a_i\leq10^6-1)$，输入按升序给出。

输出

输出两人合作捡起所有奖品需要的最少时间。

样例

题解

枚举所有相邻位置的分割点，两个人捡起所有物品的时间就是 $\max(a_i-1,10^6-a_{i+1})$，取最小值就是答案。

过题代码

#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>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, ans;
int num[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    while(scanf("%d", &n) != EOF) {
        ans = INT_MAX;
        num[0] = 1;
        num[n + 1] = 1000000;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 0; i <= n; ++i) {
            ans = min(ans, max(num[i] - 1, 1000000 - num[i + 1]));
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Constructing Tests

题意

给定一个整数 $x$，要求构造一个 $n\times n$ 的 $01$ 矩阵，使得这个矩阵中，任意一个 $m\times m$ 的子矩阵中都至少含有一个 $0$，且矩阵中 $1$ 的数量的最大值等于 $x$。

输入

第一行为一个整数 $t~(1\leq t\leq100)$，接下去有 $t$ 个整数 $x_1,x_2,\cdots,x_t~(0\leq x_i\leq10^9)$。

输出

对于每个 $x$，都输出一行两个整数 $n,m$，要求 $n,m$ 满足题给条件且 $1\leq m\leq n\leq10^9$，如果不存在满足条件的答案，输出 $-1$。

样例

题解

可以发现，要使得 $01$ 矩阵中的 $1$ 的数量最多，就要让 $n\times n$ 的矩阵中每个 $(im,jm)~(i,j\in N^+,im,jm\leq n)$ 的位置都放上一个 $0$，因此矩阵中最多的 $1$ 的数量就等于 $n^2-\lfloor\frac{n}{m}\rfloor^2$，可以对于 $n^2\in[\sqrt{x}，4\times10^9]$ 内所有的整数，二分 $m$ 的值使 $n,m$ 满足公式的值等于 $x$。

过题代码

#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>
using namespace std;
#define LL long long
int T;
LL x, n, m;
LL judge(LL mid) {
    return n * n - (n / mid) * (n / mid);
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    while(scanf("%d", &T) != EOF) {
        while(T--) {
            m = -1;
            scanf("%I64d", &x);
            LL sq = sqrt(x) + 1;
            for(n = sq; n * n <= 4000000000LL; ++n) {
                LL low = 1;
                LL high = n;
                LL mid;
                while(high - low > 1) {
                    mid = (high + low) / 2;
                    if(judge(mid) >= x) {
                        high = mid;
                    } else {
                        low = mid;
                    }
                }
                if(judge(high) == x) {
                    m = high;
                    break;
                }
            }
            if(m == -1) {
                printf("-1\n");
            } else {
                printf("%I64d %I64d\n", n, m);
            }
        }
    }
    return 0;
}