[THUPC2021] 挑战图灵奖

Time_tears · 2021-06-13 10:45:27 · 题解

原题等价于给 n 个点的环染色，不能有连续 k+1 个点的中颜色存在 2 个相同。

考虑当 n 很大的时候此时答案不是 k+1 就是 k+2，因为可以用 k+1,k+2 去凑出 n。

当 n 不大的时候暴力枚举 ans 从 k+1 到 2k，当能用这些数凑出 n 时，此时就是最小的答案。

算出答案后与 x 比较即可。

#include<bits/stdc++.h>
#define Mx 1000005
using namespace std;
char N[Mx],X[Mx];
int n,k,x;
void Check(int a,int b) {
    if(a==b)puts("Correct, but it doesn't necessarily mean that you can win the Turing Award.");
    if(a<b)puts("Wrong, don't cheat me, you are too far away from the Turing Award.\n1");
    if(a>b)puts("Wrong, don't cheat me, you are too far away from the Turing Award.\n0");exit(0);
}
int main() {
    scanf("%s%d%s",N+1,&k,X+1);
    if(strlen(X+1)>=4)return puts("Wrong, don't cheat me, you are too far away from the Turing Award.\n1"),0;
    for(int i=1,len=strlen(X+1); i<=len; ++i)x=x*10+X[i]-'0';
    if(strlen(N+1)>5) {
        for(int i=1,len=strlen(N+1); i<=len; ++i)n=(n*10+N[i]-'0')%(k+1);
        if(n==0)Check(k+1,x);else Check(k+2,x);
    } else {
        for(int i=1,len=strlen(N+1); i<=len; ++i)n=n*10+N[i]-'0';
        if(n<k+1)Check(n,x);
        int tmp=n/(k+1),tt=n%(k+1);
        for(int ans=0; 1; ++ans)if(tmp*ans>=tt)Check(k+1+ans,x);
    }
    return 0;
}