結果

問題 No.7 プライムナンバーゲーム
ユーザー C_kumoC_kumo
提出日時 2019-01-20 05:20:35
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 2,515 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 33,280 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-07-19 05:41:06
合計ジャッジ時間 6,619 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define WIN "Win"
#define LOS "Lose"

#define DEBUG 0

short p[10000];
short pNum;

void iniBoard(short n,short *nowNum,char *turn);
void makePrimeList(short n);
char searchMM(short nowNum,char turn,short depth);
char isLeaf(short nowNum);
char eval(char turn);
short makeHaveList(short nowNum);

int main(void)
{
	short n;
	short nowNum;
	char turn;
	char ret;

	scanf("%hd",&n);
	iniBoard(n,&nowNum,&turn);
	makePrimeList(n);

	ret = searchMM(nowNum,turn,0);

	if (ret==1) printf("%s\n",WIN);
	else printf("%s\n",LOS);

	return 0;
}

void iniBoard(short n,short *nowNum,char *turn)
{
	*nowNum = n;
	*turn = 0;
	return;
}

// return number of prime
void makePrimeList(short n)
{
	short i,j,*tmpP;
	tmpP = (short *)malloc(sizeof(short) * n);
	tmpP[0] = 1;
	for (i=1;i<n;i++) tmpP[i] = 0;

	pNum = 0;
	for (i=2;i<=sqrt(n);i++) {
		if (tmpP[i-1]==1) continue;
		
		p[pNum] = i;
		pNum++;
		for (j=i;j<=n;j+=i) {
			tmpP[j-1] = 1;
		}
	}

	for (i=(int)sqrt(n);i<=n;i++) {
		if (tmpP[i-1]==1) continue;

		p[pNum] = i;
		pNum++;
	}

	return;
}

char searchMM(short nowNum,char turn,short depth)
{
	short i,j,haveNum,tmp;
	char best,val;

	if (DEBUG) {
		for (i=0;i<depth;i++) printf("=");
		printf(" depth=%hd nowNum=%hd turn=%hhd\n",depth,nowNum,turn);
	}

	// check end
	if (isLeaf(nowNum)==1) return eval(turn);

	// expand
	haveNum = makeHaveList(nowNum);
	if (DEBUG) {
		for (i=0;i<depth;i++) printf("=");
		printf(" p=");
		for (i=0;i<haveNum;i++) printf(" %hd",p[i]);
		printf("\n");
	}

	if      (turn==0) best = -99;
	else if (turn==1) best = 99;

	for (i=0;i<haveNum;i++) {
		tmp = nowNum - p[i];
		if (DEBUG) {
			for (j=0;j<depth;j++) printf("=");
			printf(" select=%hd nextNum=%hd\n",p[i],tmp);
		}
		val = searchMM(tmp,1-turn,depth+1);
		if (DEBUG) {
			for (j=0;j<depth;j++) printf("=");
			printf(" val=%hhd\n",val);
		}
		if        (turn==0) {
			// turn of me
			if (best < val) best = val;
		} else if (turn==1) {
			// turn of opp
			if (best > val) best = val;
		}
	}

	if (DEBUG) {
		for (j=0;j<depth;j++) printf("=");
		printf(" best=%hhd\n",best);
	}
	return best;
}

char isLeaf(short nowNum)
{
	if (nowNum==0 || nowNum==1) return 1;
	else if (nowNum < 0)        return -1;
	else                        return 0;
}

char eval(char turn)
{
	if      (turn == 0) return 1; // win
	else if (turn == 1) return 0; // lose
}

short makeHaveList(short nowNum)
{
	short i;
	for (i=0;i<pNum;i++) {
		if (p[i] > nowNum) return i;
	}
	return i;
}
0