程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1517 (類巴神博弈)

hdu 1517 (類巴神博弈)

編輯:C++入門知識

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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved