HDU 2516 돌 빼 기 게임 (바 시 게임)

돌 뽑 기 놀이
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2524    Accepted Submission(s): 1443
Problem Description
한 무더기 의 돌 은 n 개가 있 는데, 두 사람 이 번갈아 가 며 가 져 간다. 선 취 자 는 첫 번 째 로 여러 개 를 가 져 갈 수 있 지만, 다 가 져 갈 수 는 없다. 이후 매번 가 져 온 돌 수 는 지난번 취 자 수의 2 배 를 초과 해 서 는 안 된다.이 긴 사람 이 이 깁 니 다. 먼저 이 긴 사람 은 "Second win"을 출력 합 니 다. 먼저 이 긴 사람 은 "First win"을 출력 합 니 다.
 
Input
여러 그룹 을 입력 하 십시오. 각 그룹의 첫 번 째 줄 은 2 < = n < 2 ^ 31. n = 0 으로 종료 합 니 다.
 
Output
선 취자 마이너스 출력 "Second win". 선 취자 승 출력 "First win". 
샘플 출력 참조.
 
Sample Input

   
   
   
   

    
    
    
    2
13
10000
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Second win
Second win
First win
   
   
   
   

 
제목 의 뜻 이 명확 하 다. 이 문제 도 PN 그림 에서 착안 하여 다음 과 같다.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20……
p p n p n n p n  n    n   n   p    n   n   n   n    n   n   n……
위의 PN 그림 은 쉽게 그 릴 수 있 으 며 필 패 상 태 는 2, 3, 5, 8, 13 이다.사실 나 는 21 시의 상 태 를 그리 지 않 았 다. 필 패 상태 서열 이 피 보 나 절 수열 인 것 을 보 았 기 때문에 필 패 상태 가 피 보 나 치 에 부합 한다 고 직접 추측 하고 제출 한 후에 AC 가 되 었 다.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

int a,b;

int main(){
    //freopen("in.txt","r",stdin);
    //(author : CSDN iaccepted)
	int n,ts;
	bool mark;
	
	
	while(scanf("%d",&n) && n){
		a = 2,b = 3;
		mark = false;
		while(a<=n){
			if(a==n || b==n){
				mark = true;
				break;
			}
			ts = (a  + b);
			a = b;
			b = ts;
		}
		if(mark){
			printf("Second win
");
		}else{
			printf("First win
");
		}
	}
    return 0;
}