mygame.c

AStar2006 的3.变态比赛规则的一种算法.采用贪心算法,效率比较高.

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

float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1); // 计算第一个近似根
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x); // 牛顿迭代法
return x;
}

int Game(int N,long K)
{
	long max,LE;
	int p,LP;

	if( N<=0 || N>500 || K<0 || K>N*(N-1)/2 )
		return 0;

    if( K==0 || K==N-1)
        return 1;

    if( N==1 || K<N-1 )
        return 0;

	max=N*(N-1)/2;
	while (1)
	{
		
		p=(int)(1.0/ InvSqrt((max-K)*2));
		LP=N-p;
		if (LP<0) return 0;
		if (p==1 && LP>=1) return 1;
		LE=max-p*(p-1)/2;
		if (LE==K) return 1;
		if (LE<K) return 0;
		max=LE;
		N=LP;
	}
}

int main()
{
	long K;
	int N,Result;

	printf("Please input N,K:");
	scanf("%d,%d",&N,&K);

	Result=Game(N,K);
	if (Result) printf("YES");
	else printf("NO");
	return 1;
}