結果

問題 No.7 プライムナンバーゲーム
ユーザー prog470prog470
提出日時 2016-09-14 12:08:24
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,850 bytes
コンパイル時間 476 ms
コンパイル使用メモリ 68,824 KB
最終ジャッジ日時 2024-11-14 19:49:44
合計ジャッジ時間 878 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘void primMake()’:
main.cpp:27:21: error: ‘sqrt’ was not declared in this scope
   27 |                 if (sqrt(10000.0) <= (double)pr) {
      |                     ^~~~

ソースコード

diff # 

#include<stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <string>
#include <stdio.h>

using namespace std;

int dp[10005];	
//自分のターンでiだったときの勝敗はdp[i]

set<int> prim;
int num[10001] = {}, pr;	//num[i]==0ならiは素数リストにある

void primMake() {
	pr = 2;
	num[0] = num[1] = 1;
	while (1) {
		prim.insert(pr);
		if (sqrt(10000.0) <= (double)pr) {
			break;
		}

		for (int i = pr; i <= 10000; i++) {
			if (i % pr == 0) {
				num[i] = 1;
			}
		}

		for (int i = pr; i <= 10000; i++) {
			if (num[i] != 1) {
				pr = i;
				break;
				//このbreakないとprは永久に同じ
			}
		}
	}
	for (int i = 2; i <= 10000; i++) {
		if (num[i] == 0) prim.insert(i);
	}
}

int f(int n) {

	if (dp[n] != -1) return dp[n];

	//次のdpに、少なくとも一つはかつ道(次のdp = 0)があるならdp[n]=1
	bool flag = false;
	set<int>::iterator dip = prim.begin();
	while ((*dip) <= n && dip != prim.end()) { 
		//cout << "n: " << n << " diff: " << (*dip) << " toNum: " << (n - (*dip)) << endl;
		//now以下の素数に順にアクセス（小さいほうから）
		if (f(n - (*dip)) == 0) flag = true;
		//次が0とは、つまり相手が負けること
		dip++;
	}
	if (flag) {
		//cout << "dp[" << n << "]: " << 1 << endl;
		return dp[n] = 1;
	}
	else {
		//cout << "dp[" << n << "]: " << 0 << endl;
		return dp[n] = 0;
	}
}

int main() {

	fill(dp, dp+10005, -1);
	dp[0] = dp[1] = 1;	
	// 1:win, 0:lose, -1:NULL
	//自分のターンで0or1なら既に相手が、それしか選べなかったということ

	int N;
	cin >> N;

	primMake();
	//cout << "prim list sinish!" << endl;

	f(N);

	if (dp[N] == 1) cout << "Win"<< endl;
	else cout << "Lose" << endl;

	return 0;
}
0