HDU 위 조 프 게임

2335 단어 HDU
원본 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1527
돌 뽑 기 놀이
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6717    Accepted Submission(s): 3653
Problem Description
두 무더기 의 돌 이 있 는데, 수량 이 임의로 다 를 수 있다.게임 은 두 사람 이 돌아 가면 서 돌 을 채취 하기 시작 했다.게임 규정 에 따 르 면 매번 두 가지 서로 다른 취 법 이 있 는데 하 나 는 임의의 한 무더기 에서 임의의 많은 돌 을 가 져 갈 수 있다.둘 째 는 두 더미 에서 같은 양의 돌 을 동시에 가 져 갈 수 있다.마지막 으로 돌 을 모두 가 져 온 자가 승자 다.지금 은 최초의 두 무더기 의 돌 수 를 제시 합 니 다. 만약 당신 이 먼저 취 할 차례 라면 쌍방 이 모두 가장 좋 은 전략 을 취한 다 고 가정 하고 마지막 에 당신 이 승자 인지 패자 인지 물 어보 세 요.
 
Input
몇 줄 을 포함 하 는 지 입력 하면 몇 가지 돌의 초기 상황 을 나타 낸다. 그 중에서 한 줄 에 두 개의 부정 정수 a 와 b 를 포함 하고 두 개의 돌의 수 를 나타 낸다. a 와 b 는 모두 1, 000, 000, 000 보다 크 지 않다.
 
Output
출력 에 대응 하 는 줄 도 몇 개 있 습 니 다. 줄 마다 숫자 1 이나 0 을 포함 하고 마지막 에 승자 라면 1 이 고 반대로 0 입 니 다.
 
Sample Input
 
   
2 1 8 4 4 7
 

Sample Output
 
   
0 1 0
题解:后来知道是威佐夫博弈,所以判断是不是奇异局势。

威佐夫博弈(Wythoff Game):有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜。 
那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?我们有如下公式: 
ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,…n 方括号表示取整函数)

代码如下:

#include
#include
int  main ()
{
   int n,m,k,t;
   while(~scanf("%d%d",&n,&m))
   {  
       if(n

좋은 웹페이지 즐겨찾기