算法學習之路|取石子（2)

1堆石子有n個,兩人輪流取.先取者第1次可以取任意多個，但不能全部取完.以後每次取的石子數不能超過上次取子數的2倍。取完者勝.先取者負輸出"Second win".先取者勝輸出"First win".

輸入格式：

輸入有多組.每組第1行是2<=n<2^31. n=0退出.

輸出格式：

先取者負輸出"Second win". 先取者勝輸出"First win".

參看Sample Output.

輸入樣例：

2

13

10000

輸出樣例：

Second win

First win

取石子的更新版（一）

解題思路：

模拟一下：

2顆：先取1，後取1，後勝

3顆：先取1，後取2，後勝；先取2，後取1，後勝

4顆：先取1，剩3，先勝；（後勝情況不會出現，沒有傻子）

5顆：先取1，剩4，後勝；先取2，剩3，後勝；先取3，剩2，後勝；先取4，剩1；後勝

6顆：先取1，剩5，先勝

7顆：先取2，剩5，後取1，剩4，先勝，後取2,3,4都是先勝

8顆：先取1，剩7，後勝

……

通過以上模拟，可以看出在2,3,5,8顆的情況下，先取無論怎麼取都無法獲勝，可以通過歸納法，看出這是斐波那契數列的一部分，答案也确是如此。