結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー kt_tenel
提出日時 2018-03-19 22:06:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 1,800 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 92,132 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 16:09:53
合計ジャッジ時間 1,320 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;
int prime[100002]={};
int Er_N=10000;
void Er(){//Eratosthenes  1:PRIME  0:NOT PRIME
	for(int i = 2; i < Er_N; i++){
		prime[i] = 1;
	}
	int limit_Er_roop=sqrt(Er_N);
	for(int i = 2; i < limit_Er_roop; i++){
		if(prime[i]){
			for(int j = 0; i * (j + 2) < Er_N; j++){
				prime[i *(j + 2)] = 0;
			}
		}
	}
}
int idx;
int a[5000];
int wl[10001];//1:win 0:lose

void mem(int n){
		if(wl[n]!=-1)return;
		int f=0;
		FORD(i,idx,0){
			int t=n-a[i];
			if(t<=2)continue;
			if(wl[t]==-1)mem(t);
			if(wl[t]==0)f=1;
		}
		wl[n]=f;
}

int main(){
	Er();
	idx=0;
	string re[2]={"Lose","Win"};
	FOR(i,0,10000){
		if(prime[i])a[idx++]=i;
	}
	FOR(i,0,10001){
		wl[i]=-1;
	}
	wl[0]=wl[1]=1;
	wl[2]=wl[3]=0;
	FOR(i,2,4){
		FOR(j,0,idx){
			int t=i+a[j];
			if(t>10000)break;
			wl[t]=1;
		}
	}
	int n;
	cin>>n;
	mem(n);
	cout<<re[wl[n]]<<endl;

    return 0;
}
0