#111986 (C++11) No.7 プライムナンバーゲーム

• 問題: No.7 プライムナンバーゲーム
• ユーザー: shisyamokongari
• 提出日時: 2016-08-22 01:23:36
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 31 ms / 5,000 ms
• コード長: 883 bytes
• コンパイル時間: 658 ms
• コンパイル使用メモリ: 65,488 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-01 15:47:48
• 合計ジャッジ時間: 1,734 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	28 ms; 5,248 KB
testcase_01	AC	31 ms; 5,248 KB
testcase_02	AC	28 ms; 5,248 KB
testcase_03	AC	31 ms; 5,248 KB
testcase_04	AC	29 ms; 5,248 KB
testcase_05	AC	30 ms; 5,248 KB
testcase_06	AC	30 ms; 5,248 KB
testcase_07	AC	30 ms; 5,248 KB
testcase_08	AC	30 ms; 5,248 KB
testcase_09	AC	30 ms; 5,248 KB
testcase_10	AC	30 ms; 5,248 KB
testcase_11	AC	29 ms; 5,248 KB
testcase_12	AC	28 ms; 5,248 KB
testcase_13	AC	29 ms; 5,248 KB
testcase_14	AC	29 ms; 5,248 KB
testcase_15	AC	29 ms; 5,248 KB
testcase_16	AC	31 ms; 5,248 KB

ソースコード

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

#define NMAX 10000
#define WIN 1
#define LOSE 0
#define NOT -1

int main(){

	vector<int> sosuu;
	int hurui[NMAX+1];
	int K,N;
	int wl[NMAX+1];

	for(int i=0;i<=NMAX;i++) hurui[i]=0;
	hurui[0]=1,hurui[1]=1;

	for(int i=0;i<=NMAX;i++){
		if(hurui[i]==0){
			sosuu.push_back(i);
			for(int j=i*2;j<NMAX;j+=i) hurui[j]=1;
		}
	}

	for(int i=0;i<=NMAX;i++) wl[i]=NOT;

	wl[2]=LOSE;
	wl[3]=LOSE;

	while(1){
		bool f=true;
		for(int i=2;i<=NMAX;i++){
			if(wl[i]==NOT) f=false;
		}
		if(f) break;
		for(int i=2;i<=NMAX;i++){
			if(wl[i]!=NOT){
				for(int j=0;j<sosuu.size();j++){
					if(i+sosuu[j]<=NMAX){
						if(wl[i]==LOSE) wl[i+sosuu[j]]=WIN;
						if(wl[i]==WIN&&wl[i+sosuu[j]]!=WIN) wl[i+sosuu[j]]=LOSE;
					}
				}
			}
		}
	}

	cin>>N;

	if(wl[N]==WIN) cout<<"Win"<<endl;
	else cout<<"Lose"<<endl;
}