結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー dnish
提出日時 2017-01-13 18:58:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 613 bytes
コンパイル時間 1,623 ms
コンパイル使用メモリ 170,284 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-01 15:54:48
合計ジャッジ時間 2,265 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

bool dp[10001];

void check(int n,int N){
	for(int i=n;i<=N;i++){
		if(dp[i]) continue;
		else dp[i] = !dp[i-n];
	}
}
int main() {
	int N;
	cin>>N;
	fill(dp,dp+10001,false);
	int k;
	dp[0]=dp[1]=true;
	vector<int> sosu;
	sosu.push_back(2);
	for(int i=3;i<=N;i+=2){
		k=0;
		for(int j=3;j<=sqrt(i);j+=2){
			if(i%j==0) {
				k=1;
				break;
			}
		}
		if(k==0)	sosu.push_back(i);
	}
	for(int i=2;i<=N;i++){
		for(auto j:sosu){
			if(dp[i]) 	break;
			if(i-j<0)	break;
			dp[i] |= !dp[i-j];
		}
	}
	if(dp[N]) cout<<"Win"<<endl;
	else cout<<"Lose"<<endl;
	
	return 0;
}
0