自动搬运

查看原文

来自洛谷，原作者为

	Time_tears oi复健ing

搬运于2025-08-24 22:31:30，当前版本为作者最后更新于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;
}