公式
D - Prime Sum Game 解説 by en_translator
By finding all the primes under \(200\) using Eratosthenes’ sieve, we can assume that we can determine if a number is a prime in an \(O(1)\) time.
Takahashi wins if and only if “there exists a number \(X\) such that, after Takahashi chooses \(X\), Aoki can only make a composite number no matter what number he chooses.” Determine if there is such \(X\).
Sample code (Python)
prime=[True]*201
prime[0]=False
prime[1]=False
for p in range(15):
if prime[p]:
for i in range(p*p,201,p):
prime[i]=False
A,B,C,D=map(int,input().split())
for x in range(A,B+1):
if all(not prime[x+y] for y in range(C,D+1)):
print("Takahashi")
exit()
print("Aoki")
Sample code (C)
#include<stdio.h>
int prime[210];
int main(){
for(int i=2;i<=200;i++)prime[i]=1;
for(int p=2;p*p<=200;p++)if(prime[p])for(int i=p*p;i<=200;i+=p)prime[i]=0;
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
for(int x=a;x<=b;x++){
int flag=1;
for(int y=c;y<=d;y++)flag&=!prime[x+y];
if(flag){
puts("Takahashi");
return 0;
}
}
puts("Aoki");
}
Bonus: Solve \(10^5\) cases in which the upper bounds of \(A,B,C\) and \(D\) are \(10^5\). (Worth \(500\) points?)
投稿日時:
最終更新: