hdu 2516 (바 시 게임)

돌 뽑 기 놀이
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2994    Accepted Submission(s): 1748
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
 
분석: 일부 데 이 터 를 모 의 하면 규칙 을 찾 을 수 있 습 니 다. 모 의 를 통 해 두 번 째 사람 이 이 기 는 것 이 피 폴 라 치 수열 이라는 것 을 알 수 있 습 니 다.

#include 
#include 
#include 
#include 
#include 
using namespace std;

int f[50];

int main ()
{
    int n;
    int i,j,ok;
    while (scanf ("%d",&n)==1&&n)
    {
        f[1] = 2;
        f[2] = 3;
        for (i=3; i<45; i++)
        f[i] = f[i-1] + f[i-2];
        ok = 0;
        for (j=1; j<45; j++)
        {
            if (n == f[j])
            {
                ok = 1;
                break;
            }
        }
        if (ok)
        printf ("Second win
");
        else
        printf ("First win
");
    }
    return 0;
}