Contest Duration: - (local time) (100 minutes) Back to Home

D - Prime Sum Game Editorial 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?)

posted:
last update: