hdu 1517 （類巴神博弈）

A Multiplication Game

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3977 Accepted Submission(s): 2264

Problem Description Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p >= n.

Input Each line of input contains one integer number n.

Output For each line of input output one line either

Stan wins.

or

Ollie wins.

assuming that both of them play perfectly.

Sample Input

162
17
34012226

Sample Output

Stan wins.
Ollie wins.
Stan wins.

Source University of Waterloo Local Contest 2001.09.22
分析與巴什博弈很類似，將巴神博弈中的加法轉化為此處的乘法，進行類比。 顯然2~9之間先手贏（實際上此處為一的時候也為先手贏，最少值乘以二就超過了一） 10~18的時候，不管先手怎麼安排第一步，後手贏！ 要想先手繼續贏，則需要在2~9 的基礎上乘以18（主要是後面的范圍，前面的范圍與前 一個必敗（勝）態，緊緊相鄰即可），此時，不管後手怎麼辦，都能夠通過 接下來的彌補，使有利局勢，保證在先手的手裡。即要想先手贏，需要在最初的基礎上 多次乘以18。同理要想後手贏，需要在10~18的基礎上多次乘以18.即判斷輸入的n除掉 多個18後剩下來的m與9作比較即可！m<=9，先手贏。10<=m<=18,後手贏！
代碼如下：

#include
int main()
{
    double n;//此處需要用double型 數據較大，沒想到竟然__int64 位竟然都不可以-_-! 
    while(~scanf("%lf",&n))
    {
        while(n>18)//循環到最後觀察最終剩余的數的范圍，在2~9之間為先手的必勝態，10~18為先手的必敗態 
        n/=18;
        printf(n<=9?"Stan wins.\n":"Ollie wins.\n");
    }
    return 0;
}