[BOJ 26973] Circular Barn

 

https://www.acmicpc.net/problem/26973

26973번: Circular Barn

 

- 문제 요약

 

John과 Nhoj는 원형 헛간 (1 <=N <=2*10^5개의 헛간이 원형으로 이어져 있는 곳)에서 게임을 하고 있습니다. 각 헛간에는 ai(1 <=ai <=5*10^6) 마리의 소가 있습니다. 게임은 아래와 같은 방식으로 진행됩니다.

• 두 사람은 항상 같은 헛간에 있습니다. 방에 들어간 후 두 사람은 각각 한 턴을 진행하고, John이 먼저 시작합니다. 두 사람은 1번 헛간에 제일 먼저 들어갑니다.
• 들어갔을 때 헛간에 소가 없으면 지게 됩니다. 헛간에 소가 있다면 1~(현재 방에 있는 소의 수)중 소수인 수를 선택하고 그 만큼의 소를 헛간 밖으로 내보냅니다.
• 두 사람은 턴이 끝나면 다음 번호 헛간으로 이동합니다.(현재 위치가 N번 헛간이라면 다시 1번 헛간으로 이동합니다)

두 사람이 항상 최적의 상태로 플레이 할 때 게임에서 승리하는 사람의 이름을 출력하세요.

(두 사람의 이름은 "Farmer John", "Farmer Nhoj"입니다)

 

 

- 알고리즘 정리

 

N이 1일 경우에는 ai가 4로 나누어지지 않는 경우에만 John이 승리합니다.

N이 1보다 클 때, 증명을 하다보면 a1이 짝수일 경우에 답이 a1/2 임을 알 수 있습니다.

 

N의 범위인 5*10^6만큼의 소수를 미리 배열에 넣어놓고(에라토스테네스의 체), 헛간의 배열이 원형이라는 점을 이용해서점화식을 작성해 주면 됩니다.

 

 

 - 코드 작성

 

#include<bits/stdc++.h>
using namespace std;
 
#define MAX 5000001
int t,n,mnmn[MAX]={0,1},mxmx[4]={2,1,2,3};
bool check[MAX];
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for(int i=2;i<MAX;i++){
		if(!check[i]){
			for(int j=i;j<MAX;j+=i){
				check[j]=true;
			}
			mxmx[i%4]=i;
		}
		mnmn[i]=(i-mxmx[i%4])/2+1;
	}
	cin>>t;
	while(t--){
		cin>>n;
		int ans=MAX;
		for(int i=0;i<n;i++){
			int a;
			cin>>a;
			if(mnmn[a]/2<ans/2){
				ans=mnmn[a];
			}
		}
		if(ans&1){
			cout<<"Farmer John"<<endl;
		}
		else{
			cout<<"Farmer Nhoj"<<endl;
		}
	}
}

코드 제출 결과

틀왜맞