結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー C_kumo
提出日時 2019-01-20 05:37:10
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 261 ms / 5,000 ms
コード長 2,604 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 32,768 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 16:17:04
合計ジャッジ時間 1,291 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

#define DEBUG 0

short p[1300];
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");
	}

	for (i=haveNum-1;i>=0;i--) {
		tmp = nowNum - p[i];
		if (DEBUG) {
			for (j=0;j<depth;j++) printf("=");
			printf(" select=%hd nextNum=%hd\n",p[i],tmp);
			fflush(stdout);
		}
		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        (val == 1) {
				best = 1;
				break;
			} else if (val == 0) {
				best = 0;
			}
		} else if (turn==1) {
			// turn of opp
			if        (val == 0) {
				best = 0;
				break;
			} else if (val == 1) {
				best = 1;
			}
		}
	}

	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