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: