結果

問題 No.7 プライムナンバーゲーム
ユーザー E31415926E31415926
提出日時 2016-04-04 19:04:58
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 948 bytes
コンパイル時間 539 ms
コンパイル使用メモリ 55,048 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-14 21:28:57
合計ジャッジ時間 1,252 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 WA -
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 WA -
testcase_07 AC 2 ms
6,940 KB
testcase_08 WA -
testcase_09 AC 2 ms
6,944 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 WA -
testcase_16 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
using namespace std;
#define prime		0
#define notprime	1
#define turn_me		1
#define turn_eve	-1

char *p;
void primelist(char p[10000]);
int game(int turn, int n);

int main()
{
	int n, result;
	p = new char[10000]{ notprime,notprime };
	cin >> n;
	if (n == 2 || n == 3) {
		cout << "Win" << endl;
		return 0;
	}
	primelist(p);
	result = game(turn_me, n);
	if (result == turn_me)cout << "Win" << endl;
	else cout << "Lose" << endl;
	return 0;
}

void primelist(char p[10000])
{
	int i, j;
	for (i = 4; i < 10000; i += 2)p[i] = notprime;
	for (i = 3; i < 100; i += 2) {
		if (p[i] == prime) {
			for (j = i*i; j < 10000; j += i) p[j] = notprime;
		}
	}
	return;
}

int game(int turn, int n)
{
	int i;
	if (p[n - 2] == prime || p[n - 3] == prime)return turn;
	if (game(-turn, n - 2) == turn)return turn;
	for (i = 2; i < n - 1; i += 2) {
		if (p[i] == prime) {
			if (game(-turn, n - i) == turn)return turn;
		}
	}
	return -turn;
}
0